Skip to content

Commit 73768ee

Browse files
adriangbclaude
andauthored
perf: GroupsAccumulatorAdapter walks only the groups a batch has rows for (#25123)
## Which issue does this PR close? - Closes #25116. ## Rationale for this change Some aggregate functions do not have a `GroupsAccumulator`. The built-in examples are `covar_samp`, `covar_pop`, `regr_*`, `approx_percentile_cont`, `approx_median`, `nth_value` and `any_value`. `COUNT(DISTINCT)` on any non-integer type is another. A user-defined aggregate that has only an `Accumulator` is one too. For all of these, DataFusion uses `GroupsAccumulatorAdapter`. The adapter keeps one `Accumulator` for each group. It sends the rows of each input batch to the correct accumulators. If you group by a column that has many different values, these queries are slow. This query on the ClickBench `hits` data is an example: ```sql SELECT "UserID", covar_samp("ResolutionWidth", "ResolutionHeight") AS c FROM hits GROUP BY "UserID"; ``` The cause is the adapter. To put the rows of a batch in group order, it looks at every group that exists and skips the empty ones. It does this for each batch, whatever that batch touches. There are 17.6 million different `UserID` values, thus approximately 1.5 million groups in each of the 12 partitions. With 8192 rows in a batch, the adapter takes approximately 180 steps for each input row before it starts the aggregate work. ## What changes are included in this PR? ### 1. The adapter looks only at the groups that a batch has rows for The loop that puts each row index into its group already reaches every group that the batch has rows for. A group's scratch indexes are empty exactly when the batch has not reached that group yet, because the adapter empties them at the end of each batch. To record the group at that moment thus costs one comparison on a cache line that the loop already holds. The adapter then builds its `take` index from that list of groups. It no longer looks at the groups with no rows. The cost of a batch is now proportional to the rows in the batch and the groups that those rows are in. The rows of a group stay in the same order as in the input. Thus each `Accumulator` gets the same rows, in the same order, as before this change. The list of groups is in order of first appearance and not in order of group index. The code that reads the list does not depend on that order. The memory accounting for the scratch indexes does not change. `main` already charges the growth when a push grows a vector (#25051), and that is not a loop over every group. ### 2. Two new `clickbench_extended` queries Q15 groups `covar_samp` by `"UserID"` (17.6 million groups) and Q16 groups it by `"RegionID"` (9,040 groups). The aggregate is cheap, thus the adapter is the largest part of the time. An outer `MAX` keeps the result small. ## Benchmark results Every number below is from the bench bot on a 12 vCPU `c4a-highmem-16`. Alongside the runs of this PR are control runs that compare the base against itself, so the noise is measured and not assumed. **Each cell is `base -> this PR`, and the ratio is this PR divided by the base, thus 0.94x means this PR takes 94% of the time, which is 6% faster.** `clickbench_extended` against the merge base `0576a0b400`, three runs of each: | Query | control (base vs base) | this PR | | --- | --- | --- | | Q5 `APPROX_PERCENTILE_CONT` by `ClientIP, WatchID` | 10720 -> 11032 ms (1.03x)<br>10917 -> 11029 ms (1.01x)<br>11249 -> 10859 ms (0.97x) | 11133 -> 10429 ms (**0.94x**)<br>11312 -> 10507 ms (**0.93x**)<br>11146 -> 10510 ms (**0.94x**) | | Q9 `FIRST_VALUE(URL ORDER BY EventTime)` by `UserID` | 2854 -> 2735 ms (0.96x)<br>2912 -> 2894 ms (0.99x)<br>2966 -> 2944 ms (0.99x) | 2919 -> 3199 ms (1.10x)<br>2861 -> 3156 ms (1.10x)<br>2868 -> 3200 ms (1.12x) | | Suite total | 21616 -> 21763 ms (1.007x)<br>22092 -> 22216 ms (1.006x)<br>22785 -> 22555 ms (0.990x) | 22412 -> 21871 ms (0.976x)<br>22535 -> 22043 ms (0.978x)<br>22385 -> 22075 ms (0.986x) | Q5 is the query in the suite whose aggregate has no `GroupsAccumulator` and whose `GROUP BY` has many values. It takes about 700 ms less in every run, outside the band that the control gives. Q9 is slower in every run, but it does not run the code that this PR changes. `FIRST_VALUE` has a native `GroupsAccumulator` for `Utf8View`. To make sure, I added a print where the adapter is created and ran Q9 on the local ClickBench data. All 24 accumulators (12 partitions, partial and final) are native, and none of them is an adapter. A `covar_samp` query in the same run creates 24 adapters, which shows that the print works. The Q9 change thus comes from how the binary is built and laid out, not from the adapter. Q9 did not change in the runs before the rebase, which used the same adapter change. Q14 (`COUNT(DISTINCT str)` by `SearchPhrase`) was 0.83x to 0.88x before the rebase. It no longer changes, because #24859 now rewrites that query so that it does not use the adapter. On `main` it went from about 2700 ms to about 580 ms. Every other query in the suite stays inside the control band. `tpch_sf1` (0.993x), `tpcds_sf1` (0.994x), `external_aggr` (0.990x) and `clickbench_partitioned` (0.993x) show no change. The new Q15 and Q16 are not in these results. The bot compares against the merge base, which does not have them, so it drops them. @alamb measured Q15 locally in #25123 (review): five runs take 5.11 to 5.24 s on `main` and 4.10 to 4.80 s on this branch. <details><summary>Why this PR does not also drop the per-group index vectors</summary> The issue asks for two steps, and this PR is the first of them. The second step replaces the scratch `Vec<u32>` that each group holds with a counting sort over the batch. I built that and measured it on the same machine, against `40488988ad` before the rebase, in #25132 and in the earlier commits of this PR. It is faster than this PR where the groups are many. A microbenchmark of the adapter alone, with an accumulator that only counts its rows, at 1M groups measured 309.84 -> 241.45 ms (0.78x) for this PR and 309.84 -> 171.81 ms (0.55x) for the counting sort, and Q14 measured 0.84x, 0.84x and 0.83x for the counting sort against 0.88x, 0.88x and 0.83x for this PR. It is slower where the groups are few. Q2 groups by a column with 110 different values and has four `COUNT(DISTINCT)` aggregates, thus four adapters that each route every batch. Q2 measured 1.12x, 1.10x and 1.11x against a control of 1.00x, 1.00x and 0.99x. That is a 10% loss, and three runs and three controls say that it is not noise. To measure each half of the change on its own says why. At 64 groups, to stop looking at the idle groups gives 0.95x, and to then replace the per-group vectors with a counting sort gives 1.09x against that, because the second pass over the batch buys nothing when there are few groups. At 1M groups the same two changes give 0.78x and then a further 0.71x. The two halves thus pull in opposite directions at a low group count. This PR is the half that pulls the same way everywhere. The per-group vectors, and the memory that they hold, are left to a later change. </details> ## What is the testing strategy for this PR? The existing tests cover the change. To check that, I changed the code to record a group on every row instead of on the first one, so that a group gets its rows twice. The sqllogictest suite then fails 9 queries, for example `regr_count` and `approx_distinct` in `subquery.slt`. Thus this PR adds no new unit tests. The existing adapter unit tests, the `datafusion-functions-aggregate` tests, the sqllogictest suite and the two memory-limit tests from #24858 (`aggregate_adapter_spills_on_retained_indices` and `aggregate_adapter_charges_retained_indices_once`) pass. ## Are there any user-facing changes? Queries that group by a column with many different values, and that use an aggregate with no `GroupsAccumulator`, are faster. There are no changes to any public API and no changes to any result. 🤖 Generated with [Claude Code](https://claude.com/claude-code) --------- Co-authored-by: Claude Opus 5 <[email protected]>
1 parent d939014 commit 73768ee

4 files changed

Lines changed: 61 additions & 19 deletions

File tree

‎benchmarks/queries/clickbench/README.md‎

Lines changed: 28 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -260,7 +260,6 @@ FROM hits
260260
WHERE "URL" < 'zzzz';
261261
```
262262

263-
264263
### Q14: Grouped `COUNT(DISTINCT <string>)` beside a non-distinct `COUNT(*)`
265264

266265
**Question**: "For the top 10 search phrases by hit count, how many distinct
@@ -301,6 +300,34 @@ LIMIT 10;
301300

302301

303302

303+
### Q15: Correlation of ad slot dimensions per user
304+
305+
**Question**: "How correlated are the width and height of the screens each user browses from?"
306+
307+
**Important Query Properties**: `covar_samp` over a very high cardinality `GROUP BY` (about 17.6M distinct `UserID`s). Q16 is the low cardinality version of this query.
308+
309+
```sql
310+
SELECT MAX(c) FROM (
311+
SELECT covar_samp("ResolutionWidth", "ResolutionHeight") as c
312+
FROM hits
313+
GROUP BY "UserID"
314+
);
315+
```
316+
317+
### Q16: Correlation of ad slot dimensions per region
318+
319+
**Question**: "How correlated are the width and height of the screens browsed from in each region?"
320+
321+
**Important Query Properties**: the same `covar_samp` aggregate as Q15, but over about 9,000 distinct `RegionID`s instead of 17.6M. It is the low cardinality version of Q15.
322+
323+
```sql
324+
SELECT MAX(c) FROM (
325+
SELECT covar_samp("ResolutionWidth", "ResolutionHeight") as c
326+
FROM hits
327+
GROUP BY "RegionID"
328+
);
329+
```
330+
304331
## Data Notes
305332

306333
Here are some interesting statistics about the data used in the queries
Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
-- Must set for ClickBench hits_partitioned dataset. See https://github.com/apache/datafusion/issues/16591
2+
-- set datafusion.execution.parquet.binary_as_string = true
3+
4+
SELECT MAX(c) FROM (
5+
SELECT covar_samp("ResolutionWidth", "ResolutionHeight") as c
6+
FROM hits
7+
GROUP BY "UserID"
8+
);
Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
-- Must set for ClickBench hits_partitioned dataset. See https://github.com/apache/datafusion/issues/16591
2+
-- set datafusion.execution.parquet.binary_as_string = true
3+
4+
SELECT MAX(c) FROM (
5+
SELECT covar_samp("ResolutionWidth", "ResolutionHeight") as c
6+
FROM hits
7+
GROUP BY "RegionID"
8+
);

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

Lines changed: 17 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -235,14 +235,23 @@ impl GroupsAccumulatorAdapter {
235235

236236
assert_eq!(values[0].len(), group_indices.len());
237237

238+
// groups_with_rows holds a list of group indexes that have any rows
239+
// that need to be accumulated, stored in order of first appearance in
240+
// this batch
241+
let mut groups_with_rows = vec![];
242+
238243
// figure out which input rows correspond to which groups.
239-
// Note that self.state.indices starts empty for all groups
240-
// (it is cleared out below)
244+
// Note that self.state.indices starts empty for all groups (it is
245+
// cleared out below), so an empty one is exactly a group that this
246+
// batch has not reached yet.
241247
// Charge retained scratch capacity only when a push grows a vector,
242248
// avoiding another pass over every group after indexing.
243249
let mut indices_allocation_delta = 0;
244250
for (idx, group_index) in group_indices.iter().enumerate() {
245251
let indices = &mut self.states[*group_index].indices;
252+
if indices.is_empty() {
253+
groups_with_rows.push(*group_index);
254+
}
246255
if indices.len() < indices.capacity() {
247256
indices.push(idx as u32);
248257
} else {
@@ -253,27 +262,17 @@ impl GroupsAccumulatorAdapter {
253262
}
254263
self.add_allocation(indices_allocation_delta);
255264

256-
// groups_with_rows holds a list of group indexes that have
257-
// any rows that need to be accumulated, stored in order of
258-
// group_index
259-
260-
let mut groups_with_rows = vec![];
261-
262265
// batch_indices holds indices into values, each group is contiguous
263-
let mut batch_indices = vec![];
266+
let mut batch_indices = Vec::with_capacity(group_indices.len());
264267

265268
// offsets[i] is index into batch_indices where the rows for
266-
// group_index i starts
267-
let mut offsets = vec![0];
269+
// groups_with_rows[i] start
270+
let mut offsets = Vec::with_capacity(groups_with_rows.len() + 1);
271+
offsets.push(0);
268272

269273
let mut offset_so_far = 0;
270-
for (group_index, state) in self.states.iter_mut().enumerate() {
271-
let indices = &state.indices;
272-
if indices.is_empty() {
273-
continue;
274-
}
275-
276-
groups_with_rows.push(group_index);
274+
for &group_index in groups_with_rows.iter() {
275+
let indices = &self.states[group_index].indices;
277276
batch_indices.extend_from_slice(indices);
278277
offset_so_far += indices.len();
279278
offsets.push(offset_so_far);

0 commit comments

Comments
 (0)