Skip to content

Commit 8ae66e4

Browse files
1fanwangkumarUjjawal
authored andcommitted
perf: avoid quadratic planning for SELECTs with many aggregates (apache#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]>
1 parent af43b1c commit 8ae66e4

3 files changed

Lines changed: 47 additions & 18 deletions

File tree

‎datafusion/core/benches/sql_planner.rs‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -829,6 +829,14 @@ fn criterion_benchmark(c: &mut Criterion) {
829829
});
830830
}
831831

832+
{
833+
let aggs: Vec<String> = (0..1000).map(|i| format!("SUM(d{i})")).collect();
834+
let query = format!("SELECT {} FROM t1000", aggs.join(", "));
835+
c.bench_function("logical_wide_aggregate_1000_exprs", |b| {
836+
b.iter(|| logical_plan(&ctx, &rt, &query))
837+
});
838+
}
839+
832840
// Many CASE WHEN expressions (complex expressions)
833841
{
834842
let cases: Vec<String> = (0..50)

‎datafusion/expr/src/logical_plan/builder.rs‎

Lines changed: 7 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -38,7 +38,7 @@ use crate::logical_plan::{
3838
};
3939
use crate::select_expr::SelectExpr;
4040
use crate::utils::{
41-
can_hash, check_all_columns_from_schema, columnize_expr, compare_sort_expr,
41+
Columnizer, can_hash, check_all_columns_from_schema, compare_sort_expr,
4242
expand_qualified_wildcard, expand_wildcard, expr_to_columns,
4343
find_valid_equijoin_key_pair, group_window_expr_by_sort_keys,
4444
split_conjunction_owned,
@@ -2082,6 +2082,7 @@ fn project_with_validation(
20822082
let mut projected_expr = vec![];
20832083
let mut has_wildcard = false;
20842084
let mut normalizer = ColumnNormalizer::new(&plan);
2085+
let columnizer = Columnizer::new(&plan);
20852086
for (e, validate) in expr {
20862087
let e = e.into();
20872088
match e {
@@ -2100,7 +2101,7 @@ fn project_with_validation(
21002101
for e in expanded {
21012102
if validate {
21022103
projected_expr
2103-
.push(columnize_expr(normalizer.normalize(e)?, &plan)?)
2104+
.push(columnizer.columnize(normalizer.normalize(e)?)?)
21042105
} else {
21052106
projected_expr.push(e)
21062107
}
@@ -2122,15 +2123,15 @@ fn project_with_validation(
21222123
for e in expanded {
21232124
if validate {
21242125
projected_expr
2125-
.push(columnize_expr(normalizer.normalize(e)?, &plan)?)
2126+
.push(columnizer.columnize(normalizer.normalize(e)?)?)
21262127
} else {
21272128
projected_expr.push(e)
21282129
}
21292130
}
21302131
}
21312132
SelectExpr::Expression(e) => {
21322133
if validate {
2133-
projected_expr.push(columnize_expr(normalizer.normalize(e)?, &plan)?)
2134+
projected_expr.push(columnizer.columnize(normalizer.normalize(e)?)?)
21342135
} else {
21352136
projected_expr.push(e)
21362137
}
@@ -2157,6 +2158,8 @@ fn project_with_validation(
21572158

21582159
validate_unique_names("Projections", projected_expr.iter())?;
21592160

2161+
// `columnizer` borrows `plan`, which moves into the projection below.
2162+
drop(columnizer);
21602163
Projection::try_new(projected_expr, Arc::new(plan)).map(LogicalPlan::Projection)
21612164
}
21622165

‎datafusion/expr/src/utils.rs‎

Lines changed: 32 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -963,20 +963,38 @@ pub fn exprlist_to_fields<'a>(
963963
/// .project(vec![col("c1"), col("SUM(c2)")?
964964
/// ```
965965
pub fn columnize_expr(e: Expr, input: &LogicalPlan) -> Result<Expr> {
966-
let output_exprs = match input.columnized_output_exprs() {
967-
Ok(exprs) if !exprs.is_empty() => exprs,
968-
_ => return Ok(e),
969-
};
970-
let exprs_map: HashMap<&Expr, Column> = output_exprs.into_iter().collect();
971-
e.transform_down(|node: Expr| match exprs_map.get(&node) {
972-
Some(column) => Ok(Transformed::new(
973-
Expr::Column(column.clone()),
974-
true,
975-
TreeNodeRecursion::Jump,
976-
)),
977-
None => Ok(Transformed::no(node)),
978-
})
979-
.data()
966+
Columnizer::new(input).columnize(e)
967+
}
968+
969+
/// Applies [`columnize_expr`] to many expressions over the same input plan,
970+
/// building the lookup of the input's output expressions only once.
971+
pub(crate) struct Columnizer<'a> {
972+
output_exprs: HashMap<&'a Expr, Column>,
973+
}
974+
975+
impl<'a> Columnizer<'a> {
976+
pub(crate) fn new(input: &'a LogicalPlan) -> Self {
977+
let output_exprs = input
978+
.columnized_output_exprs()
979+
.map(|exprs| exprs.into_iter().collect())
980+
.unwrap_or_default();
981+
Self { output_exprs }
982+
}
983+
984+
pub(crate) fn columnize(&self, e: Expr) -> Result<Expr> {
985+
if self.output_exprs.is_empty() {
986+
return Ok(e);
987+
}
988+
e.transform_down(|node: Expr| match self.output_exprs.get(&node) {
989+
Some(column) => Ok(Transformed::new(
990+
Expr::Column(column.clone()),
991+
true,
992+
TreeNodeRecursion::Jump,
993+
)),
994+
None => Ok(Transformed::no(node)),
995+
})
996+
.data()
997+
}
980998
}
981999

9821000
/// Collect all deeply nested `Expr::Column`'s. They are returned in order of

0 commit comments

Comments
 (0)