adriangb commented on code in PR #26967:
URL: https://github.com/apache/datafusion/pull/26967#discussion_r4581172053


##########
datafusion/physical-expr/src/equivalence/class.rs:
##########
@@ -213,6 +213,35 @@ impl EquivalenceClass {
             }
         }
         self.exprs.insert(expr);
+        self.promote_sub_expressions();

Review Comment:
   `EquivalenceClass::new` calls `push` per member, so building a class of n 
members runs n promotion passes. `new` could insert everything and promote 
once, as `extend` does.



##########
datafusion/physical-expr/src/equivalence/class.rs:
##########
@@ -213,6 +213,35 @@ impl EquivalenceClass {
             }
         }
         self.exprs.insert(expr);
+        self.promote_sub_expressions();
+    }
+
+    /// Makes sure the canonical expression does not contain another expression
+    /// of this class. Otherwise, with `a + b` as the canonical expression of a
+    /// class that also holds `a`, normalization would replace the `a` inside
+    /// `a + b` and turn `a + b` into `(a + b) + b`.
+    fn promote_sub_expressions(&mut self) {
+        // Each promoted expression is inside the previous canonical
+        // expression, so there are at most as many rounds as members.
+        for _ in 0..self.exprs.len() {
+            let Some(canonical) = self.exprs.first() else {
+                return;
+            };
+            let children = canonical.children();
+            let Some(idx) = self.exprs.iter().skip(1).position(|expr| {
+                // Only the children are searched: an expression equal to the
+                // canonical expression itself is not inside it. The unwrap is
+                // safe because the closure always returns `Ok`.
+                children
+                    .iter()
+                    .any(|child| child.exists(|node| Ok(node == 
expr)).unwrap())
+            }) else {
+                return;
+            };
+            // `idx` skips the canonical expression, so the expression to
+            // promote is at `idx + 1`.
+            self.exprs.move_index(idx + 1, 0);

Review Comment:
   Keeping the real index removes the `+ 1` and its comment:
   
   ```suggestion
               let children = canonical.children();
               // Only the children are searched: an expression equal to the
               // canonical expression itself is not inside it.
               let Some(idx) = 
self.exprs.iter().enumerate().skip(1).find_map(|(idx, expr)| {
                   children
                       .iter()
                       .any(|child| child.exists(|node| Ok(node == 
expr)).unwrap())
                       .then_some(idx)
               }) else {
                   return;
               };
               self.exprs.move_index(idx, 0);
   ```



##########
datafusion/sqllogictest/test_files/sort_merge_join.slt:
##########
@@ -1129,6 +1129,38 @@ DROP TABLE smj_key_r;
 statement ok
 RESET datafusion.execution.batch_size;
 
+# Regression test for #26623: a filter that equates an expression with one of

Review Comment:
   ```suggestion
   # Regression test for https://github.com/apache/datafusion/issues/26623: a 
filter that equates an expression with one of
   ```



##########
datafusion/physical-expr/src/equivalence/class.rs:
##########
@@ -1737,4 +1767,48 @@ mod tests {
 
         Ok(())
     }
+
+    #[test]
+    fn test_sub_expression_is_canonical_on_every_path() -> Result<()> {
+        let schema = abc_schema();
+        let (a, b, c) = (col("a", &schema)?, col("b", &schema)?, col("c", 
&schema)?);
+        let a_plus_b = binary(Arc::clone(&a), Operator::Plus, b, &schema)?;
+
+        // A class built directly, with the larger expression first
+        let group = EquivalenceGroup::new([EquivalenceClass::new([
+            Arc::clone(&a_plus_b),
+            Arc::clone(&a),
+        ])]);
+        assert!(group.normalize_expr(Arc::clone(&a_plus_b)).eq(&a));

Review Comment:
   `assert_eq!` prints both sides on failure:
   
   ```suggestion
           assert_eq!(&group.normalize_expr(Arc::clone(&a_plus_b)), &a);
   ```
   
   (Same for L1790 and L1811.)



##########
datafusion/sqllogictest/test_files/equivalence_properties.slt:
##########
@@ -331,6 +331,49 @@ SELECT count(*) FROM t_double WHERE a = sqrt(b);
 statement ok
 DROP TABLE t_double;
 
+###
+### Equalities
+###
+
+statement ok
+CREATE TABLE eq_t (a BIGINT, b BIGINT, c BIGINT) AS VALUES (1, 1, 2), (3, 3, 
4), (5, 5, 0), (2, 2, 3);
+
+# The filter puts a and b in one class, and c and a + 1 in another. The inner

Review Comment:
   This query has no sub-expression in a class. It guards against a fix inside 
`normalize_expr`. Could the comment say so?



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