Skip to main content

vortex_array/arrays/varbinview/
compact.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4//! Defines a compaction operation for VarBinViewArrays that evicts unused buffers so they can
5//! be dropped.
6
7use std::ops::Range;
8
9use vortex_error::VortexExpect;
10use vortex_error::VortexResult;
11use vortex_mask::Mask;
12
13use crate::ExecutionCtx;
14use crate::arrays::VarBinViewArray;
15use crate::arrays::varbinview::Ref;
16use crate::builders::VarBinViewBuilder;
17
18const DEFAULT_COMPACTION_THRESHOLD: f64 = 0.5;
19const MIN_RETAINED_BYTES_PER_ROW_TO_CHECK_COMPACTION: u64 = 128;
20
21impl VarBinViewArray {
22    /// Returns a compacted copy of the input array, where all wasted space has been cleaned up. This
23    /// operation can be very expensive, in the worst case copying all existing string data into
24    /// a new allocation.
25    ///
26    /// After slicing/taking operations `VarBinViewArray`s can continue to hold references to buffers
27    /// that are no longer visible. We detect when there is wasted space in any of the buffers, and if
28    /// so, will aggressively compact all visible outlined string data into new buffers while keeping
29    /// well-utilized buffers unchanged.
30    pub fn compact_buffers(&self, ctx: &mut ExecutionCtx) -> VortexResult<VarBinViewArray> {
31        // If there is nothing to be gained by compaction, return the original array untouched.
32        if !self.should_compact(ctx)? {
33            return Ok(self.clone());
34        }
35
36        self.compact_with_threshold(DEFAULT_COMPACTION_THRESHOLD, ctx)
37    }
38
39    fn should_compact(&self, ctx: &mut ExecutionCtx) -> VortexResult<bool> {
40        let nbuffers = self.data_buffers().len();
41
42        // If the array is entirely inlined strings, do not attempt to compact.
43        if nbuffers == 0 {
44            return Ok(false);
45        }
46
47        // These will fail to write, so in most cases we want to compact this.
48        if nbuffers > u16::MAX as usize {
49            return Ok(true);
50        }
51
52        let buffer_total_bytes: u64 = self.buffers.iter().map(|buf| buf.len() as u64).sum();
53        if buffer_total_bytes == 0 {
54            return Ok(true);
55        }
56
57        let len = u64::try_from(self.len()).unwrap_or(u64::MAX);
58        if len > 0 && buffer_total_bytes / len <= MIN_RETAINED_BYTES_PER_ROW_TO_CHECK_COMPACTION {
59            return Ok(false);
60        }
61
62        let bytes_referenced: u64 = self.count_referenced_bytes(ctx)?;
63        Ok((bytes_referenced as f64 / buffer_total_bytes as f64) < DEFAULT_COMPACTION_THRESHOLD)
64    }
65
66    /// Iterates over all valid, non-inlined views, calling the provided
67    /// closure for each one.
68    #[allow(clippy::inline_always)]
69    #[inline(always)]
70    fn iter_valid_views<F>(&self, ctx: &mut ExecutionCtx, mut f: F) -> VortexResult<()>
71    where
72        F: FnMut(&Ref),
73    {
74        match self.as_ref().validity()?.execute_mask(self.len(), ctx)? {
75            Mask::AllTrue(_) => {
76                for &view in self.views().iter() {
77                    if !view.is_inlined() {
78                        f(view.as_view());
79                    }
80                }
81            }
82            Mask::AllFalse(_) => {}
83            Mask::Values(v) => {
84                for (&view, is_valid) in self.views().iter().zip(v.bit_buffer().iter()) {
85                    if is_valid && !view.is_inlined() {
86                        f(view.as_view());
87                    }
88                }
89            }
90        }
91        Ok(())
92    }
93
94    /// Count the number of bytes addressed by the views, not including null
95    /// values or any inlined strings.
96    fn count_referenced_bytes(&self, ctx: &mut ExecutionCtx) -> VortexResult<u64> {
97        let mut total = 0u64;
98        self.iter_valid_views(ctx, |view| total += view.size as u64)?;
99        Ok(total)
100    }
101
102    pub(crate) fn buffer_utilizations(
103        &self,
104        ctx: &mut ExecutionCtx,
105    ) -> VortexResult<Vec<BufferUtilization>> {
106        let mut utilizations: Vec<BufferUtilization> = self
107            .data_buffers()
108            .iter()
109            .map(|buf| {
110                let len = u32::try_from(buf.len()).vortex_expect("buffer sizes must fit in u32");
111                BufferUtilization::zero(len)
112            })
113            .collect();
114
115        self.iter_valid_views(ctx, |view| {
116            utilizations[view.buffer_index as usize].add(view.offset, view.size);
117        })?;
118
119        Ok(utilizations)
120    }
121
122    /// Returns a compacted copy of the input array using selective buffer compaction.
123    ///
124    /// This method analyzes each buffer's utilization and applies one of three strategies:
125    /// - **KeepFull** (zero-copy): Well-utilized buffers are kept unchanged
126    /// - **Slice** (zero-copy): Buffers with contiguous ranges of used data are sliced to that range
127    /// - **Rewrite**: Poorly-utilized buffers have their data copied to new compact buffers
128    ///
129    /// By preserving or slicing well-utilized buffers, compaction becomes zero-copy in many cases.
130    ///
131    /// # Arguments
132    ///
133    /// * `buffer_utilization_threshold` - Threshold in range [0, 1]. Buffers with utilization
134    ///   below this value will be compacted. Use 0.0 for no compaction, 1.0 for aggressive
135    ///   compaction of any buffer with wasted space.
136    pub fn compact_with_threshold(
137        &self,
138        buffer_utilization_threshold: f64, // [0, 1]
139        ctx: &mut ExecutionCtx,
140    ) -> VortexResult<VarBinViewArray> {
141        let mut builder = VarBinViewBuilder::with_compaction_in(
142            self.dtype().clone(),
143            self.len(),
144            buffer_utilization_threshold,
145            ctx.allocator().clone(),
146        );
147        builder.append_varbinview_array(self, ctx)?;
148        Ok(builder.finish_into_varbinview())
149    }
150}
151
152pub(crate) struct BufferUtilization {
153    len: u32,
154    used: u32,
155    min_offset: u32,
156    max_offset_end: u32,
157}
158
159impl BufferUtilization {
160    pub(crate) fn zero(len: u32) -> Self {
161        BufferUtilization {
162            len,
163            used: 0u32,
164            min_offset: u32::MAX,
165            max_offset_end: 0,
166        }
167    }
168
169    pub(crate) fn add(&mut self, offset: u32, size: u32) {
170        self.used += size;
171        self.min_offset = self.min_offset.min(offset);
172        self.max_offset_end = self.max_offset_end.max(offset + size);
173    }
174
175    pub fn overall_utilization(&self) -> f64 {
176        match self.len {
177            0 => 0.0,
178            len => self.used as f64 / len as f64,
179        }
180    }
181
182    pub fn range_utilization(&self) -> f64 {
183        match self.range_span() {
184            0 => 0.0,
185            span => self.used as f64 / span as f64,
186        }
187    }
188
189    pub fn range(&self) -> Range<u32> {
190        self.min_offset..self.max_offset_end
191    }
192
193    fn range_span(&self) -> u32 {
194        self.max_offset_end.saturating_sub(self.min_offset)
195    }
196}
197
198#[cfg(test)]
199mod tests {
200    use std::sync::LazyLock;
201
202    use rstest::rstest;
203    use vortex_buffer::buffer;
204    use vortex_session::VortexSession;
205
206    use crate::IntoArray;
207    use crate::VortexSessionExecute;
208    use crate::arrays::VarBinArray;
209    use crate::arrays::VarBinViewArray;
210    use crate::assert_arrays_eq;
211    use crate::dtype::DType;
212    use crate::dtype::Nullability;
213
214    static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
215    #[test]
216    fn test_optimize_compacts_buffers() {
217        let mut ctx = SESSION.create_execution_ctx();
218        // Create a VarBinViewArray with some long strings that will create multiple buffers
219        let excluded = "unused long string".repeat(100);
220        let original = VarBinViewArray::from_iter_nullable_str([
221            Some("short"),
222            Some("this is a longer string that will be stored in a buffer"),
223            Some(excluded.as_str()),
224            Some("another very long string that definitely needs a buffer to store it"),
225            Some("tiny"),
226        ]);
227
228        // Verify it has buffers
229        assert!(!original.data_buffers().is_empty());
230        let original_buffers = original.data_buffers().len();
231
232        // Take only the first and last elements (indices 0 and 4)
233        let indices = buffer![0u32, 4u32].into_array();
234        let taken = original.take(indices).unwrap();
235        let taken = taken.execute::<VarBinViewArray>(&mut ctx).unwrap();
236        // The taken array should still have the same number of buffers
237        assert_eq!(taken.data_buffers().len(), original_buffers);
238
239        // Now optimize the taken array
240        let optimized_array = taken.compact_buffers(&mut ctx).unwrap();
241
242        assert!(optimized_array.data_buffers().is_empty());
243
244        // Verify the data is still correct
245        assert_arrays_eq!(
246            optimized_array,
247            <VarBinArray as FromIterator<_>>::from_iter([Some("short"), Some("tiny")]),
248            &mut ctx
249        );
250    }
251
252    #[test]
253    fn test_optimize_with_long_strings() {
254        let mut ctx = SESSION.create_execution_ctx();
255        // Create strings that are definitely longer than 12 bytes
256        let long_string_1 = "this is definitely a very long string that exceeds the inline limit";
257        let long_string_2 = "another extremely long string that also needs external buffer storage";
258        let long_string_3 = "yet another long string for testing buffer compaction functionality";
259
260        let original = VarBinViewArray::from_iter_str([
261            long_string_1,
262            long_string_2,
263            long_string_3,
264            "short1",
265            "short2",
266        ]);
267
268        // Take only the first and third long strings (indices 0 and 2)
269        let indices = buffer![0u32, 2u32].into_array();
270        let taken = original.take(indices).unwrap();
271        let taken_array = taken
272            .execute::<VarBinViewArray>(&mut SESSION.create_execution_ctx())
273            .unwrap();
274
275        let optimized_array = taken_array.compact_with_threshold(1.0, &mut ctx).unwrap();
276
277        // The optimized array should have exactly 1 buffer (consolidated)
278        assert_eq!(optimized_array.data_buffers().len(), 1);
279        assert_eq!(
280            optimized_array.buffer(0).len(),
281            long_string_1.len() + long_string_3.len()
282        );
283
284        // Verify the data is still correct
285        assert_arrays_eq!(
286            optimized_array,
287            VarBinArray::from(vec![long_string_1, long_string_3]),
288            &mut ctx
289        );
290    }
291
292    #[test]
293    fn test_optimize_no_buffers() {
294        let mut ctx = SESSION.create_execution_ctx();
295        // Create an array with only short strings (all inlined)
296        let original = VarBinViewArray::from_iter_str(["a", "bb", "ccc", "dddd"]);
297
298        // This should have no buffers
299        assert_eq!(original.data_buffers().len(), 0);
300
301        // Optimize should return the same array
302        let optimized_array = original.compact_buffers(&mut ctx).unwrap();
303
304        assert_eq!(optimized_array.data_buffers().len(), 0);
305
306        assert_arrays_eq!(optimized_array, original, &mut ctx);
307    }
308
309    #[test]
310    fn test_optimize_single_buffer() {
311        let mut ctx = SESSION.create_execution_ctx();
312        // Create an array that naturally has only one buffer
313        let str1 = "this is a long string that goes into a buffer";
314        let str2 = "another long string in the same buffer";
315        let original = VarBinViewArray::from_iter_str([str1, str2]);
316
317        // Should have 1 compact buffer
318        assert_eq!(original.data_buffers().len(), 1);
319        assert_eq!(original.buffer(0).len(), str1.len() + str2.len());
320
321        // Optimize should return the same array (no change needed)
322        let optimized_array = original.compact_buffers(&mut ctx).unwrap();
323
324        assert_eq!(optimized_array.data_buffers().len(), 1);
325
326        assert_arrays_eq!(optimized_array, original, &mut ctx);
327    }
328
329    #[test]
330    fn test_selective_compaction_with_threshold_zero() {
331        let mut ctx = SESSION.create_execution_ctx();
332        // threshold=0 should keep all buffers (no compaction)
333        let original = VarBinViewArray::from_iter_str([
334            "this is a longer string that will be stored in a buffer",
335            "another very long string that definitely needs a buffer to store it",
336        ]);
337
338        let original_buffers = original.data_buffers().len();
339        assert!(original_buffers > 0);
340
341        // Take only first element
342        let indices = buffer![0u32].into_array();
343        let taken = original.take(indices).unwrap();
344        let taken = taken
345            .execute::<VarBinViewArray>(&mut SESSION.create_execution_ctx())
346            .unwrap();
347        // Compact with threshold=0 (should not compact)
348        let compacted = taken.compact_with_threshold(0.0, &mut ctx).unwrap();
349
350        // Should still have the same number of buffers as the taken array
351        assert_eq!(compacted.data_buffers().len(), taken.data_buffers().len());
352
353        // Verify correctness
354        assert_arrays_eq!(compacted, taken, &mut ctx);
355    }
356
357    #[test]
358    fn test_selective_compaction_with_high_threshold() {
359        let mut ctx = SESSION.create_execution_ctx();
360        // threshold=1.0 should compact any buffer with waste
361        let original = VarBinViewArray::from_iter_str([
362            "this is a longer string that will be stored in a buffer",
363            "another very long string that definitely needs a buffer to store it",
364            "yet another long string",
365        ]);
366
367        // Take only first and last elements
368        let indices = buffer![0u32, 2u32].into_array();
369        let taken = original.take(indices).unwrap();
370        let taken = taken
371            .execute::<VarBinViewArray>(&mut SESSION.create_execution_ctx())
372            .unwrap();
373
374        let original_buffers = taken.data_buffers().len();
375
376        // Compact with threshold=1.0 (aggressive compaction)
377        let compacted = taken.compact_with_threshold(1.0, &mut ctx).unwrap();
378
379        // Should have compacted buffers
380        assert!(compacted.data_buffers().len() <= original_buffers);
381        assert!(
382            compacted
383                .data_buffers()
384                .iter()
385                .map(|b| b.len())
386                .sum::<usize>()
387                < taken.data_buffers().iter().map(|b| b.len()).sum::<usize>()
388        );
389
390        // Verify correctness
391        assert_arrays_eq!(compacted, taken, &mut ctx);
392    }
393
394    #[test]
395    fn test_selective_compaction_preserves_well_utilized_buffers() {
396        let mut ctx = SESSION.create_execution_ctx();
397        // Create an array with multiple strings in one buffer (well-utilized)
398        let str1 = "first long string that needs external buffer storage";
399        let str2 = "second long string also in buffer";
400        let str3 = "third long string in same buffer";
401
402        let original = VarBinViewArray::from_iter_str([str1, str2, str3]);
403
404        // All strings should be in one well-utilized buffer
405        assert_eq!(original.data_buffers().len(), 1);
406
407        // Compact with high threshold
408        let compacted = original.compact_with_threshold(0.8, &mut ctx).unwrap();
409
410        // Well-utilized buffer should be preserved
411        assert_eq!(compacted.data_buffers().len(), 1);
412        assert_eq!(compacted.buffer(0).as_ptr(), original.buffer(0).as_ptr());
413        assert_eq!(
414            compacted.buffer(0).as_slice(),
415            original.buffer(0).as_slice()
416        );
417
418        // Verify all data is correct
419        assert_arrays_eq!(compacted, original, &mut ctx);
420    }
421
422    #[test]
423    fn test_selective_compaction_with_mixed_utilization() {
424        let mut ctx = SESSION.create_execution_ctx();
425        // Create array with some long strings
426        let strings: Vec<String> = (0..10)
427            .map(|i| {
428                format!(
429                    "this is a long string number {} that needs buffer storage",
430                    i
431                )
432            })
433            .collect();
434
435        let original = VarBinViewArray::from_iter_str(strings.iter().map(|s| s.as_str()));
436
437        // Take every other element to create mixed utilization
438        let indices_array = buffer![0u32, 2u32, 4u32, 6u32, 8u32].into_array();
439        let taken = original.take(indices_array).unwrap();
440        let taken = taken
441            .execute::<VarBinViewArray>(&mut SESSION.create_execution_ctx())
442            .unwrap();
443
444        // Compact with moderate threshold
445        let compacted = taken.compact_with_threshold(0.7, &mut ctx).unwrap();
446
447        let expected = VarBinViewArray::from_iter(
448            [0, 2, 4, 6, 8].map(|i| Some(strings[i].as_str())),
449            DType::Utf8(Nullability::NonNullable),
450        );
451        assert_arrays_eq!(compacted, expected, &mut ctx);
452    }
453
454    #[test]
455    fn test_slice_strategy_with_contiguous_range() {
456        let mut ctx = SESSION.create_execution_ctx();
457        // Create array with strings that will be in one buffer
458        let strings: Vec<String> = (0..20)
459            .map(|i| format!("this is a long string number {} for slice test", i))
460            .collect();
461
462        let original = VarBinViewArray::from_iter_str(strings.iter().map(|s| s.as_str()));
463
464        // Take only the first 5 elements - they should be in a contiguous range at the start
465        let indices_array = buffer![0u32, 1u32, 2u32, 3u32, 4u32].into_array();
466        let taken = original.take(indices_array).unwrap();
467        let taken = taken
468            .execute::<VarBinViewArray>(&mut SESSION.create_execution_ctx())
469            .unwrap();
470        // Get buffer stats before compaction
471        let original_ptr = taken.buffer(0).as_ptr();
472
473        // Compact with a threshold that should trigger slicing
474        // The range utilization should be high even if overall utilization is low
475        let compacted = taken.compact_with_threshold(0.8, &mut ctx).unwrap();
476
477        // After compaction, we should still have buffers (sliced, not rewritten)
478        assert!(
479            !compacted.data_buffers().is_empty(),
480            "Should have buffers after slice compaction"
481        );
482
483        // Verify correctness
484        assert_arrays_eq!(&compacted, taken, &mut ctx);
485
486        assert_eq!(compacted.data_buffers().len(), 1);
487        assert_eq!(compacted.buffer(0).as_ptr(), original_ptr);
488        assert_eq!(
489            compacted.buffer(0).len(),
490            strings[..5].iter().map(String::len).sum::<usize>()
491        );
492    }
493
494    const LONG1: &str = "long string one!";
495    const LONG2: &str = "long string two!";
496    const SHORT: &str = "x";
497    const EXPECTED_BYTES: u64 = (LONG1.len() + LONG2.len()) as u64;
498
499    fn mixed_array() -> VarBinViewArray {
500        VarBinViewArray::from_iter_nullable_str([Some(LONG1), None, Some(LONG2), Some(SHORT)])
501    }
502
503    #[rstest]
504    #[case::non_nullable(VarBinViewArray::from_iter_str([LONG1, LONG2, SHORT]), EXPECTED_BYTES, &[1.0])]
505    #[case::all_valid(VarBinViewArray::from_iter_nullable_str([Some(LONG1), Some(LONG2), Some(SHORT)]), EXPECTED_BYTES, &[1.0])]
506    #[case::all_invalid(VarBinViewArray::from_iter_nullable_str([None::<&str>, None]), 0, &[])]
507    #[case::mixed_validity(mixed_array(), EXPECTED_BYTES, &[1.0])]
508    fn test_validity_code_paths(
509        #[case] arr: VarBinViewArray,
510        #[case] expected_bytes: u64,
511        #[case] expected_utils: &[f64],
512    ) {
513        let mut ctx = SESSION.create_execution_ctx();
514        assert_eq!(
515            arr.count_referenced_bytes(&mut ctx).unwrap(),
516            expected_bytes
517        );
518        let utils: Vec<f64> = arr
519            .buffer_utilizations(&mut ctx)
520            .unwrap()
521            .iter()
522            .map(|u| u.overall_utilization())
523            .collect();
524        assert_eq!(utils, expected_utils);
525    }
526}