Skip to content

Commit a57ed5e

Browse files
buraksennlukekim
authored andcommitted
fix: prevent incorrect results when pushing filters through anti joins (apache#24045)
## Which issue does this PR close? - Closes apache#24002. ## Rationale for this change Pushing filters to an anti join's non-output side can produce incorrect results. ## What changes are included in this PR? Restrict anti-join filter pushdown to the output side while preserving two-sided join-key pushdown for semi joins. ## Are these changes tested? Yes, with updated unit and SQL logic tests. ## Are there any user-facing changes? no API changes but some downstream expected plans may change (cherry picked from commit a3f0f93) Conflict resolved when applying to spiceai-54 (DataFusion 54.1): - datafusion/sqllogictest/test_files/dynamic_filter_pushdown_config.slt: the expected physical plan for the NOT IN + TopK query keeps the 54.1 display (no null_aware marker on HashJoinExec, no dynamic_rg_pruning field). With this change the TopK filter no longer reaches the non-output side, so the right-side scan drops from two dynamic filters to one; the one that remains is the hash join's own probe-side filter, which upstream no longer pushes for a null-aware anti join with a nullable build key (5975a2d, apache#23173, not on 54.1). Query results are unchanged from upstream.
1 parent 260b243 commit a57ed5e

3 files changed

Lines changed: 77 additions & 34 deletions

File tree

‎datafusion/core/tests/physical_optimizer/filter_pushdown.rs‎

Lines changed: 26 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1587,10 +1587,8 @@ fn test_hashjoin_parent_filter_pushdown_mark_join() {
15871587
);
15881588
}
15891589

1590-
/// Test that filters on join key columns are pushed to both sides of semi/anti joins.
1591-
/// For LeftSemi/LeftAnti, the output only contains left columns, but filters on
1592-
/// join key columns can also be pushed to the right (non-preserved) side because
1593-
/// the equijoin condition guarantees the key values match.
1590+
/// Semi-join key filters can be pushed to both sides, but anti-join filters must
1591+
/// only rely on the output side to preserve their semantics.
15941592
#[test]
15951593
fn test_hashjoin_parent_filter_pushdown_semi_anti_join() {
15961594
use datafusion_common::JoinType;
@@ -1620,8 +1618,8 @@ fn test_hashjoin_parent_filter_pushdown_semi_anti_join() {
16201618
let join = Arc::new(
16211619
HashJoinExec::try_new(
16221620
left_scan,
1623-
right_scan,
1624-
on,
1621+
Arc::clone(&right_scan),
1622+
on.clone(),
16251623
None,
16261624
&JoinType::LeftSemi,
16271625
None,
@@ -1660,6 +1658,24 @@ fn test_hashjoin_parent_filter_pushdown_semi_anti_join() {
16601658
- DataSourceExec: file_groups={1 group: [[test.parquet]]}, projection=[k, w], file_type=test, pushdown_supported=true, predicate=k@0 = x
16611659
"
16621660
);
1661+
1662+
let join = Arc::new(
1663+
HashJoinExec::try_new(
1664+
TestScanBuilder::new(Arc::clone(&left_schema)).build(),
1665+
right_scan,
1666+
on,
1667+
None,
1668+
&JoinType::LeftAnti,
1669+
None,
1670+
PartitionMode::Partitioned,
1671+
datafusion_common::NullEquality::NullEqualsNothing,
1672+
false,
1673+
)
1674+
.unwrap(),
1675+
);
1676+
let predicate = Arc::new(Literal::new(ScalarValue::Boolean(Some(false))));
1677+
let plan = Arc::new(FilterExec::try_new(predicate, join).unwrap());
1678+
assert_parent_filter_remains(plan);
16631679
}
16641680

16651681
#[test]
@@ -1898,13 +1914,13 @@ fn col_lit_predicate(
18981914
))
18991915
}
19001916

1901-
fn assert_parent_filter_remains_above_aggregate(plan: Arc<dyn ExecutionPlan>) {
1917+
fn assert_parent_filter_remains(plan: Arc<dyn ExecutionPlan>) {
19021918
let mut config = ConfigOptions::default();
19031919
config.execution.parquet.pushdown_filters = true;
19041920
let optimized = FilterPushdown::new().optimize(plan, &config).unwrap();
19051921
assert!(
19061922
optimized.downcast_ref::<FilterExec>().is_some(),
1907-
"parent filter must remain above aggregate"
1923+
"parent filter must remain"
19081924
);
19091925
}
19101926

@@ -2233,7 +2249,7 @@ fn test_no_pushdown_constant_false_through_global_aggregate() {
22332249
let predicate = Arc::new(Literal::new(ScalarValue::Boolean(Some(false))));
22342250
let plan = Arc::new(FilterExec::try_new(predicate, aggregate).unwrap());
22352251

2236-
assert_parent_filter_remains_above_aggregate(plan);
2252+
assert_parent_filter_remains(plan);
22372253
}
22382254

22392255
#[test]
@@ -2270,7 +2286,7 @@ fn test_no_pushdown_constant_false_through_empty_grouping_set() {
22702286
let predicate = Arc::new(Literal::new(ScalarValue::Boolean(Some(false))));
22712287
let plan = Arc::new(FilterExec::try_new(predicate, aggregate).unwrap());
22722288

2273-
assert_parent_filter_remains_above_aggregate(plan);
2289+
assert_parent_filter_remains(plan);
22742290
}
22752291

22762292
#[test]

‎datafusion/physical-plan/src/joins/hash_join/exec.rs‎

Lines changed: 13 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -1639,14 +1639,11 @@ impl<A: CollectLeftAccumulator + 'static> ExecutionPlan for HashJoinExec<A> {
16391639
};
16401640
});
16411641

1642-
// For semi/anti joins, the non-preserved side's columns are not in the
1643-
// output, but filters on join key columns can still be pushed there.
1644-
// We find output columns that are join keys on the preserved side and
1645-
// add their output indices to the non-preserved side's allowed set.
1646-
// The name-based remap in FilterRemapper will then match them to the
1647-
// corresponding column in the non-preserved child's schema.
1642+
// For semi joins, filters on output join keys can also be pushed to the
1643+
// non-output side: every emitted row has an equal key there. This is not
1644+
// true for anti joins, whose emitted rows have no match.
16481645
match self.join_type {
1649-
JoinType::LeftSemi | JoinType::LeftAnti => {
1646+
JoinType::LeftSemi => {
16501647
let left_key_indices: HashSet<usize> = self
16511648
.on
16521649
.iter()
@@ -1660,7 +1657,7 @@ impl<A: CollectLeftAccumulator + 'static> ExecutionPlan for HashJoinExec<A> {
16601657
}
16611658
}
16621659
}
1663-
JoinType::RightSemi | JoinType::RightAnti => {
1660+
JoinType::RightSemi => {
16641661
let right_key_indices: HashSet<usize> = self
16651662
.on
16661663
.iter()
@@ -1766,21 +1763,18 @@ impl<A: CollectLeftAccumulator + 'static> ExecutionPlan for HashJoinExec<A> {
17661763
/// Determines which sides of a join are "preserved" for filter pushdown.
17671764
///
17681765
/// A preserved side means filters on that side's columns can be safely pushed
1769-
/// below the join. This mirrors the logic in the logical optimizer's
1770-
/// `lr_is_preserved` in `datafusion/optimizer/src/push_down_filter.rs`.
1766+
/// below the join. This mostly mirrors the logical optimizer's `lr_is_preserved`;
1767+
/// semi joins additionally allow join-key filters on the non-output side.
17711768
fn lr_is_preserved(join_type: JoinType) -> (bool, bool) {
17721769
match join_type {
17731770
JoinType::Inner => (true, true),
17741771
JoinType::Left => (true, false),
17751772
JoinType::Right => (false, true),
17761773
JoinType::Full => (false, false),
1777-
// Filters in semi/anti joins are either on the preserved side, or on join keys,
1778-
// as all output columns come from the preserved side. Join key filters can be
1779-
// safely pushed down into the other side.
1780-
JoinType::LeftSemi | JoinType::LeftAnti => (true, true),
1781-
JoinType::RightSemi | JoinType::RightAnti => (true, true),
1782-
JoinType::LeftMark => (true, false),
1783-
JoinType::RightMark => (false, true),
1774+
// Callers restrict the non-output side of semi joins to join-key columns.
1775+
JoinType::LeftSemi | JoinType::RightSemi => (true, true),
1776+
JoinType::LeftAnti | JoinType::LeftMark => (true, false),
1777+
JoinType::RightAnti | JoinType::RightMark => (false, true),
17841778
}
17851779
}
17861780

@@ -6406,10 +6400,10 @@ mod tests {
64066400
assert_eq!(lr_is_preserved(JoinType::Right), (false, true));
64076401
assert_eq!(lr_is_preserved(JoinType::Full), (false, false));
64086402
assert_eq!(lr_is_preserved(JoinType::LeftSemi), (true, true));
6409-
assert_eq!(lr_is_preserved(JoinType::LeftAnti), (true, true));
6403+
assert_eq!(lr_is_preserved(JoinType::LeftAnti), (true, false));
64106404
assert_eq!(lr_is_preserved(JoinType::LeftMark), (true, false));
64116405
assert_eq!(lr_is_preserved(JoinType::RightSemi), (true, true));
6412-
assert_eq!(lr_is_preserved(JoinType::RightAnti), (true, true));
6406+
assert_eq!(lr_is_preserved(JoinType::RightAnti), (false, true));
64136407
assert_eq!(lr_is_preserved(JoinType::RightMark), (false, true));
64146408
}
64156409

‎datafusion/sqllogictest/test_files/dynamic_filter_pushdown_config.slt‎

Lines changed: 38 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -457,10 +457,9 @@ ORDER BY l.id LIMIT 2;
457457
1 left1
458458
3 left3
459459

460-
# ANTI JOIN with TopK parent: TopK generates a dynamic filter on `id` (join
461-
# key) that pushes through the LeftAnti join to both the preserved and
462-
# non-preserved sides. The HashJoin pushes the self-generated filter to the
463-
# right hand side of the LeftAnti join.
460+
# ANTI JOIN with TopK parent: the TopK dynamic filter on `id` is pushed only
461+
# to the preserved output side. Filtering the non-output side can create
462+
# anti-join output.
464463
query TT
465464
EXPLAIN SELECT l.*
466465
FROM left_parquet l
@@ -479,7 +478,7 @@ physical_plan
479478
01)SortExec: TopK(fetch=2), expr=[id@0 ASC NULLS LAST], preserve_partitioning=[false]
480479
02)--HashJoinExec: mode=CollectLeft, join_type=LeftAnti, on=[(id@0, id@0)]
481480
03)----DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/dynamic_filter_pushdown_config/join_left.parquet]]}, projection=[id, data], file_type=parquet, predicate=DynamicFilter [ empty ]
482-
04)----DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/dynamic_filter_pushdown_config/join_right.parquet]]}, projection=[id], file_type=parquet, predicate=DynamicFilter [ empty ] AND DynamicFilter [ empty ]
481+
04)----DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/dynamic_filter_pushdown_config/join_right.parquet]]}, projection=[id], file_type=parquet, predicate=DynamicFilter [ empty ]
483482

484483
# Correctness check
485484
query IT
@@ -491,6 +490,40 @@ ORDER BY l.id LIMIT 2;
491490
2 left2
492491
4 left4
493492

493+
# A parent filter must remain when only an anti join's non-output side accepts
494+
# pushdown; otherwise filtering that side creates incorrect anti-join rows.
495+
statement ok
496+
SET datafusion.optimizer.max_passes = 0;
497+
498+
statement ok
499+
SET datafusion.optimizer.join_reordering = false;
500+
501+
statement ok
502+
SET datafusion.execution.parquet.pushdown_filters = true;
503+
504+
query I
505+
SELECT count(*)
506+
FROM join_left l LEFT ANTI JOIN right_parquet r USING (id)
507+
WHERE false;
508+
----
509+
0
510+
511+
query I
512+
SELECT count(*)
513+
FROM right_parquet r RIGHT ANTI JOIN join_left l USING (id)
514+
WHERE false;
515+
----
516+
0
517+
518+
statement ok
519+
RESET datafusion.optimizer.max_passes;
520+
521+
statement ok
522+
RESET datafusion.optimizer.join_reordering;
523+
524+
statement ok
525+
RESET datafusion.execution.parquet.pushdown_filters;
526+
494527
# Test 3: Test independent control
495528

496529
# Disable TopK, keep Join enabled

0 commit comments

Comments
 (0)