Skip to content

Commit 3e27f79

Browse files
adriangbclaude
andcommitted
perf: walk only the groups a batch has rows for
Option 1 of #25116: record each group the first time the push loop reaches it, then build the `take` index from that list instead of from a scan over every group that exists. The scratch `Vec<u32>` per group stays. This is the counterfactual for PR #25123, which additionally replaces those per-group vectors with a counting sort. Benchmark only. Co-Authored-By: Claude Opus 5 <[email protected]>
1 parent 4048898 commit 3e27f79

1 file changed

Lines changed: 19 additions & 19 deletions

File tree

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

Lines changed: 19 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -200,34 +200,34 @@ impl GroupsAccumulatorAdapter {
200200

201201
assert_eq!(values[0].len(), group_indices.len());
202202

203+
// groups_with_rows holds a list of group indexes that have any rows
204+
// that need to be accumulated, stored in order of first appearance in
205+
// this batch
206+
let mut groups_with_rows = vec![];
207+
203208
// figure out which input rows correspond to which groups.
204-
// Note that self.state.indices starts empty for all groups
205-
// (it is cleared out below)
209+
// Note that self.state.indices starts empty for all groups (it is
210+
// cleared out below), so an empty one is exactly a group that this
211+
// batch has not reached yet
206212
for (idx, group_index) in group_indices.iter().enumerate() {
207-
self.states[*group_index].indices.push(idx as u32);
213+
let state = &mut self.states[*group_index];
214+
if state.indices.is_empty() {
215+
groups_with_rows.push(*group_index);
216+
}
217+
state.indices.push(idx as u32);
208218
}
209219

210-
// groups_with_rows holds a list of group indexes that have
211-
// any rows that need to be accumulated, stored in order of
212-
// group_index
213-
214-
let mut groups_with_rows = vec![];
215-
216220
// batch_indices holds indices into values, each group is contiguous
217-
let mut batch_indices = vec![];
221+
let mut batch_indices = Vec::with_capacity(group_indices.len());
218222

219223
// offsets[i] is index into batch_indices where the rows for
220-
// group_index i starts
221-
let mut offsets = vec![0];
224+
// groups_with_rows[i] start
225+
let mut offsets = Vec::with_capacity(groups_with_rows.len() + 1);
226+
offsets.push(0);
222227

223228
let mut offset_so_far = 0;
224-
for (group_index, state) in self.states.iter_mut().enumerate() {
225-
let indices = &state.indices;
226-
if indices.is_empty() {
227-
continue;
228-
}
229-
230-
groups_with_rows.push(group_index);
229+
for &group_index in groups_with_rows.iter() {
230+
let indices = &self.states[group_index].indices;
231231
batch_indices.extend_from_slice(indices);
232232
offset_so_far += indices.len();
233233
offsets.push(offset_so_far);

0 commit comments

Comments
 (0)