Repository navigation
Commit d4c2a32
authored
perf: reuse projection schema in
## Which issue does this close?
Closes #24264. Answers #24284 in the process.
## Rationale for this change
`rewrite_projection_given_requirements`, the core of
`OptimizeProjections`, prunes a projection's expressions to the subset
actually required and then rebuilds it with `Projection::try_new`.
`try_new` recomputes the output schema via `projection_schema`, calling
`Expr::to_field` for every retained expression; column resolution is a
linear scan over the input schema, so this is `O(exprs * schema_width)`
per projection, per pass. The retained expressions are a subset of the
ones the projection already has, so the answer is usually already
sitting in `proj.schema`.
Reusing it is only safe if that schema is still what the expressions
derive. `OptimizeProjections` recomputing every schema was quietly
fixing up the cases where it is not, so this PR first makes those cases
explicit.
## What changes are included in this PR?
A stored projection schema can go stale in three ways. Each is handled
where it happens:
**1. A rule rewrites the projection's own expressions.**
- `LogicalPlan::map_expressions` now derives the projection schema again
when the expressions were rewritten, and keeps it otherwise. This covers
in-tree rules such as `SimplifyExpressions` (constant folding can turn a
nullable function call into a non-null literal) and downstream rules
registered with `add_optimizer_rule`, which previously relied on the
next `OptimizeProjections` pass to fix the schema up. This is the root
cause #24284 points at.
- `CommonSubexprEliminate` builds its projection itself, so it derives
the schema there when it changed something
(`common_subexpr_eliminate.rs`). Splitting a CASE guard such as `WHEN x
IS NOT NULL THEN x` into two common subexpressions means the rewritten
CASE can no longer be proven non-null, while the stored schema still
said non-null. This is the sqlite sqllogictest failure the previous
revision hit (`slt_good_1.slt:33179`); a minimal version is now in
`cse.slt`.
**2. The projection contains a subquery.** A subquery is optimized on
its own, so the field it produces can change after the outer
projection's schema was derived. `OptimizeProjections` recomputes the
schema for these.
**3. Rewriting the input changes a field the projection reads**, for
example an aggregate rebuilt after constant folding made a group column
non-null. After the input is rewritten, `OptimizeProjections` compares
the `k` fields the projection reads before and after
(`read_fields_unchanged`). If any differ, it recomputes.
**Otherwise it reuses the schema.** `project_schema_by_indices` selects
the already-computed fields at the retained indices and builds with
`Projection::try_new_with_schema`; when nothing is pruned, the existing
`Arc` is reused as-is. Functional dependencies are projected through the
kept indices; they can be weaker than recomputed ones, never stronger.
The checks cost `O(k)` with no name lookups, so the common case goes
from `O(exprs * width)` to `O(k)`.
## Benchmarks
The existing `sql_planner` cases barely exercise this: their projections
are narrow or plain columns, so recomputing the schema is cheap there.
#26841 adds `optimizer_wide_projection_stack_{all,half}`: four nested
projections of 200 computed expressions each over a 200-column table, as
produced by layered views. Locally (Apple M4 Pro), with that benchmark
applied to both sides:
| case | main | this PR |
|---|---|---|
| `optimizer_wide_projection_stack_all` | 11.28 ms | 6.24 ms (-45%) |
| `optimizer_wide_projection_stack_half` | 5.57 ms | 3.81 ms (-32%) |
On a downstream production query with a ~60-column projection,
`OptimizeProjections` went from 18.1 ms to 9.2 ms (-49%).
## Are these changes tested?
To check that nothing else can go stale, I temporarily logged every
reused schema that differs from `projection_schema` and ran all 542
sqllogictest files. Before (2) and (3) it logged 13 cases (12 scalar
subqueries, 1 aggregate); with them it logs none. So for everything the
test suite covers, the reused fields are exactly what `try_new` would
compute, and final plans are unchanged.
Tests, each verified to fail without its fix:
- `projection_schema_follows_rule_rewrite` (a downstream-style rule
using `map_expressions`), `projection_schema_kept_without_rule_rewrite`
(unchanged expressions keep the same schema `Arc`),
`projection_schema_follows_rewritten_exprs` (CSE unit test) and the
`cse.slt` coalesce case for (1)
- `projection_schema_follows_subquery` for (2)
- `projection_schema_follows_rewritten_input` for (3)
- `project_schema_by_indices_matches_recompute`: the sliced schema
matches `projection_schema` on fields, qualifiers, metadata and
functional dependencies, and the identity subset reuses the same `Arc`
No existing test or snapshot needed updating. Local runs on current
`main`: `datafusion-optimizer` 958 + 29 + 5, `datafusion-expr`, and all
542 sqllogictest files.
## Are there any user-facing changes?
Optimized plans are unchanged. `LogicalPlan::map_expressions` now
returns a projection with a freshly derived schema when it rewrote the
projection's expressions, so custom rules no longer need to rebuild it
with `Projection::try_new` themselves.
API change: because the schema is derived from the new expressions, a
rewrite that renames outputs (e.g. `unalias`) now changes the returned
`schema()`, and a rewrite whose new expressions reference columns of an
input installed only afterwards now fails inside `map_expressions` on a
`Projection`. The 56.0.0 upgrade guide describes both and the migration.OptimizeProjections instead of recomputing it (#24281)1 parent 867bf3c commit d4c2a32
5 files changed
Lines changed: 505 additions & 21 deletions
File tree
- datafusion
- expr/src/logical_plan
- optimizer/src
- optimize_projections
- sqllogictest/test_files
- docs/source/library-user-guide/upgrading
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
544 | 544 | | |
545 | 545 | | |
546 | 546 | | |
| 547 | + | |
| 548 | + | |
| 549 | + | |
547 | 550 | | |
548 | 551 | | |
549 | 552 | | |
| |||
553 | 556 | | |
554 | 557 | | |
555 | 558 | | |
556 | | - | |
557 | | - | |
558 | | - | |
559 | | - | |
560 | | - | |
561 | | - | |
562 | | - | |
| 559 | + | |
| 560 | + | |
| 561 | + | |
| 562 | + | |
| 563 | + | |
| 564 | + | |
| 565 | + | |
| 566 | + | |
| 567 | + | |
| 568 | + | |
| 569 | + | |
| 570 | + | |
| 571 | + | |
| 572 | + | |
| 573 | + | |
| 574 | + | |
| 575 | + | |
| 576 | + | |
| 577 | + | |
563 | 578 | | |
564 | 579 | | |
565 | 580 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
76 | 76 | | |
77 | 77 | | |
78 | 78 | | |
79 | | - | |
80 | | - | |
81 | | - | |
82 | | - | |
83 | | - | |
| 79 | + | |
| 80 | + | |
| 81 | + | |
| 82 | + | |
| 83 | + | |
| 84 | + | |
| 85 | + | |
| 86 | + | |
| 87 | + | |
| 88 | + | |
| 89 | + | |
| 90 | + | |
| 91 | + | |
| 92 | + | |
| 93 | + | |
| 94 | + | |
84 | 95 | | |
85 | 96 | | |
86 | 97 | | |
| |||
889 | 900 | | |
890 | 901 | | |
891 | 902 | | |
892 | | - | |
| 903 | + | |
893 | 904 | | |
894 | 905 | | |
895 | 906 | | |
896 | | - | |
| 907 | + | |
897 | 908 | | |
898 | 909 | | |
899 | 910 | | |
| |||
2157 | 2168 | | |
2158 | 2169 | | |
2159 | 2170 | | |
| 2171 | + | |
| 2172 | + | |
| 2173 | + | |
| 2174 | + | |
| 2175 | + | |
| 2176 | + | |
| 2177 | + | |
| 2178 | + | |
| 2179 | + | |
| 2180 | + | |
| 2181 | + | |
| 2182 | + | |
| 2183 | + | |
| 2184 | + | |
| 2185 | + | |
| 2186 | + | |
| 2187 | + | |
| 2188 | + | |
| 2189 | + | |
| 2190 | + | |
| 2191 | + | |
| 2192 | + | |
| 2193 | + | |
| 2194 | + | |
| 2195 | + | |
| 2196 | + | |
| 2197 | + | |
2160 | 2198 | | |
0 commit comments