abp002 opened a new issue, #27537:
URL: https://github.com/apache/datafusion/issues/27537

   ### Describe the bug
   
   Follow-up to #26967 
([review](https://github.com/apache/datafusion/pull/26967#pullrequestreview-5914040412)).
 That PR fixes a filter that puts `a + b` and `a` in one equivalence class. The 
same failure remains when two classes refer to each other.
   
   With `x.a + x.b = x.c AND x.c + x.b = x.a` the classes are `{a + b, c}` and 
`{c + b, a}`. Neither canonical expression contains a member of its own class, 
but each contains a member of the other, so `EquivalenceGroup::normalize_expr` 
is not idempotent:
   
   ```
   a -> c + b -> (a + b) + b -> ...
   ```
   
   ### To Reproduce
   
   ```sql
   set datafusion.optimizer.prefer_hash_join = false;
   CREATE TABLE t (a BIGINT, b BIGINT, c BIGINT) AS VALUES (1, 0, 1), (2, 3, 5);
   SELECT * FROM t x JOIN t y ON x.a = y.a AND x.b = y.b
   WHERE x.a + x.b = x.c AND x.c + x.b = x.a;
   ```
   
   ```
   SanityCheckPlan: ... does not satisfy order requirements: [a@0 ASC, b@1 ASC].
   Child-0 order: [[c@2 + b@1 ASC, b@1 ASC]]
   ```
   
   ### Expected behavior
   
   The query returns `1 0 1 1 0 1`, as it does with `prefer_hash_join = true`. 
In general, no canonical expression should contain a member of any class.
   
   ### Additional context
   
   @adriangb suggested this shape in the review:
   
   1. Pick the canonical expression by cost, like Trino's `EqualityInference`: 
fewest columns, then fewest nodes, then a stable tiebreak. Then `a` beats `a + 
b` without a promotion pass.
   2. When a class is added or merged, check the canonical expressions across 
classes. If one contains a member of another class, directly or through a 
cycle, choose a different canonical expression or skip that rewrite.
   3. Add `debug_assert_eq!(normalize(normalize(e)), normalize(e))` in 
`normalize_expr`, so the next case fails in tests instead of in 
`SanityCheckPlan`.
   
   ### Willingness to contribute
   
   I cannot contribute a fix for this bug at this time
   


-- 
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