asolimando opened a new issue, #27599: URL: https://github.com/apache/datafusion/issues/27599
### Is your feature request related to a problem or challenge? Follow-up to the discussion on #27250 ([comment](https://github.com/apache/datafusion/pull/27250#discussion_r4510283474), [reply](https://github.com/apache/datafusion/pull/27250#discussion_r4532709484)): the physical plan misses sorting and grouping optimizations because `EquivalenceProperties` does not know which columns determine which. #### Running example All the queries below use these two tables, with `datafusion.execution.target_partitions = 1`: ```sql -- items.csv: i_id,i_name,i_cat / 1,apple,fruit / 2,bread,bakery / 3,cheese,dairy CREATE EXTERNAL TABLE items (i_id INT, i_name VARCHAR, i_cat VARCHAR, PRIMARY KEY (i_id)) STORED AS CSV WITH ORDER (i_id ASC) LOCATION 'items.csv' OPTIONS ('format.has_header' 'true'); -- sales.csv: s_item,s_day,s_qty / 1,1,5 / 1,2,3 / 2,1,7 / 2,3,1 / 3,2,4 CREATE EXTERNAL TABLE sales (s_item INT, s_day INT, s_qty INT) STORED AS CSV WITH ORDER (s_item ASC, s_day ASC) LOCATION 'sales.csv' OPTIONS ('format.has_header' 'true'); ``` Each query computes `items JOIN sales ON s_item = i_id`. The plan is a `HashJoinExec` (`CollectLeft`) with `items` as the build side and `sales` as the probe side. For an inner join, `HashJoinExec` keeps the order of its probe side (the right input, here `sales`), so the join output is sorted by `[s_item, s_day]`. #### Preliminaries - A *functional dependency* `X -> Y` holds when any two rows with the same values in the columns `X` also have the same values in `Y`. In `items`, `i_id -> i_name`. - A *key* is a set of columns that determines every column, because no two rows share its values. `i_id` is a key of `items`, but not of the join output, where an item appears once per sale. `i_id -> i_name` still holds there. - `EquivalenceProperties` (see the docs added in #27250) tracks equivalence classes, constants, orderings, groupings and the table `Constraints` (`PRIMARY KEY` and `UNIQUE`). The join adds the equivalence class `{s_item, i_id}`. - Functional dependencies exist only on the logical side (`FunctionalDependencies` on `DFSchema`). The physical side receives only the table `Constraints`, uses them only to check orderings (`satisfied_by_constraints`), and drops them at joins (`join_equivalence_properties` starts from `EquivalenceProperties::new`). Combining the two facts gives `s_item -> i_name`: the equivalence class makes `s_item` interchangeable with `i_id`, and `i_id -> i_name`. With it, sorting by `s_item` also sorts by `[s_item, i_name]`, and grouping by `s_item` also groups by `[s_item, i_name]`. The logical side has the dependency but no equivalence classes, and the physical side has the equivalence class but no dependency, so neither can prove it today. #### Missed optimizations Each query below is planned worse than a control query that differs only in `i_name`. 1. **Aggregate.** `GROUP BY s_item, i_name` cannot use the full input order: ```sql SELECT s_item, i_name, sum(s_qty) FROM items JOIN sales ON s_item = i_id GROUP BY s_item, i_name; -- AggregateExec: mode=Single, gby=[s_item@1 as s_item, i_name@0 as i_name], ..., group_clustering_mode=Partial([0]) ``` The same result with `GROUP BY s_item` and `max(i_name)` gets `group_clustering_mode=Full`. 2. **Sort.** A determined column in `ORDER BY` adds a sort: ```sql SELECT s_item, i_name, s_day FROM items JOIN sales ON s_item = i_id ORDER BY s_item, i_name, s_day; -- SortExec: expr=[s_item@0 ASC NULLS LAST, i_name@1 ASC NULLS LAST, s_day@2 ASC NULLS LAST] ``` `ORDER BY s_item, s_day` needs no sort. 3. **Window.** A determined column in `PARTITION BY` adds a sort, whichever order the keys are written in: ```sql SELECT s_item, i_name, s_day, sum(s_qty) OVER (PARTITION BY s_item, i_name ORDER BY s_day) FROM items JOIN sales ON s_item = i_id; -- SortExec: expr=[s_item@1 ASC NULLS LAST, i_name@0 ASC NULLS LAST, s_day@2 ASC NULLS LAST] ``` `PARTITION BY s_item ORDER BY s_day` needs no sort. ### Describe the solution you'd like 1. **Representation.** General functional dependencies (determinant columns to dependent columns), or only keys? The running example needs general dependencies: `i_id` is not a key of the join output. 2. **Sources.** Where do the dependencies come from: table constraints, aggregates (the group keys are a key of the output), joins (each side's dependencies, and its keys when the join cannot repeat its rows), or the logical `FunctionalDependencies` at physical planning? 3. **Propagation.** Every operator has to decide which dependencies still hold in its output: partial and final aggregates, unions and merges across partitions, outer joins (NULL-padded rows), unnest, and nullable `UNIQUE` columns. Keys in plans have caused wrong results before (#26818, #27112, #21507, #24787), so the rules need to be explicit and tested. 4. **Consumers.** Which checks use them: ordering satisfaction, grouping satisfaction (`grouping_satisfy`), and the reduction of `PARTITION BY` and `GROUP BY` keys (`find_longest_permutation`)? 5. **Cost.** The closure runs inside `compute_properties`, so planning time needs benchmarks. A possible starting point, for discussion only: `SortKeyWalk` (`properties/walk.rs`) already treats a pinned column as having one value within a group of rows. A functional dependency extends that: once `X` is pinned, every column that `X` determines is pinned too, and a key is the case where `X` determines every column. Together with the equivalence classes, this would cover all three examples. ### Describe alternatives you've considered - Derive dependencies from join equalities on the logical side. That would let the logical optimizer remove `i_name` from `ORDER BY` (example 2), but not the requirements that physical operators create (examples 1 and 3). - Rewrite `GROUP BY s_item, i_name` to `GROUP BY s_item` with an aggregate for `i_name` on the logical side. That fixes example 1 only. ### Additional context - #14111 added table constraints to `EquivalenceProperties`. - #21361 prunes functionally redundant `ORDER BY` keys on the logical side. - #27113 fixed functional dependencies of aggregates. - #25053 stops hash and sort-merge joins from adding the other input's ordering after the maintained input's ordering, because a probe row with duplicate join keys repeats the matching rows. That ordering is valid when the probe join key is a key, so keys on the physical side could keep it. -- 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]
