Skip to content

Commit 6b5b27b

Browse files
committed
fix: charge retained scratch indices capacity in GroupsAccumulatorAdapter
`GroupsAccumulatorAdapter` tracks per-group memory in `allocation_bytes` by measuring each `AccumulatorState::size()` before and after accumulator work and applying the delta. `size()` includes the scratch `indices` vector's capacity, but that capacity is never charged, because: 1. `indices` grows in the per-row push loop, which runs before `sizes_pre` is measured; 2. `indices.clear()` after the accumulator call retains the capacity. So `sizes_pre` and `sizes_post` observe the identical `allocated_size()` on every batch and the delta is always zero. The capacity is charged exactly zero times, permanently, while `size()` is what the aggregate stream reports to the `MemoryPool`, so the pool under-counts and memory-pressure handling is delayed. The same asymmetry has a second effect at emit time: `evaluate` and `state` call `free_allocation(state.size())`, which releases capacity that was never charged, so `allocation_bytes` drifts down (and saturates at zero) across partial emits. Charge the growth explicitly. `indices_allocation_bytes` records the capacity already charged; each batch totals the current capacity in the pass that already visits every group and charges only the difference, so a group whose `indices` grew once and was then cleared stays charged without being charged again. Emitting a state drops its capacity from that total. The invariant is now that `allocation_bytes` equals the sum of `AccumulatorState::size()` plus the `states` vector allocation, which is what the added tests assert. No new per-row work: the push loop is untouched, and no `size()` call is added (`size()` was historically a bottleneck with many distinct groups, which is why deltas are used). The added cost is one `usize` addition per group per batch in an existing loop. Measured on a 16384-row batch across 1000 groups, with 8192 rows in group 0 and the rest spread evenly over the remaining 999, using a 16-byte accumulator: 168,096 bytes truly retained, 96,960 reported before, so 71,136 bytes (42%) went unaccounted. Query results are unchanged.
1 parent da89c7c commit 6b5b27b

1 file changed

Lines changed: 169 additions & 2 deletions

File tree

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

Lines changed: 169 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -102,6 +102,17 @@ pub struct GroupsAccumulatorAdapter {
102102
/// bottleneck in earlier implementations when there were many
103103
/// distinct groups.
104104
allocation_bytes: usize,
105+
106+
/// The portion of [`Self::allocation_bytes`] that is the scratch
107+
/// [`AccumulatorState::indices`] capacity held by [`Self::states`].
108+
///
109+
/// The scratch vectors are cleared, but not deallocated, at the end of every
110+
/// batch, so their capacity is retained for the lifetime of the group. The
111+
/// pre/post deltas taken around [`Accumulator`] work therefore see the same
112+
/// capacity on both sides and can never charge it. This field records what
113+
/// has already been charged so each batch charges only the growth since the
114+
/// previous one.
115+
indices_allocation_bytes: usize,
105116
}
106117

107118
struct AccumulatorState {
@@ -139,6 +150,7 @@ impl GroupsAccumulatorAdapter {
139150
factory: Box::new(factory),
140151
states: vec![],
141152
allocation_bytes: 0,
153+
indices_allocation_bytes: 0,
142154
}
143155
}
144156

@@ -221,8 +233,12 @@ impl GroupsAccumulatorAdapter {
221233
let mut offsets = vec![0];
222234

223235
let mut offset_so_far = 0;
236+
let mut indices_allocation_bytes = 0;
224237
for (group_index, state) in self.states.iter_mut().enumerate() {
225238
let indices = &state.indices;
239+
// this pass already visits every group, so totalling the scratch
240+
// capacity here costs a field read rather than a `size()` call
241+
indices_allocation_bytes += indices.allocated_size();
226242
if indices.is_empty() {
227243
continue;
228244
}
@@ -234,6 +250,13 @@ impl GroupsAccumulatorAdapter {
234250
}
235251
let batch_indices = batch_indices.into();
236252

253+
// The push loop above is the only place `indices` grows. Charge the
254+
// growth since the previous batch here: the pre/post deltas below
255+
// observe the identical capacity on both sides, because `f` does not
256+
// touch `indices` and the `clear()` after it retains the capacity.
257+
self.adjust_allocation(self.indices_allocation_bytes, indices_allocation_bytes);
258+
self.indices_allocation_bytes = indices_allocation_bytes;
259+
237260
// reorder the values and opt_filter by batch_indices so that
238261
// all values for each group are contiguous, then invoke the
239262
// accumulator once per group with values
@@ -284,6 +307,18 @@ impl GroupsAccumulatorAdapter {
284307
self.allocation_bytes = self.allocation_bytes.saturating_sub(size)
285308
}
286309

310+
/// Release the allocation held by a state that is being emitted.
311+
///
312+
/// [`AccumulatorState::size`] covers the scratch `indices` capacity, so
313+
/// this also drops it from [`Self::indices_allocation_bytes`] to keep that
314+
/// running total equal to the capacity still held by [`Self::states`].
315+
fn free_state_allocation(&mut self, state: &AccumulatorState) {
316+
self.free_allocation(state.size());
317+
self.indices_allocation_bytes = self
318+
.indices_allocation_bytes
319+
.saturating_sub(state.indices.allocated_size());
320+
}
321+
287322
/// Adjusts the allocation for something that started with
288323
/// start_size and now has new_size avoiding overflow
289324
///
@@ -325,7 +360,7 @@ impl GroupsAccumulator for GroupsAccumulatorAdapter {
325360
let results: Vec<ScalarValue> = states
326361
.into_iter()
327362
.map(|mut state| {
328-
self.free_allocation(state.size());
363+
self.free_state_allocation(&state);
329364
state.accumulator.evaluate()
330365
})
331366
.collect::<Result<_>>()?;
@@ -375,7 +410,7 @@ impl GroupsAccumulator for GroupsAccumulatorAdapter {
375410
let mut results: Vec<Vec<ScalarValue>> = vec![];
376411

377412
for mut state in states {
378-
self.free_allocation(state.size());
413+
self.free_state_allocation(&state);
379414
let accumulator_state = state.accumulator.state()?;
380415
results.resize_with(accumulator_state.len(), Vec::new);
381416
for (idx, state_val) in accumulator_state.into_iter().enumerate() {
@@ -576,4 +611,136 @@ mod tests {
576611
assert!(!accumulator.supports_state_preserving());
577612
Ok(())
578613
}
614+
615+
/// Accumulator whose `size()` is constant, so that the only thing that can
616+
/// move the adapter's reported size is the adapter's own bookkeeping.
617+
#[derive(Debug, Default)]
618+
struct CountingAccumulator {
619+
count: i64,
620+
}
621+
622+
impl Accumulator for CountingAccumulator {
623+
fn update_batch(&mut self, values: &[ArrayRef]) -> Result<()> {
624+
self.count += values[0].len() as i64;
625+
Ok(())
626+
}
627+
628+
fn evaluate(&mut self) -> Result<ScalarValue> {
629+
Ok(ScalarValue::Int64(Some(self.count)))
630+
}
631+
632+
fn size(&self) -> usize {
633+
size_of::<Self>()
634+
}
635+
636+
fn state(&mut self) -> Result<Vec<ScalarValue>> {
637+
Ok(vec![ScalarValue::Int64(Some(self.count))])
638+
}
639+
640+
fn merge_batch(&mut self, states: &[ArrayRef]) -> Result<()> {
641+
let counts = states[0].as_primitive::<Int64Type>();
642+
self.count += counts.iter().flatten().sum::<i64>();
643+
Ok(())
644+
}
645+
}
646+
647+
fn test_adapter() -> GroupsAccumulatorAdapter {
648+
GroupsAccumulatorAdapter::new(|| Ok(Box::new(CountingAccumulator::default())))
649+
}
650+
651+
/// The size the adapter should be reporting, computed directly from the
652+
/// states it is holding rather than from its running total.
653+
fn retained_size(adapter: &GroupsAccumulatorAdapter) -> usize {
654+
adapter
655+
.states
656+
.iter()
657+
.map(|state| state.size())
658+
.sum::<usize>()
659+
+ adapter.states.allocated_size()
660+
}
661+
662+
/// Builds a batch where group 0 takes `hot_rows` rows and group 1 takes one.
663+
fn skewed_batch(hot_rows: usize) -> (Vec<ArrayRef>, Vec<usize>) {
664+
let mut group_indices = vec![0; hot_rows];
665+
group_indices.push(1);
666+
let values: ArrayRef = Arc::new(Int64Array::from(vec![1; group_indices.len()]));
667+
(vec![values], group_indices)
668+
}
669+
670+
fn update(adapter: &mut GroupsAccumulatorAdapter, hot_rows: usize) {
671+
let (values, group_indices) = skewed_batch(hot_rows);
672+
adapter
673+
.update_batch(&values, &group_indices, None, 2)
674+
.unwrap();
675+
}
676+
677+
#[test]
678+
fn accounts_for_retained_indices_capacity() {
679+
const HOT_ROWS: usize = 8192;
680+
681+
let mut adapter = test_adapter();
682+
update(&mut adapter, HOT_ROWS);
683+
684+
// The scratch `indices` vector for group 0 grew to hold `HOT_ROWS`
685+
// `u32`s and keeps that capacity after `clear()`, so it has to show up
686+
// in the reported size.
687+
assert_eq!(adapter.size(), retained_size(&adapter));
688+
assert!(
689+
adapter.size() >= HOT_ROWS * size_of::<u32>(),
690+
"reported {} bytes, which cannot cover {} retained indices",
691+
adapter.size(),
692+
HOT_ROWS
693+
);
694+
695+
// A second batch of the same shape reuses the existing capacity, so the
696+
// reported size must not move: the capacity is charged once, not once
697+
// per batch.
698+
let after_first_batch = adapter.size();
699+
update(&mut adapter, HOT_ROWS);
700+
assert_eq!(adapter.size(), after_first_batch);
701+
assert_eq!(adapter.size(), retained_size(&adapter));
702+
703+
// Growing the hot group further charges only the additional capacity.
704+
update(&mut adapter, HOT_ROWS * 4);
705+
assert!(adapter.size() > after_first_batch);
706+
assert_eq!(adapter.size(), retained_size(&adapter));
707+
708+
// A smaller batch afterwards keeps the capacity, and keeps charging it.
709+
let after_growth = adapter.size();
710+
update(&mut adapter, 1);
711+
assert_eq!(adapter.size(), after_growth);
712+
assert_eq!(adapter.size(), retained_size(&adapter));
713+
}
714+
715+
#[test]
716+
fn releases_retained_indices_capacity_on_emit() {
717+
const HOT_ROWS: usize = 8192;
718+
719+
let mut adapter = test_adapter();
720+
update(&mut adapter, HOT_ROWS);
721+
722+
// Emitting the hot group must release its retained capacity, and must
723+
// not release capacity that belongs to the groups left behind.
724+
adapter.state(EmitTo::First(1)).unwrap();
725+
assert_eq!(adapter.size(), retained_size(&adapter));
726+
727+
update(&mut adapter, HOT_ROWS);
728+
assert_eq!(adapter.size(), retained_size(&adapter));
729+
730+
adapter.evaluate(EmitTo::All).unwrap();
731+
assert_eq!(adapter.size(), 0);
732+
assert_eq!(adapter.size(), retained_size(&adapter));
733+
}
734+
735+
#[test]
736+
fn merge_batch_accounts_for_retained_indices_capacity() {
737+
const HOT_ROWS: usize = 8192;
738+
739+
let mut adapter = test_adapter();
740+
let (values, group_indices) = skewed_batch(HOT_ROWS);
741+
adapter.merge_batch(&values, &group_indices, 2).unwrap();
742+
743+
assert_eq!(adapter.size(), retained_size(&adapter));
744+
assert!(adapter.size() >= HOT_ROWS * size_of::<u32>());
745+
}
579746
}

0 commit comments

Comments
 (0)