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]

Reply via email to