Skip to content

Commit d80d213

Browse files
adriangbclaude
authored andcommitted
perf: reuse GroupsAccumulatorAdapter scratch buffers across batches (apache#25605)
## Which issue does this PR close? - Closes apache#25604. ## Rationale for this change `GroupsAccumulatorAdapter` runs every aggregate that has no `GroupsAccumulator` of its own. For each input batch, `invoke_per_accumulator` allocated three new buffers, `groups_with_rows`, `offsets` and `batch_indices`, and dropped them at the end of the batch. @alamb suggested to reuse them in apache#25123 (comment). ## What changes are included in this PR? 1. **Reuse `groups_with_rows` and `offsets`.** A new `Scratch` struct on the adapter holds the buffers. Each batch clears them and fills them again, so they allocate only when a batch needs more capacity than an earlier batch. `invoke_per_accumulator` takes the buffers out of `self` for the batch and puts them back on every return path, errors included. The body moves unchanged into `invoke_per_accumulator_with_scratch`. 2. **Reuse `batch_indices`.** The adapter moves the buffer into the `UInt32Array` for the `take` kernels without a copy. The kernels only borrow the array, thus the adapter then gets the buffer back without a copy through `into_parts`. 3. **Shrink oversized buffers.** A buffer keeps the capacity of the largest batch that it has seen. After each batch, the adapter shrinks a buffer whose capacity is more than 64 Ki entries and more than 4 times what the batch used. It shrinks to the smaller of the two, so it never keeps more than either limit allows. Thus one unusually large batch does not make the adapter keep that memory for all the batches after it. The adapter charges the change in the capacity of the buffers to `allocation_bytes`, thus `GroupsAccumulator::size` includes them and the memory pool sees them. It releases them when an emit leaves no group, thus an adapter that has emitted all groups still reports 0 bytes. Each adapter belongs to one partition's aggregate stream, and `GroupsAccumulator` methods take `&mut self`, so the buffers are never shared between partitions. I have not measured a speed change. This removes three allocations for each batch, while the same batch calls `Accumulator::update_batch` once for each group that it touches. Thus I expect the change to be small. ## What is the testing strategy for this PR? - `adapter_charges_retained_indices_once_and_releases_them`, `adapter_clears_successful_group_indices_after_later_error` and `adapter_reconciles_allocation_after_later_error_with_grouped_metric` check the exact memory charge, which now includes the scratch buffers. The first one also checks that the adapter keeps some scratch capacity after a batch, that `batch_indices` comes back from the `take` kernels, and that `size()` is 0 after `evaluate(EmitTo::All)`. - `adapter_releases_oversized_scratch` sends a batch with 128 Ki groups and then a batch with one row. It checks that the second batch shrinks each large buffer to exactly 4 times what it used, and that `size()` goes down by the released amount. To make sure that these tests catch an error, I removed each part in turn: - Without the charge for the scratch buffers, the three accounting tests fail. - Without the release on emit, `adapter_charges_retained_indices_once_and_releases_them` fails. - Without the shrink of oversized buffers, without it for `batch_indices` alone, with a release to capacity 0 instead of the shrink, or with a shrink to 64 Ki entries instead of the smaller limit, `adapter_releases_oversized_scratch` fails. The unit tests of `datafusion-functions-aggregate-common`, the `memory_limit` tests in `core_integration` and the sqllogictest suite pass. ## Are there any user-facing changes? No. There are no changes to any public API or to any result. 🤖 Generated with [Claude Code](https://claude.com/claude-code) --------- Co-authored-by: Claude Opus 5 <[email protected]>
1 parent 9b469be commit d80d213

1 file changed

Lines changed: 177 additions & 7 deletions

File tree

‎datafusion/functions-aggregate-common/src/aggregate/groups_accumulator.rs‎

Lines changed: 177 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -111,6 +111,63 @@ pub struct GroupsAccumulatorAdapter {
111111

112112
/// Optional aggregate-owned metric timed once for a grouped update batch.
113113
grouped_update_metric: OnceLock<Option<Arc<dyn AggregateMetric>>>,
114+
115+
/// Buffers reused by every call to `invoke_per_accumulator`
116+
scratch: Scratch,
117+
}
118+
119+
/// Per-batch buffers of [`GroupsAccumulatorAdapter`], kept between batches so
120+
/// that each batch does not allocate them again. Their capacity is part of
121+
/// [`GroupsAccumulatorAdapter::allocation_bytes`].
122+
#[derive(Default)]
123+
struct Scratch {
124+
/// Group indexes that have rows in the batch, in order of first
125+
/// appearance in the batch
126+
groups_with_rows: Vec<usize>,
127+
128+
/// `offsets[i]` is the index into `batch_indices` where the rows for
129+
/// `groups_with_rows[i]` start
130+
offsets: Vec<usize>,
131+
132+
/// Indices into the batch rows, with the rows of each group contiguous
133+
batch_indices: Vec<u32>,
134+
}
135+
136+
/// A scratch buffer keeps its capacity after a batch unless that capacity is
137+
/// more than this many entries and more than [`SCRATCH_RETAIN_RATIO`] times
138+
/// what the batch used. Then it shrinks to the smaller of the two. This stops
139+
/// one unusually large batch from holding memory for all the batches after it.
140+
const MAX_RETAINED_SCRATCH_ENTRIES: usize = 64 * 1024;
141+
142+
/// See [`MAX_RETAINED_SCRATCH_ENTRIES`]
143+
const SCRATCH_RETAIN_RATIO: usize = 4;
144+
145+
impl Scratch {
146+
fn allocated_size(&self) -> usize {
147+
self.groups_with_rows.allocated_size()
148+
+ self.offsets.allocated_size()
149+
+ self.batch_indices.allocated_size()
150+
}
151+
152+
/// Shrink each buffer that is much larger than the batch that just used
153+
/// it. Call this after the batch, before the buffers are cleared for the
154+
/// next batch.
155+
fn release_oversized(&mut self) {
156+
fn release_if_oversized<T>(buffer: &mut Vec<T>) {
157+
let keep = SCRATCH_RETAIN_RATIO * buffer.len();
158+
if buffer.capacity() > MAX_RETAINED_SCRATCH_ENTRIES
159+
&& buffer.capacity() > keep
160+
{
161+
// The batch is done with the contents, so clear them first
162+
// and the shrink has nothing to copy
163+
buffer.clear();
164+
buffer.shrink_to(MAX_RETAINED_SCRATCH_ENTRIES.min(keep));
165+
}
166+
}
167+
release_if_oversized(&mut self.groups_with_rows);
168+
release_if_oversized(&mut self.offsets);
169+
release_if_oversized(&mut self.batch_indices);
170+
}
114171
}
115172

116173
/// Maximum number of prepared group inputs retained while timing an
@@ -154,6 +211,7 @@ impl GroupsAccumulatorAdapter {
154211
allocation_bytes: 0,
155212
metrics: None,
156213
grouped_update_metric: OnceLock::new(),
214+
scratch: Scratch::default(),
157215
}
158216
}
159217

@@ -235,10 +293,45 @@ impl GroupsAccumulatorAdapter {
235293

236294
assert_eq!(values[0].len(), group_indices.len());
237295

296+
// Take the scratch buffers out of `self` for the batch, and put them
297+
// back on every return path, including errors
298+
let mut scratch = std::mem::take(&mut self.scratch);
299+
let scratch_size_pre = scratch.allocated_size();
300+
let result = self.invoke_per_accumulator_with_scratch(
301+
&mut scratch,
302+
values,
303+
group_indices,
304+
opt_filter,
305+
f,
306+
);
307+
scratch.release_oversized();
308+
self.adjust_allocation(scratch_size_pre, scratch.allocated_size());
309+
self.scratch = scratch;
310+
result
311+
}
312+
313+
/// Body of [`Self::invoke_per_accumulator`], with its scratch buffers
314+
fn invoke_per_accumulator_with_scratch<F>(
315+
&mut self,
316+
scratch: &mut Scratch,
317+
values: &[ArrayRef],
318+
group_indices: &[usize],
319+
opt_filter: Option<&BooleanArray>,
320+
f: F,
321+
) -> Result<()>
322+
where
323+
F: Fn(&mut dyn Accumulator, &[ArrayRef]) -> Result<()>,
324+
{
325+
let Scratch {
326+
groups_with_rows,
327+
offsets,
328+
batch_indices,
329+
} = scratch;
330+
238331
// groups_with_rows holds a list of group indexes that have any rows
239332
// that need to be accumulated, stored in order of first appearance in
240333
// this batch
241-
let mut groups_with_rows = vec![];
334+
groups_with_rows.clear();
242335

243336
// figure out which input rows correspond to which groups.
244337
// Note that self.state.indices starts empty for all groups (it is
@@ -263,11 +356,18 @@ impl GroupsAccumulatorAdapter {
263356
self.add_allocation(indices_allocation_delta);
264357

265358
// batch_indices holds indices into values, each group is contiguous
266-
let mut batch_indices = Vec::with_capacity(group_indices.len());
359+
batch_indices.clear();
360+
batch_indices
361+
.try_reserve(group_indices.len())
362+
.map_err(|e| {
363+
arrow_datafusion_err!(arrow::error::ArrowError::MemoryError(
364+
e.to_string()
365+
))
366+
})?;
267367

268368
// offsets[i] is index into batch_indices where the rows for
269369
// groups_with_rows[i] start
270-
let mut offsets = Vec::with_capacity(groups_with_rows.len() + 1);
370+
offsets.clear();
271371
offsets.push(0);
272372

273373
let mut offset_so_far = 0;
@@ -277,13 +377,20 @@ impl GroupsAccumulatorAdapter {
277377
offset_so_far += indices.len();
278378
offsets.push(offset_so_far);
279379
}
280-
let batch_indices = batch_indices.into();
380+
// Move the buffer into an array without a copy, for the take kernels
381+
let indices_array =
382+
PrimitiveArray::<UInt32Type>::from(std::mem::take(batch_indices));
281383

282384
// reorder the values and opt_filter by batch_indices so that
283385
// all values for each group are contiguous, then invoke the
284386
// accumulator once per group with values
285-
let values = take_arrays(values, &batch_indices, None)?;
286-
let opt_filter = get_filter_at_indices(opt_filter, &batch_indices)?;
387+
let values = take_arrays(values, &indices_array, None)?;
388+
let opt_filter = get_filter_at_indices(opt_filter, &indices_array)?;
389+
390+
// The take kernels only borrow the indices, so the array holds the
391+
// only reference to the buffer and we can get it back without a copy
392+
let (_, indices_buffer, _) = indices_array.into_parts();
393+
*batch_indices = indices_buffer.into_inner().into_vec().unwrap_or_default();
287394

288395
let grouped_update_metric = self.grouped_metric();
289396

@@ -398,6 +505,15 @@ impl GroupsAccumulatorAdapter {
398505
self.allocation_bytes = self.allocation_bytes.saturating_sub(size)
399506
}
400507

508+
/// Release the scratch buffers when no group is left, so that an adapter
509+
/// that has emitted every group holds no memory
510+
fn free_scratch_if_empty(&mut self) {
511+
if self.states.is_empty() {
512+
let scratch = std::mem::take(&mut self.scratch);
513+
self.free_allocation(scratch.allocated_size());
514+
}
515+
}
516+
401517
/// Release the allocation held by a state that is being emitted.
402518
fn free_state_allocation(&mut self, state: &AccumulatorState) {
403519
self.free_allocation(state.size());
@@ -456,6 +572,7 @@ impl GroupsAccumulator for GroupsAccumulatorAdapter {
456572
let result = ScalarValue::iter_to_array(results);
457573

458574
self.adjust_allocation(vec_size_pre, self.states.allocated_size());
575+
self.free_scratch_if_empty();
459576

460577
result
461578
}
@@ -520,6 +637,7 @@ impl GroupsAccumulator for GroupsAccumulatorAdapter {
520637
}
521638
}
522639
self.adjust_allocation(vec_size_pre, self.states.allocated_size());
640+
self.free_scratch_if_empty();
523641

524642
Ok(arrays)
525643
}
@@ -820,7 +938,14 @@ mod tests {
820938
let retained_indices = adapter.states[0].indices.allocated_size();
821939
assert!(retained_indices > 0);
822940
assert!(adapter.states[0].indices.is_empty());
823-
assert_eq!(adapter.size(), allocation_before_update + retained_indices);
941+
// The indices buffer comes back from the take kernels without a copy
942+
assert!(adapter.scratch.batch_indices.capacity() >= 4);
943+
let retained_scratch = adapter.scratch.allocated_size();
944+
assert!(retained_scratch > 0);
945+
assert_eq!(
946+
adapter.size(),
947+
allocation_before_update + retained_indices + retained_scratch
948+
);
824949

825950
let allocation_after_first_update = adapter.size();
826951
adapter.update_batch(&[values], &[0, 0, 0, 0], None, 1)?;
@@ -1085,6 +1210,7 @@ mod tests {
10851210
.iter()
10861211
.map(AccumulatorState::size)
10871212
.sum::<usize>()
1213+
+ accumulator.scratch.allocated_size()
10881214
);
10891215
accumulator.update_batch(&[values], &[0, 1], None, 2)?;
10901216

@@ -1129,6 +1255,7 @@ mod tests {
11291255
.iter()
11301256
.map(AccumulatorState::size)
11311257
.sum::<usize>()
1258+
+ accumulator.scratch.allocated_size()
11321259
);
11331260
Ok(())
11341261
}
@@ -1158,6 +1285,49 @@ mod tests {
11581285
Ok(())
11591286
}
11601287

1288+
/// One large batch must not make the adapter keep its scratch capacity
1289+
/// for the smaller batches after it.
1290+
#[test]
1291+
fn adapter_releases_oversized_scratch() -> Result<()> {
1292+
const NUM_GROUPS: usize = 2 * MAX_RETAINED_SCRATCH_ENTRIES;
1293+
let mut adapter = GroupsAccumulatorAdapter::new(|| {
1294+
Ok(Box::new(MaxAccumulator::try_new(&DataType::Int64)?)
1295+
as Box<dyn Accumulator>)
1296+
});
1297+
1298+
// every row is a different group, so the scratch buffers need one
1299+
// entry for each row
1300+
let group_indices: Vec<usize> = (0..NUM_GROUPS).collect();
1301+
let values: ArrayRef =
1302+
Arc::new(Int64Array::from_iter_values(0..NUM_GROUPS as i64));
1303+
adapter.update_batch(&[values], &group_indices, None, NUM_GROUPS)?;
1304+
let large_scratch = adapter.scratch.allocated_size();
1305+
assert!(large_scratch >= NUM_GROUPS * size_of::<usize>());
1306+
let size_after_large_batch = adapter.size();
1307+
1308+
// a batch with one row shrinks each large buffer to
1309+
// SCRATCH_RETAIN_RATIO times what it used: one group, two offsets and
1310+
// one row index
1311+
let values: ArrayRef = Arc::new(Int64Array::from(vec![1]));
1312+
adapter.update_batch(&[values], &[0], None, NUM_GROUPS)?;
1313+
let small_scratch = adapter.scratch.allocated_size();
1314+
assert!(small_scratch < large_scratch);
1315+
assert_eq!(
1316+
adapter.scratch.groups_with_rows.capacity(),
1317+
SCRATCH_RETAIN_RATIO
1318+
);
1319+
assert_eq!(adapter.scratch.offsets.capacity(), 2 * SCRATCH_RETAIN_RATIO);
1320+
assert_eq!(
1321+
adapter.scratch.batch_indices.capacity(),
1322+
SCRATCH_RETAIN_RATIO
1323+
);
1324+
assert_eq!(
1325+
adapter.size(),
1326+
size_after_large_batch - large_scratch + small_scratch
1327+
);
1328+
Ok(())
1329+
}
1330+
11611331
#[test]
11621332
fn adapter_preserving_evaluation_uses_accumulator_contract() -> Result<()> {
11631333
let mut accumulator = GroupsAccumulatorAdapter::new(|| {

0 commit comments

Comments
 (0)