apache / apache/datafusion

Expose to `GroupsAccumulator` whether all the groups are sorted

Open
#14,991 17 comments 0 reactions 0 assignees View on GitHub
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.