feat: give logical plan columns an identity (ColumnId) - #26842

The core change

A column gets a ColumnId where it is defined, and references read it by that id. The name becomes a label.

// datafusion/common/src/column.rs
pub struct ColumnId(NonZeroU64);

pub struct Column {
    pub relation: Option<TableReference>,
    pub name: String,
    pub spans: Spans,
    /// The identity of the column this refers to
    pub id: Option<ColumnId>, // new
}

// datafusion/expr/src/expr.rs
/// An output of a Projection, Window, DistinctOn or Aggregate.
/// There is no way to build these nodes without ids.
pub struct NamedExpr {
    pub expr: Expr,
    pub id: ColumnId,
    // ...
}

Ids come from a ColumnIdGenerator per session. Columns that a node defines without an expression (union and recursive query outputs, unnested columns, the join mark column) keep their ids in the node's schema. TableScan keeps the ids of its source columns in a shared Arc<[ColumnId]>, so rebuilding a scan doesn't allocate per column.

Which issue does this PR close?

It closes no issues as a draft. It is related to the leaf expression and filter pushdown epic, #25459, and to the older discussions about column identity (#8379, #12723, #1468).

Bugs fixed

Each row was run on main at 888879d01c and on this branch. All are open except #26619.

Wrong results

Errors on valid queries

Other

#21727 and #15558 use targeted rewrites that only cover some shapes; see "Decorrelation: deferred work". #26622 was on the earlier list, but it now gives the same output on main, so it is not counted here.

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, 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 wrong results, No field named errors, duplicate name errors and panics.

Each of these bugs has been fixed, or is being fixed, in the rule that hit it. The cause is shared, so the class keeps coming back. Spark (ExprId), DuckDB (ColumnBinding), Trino (symbols) and CockroachDB (ColumnID) all give each column an identity independent of its name.

What changes are included in this PR?

179 files, +18,951/−4,450. Each commit is one stage, and each builds and passes on its own (see the testing section for the exception).

Stages 1 and 2 are the smallest, but they fix nothing by themselves: the benefit starts at stage 6, because names decide identity until then.

What the switch changes:

• Names come from definitions. They are restored at the root and for write inputs when optimization ends, so rules no longer need NamePreserver or alias_if_changed.
• Equality of columns, schemas and plans includes ids. is_equivalent_up_to_column_ids and Expr::without_column_ids compare without them.
• A column with an id is looked up by id only. References without an id, such as hand-built expressions, still resolve by name.
• Outputs may share a name when their ids differ. A lookup by that name is ambiguous, as in Postgres.
• __common_expr_N and __datafusion_extracted_N are gone. Common subexpressions are named after their expressions, and extraction is a typed mark on NamedExpr.

Decorrelation: deferred work

Ids fix decorrelation bugs that are about binding: #26234, #26033, #26692, and the projection form of #26619. They do not make decorrelation general. That is #5492, and this PR leaves it open.

Stage 9 is a stopgap. On #21727, the request was not to extend the existing subquery rewrites because of the risk of more wrong results. Stage 9 does add to them, so it is the last commit, its rewrites are in their own module (decorrelate_nested.rs), and they are documented as going away with #5492. Both match columns by id, and apply only where they are exact:

• Substitution ([dbolympics] Support Nested correlated subquery error with a depth exceeding 1 #15558): a top-level conjunct x = outer.col in the middle subquery lets nested subqueries read x. Only for the same type, not floats or nested types, and x may be nullable only if outer.col is.
• Flattening ([dbolympics] Grandparent column reference in nested subquery causes planner error #21727): a positive EXISTS or IN directly inside an EXISTS or IN becomes an inner join in the middle subquery, because only the middle's set of rows matters.

Stage 9 can be dropped. #21727 and #15558 would go back to failing, and the verifier's allowlist would return. It also carries PushDownFilter fixes that would need to be kept.

Two-level shapes that still fail. These stop with Physical plan does not support logical expression Exists/InSubquery/ScalarSubquery, and column_identity.slt tests that none of them returns rows:

• NOT EXISTS or NOT IN at the nested level
• EXISTS under OR
• an aggregate, LIMIT, DISTINCT or window in the middle subquery
• a scalar middle subquery with no equality to substitute through
• an equality under OR, on floats, or across a cast
• the ON clause of MERGE (merge_into.slt)

Decorrelating these needs the column two levels up to be in scope where the predicate runs. The middle subquery can't output it without changing its row count, so this takes a dependent join: push the distinct values of the outer columns down as a domain, group or join on them, and join back.

Issues from the #5492 list that this PR does not change. Same results on main and on this branch:

#26704 (subqueries in an aggregate) is also unchanged. It needs a new rewrite, not a fix to column identity.

What ids could offer #5492 (a proposal, not built here):

• The domain is a copy of part of the outer plan. with_fresh_column_ids makes that copy without name clashes.
• Mapping a correlated column to the domain column is a map from id to id, so it doesn't matter if the levels read the same table.
• The verifier reports a reference to a column that is out of scope as a stale id, so a rewrite that gets this wrong fails in tests.
• The rewrites in stage 9 and the DecorrelatePredicateSubquery and ScalarSubqueryToJoin rules could then be deleted.

What is the testing strategy for this PR?

• datafusion/sqllogictest/test_files/column_identity.slt has a regression test for the fixed issues and for the shapes that must keep failing. Error when joining dataframes with duplicate column names if dataframes generated from file #14147 and Unparser with PostgreSqlDialect fails after Optimization Pass #21066 have Rust tests, as they need the DataFrame and unparser APIs.
• The verifier (DATAFUSION_COLUMN_ID_VERIFY=1) checks after every analyzer and optimizer rule that references have an id, that the id is in scope, and that the name agrees. At the top of the stack it has no allowlist.
• Top of the stack: the CI command passes with the verifier on (13,594 tests and 547 sqllogictest files), and so do 482 doctests, 116 datafusion-cli tests, and the examples.
• Every stage was run separately with fmt, clippy, rustdoc and the CI command, with the verifier on from stage 4.
  • Exception: stages 4 and 5 fail leaf_pushdown_fuzz and leaf_pushdown_fuzz_extended, with the verifier on only. Both pass without the verifier, and from stage 6 on.
• Expected plans change for the new names of common subexpressions and extracted columns, the fixed queries, and the plans of unsupported subqueries, which are now left in place.

Performance

Planning time was measured on the sql_planner benchmarks before rebasing onto the current main, against 934691e9af. Across 142 benchmarks the median change was +2.4% and the mean −0.8%.

Window benchmarks are 7–10% slower and TPC-H physical plans 5–8%. What remains is the extra passes over the plan: binding when the analyzer starts, the final relabel, and finding the highest id.

These numbers need rerunning. #26630 (a name index on DFSchema) has merged since. Lookups by id are still linear scans, so they may not share that gain, and wide schemas may compare worse than shown.

Are there any user-facing changes?

Yes. This needs the api change label. The upgrade guide (56.0.0.md) covers the API changes.

• Queries: duplicate output names are allowed when they are different columns: SELECT a AS c1, b AS c1, SELECT ts, id, *.
• EXPLAIN: common subexpressions and extracted expressions are named after their expressions.
• API:
  • Column is #[non_exhaustive] and has an id.
  • Projection, Window, DistinctOn and Aggregate take NamedExprs.
  • Expr::GroupingSet no longer appears in Aggregate.group_expr.
  • OptimizerConfig::column_id_generator is required.
  • Constructors such as Union::try_new take a generator.
• Behaviour:
  • Column and plan equality include ids, so two plans built separately are generally not ==.
  • A custom analyzer rule can't rename a query's outputs, because names are restored at the root.
  • The simplifier now reports canonicalizing and shortening an IN list as a transformation.
  • A table provider's schema with duplicate names no longer errors in physical planning.
  • A filter with a correlated subquery is no longer pushed down.

Open questions

• Landing. Stages 1–2 could land alone, but deliver nothing to users yet. Could the equality change be done without a global switch, so that the work can land one operator at a time?
• NamedExpr versus optional ids. Required ids on definitions make up a large part of stage 3. An alternative is optional ids enforced by the verifier, with NamedExpr as a later tightening.
• The name fallback. References without ids still resolve by name in production. Removing it would break hand-built plans.
• Extension nodes that compute columns have to opt in to ids.
• Readability. Debug hides ids. A computed column keeps the name of its expression, so t.a + t.b * Int64(2) in a logical plan can mean the column named t.a + t.b, times 2. CAST keeps its input's name.

This PR was written with the help of an AI assistant (Claude Code).

🤖 Generated with Claude Code