Expr simplifier doesn't simplify exprs that are same if you swap lhs with rhs regardless of cycles

[ion-elgreco]

Describe the bug

I was doing some improvements to merge in delta-rs to add an expr simplifier on our early pruning filter. While doing this I noticed that these type of expressions: s.foo = 'a' and 'a' = s.foo are not getting simplified into s.foo='a' directly but rather in s.foo='a' and s.foo='a' even when you set max cycles to ludicrous number of 100.

If the lhs and rhs can be swapped and then it's equal to an existing expression, it should be removed in one cicle.

See one of our logs after using the simplifier:

Before simplifying

[crates/core/src/operations/merge/mod.rs:864:5] commit_predicate.clone() = Some(
    "unique_row_hash BETWEEN 'new_hash' AND 'new_hash' AND 202502 = month_id AND month_id = 202502 AND 20250226 = date_id AND date_id = 20250226",
)

After simplifying once with max cycles 100

[crates/core/src/operations/merge/mod.rs:886:5] commit_predicate.clone() = Some(
    "unique_row_hash >= 'new_hash' AND unique_row_hash <= 'new_hash' AND month_id = 202502 AND month_id = 202502 AND date_id = 20250226 AND date_id = 20250226",
)

To Reproduce

This is the starting expression.

Some(
    BinaryExpr(
        BinaryExpr {
            left: BinaryExpr(
                BinaryExpr {
                    left: BinaryExpr(
                        BinaryExpr {
                            left: Column(
                                Column {
                                    relation: Some(
                                        Bare {
                                            table: "t",
                                        },
                                    ),
                                    name: "unique_row_hash",
                                },
                            ),
                            op: GtEq,
                            right: Literal(
                                Utf8("new_hash"),
                            ),
                        },
                    ),
                    op: And,
                    right: BinaryExpr(
                        BinaryExpr {
                            left: Column(
                                Column {
                                    relation: Some(
                                        Bare {
                                            table: "t",
                                        },
                                    ),
                                    name: "unique_row_hash",
                                },
                            ),
                            op: LtEq,
                            right: Literal(
                                Utf8("new_hash"),
                            ),
                        },
                    ),
                },
            ),
            op: And,
            right: BinaryExpr(
                BinaryExpr {
                    left: BinaryExpr(
                        BinaryExpr {
                            left: BinaryExpr(
                                BinaryExpr {
                                    left: BinaryExpr(
                                        BinaryExpr {
                                            left: Column(
                                                Column {
                                                    relation: Some(
                                                        Bare {
                                                            table: "t",
                                                        },
                                                    ),
                                                    name: "month_id",
                                                },
                                            ),
                                            op: Eq,
                                            right: Literal(
                                                Int32(202502),
                                            ),
                                        },
                                    ),
                                    op: And,
                                    right: BinaryExpr(
                                        BinaryExpr {
                                            left: Column(
                                                Column {
                                                    relation: Some(
                                                        Bare {
                                                            table: "t",
                                                        },
                                                    ),
                                                    name: "month_id",
                                                },
                                            ),
                                            op: Eq,
                                            right: Literal(
                                                Int64(202502),
                                            ),
                                        },
                                    ),
                                },
                            ),
                            op: And,
                            right: BinaryExpr(
                                BinaryExpr {
                                    left: Column(
                                        Column {
                                            relation: Some(
                                                Bare {
                                                    table: "t",
                                                },
                                            ),
                                            name: "date_id",
                                        },
                                    ),
                                    op: Eq,
                                    right: Literal(
                                        Int32(20250226),
                                    ),
                                },
                            ),
                        },
                    ),
                    op: And,
                    right: BinaryExpr(
                        BinaryExpr {
                            left: Column(
                                Column {
                                    relation: Some(
                                        Bare {
                                            table: "t",
                                        },
                                    ),
                                    name: "date_id",
                                },
                            ),
                            op: Eq,
                            right: Literal(
                                Int64(20250226),
                            ),
                        },
                    ),
                },
            ),
        },
    ),
)

Expected behavior

Simplify further

Additional context

No response

[alamb]

I think this would be a nice improvement

There are code and existing tests that can simplify this type of expression. See tests here

datafusion/datafusion/optimizer/src/simplify_expressions/expr_simplifier.rs

Line 1993 in 5e49094

fn test_simplify_canonicalize() {

Maybe we need to improve the logic somehow

This would be a good thing for someone to look into

[ion-elgreco]

@alamb something to note, even after manually applying the optimizer again it doesn't simply foo = 5 and foo = 5

[jayzhan211]

[2025-03-04T01:01:44Z DEBUG datafusion_optimizer::utils] simplify_expressions:
    Projection: t.a
      Filter: CAST(t.b AS Int64) = Int64(4) AND Int64(4) = CAST(t.b AS Int64)
        TableScan: t
    
[2025-03-04T01:01:44Z DEBUG datafusion_optimizer::utils] unwrap_cast_in_comparison:
    Projection: t.a
      Filter: t.b = Int32(4) AND Int32(4) = t.b
        TableScan: t
    
[2025-03-04T01:01:44Z DEBUG datafusion_optimizer::optimizer] Plan unchanged by optimizer rule 'replace_distinct_aggregate' (pass 0)
[2025-03-04T01:01:44Z DEBUG datafusion_optimizer::optimizer] Plan unchanged by optimizer rule 'eliminate_join' (pass 0)
[2025-03-04T01:01:44Z DEBUG datafusion_optimizer::optimizer] Plan unchanged by optimizer rule 'decorrelate_predicate_subquery' (pass 0)
[2025-03-04T01:01:44Z DEBUG datafusion_optimizer::optimizer] Plan unchanged by optimizer rule 'scalar_subquery_to_join' (pass 0)
[2025-03-04T01:01:44Z DEBUG datafusion_optimizer::optimizer] Plan unchanged by optimizer rule 'extract_equijoin_predicate' (pass 0)
[2025-03-04T01:01:44Z DEBUG datafusion_optimizer::optimizer] Plan unchanged by optimizer rule 'eliminate_duplicated_expr' (pass 0)
[2025-03-04T01:01:44Z DEBUG datafusion_optimizer::optimizer] Plan unchanged by optimizer rule 'eliminate_filter' (pass 0)
[2025-03-04T01:01:44Z DEBUG datafusion_optimizer::optimizer] Plan unchanged by optimizer rule 'eliminate_cross_join' (pass 0)
[2025-03-04T01:01:44Z DEBUG sqlparser::parser] Parsing sql '__common_expr_1'...
[2025-03-04T01:01:44Z DEBUG sqlparser::parser] Parsing sql '__common_expr_1'...
[2025-03-04T01:01:44Z DEBUG datafusion_optimizer::utils] common_sub_expression_eliminate:
    Projection: t.a
      Projection: t.a, t.b
        Filter: __common_expr_1 AND __common_expr_1
          Projection: t.b = Int32(4) AS __common_expr_1, t.a, t.b
            TableScan: t

We simplify A = B and B = A in common_sub_expression_eliminate but not simplify_expressions

@ion-elgreco You might want to add CommonSubexprEliminate to your analyzer rules

[alamb]

@jayzhan211 has a PR to fix this here:

• Simplify Between expression to Eq #14994

[alamb]

We simplify A = B and B = A in common_sub_expression_eliminate but not simplify_expressions

I wonder if this is another example of code that would be beneficial to pull into simplify_expressions 🤔

[ion-elgreco]

@jayzhan211 has a PR to fix this here:

• Simplify Between expression to Eq #14994

If the fix gets included in DF46, then we can give it a spin in delta-rs to see if it fully resolves the issue

[alamb]

I think it will not be present in DataFusion 46 (we have the RC out for voting now)