vortex_array/arrays/varbinview/
compact.rs1use 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 pub fn compact_buffers(&self, ctx: &mut ExecutionCtx) -> VortexResult<VarBinViewArray> {
31 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 nbuffers == 0 {
44 return Ok(false);
45 }
46
47 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 #[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 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 pub fn compact_with_threshold(
137 &self,
138 buffer_utilization_threshold: f64, 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 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 assert!(!original.data_buffers().is_empty());
230 let original_buffers = original.data_buffers().len();
231
232 let indices = buffer![0u32, 4u32].into_array();
234 let taken = original.take(indices).unwrap();
235 let taken = taken.execute::<VarBinViewArray>(&mut ctx).unwrap();
236 assert_eq!(taken.data_buffers().len(), original_buffers);
238
239 let optimized_array = taken.compact_buffers(&mut ctx).unwrap();
241
242 assert!(optimized_array.data_buffers().is_empty());
243
244 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 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 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 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 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 let original = VarBinViewArray::from_iter_str(["a", "bb", "ccc", "dddd"]);
297
298 assert_eq!(original.data_buffers().len(), 0);
300
301 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 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 assert_eq!(original.data_buffers().len(), 1);
319 assert_eq!(original.buffer(0).len(), str1.len() + str2.len());
320
321 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 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 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 let compacted = taken.compact_with_threshold(0.0, &mut ctx).unwrap();
349
350 assert_eq!(compacted.data_buffers().len(), taken.data_buffers().len());
352
353 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 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 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 let compacted = taken.compact_with_threshold(1.0, &mut ctx).unwrap();
378
379 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 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 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 assert_eq!(original.data_buffers().len(), 1);
406
407 let compacted = original.compact_with_threshold(0.8, &mut ctx).unwrap();
409
410 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 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 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 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 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 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 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 let original_ptr = taken.buffer(0).as_ptr();
472
473 let compacted = taken.compact_with_threshold(0.8, &mut ctx).unwrap();
476
477 assert!(
479 !compacted.data_buffers().is_empty(),
480 "Should have buffers after slice compaction"
481 );
482
483 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}