Expose to `GroupsAccumulator` whether all the groups are sorted
- Dominant language
- Rust
- Stars
- 9.3k
- Forks
- 2.4k
- Avg merge
- 3d 7h
- Merged PRs (30d)
- 344
Description
Let's take for example the following plan:
```
Project
Aggregate
Sort
Project
Scan
```
and the sort is on the aggregate expressions.
this means that we will get the `group_indices` in the `GroupsAccumulator` similar to this (right?)
```rust
// Call 1 to update_batch/merge_batch
group_indices: [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3]
// Call 2 to update_batch/merge_batch
group_indices: [3, 3, 4, 4, 4, 4]
```
and once we got group index 2 we know for sure we will never see group index 1 again (until it is collected in by `state`/`evaluate`).
Knowing this a lot of optimizations can be done
For example we can avoid the reordering here:
https://github.com/apache/datafusion/blob/2fcab2ef0da474ec000d7410427b9d18afb5820b/datafusion/functions-aggregate-common/src/aggregate/groups_accumulator.rs#L238-L241
or get each group by slicing from the first index saw the group to the last index
And custom implementations of `GroupsAccumulator` could take advantage of that by keeping all the group outputs in a single builder allowing for fast building the output for `state`/`evaluate`
Also it looks like we already have this information in the `AggregateExec` https://github.com/apache/datafusion/blob/2fcab2ef0da474ec000d7410427b9d18afb5820b/datafusion/physical-plan/src/aggregates/mod.rs#L393-L394
Contributor guide
Research direction
Start by reading datafusion/functions-aggregate-common/src/aggregate/groups_accumulator.rs around the linked reordering code, then inspect datafusion/physical-plan/src/aggregates/mod.rs around AggregateExec's existing sorted-group information. Trace how that information reaches GroupsAccumulator update_batch/merge_batch; done means exposing the all-groups-sorted property and using it for the described ordering or slicing optimization, with focused tests for sorted batches across calls.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- backend
- Issue type
- Feature
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100