Resolve columns by schema index, not by name, in ExtractLeafExpressions and PushDownLeafProjections

[adriangb]

Is your feature request related to a problem or challenge?

ExtractLeafExpressions and PushDownLeafProjections resolve columns by name. Every decision the two rules make about which column is which compares strings. This is the root of a series of planning failures and wrong results, and each fix so far has patched one comparison.

The name keyed sites, all in datafusion/optimizer/src/extract_leaf_expressions.rs:

Site	Key
build_projection_replace_map	Column::flat_name() of the projection output
replace_cols_by_name (from push_down_filter.rs, called by both loops of build_extraction_projection_impl)	exact flat_name() string match
build_extraction_projection_impl, pass-through loop	existing_cols holds bare Expr::Column entries only
build_extraction_projection_impl, extracted expression loop	expression equality after the flat_name() rewrite
split_and_push_projection, needs_recovery	set of unqualified field names, BTreeSet<&str>
find_owning_input and route_to_inputs	ColumnReference sets per input
is_pure_extraction_projection, routing_extract, advance_generator_past_existing	starts_with(EXTRACTED_EXPR_PREFIX) on the alias name

The bugs these sites produced:

• Wrong results: leaf expression pushdown removes a computed column that has the same name as its input column #25414: needs_recovery compares names only, so (- t.a) AS a looks like the table column a, and the recovery projection is dropped. Wrong results in the default configuration.
• fix: resolve pass-through columns against the input when merging an extraction projection #25412: the pass-through comparison reads one side qualified and the other bare, so a column is added a second time. Planning error.
• push_down_leaf_projections fails for self joins in some scenarios #24241: a self join gives p.__datafusion_extracted_1 and a bare __datafusion_extracted_1 in one schema. Planning error.
• optimize_projections fails with "No field named ..." when join keys contain get_field (ExtractLeafExpressions) #22895: an extracted join key makes optimize_projections fail with "No field named".
• A rename or a swap in a projection makes the merge push the input column beside the rename. Planning error. Filed separately.
• The extracted expression loop writes the same expression two times when the two spellings differ. Filed separately.

The physical layer has not had this class of bug. A physical expression names a column as col@idx, so a rename cannot make two columns look like one.

OptimizeProjections also has not had this class, and it works over the same plans. It walks down carrying RequiredIndices, a sorted set of column indices into the child schema (datafusion/optimizer/src/optimize_projections/required_indices.rs), and rewrites the plan on the way back up. It never moves a node through another node.

Describe the solution you'd like

Give the leaf rules the same shape as OptimizeProjections.

1. Walk the plan top-down. Carry, per scan, the set of leaf expressions that the subtree above needs. Identify each requirement by the child schema index it reads, not by a name.
2. Rewrite bottom-up. Build the extraction projection directly above the scan, once, from that set. Rewrite each consumer on the way back up to read the column the new projection produces, again by index.
3. Delete the "move a Projection node through one node type at a time" machinery: push_extraction_pairs, route_to_inputs, split_and_push_projection and the recovery projection logic. A single bottom-up rewrite has no intermediate plan whose schema can drift, so there is nothing to recover.

This is a large refactor. It replaces most of a 3300 line file. I suggest it lands as one change rather than as a migration, because the two designs cannot both own the extraction projection.

Describe alternatives you've considered

Keep the current shape and key every comparison on (qualifier, name, type). This is what the individual fixes do. It closes each shape as it is reported. It does not close the class, because a plan can hold two fields with the same qualifier, name and type.

Keep the current shape and thread a (plan node, index) identity through the existing helpers. This gets the right identity, but the helpers still move a Projection node through Filter, Sort, Limit, Aggregate, Join, Union and SubqueryAlias one at a time. Each move needs its own remap, so the number of places that can be wrong does not change.

Additional context

The guard set for the refactor:

• 55 unit tests in datafusion/optimizer/src/extract_leaf_expressions.rs. They assert plan text at each of the two passes, so they show any change of shape.
• datafusion/sqllogictest/test_files/: struct.slt, map.slt, dictionary_struct.slt, projection_pushdown.slt, projection.slt, cse.slt, parquet_nested_schema_pruning.slt, schema_evolution_nested.slt, subquery_projection.slt.
• The MREs of 25414, 25412, 24241 and 22895 belong in struct.slt as part of the refactor.

A differential fuzz would raise confidence a lot. Run the same statement with datafusion.optimizer.enable_leaf_expression_pushdown set to true and to false, and compare the rows. A grid of 900 generated statements over a three column table with one struct column found 207 planning errors and two wrong result shapes on main that way.

Tracked in the leaf-pushdown EPIC: #25459