Skip to content

Commit a3f0f93

Browse files
authored
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
1 parent 17694ac commit a3f0f93

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
@@ -1506,10 +1506,8 @@ fn test_hashjoin_parent_filter_pushdown_mark_join() {
15061506
);
15071507
}
15081508

1509-
/// Test that filters on join key columns are pushed to both sides of semi/anti joins.
1510-
/// For LeftSemi/LeftAnti, the output only contains left columns, but filters on
1511-
/// join key columns can also be pushed to the right (non-preserved) side because
1512-
/// the equijoin condition guarantees the key values match.
1509+
/// Semi-join key filters can be pushed to both sides, but anti-join filters must
1510+
/// only rely on the output side to preserve their semantics.
15131511
#[test]
15141512
fn test_hashjoin_parent_filter_pushdown_semi_anti_join() {
15151513
use datafusion_common::JoinType;
@@ -1539,8 +1537,8 @@ fn test_hashjoin_parent_filter_pushdown_semi_anti_join() {
15391537
let join = Arc::new(
15401538
HashJoinExec::try_new(
15411539
left_scan,
1542-
right_scan,
1543-
on,
1540+
Arc::clone(&right_scan),
1541+
on.clone(),
15441542
None,
15451543
&JoinType::LeftSemi,
15461544
None,
@@ -1579,6 +1577,24 @@ fn test_hashjoin_parent_filter_pushdown_semi_anti_join() {
15791577
- DataSourceExec: file_groups={1 group: [[test.parquet]]}, projection=[k, w], file_type=test, pushdown_supported=true, predicate=k@0 = x
15801578
"
15811579
);
1580+
1581+
let join = Arc::new(
1582+
HashJoinExec::try_new(
1583+
TestScanBuilder::new(Arc::clone(&left_schema)).build(),
1584+
right_scan,
1585+
on,
1586+
None,
1587+
&JoinType::LeftAnti,
1588+
None,
1589+
PartitionMode::Partitioned,
1590+
datafusion_common::NullEquality::NullEqualsNothing,
1591+
false,
1592+
)
1593+
.unwrap(),
1594+
);
1595+
let predicate = Arc::new(Literal::new(ScalarValue::Boolean(Some(false))));
1596+
let plan = Arc::new(FilterExec::try_new(predicate, join).unwrap());
1597+
assert_parent_filter_remains(plan);
15821598
}
15831599

15841600
#[test]
@@ -1817,13 +1833,13 @@ fn col_lit_predicate(
18171833
))
18181834
}
18191835

1820-
fn assert_parent_filter_remains_above_aggregate(plan: Arc<dyn ExecutionPlan>) {
1836+
fn assert_parent_filter_remains(plan: Arc<dyn ExecutionPlan>) {
18211837
let mut config = ConfigOptions::default();
18221838
config.execution.parquet.pushdown_filters = true;
18231839
let optimized = FilterPushdown::new().optimize(plan, &config).unwrap();
18241840
assert!(
18251841
optimized.downcast_ref::<FilterExec>().is_some(),
1826-
"parent filter must remain above aggregate"
1842+
"parent filter must remain"
18271843
);
18281844
}
18291845

@@ -2152,7 +2168,7 @@ fn test_no_pushdown_constant_false_through_global_aggregate() {
21522168
let predicate = Arc::new(Literal::new(ScalarValue::Boolean(Some(false))));
21532169
let plan = Arc::new(FilterExec::try_new(predicate, aggregate).unwrap());
21542170

2155-
assert_parent_filter_remains_above_aggregate(plan);
2171+
assert_parent_filter_remains(plan);
21562172
}
21572173

21582174
#[test]
@@ -2189,7 +2205,7 @@ fn test_no_pushdown_constant_false_through_empty_grouping_set() {
21892205
let predicate = Arc::new(Literal::new(ScalarValue::Boolean(Some(false))));
21902206
let plan = Arc::new(FilterExec::try_new(predicate, aggregate).unwrap());
21912207

2192-
assert_parent_filter_remains_above_aggregate(plan);
2208+
assert_parent_filter_remains(plan);
21932209
}
21942210

21952211
#[test]

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

Lines changed: 13 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -1645,14 +1645,11 @@ impl ExecutionPlan for HashJoinExec {
16451645
};
16461646
});
16471647

1648-
// For semi/anti joins, the non-preserved side's columns are not in the
1649-
// output, but filters on join key columns can still be pushed there.
1650-
// We find output columns that are join keys on the preserved side and
1651-
// add their output indices to the non-preserved side's allowed set.
1652-
// The name-based remap in FilterRemapper will then match them to the
1653-
// corresponding column in the non-preserved child's schema.
1648+
// For semi joins, filters on output join keys can also be pushed to the
1649+
// non-output side: every emitted row has an equal key there. This is not
1650+
// true for anti joins, whose emitted rows have no match.
16541651
match self.join_type {
1655-
JoinType::LeftSemi | JoinType::LeftAnti => {
1652+
JoinType::LeftSemi => {
16561653
let left_key_indices: HashSet<usize> = self
16571654
.on
16581655
.iter()
@@ -1666,7 +1663,7 @@ impl ExecutionPlan for HashJoinExec {
16661663
}
16671664
}
16681665
}
1669-
JoinType::RightSemi | JoinType::RightAnti => {
1666+
JoinType::RightSemi => {
16701667
let right_key_indices: HashSet<usize> = self
16711668
.on
16721669
.iter()
@@ -1969,21 +1966,18 @@ impl HashJoinExec {
19691966
/// Determines which sides of a join are "preserved" for filter pushdown.
19701967
///
19711968
/// A preserved side means filters on that side's columns can be safely pushed
1972-
/// below the join. This mirrors the logic in the logical optimizer's
1973-
/// `lr_is_preserved` in `datafusion/optimizer/src/push_down_filter.rs`.
1969+
/// below the join. This mostly mirrors the logical optimizer's `lr_is_preserved`;
1970+
/// semi joins additionally allow join-key filters on the non-output side.
19741971
fn lr_is_preserved(join_type: JoinType) -> (bool, bool) {
19751972
match join_type {
19761973
JoinType::Inner => (true, true),
19771974
JoinType::Left => (true, false),
19781975
JoinType::Right => (false, true),
19791976
JoinType::Full => (false, false),
1980-
// Filters in semi/anti joins are either on the preserved side, or on join keys,
1981-
// as all output columns come from the preserved side. Join key filters can be
1982-
// safely pushed down into the other side.
1983-
JoinType::LeftSemi | JoinType::LeftAnti => (true, true),
1984-
JoinType::RightSemi | JoinType::RightAnti => (true, true),
1985-
JoinType::LeftMark => (true, false),
1986-
JoinType::RightMark => (false, true),
1977+
// Callers restrict the non-output side of semi joins to join-key columns.
1978+
JoinType::LeftSemi | JoinType::RightSemi => (true, true),
1979+
JoinType::LeftAnti | JoinType::LeftMark => (true, false),
1980+
JoinType::RightAnti | JoinType::RightMark => (false, true),
19871981
}
19881982
}
19891983

@@ -6848,10 +6842,10 @@ mod tests {
68486842
assert_eq!(lr_is_preserved(JoinType::Right), (false, true));
68496843
assert_eq!(lr_is_preserved(JoinType::Full), (false, false));
68506844
assert_eq!(lr_is_preserved(JoinType::LeftSemi), (true, true));
6851-
assert_eq!(lr_is_preserved(JoinType::LeftAnti), (true, true));
6845+
assert_eq!(lr_is_preserved(JoinType::LeftAnti), (true, false));
68526846
assert_eq!(lr_is_preserved(JoinType::LeftMark), (true, false));
68536847
assert_eq!(lr_is_preserved(JoinType::RightSemi), (true, true));
6854-
assert_eq!(lr_is_preserved(JoinType::RightAnti), (true, true));
6848+
assert_eq!(lr_is_preserved(JoinType::RightAnti), (false, true));
68556849
assert_eq!(lr_is_preserved(JoinType::RightMark), (false, true));
68566850
}
68576851

‎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)], null_aware
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 ], dynamic_rg_pruning=eligible
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 ], dynamic_rg_pruning=eligible
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
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)