apache / apache/datafusion

OptimizeProjections: projection schema construction is O(exprs × width)

Open
#24,264 0 comments 0 reactions 1 assignee Claimed by @zhuqi-lucas View on GitHub
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.