`SqlToRel::statement_to_plan` is superlinear for a wide `Aggregate` (exponent ≈ 1.8, DataFusion 54.1.0)
- Dominant language
- Rust
- Stars
- 9.3k
- Forks
- 2.4k
- Avg merge
- 3d 7h
- Merged PRs (30d)
- 344
Description
Planning `SELECT CAST(sum(id + i) AS VARCHAR) AS ci …` with N slots over a
200 k-row, one-column `Int64` MemTable is superlinear in N on a release
build of DataFusion 54.1.0, on a stock `SessionContext` with no extensions:
| N | parse (s) | `statement_to_plan` (s) | analyzer (s) | optimizer (s) | `ctx.sql` (s) |
|---:|---:|---:|---:|---:|---:|
| 50 | 0.0004 | 0.0024 | 0.0007 | 0.0049 | 0.0027 |
| 250 | 0.0015 | 0.0307 | 0.0039 | 0.0235 | 0.0323 |
| 2500 | 0.0171 | 2.7434 | 0.0901 | 0.2522 | 2.7545 |
`statement_to_plan` alone is 96 % of `sql()` at N = 2500 and fits
`time ∝ N^1.81` over the three sizes (per-rule timing shows every analyzer
and optimizer rule near-linear). Three discriminators:
- The same N-expression aggregate built through
`DataFrame::aggregate(Vec::new(), exprs)` — no SQL — takes **0.012 s** at
N = 2500, so the logical `Aggregate` node itself is cheap.
- A bare `sum(id + i)` aggregate **without** any CAST shows the same
superlinear `statement_to_plan` (2.69 s at 2500), so CAST is not the
amplifier.
- A same-width standalone `CAST(id + i)` *projection* plans in 0.038 s —
the blow-up is specific to the wide `Aggregate` SQL path.
`datafusion.optimizer.max_passes` 0 / 1 / 3 does not move the wall.
A `py-spy --native` profile of the same `sql()` clusters on
`foldhash`/`hashbrown` hashing, `TreeNode::apply`, and
`TypeCoercionRewriter`. Suspected mechanism: an O(N)-per-expression
TreeNode walk or hash inside `SqlToRel`'s aggregate expression handling
(qualify/normalize per select item).
Minimal reproduction (Rust, release): register a one-column `Int64`
`MemTable` named `t` on a stock `SessionContext`, then time
`state.statement_to_plan(state.sql_to_statement(&sql, "generic").await?)`
for `SELECT` of N items `CAST(sum(id + i) AS VARCHAR) AS c{i}`.
Contributor guide
Research direction
Start with the minimal Rust reproduction using a stock SessionContext and compare state.statement_to_plan with the DataFrame::aggregate path. Trace SqlToRel::statement_to_plan around aggregate expression handling, then inspect the TypeCoercionRewriter and TreeNode::apply areas highlighted by the profile. Done means the wide SQL Aggregate no longer shows the reported superlinear planning time while retaining correct plans.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust, sql
- Domain
- databases, performance
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 52/100