cetra3 opened a new pull request, #26842: URL: https://github.com/apache/datafusion/pull/26842
> [!NOTE] > This is a draft to discuss a direction, not a PR to merge as is. It shows what giving logical plan columns an identity looks like end to end, and which bugs it fixes. If the direction is wanted, it would be split into reviewable steps (see "How this could land"). ## Which issue does this PR close? It does not close issues on its own. It is related to the leaf expression and filter pushdown epic, #25459, and to the older discussions about column identity (#8379, #12723, #1468). It fixes the issues below with one mechanism. Several have open targeted fixes, which are smaller and can land first. This PR is not meant to compete with them. | Issue | On `main` | With this PR | Targeted fix | |---|---|---|---| | #26619 | fixed by #26783 (was a `Utf8View > Int32` comparison error) | `2` | #26783 | | #26621 | `No field named t.a`, or a panic | `1 2 4`, `1 2 x` | #26702 | | #26573 | `No field named x.a` | `(1,1), (1,2)` | #26596 | | #25837 | `No field named l.id` | `(1,10), (2,20)` | #26044 | | #26692 | wrong results; errors | correct | #26699 | | #26622 | schema check failure | `false, true` | #26638 | | #26033 | `No field named __correlated_sq_1.y` | correct (4 variants) | #26558 | | #26221 | `duplicate unqualified field name "sum(t.x)"` (aliased form) | `3 3`, `2 2` | #26376, #26350 | | #3353 | `duplicate unqualified field name` | `99 99` | #26376 | | #6543 | `Projections require unique expression names` | two `c1` columns | | | #4478 | `Projections require unique expression names` | `1 1` | | | #13558 | `Projections require unique expression names` | `1, 3, 5` | | | #25447 | the same `get_field` is extracted and computed twice | computed once | assigned | Each fix has a regression test in `column_identity.slt`, or shows in the expected plans of the existing leaf pushdown tests (#25447). ## Rationale for this change The optimizer identifies a column by its qualifier and name. Two different columns can have the same name: a column and a cast of it (`t.a` and `CAST(t.a AS ...)`, which is also named `t.a`), two scans of the same table, the outputs of two references to a CTE, or two aggregates that differ only by a cast. When a rule moves or rebuilds a node, it finds the columns it needs by name, and with such plans it finds the wrong one, or none. Users see errors such as `No field named t.a`, duplicate field name errors, Arrow type errors, panics and wrong results. Each of the issues above was fixed, or is being fixed, in the rule that hit it. The cause is shared, and so the class keeps coming back. Other planners give each column an identity that does not depend on its name: Spark (`ExprId`), DuckDB (`ColumnBinding`), Trino (symbols), CockroachDB (`ColumnID`). This PR does the same for DataFusion's logical plans. ## What changes are included in this PR? **Where ids come from.** A `ColumnId` is created where a column is defined and stored with the definition. No pass assigns or repairs ids later. | Columns | Id | |---|---| | Table scan, `VALUES` | allocated when the node is built, and kept when it is rebuilt (`TableScanBuilder::from`) | | Computed outputs of `Projection`, `Aggregate`, `Window`, `DistinctOn` | allocated by `Alias::new`. The constructors wrap any output that is not a column or an alias in an implicit alias named after the expression (`named_output_expr`), so the id is part of the expression and survives rewrites. Implicit aliases are not displayed. | | `Union`, `RecursiveQuery` outputs | allocated when the node is built, and kept by every rebuild | | Join mark column, grouping set columns, `__grouping_id`, unnested columns | derived from the id of the one input column they come from | | Columns that rules define (common subexpressions, extracted leaf expressions, ...) | allocated by the rule, which gives the same id to the references it builds | **References.** A reference gets the id of the column it resolves to when its name is resolved: `normalize_col`, the builder's `ColumnNormalizer`, `expr_as_column_expr`, outer references, and the `DFSchema::column(i)` helpers. Schema lookups use the id first, and the qualifier and name when there is no id. **Semantics:** - `Column` equality compares ids when both columns have one. Hashing and ordering are still by name. - Comparisons that mean "computes the same rows" (subquery equality, CSE's `NormalizeEq`, `unions_to_filter`) compare plans up to ids (`LogicalPlan::is_equivalent_up_to_column_ids`). - A copy of a plan gets new ids (`with_fresh_column_ids`), for example each reference to a CTE. - Two unqualified fields with the same name are allowed when their ids differ, and a lookup by that name is ambiguous, as in Postgres. **Names.** Rules no longer generate unique names. CSE and leaf extraction name the columns they define after their expressions (`t.a + t.b`, not `__common_expr_1`; `t.s[x]`, not `__datafusion_extracted_1`) and reference them by id. This removes the alias generators of these rules, the reserved `__datafusion_extracted` prefix, and the scan that skipped past user aliases with that prefix. Extraction projections are recognized by `AliasKind::Extraction` instead of by the prefix. **EXPLAIN.** Because names are no longer unique, a logical plan quotes a column reference whose name is not a plain identifier while it is displayed: `"t.a + t.b" * Int64(2)`, `"sum(t.x)" AS total`. Without the quotes, a column named `t.ts` that holds `CAST(t.ts AS ...)` reads as the table column. Only the display changes; names and `Expr`'s `Display` elsewhere do not. **Validator.** `LogicalPlan::column_id_issues` reports references without an id, with a stale id, or whose id and name disagree. The analyzer and optimizer log them after each rule under the `datafusion::column_id` target, at debug level; there is no cost when that target is off. ## What is the testing strategy for this PR? - `datafusion/sqllogictest/test_files/column_identity.slt` has a regression test for each fixed issue, and for duplicate names. - The existing suites pass: sqllogictest (all files), unit tests of `common`, `expr`, `optimizer`, `sql`, `proto` and `substrait`, and `cargo test -p datafusion --lib --tests`. Many expected plans changed. Apart from the queries that now work, the changes are: the new names of common subexpressions and extracted columns, quoted column references, and extractions that are no longer computed twice. A script checked that the other changed lines differ only by quotes. The hunks that rename common subexpressions and extractions were not checked by script, only sampled by hand. - With `RUST_LOG=datafusion::column_id=debug`, the sqllogictest suite reports no reference whose id and name refer to different columns, and none whose id refers to a column with another name. ## Are there any user-facing changes? Yes. This needs the `api change` label. - Duplicate output names are allowed when they are different columns: `SELECT a AS c1, a AS c1`, `SELECT count(), count()`, also in the DataFrame API. `SELECT a, a` is still rejected. - EXPLAIN output changes: common subexpressions and extracted leaf expressions are named after their expressions, and logical plans quote column references that are not identifiers. - An output keeps its name when an analyzer rule rewrites its expression: `SELECT 42` stays `Int64(42)` after a rule turns the literal into a `UInt64`. - API: `Column` and `Alias` gain fields (`Column::id`, `Alias::id`, `Alias::kind`), `DFSchema` stores field ids, and there is a new module `logical_plan::column_ids` (`ColumnMap`, `replace_columns`, renaming and validation). `Expr` grows from 112 to 128 bytes, and `LogicalPlan` from 176 to 192. ## Open questions and known gaps - **Planning cost is not measured yet.** Plans do more work: id lookups, renames, and alpha-equivalence comparisons. - **The migration is not finished.** The validator still reports references without an id or with a stale id, mostly from the SQL planner's intermediate SELECT projection, `optimize_projections`, type coercion and the simplifier. They work today only because lookups fall back to the name, so that fallback cannot be removed yet. - **Some plans don't carry ids.** Plans decoded from protobuf or Substrait, and `UserDefinedLogicalNode` schemas, have no ids. They work by name, as before. - **Not fixed here:** the unaliased form of #26221 (`SELECT sum(x), sum(CAST(x AS ...))`), #21727 and #15558 (outer references two levels up), and #26704. - **Design choices to discuss:** implicit aliases on every computed output; duplicate output names; quoting in EXPLAIN; `Column` equality by id. ## How this could land 1. Add `ColumnId` and ids on schemas, aliases and references, with lookups by id and a name fallback. Plans and EXPLAIN do not change. 2. Make the constructors and rules id aware, one area at a time, with the validator as the measure. 3. Switch `Column` equality to ids, and allow duplicate names. 4. Remove the generated names from CSE and leaf extraction. This PR was written with the help of an AI assistant (Claude Code). 🤖 Generated with [Claude Code](https://claude.com/claude-code) -- 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]
