Repository navigation
perf: avoid quadratic planning for SELECTs with many aggregates - #25739
Merged
alamb merged 2 commits intoOct 1, 2026
Merged
Conversation
Building the projection above an aggregate rebuilt the lookup of the aggregate's output expressions for every select item. Build it once per projection and reuse it. Signed-off-by: Stefan Wang <[email protected]>
github-actions
Bot
added
logical-expr
Codecov Report❌ Patch coverage is
Additional details and impacted files@@ Coverage Diff @@
## main #25739 +/- ##
==========================================
- Coverage 82.60% 82.60% -0.01%
==========================================
Files 1144 1144
Lines 442904 442915 +11
Branches 442904 442915 +11
==========================================
+ Hits 365878 365884 +6
- Misses 54874 54876 +2
- Partials 22152 22155 +3 ☔ View full report in Codecov by Harness. 🚀 New features to boost your workflow:
|
Contributor
|
Thanks @1fanwang Can you please submit the benchmark as a separate PR so we can use our automated benchmark bot to compare them? |
Contributor
|
run benchmark sql_planner |
|
🤖 Benchmark running (GKE) | trigger CPU Details (lscpu)Comparing 1fanwang-datafusion-issue-prioritization (eb8f5ce) to 696eaf5 (merge-base) diff Run configurationrun benchmark sql_plannerResults will be posted here when complete File an issue against this benchmark runner |
|
🤖 Benchmark completed (GKE) | trigger Instance: Comparing 1fanwang-datafusion-issue-prioritization (eb8f5ce) to 696eaf5 (merge-base) diff Run configurationrun benchmark sql_plannerCPU Details (lscpu)Details
Resource Usagesql_planner — base (merge-base)
sql_planner — branch
File an issue against this benchmark runner |
Contributor
|
run benchmark sql_planner |
|
🤖 Benchmark running (GKE) | trigger CPU Details (lscpu)Comparing 1fanwang-datafusion-issue-prioritization (eb8f5ce) to 696eaf5 (merge-base) diff Run configurationrun benchmark sql_plannerResults will be posted here when complete File an issue against this benchmark runner |
|
🤖 Benchmark completed (GKE) | trigger Instance: Comparing 1fanwang-datafusion-issue-prioritization (eb8f5ce) to 696eaf5 (merge-base) diff Run configurationrun benchmark sql_plannerCPU Details (lscpu)Details
Resource Usagesql_planner — base (merge-base)
sql_planner — branch
File an issue against this benchmark runner |
Contributor
Looks good to me |
alamb
approved these changes
Sep 25, 2026
Contributor
|
Pushed main to unblock the CI |
Omega359
pushed a commit
to Omega359/arrow-datafusion
that referenced
this pull request
Oct 11, 2026
…he#25739) ## Which issue does this PR close? - Part of apache#25248. ## Rationale for this change Planning a `SELECT` with many aggregate expressions takes time that grows with the square of the number of expressions. The report measured 2.7 s of SQL planning for 2,500 items, and a profile shows almost all of it goes into building the projection above the aggregate. For each select item, the planner replaces sub-expressions that the aggregate already computes with references to its output columns. It rebuilt the lookup table of those expressions for every item, so N items built N tables of N entries. Hashing an aggregate expression also hashes its function signature, which makes each rebuild slow. ## What changes are included in this PR? - The projection builder now builds that table once and reuses it for every item, through a crate-private `Columnizer`. `columnize_expr` keeps its signature and uses the same helper. This follows apache#25010, which reuses the column normalization context in the same function. - The `sql_planner` benchmark gains a case with 1,000 aggregates. Very wide selects still do some quadratic work. Two SQL planner helpers, `rebase_expr` and `find_aggregate_exprs`, compare each expression against a list, and schema field lookups scan every field. I'd rather handle those in separate PRs, so this one only references the issue. ## What is the testing strategy for this PR? The rewrite gives the same result as before, so the existing expression, SQL planner and optimizer tests and the sqllogictest suite cover it, and they pass locally. `sql_planner` benchmark against `main` on an 18-core M-series Mac, `release-nonlto`: | Benchmark | main | this PR | change | | --- | --- | --- | --- | | `logical_wide_aggregate_1000_exprs` (new) | 182.3 ms | 31.1 ms | -83% | | `logical_wide_aggregate_100_exprs` | 2.43 ms | 0.89 ms | -63% | | `physical_select_aggregates_from_200` | 6.98 ms | 4.69 ms | -33% | The query shape from the issue, `CAST(sum(id + i) AS VARCHAR)` repeated N times, planned with `EXPLAIN` in `datafusion-cli` (unoptimized `ci` build, so absolute times are high): | N | main | this PR | | --- | --- | --- | | 500 | 0.72 s | 0.66 s | | 1000 | 1.56 s | 0.87 s | | 2000 | 5.05 s | 1.83 s | | 4000 | 18.83 s | 4.57 s | <details> <summary>Commands and raw output</summary> Benchmarks. The new case is copied onto `main` so both runs measure the same queries. The `sql_planner` bench checks that `benchmarks/data/hits_partitioned` exists at startup; I used a one-row stand-in, since none of these three cases read it. ``` PR=eb8f5ce9d4d0b50cffb97648188c84a4034ec92c git fetch origin main "$PR" git switch --detach origin/main git checkout "$PR" -- datafusion/core/benches/sql_planner.rs cargo bench -p datafusion --bench sql_planner --profile release-nonlto -- \ 'logical_wide_aggregate|physical_select_aggregates_from_200' --save-baseline main git checkout -f "$PR" cargo bench -p datafusion --bench sql_planner --profile release-nonlto -- \ 'logical_wide_aggregate|physical_select_aggregates_from_200' --baseline main ``` `main`: ``` physical_select_aggregates_from_200 time: [6.8908 ms 6.9799 ms 7.0789 ms] logical_wide_aggregate_100_exprs time: [2.3629 ms 2.4285 ms 2.4977 ms] logical_wide_aggregate_1000_exprs time: [180.60 ms 182.29 ms 184.28 ms] ``` This PR: ``` physical_select_aggregates_from_200 time: [4.6522 ms 4.6890 ms 4.7269 ms] change: [−33.854% −32.821% −31.767%] (p = 0.00 < 0.05) Performance has improved. logical_wide_aggregate_100_exprs time: [881.22 µs 888.79 µs 897.96 µs] change: [−63.824% −62.709% −61.533%] (p = 0.00 < 0.05) Performance has improved. logical_wide_aggregate_1000_exprs time: [30.705 ms 31.131 ms 31.628 ms] change: [−83.222% −82.922% −82.577%] (p = 0.00 < 0.05) Performance has improved. ``` `datafusion-cli` timing, with the CLI built by `cargo build --profile ci -p datafusion-cli` on each side: ```bash #!/usr/bin/env bash # Usage: wide-timing.sh <datafusion-cli> set -euo pipefail python3 - <<'EOF' for n in (500, 1000, 2000, 4000): items = ', '.join(f'CAST(sum(id + {i}) AS VARCHAR) AS c{i}' for i in range(n)) with open(f'wide_{n}.sql', 'w') as f: f.write('CREATE TABLE t AS SELECT value AS id FROM range(1000);\n') f.write(f'EXPLAIN SELECT {items} FROM t;\n') EOF for n in 500 1000 2000 4000; do /usr/bin/time -p "$1" -q -f "wide_$n.sql" 2>&1 >/dev/null | awk -v n="$n" '/^real/ {print "N=" n, $2 "s"}' done ``` ``` == main N=500 0.72s N=1000 1.56s N=2000 5.05s N=4000 18.83s == this PR N=500 0.66s N=1000 0.87s N=2000 1.83s N=4000 4.57s ``` </details> ## Are there any user-facing changes? No. Planning is faster, and `columnize_expr` keeps its signature and behavior. Signed-off-by: Stefan Wang <[email protected]> Co-authored-by: Kumar Ujjawal <[email protected]>
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Which issue does this PR close?
SqlToRel::statement_to_planis superlinear for a wideAggregate(exponent ≈ 1.8, DataFusion 54.1.0) #25248.Rationale for this change
Planning a
SELECTwith many aggregate expressions takes time that grows with the square of the number of expressions. The report measured 2.7 s of SQL planning for 2,500 items, and a profile shows almost all of it goes into building the projection above the aggregate.For each select item, the planner replaces sub-expressions that the aggregate already computes with references to its output columns. It rebuilt the lookup table of those expressions for every item, so N items built N tables of N entries. Hashing an aggregate expression also hashes its function signature, which makes each rebuild slow.
What changes are included in this PR?
Columnizer.columnize_exprkeeps its signature and uses the same helper. This follows perf: reuse column normalization context across expressions #25010, which reuses the column normalization context in the same function.sql_plannerbenchmark gains a case with 1,000 aggregates.Very wide selects still do some quadratic work. Two SQL planner helpers,
rebase_exprandfind_aggregate_exprs, compare each expression against a list, and schema field lookups scan every field. I'd rather handle those in separate PRs, so this one only references the issue.What is the testing strategy for this PR?
The rewrite gives the same result as before, so the existing expression, SQL planner and optimizer tests and the sqllogictest suite cover it, and they pass locally.
sql_plannerbenchmark againstmainon an 18-core M-series Mac,release-nonlto:logical_wide_aggregate_1000_exprs(new)logical_wide_aggregate_100_exprsphysical_select_aggregates_from_200The query shape from the issue,
CAST(sum(id + i) AS VARCHAR)repeated N times, planned withEXPLAINindatafusion-cli(unoptimizedcibuild, so absolute times are high):Commands and raw output
Benchmarks. The new case is copied onto
mainso both runs measure the same queries. Thesql_plannerbench checks thatbenchmarks/data/hits_partitionedexists at startup; I used a one-row stand-in, since none of these three cases read it.main:This PR:
datafusion-clitiming, with the CLI built bycargo build --profile ci -p datafusion-clion each side:Are there any user-facing changes?
No. Planning is faster, and
columnize_exprkeeps its signature and behavior.