1use std::any::Any;
5use std::ops::Range;
6use std::sync::Arc;
7
8use itertools::Itertools;
9use num_traits::AsPrimitive;
10use vortex_buffer::Alignment;
11use vortex_buffer::Buffer;
12use vortex_buffer::BufferAllocatorRef;
13use vortex_buffer::BufferMut;
14use vortex_buffer::ByteBuffer;
15use vortex_buffer::ByteBufferMut;
16use vortex_error::VortexExpect;
17use vortex_error::VortexResult;
18use vortex_error::vortex_bail;
19use vortex_error::vortex_ensure_eq;
20use vortex_mask::AllOr;
21use vortex_mask::Mask;
22use vortex_utils::aliases::hash_map::Entry;
23use vortex_utils::aliases::hash_map::HashMap;
24
25use crate::ArrayRef;
26use crate::ExecutionCtx;
27use crate::IntoArray;
28use crate::arrays::VarBinViewArray;
29use crate::arrays::varbinview::VarBinViewArrayExt;
30use crate::arrays::varbinview::build_views::BinaryView;
31use crate::arrays::varbinview::build_views::MAX_BUFFER_LEN;
32use crate::arrays::varbinview::build_views::extend_views;
33use crate::arrays::varbinview::compact::BufferUtilization;
34use crate::builders::ArrayBuilder;
35use crate::builders::LazyBitBufferBuilder;
36use crate::canonical::Canonical;
37use crate::dtype::DType;
38use crate::dtype::NativePType;
39use crate::scalar::Scalar;
40
41pub struct VarBinViewBuilder {
43 dtype: DType,
44 views_builder: BufferMut<BinaryView>,
45 nulls: LazyBitBufferBuilder,
46 completed: CompletedBuffers,
47 in_progress: Option<ByteBufferMut>,
48 growth_strategy: BufferGrowthStrategy,
49 compaction_threshold: f64,
50 allocator: BufferAllocatorRef,
51}
52
53impl VarBinViewBuilder {
54 #[deprecated(note = "use `with_capacity_in` with an explicit allocator")]
56 pub fn with_capacity(dtype: DType, capacity: usize) -> Self {
57 Self::with_capacity_in(dtype, capacity, BufferAllocatorRef::statically_allocated())
58 }
59
60 pub fn with_capacity_in(dtype: DType, capacity: usize, allocator: BufferAllocatorRef) -> Self {
62 Self::new_in(
63 dtype,
64 capacity,
65 Default::default(),
66 Default::default(),
67 0.0,
68 allocator,
69 )
70 }
71
72 #[deprecated(note = "use `with_buffer_deduplication_in` with an explicit allocator")]
74 pub fn with_buffer_deduplication(dtype: DType, capacity: usize) -> Self {
75 Self::with_buffer_deduplication_in(
76 dtype,
77 capacity,
78 BufferAllocatorRef::statically_allocated(),
79 )
80 }
81
82 pub fn with_buffer_deduplication_in(
84 dtype: DType,
85 capacity: usize,
86 allocator: BufferAllocatorRef,
87 ) -> Self {
88 Self::new_in(
89 dtype,
90 capacity,
91 CompletedBuffers::Deduplicated(Default::default()),
92 Default::default(),
93 0.0,
94 allocator,
95 )
96 }
97
98 #[deprecated(note = "use `with_compaction_in` with an explicit allocator")]
100 pub fn with_compaction(dtype: DType, capacity: usize, compaction_threshold: f64) -> Self {
101 Self::with_compaction_in(
102 dtype,
103 capacity,
104 compaction_threshold,
105 BufferAllocatorRef::statically_allocated(),
106 )
107 }
108
109 pub fn with_compaction_in(
111 dtype: DType,
112 capacity: usize,
113 compaction_threshold: f64,
114 allocator: BufferAllocatorRef,
115 ) -> Self {
116 Self::new_in(
117 dtype,
118 capacity,
119 Default::default(),
120 Default::default(),
121 compaction_threshold,
122 allocator,
123 )
124 }
125
126 #[deprecated(note = "use `new_in` with an explicit allocator")]
128 pub fn new(
129 dtype: DType,
130 capacity: usize,
131 completed: CompletedBuffers,
132 growth_strategy: BufferGrowthStrategy,
133 compaction_threshold: f64,
134 ) -> Self {
135 Self::new_in(
136 dtype,
137 capacity,
138 completed,
139 growth_strategy,
140 compaction_threshold,
141 BufferAllocatorRef::statically_allocated(),
142 )
143 }
144
145 pub fn new_in(
147 dtype: DType,
148 capacity: usize,
149 completed: CompletedBuffers,
150 growth_strategy: BufferGrowthStrategy,
151 compaction_threshold: f64,
152 allocator: BufferAllocatorRef,
153 ) -> Self {
154 assert!(
155 matches!(dtype, DType::Utf8(_) | DType::Binary(_)),
156 "VarBinViewBuilder DType must be Utf8 or Binary."
157 );
158 Self {
159 views_builder: BufferMut::with_capacity_preferred_aligned_in(
160 capacity,
161 Alignment::of::<BinaryView>(),
162 None,
163 allocator.clone(),
164 ),
165 nulls: LazyBitBufferBuilder::new(capacity, allocator.clone()),
166 completed,
167 in_progress: None,
168 dtype,
169 growth_strategy,
170 compaction_threshold,
171 allocator,
172 }
173 }
174
175 fn append_value_view(&mut self, value: &[u8]) {
176 let length =
177 u32::try_from(value.len()).vortex_expect("cannot have a single string >2^32 in length");
178 if length <= 12 {
179 self.views_builder.push(BinaryView::make_view(value, 0, 0));
180 return;
181 }
182
183 let (buffer_idx, offset) = self.append_value_to_buffer(value);
184 let view = BinaryView::make_view(value, buffer_idx, offset);
185 self.views_builder.push(view);
186 }
187
188 pub fn append_value<S: AsRef<[u8]>>(&mut self, value: S) {
190 self.append_value_view(value.as_ref());
191 self.nulls.append_non_null();
192 }
193
194 pub fn append_n_values<S: AsRef<[u8]>>(&mut self, value: S, n: usize) {
196 if n == 0 {
197 return;
198 }
199 let bytes = value.as_ref();
200 let view = if bytes.len() <= BinaryView::MAX_INLINED_SIZE {
201 BinaryView::make_view(bytes, 0, 0)
202 } else {
203 let (buffer_idx, offset) = self.append_value_to_buffer(bytes);
204 BinaryView::make_view(bytes, buffer_idx, offset)
205 };
206 self.views_builder.push_n(view, n);
207 self.nulls.append_n_non_nulls(n);
208 }
209
210 fn flush_in_progress(&mut self) {
211 let Some(block) = self.in_progress.take() else {
212 return;
213 };
214
215 assert!(block.len() < u32::MAX as usize, "Block too large");
216
217 let initial_len = self.completed.len();
218 self.completed.push(block.freeze());
219 assert_eq!(
220 self.completed.len(),
221 initial_len + 1,
222 "Invalid state, just completed block already exists"
223 );
224 }
225
226 fn init_in_progress(&mut self, min_len: usize) {
227 let next_buffer_size = self.growth_strategy.next_size() as usize;
228 let to_reserve = next_buffer_size.max(min_len);
229 self.in_progress = Some(ByteBufferMut::with_capacity_preferred_aligned_in(
230 to_reserve,
231 Alignment::of::<u8>(),
232 None,
233 self.allocator.clone(),
234 ));
235 }
236
237 fn append_value_to_buffer(&mut self, value: &[u8]) -> (u32, u32) {
239 assert!(
240 value.len() > BinaryView::MAX_INLINED_SIZE,
241 "must inline small strings"
242 );
243
244 if let Some(in_progress) = &mut self.in_progress {
245 let required_cap = in_progress.len() + value.len();
246 if in_progress.capacity() < required_cap {
247 self.flush_in_progress();
248 self.init_in_progress(value.len());
249 }
250 } else {
251 self.init_in_progress(value.len())
252 };
253
254 let in_progress = self
255 .in_progress
256 .as_mut()
257 .vortex_expect("in_progress just set");
258
259 let buffer_idx = self.completed.len();
260 let offset = u32::try_from(in_progress.len()).vortex_expect("too many buffers");
261 in_progress.extend_from_slice(value);
262
263 (buffer_idx, offset)
264 }
265
266 pub fn completed_block_count(&self) -> u32 {
267 self.completed.len()
268 }
269
270 fn compacts_buffers(&self) -> bool {
275 self.compaction_threshold > 0.0
276 }
277
278 pub fn append_views_built_at(
298 &mut self,
299 validity: &Mask,
300 build: impl FnOnce(u32) -> VortexResult<(Vec<ByteBuffer>, Buffer<BinaryView>)>,
301 ) -> VortexResult<()> {
302 self.flush_in_progress();
303
304 let start_index = self.completed.len();
305 let (buffers, views) = build(start_index)?;
306 assert_eq!(
307 views.len(),
308 validity.len(),
309 "Must build one view per validity entry"
310 );
311
312 let expected_completed_len = start_index as usize + buffers.len();
313 self.completed.extend_from_slice_unchecked(&buffers);
314 assert_eq!(
315 self.completed.len() as usize,
316 expected_completed_len,
317 "Some buffers already exist",
318 );
319 self.views_builder.extend_trusted(views.iter().copied());
320 self.nulls.append_validity_mask(validity);
321
322 debug_assert_eq!(self.nulls.len(), self.views_builder.len());
323 Ok(())
324 }
325
326 fn push_buffers(&mut self, buffers: impl IntoIterator<Item = ByteBuffer>) -> Vec<u32> {
342 self.flush_in_progress();
343 buffers
344 .into_iter()
345 .map(|buffer| self.completed.push(buffer))
346 .collect()
347 }
348
349 fn push_buffers_compacted(
355 &mut self,
356 buffers: Vec<ByteBuffer>,
357 utilizations: &[BufferUtilization],
358 ) -> Vec<CompactedSlot> {
359 self.flush_in_progress();
360 buffers
361 .into_iter()
362 .zip(utilizations)
363 .map(|(buffer, utilization)| {
364 match compaction_strategy(utilization, self.compaction_threshold) {
365 CompactionStrategy::KeepFull => CompactedSlot::Kept {
366 index: self.completed.push(buffer),
367 },
368 CompactionStrategy::Slice { start, end } => CompactedSlot::Sliced {
369 index: self
370 .completed
371 .push(buffer.slice(start as usize..end as usize)),
372 shift: start,
373 },
374 CompactionStrategy::Rewrite => CompactedSlot::Rewrite { source: buffer },
375 }
376 })
377 .collect()
378 }
379
380 fn remap_view_compacted(&mut self, view: BinaryView, slots: &[CompactedSlot]) -> BinaryView {
384 if view.is_inlined() {
385 return view;
386 }
387 let view_ref = view.as_view();
388 match &slots[view_ref.buffer_index as usize] {
389 CompactedSlot::Kept { index } => view_ref
390 .with_buffer_and_offset(*index, view_ref.offset)
391 .into(),
392 CompactedSlot::Sliced { index, shift } => view_ref
393 .with_buffer_and_offset(*index, view_ref.offset - shift)
394 .into(),
395 CompactedSlot::Rewrite { source } => {
396 let bytes = &source.as_slice()[view_ref.as_range()];
397 let (buffer_idx, offset) = self.append_value_to_buffer(bytes);
398 BinaryView::make_view(bytes, buffer_idx, offset)
399 }
400 }
401 }
402
403 pub fn append_views_gathered(
422 &mut self,
423 buffers: impl IntoIterator<Item = ByteBuffer>,
424 views: &[BinaryView],
425 validity: &Mask,
426 view_at: impl Fn(usize) -> usize,
427 ) {
428 if self.compacts_buffers() {
429 return self.append_views_gathered_compacted(
430 buffers.into_iter().collect(),
431 views,
432 validity,
433 view_at,
434 );
435 }
436
437 let mapping = self.push_buffers(buffers);
438
439 self.views_builder.reserve(validity.len());
440 match validity {
441 Mask::AllTrue(len) => self
442 .views_builder
443 .extend_trusted((0..*len).map(|row| remap_view(views[view_at(row)], &mapping))),
444 Mask::AllFalse(len) => self.views_builder.push_n(BinaryView::empty_view(), *len),
445 Mask::Values(values) => {
446 let bits = values.bit_buffer();
447 let start = self.views_builder.len();
448 self.views_builder
449 .push_n(BinaryView::empty_view(), bits.len());
450 let gathered = &mut self.views_builder[start..];
451 bits.for_each_set_index(|row| {
452 gathered[row] = remap_view(views[view_at(row)], &mapping);
453 });
454 }
455 }
456
457 self.nulls.append_validity_mask(validity);
458 debug_assert_eq!(self.nulls.len(), self.views_builder.len());
459 }
460
461 fn append_views_gathered_compacted(
467 &mut self,
468 buffers: Vec<ByteBuffer>,
469 views: &[BinaryView],
470 validity: &Mask,
471 view_at: impl Fn(usize) -> usize,
472 ) {
473 let mut referenced = vec![false; views.len()];
474 match validity {
475 Mask::AllTrue(len) => (0..*len).for_each(|row| referenced[view_at(row)] = true),
476 Mask::AllFalse(_) => {}
477 Mask::Values(values) => values
478 .bit_buffer()
479 .for_each_set_index(|row| referenced[view_at(row)] = true),
480 }
481
482 let mut utilizations = unmeasured_utilizations(&buffers);
483 for (view, _) in views.iter().zip(&referenced).filter(|(_, used)| **used) {
484 measure_view(&mut utilizations, view);
485 }
486 let slots = self.push_buffers_compacted(buffers, &utilizations);
487
488 let mut remapped = vec![BinaryView::empty_view(); views.len()];
489 for (idx, view) in views.iter().enumerate() {
490 if referenced[idx] {
491 remapped[idx] = self.remap_view_compacted(*view, &slots);
492 }
493 }
494
495 self.views_builder.reserve(validity.len());
496 match validity {
497 Mask::AllTrue(len) => self
498 .views_builder
499 .extend_trusted((0..*len).map(|row| remapped[view_at(row)])),
500 Mask::AllFalse(len) => self.views_builder.push_n(BinaryView::empty_view(), *len),
501 Mask::Values(values) => {
502 let bits = values.bit_buffer();
503 let start = self.views_builder.len();
504 self.views_builder
505 .push_n(BinaryView::empty_view(), bits.len());
506 let gathered = &mut self.views_builder[start..];
507 bits.for_each_set_index(|row| gathered[row] = remapped[view_at(row)]);
508 }
509 }
510
511 self.nulls.append_validity_mask(validity);
512 debug_assert_eq!(self.nulls.len(), self.views_builder.len());
513 }
514
515 pub fn append_views_scattered(
532 &mut self,
533 buffers: impl IntoIterator<Item = ByteBuffer>,
534 len: usize,
535 fill: BinaryView,
536 patches: impl Iterator<Item = (usize, BinaryView)>,
537 validity: &Mask,
538 ) {
539 assert_eq!(validity.len(), len, "Must have one validity entry per row");
540 let mapping = self.push_buffers(buffers);
541
542 let start = self.views_builder.len();
543 self.views_builder.push_n(remap_view(fill, &mapping), len);
544 let scattered = &mut self.views_builder[start..];
545 for (row, view) in patches {
546 scattered[row] = remap_view(view, &mapping);
547 }
548
549 self.nulls.append_validity_mask(validity);
550 debug_assert_eq!(self.nulls.len(), self.views_builder.len());
551 }
552
553 pub fn append_buffer_with_lengths<P: NativePType + AsPrimitive<usize>>(
571 &mut self,
572 bytes: ByteBuffer,
573 lengths: &[P],
574 validity: &Mask,
575 ) {
576 assert_eq!(
577 lengths.len(),
578 validity.len(),
579 "Must have one length per validity entry"
580 );
581 self.append_buffer_views(&bytes, lengths.len(), validity, |i| lengths[i].as_());
582 }
583
584 pub fn append_buffer_with_offsets<P: NativePType + AsPrimitive<usize>>(
597 &mut self,
598 bytes: ByteBuffer,
599 offsets: &[P],
600 validity: &Mask,
601 ) {
602 assert_eq!(
603 offsets.len(),
604 validity.len() + 1,
605 "Must have one more offset than validity entries"
606 );
607 let first: usize = offsets[0].as_();
608 let last: usize = offsets[offsets.len() - 1].as_();
609 let bytes = bytes.slice(first..last);
610 self.append_buffer_views(&bytes, validity.len(), validity, |i| {
613 AsPrimitive::<usize>::as_(offsets[i + 1])
614 .wrapping_sub(AsPrimitive::<usize>::as_(offsets[i]))
615 });
616 }
617
618 fn append_buffer_views(
621 &mut self,
622 bytes: &ByteBuffer,
623 count: usize,
624 validity: &Mask,
625 len_at: impl Fn(usize) -> usize,
626 ) {
627 self.flush_in_progress();
628
629 if self.compacts_buffers() && bytes.len() <= MAX_BUFFER_LEN {
635 let referenced: usize = match validity.bit_buffer() {
636 AllOr::All => (0..count)
637 .map(&len_at)
638 .filter(|len| *len > BinaryView::MAX_INLINED_SIZE)
639 .sum(),
640 AllOr::None => 0,
641 AllOr::Some(b) => {
642 let mut sum = 0;
643 b.for_each_set_index(|idx| {
644 let len = len_at(idx);
645 if len > BinaryView::MAX_INLINED_SIZE {
646 sum += len;
647 }
648 });
649 sum
650 }
651 };
652 #[expect(clippy::cast_precision_loss)]
653 if (referenced as f64) < self.compaction_threshold * (bytes.len() as f64) {
654 return self
655 .append_buffer_views_rewritten(bytes, count, validity, len_at, referenced);
656 }
657 }
658
659 let start_index = self.completed.len();
660 let segments = extend_views(
661 &mut self.views_builder,
662 start_index,
663 MAX_BUFFER_LEN,
664 bytes,
665 count,
666 len_at,
667 );
668
669 let expected_completed_len = start_index as usize + segments.len();
670 self.completed.extend_from_slice_unchecked(&segments);
671 assert_eq!(
672 self.completed.len() as usize,
673 expected_completed_len,
674 "Some buffers already exist",
675 );
676
677 self.nulls.append_validity_mask(validity);
678 debug_assert_eq!(self.nulls.len(), self.views_builder.len());
679 }
680
681 fn append_buffer_views_rewritten(
685 &mut self,
686 bytes: &ByteBuffer,
687 count: usize,
688 validity: &Mask,
689 len_at: impl Fn(usize) -> usize,
690 referenced: usize,
691 ) {
692 let buf_index = self.completed.len();
693 let mut compact = ByteBufferMut::with_capacity_in(referenced, self.allocator.clone());
694 self.views_builder.reserve(count);
695
696 let data = bytes.as_slice();
697 let mut offset = 0usize;
698 for (i, is_valid) in validity.iter().enumerate() {
699 let len = len_at(i);
700 let value = &data[offset..offset + len];
701 let view = if !is_valid {
702 BinaryView::empty_view()
703 } else if len > BinaryView::MAX_INLINED_SIZE {
704 #[expect(clippy::cast_possible_truncation)]
707 let view = BinaryView::make_view(value, buf_index, compact.len() as u32);
708 compact.extend_from_slice(value);
709 view
710 } else {
711 BinaryView::make_view(value, buf_index, 0)
712 };
713 self.views_builder.push(view);
714 offset += len;
715 }
716 assert_eq!(
717 offset,
718 data.len(),
719 "value lengths must describe the byte heap exactly"
720 );
721
722 if !compact.is_empty() {
723 let pushed_index = self.completed.push(compact.freeze());
724 assert_eq!(pushed_index, buf_index, "Buffer already exists");
725 }
726
727 self.nulls.append_validity_mask(validity);
728 debug_assert_eq!(self.nulls.len(), self.views_builder.len());
729 }
730
731 pub fn finish_into_varbinview(&mut self) -> VarBinViewArray {
733 self.flush_in_progress();
734 let buffers = std::mem::take(&mut self.completed);
735
736 assert_eq!(
737 self.views_builder.len(),
738 self.nulls.len(),
739 "View and validity length must match"
740 );
741
742 let validity = self.nulls.finish_with_nullability(self.dtype.nullability());
743
744 let views = std::mem::replace(
745 &mut self.views_builder,
746 BufferMut::empty_aligned_in(Alignment::of::<BinaryView>(), self.allocator.clone()),
747 )
748 .freeze();
749
750 unsafe {
752 VarBinViewArray::new_unchecked(views, buffers.finish(), self.dtype.clone(), validity)
753 }
754 }
755
756 pub(crate) fn append_varbinview_array(
757 &mut self,
758 array: &VarBinViewArray,
759 ctx: &mut ExecutionCtx,
760 ) -> VortexResult<()> {
761 self.flush_in_progress();
762
763 let mask = array.varbinview_validity().execute_mask(array.len(), ctx)?;
764
765 self.nulls.append_validity_mask(&mask);
766
767 let view_adjustment =
768 self.completed
769 .extend_from_compaction(BuffersWithOffsets::from_array(
770 array,
771 self.compaction_threshold,
772 ctx,
773 ));
774
775 match view_adjustment {
776 ViewAdjustment::Precomputed(adjustment) => self.views_builder.extend_trusted(
777 array
778 .views()
779 .iter()
780 .map(|view| adjustment.adjust_view(view)),
781 ),
782 ViewAdjustment::Rewriting(adjustment) => match mask {
783 Mask::AllTrue(_) => {
784 for (idx, &view) in array.views().iter().enumerate() {
785 let new_view = self.push_view(view, &adjustment, array, idx);
786 self.views_builder.push(new_view);
787 }
788 }
789 Mask::AllFalse(_) => {
790 self.views_builder
791 .push_n(BinaryView::empty_view(), array.len());
792 }
793 Mask::Values(v) => {
794 let views = array.views();
795 let start = self.views_builder.len();
796 self.views_builder
797 .push_n(BinaryView::empty_view(), array.len());
798 v.bit_buffer().for_each_set_index(|idx| {
799 let new_view = self.push_view(views[idx], &adjustment, array, idx);
800 self.views_builder[start + idx] = new_view;
801 });
802 }
803 },
804 }
805
806 Ok(())
807 }
808}
809
810impl ArrayBuilder for VarBinViewBuilder {
811 fn as_any(&self) -> &dyn Any {
812 self
813 }
814
815 fn as_any_mut(&mut self) -> &mut dyn Any {
816 self
817 }
818
819 fn dtype(&self) -> &DType {
820 &self.dtype
821 }
822
823 fn len(&self) -> usize {
824 self.nulls.len()
825 }
826
827 fn append_zeros(&mut self, n: usize) {
828 self.views_builder.push_n(BinaryView::empty_view(), n);
829 self.nulls.append_n_non_nulls(n);
830 }
831
832 unsafe fn append_nulls_unchecked(&mut self, n: usize) {
833 self.views_builder.push_n(BinaryView::empty_view(), n);
834 self.nulls.append_n_nulls(n);
835 }
836
837 fn append_scalar(&mut self, scalar: &Scalar) -> VortexResult<()> {
838 vortex_ensure_eq!(
839 scalar.dtype(),
840 self.dtype(),
841 "VarBinViewBuilder received a scalar with the wrong dtype"
842 );
843
844 match self.dtype() {
845 DType::Utf8(_) => match scalar.as_utf8().value() {
846 Some(value) => self.append_value(value),
847 None => self.append_null(),
848 },
849 DType::Binary(_) => match scalar.as_binary().value() {
850 Some(value) => self.append_value(value),
851 None => self.append_null(),
852 },
853 _ => vortex_bail!(
854 "VarBinViewBuilder can only handle Utf8 or Binary scalars, got {:?}",
855 scalar.dtype()
856 ),
857 }
858
859 Ok(())
860 }
861
862 fn reserve_exact(&mut self, additional: usize) {
863 self.views_builder.reserve(additional);
864 self.nulls.reserve_exact(additional);
865 }
866
867 fn finish(&mut self) -> ArrayRef {
868 self.finish_into_varbinview().into_array()
869 }
870
871 fn finish_into_canonical(&mut self, _ctx: &mut ExecutionCtx) -> Canonical {
872 Canonical::VarBinView(self.finish_into_varbinview())
873 }
874}
875
876impl VarBinViewBuilder {
877 #[allow(clippy::inline_always)]
878 #[inline(always)]
879 fn push_view(
880 &mut self,
881 view: BinaryView,
882 adjustment: &RewritingViewAdjustment,
883 array: &VarBinViewArray,
884 idx: usize,
885 ) -> BinaryView {
886 if view.is_inlined() {
887 view
888 } else if let Some(adjusted) = adjustment.adjust_view(&view) {
889 adjusted
890 } else {
891 let bytes = array.bytes_at(idx);
892 let (new_buf_idx, new_offset) = self.append_value_to_buffer(&bytes);
893 BinaryView::make_view(bytes.as_slice(), new_buf_idx, new_offset)
894 }
895 }
896}
897
898#[inline]
902fn remap_view(view: BinaryView, mapping: &[u32]) -> BinaryView {
903 if view.is_inlined() {
904 view
905 } else {
906 let view_ref = view.as_view();
907 view_ref
908 .with_buffer_and_offset(mapping[view_ref.buffer_index as usize], view_ref.offset)
909 .into()
910 }
911}
912
913enum CompactedSlot {
915 Kept { index: u32 },
917 Sliced { index: u32, shift: u32 },
919 Rewrite { source: ByteBuffer },
922}
923
924fn unmeasured_utilizations(buffers: &[ByteBuffer]) -> Vec<BufferUtilization> {
926 buffers
927 .iter()
928 .map(|buffer| {
929 BufferUtilization::zero(u32::try_from(buffer.len()).unwrap_or(u32::MAX))
933 })
934 .collect()
935}
936
937fn measure_view(utilizations: &mut [BufferUtilization], view: &BinaryView) {
939 if !view.is_inlined() {
940 let view_ref = view.as_view();
941 utilizations[view_ref.buffer_index as usize].add(view_ref.offset, view_ref.size);
942 }
943}
944
945pub enum CompletedBuffers {
946 Default(Vec<ByteBuffer>),
947 Deduplicated(DeduplicatedBuffers),
948}
949
950impl Default for CompletedBuffers {
951 fn default() -> Self {
952 Self::Default(Vec::new())
953 }
954}
955
956#[expect(clippy::cast_possible_truncation)]
958impl CompletedBuffers {
959 fn len(&self) -> u32 {
960 match self {
961 Self::Default(buffers) => buffers.len() as u32,
962 Self::Deduplicated(buffers) => buffers.len(),
963 }
964 }
965
966 fn push(&mut self, block: ByteBuffer) -> u32 {
969 match self {
970 Self::Default(buffers) => {
971 assert!(buffers.len() < u32::MAX as usize, "Too many blocks");
972 buffers.push(block);
973 self.len() - 1
974 }
975 Self::Deduplicated(buffers) => buffers.push(block),
976 }
977 }
978
979 fn extend_from_slice_unchecked(&mut self, buffers: &[ByteBuffer]) {
981 for buffer in buffers {
982 self.push(buffer.clone());
983 }
984 }
985
986 fn extend_from_compaction(&mut self, buffers: BuffersWithOffsets) -> ViewAdjustment {
987 match (self, buffers) {
988 (
989 Self::Default(completed_buffers),
990 BuffersWithOffsets::AllKept { buffers, offsets },
991 ) => {
992 let buffer_offset = completed_buffers.len() as u32;
993 completed_buffers.extend_from_slice(&buffers);
994 ViewAdjustment::shift(buffer_offset, offsets)
995 }
996 (
997 Self::Default(completed_buffers),
998 BuffersWithOffsets::SomeCompacted { buffers, offsets },
999 ) => {
1000 let lookup = buffers
1001 .iter()
1002 .map(|maybe_buffer| {
1003 maybe_buffer.as_ref().map(|buffer| {
1004 completed_buffers.push(buffer.clone());
1005 completed_buffers.len() as u32 - 1
1006 })
1007 })
1008 .collect();
1009 ViewAdjustment::rewriting(lookup, offsets)
1010 }
1011
1012 (
1013 Self::Deduplicated(completed_buffers),
1014 BuffersWithOffsets::AllKept { buffers, offsets },
1015 ) => {
1016 let buffer_lookup = completed_buffers.extend_from_iter(buffers.iter().cloned());
1017 ViewAdjustment::lookup(buffer_lookup, offsets)
1018 }
1019 (
1020 Self::Deduplicated(completed_buffers),
1021 BuffersWithOffsets::SomeCompacted { buffers, offsets },
1022 ) => {
1023 let buffer_lookup = completed_buffers.extend_from_option_slice(&buffers);
1024 ViewAdjustment::rewriting(buffer_lookup, offsets)
1025 }
1026 }
1027 }
1028
1029 fn finish(self) -> Arc<[ByteBuffer]> {
1030 match self {
1031 Self::Default(buffers) => Arc::from(buffers),
1032 Self::Deduplicated(buffers) => buffers.finish(),
1033 }
1034 }
1035}
1036
1037#[derive(Default)]
1038pub struct DeduplicatedBuffers {
1039 buffers: Vec<ByteBuffer>,
1040 buffer_to_idx: HashMap<BufferId, u32>,
1041}
1042
1043impl DeduplicatedBuffers {
1044 #[expect(clippy::cast_possible_truncation)]
1046 fn len(&self) -> u32 {
1047 self.buffers.len() as u32
1048 }
1049
1050 pub(crate) fn push(&mut self, block: ByteBuffer) -> u32 {
1052 assert!(self.buffers.len() < u32::MAX as usize, "Too many blocks");
1053
1054 let initial_len = self.len();
1055 let id = BufferId::from(&block);
1056 match self.buffer_to_idx.entry(id) {
1057 Entry::Occupied(idx) => *idx.get(),
1058 Entry::Vacant(entry) => {
1059 let idx = initial_len;
1060 entry.insert(idx);
1061 self.buffers.push(block);
1062 idx
1063 }
1064 }
1065 }
1066
1067 pub(crate) fn extend_from_option_slice(
1068 &mut self,
1069 buffers: &[Option<ByteBuffer>],
1070 ) -> Vec<Option<u32>> {
1071 buffers
1072 .iter()
1073 .map(|buffer| buffer.as_ref().map(|buf| self.push(buf.clone())))
1074 .collect()
1075 }
1076
1077 pub(crate) fn extend_from_iter(
1078 &mut self,
1079 buffers: impl Iterator<Item = ByteBuffer>,
1080 ) -> Vec<u32> {
1081 buffers.map(|buffer| self.push(buffer)).collect()
1082 }
1083
1084 pub(crate) fn finish(self) -> Arc<[ByteBuffer]> {
1085 Arc::from(self.buffers)
1086 }
1087}
1088
1089#[derive(PartialEq, Eq, Hash)]
1090struct BufferId {
1091 ptr: usize,
1093 len: usize,
1094}
1095
1096impl BufferId {
1097 fn from(buffer: &ByteBuffer) -> Self {
1098 let slice = buffer.as_slice();
1099 Self {
1100 ptr: slice.as_ptr() as usize,
1101 len: slice.len(),
1102 }
1103 }
1104}
1105
1106#[derive(Debug, Clone)]
1107pub enum BufferGrowthStrategy {
1108 Fixed { size: u32 },
1110 Exponential { current_size: u32, max_size: u32 },
1112}
1113
1114impl Default for BufferGrowthStrategy {
1115 fn default() -> Self {
1116 Self::Exponential {
1117 current_size: 4 * 1024, max_size: 2 * 1024 * 1024, }
1120 }
1121}
1122
1123impl BufferGrowthStrategy {
1124 pub fn fixed(size: u32) -> Self {
1125 Self::Fixed { size }
1126 }
1127
1128 pub fn exponential(initial_size: u32, max_size: u32) -> Self {
1129 Self::Exponential {
1130 current_size: initial_size,
1131 max_size,
1132 }
1133 }
1134
1135 pub fn next_size(&mut self) -> u32 {
1137 match self {
1138 Self::Fixed { size } => *size,
1139 Self::Exponential {
1140 current_size,
1141 max_size,
1142 } => {
1143 let result = *current_size;
1144 if *current_size < *max_size {
1145 *current_size = current_size.saturating_mul(2).min(*max_size);
1146 }
1147 result
1148 }
1149 }
1150 }
1151}
1152
1153enum BuffersWithOffsets {
1154 AllKept {
1155 buffers: Arc<[ByteBuffer]>,
1156 offsets: Option<Vec<u32>>,
1157 },
1158 SomeCompacted {
1159 buffers: Vec<Option<ByteBuffer>>,
1160 offsets: Option<Vec<u32>>,
1161 },
1162}
1163
1164impl BuffersWithOffsets {
1165 pub fn from_array(
1166 array: &VarBinViewArray,
1167 compaction_threshold: f64,
1168 ctx: &mut ExecutionCtx,
1169 ) -> Self {
1170 if compaction_threshold == 0.0 {
1171 return Self::AllKept {
1172 buffers: Arc::from(
1173 array
1174 .data_buffers()
1175 .iter()
1176 .cloned()
1177 .map(|b| b.unwrap_host())
1178 .collect_vec(),
1179 ),
1180 offsets: None,
1181 };
1182 }
1183
1184 let buffer_utilizations = array
1185 .buffer_utilizations(ctx)
1186 .vortex_expect("buffer_utilizations in BuffersWithOffsets::from_array");
1187 let mut has_rewrite = false;
1188 let mut has_nonzero_offset = false;
1189 for utilization in buffer_utilizations.iter() {
1190 match compaction_strategy(utilization, compaction_threshold) {
1191 CompactionStrategy::KeepFull => continue,
1192 CompactionStrategy::Slice { .. } => has_nonzero_offset = true,
1193 CompactionStrategy::Rewrite => has_rewrite = true,
1194 }
1195 }
1196
1197 let buffers_with_offsets_iter = buffer_utilizations
1198 .iter()
1199 .zip(array.data_buffers().iter())
1200 .map(|(utilization, buffer)| {
1201 match compaction_strategy(utilization, compaction_threshold) {
1202 CompactionStrategy::KeepFull => (Some(buffer.as_host().clone()), 0),
1203 CompactionStrategy::Slice { start, end } => (
1204 Some(buffer.as_host().slice(start as usize..end as usize)),
1205 start,
1206 ),
1207 CompactionStrategy::Rewrite => (None, 0),
1208 }
1209 });
1210
1211 match (has_rewrite, has_nonzero_offset) {
1212 (false, false) => {
1214 let buffers: Vec<_> = buffers_with_offsets_iter
1215 .map(|(b, _)| b.vortex_expect("already checked for rewrite"))
1216 .collect();
1217 Self::AllKept {
1218 buffers: Arc::from(buffers),
1219 offsets: None,
1220 }
1221 }
1222 (true, false) => {
1224 let buffers: Vec<_> = buffers_with_offsets_iter.map(|(b, _)| b).collect();
1225 Self::SomeCompacted {
1226 buffers,
1227 offsets: None,
1228 }
1229 }
1230 (false, true) => {
1232 let (buffers, offsets): (Vec<_>, _) = buffers_with_offsets_iter
1233 .map(|(buffer, offset)| {
1234 (buffer.vortex_expect("already checked for rewrite"), offset)
1235 })
1236 .collect();
1237 Self::AllKept {
1238 buffers: Arc::from(buffers),
1239 offsets: Some(offsets),
1240 }
1241 }
1242 (true, true) => {
1244 let (buffers, offsets) = buffers_with_offsets_iter.collect();
1245 Self::SomeCompacted {
1246 buffers,
1247 offsets: Some(offsets),
1248 }
1249 }
1250 }
1251 }
1252}
1253
1254#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1255enum CompactionStrategy {
1256 KeepFull,
1257 Slice {
1259 start: u32,
1260 end: u32,
1261 },
1262 Rewrite,
1264}
1265
1266fn compaction_strategy(
1267 buffer_utilization: &BufferUtilization,
1268 threshold: f64,
1269) -> CompactionStrategy {
1270 match buffer_utilization.overall_utilization() {
1271 0.0 => CompactionStrategy::Rewrite,
1273 utilised if utilised >= threshold => CompactionStrategy::KeepFull,
1274 _ if buffer_utilization.range_utilization() >= threshold => {
1275 let Range { start, end } = buffer_utilization.range();
1276 CompactionStrategy::Slice { start, end }
1277 }
1278 _ => CompactionStrategy::Rewrite,
1279 }
1280}
1281
1282enum ViewAdjustment {
1283 Precomputed(PrecomputedViewAdjustment),
1284 Rewriting(RewritingViewAdjustment),
1285}
1286
1287impl ViewAdjustment {
1288 fn shift(buffer_offset: u32, offsets: Option<Vec<u32>>) -> Self {
1289 Self::Precomputed(PrecomputedViewAdjustment::Shift {
1290 buffer_offset,
1291 offsets,
1292 })
1293 }
1294
1295 fn lookup(buffer_lookup: Vec<u32>, offsets: Option<Vec<u32>>) -> Self {
1296 Self::Precomputed(PrecomputedViewAdjustment::Lookup {
1297 buffer_lookup,
1298 offsets,
1299 })
1300 }
1301
1302 fn rewriting(buffer_lookup: Vec<Option<u32>>, offsets: Option<Vec<u32>>) -> Self {
1303 Self::Rewriting(RewritingViewAdjustment {
1304 buffer_lookup,
1305 offsets,
1306 })
1307 }
1308}
1309
1310enum PrecomputedViewAdjustment {
1312 Shift {
1313 buffer_offset: u32,
1314 offsets: Option<Vec<u32>>,
1315 },
1316 Lookup {
1317 buffer_lookup: Vec<u32>,
1318 offsets: Option<Vec<u32>>,
1319 },
1320}
1321
1322impl PrecomputedViewAdjustment {
1323 #[inline]
1324 fn adjust_view(&self, view: &BinaryView) -> BinaryView {
1325 if view.is_inlined() {
1326 return *view;
1327 }
1328 let view_ref = view.as_view();
1329 match self {
1330 Self::Shift {
1331 buffer_offset,
1332 offsets,
1333 } => {
1334 let b_idx = view_ref.buffer_index;
1335 let offset_shift = offsets
1336 .as_ref()
1337 .map(|o| o[b_idx as usize])
1338 .unwrap_or_default();
1339
1340 if view_ref.offset < offset_shift {
1343 return BinaryView::empty_view();
1344 }
1345
1346 view_ref
1347 .with_buffer_and_offset(b_idx + buffer_offset, view_ref.offset - offset_shift)
1348 }
1349 Self::Lookup {
1350 buffer_lookup,
1351 offsets,
1352 } => {
1353 let b_idx = view_ref.buffer_index;
1354 let buffer = buffer_lookup[b_idx as usize];
1355 let offset_shift = offsets
1356 .as_ref()
1357 .map(|o| o[b_idx as usize])
1358 .unwrap_or_default();
1359
1360 if view_ref.offset < offset_shift {
1363 return BinaryView::empty_view();
1364 }
1365
1366 view_ref.with_buffer_and_offset(buffer, view_ref.offset - offset_shift)
1367 }
1368 }
1369 .into()
1370 }
1371}
1372
1373struct RewritingViewAdjustment {
1374 buffer_lookup: Vec<Option<u32>>,
1375 offsets: Option<Vec<u32>>,
1376}
1377
1378impl RewritingViewAdjustment {
1379 #[inline]
1382 fn adjust_view(&self, view: &BinaryView) -> Option<BinaryView> {
1383 if view.is_inlined() {
1384 return Some(*view);
1385 }
1386
1387 let view_ref = view.as_view();
1388 self.buffer_lookup[view_ref.buffer_index as usize].map(|buffer| {
1389 let offset_shift = self
1390 .offsets
1391 .as_ref()
1392 .map(|o| o[view_ref.buffer_index as usize])
1393 .unwrap_or_default();
1394 view_ref
1395 .with_buffer_and_offset(buffer, view_ref.offset - offset_shift)
1396 .into()
1397 })
1398 }
1399}
1400
1401#[cfg(test)]
1402mod tests {
1403 use std::sync::LazyLock;
1404
1405 use vortex_buffer::BufferAllocatorRef;
1406 use vortex_buffer::ByteBuffer;
1407 use vortex_error::VortexResult;
1408 use vortex_mask::Mask;
1409 use vortex_session::VortexSession;
1410
1411 use crate::IntoArray;
1412 use crate::VortexSessionExecute;
1413 use crate::assert_arrays_eq;
1414 use crate::builders::ArrayBuilder;
1415 use crate::builders::VarBinViewBuilder;
1416 use crate::builders::varbinview::VarBinViewArray;
1417 use crate::dtype::DType;
1418 use crate::dtype::Nullability;
1419 use crate::scalar::Scalar;
1420
1421 static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
1422
1423 const LONG: &str = "a value that is far too long to inline";
1425
1426 #[test]
1429 fn test_append_buffer_with_lengths() {
1430 let mut ctx = SESSION.create_execution_ctx();
1431 let mut builder = VarBinViewBuilder::with_capacity_in(
1432 DType::Utf8(Nullability::Nullable),
1433 8,
1434 BufferAllocatorRef::statically_allocated(),
1435 );
1436
1437 builder.append_value(LONG);
1439
1440 let heap = ByteBuffer::copy_from([LONG.as_bytes(), b"", b"tiny"].concat());
1441 let heap_ptr = heap.as_ptr();
1442 let lengths = [u32::try_from(LONG.len()).unwrap(), 0, 4];
1443 builder.append_buffer_with_lengths(heap, &lengths, &Mask::from_iter([true, false, true]));
1444
1445 builder.append_value("tail");
1446
1447 let actual = builder.finish_into_varbinview();
1448 assert_eq!(actual.data_buffers()[1].as_host().as_ptr(), heap_ptr);
1450
1451 let expected = <VarBinViewArray as FromIterator<_>>::from_iter([
1452 Some(LONG),
1453 Some(LONG),
1454 None,
1455 Some("tiny"),
1456 Some("tail"),
1457 ]);
1458 assert_arrays_eq!(actual, expected, &mut ctx);
1459 }
1460
1461 #[test]
1463 fn test_append_buffer_with_offsets() {
1464 let mut ctx = SESSION.create_execution_ctx();
1465 let mut builder = VarBinViewBuilder::with_capacity_in(
1466 DType::Utf8(Nullability::Nullable),
1467 8,
1468 BufferAllocatorRef::statically_allocated(),
1469 );
1470
1471 let heap = ByteBuffer::copy_from(format!("..{LONG}tiny!!"));
1472 let long_len = u32::try_from(LONG.len()).unwrap();
1473 let offsets = [2u32, 2 + long_len, 2 + long_len, 2 + long_len + 4];
1474 builder.append_buffer_with_offsets(
1475 heap.clone(),
1476 &offsets,
1477 &Mask::from_iter([true, false, true]),
1478 );
1479
1480 let actual = builder.finish_into_varbinview();
1481 assert_eq!(actual.data_buffers()[0].as_host().as_ptr(), unsafe {
1484 heap.as_ptr().add(2)
1485 });
1486 assert_eq!(
1487 actual.data_buffers()[0].len(),
1488 LONG.len() + 4,
1489 "only the referenced range must be adopted"
1490 );
1491
1492 let expected =
1493 <VarBinViewArray as FromIterator<_>>::from_iter([Some(LONG), None, Some("tiny")]);
1494 assert_arrays_eq!(actual, expected, &mut ctx);
1495 }
1496
1497 #[test]
1500 fn test_append_buffer_with_lengths_compacts_underutilized_heap() {
1501 let mut ctx = SESSION.create_execution_ctx();
1502 let mut builder = VarBinViewBuilder::with_compaction_in(
1503 DType::Utf8(Nullability::Nullable),
1504 4,
1505 1.0,
1506 BufferAllocatorRef::statically_allocated(),
1507 );
1508
1509 let heap = ByteBuffer::copy_from([b"short".as_slice(), LONG.as_bytes(), b"tiny"].concat());
1510 let lengths = [5u32, u32::try_from(LONG.len()).unwrap(), 4];
1511 builder.append_buffer_with_lengths(heap, &lengths, &Mask::new_true(3));
1512
1513 let actual = builder.finish_into_varbinview();
1514 assert_eq!(actual.data_buffers().len(), 1);
1515 assert_eq!(
1516 actual.data_buffers()[0].len(),
1517 LONG.len(),
1518 "the compact buffer must hold only the non-inlined values"
1519 );
1520
1521 let expected = <VarBinViewArray as FromIterator<_>>::from_iter([
1522 Some("short"),
1523 Some(LONG),
1524 Some("tiny"),
1525 ]);
1526 assert_arrays_eq!(actual, expected, &mut ctx);
1527 }
1528
1529 #[test]
1532 fn test_append_buffer_with_lengths_compaction_skips_null_bytes() {
1533 let mut ctx = SESSION.create_execution_ctx();
1534 let mut builder = VarBinViewBuilder::with_compaction_in(
1535 DType::Utf8(Nullability::Nullable),
1536 2,
1537 1.0,
1538 BufferAllocatorRef::statically_allocated(),
1539 );
1540
1541 let heap = ByteBuffer::copy_from([LONG.as_bytes(), LONG.as_bytes()].concat());
1542 let lengths = [u32::try_from(LONG.len()).unwrap(); 2];
1543 builder.append_buffer_with_lengths(heap, &lengths, &Mask::from_iter([false, true]));
1544
1545 let actual = builder.finish_into_varbinview();
1546 assert_eq!(actual.data_buffers().len(), 1);
1547 assert_eq!(
1548 actual.data_buffers()[0].len(),
1549 LONG.len(),
1550 "the compact buffer must omit bytes belonging to null rows"
1551 );
1552
1553 let expected = <VarBinViewArray as FromIterator<_>>::from_iter([None::<&str>, Some(LONG)]);
1554 assert_arrays_eq!(actual, expected, &mut ctx);
1555 }
1556
1557 #[test]
1560 fn test_push_buffers_deduplicates() {
1561 let mut builder = VarBinViewBuilder::with_buffer_deduplication_in(
1562 DType::Utf8(Nullability::Nullable),
1563 8,
1564 BufferAllocatorRef::statically_allocated(),
1565 );
1566
1567 let first = ByteBuffer::copy_from(LONG);
1568 let second = ByteBuffer::copy_from("another value far too long to inline");
1569
1570 assert_eq!(
1571 builder.push_buffers([first.clone(), second.clone()]),
1572 [0, 1]
1573 );
1574 assert_eq!(builder.push_buffers([second, first]), [1, 0]);
1575 assert_eq!(builder.completed_block_count(), 2);
1576 }
1577
1578 #[test]
1581 fn test_append_views_gathered() {
1582 let mut ctx = SESSION.create_execution_ctx();
1583 let dictionary = <VarBinViewArray as FromIterator<_>>::from_iter([
1584 Some("tiny"),
1585 Some(LONG),
1586 Some("small"),
1587 ]);
1588 let buffers = dictionary
1589 .data_buffers()
1590 .iter()
1591 .map(|buffer| buffer.as_host().clone())
1592 .collect::<Vec<_>>();
1593
1594 let mut builder = VarBinViewBuilder::with_capacity_in(
1595 DType::Utf8(Nullability::Nullable),
1596 8,
1597 BufferAllocatorRef::statically_allocated(),
1598 );
1599 builder.append_value(LONG);
1601
1602 let codes: [usize; 4] = [1, 0, usize::MAX, 2];
1603 let views = dictionary.views();
1604 builder.append_views_gathered(
1605 buffers,
1606 views,
1607 &Mask::from_iter([true, true, false, true]),
1608 |row| codes[row],
1610 );
1611
1612 let expected = <VarBinViewArray as FromIterator<_>>::from_iter([
1613 Some(LONG),
1614 Some(LONG),
1615 Some("tiny"),
1616 None,
1617 Some("small"),
1618 ]);
1619 assert_arrays_eq!(builder.finish_into_varbinview(), expected, &mut ctx);
1620 }
1621
1622 #[test]
1625 fn test_append_views_scattered() {
1626 use crate::arrays::varbinview::build_views::BinaryView;
1627
1628 let mut ctx = SESSION.create_execution_ctx();
1629 let patch_values =
1630 <VarBinViewArray as FromIterator<_>>::from_iter([Some(LONG), Some("tiny")]);
1631 let mut buffers = patch_values
1632 .data_buffers()
1633 .iter()
1634 .map(|buffer| buffer.as_host().clone())
1635 .collect::<Vec<_>>();
1636
1637 let fill_bytes = ByteBuffer::copy_from("a fill value too long to inline");
1638 buffers.push(fill_bytes.clone());
1639 let fill = BinaryView::make_view(
1640 fill_bytes.as_slice(),
1641 u32::try_from(buffers.len() - 1).unwrap(),
1642 0,
1643 );
1644
1645 let mut builder = VarBinViewBuilder::with_capacity_in(
1646 DType::Utf8(Nullability::Nullable),
1647 8,
1648 BufferAllocatorRef::statically_allocated(),
1649 );
1650 let views = patch_values.views();
1651 builder.append_views_scattered(
1652 buffers,
1653 5,
1654 fill,
1655 [(1usize, views[0]), (3usize, views[1])].into_iter(),
1656 &Mask::from_iter([true, true, false, true, true]),
1657 );
1658
1659 let expected = <VarBinViewArray as FromIterator<_>>::from_iter([
1660 Some("a fill value too long to inline"),
1661 Some(LONG),
1662 None,
1663 Some("tiny"),
1664 Some("a fill value too long to inline"),
1665 ]);
1666 assert_arrays_eq!(builder.finish_into_varbinview(), expected, &mut ctx);
1667 }
1668
1669 #[test]
1673 fn test_append_views_gathered_compacts_unreferenced_values() {
1674 const DEAD: &str = "a dead value nobody gathers, far too long to inline";
1675 const OTHER: &str = "another value far too long to inline";
1676
1677 let mut ctx = SESSION.create_execution_ctx();
1678 let dictionary =
1679 <VarBinViewArray as FromIterator<_>>::from_iter([Some(LONG), Some(DEAD), Some(OTHER)]);
1680 assert_eq!(dictionary.data_buffers().len(), 1);
1681 let buffers = dictionary
1682 .data_buffers()
1683 .iter()
1684 .map(|buffer| buffer.as_host().clone())
1685 .collect::<Vec<_>>();
1686
1687 let mut builder = VarBinViewBuilder::with_compaction_in(
1688 DType::Utf8(Nullability::Nullable),
1689 8,
1690 1.0,
1691 BufferAllocatorRef::statically_allocated(),
1692 );
1693 let codes: [usize; 5] = [2, 0, usize::MAX, 2, 0];
1694 builder.append_views_gathered(
1695 buffers,
1696 dictionary.views(),
1697 &Mask::from_iter([true, true, false, true, true]),
1698 |row| codes[row],
1699 );
1700
1701 let actual = builder.finish_into_varbinview();
1702 assert_eq!(actual.data_buffers().len(), 1);
1703 assert_eq!(
1704 actual.data_buffers()[0].len(),
1705 LONG.len() + OTHER.len(),
1706 "the rewritten buffer must hold each referenced value exactly once"
1707 );
1708
1709 let expected = <VarBinViewArray as FromIterator<_>>::from_iter([
1710 Some(OTHER),
1711 Some(LONG),
1712 None,
1713 Some(OTHER),
1714 Some(LONG),
1715 ]);
1716 assert_arrays_eq!(actual, expected, &mut ctx);
1717 }
1718
1719 #[test]
1722 fn test_append_views_gathered_slices_contiguous_range() {
1723 const TAIL: &str = "the referenced tail value, too long to inline";
1724
1725 let mut ctx = SESSION.create_execution_ctx();
1726 let dictionary = <VarBinViewArray as FromIterator<_>>::from_iter([Some(LONG), Some(TAIL)]);
1727 let heap = dictionary.data_buffers()[0].as_host().clone();
1728
1729 let mut builder = VarBinViewBuilder::with_compaction_in(
1730 DType::Utf8(Nullability::Nullable),
1731 8,
1732 1.0,
1733 BufferAllocatorRef::statically_allocated(),
1734 );
1735 builder.append_views_gathered(
1736 [heap.clone()],
1737 dictionary.views(),
1738 &Mask::new_true(2),
1739 |_| 1,
1740 );
1741
1742 let actual = builder.finish_into_varbinview();
1743 assert_eq!(actual.data_buffers().len(), 1);
1744 assert_eq!(actual.data_buffers()[0].len(), TAIL.len());
1745 assert_eq!(actual.data_buffers()[0].as_host().as_ptr(), unsafe {
1747 heap.as_ptr().add(LONG.len())
1748 });
1749
1750 let expected = <VarBinViewArray as FromIterator<_>>::from_iter([Some(TAIL), Some(TAIL)]);
1751 assert_arrays_eq!(actual, expected, &mut ctx);
1752 }
1753
1754 #[test]
1756 fn test_append_views_gathered_keeps_utilized_buffer() {
1757 const SHORTER: &str = "a shorter long value";
1758
1759 let mut ctx = SESSION.create_execution_ctx();
1760 let dictionary =
1761 <VarBinViewArray as FromIterator<_>>::from_iter([Some(LONG), Some(SHORTER)]);
1762 let heap = dictionary.data_buffers()[0].as_host().clone();
1763
1764 let mut builder = VarBinViewBuilder::with_compaction_in(
1765 DType::Utf8(Nullability::Nullable),
1766 8,
1767 0.5,
1768 BufferAllocatorRef::statically_allocated(),
1769 );
1770 builder.append_views_gathered(
1771 [heap.clone()],
1772 dictionary.views(),
1773 &Mask::new_true(1),
1774 |_| 0,
1775 );
1776
1777 let actual = builder.finish_into_varbinview();
1778 assert_eq!(actual.data_buffers().len(), 1);
1779 assert_eq!(actual.data_buffers()[0].as_host().as_ptr(), heap.as_ptr());
1780 assert_eq!(actual.data_buffers()[0].len(), heap.len());
1781
1782 let expected = <VarBinViewArray as FromIterator<_>>::from_iter([Some(LONG)]);
1783 assert_arrays_eq!(actual, expected, &mut ctx);
1784 }
1785
1786 #[test]
1789 fn test_append_views_gathered_all_null_drops_buffers() {
1790 let mut ctx = SESSION.create_execution_ctx();
1791 let dictionary = <VarBinViewArray as FromIterator<_>>::from_iter([Some(LONG)]);
1792 let buffers = dictionary
1793 .data_buffers()
1794 .iter()
1795 .map(|buffer| buffer.as_host().clone())
1796 .collect::<Vec<_>>();
1797
1798 let mut builder = VarBinViewBuilder::with_compaction_in(
1799 DType::Utf8(Nullability::Nullable),
1800 8,
1801 1.0,
1802 BufferAllocatorRef::statically_allocated(),
1803 );
1804 builder.append_views_gathered(buffers, dictionary.views(), &Mask::new_false(3), |_| {
1805 usize::MAX
1806 });
1807
1808 let actual = builder.finish_into_varbinview();
1809 assert!(
1810 actual.data_buffers().is_empty(),
1811 "an all-null gather must not retain any buffers"
1812 );
1813
1814 let expected = <VarBinViewArray as FromIterator<_>>::from_iter([None::<&str>, None, None]);
1815 assert_arrays_eq!(actual, expected, &mut ctx);
1816 }
1817
1818 #[test]
1820 fn test_append_buffer_with_lengths_drops_fully_inlined_heap() {
1821 let mut ctx = SESSION.create_execution_ctx();
1822 let mut builder = VarBinViewBuilder::with_compaction_in(
1823 DType::Utf8(Nullability::Nullable),
1824 4,
1825 1.0,
1826 BufferAllocatorRef::statically_allocated(),
1827 );
1828
1829 let heap = ByteBuffer::copy_from(b"shorttinysmall".as_slice());
1830 builder.append_buffer_with_lengths(heap, &[5u32, 4, 5], &Mask::new_true(3));
1831
1832 let actual = builder.finish_into_varbinview();
1833 assert!(
1834 actual.data_buffers().is_empty(),
1835 "a fully-inlined append must not retain any value bytes"
1836 );
1837
1838 let expected = <VarBinViewArray as FromIterator<_>>::from_iter([
1839 Some("short"),
1840 Some("tiny"),
1841 Some("small"),
1842 ]);
1843 assert_arrays_eq!(actual, expected, &mut ctx);
1844 }
1845
1846 #[test]
1847 fn test_utf8_builder() {
1848 let mut ctx = SESSION.create_execution_ctx();
1849 let mut builder = VarBinViewBuilder::with_capacity_in(
1850 DType::Utf8(Nullability::Nullable),
1851 10,
1852 BufferAllocatorRef::statically_allocated(),
1853 );
1854
1855 builder.append_value("Hello");
1856 builder.append_null();
1857 builder.append_value("World");
1858
1859 builder.append_nulls(2);
1860
1861 builder.append_zeros(2);
1862 builder.append_value("test");
1863
1864 let actual = builder.finish();
1865 let expected = <VarBinViewArray as FromIterator<_>>::from_iter([
1866 Some("Hello"),
1867 None,
1868 Some("World"),
1869 None,
1870 None,
1871 Some(""),
1872 Some(""),
1873 Some("test"),
1874 ]);
1875 for (index, value) in [
1876 Some("Hello"),
1877 None,
1878 Some("World"),
1879 None,
1880 None,
1881 Some(""),
1882 Some(""),
1883 Some("test"),
1884 ]
1885 .into_iter()
1886 .enumerate()
1887 {
1888 let expected = value.map_or_else(
1889 || Scalar::null(DType::Utf8(Nullability::Nullable)),
1890 |value| Scalar::utf8(value, Nullability::Nullable),
1891 );
1892 assert_eq!(actual.execute_scalar(index, &mut ctx).unwrap(), expected);
1893 }
1894 assert_arrays_eq!(actual, expected, &mut ctx);
1895 }
1896
1897 #[test]
1898 fn test_utf8_builder_with_extend() {
1899 let mut ctx = SESSION.create_execution_ctx();
1900 let array = {
1901 let mut builder = VarBinViewBuilder::with_capacity_in(
1902 DType::Utf8(Nullability::Nullable),
1903 10,
1904 BufferAllocatorRef::statically_allocated(),
1905 );
1906 builder.append_null();
1907 builder.append_value("Hello2");
1908 builder.finish()
1909 };
1910 let mut builder = VarBinViewBuilder::with_capacity_in(
1911 DType::Utf8(Nullability::Nullable),
1912 10,
1913 BufferAllocatorRef::statically_allocated(),
1914 );
1915
1916 builder.append_value("Hello1");
1917 array.append_to_builder(&mut builder, &mut ctx).unwrap();
1918 builder.append_nulls(2);
1919 builder.append_value("Hello3");
1920
1921 let actual = builder.finish_into_canonical(&mut ctx);
1922 let expected = <VarBinViewArray as FromIterator<_>>::from_iter([
1923 Some("Hello1"),
1924 None,
1925 Some("Hello2"),
1926 None,
1927 None,
1928 Some("Hello3"),
1929 ]);
1930 let actual = actual.into_array();
1931 for (index, value) in [
1932 Some("Hello1"),
1933 None,
1934 Some("Hello2"),
1935 None,
1936 None,
1937 Some("Hello3"),
1938 ]
1939 .into_iter()
1940 .enumerate()
1941 {
1942 let expected = value.map_or_else(
1943 || Scalar::null(DType::Utf8(Nullability::Nullable)),
1944 |value| Scalar::utf8(value, Nullability::Nullable),
1945 );
1946 assert_eq!(actual.execute_scalar(index, &mut ctx).unwrap(), expected);
1947 }
1948 assert_arrays_eq!(actual, expected.into_array(), &mut ctx);
1949 }
1950
1951 #[test]
1952 fn test_buffer_deduplication() -> VortexResult<()> {
1953 let array = {
1954 let mut builder = VarBinViewBuilder::with_capacity_in(
1955 DType::Utf8(Nullability::Nullable),
1956 10,
1957 BufferAllocatorRef::statically_allocated(),
1958 );
1959 builder.append_value("This is a long string that should not be inlined");
1960 builder.append_value("short string");
1961 builder.finish_into_varbinview()
1962 };
1963
1964 assert_eq!(array.data_buffers().len(), 1);
1965 let mut builder = VarBinViewBuilder::with_buffer_deduplication_in(
1966 DType::Utf8(Nullability::Nullable),
1967 10,
1968 BufferAllocatorRef::statically_allocated(),
1969 );
1970
1971 let mut ctx = SESSION.create_execution_ctx();
1972
1973 array.append_to_builder(&mut builder, &mut ctx)?;
1974 assert_eq!(builder.completed_block_count(), 1);
1975
1976 array
1977 .slice(1..2)?
1978 .append_to_builder(&mut builder, &mut ctx)?;
1979 array
1980 .slice(0..1)?
1981 .append_to_builder(&mut builder, &mut ctx)?;
1982 assert_eq!(builder.completed_block_count(), 1);
1983
1984 let array2 = {
1985 let mut builder = VarBinViewBuilder::with_capacity_in(
1986 DType::Utf8(Nullability::Nullable),
1987 10,
1988 BufferAllocatorRef::statically_allocated(),
1989 );
1990 builder.append_value("This is a long string that should not be inlined");
1991 builder.finish_into_varbinview()
1992 };
1993
1994 array2.append_to_builder(&mut builder, &mut ctx)?;
1995 assert_eq!(builder.completed_block_count(), 2);
1996
1997 array
1998 .slice(0..1)?
1999 .append_to_builder(&mut builder, &mut ctx)?;
2000 array2
2001 .slice(0..1)?
2002 .append_to_builder(&mut builder, &mut ctx)?;
2003 assert_eq!(builder.completed_block_count(), 2);
2004 let actual = builder.finish_into_varbinview();
2005 let long = "This is a long string that should not be inlined";
2006 assert_eq!(actual.dtype(), &DType::Utf8(Nullability::Nullable));
2007 assert_eq!(actual.len(), 7);
2008 for (index, value) in [long, "short string", "short string", long, long, long, long]
2009 .into_iter()
2010 .enumerate()
2011 {
2012 assert_eq!(
2013 actual.execute_scalar(index, &mut ctx)?,
2014 Scalar::utf8(value, Nullability::Nullable)
2015 );
2016 }
2017 Ok(())
2018 }
2019
2020 #[test]
2021 fn test_append_scalar() {
2022 let mut ctx = SESSION.create_execution_ctx();
2023 use crate::scalar::Scalar;
2024
2025 let mut utf8_builder = VarBinViewBuilder::with_capacity_in(
2027 DType::Utf8(Nullability::Nullable),
2028 10,
2029 BufferAllocatorRef::statically_allocated(),
2030 );
2031
2032 let utf8_scalar1 = Scalar::utf8("hello", Nullability::Nullable);
2034 utf8_builder.append_scalar(&utf8_scalar1).unwrap();
2035
2036 let utf8_scalar2 = Scalar::utf8("world", Nullability::Nullable);
2038 utf8_builder.append_scalar(&utf8_scalar2).unwrap();
2039
2040 let null_scalar = Scalar::null(DType::Utf8(Nullability::Nullable));
2042 utf8_builder.append_scalar(&null_scalar).unwrap();
2043
2044 let array = utf8_builder.finish();
2045 let expected =
2046 <VarBinViewArray as FromIterator<_>>::from_iter([Some("hello"), Some("world"), None]);
2047 assert_arrays_eq!(&array, &expected, &mut ctx);
2048
2049 let mut binary_builder = VarBinViewBuilder::with_capacity_in(
2051 DType::Binary(Nullability::Nullable),
2052 10,
2053 BufferAllocatorRef::statically_allocated(),
2054 );
2055
2056 let binary_scalar = Scalar::binary(vec![1u8, 2, 3], Nullability::Nullable);
2057 binary_builder.append_scalar(&binary_scalar).unwrap();
2058
2059 let binary_null = Scalar::null(DType::Binary(Nullability::Nullable));
2060 binary_builder.append_scalar(&binary_null).unwrap();
2061
2062 let binary_array = binary_builder.finish();
2063 let expected =
2064 <VarBinViewArray as FromIterator<_>>::from_iter([Some(vec![1u8, 2, 3]), None]);
2065 assert_arrays_eq!(&binary_array, &expected, &mut ctx);
2066
2067 let mut builder = VarBinViewBuilder::with_capacity_in(
2069 DType::Utf8(Nullability::NonNullable),
2070 10,
2071 BufferAllocatorRef::statically_allocated(),
2072 );
2073 let wrong_scalar = Scalar::from(42i32);
2074 assert!(builder.append_scalar(&wrong_scalar).is_err());
2075 }
2076
2077 #[test]
2078 fn test_buffer_growth_strategies() {
2079 use super::BufferGrowthStrategy;
2080
2081 let mut strategy = BufferGrowthStrategy::fixed(1024);
2083
2084 assert_eq!(strategy.next_size(), 1024);
2086 assert_eq!(strategy.next_size(), 1024);
2087 assert_eq!(strategy.next_size(), 1024);
2088
2089 let mut strategy = BufferGrowthStrategy::exponential(1024, 8192);
2091
2092 assert_eq!(strategy.next_size(), 1024); assert_eq!(strategy.next_size(), 2048); assert_eq!(strategy.next_size(), 4096); assert_eq!(strategy.next_size(), 8192); assert_eq!(strategy.next_size(), 8192); }
2099
2100 #[test]
2101 fn test_large_value_allocation() {
2102 use super::BufferGrowthStrategy;
2103 use super::VarBinViewBuilder;
2104
2105 let mut builder = VarBinViewBuilder::new_in(
2106 DType::Binary(Nullability::Nullable),
2107 10,
2108 Default::default(),
2109 BufferGrowthStrategy::exponential(1024, 4096),
2110 0.0,
2111 BufferAllocatorRef::statically_allocated(),
2112 );
2113
2114 let large_value = vec![0u8; 8192];
2116
2117 builder.append_value(&large_value);
2119
2120 let array = builder.finish_into_varbinview();
2121 assert_eq!(array.len(), 1);
2122
2123 let retrieved = array
2125 .execute_scalar(0, &mut SESSION.create_execution_ctx())
2126 .unwrap()
2127 .as_binary()
2128 .value()
2129 .cloned()
2130 .unwrap();
2131 assert_eq!(retrieved.len(), 8192);
2132 assert_eq!(retrieved.as_slice(), &large_value);
2133 }
2134}