Skip to content

Commit f9bf628

Browse files
rluvatonmzabaluev
andauthored
feat(coalesce): add size function (#10331)
# Which issue does this PR close? N/A But this is prerequisite for: - apache/datafusion#23385 # Rationale for this change We want to be able to reserve memory for the data that `BatchCoalescer` is using in DataFusion and other places # What changes are included in this PR? added `size` functions and implement sizing + tests # Are these changes tested? Yes # Are there any user-facing changes? yes, new function --------- Co-authored-by: Mikhail Zabaluev <[email protected]>
1 parent a5158c8 commit f9bf628

4 files changed

Lines changed: 478 additions & 10 deletions

File tree

‎arrow-select/src/coalesce.rs‎

Lines changed: 127 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -583,6 +583,22 @@ impl BatchCoalescer {
583583
pub fn next_completed_batch(&mut self) -> Option<RecordBatch> {
584584
self.completed.pop_front()
585585
}
586+
587+
/// Returns the number of bytes used by this data structure.
588+
pub fn size(&self) -> usize {
589+
self.in_progress_arrays.capacity() * size_of::<Box<dyn InProgressArray>>()
590+
+ self
591+
.in_progress_arrays
592+
.iter()
593+
.map(|array| array.size())
594+
.sum::<usize>()
595+
+ self.completed.capacity() * size_of::<RecordBatch>()
596+
+ self
597+
.completed
598+
.iter()
599+
.map(|batch| batch.get_array_memory_size())
600+
.sum::<usize>()
601+
}
586602
}
587603

588604
impl BatchCoalescer {
@@ -742,6 +758,9 @@ trait InProgressArray: std::fmt::Debug + Send + Sync {
742758

743759
/// Finish the currently in-progress array and return it as an `ArrayRef`
744760
fn finish(&mut self) -> Result<ArrayRef, ArrowError>;
761+
762+
/// Get the number of bytes this array is using
763+
fn size(&self) -> usize;
745764
}
746765

747766
#[cfg(test)]
@@ -2683,4 +2702,112 @@ mod tests {
26832702
"unexpected error: {err}"
26842703
);
26852704
}
2705+
2706+
#[test]
2707+
fn test_size_grows_with_buffering_and_shrinks_when_draining() {
2708+
let batch = uint32_batch(0..8);
2709+
let mut coalescer = BatchCoalescer::new(batch.schema(), 21);
2710+
let baseline = coalescer.size();
2711+
assert!(baseline > 0, "size includes container capacities");
2712+
2713+
// Buffer rows without completing a batch
2714+
coalescer.push_batch(batch.clone()).unwrap();
2715+
assert!(coalescer.next_completed_batch().is_none());
2716+
let buffered = coalescer.size();
2717+
assert!(
2718+
buffered > baseline,
2719+
"buffering rows should grow size ({buffered} > {baseline})"
2720+
);
2721+
2722+
// Push enough to complete several batches
2723+
for _ in 0..10 {
2724+
coalescer.push_batch(batch.clone()).unwrap();
2725+
}
2726+
let peak = coalescer.size();
2727+
assert!(peak > buffered);
2728+
2729+
// Draining completed batches must never grow the reported size
2730+
let mut prev = peak;
2731+
let mut drained_any = false;
2732+
while coalescer.next_completed_batch().is_some() {
2733+
drained_any = true;
2734+
let now = coalescer.size();
2735+
assert!(now <= prev, "size grew while draining: {now} > {prev}");
2736+
prev = now;
2737+
}
2738+
assert!(drained_any);
2739+
assert!(
2740+
prev < peak,
2741+
"draining completed batches should release memory"
2742+
);
2743+
}
2744+
2745+
#[test]
2746+
fn test_size_string_view_buffers_released_after_drain() {
2747+
// Long strings spill into external data buffers, exercising the byte-view
2748+
// size accounting through the real coalescer path (including compaction).
2749+
let batch = stringview_batch_repeated(
2750+
1000,
2751+
[Some("this string is definitely longer than 12 bytes")],
2752+
);
2753+
let mut coalescer = BatchCoalescer::new(batch.schema(), 4096);
2754+
let baseline = coalescer.size();
2755+
2756+
for _ in 0..20 {
2757+
coalescer.push_batch(batch.clone()).unwrap();
2758+
}
2759+
let peak = coalescer.size();
2760+
assert!(
2761+
peak > baseline,
2762+
"buffered string view data should grow size ({peak} > {baseline})"
2763+
);
2764+
2765+
coalescer.finish_buffered_batch().unwrap();
2766+
while coalescer.next_completed_batch().is_some() {}
2767+
2768+
// Once fully drained the in-progress byte-view buffers are released.
2769+
let drained = coalescer.size();
2770+
assert!(
2771+
drained < peak,
2772+
"draining should release buffered data ({drained} < {peak})"
2773+
);
2774+
}
2775+
2776+
/// Every byte added to the accounting must eventually be removed: running the
2777+
/// exact same push/finish/drain sequence twice must report identical sizes.
2778+
/// This catches accounting leaks and drift without hard-coding magic numbers.
2779+
#[test]
2780+
fn test_size_accounting_conserved_across_cycles() {
2781+
// Primitive column: internal capacities stabilize after the first cycle
2782+
// (unlike byte-view, whose buffer sizer keeps growing), so the readings
2783+
// are deterministic across cycles.
2784+
let batch = uint32_batch(0..8);
2785+
let mut coalescer = BatchCoalescer::new(batch.schema(), 4096);
2786+
2787+
let run_cycle = |coalescer: &mut BatchCoalescer| {
2788+
for _ in 0..20 {
2789+
coalescer.push_batch(batch.clone()).unwrap();
2790+
}
2791+
coalescer.finish_buffered_batch().unwrap();
2792+
let peak = coalescer.size();
2793+
while coalescer.next_completed_batch().is_some() {}
2794+
(peak, coalescer.size())
2795+
};
2796+
2797+
let (peak1, drained1) = run_cycle(&mut coalescer);
2798+
let (peak2, drained2) = run_cycle(&mut coalescer);
2799+
2800+
assert_eq!(
2801+
peak1, peak2,
2802+
"identical work must report identical peak size"
2803+
);
2804+
assert_eq!(
2805+
drained1, drained2,
2806+
"fully-drained size must be stable across cycles (no accounting leak)"
2807+
);
2808+
assert!(
2809+
drained1 < peak1,
2810+
"draining must release the accounted memory"
2811+
);
2812+
}
26862813
}

‎arrow-select/src/coalesce/byte_view.rs‎

Lines changed: 137 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -54,6 +54,10 @@ pub(crate) struct InProgressByteViewArray<B: ByteViewType> {
5454
/// Phantom so we can use the same struct for both StringViewArray and
5555
/// BinaryViewArray
5656
_phantom: PhantomData<B>,
57+
/// The size in bytes the [`Buffer`]s in [`Self::completed`] is taking
58+
completed_buffers_size: usize,
59+
/// The size in bytes from [`Self::source`] that it is being used in [`Self::completed`]
60+
size_of_completed_buffers_from_current_source: usize,
5761
}
5862

5963
struct Source {
@@ -89,6 +93,8 @@ impl<B: ByteViewType> InProgressByteViewArray<B> {
8993
nulls: NullBufferBuilder::new(batch_size), // no allocation
9094
current: None,
9195
completed: vec![],
96+
completed_buffers_size: 0,
97+
size_of_completed_buffers_from_current_source: 0,
9298
buffer_source,
9399
_phantom: PhantomData,
94100
}
@@ -109,7 +115,10 @@ impl<B: ByteViewType> InProgressByteViewArray<B> {
109115
let Some(next_buffer) = self.current.take() else {
110116
return;
111117
};
112-
self.completed.push(next_buffer.into());
118+
let buffer: Buffer = next_buffer.into();
119+
120+
self.completed_buffers_size += buffer.capacity();
121+
self.completed.push(buffer);
113122
}
114123

115124
fn append_views_by_filter(&mut self, views: &[u128], filter: &FilterPredicate) {
@@ -169,10 +178,26 @@ impl<B: ByteViewType> InProgressByteViewArray<B> {
169178

170179
/// Append views to self.views, updating the buffer index if necessary
171180
#[inline(never)]
172-
fn append_views_and_update_buffer_index(&mut self, views: &[u128], buffers: &[Buffer]) {
181+
fn append_views_and_update_buffer_index(
182+
&mut self,
183+
views: &[u128],
184+
buffers: &[Buffer],
185+
is_reused: bool,
186+
) {
173187
if let Some(buffer) = self.current.take() {
174-
self.completed.push(buffer.into());
188+
let buffer: Buffer = buffer.into();
189+
self.completed_buffers_size += buffer.capacity();
190+
self.completed.push(buffer);
175191
}
192+
193+
let buffers_size = buffers.iter().map(|b| b.capacity()).sum::<usize>();
194+
if !is_reused {
195+
self.completed_buffers_size += buffers_size;
196+
} else if self.size_of_completed_buffers_from_current_source == 0 {
197+
// Don't double count buffers size if already counted that
198+
self.size_of_completed_buffers_from_current_source += buffers_size;
199+
}
200+
176201
let starting_buffer: u32 = self.completed.len().try_into().expect("too many buffers");
177202
self.completed.extend_from_slice(buffers);
178203

@@ -251,8 +276,9 @@ impl<B: ByteViewType> InProgressByteViewArray<B> {
251276
let remaining_view_buffer_size = view_buffer_size - string_bytes_to_copy;
252277

253278
self.append_views_and_copy_strings_inner(first_views, current, buffers);
254-
let completed = self.current.take().expect("completed");
255-
self.completed.push(completed.into());
279+
let completed: Buffer = self.current.take().expect("completed").into();
280+
self.completed_buffers_size += completed.capacity();
281+
self.completed.push(completed);
256282

257283
// Copy any remaining views into a new buffer
258284
let remaining_views = &views[num_view_to_current..];
@@ -328,13 +354,18 @@ impl<B: ByteViewType> InProgressByteViewArray<B> {
328354
}
329355
b.as_u128()
330356
});
357+
331358
self.views.extend(new_views);
332359
self.current = Some(dst_buffer);
333360
}
334361
}
335362

336363
impl<B: ByteViewType> InProgressArray for InProgressByteViewArray<B> {
337364
fn set_source(&mut self, source: Option<ArrayRef>) {
365+
// If used values from source, add only the size that was used
366+
self.completed_buffers_size += self.size_of_completed_buffers_from_current_source;
367+
self.size_of_completed_buffers_from_current_source = 0;
368+
338369
self.source = source.map(|array| {
339370
let s = array.as_byte_view::<B>();
340371

@@ -358,7 +389,7 @@ impl<B: ByteViewType> InProgressArray for InProgressByteViewArray<B> {
358389
need_gc,
359390
ideal_buffer_size,
360391
}
361-
})
392+
});
362393
}
363394

364395
fn copy_rows(&mut self, offset: usize, len: usize) -> Result<(), ArrowError> {
@@ -397,7 +428,7 @@ impl<B: ByteViewType> InProgressArray for InProgressByteViewArray<B> {
397428
if source.need_gc {
398429
self.append_views_and_copy_strings(views, source.ideal_buffer_size, buffers);
399430
} else {
400-
self.append_views_and_update_buffer_index(views, buffers);
431+
self.append_views_and_update_buffer_index(views, buffers, true);
401432
}
402433
self.source = Some(source);
403434
Ok(())
@@ -452,7 +483,7 @@ impl<B: ByteViewType> InProgressArray for InProgressByteViewArray<B> {
452483
} else {
453484
self.nulls.append_n_non_nulls(filter.count());
454485
}
455-
self.append_views_and_update_buffer_index(filtered.views(), filtered.data_buffers());
486+
self.append_views_and_update_buffer_index(filtered.views(), filtered.data_buffers(), false);
456487
Ok(())
457488
}
458489

@@ -464,12 +495,27 @@ impl<B: ByteViewType> InProgressArray for InProgressByteViewArray<B> {
464495
let nulls = self.nulls.finish();
465496
self.nulls = NullBufferBuilder::new(self.batch_size);
466497

498+
// Not reusing anything since we took all complete
499+
self.size_of_completed_buffers_from_current_source = 0;
500+
self.completed_buffers_size = 0;
501+
467502
// Safety: we created valid views and buffers above and the
468503
// input arrays had value data and nulls
469504
let new_array =
470505
unsafe { GenericByteViewArray::<B>::new_unchecked(views.into(), buffers, nulls) };
471506
Ok(Arc::new(new_array))
472507
}
508+
509+
fn size(&self) -> usize {
510+
self.completed_buffers_size
511+
+ self.current.as_ref().map_or(0, |c| c.capacity())
512+
+ self.nulls.allocated_size()
513+
+ self.views.capacity() * size_of::<u128>()
514+
+ self
515+
.source
516+
.as_ref()
517+
.map_or(0, |s| s.array.get_array_memory_size())
518+
}
473519
}
474520

475521
const STARTING_BLOCK_SIZE: usize = 4 * 1024; // (note the first size used is actually 8KiB)
@@ -607,4 +653,87 @@ mod tests {
607653
"expected filtered output to reuse the source data buffer"
608654
);
609655
}
656+
657+
/// Build a compacted BinaryViewArray whose values all spill into external
658+
/// data buffers. `gc()` makes the buffers dense so the coalescer reuses them
659+
/// (`need_gc == false`) rather than copying/compacting them.
660+
fn non_inline_array(n: usize) -> (BinaryViewArray, usize) {
661+
let values = (0..n)
662+
.map(|i| format!("This value is longer than 12 bytes: {i}").into_bytes())
663+
.collect::<Vec<_>>();
664+
let array = BinaryViewArray::from_iter(values.iter().map(|v| Some(v.as_slice()))).gc();
665+
assert!(!array.data_buffers().is_empty());
666+
let buffer_capacity = array.data_buffers().iter().map(|b| b.capacity()).sum();
667+
(array, buffer_capacity)
668+
}
669+
670+
#[test]
671+
fn test_size_empty() {
672+
let in_progress = InProgressByteViewArray::<BinaryViewType>::new(64);
673+
assert_eq!(in_progress.size(), 0);
674+
}
675+
676+
#[test]
677+
fn test_size_reused_buffers_not_double_counted() {
678+
let (array, buffer_capacity) = non_inline_array(64);
679+
let source: ArrayRef = Arc::new(array);
680+
681+
let mut in_progress = InProgressByteViewArray::<BinaryViewType>::new(64);
682+
in_progress.set_source(Some(Arc::clone(&source)));
683+
684+
in_progress.copy_rows(0, 60).unwrap();
685+
in_progress.copy_rows(60, 4).unwrap();
686+
687+
// The reused buffers now live in `completed`, but while the source is
688+
// still set they are counted via the source, not `completed_buffers_size`,
689+
// to avoid double counting them.
690+
assert_eq!(in_progress.completed_buffers_size, 0);
691+
assert_eq!(
692+
in_progress.size_of_completed_buffers_from_current_source,
693+
buffer_capacity,
694+
);
695+
696+
// Setting a new source commits the pending reused-buffer bytes, since the
697+
// old source (and its double count) is dropped.
698+
let other: ArrayRef = Arc::new(BinaryViewArray::from_iter(std::iter::once(Some(
699+
b"short".as_slice(),
700+
))));
701+
in_progress.set_source(Some(Arc::clone(&other)));
702+
assert_eq!(in_progress.completed_buffers_size, buffer_capacity);
703+
assert_eq!(in_progress.size_of_completed_buffers_from_current_source, 0);
704+
705+
// finish() releases everything.
706+
in_progress.finish().unwrap();
707+
assert_eq!(in_progress.completed_buffers_size, 0);
708+
assert_eq!(in_progress.size_of_completed_buffers_from_current_source, 0);
709+
}
710+
711+
#[test]
712+
fn size_should_be_the_same_if_copying_multiple_time_from_same_source_or_once() {
713+
let (array, _buffer_capacity) = non_inline_array(64);
714+
let source: ArrayRef = Arc::new(array);
715+
716+
let in_progress_size_with_split = {
717+
let mut in_progress = InProgressByteViewArray::<BinaryViewType>::new(64);
718+
in_progress.set_source(Some(Arc::clone(&source)));
719+
720+
in_progress.copy_rows(0, 60).unwrap();
721+
in_progress.copy_rows(60, 4).unwrap();
722+
in_progress.set_source(None);
723+
724+
in_progress.size()
725+
};
726+
727+
let in_progress_size_without_split = {
728+
let mut in_progress = InProgressByteViewArray::<BinaryViewType>::new(64);
729+
in_progress.set_source(Some(Arc::clone(&source)));
730+
731+
in_progress.copy_rows(0, 64).unwrap();
732+
in_progress.set_source(None);
733+
734+
in_progress.size()
735+
};
736+
737+
assert_eq!(in_progress_size_with_split, in_progress_size_without_split);
738+
}
610739
}

0 commit comments

Comments
 (0)