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/10/01 16:21:19 UTC
(datafusion) branch gh-readonly-queue/main/pr-25739-2b1fcae86640898274eecffb054683d093c1bdb8 created (now c222b69bd0)
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-25739-2b1fcae86640898274eecffb054683d093c1bdb8
in repository https://gitbox.apache.org/repos/asf/datafusion.git
at c222b69bd0 perf: avoid quadratic planning for SELECTs with many aggregates (#25739)
This branch includes the following new commits:
new c222b69bd0 perf: avoid quadratic planning for SELECTs with many aggregates (#25739)
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: avoid quadratic planning for SELECTs with many aggregates (#25739)
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-25739-2b1fcae86640898274eecffb054683d093c1bdb8
in repository https://gitbox.apache.org/repos/asf/datafusion.git
commit c222b69bd0030c51451c016fb1749d7c7a7054c2
Author: Stefan Wang <1f...@gmail.com>
AuthorDate: Thu Oct 1 16:20:54 2026 +0000
perf: avoid quadratic planning for SELECTs with many aggregates (#25739)
## Which issue does this PR close?
- Part of #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 #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 <1f...@gmail.com>
Co-authored-by: Kumar Ujjawal <uj...@gmail.com>
---
datafusion/core/benches/sql_planner.rs | 8 +++++
datafusion/expr/src/logical_plan/builder.rs | 11 ++++---
datafusion/expr/src/utils.rs | 46 ++++++++++++++++++++---------
3 files changed, 47 insertions(+), 18 deletions(-)
diff --git a/datafusion/core/benches/sql_planner.rs b/datafusion/core/benches/sql_planner.rs
index 48770541ca..5e5a63c0e9 100644
--- a/datafusion/core/benches/sql_planner.rs
+++ b/datafusion/core/benches/sql_planner.rs
@@ -829,6 +829,14 @@ fn criterion_benchmark(c: &mut Criterion) {
});
}
+ {
+ let aggs: Vec<String> = (0..1000).map(|i| format!("SUM(d{i})")).collect();
+ let query = format!("SELECT {} FROM t1000", aggs.join(", "));
+ c.bench_function("logical_wide_aggregate_1000_exprs", |b| {
+ b.iter(|| logical_plan(&ctx, &rt, &query))
+ });
+ }
+
// Many CASE WHEN expressions (complex expressions)
{
let cases: Vec<String> = (0..50)
diff --git a/datafusion/expr/src/logical_plan/builder.rs b/datafusion/expr/src/logical_plan/builder.rs
index 964c6de396..64fc9b81ee 100644
--- a/datafusion/expr/src/logical_plan/builder.rs
+++ b/datafusion/expr/src/logical_plan/builder.rs
@@ -38,7 +38,7 @@ use crate::logical_plan::{
};
use crate::select_expr::SelectExpr;
use crate::utils::{
- can_hash, check_all_columns_from_schema, columnize_expr, compare_sort_expr,
+ Columnizer, can_hash, check_all_columns_from_schema, compare_sort_expr,
expand_qualified_wildcard, expand_wildcard, expr_to_columns,
find_valid_equijoin_key_pair, group_window_expr_by_sort_keys,
split_conjunction_owned,
@@ -2082,6 +2082,7 @@ fn project_with_validation(
let mut projected_expr = vec![];
let mut has_wildcard = false;
let mut normalizer = ColumnNormalizer::new(&plan);
+ let columnizer = Columnizer::new(&plan);
for (e, validate) in expr {
let e = e.into();
match e {
@@ -2100,7 +2101,7 @@ fn project_with_validation(
for e in expanded {
if validate {
projected_expr
- .push(columnize_expr(normalizer.normalize(e)?, &plan)?)
+ .push(columnizer.columnize(normalizer.normalize(e)?)?)
} else {
projected_expr.push(e)
}
@@ -2122,7 +2123,7 @@ fn project_with_validation(
for e in expanded {
if validate {
projected_expr
- .push(columnize_expr(normalizer.normalize(e)?, &plan)?)
+ .push(columnizer.columnize(normalizer.normalize(e)?)?)
} else {
projected_expr.push(e)
}
@@ -2130,7 +2131,7 @@ fn project_with_validation(
}
SelectExpr::Expression(e) => {
if validate {
- projected_expr.push(columnize_expr(normalizer.normalize(e)?, &plan)?)
+ projected_expr.push(columnizer.columnize(normalizer.normalize(e)?)?)
} else {
projected_expr.push(e)
}
@@ -2157,6 +2158,8 @@ fn project_with_validation(
validate_unique_names("Projections", projected_expr.iter())?;
+ // `columnizer` borrows `plan`, which moves into the projection below.
+ drop(columnizer);
Projection::try_new(projected_expr, Arc::new(plan)).map(LogicalPlan::Projection)
}
diff --git a/datafusion/expr/src/utils.rs b/datafusion/expr/src/utils.rs
index 07af8b1f56..238025b00a 100644
--- a/datafusion/expr/src/utils.rs
+++ b/datafusion/expr/src/utils.rs
@@ -963,20 +963,38 @@ pub fn exprlist_to_fields<'a>(
/// .project(vec![col("c1"), col("SUM(c2)")?
/// ```
pub fn columnize_expr(e: Expr, input: &LogicalPlan) -> Result<Expr> {
- let output_exprs = match input.columnized_output_exprs() {
- Ok(exprs) if !exprs.is_empty() => exprs,
- _ => return Ok(e),
- };
- let exprs_map: HashMap<&Expr, Column> = output_exprs.into_iter().collect();
- e.transform_down(|node: Expr| match exprs_map.get(&node) {
- Some(column) => Ok(Transformed::new(
- Expr::Column(column.clone()),
- true,
- TreeNodeRecursion::Jump,
- )),
- None => Ok(Transformed::no(node)),
- })
- .data()
+ Columnizer::new(input).columnize(e)
+}
+
+/// Applies [`columnize_expr`] to many expressions over the same input plan,
+/// building the lookup of the input's output expressions only once.
+pub(crate) struct Columnizer<'a> {
+ output_exprs: HashMap<&'a Expr, Column>,
+}
+
+impl<'a> Columnizer<'a> {
+ pub(crate) fn new(input: &'a LogicalPlan) -> Self {
+ let output_exprs = input
+ .columnized_output_exprs()
+ .map(|exprs| exprs.into_iter().collect())
+ .unwrap_or_default();
+ Self { output_exprs }
+ }
+
+ pub(crate) fn columnize(&self, e: Expr) -> Result<Expr> {
+ if self.output_exprs.is_empty() {
+ return Ok(e);
+ }
+ e.transform_down(|node: Expr| match self.output_exprs.get(&node) {
+ Some(column) => Ok(Transformed::new(
+ Expr::Column(column.clone()),
+ true,
+ TreeNodeRecursion::Jump,
+ )),
+ None => Ok(Transformed::no(node)),
+ })
+ .data()
+ }
}
/// Collect all deeply nested `Expr::Column`'s. They are returned in order of
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org