Skip to content

Commit 76dacb4

Browse files
committed
fix: keep a sub-expression as the canonical expression of its equivalence class
Closes apache#26623.
1 parent 0a363f6 commit 76dacb4

3 files changed

Lines changed: 90 additions & 1 deletion

File tree

‎datafusion/physical-expr/src/equivalence/class.rs‎

Lines changed: 33 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -215,6 +215,34 @@ impl EquivalenceClass {
215215
self.exprs.insert(expr);
216216
}
217217

218+
/// Makes sure the canonical expression does not contain another expression
219+
/// of this class. Otherwise, with `a + b` as the canonical expression of a
220+
/// class that also holds `a`, normalization would replace the `a` inside
221+
/// `a + b` and turn `a + b` into `(a + b) + b`.
222+
fn promote_sub_expressions(&mut self) {
223+
// Each promoted expression is inside the previous canonical
224+
// expression, so there are at most as many rounds as members.
225+
for _ in 0..self.exprs.len() {
226+
let Some(canonical) = self.exprs.first() else {
227+
return;
228+
};
229+
let children = canonical.children();
230+
let Some(idx) = self.exprs.iter().skip(1).position(|expr| {
231+
// Only the children are searched: an expression equal to the
232+
// canonical expression itself is not inside it. The unwrap is
233+
// safe because the closure always returns `Ok`.
234+
children
235+
.iter()
236+
.any(|child| child.exists(|node| Ok(node == expr)).unwrap())
237+
}) else {
238+
return;
239+
};
240+
// `idx` skips the canonical expression, so the expression to
241+
// promote is at `idx + 1`.
242+
self.exprs.move_index(idx + 1, 0);
243+
}
244+
}
245+
218246
/// Inserts all the expressions from other into this class.
219247
pub fn extend(&mut self, other: Self) {
220248
self.exprs.extend(other.exprs);
@@ -441,21 +469,25 @@ impl EquivalenceGroup {
441469
// Update the lookup table for the second class:
442470
Self::update_lookup_table(&mut self.map, &other_class, first_idx);
443471
self.classes[first_idx].extend(other_class);
472+
self.classes[first_idx].promote_sub_expressions();
444473
}
445474
(Some(group_idx), None) => {
446475
// Right side is new, extend left side's class:
447476
self.map.insert(Arc::clone(&right), group_idx);
448477
self.classes[group_idx].push(right);
478+
self.classes[group_idx].promote_sub_expressions();
449479
}
450480
(None, Some(group_idx)) => {
451481
// Left side is new, extend right side's class:
452482
self.map.insert(Arc::clone(&left), group_idx);
453483
self.classes[group_idx].push(left);
484+
self.classes[group_idx].promote_sub_expressions();
454485
}
455486
(None, None) => {
456487
// None of the expressions is among existing classes.
457488
// Create a new equivalence class and extend the group.
458-
let class = EquivalenceClass::new([left, right]);
489+
let mut class = EquivalenceClass::new([left, right]);
490+
class.promote_sub_expressions();
459491
Self::update_lookup_table(&mut self.map, &class, self.classes.len());
460492
self.classes.push(class);
461493
return true;

‎datafusion/sqllogictest/test_files/equivalence_properties.slt‎

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -331,6 +331,49 @@ SELECT count(*) FROM t_double WHERE a = sqrt(b);
331331
statement ok
332332
DROP TABLE t_double;
333333

334+
###
335+
### Equalities
336+
###
337+
338+
statement ok
339+
CREATE TABLE eq_t (a BIGINT, b BIGINT, c BIGINT) AS VALUES (1, 1, 2), (3, 3, 4), (5, 5, 0), (2, 2, 3);
340+
341+
# The filter puts a and b in one class, and c and a + 1 in another. The inner
342+
# ORDER BY a + 1 LIMIT 100 sorts by a member of the second class, so the outer
343+
# ORDER BY a + 1 is already satisfied and the plan has no second sort.
344+
query TT
345+
EXPLAIN SELECT * FROM (SELECT * FROM eq_t ORDER BY a + 1 LIMIT 100) WHERE a = b AND c = a + 1 ORDER BY a + 1;
346+
----
347+
physical_plan
348+
01)FilterExec: b@1 = a@0 AND c@2 = a@0 + 1
349+
02)--SortExec: TopK(fetch=100), expr=[a@0 + 1 ASC NULLS LAST], preserve_partitioning=[false]
350+
03)----DataSourceExec: partitions=1, partition_sizes=[1]
351+
352+
query III
353+
SELECT * FROM (SELECT * FROM eq_t ORDER BY a + 1 LIMIT 100) WHERE a = b AND c = a + 1 ORDER BY a + 1;
354+
----
355+
1 1 2
356+
2 2 3
357+
3 3 4
358+
359+
statement ok
360+
DROP TABLE eq_t;
361+
362+
# The two IN lists hold the same values in a different order, so they compare
363+
# equal but are kept as two members of the class of b. Planning must still
364+
# finish.
365+
statement ok
366+
CREATE TABLE eq_in (a INT, b BOOLEAN) AS VALUES (1, true), (9, false);
367+
368+
query IB rowsort
369+
SELECT * FROM eq_in WHERE (a IN (1, 2, 3, 4)) = b AND (a IN (4, 3, 2, 1)) = b;
370+
----
371+
1 true
372+
9 false
373+
374+
statement ok
375+
DROP TABLE eq_in;
376+
334377
###
335378
### Order-preserving repartition of an unbounded input
336379
###

‎datafusion/sqllogictest/test_files/sort_merge_join.slt‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1129,6 +1129,20 @@ DROP TABLE smj_key_r;
11291129
statement ok
11301130
RESET datafusion.execution.batch_size;
11311131

1132+
# Regression test for #26623: a filter that equates an expression with one of
1133+
# its own sub-expressions must not make the sort below the join fail the
1134+
# sanity check
1135+
statement ok
1136+
CREATE TABLE smj_self_eq (a INT, b INT) AS VALUES (1, 0), (2, 3);
1137+
1138+
query IIII
1139+
SELECT * FROM smj_self_eq x JOIN smj_self_eq y ON x.a = y.a AND x.b = y.b WHERE x.a + x.b = x.a;
1140+
----
1141+
1 0 1 0
1142+
1143+
statement ok
1144+
DROP TABLE smj_self_eq;
1145+
11321146
# Config reset
11331147
statement ok
11341148
RESET datafusion.optimizer.prefer_hash_join;

0 commit comments

Comments
 (0)