You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datafusion.apache.org by gi...@apache.org on 2026/09/02 05:43:33 UTC
(datafusion) branch gh-readonly-queue/main/pr-23615-1608ee70faa06063a38f01e8c57c1a6879708cd6 created (now adb071111f)
This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a change to branch gh-readonly-queue/main/pr-23615-1608ee70faa06063a38f01e8c57c1a6879708cd6
in repository https://gitbox.apache.org/repos/asf/datafusion.git
at adb071111f fix: dedup commutative AND/OR operands when canonicalize is disabled (#23615)
This branch includes the following new commits:
new adb071111f fix: dedup commutative AND/OR operands when canonicalize is disabled (#23615)
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org
(datafusion) 01/01: fix: dedup commutative AND/OR operands when canonicalize is disabled (#23615)
Posted by gi...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a commit to branch gh-readonly-queue/main/pr-23615-1608ee70faa06063a38f01e8c57c1a6879708cd6
in repository https://gitbox.apache.org/repos/asf/datafusion.git
commit adb071111f43474aa0010004c3e041d886be7929
Author: Stefan Wang <1f...@gmail.com>
AuthorDate: Wed Sep 2 05:43:10 2026 +0000
fix: dedup commutative AND/OR operands when canonicalize is disabled (#23615)
## Which issue does this PR close?
- Closes #14943.
Revives #21870, which was closed by the stale bot. The direction was
agreed in that thread, and `sql_planner` was benchmarked there
([results](https://github.com/apache/datafusion/pull/21870#issuecomment-4338614104),
no measurable change).
## Rationale for this change
`SimplifyExpressions` disables canonicalization for `LogicalPlan::Join`
(see #8780), so the AND/OR dedup in `expr_contains_inner` cannot
recognize duplicates that differ only by commutative operand order (`A =
B` vs `B = A`). Simplifying inside a join filter, the delta-rs MERGE
case reported in #14943, keeps the duplicate across simplifier cycles
because nothing normalizes operand order first.
The issue thread pointed at the fix: CSE already dedups `A = B` / `B =
A` via `NormalizeEq`, so this routes the simplifier's leaf comparison
through the same trait.
## What changes are included in this PR?
`expr_contains_inner` compares leaves with `Expr::normalize_eq` instead
of `==`. `NormalizeEq` handles `+`, `*`, `&`, `|`, `^`, `=`, and `!=`
commutatively and falls back to structural `==` for everything else.
Non-commutative rules and the existing `!needle.is_volatile()` guard are
unchanged. A regression test covers the `AND`, `OR`, and 3-conjunct
nested forms.
`delete_xor_in_complex_expr` uses `normalize_eq` as well.
`expr_contains` guards the `BitwiseXor` rules, which then hand deletion
off to that helper. Leaving it structural let the guard fire on operands
the helper could not delete, so the rule rebuilt its input and still
reported `Transformed::yes`, spinning the simplifier to its cycle limit
without changing the result. XOR is the only `expr_contains` caller
shaped that way. The other eight return `*left`/`*right` directly, so a
normalized match there is always a real change.
`NormalizeEq for Expr` also now compares scalar/aggregate/window
functions by full identity rather than `name()` alone. It previously
treated two distinct functions that share a display name as equal, so
routing the dedup through it collapsed `regex_udf(x) AND regex_udf(x)`
(two different UDFs, same name) into one predicate. Registry-parsed SQL
reuses one instance per name and is unaffected. This only stops merging
genuinely distinct same-named functions, which programmatically built
plans (delta-rs MERGE, the #14943 reporter) can produce.
## Are these changes tested?
Each fix has a regression that fails without it.
`test_simplify_swapped_operands_in_and_or_no_canonicalize` fails on
`main` (the duplicate passes through unchanged) and passes with the fix;
the `simplify_expr.slt` cases cover the join path end to end.
`test_simplify_swapped_operands_in_xor_no_canonicalize` pins the cycle
behavior: with `delete_xor_in_complex_expr` left structural it returns
the input unchanged after `cycles=3`, and with the fix it folds to `0`
in `cycles=2`. The existing `test_parameterized_scalar_udf` guards the
function-identity fix.
`datafusion-optimizer`, `datafusion-common`, `datafusion-expr`, and the
full `sqllogictest` suite pass. `cargo fmt`/`clippy -D warnings` are
clean. `sql_planner` shows no measurable change.
## Are there any user-facing changes?
No public API changes. AND/OR and XOR chains containing
commutative-equivalent duplicates now collapse even when the
simplifier's canonicalizer is disabled (currently the
`LogicalPlan::Join` path). Canonicalize-on paths produce the same output
as before.
---------
Signed-off-by: 1fanwang <1f...@gmail.com>
Signed-off-by: Stefan Wang <1f...@gmail.com>
Co-authored-by: Andrew Lamb <an...@nerdnetworks.org>
---
datafusion/expr/src/expr.rs | 35 ++++++++-
.../src/simplify_expressions/expr_simplifier.rs | 85 ++++++++++++++++++++++
.../optimizer/src/simplify_expressions/utils.rs | 20 ++++-
.../sqllogictest/test_files/simplify_expr.slt | 54 ++++++++++++++
4 files changed, 187 insertions(+), 7 deletions(-)
diff --git a/datafusion/expr/src/expr.rs b/datafusion/expr/src/expr.rs
index 3b708b4ede..ad491c9782 100644
--- a/datafusion/expr/src/expr.rs
+++ b/datafusion/expr/src/expr.rs
@@ -2514,7 +2514,7 @@ impl NormalizeEq for Expr {
args: other_args,
}),
) => {
- self_func.name() == other_func.name()
+ self_func == other_func
&& self_args.len() == other_args.len()
&& self_args
.iter()
@@ -2545,7 +2545,7 @@ impl NormalizeEq for Expr {
},
}),
) => {
- self_func.name() == other_func.name()
+ self_func == other_func
&& self_distinct == other_distinct
&& self_null_treatment == other_null_treatment
&& self_args.len() == other_args.len()
@@ -2598,7 +2598,7 @@ impl NormalizeEq for Expr {
},
} = other.as_ref();
- self_fun.name() == other_fun.name()
+ self_fun == other_fun
&& self_window_frame == other_window_frame
&& match (self_filter, other_filter) {
(Some(a), Some(b)) => a.normalize_eq(b),
@@ -2611,10 +2611,12 @@ impl NormalizeEq for Expr {
.iter()
.zip(other_args.iter())
.all(|(a, b)| a.normalize_eq(b))
+ && self_partition_by.len() == other_partition_by.len()
&& self_partition_by
.iter()
.zip(other_partition_by.iter())
.all(|(a, b)| a.normalize_eq(b))
+ && self_order_by.len() == other_order_by.len()
&& self_order_by
.iter()
.zip(other_order_by.iter())
@@ -3831,6 +3833,7 @@ pub fn physical_name(expr: &Expr) -> Result<String> {
#[cfg(test)]
mod test {
use crate::expr_fn::col;
+ use crate::test::function_stub::max_udaf;
use crate::{
ColumnarValue, ScalarFunctionArgs, ScalarUDF, ScalarUDFImpl, Volatility, case,
lit, placeholder, qualified_wildcard, wildcard, wildcard_with_options,
@@ -4345,6 +4348,32 @@ mod test {
use super::*;
use crate::logical_plan::{EmptyRelation, LogicalPlan};
+ #[test]
+ fn normalize_eq_window_function_over_clause_lengths() {
+ let window = |partition_by: Vec<Expr>, order_by: Vec<Sort>| {
+ let mut window = WindowFunction::new(max_udaf(), vec![col("value")]);
+ window.params.partition_by = partition_by;
+ window.params.order_by = order_by;
+ Expr::from(window)
+ };
+ let base = window(vec![col("a")], vec![Sort::new(col("a"), true, true)]);
+
+ let extra_partition = window(
+ vec![col("a"), col("b")],
+ vec![Sort::new(col("a"), true, true)],
+ );
+ assert!(!base.normalize_eq(&extra_partition));
+
+ let extra_order = window(
+ vec![col("a")],
+ vec![
+ Sort::new(col("a"), true, true),
+ Sort::new(col("b"), true, true),
+ ],
+ );
+ assert!(!base.normalize_eq(&extra_order));
+ }
+
#[test]
fn test_display_wildcard() {
assert_eq!(format!("{}", wildcard()), "*");
diff --git a/datafusion/optimizer/src/simplify_expressions/expr_simplifier.rs b/datafusion/optimizer/src/simplify_expressions/expr_simplifier.rs
index dadea47848..ec01becb8f 100644
--- a/datafusion/optimizer/src/simplify_expressions/expr_simplifier.rs
+++ b/datafusion/optimizer/src/simplify_expressions/expr_simplifier.rs
@@ -2514,6 +2514,77 @@ mod tests {
}
}
+ #[test]
+ fn test_simplify_swapped_operands_in_and_or_no_canonicalize() {
+ // Regression test for https://github.com/apache/datafusion/issues/14943
+ //
+ // `SimplifyExpressions` disables canonicalization for `LogicalPlan::Join`
+ // (see https://github.com/apache/datafusion/pull/8780), so commutative
+ // operands like `A = B` and `B = A` cannot be normalized to a single
+ // form before AND/OR dedup runs. The dedup itself must therefore
+ // recognize commutative equivalence directly.
+
+ // c3 = 5 AND 5 = c3 --> c3 = 5
+ let expr = col("c3_non_null")
+ .eq(lit(5_i64))
+ .and(lit(5_i64).eq(col("c3_non_null")));
+ let expected = col("c3_non_null").eq(lit(5_i64));
+ assert_eq!(simplify_no_canonicalize(expr), expected);
+
+ // 5 = c3 AND c3 = 5 --> 5 = c3
+ let expr = lit(5_i64)
+ .eq(col("c3_non_null"))
+ .and(col("c3_non_null").eq(lit(5_i64)));
+ let expected = lit(5_i64).eq(col("c3_non_null"));
+ assert_eq!(simplify_no_canonicalize(expr), expected);
+
+ // c3 = 5 OR 5 = c3 --> c3 = 5
+ let expr = col("c3_non_null")
+ .eq(lit(5_i64))
+ .or(lit(5_i64).eq(col("c3_non_null")));
+ let expected = col("c3_non_null").eq(lit(5_i64));
+ assert_eq!(simplify_no_canonicalize(expr), expected);
+
+ // (c3 = 5 AND c4 > 0) AND (5 = c3) --> c3 = 5 AND c4 > 0
+ let expr = col("c3_non_null")
+ .eq(lit(5_i64))
+ .and(col("c4_non_null").gt(lit(0_u32)))
+ .and(lit(5_i64).eq(col("c3_non_null")));
+ let expected = col("c3_non_null")
+ .eq(lit(5_i64))
+ .and(col("c4_non_null").gt(lit(0_u32)));
+ assert_eq!(simplify_no_canonicalize(expr), expected);
+ }
+
+ #[test]
+ fn test_simplify_swapped_operands_in_xor_no_canonicalize() {
+ // `expr_contains` guards the XOR rules, so `delete_xor_in_complex_expr` has to
+ // use the same equality relation. Comparing structurally there while the guard
+ // normalizes makes the rule rebuild its input and still report `Transformed::yes`,
+ // which spins the simplifier until it hits the cycle limit.
+ //
+ // Operands are non-nullable so the expected results do not depend on how the XOR
+ // rules treat a NULL operand, which is a separate question from the cycle.
+
+ // (c4_non_null + 1) ^ (1 + c4_non_null) --> 0
+ let expr = bitwise_xor(
+ col("c4_non_null") + lit(1_u32),
+ lit(1_u32) + col("c4_non_null"),
+ );
+ let (simplified, cycles) = simplify_no_canonicalize_with_cycle_count(expr);
+ assert_eq!(simplified, lit(0_u32));
+ assert_eq!(cycles, 2);
+
+ // (c4_non_null + 1) ^ ((1 + c4_non_null) ^ c4_non_null) --> c4_non_null
+ let expr = bitwise_xor(
+ col("c4_non_null") + lit(1_u32),
+ bitwise_xor(lit(1_u32) + col("c4_non_null"), col("c4_non_null")),
+ );
+ let (simplified, cycles) = simplify_no_canonicalize_with_cycle_count(expr);
+ assert_eq!(simplified, col("c4_non_null"));
+ assert_eq!(cycles, 2);
+ }
+
#[test]
fn test_simplify_eq_not_self() {
// `expr_a`: column `c2` is nullable, so `c2 = c2` simplifies to `c2 IS NOT NULL OR NULL`
@@ -3667,6 +3738,20 @@ mod tests {
try_simplify(expr).unwrap()
}
+ fn simplify_no_canonicalize(expr: Expr) -> Expr {
+ simplify_no_canonicalize_with_cycle_count(expr).0
+ }
+
+ fn simplify_no_canonicalize_with_cycle_count(expr: Expr) -> (Expr, u32) {
+ let schema = expr_test_schema();
+ let (transformed, count) =
+ ExprSimplifier::new(SimplifyContext::builder().with_schema(schema).build())
+ .with_canonicalize(false)
+ .simplify_with_cycle_count_transformed(expr)
+ .unwrap();
+ (transformed.data, count)
+ }
+
fn try_simplify_with_cycle_count(expr: Expr) -> Result<(Expr, u32)> {
let schema = expr_test_schema();
let simplifier =
diff --git a/datafusion/optimizer/src/simplify_expressions/utils.rs b/datafusion/optimizer/src/simplify_expressions/utils.rs
index 89bb762d59..78d801630c 100644
--- a/datafusion/optimizer/src/simplify_expressions/utils.rs
+++ b/datafusion/optimizer/src/simplify_expressions/utils.rs
@@ -17,6 +17,7 @@
//! Utility functions for expression simplification
+use datafusion_common::cse::NormalizeEq;
use datafusion_common::{Result, ScalarValue, internal_err};
use datafusion_expr::{
Case, Expr, Like, Operator,
@@ -26,13 +27,18 @@ use datafusion_expr::{
/// returns true if `needle` is found in a chain of search_op
/// expressions. Such as: (A AND B) AND C
+///
+/// Equality uses [`NormalizeEq`] so commutative operands (`A = B` vs `B = A`)
+/// are recognized as the same predicate even when the canonicalizer is
+/// disabled, notably for `LogicalPlan::Join` filters (see
+/// <https://github.com/apache/datafusion/pull/8780>).
fn expr_contains_inner(expr: &Expr, needle: &Expr, search_op: Operator) -> bool {
match expr {
Expr::BinaryExpr(BinaryExpr { left, op, right }) if *op == search_op => {
expr_contains_inner(left, needle, search_op)
|| expr_contains_inner(right, needle, search_op)
}
- _ => expr == needle,
+ _ => expr.normalize_eq(needle),
}
}
@@ -43,6 +49,12 @@ pub fn expr_contains(expr: &Expr, needle: &Expr, search_op: Operator) -> bool {
/// Deletes all 'needles' or remains one 'needle' that are found in a chain of xor
/// expressions. Such as: A ^ (A ^ (B ^ A))
+///
+/// Matching uses [`NormalizeEq`] to stay consistent with the [`expr_contains`]
+/// guard on the XOR rules. A structural comparison here would let the guard fire
+/// on operands this function then fails to delete, so the rule would rebuild its
+/// input and still report a transformation, spinning the simplifier until it hits
+/// the cycle limit.
pub fn delete_xor_in_complex_expr(expr: &Expr, needle: &Expr, is_left: bool) -> Expr {
/// Deletes recursively 'needles' in a chain of xor expressions
fn recursive_delete_xor_in_expr(
@@ -56,10 +68,10 @@ pub fn delete_xor_in_complex_expr(expr: &Expr, needle: &Expr, is_left: bool) ->
{
let left_expr = recursive_delete_xor_in_expr(left, needle, xor_counter);
let right_expr = recursive_delete_xor_in_expr(right, needle, xor_counter);
- if left_expr == *needle {
+ if left_expr.normalize_eq(needle) {
*xor_counter += 1;
return right_expr;
- } else if right_expr == *needle {
+ } else if right_expr.normalize_eq(needle) {
*xor_counter += 1;
return left_expr;
}
@@ -76,7 +88,7 @@ pub fn delete_xor_in_complex_expr(expr: &Expr, needle: &Expr, is_left: bool) ->
let mut xor_counter: i32 = 0;
let result_expr = recursive_delete_xor_in_expr(expr, needle, &mut xor_counter);
- if result_expr == *needle {
+ if result_expr.normalize_eq(needle) {
return needle.clone();
} else if xor_counter % 2 == 0 {
if is_left {
diff --git a/datafusion/sqllogictest/test_files/simplify_expr.slt b/datafusion/sqllogictest/test_files/simplify_expr.slt
index 158096328e..b24a1a6cff 100644
--- a/datafusion/sqllogictest/test_files/simplify_expr.slt
+++ b/datafusion/sqllogictest/test_files/simplify_expr.slt
@@ -165,6 +165,60 @@ physical_plan
01)ProjectionExec: expr=[column1@0 = 1 as opt1, column1@0 = 2 AND column1@0 != 2 as noopt1, column1@0 = 4 as opt2, column1@0 != 5 AND column1@0 = 5 as noopt2]
02)--DataSourceExec: partitions=1, partition_sizes=[1]
+# Dedup commutative AND/OR operands in join conditions
+# (canonicalization is disabled for joins, so `A = B` vs `B = A` must be
+# recognized directly). See https://github.com/apache/datafusion/issues/14943
+
+statement ok
+create table t1(a int) as values (1), (2);
+
+statement ok
+create table t2(b int) as values (1), (3);
+
+# `t1.a = t2.b OR t2.b = t1.a` simplifies to `t1.a = t2.b`, allowing a
+# HashJoin instead of a NestedLoopJoin
+query TT
+explain select * from t1 join t2 on t1.a = t2.b or t2.b = t1.a;
+----
+logical_plan
+01)Inner Join: t1.a = t2.b
+02)--TableScan: t1 projection=[a]
+03)--TableScan: t2 projection=[b]
+physical_plan
+01)HashJoinExec: mode=CollectLeft, join_type=Inner, on=[(a@0, b@0)]
+02)--DataSourceExec: partitions=1, partition_sizes=[1]
+03)--DataSourceExec: partitions=1, partition_sizes=[1]
+
+query II
+select * from t1 join t2 on t1.a = t2.b or t2.b = t1.a;
+----
+1 1
+
+# swapped commutative operands (`t1.a + t2.b` vs `t2.b + t1.a`) dedup within
+# a non-equi join filter
+query TT
+explain select * from t1 join t2 on t1.a > t2.b and (t1.a + t2.b > 1 or t2.b + t1.a > 1);
+----
+logical_plan
+01)Inner Join: Filter: t1.a > t2.b AND t1.a + t2.b > Int32(1)
+02)--TableScan: t1 projection=[a]
+03)--TableScan: t2 projection=[b]
+physical_plan
+01)NestedLoopJoinExec: join_type=Inner, filter=a@0 > b@1 AND a@0 + b@1 > 1
+02)--DataSourceExec: partitions=1, partition_sizes=[1]
+03)--DataSourceExec: partitions=1, partition_sizes=[1]
+
+query II
+select * from t1 join t2 on t1.a > t2.b and (t1.a + t2.b > 1 or t2.b + t1.a > 1);
+----
+2 1
+
+statement ok
+drop table t1;
+
+statement ok
+drop table t2;
+
# Identity Date cast in a comparison predicate.
# `cast(d AS date)` where `d` is already Date32 is an identity cast and should
# fold away, so the predicate compares against the bare column `d`. This enables
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org