You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datafusion.apache.org by gi...@apache.org on 2026/09/23 18:17:12 UTC

(datafusion) branch gh-readonly-queue/main/pr-25123-d939014973cd58f190d216e629bec3021066ad3f created (now 73768ee34c)

This is an automated email from the ASF dual-hosted git repository.

github-merge-queue[bot] pushed a change to branch gh-readonly-queue/main/pr-25123-d939014973cd58f190d216e629bec3021066ad3f
in repository https://gitbox.apache.org/repos/asf/datafusion.git


      at 73768ee34c perf: GroupsAccumulatorAdapter walks only the groups a batch has rows for (#25123)

This branch includes the following new commits:

     new 73768ee34c perf: GroupsAccumulatorAdapter walks only the groups a batch has rows for (#25123)

The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails.  The revisions
listed as "add" were already present in the repository and have only
been added to this reference.



---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org


(datafusion) 01/01: perf: GroupsAccumulatorAdapter walks only the groups a batch has rows for (#25123)

Posted by gi...@apache.org.
This is an automated email from the ASF dual-hosted git repository.

github-merge-queue[bot] pushed a commit to branch gh-readonly-queue/main/pr-25123-d939014973cd58f190d216e629bec3021066ad3f
in repository https://gitbox.apache.org/repos/asf/datafusion.git

commit 73768ee34c1747c2a13a93ee822e35d5b795390f
Author: Adrian Garcia Badaracco <17...@users.noreply.github.com>
AuthorDate: Wed Sep 23 18:16:49 2026 +0000

    perf: GroupsAccumulatorAdapter walks only the groups a batch has rows for (#25123)
    
    ## Which issue does this PR close?
    
    - Closes https://github.com/apache/datafusion/issues/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
    (https://github.com/apache/datafusion/pull/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
    https://github.com/apache/datafusion/pull/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
    https://github.com/apache/datafusion/pull/25123#pullrequestreview-5271822034:
    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
    https://github.com/apache/datafusion/pull/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
    https://github.com/apache/datafusion/pull/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 <no...@anthropic.com>
---
 benchmarks/queries/clickbench/README.md            | 29 +++++++++++++++++-
 benchmarks/queries/clickbench/extended/q15.sql     |  8 +++++
 benchmarks/queries/clickbench/extended/q16.sql     |  8 +++++
 .../src/aggregate/groups_accumulator.rs            | 35 +++++++++++-----------
 4 files changed, 61 insertions(+), 19 deletions(-)

diff --git a/benchmarks/queries/clickbench/README.md b/benchmarks/queries/clickbench/README.md
index 2fd31c0b4c..c0ee7bc327 100644
--- a/benchmarks/queries/clickbench/README.md
+++ b/benchmarks/queries/clickbench/README.md
@@ -260,7 +260,6 @@ FROM hits
 WHERE "URL" < 'zzzz';
 ```
 
-
 ### Q14: Grouped `COUNT(DISTINCT <string>)` beside a non-distinct `COUNT(*)`
 
 **Question**: "For the top 10 search phrases by hit count, how many distinct
@@ -301,6 +300,34 @@ LIMIT 10;
 
 
 
+### Q15: Correlation of ad slot dimensions per user
+
+**Question**: "How correlated are the width and height of the screens each user browses from?"
+
+**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.
+
+```sql
+SELECT MAX(c) FROM (
+    SELECT covar_samp("ResolutionWidth", "ResolutionHeight") as c
+    FROM hits
+    GROUP BY "UserID"
+);
+```
+
+### Q16: Correlation of ad slot dimensions per region
+
+**Question**: "How correlated are the width and height of the screens browsed from in each region?"
+
+**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.
+
+```sql
+SELECT MAX(c) FROM (
+    SELECT covar_samp("ResolutionWidth", "ResolutionHeight") as c
+    FROM hits
+    GROUP BY "RegionID"
+);
+```
+
 ## Data Notes
 
 Here are some interesting statistics about the data used in the queries
diff --git a/benchmarks/queries/clickbench/extended/q15.sql b/benchmarks/queries/clickbench/extended/q15.sql
new file mode 100644
index 0000000000..e648b8dd97
--- /dev/null
+++ b/benchmarks/queries/clickbench/extended/q15.sql
@@ -0,0 +1,8 @@
+-- Must set for ClickBench hits_partitioned dataset. See https://github.com/apache/datafusion/issues/16591
+-- set datafusion.execution.parquet.binary_as_string = true
+
+SELECT MAX(c) FROM (
+    SELECT covar_samp("ResolutionWidth", "ResolutionHeight") as c
+    FROM hits
+    GROUP BY "UserID"
+);
diff --git a/benchmarks/queries/clickbench/extended/q16.sql b/benchmarks/queries/clickbench/extended/q16.sql
new file mode 100644
index 0000000000..f3db0ae2df
--- /dev/null
+++ b/benchmarks/queries/clickbench/extended/q16.sql
@@ -0,0 +1,8 @@
+-- Must set for ClickBench hits_partitioned dataset. See https://github.com/apache/datafusion/issues/16591
+-- set datafusion.execution.parquet.binary_as_string = true
+
+SELECT MAX(c) FROM (
+    SELECT covar_samp("ResolutionWidth", "ResolutionHeight") as c
+    FROM hits
+    GROUP BY "RegionID"
+);
diff --git a/datafusion/functions-aggregate-common/src/aggregate/groups_accumulator.rs b/datafusion/functions-aggregate-common/src/aggregate/groups_accumulator.rs
index 41917329b2..d49cae6a16 100644
--- a/datafusion/functions-aggregate-common/src/aggregate/groups_accumulator.rs
+++ b/datafusion/functions-aggregate-common/src/aggregate/groups_accumulator.rs
@@ -235,14 +235,23 @@ impl GroupsAccumulatorAdapter {
 
         assert_eq!(values[0].len(), group_indices.len());
 
+        // groups_with_rows holds a list of group indexes that have any rows
+        // that need to be accumulated, stored in order of first appearance in
+        // this batch
+        let mut groups_with_rows = vec![];
+
         // figure out which input rows correspond to which groups.
-        // Note that self.state.indices starts empty for all groups
-        // (it is cleared out below)
+        // Note that self.state.indices starts empty for all groups (it is
+        // cleared out below), so an empty one is exactly a group that this
+        // batch has not reached yet.
         // Charge retained scratch capacity only when a push grows a vector,
         // avoiding another pass over every group after indexing.
         let mut indices_allocation_delta = 0;
         for (idx, group_index) in group_indices.iter().enumerate() {
             let indices = &mut self.states[*group_index].indices;
+            if indices.is_empty() {
+                groups_with_rows.push(*group_index);
+            }
             if indices.len() < indices.capacity() {
                 indices.push(idx as u32);
             } else {
@@ -253,27 +262,17 @@ impl GroupsAccumulatorAdapter {
         }
         self.add_allocation(indices_allocation_delta);
 
-        // groups_with_rows holds a list of group indexes that have
-        // any rows that need to be accumulated, stored in order of
-        // group_index
-
-        let mut groups_with_rows = vec![];
-
         // batch_indices holds indices into values, each group is contiguous
-        let mut batch_indices = vec![];
+        let mut batch_indices = Vec::with_capacity(group_indices.len());
 
         // offsets[i] is index into batch_indices where the rows for
-        // group_index i starts
-        let mut offsets = vec![0];
+        // groups_with_rows[i] start
+        let mut offsets = Vec::with_capacity(groups_with_rows.len() + 1);
+        offsets.push(0);
 
         let mut offset_so_far = 0;
-        for (group_index, state) in self.states.iter_mut().enumerate() {
-            let indices = &state.indices;
-            if indices.is_empty() {
-                continue;
-            }
-
-            groups_with_rows.push(group_index);
+        for &group_index in groups_with_rows.iter() {
+            let indices = &self.states[group_index].indices;
             batch_indices.extend_from_slice(indices);
             offset_so_far += indices.len();
             offsets.push(offset_so_far);


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org