adriangb opened a new issue, #25448: URL: https://github.com/apache/datafusion/issues/25448
### 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: - https://github.com/apache/datafusion/issues/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. - https://github.com/apache/datafusion/pull/25412: the pass-through comparison reads one side qualified and the other bare, so a column is added a second time. Planning error. - https://github.com/apache/datafusion/issues/24241: a self join gives `p.__datafusion_extracted_1` and a bare `__datafusion_extracted_1` in one schema. Planning error. - https://github.com/apache/datafusion/issues/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. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
