Skip to content

Commit 155f789

Browse files
committed
Add support to SMJ for producing dynamic filters.
1 parent 32f8ef7 commit 155f789

18 files changed

Lines changed: 1471 additions & 86 deletions

File tree

‎datafusion/core/tests/fuzz_cases/smj_filter_pushdown.rs‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -39,7 +39,7 @@ use datafusion_datasource_parquet::ParquetFormat;
3939
use datafusion_execution::object_store::ObjectStoreUrl;
4040
use object_store::memory::InMemory;
4141
use object_store::path::Path;
42-
use object_store::{ObjectStore, PutPayload};
42+
use object_store::{ObjectStore, ObjectStoreExt, PutPayload};
4343
use parquet::arrow::ArrowWriter;
4444

4545
fn left_schema() -> Arc<Schema> {
@@ -270,7 +270,7 @@ async fn test_smj_topk_limit_exceeds_rows() {
270270
#[tokio::test]
271271
async fn test_smj_left_join_correctness() {
272272
// Left join should produce correct results with or without dynamic filters.
273-
// No DynamicFilter is pushed through SMJ for non-Inner joins (conservative).
273+
// DynamicFilter is pushed through SMJ for any join type that preserves the filtered side.
274274
run_and_compare(
275275
"SELECT l.id, l.name, r.dept \
276276
FROM left_t l LEFT JOIN right_t r ON l.id = r.id \

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

Lines changed: 81 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -486,6 +486,7 @@ fn smj_join(
486486
/// - Left-side filters are pushed down to the left child
487487
/// - Right-side filters are pushed down to the right child
488488
/// - Cross-side filters (referencing both sides) remain as FilterExec
489+
///
489490
/// Also tests that non-Inner join types (Left) reject pushdown.
490491
#[test]
491492
fn test_static_filter_pushdown_through_sort_merge_join() {
@@ -582,7 +583,7 @@ fn test_static_filter_pushdown_through_sort_merge_join() {
582583
// The two adjacent FilterExec nodes get collapsed into a single combined predicate.
583584
insta::assert_snapshot!(
584585
OptimizationTest::new(plan, FilterPushdown::new(), true),
585-
@r"
586+
@"
586587
OptimizationTest:
587588
input:
588589
- FilterExec: e@4 = ba
@@ -592,9 +593,9 @@ fn test_static_filter_pushdown_through_sort_merge_join() {
592593
- DataSourceExec: file_groups={1 group: [[test.parquet]]}, projection=[d, e, f], file_type=test, pushdown_supported=true
593594
output:
594595
Ok:
595-
- FilterExec: e@4 = ba AND a@0 = aa
596+
- FilterExec: e@4 = ba
596597
- SortMergeJoinExec: join_type=Left, on=[(a@0, d@0)]
597-
- DataSourceExec: file_groups={1 group: [[test.parquet]]}, projection=[a, b, c], file_type=test, pushdown_supported=true
598+
- DataSourceExec: file_groups={1 group: [[test.parquet]]}, projection=[a, b, c], file_type=test, pushdown_supported=true, predicate=a@0 = aa
598599
- DataSourceExec: file_groups={1 group: [[test.parquet]]}, projection=[d, e, f], file_type=test, pushdown_supported=true
599600
"
600601
);
@@ -671,11 +672,11 @@ async fn test_dynamic_filter_pushdown_through_sort_merge_join_with_topk() {
671672
// The TopK dynamic filter should pass through the SMJ to the right scan
672673
insta::assert_snapshot!(
673674
format_plan_for_test(&plan),
674-
@r"
675+
@"
675676
- SortExec: TopK(fetch=2), expr=[e@4 ASC], preserve_partitioning=[false]
676-
- SortMergeJoinExec: join_type=Inner, on=[(a@0, d@0)]
677-
- DataSourceExec: file_groups={1 group: [[test.parquet]]}, projection=[a, b, c], file_type=test, pushdown_supported=true
678-
- DataSourceExec: file_groups={1 group: [[test.parquet]]}, projection=[d, e, f], file_type=test, pushdown_supported=true, predicate=DynamicFilter [ empty ]
677+
- SortMergeJoinExec: join_type=Inner, on=[(a@0, d@0)], left_dynamic_filter=DynamicFilter [ empty ], right_dynamic_filter=DynamicFilter [ empty ]
678+
- DataSourceExec: file_groups={1 group: [[test.parquet]]}, projection=[a, b, c], file_type=test, pushdown_supported=true, predicate=DynamicFilter [ empty ]
679+
- DataSourceExec: file_groups={1 group: [[test.parquet]]}, projection=[d, e, f], file_type=test, pushdown_supported=true, predicate=DynamicFilter [ empty ] AND DynamicFilter [ empty ]
679680
"
680681
);
681682

@@ -694,19 +695,72 @@ async fn test_dynamic_filter_pushdown_through_sort_merge_join_with_topk() {
694695
// After execution, the dynamic filter should be populated with actual bounds
695696
insta::assert_snapshot!(
696697
format_plan_for_test(&plan),
697-
@r"
698+
@"
698699
- SortExec: TopK(fetch=2), expr=[e@4 ASC], preserve_partitioning=[false], filter=[e@4 IS NULL OR e@4 < bb]
699-
- SortMergeJoinExec: join_type=Inner, on=[(a@0, d@0)]
700-
- DataSourceExec: file_groups={1 group: [[test.parquet]]}, projection=[a, b, c], file_type=test, pushdown_supported=true
701-
- DataSourceExec: file_groups={1 group: [[test.parquet]]}, projection=[d, e, f], file_type=test, pushdown_supported=true, predicate=DynamicFilter [ e@1 IS NULL OR e@1 < bb ]
700+
- SortMergeJoinExec: join_type=Inner, on=[(a@0, d@0)], left_dynamic_filter=DynamicFilter [ false ], right_dynamic_filter=DynamicFilter [ false ]
701+
- DataSourceExec: file_groups={1 group: [[test.parquet]]}, projection=[a, b, c], file_type=test, pushdown_supported=true, predicate=DynamicFilter [ false ]
702+
- DataSourceExec: file_groups={1 group: [[test.parquet]]}, projection=[d, e, f], file_type=test, pushdown_supported=true, predicate=DynamicFilter [ false ] AND DynamicFilter [ e@1 IS NULL OR e@1 < bb ]
702703
"
703704
);
704705
}
705706

706-
/// Tests filter pushdown for all non-Inner join types to ensure they correctly
707-
/// reject pushdown (conservative behavior).
707+
/// Tests filter pushdown for Full join to ensure it correctly rejects pushdown.
708708
#[test]
709-
fn test_smj_filter_pushdown_non_inner_unsupported() {
709+
fn test_smj_filter_pushdown_unsupported() {
710+
use datafusion_common::JoinType;
711+
712+
let left_schema = Arc::new(Schema::new(vec![
713+
Field::new("a", DataType::Utf8, false),
714+
Field::new("b", DataType::Utf8, false),
715+
]));
716+
let right_schema = Arc::new(Schema::new(vec![
717+
Field::new("c", DataType::Utf8, false),
718+
Field::new("d", DataType::Utf8, false),
719+
]));
720+
721+
{
722+
let join_type = JoinType::Full;
723+
let left_scan = TestScanBuilder::new(Arc::clone(&left_schema))
724+
.with_support(true)
725+
.build();
726+
let right_scan = TestScanBuilder::new(Arc::clone(&right_schema))
727+
.with_support(true)
728+
.build();
729+
let on = vec![(
730+
col("a", &left_schema).unwrap(),
731+
col("c", &right_schema).unwrap(),
732+
)];
733+
let join = smj_join(left_scan, right_scan, on, join_type);
734+
735+
let join_schema = join.schema();
736+
let filter_pred = col_lit_predicate("a", "x", &join_schema);
737+
let plan = Arc::new(FilterExec::try_new(filter_pred, join).unwrap())
738+
as Arc<dyn ExecutionPlan>;
739+
740+
let result = OptimizationTest::new(plan, FilterPushdown::new(), true);
741+
let full_output = format!("{result}");
742+
let output = full_output
743+
.split("output:")
744+
.nth(1)
745+
.expect("Expected output section in result");
746+
747+
// The filter should remain as a FilterExec (not pushed into the scan)
748+
assert!(
749+
output.contains("FilterExec"),
750+
"Expected FilterExec to remain for {join_type:?} join, got:\n{full_output}"
751+
);
752+
// The scan should NOT have a predicate
753+
assert!(
754+
!output.contains("predicate="),
755+
"Expected no predicate pushdown for {join_type:?} join, got:\n{full_output}"
756+
);
757+
}
758+
}
759+
760+
/// Tests filter pushdown for other non-Inner join types to ensure they correctly
761+
/// support pushdown for their preserved side.
762+
#[test]
763+
fn test_smj_filter_pushdown_supported() {
710764
use datafusion_common::JoinType;
711765

712766
let left_schema = Arc::new(Schema::new(vec![
@@ -722,7 +776,6 @@ fn test_smj_filter_pushdown_non_inner_unsupported() {
722776
for join_type in [
723777
JoinType::Left,
724778
JoinType::Right,
725-
JoinType::Full,
726779
JoinType::LeftSemi,
727780
JoinType::LeftAnti,
728781
JoinType::RightSemi,
@@ -744,24 +797,29 @@ fn test_smj_filter_pushdown_non_inner_unsupported() {
744797
// Pick a column from the join output; for semi/anti joins only
745798
// one side's columns are present
746799
let filter_col = match join_type {
747-
JoinType::RightSemi | JoinType::RightAnti => "c",
800+
JoinType::RightSemi | JoinType::RightAnti | JoinType::Right => "c",
748801
_ => "a",
749802
};
750803
let filter_pred = col_lit_predicate(filter_col, "x", &join_schema);
751804
let plan = Arc::new(FilterExec::try_new(filter_pred, join).unwrap())
752805
as Arc<dyn ExecutionPlan>;
753806

754807
let result = OptimizationTest::new(plan, FilterPushdown::new(), true);
755-
let output = format!("{result}");
756-
// The filter should remain as a FilterExec (not pushed into the scan)
808+
let full_output = format!("{result}");
809+
let output = full_output
810+
.split("output:")
811+
.nth(1)
812+
.expect("Expected output section in result");
813+
814+
// The filter should NOT remain as a FilterExec (pushed into the scan)
757815
assert!(
758-
output.contains("FilterExec"),
759-
"Expected FilterExec to remain for {join_type:?} join, got:\n{output}"
816+
!output.contains("FilterExec"),
817+
"Expected FilterExec to be pushed for {join_type:?} join, got:\n{full_output}"
760818
);
761-
// The scan should NOT have a predicate
819+
// The scan should HAVE a predicate
762820
assert!(
763-
!output.contains("predicate="),
764-
"Expected no predicate pushdown for {join_type:?} join, got:\n{output}"
821+
output.contains("predicate="),
822+
"Expected predicate pushdown for {join_type:?} join, got:\n{full_output}"
765823
);
766824
}
767825
}

‎datafusion/physical-plan/src/coalesce_batches.rs‎

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -277,7 +277,13 @@ impl ExecutionPlan for CoalesceBatchesExec {
277277
child_pushdown_result: ChildPushdownResult,
278278
_config: &ConfigOptions,
279279
) -> Result<FilterPushdownPropagation<Arc<dyn ExecutionPlan>>> {
280-
Ok(FilterPushdownPropagation::if_all(child_pushdown_result))
280+
let mut result = FilterPushdownPropagation::if_all(child_pushdown_result);
281+
if let Some(updated_child) = result.updated_node {
282+
let mut new_self = self.clone();
283+
new_self.input = updated_child;
284+
result.updated_node = Some(Arc::new(new_self) as _);
285+
}
286+
Ok(result)
281287
}
282288

283289
fn try_pushdown_sort(

‎datafusion/physical-plan/src/coop.rs‎

Lines changed: 6 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -350,7 +350,12 @@ impl ExecutionPlan for CooperativeExec {
350350
child_pushdown_result: ChildPushdownResult,
351351
_config: &ConfigOptions,
352352
) -> Result<FilterPushdownPropagation<Arc<dyn ExecutionPlan>>> {
353-
Ok(FilterPushdownPropagation::if_all(child_pushdown_result))
353+
let mut result = FilterPushdownPropagation::if_all(child_pushdown_result);
354+
if let Some(updated_child) = result.updated_node {
355+
result.updated_node =
356+
Some(Arc::new(CooperativeExec::new(updated_child)) as _);
357+
}
358+
Ok(result)
354359
}
355360

356361
fn try_pushdown_sort(

‎datafusion/physical-plan/src/filter.rs‎

Lines changed: 8 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -655,8 +655,14 @@ impl ExecutionPlan for FilterExec {
655655
child_pushdown_result: ChildPushdownResult,
656656
_config: &ConfigOptions,
657657
) -> Result<FilterPushdownPropagation<Arc<dyn ExecutionPlan>>> {
658-
if phase != FilterPushdownPhase::Pre {
659-
return Ok(FilterPushdownPropagation::if_all(child_pushdown_result));
658+
if !matches!(phase, FilterPushdownPhase::Pre) {
659+
let mut result = FilterPushdownPropagation::if_all(child_pushdown_result);
660+
if let Some(updated_child) = result.updated_node {
661+
let mut new_self = self.clone();
662+
new_self.input = updated_child;
663+
result.updated_node = Some(Arc::new(new_self) as _);
664+
}
665+
return Ok(result);
660666
}
661667
// We absorb any parent filters that were not handled by our children
662668
let mut unsupported_parent_filters: Vec<Arc<dyn PhysicalExpr>> =

‎datafusion/physical-plan/src/filter_pushdown.rs‎

Lines changed: 7 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -444,13 +444,15 @@ impl ChildFilterDescription {
444444
})
445445
}
446446

447-
/// Mark all parent filters as unsupported for this child.
447+
/// Create a child filter description where all parent filters are marked as unsupported,
448+
/// and no self filters are pushed down.
448449
pub fn all_unsupported(parent_filters: &[Arc<dyn PhysicalExpr>]) -> Self {
450+
let parent_filters = parent_filters
451+
.iter()
452+
.map(|f| PushedDownPredicate::unsupported(Arc::clone(f)))
453+
.collect();
449454
Self {
450-
parent_filters: parent_filters
451-
.iter()
452-
.map(|f| PushedDownPredicate::unsupported(Arc::clone(f)))
453-
.collect(),
455+
parent_filters,
454456
self_filters: vec![],
455457
}
456458
}

‎datafusion/physical-plan/src/joins/sort_merge_join/bitwise_stream.rs‎

Lines changed: 69 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -126,6 +126,7 @@ use std::sync::Arc;
126126
use std::task::{Context, Poll};
127127

128128
use crate::RecordBatchStream;
129+
use crate::joins::sort_merge_join::shared_bounds::SharedSortMergeBoundsAccumulator;
129130
use crate::joins::utils::{JoinFilter, compare_join_arrays};
130131
use crate::metrics::{
131132
BaselineMetrics, Count, ExecutionPlanMetricsSet, Gauge, MetricBuilder,
@@ -320,6 +321,17 @@ pub(crate) struct BitwiseSortMergeJoinStream {
320321
baseline_metrics: BaselineMetrics,
321322
peak_mem_used: Gauge,
322323

324+
// ========================================================================
325+
// DYNAMIC FILTER FIELDS:
326+
// These fields manage dynamic filter pushdown.
327+
// ========================================================================
328+
/// Dynamic filter for the streamed side
329+
pub streamed_dynamic_filter: Option<Arc<SharedSortMergeBoundsAccumulator>>,
330+
/// Dynamic filter for the buffered side
331+
pub buffered_dynamic_filter: Option<Arc<SharedSortMergeBoundsAccumulator>>,
332+
/// Partition ID of this stream
333+
pub partition: usize,
334+
323335
// Memory / spill — only the inner key buffer is tracked via reservation,
324336
// matching existing SMJ (which tracks only the buffered side). The outer
325337
// batch is a single batch at a time and cannot be spilled.
@@ -355,6 +367,8 @@ impl BitwiseSortMergeJoinStream {
355367
reservation: MemoryReservation,
356368
spill_manager: SpillManager,
357369
runtime_env: Arc<datafusion_execution::runtime_env::RuntimeEnv>,
370+
streamed_dynamic_filter: Option<Arc<SharedSortMergeBoundsAccumulator>>,
371+
buffered_dynamic_filter: Option<Arc<SharedSortMergeBoundsAccumulator>>,
358372
) -> Result<Self> {
359373
debug_assert!(
360374
matches!(
@@ -409,6 +423,9 @@ impl BitwiseSortMergeJoinStream {
409423
input_rows,
410424
baseline_metrics,
411425
peak_mem_used,
426+
streamed_dynamic_filter,
427+
buffered_dynamic_filter,
428+
partition,
412429
reservation,
413430
spill_manager,
414431
runtime_env,
@@ -454,8 +471,23 @@ impl BitwiseSortMergeJoinStream {
454471
/// Poll for the next outer batch. Returns true if a batch was loaded.
455472
fn poll_next_outer_batch(&mut self, cx: &mut Context<'_>) -> Poll<Result<bool>> {
456473
loop {
474+
// Report last join key before pulling next batch
475+
if let Some(accumulator) = &self.buffered_dynamic_filter
476+
&& let Some(batch) = &self.outer_batch
477+
&& let Some(key) = self.outer_key_arrays.first().and_then(|arr| {
478+
ScalarValue::try_from_array(arr, batch.num_rows() - 1).ok()
479+
})
480+
{
481+
accumulator.report_head(self.partition, key)?;
482+
}
483+
457484
match ready!(self.outer.poll_next_unpin(cx)) {
458-
None => return Poll::Ready(Ok(false)),
485+
None => {
486+
if let Some(accumulator) = &self.buffered_dynamic_filter {
487+
accumulator.mark_exhausted(self.partition)?;
488+
}
489+
return Poll::Ready(Ok(false));
490+
}
459491
Some(Err(e)) => return Poll::Ready(Err(e)),
460492
Some(Ok(batch)) => {
461493
let batch_num_rows = batch.num_rows();
@@ -465,6 +497,16 @@ impl BitwiseSortMergeJoinStream {
465497
continue;
466498
}
467499
let keys = evaluate_join_keys(&batch, &self.on_outer)?;
500+
501+
// Report first join key to the BUFFERED side's dynamic filter
502+
if let Some(accumulator) = &self.buffered_dynamic_filter
503+
&& let Some(key) = keys
504+
.first()
505+
.and_then(|arr| ScalarValue::try_from_array(arr, 0).ok())
506+
{
507+
accumulator.report_head(self.partition, key)?;
508+
}
509+
468510
self.outer_batch = Some(batch);
469511
self.outer_offset = 0;
470512
self.outer_key_arrays = keys;
@@ -480,8 +522,23 @@ impl BitwiseSortMergeJoinStream {
480522
/// Poll for the next inner batch. Returns true if a batch was loaded.
481523
fn poll_next_inner_batch(&mut self, cx: &mut Context<'_>) -> Poll<Result<bool>> {
482524
loop {
525+
// Report last join key before pulling next batch
526+
if let Some(accumulator) = &self.streamed_dynamic_filter
527+
&& let Some(batch) = &self.inner_batch
528+
&& let Some(key) = self.inner_key_arrays.first().and_then(|arr| {
529+
ScalarValue::try_from_array(arr, batch.num_rows() - 1).ok()
530+
})
531+
{
532+
accumulator.report_head(self.partition, key)?;
533+
}
534+
483535
match ready!(self.inner.poll_next_unpin(cx)) {
484-
None => return Poll::Ready(Ok(false)),
536+
None => {
537+
if let Some(accumulator) = &self.streamed_dynamic_filter {
538+
accumulator.mark_exhausted(self.partition)?;
539+
}
540+
return Poll::Ready(Ok(false));
541+
}
485542
Some(Err(e)) => return Poll::Ready(Err(e)),
486543
Some(Ok(batch)) => {
487544
let batch_num_rows = batch.num_rows();
@@ -491,6 +548,16 @@ impl BitwiseSortMergeJoinStream {
491548
continue;
492549
}
493550
let keys = evaluate_join_keys(&batch, &self.on_inner)?;
551+
552+
// Report first join key to the STREAMED side's dynamic filter
553+
if let Some(accumulator) = &self.streamed_dynamic_filter
554+
&& let Some(key) = keys
555+
.first()
556+
.and_then(|arr| ScalarValue::try_from_array(arr, 0).ok())
557+
{
558+
accumulator.report_head(self.partition, key)?;
559+
}
560+
494561
self.inner_batch = Some(batch);
495562
self.inner_offset = 0;
496563
self.inner_key_arrays = keys;

0 commit comments

Comments
 (0)