fix: keep a sub-expression as the canonical expression of its equivalence class - #26967

@abp002 thanks for the fix! Classes built through EquivalenceGroup::new or merged by EquivalenceGroup::extend (via bridge_classes) skip this promotion, so EquivalenceGroup::new([EquivalenceClass::new([a + b, a])]) still normalizes a to (a + b) + b. Both are public. Could you run the promotion inside EquivalenceClass::push and extend instead? Then every way of building a class gets it, and the four calls in add_equal_conditions go away:

         self.exprs.insert(expr);
+        self.promote_sub_expressions();
     }
@@
     pub fn extend(&mut self, other: Self) {
         self.exprs.extend(other.exprs);
+        self.promote_sub_expressions();
@@
                 self.classes[first_idx].extend(other_class);
-                self.classes[first_idx].promote_sub_expressions();
@@
                 self.classes[group_idx].push(right);
-                self.classes[group_idx].promote_sub_expressions();
@@
                 self.classes[group_idx].push(left);
-                self.classes[group_idx].promote_sub_expressions();
@@
-                let mut class = EquivalenceClass::new([left, right]);
-                class.promote_sub_expressions();
+                let class = EquivalenceClass::new([left, right]);

With this change on current main, the physical-expr unit tests and the full sqllogictest suite pass.

    #[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));

        // Two classes bridged by `extend` through the shared `c`
        let mut group = EquivalenceGroup::default();
        group.add_equal_conditions(Arc::clone(&a_plus_b), Arc::clone(&c));
        let mut other = EquivalenceGroup::default();
        other.add_equal_conditions(c, Arc::clone(&a));
        group.extend(other);
        assert!(group.normalize_expr(a_plus_b).eq(&a));
        Ok(())
    }

@abp002 the same bug also breaks a window on main, without a sort-merge join: PARTITION BY a + b ORDER BY a under WHERE a + b = a fails at runtime with Expects PARTITION BY expression to be ordered. This PR fixes it, but nothing tests that path. Could you add it?

Removing the promotion after the merge (extend) or after push(right) in add_equal_conditions still passes the tests here, because the issue query only reaches the new-class arm. These two queries reach the other arms. Both fail with SanityCheckPlan on main, and each catches one of those removals:

Optional cleanup: this test doesn't reach the loop bound in promote_sub_expressions. With the bound replaced by loop, the query still finishes, because neither IN list is inside the other. A promoted expression is always strictly inside the previous canonical expression, so it can't cycle. I'd drop this test, or change its comment so it doesn't claim to cover termination.

Optional: no test needs a second round of this loop. With for _ in 0..1 every test still passes. A second round happens when extend brings in a + b and a behind an unrelated canonical expression. This test passes here and fails with one round:

#[test]
fn test_sub_expression_promotion_takes_several_rounds() -> 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, Arc::clone(&b), &schema)?;
    let a_plus_b_plus_c = binary(
        Arc::clone(&a_plus_b),
        Operator::Plus,
        Arc::clone(&c),
        &schema,
    )?;

    // `b * c` is canonical in `other`, so `a + b` stays ahead of `a` there
    let b_times_c = binary(b, Operator::Multiply, c, &schema)?;
    let other = EquivalenceClass::new([b_times_c, a_plus_b, Arc::clone(&a)]);
    let mut class = EquivalenceClass::new([a_plus_b_plus_c]);
    class.extend(other);
    assert!(class.canonical_expr().unwrap().eq(&a));
    Ok(())
}

Added, thanks!