Pastoray opened a new pull request, #27601: URL: https://github.com/apache/datafusion/pull/27601
## Which issue does this PR close? - Part of #27599. ## Rationale for this change When a join key determines other columns, DataFusion still plans as if it doesn't. After `items JOIN sales ON s_item = i_id`, where `i_id` is the primary key of `items`, every `s_item` has exactly one `i_name`. But with `sales` sorted by `[s_item, s_day]`, the planner still: - adds a `SortExec` for `ORDER BY s_item, i_name, s_day`, - adds a `SortExec` for `sum(..) OVER (PARTITION BY s_item, i_name ORDER BY s_day)`, - plans `GROUP BY s_item, i_name` as `Partial([0])` instead of using the input's clustering on `s_item`. All three are redundant work on already-ordered or already-clustered input. ## What changes are included in this PR? This is a first slice of #27599, not the full design: - `EquivalenceProperties` stores functional dependencies between columns (`determinant -> dependents`), in a new private module `properties/functional_dependency.rs`. - Inner joins (including cross joins) keep each input's dependencies in the output. A primary key, or a `UNIQUE` constraint on non-nullable columns, counts as "key determines the other columns of that side". The key is no longer unique after the join, but it still determines its own side's columns. Outer joins drop them, since NULL padding breaks the reasoning. - Projections keep the dependencies whose columns are still in the output. A column that was projected away is replaced by an equal output column when there is one, e.g. `i_id -> i_name` becomes `s_item -> i_name` after `s_item = i_id`. - `SortKeyWalk` pins the columns that already-pinned columns determine. `ordering_satisfy`, `grouping_satisfy` and `find_longest_permutation` all use it, which covers the three cases above. Not included: aggregates as a source of dependencies, outer-join propagation, and planning-time benchmarks. Dependencies are dropped wherever they can't be shown to hold (unions, grouping sets). ## What is the testing strategy for this PR? - Unit tests in `functional_dependency.rs`: dependencies through an inner join and offsetting of the right side, ordering and grouping satisfaction, outer-join negative case, nullable `UNIQUE` not treated as a key, and projection (including the equal-column replacement and the case where nothing survives). The ordering and grouping tests fail without the `SortKeyWalk` change. - A new section in `sqllogictest/test_files/equivalence_properties.slt` with the issue's `items`/`sales` example: `EXPLAIN` plans for the `ORDER BY`, `GROUP BY` and window queries, result rows to check correctness, and a control table without a primary key that still sorts. - Existing suites: `datafusion-physical-expr` and `datafusion-physical-plan` lib tests pass. ## Are there any user-facing changes? No public API changes: all new items are private. Some query plans can change: a `SortExec` may be dropped, or a `GROUP BY` may be planned with `group_clustering_mode=Full`, when an inner join's key determines the other columns. Query results are unchanged. -- 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]
