OptimizeProjections: projection schema construction is O(exprs × width)
- Dominant language
- Rust
- Stars
- 9.3k
- Forks
- 2.4k
- Avg merge
- 3d 7h
- Merged PRs (30d)
- 344
Description
### Is your feature request related to a problem or challenge?
`OptimizeProjections` recomputes projection schemas more than necessary.
In `rewrite_projection_given_requirements` (`datafusion/optimizer/src/optimize_projections/mod.rs`), a projection that has been pruned to its required columns is rebuilt with `Projection::try_new(exprs_used, input)`. `try_new` recomputes the schema via `projection_schema` → `Expr::to_field` for every expression, and column resolution (`DFSchema::field_from_column`) is an O(M) linear scan over the input schema (there is no name→index map). So schema construction is **O(exprs × schema_width)** per projection, per optimizer pass.
This is most visible on plans with many wide `col AS col` alias projections: an alias is not a bare `Column`, so `is_projection_unnecessary` returns false and the projection is kept, its schema recomputed on every pass — even though the result schema is just a column subset of the input schema that is already available.
### Describe the solution you'd like
Build the pruned schema by **slicing the existing input schema** at the (sorted, deduped) required indices and pass it via `Projection::try_new_with_schema`, instead of recomputing it from scratch. This mirrors the schema reuse already done in `merge_consecutive_projections`. It reduces the per-projection cost from O(exprs × width) to O(k) and is behavior-preserving.
### Describe alternatives you've considered
Keeping `try_new` but adding a name→index map to `DFSchema` would also help, but is a larger change; slicing the already-available schema is local and sufficient here.
### Additional context
A separate, tiny improvement in the same area: in `datafusion/expr/src/expr_schema.rs`, `Expr::to_field` for the `Expr::Alias` branch resolves the inner expression twice — once via `expr.metadata(schema)?` (which internally calls `to_field`) and again via `expr.to_field(schema)`. These can be collapsed into a single `to_field` call, extracting both the field and its metadata from it.
I have a local patch for the first item (with a unit test) and am happy to open a PR.
---
### Update (2026-08-13)
The slicing approach proposed above is **not** behavior-preserving, contrary to what this issue originally claimed.
A `Projection`'s stored schema is not guaranteed to equal `projection_schema(input, &expr)`. `SimplifyExpressions` rewrites expressions through `LogicalPlan::map_expressions`, which replaces `expr` and keeps the existing `schema`, so constant folding can leave the schema stale: `arrow_cast([...], 'LargeList(...)')` reports `nullable: true` as a function call, folds to a non-null literal that recomputes to `nullable: false`, and the projection keeps the old value. `OptimizeProjections` calling `Projection::try_new` was silently re-normalizing that, and slicing the schema removes the normalization.
Four substrait roundtrip tests (`roundtrip_literal_list`, `roundtrip_literal_struct`, `roundtrip_literal_named_struct`, `roundtrip_literal_renamed_struct`) and `schema_evolution_nested.slt` fail as a result. The slt case matters most: the projection feeds `COPY (SELECT ...) TO ... STORED AS PARQUET`, so the stale nullability is written into the parquet file and `DESCRIBE` on the resulting external table reports `YES` where it reported `NO`. Both were verified locally against `main`, which is green.
Whether a projection's schema is an invariant or a declared output that expression rewrites must not change is now filed separately as #24284. #24281 is parked as a draft until that is settled.
The alternative this issue dismissed turned out to be the workable one. #24316 keeps `Projection::try_new` and makes the recompute cheap instead of skipping it: a lazily built name to index map on `DFSchema` (`index_of_column_by_name` and `qualified_fields_with_unqualified_name` stop scanning, and the latter stops allocating a `Vec` per lookup), plus the `Expr::Alias` single-resolve fix described below. No schema that is produced changes, so it does not depend on the outcome of #24284.
Measured on `to_field` over W `col AS col` aliases against a W-column schema:
| W | before | after | speedup |
|---|---|---|---|
| 18 | 26.74 us | 12.03 us | 2.2x |
| 40 | 75.40 us | 18.64 us | 4.0x |
| 100 | 394.8 us | 47.21 us | 8.4x |
| 300 | 3124 us | 141.4 us | 22.1x |
Per-expression cost goes from 0.98 us at W=18 to 5.32 us at W=300 before, and holds at about 0.47 us after, so the quadratic term is gone rather than just reduced. Worth noting that the linear scan I originally pointed at (`index_of_column_by_name`) is not the one `Expr::Column` actually goes through: `field_from_column` reaches `qualified_fields_with_unqualified_name` for unqualified columns, and indexing only that one moved the numbers.
Contributor guide
Assessment
This issue has not been assessed yet.