Repository navigation
Commit 73768ee
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
- extended
- datafusion/functions-aggregate-common/src/aggregate
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
260 | 260 | | |
261 | 261 | | |
262 | 262 | | |
263 | | - | |
264 | 263 | | |
265 | 264 | | |
266 | 265 | | |
| |||
301 | 300 | | |
302 | 301 | | |
303 | 302 | | |
| 303 | + | |
| 304 | + | |
| 305 | + | |
| 306 | + | |
| 307 | + | |
| 308 | + | |
| 309 | + | |
| 310 | + | |
| 311 | + | |
| 312 | + | |
| 313 | + | |
| 314 | + | |
| 315 | + | |
| 316 | + | |
| 317 | + | |
| 318 | + | |
| 319 | + | |
| 320 | + | |
| 321 | + | |
| 322 | + | |
| 323 | + | |
| 324 | + | |
| 325 | + | |
| 326 | + | |
| 327 | + | |
| 328 | + | |
| 329 | + | |
| 330 | + | |
304 | 331 | | |
305 | 332 | | |
306 | 333 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
| 1 | + | |
| 2 | + | |
| 3 | + | |
| 4 | + | |
| 5 | + | |
| 6 | + | |
| 7 | + | |
| 8 | + | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
| 1 | + | |
| 2 | + | |
| 3 | + | |
| 4 | + | |
| 5 | + | |
| 6 | + | |
| 7 | + | |
| 8 | + | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
235 | 235 | | |
236 | 236 | | |
237 | 237 | | |
| 238 | + | |
| 239 | + | |
| 240 | + | |
| 241 | + | |
| 242 | + | |
238 | 243 | | |
239 | | - | |
240 | | - | |
| 244 | + | |
| 245 | + | |
| 246 | + | |
241 | 247 | | |
242 | 248 | | |
243 | 249 | | |
244 | 250 | | |
245 | 251 | | |
| 252 | + | |
| 253 | + | |
| 254 | + | |
246 | 255 | | |
247 | 256 | | |
248 | 257 | | |
| |||
253 | 262 | | |
254 | 263 | | |
255 | 264 | | |
256 | | - | |
257 | | - | |
258 | | - | |
259 | | - | |
260 | | - | |
261 | | - | |
262 | 265 | | |
263 | | - | |
| 266 | + | |
264 | 267 | | |
265 | 268 | | |
266 | | - | |
267 | | - | |
| 269 | + | |
| 270 | + | |
| 271 | + | |
268 | 272 | | |
269 | 273 | | |
270 | | - | |
271 | | - | |
272 | | - | |
273 | | - | |
274 | | - | |
275 | | - | |
276 | | - | |
| 274 | + | |
| 275 | + | |
277 | 276 | | |
278 | 277 | | |
279 | 278 | | |
| |||
0 commit comments