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

[zhuqi-lucas]

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.