Skip to content

Commit 872df4d

Browse files
authored
fix: keep join filter columns when pushing a projection below SortMergeJoinExec (#24593)
## Rationale for this change A sort merge join with a non-equi filter panics (`index out of bounds` in `get_filter_columns`) when the query does not select a column the filter references: ```sql SET datafusion.optimizer.prefer_hash_join = false; SET datafusion.execution.target_partitions = 2; CREATE TABLE l (k VARCHAR, a INT, b INT, c INT) AS VALUES ('x', 1, 1, 1), ('y', 2, 2, 2), ('x', 3, 3, 3); CREATE TABLE r (k VARCHAR, a INT, b INT, c INT) AS VALUES ('x', 1, 1, 1), ('y', 2, 2, 2), ('z', 3, 3, 3); SELECT l.c, l.k, l.b, r.k, r.b, r.a FROM l RIGHT JOIN r ON l.k = r.k AND l.c >= r.c; ``` ``` thread 'tokio-rt-worker' panicked at datafusion/physical-plan/src/joins/sort_merge_join/filter.rs:169:34: index out of bounds: the len is 3 but the index is 3 ``` The projection pushdown added in #24517 pushes the projection into the join's children but passes `self.filter.clone()` through unchanged. The right child no longer produces `c`, but the filter's `ColumnIndex` still points at it. ## What changes are included in this PR? `SortMergeJoinExec::try_swapping_with_projection` now uses the shared `try_pushdown_through_join_with_column_indices` helper, as `HashJoinExec` and `NestedLoopJoinExec` already do. It remaps both the `on` keys and the filter's column indices to the projected children, and declines the pushdown — embedding the projection in the join instead — when the filter needs a column the projection drops. One behavioral side effect: projections containing expressions (e.g. `length(w.p)`) are now also embedded into the join, so the join only emits the columns they reference. This matches the existing behavior of the other join operators; the affected `EXPLAIN ANALYZE` expectations in `sort_merge_join_spill.slt` are updated accordingly (`projection=[...]` on the `SortMergeJoinExec` line). ## Are these changes tested? Yes. A regression test in `joins.slt` covers the panicking case (explain + results). Existing SMJ unit tests, projection tests, proto round-trip tests, and `joins.slt` / `range_partitioning.slt` / `sort_merge_join_spill.slt` pass. ## Are there any user-facing changes? No API changes. Plans for `SortMergeJoinExec` under an expression projection now show `projection=[...]` on the join node.
1 parent e1eaeb1 commit 872df4d

4 files changed

Lines changed: 131 additions & 83 deletions

File tree

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

Lines changed: 37 additions & 67 deletions
Original file line numberDiff line numberDiff line change
@@ -34,9 +34,8 @@ use crate::joins::utils::{
3434
};
3535
use crate::metrics::{ExecutionPlanMetricsSet, MetricsSet, SpillMetrics};
3636
use crate::projection::{
37-
EmbeddedProjection, ProjectionExec, join_allows_pushdown, join_table_borders,
38-
new_join_children, physical_to_column_exprs, try_embed_projection,
39-
update_join_filter, update_join_on,
37+
EmbeddedProjection, JoinData, ProjectionExec, try_embed_projection,
38+
try_pushdown_through_join_with_column_indices,
4039
};
4140
use crate::spill::spill_manager::SpillManager;
4241
use crate::statistics::{ChildStats, StatisticsArgs};
@@ -707,82 +706,53 @@ impl ExecutionPlan for SortMergeJoinExec {
707706
}))
708707
}
709708

710-
/// Tries to swap the projection with its input [`SortMergeJoinExec`]. If it can be done,
711-
/// it returns the new swapped version having the [`SortMergeJoinExec`] as the top plan.
712-
/// Otherwise, it returns None.
709+
/// Tries to push `projection` down through this join. If possible, returns a
710+
/// new [`SortMergeJoinExec`] whose children are the projected inputs. Otherwise
711+
/// the join applies the projection itself (see [`EmbeddedProjection`]).
713712
fn try_swapping_with_projection(
714713
&self,
715714
projection: &ProjectionExec,
716715
) -> Result<Option<Arc<dyn ExecutionPlan>>> {
717716
if self.projection.is_some() {
718717
return Ok(None);
719718
}
720-
// Convert projected PhysicalExpr's to columns. If not possible, we cannot proceed.
721-
let Some(projection_as_columns) = physical_to_column_exprs(projection.expr())
722-
else {
723-
return Ok(None);
724-
};
725719

726-
let (far_right_left_col_ind, far_left_right_col_ind) = join_table_borders(
727-
self.left().schema().fields().len(),
728-
&projection_as_columns,
720+
let schema = self.schema();
721+
let (_, column_indices) = build_join_schema(
722+
&self.left().schema(),
723+
&self.right().schema(),
724+
&self.join_type,
729725
);
730726

731-
// Pushing into the children needs each side's columns to stay together, which
732-
// an arbitrary projection does not. The join can apply that one itself.
733-
if !join_allows_pushdown(
734-
&projection_as_columns,
735-
&self.schema(),
736-
far_right_left_col_ind,
737-
far_left_right_col_ind,
738-
) {
739-
return try_embed_projection(projection, self);
740-
}
741-
742-
let left_field_size = self.left().schema().fields().len();
743-
let left_projection = &projection_as_columns[0..=far_right_left_col_ind as usize];
744-
let right_projection = &projection_as_columns[far_left_right_col_ind as usize..];
745-
746-
let Some(new_on) = update_join_on(
747-
left_projection,
748-
right_projection,
727+
// Remaps the join keys and the filter's column indices to the
728+
// projected children, and declines the pushdown if the projection
729+
// drops a column the filter needs.
730+
if let Some(JoinData {
731+
projected_left_child,
732+
projected_right_child,
733+
join_filter,
734+
join_on,
735+
}) = try_pushdown_through_join_with_column_indices(
736+
projection,
737+
self.left(),
738+
self.right(),
749739
self.on(),
750-
left_field_size,
751-
) else {
752-
return try_embed_projection(projection, self);
753-
};
754-
755-
let new_filter = if let Some(filter) = self.filter() {
756-
let Some(filter) = update_join_filter(
757-
left_projection,
758-
right_projection,
759-
filter,
760-
left_field_size,
761-
) else {
762-
return try_embed_projection(projection, self);
763-
};
764-
Some(filter)
740+
&schema,
741+
self.filter().as_ref(),
742+
&column_indices,
743+
)? {
744+
Ok(Some(Arc::new(SortMergeJoinExec::try_new(
745+
Arc::new(projected_left_child),
746+
Arc::new(projected_right_child),
747+
join_on,
748+
join_filter,
749+
self.join_type,
750+
self.sort_options.clone(),
751+
self.null_equality,
752+
)?)))
765753
} else {
766-
None
767-
};
768-
769-
let (new_left, new_right) = new_join_children(
770-
&projection_as_columns,
771-
far_right_left_col_ind,
772-
far_left_right_col_ind,
773-
self.children()[0],
774-
self.children()[1],
775-
)?;
776-
777-
Ok(Some(Arc::new(SortMergeJoinExec::try_new(
778-
Arc::new(new_left),
779-
Arc::new(new_right),
780-
new_on,
781-
new_filter,
782-
self.join_type,
783-
self.sort_options.clone(),
784-
self.null_equality,
785-
)?)))
754+
try_embed_projection(projection, self)
755+
}
786756
}
787757

788758
#[cfg(feature = "proto")]

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

Lines changed: 55 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -365,8 +365,16 @@ async fn join_collect_batch_size_equals_two(
365365
fn join_and_projection_for_pushdown(
366366
filter: Option<JoinFilter>,
367367
) -> Result<(Arc<SortMergeJoinExec>, ProjectionExec)> {
368-
let left = build_table(("a1", &vec![1]), ("b1", &vec![2]), ("c1", &vec![3]));
369-
let right = build_table(("a2", &vec![4]), ("b2", &vec![2]), ("c2", &vec![5]));
368+
let left = build_table(
369+
("a1", &vec![1, 2, 3]),
370+
("b1", &vec![4, 5, 5]),
371+
("c1", &vec![7, 8, 9]),
372+
);
373+
let right = build_table(
374+
("a2", &vec![10, 20, 30]),
375+
("b2", &vec![4, 5, 5]),
376+
("c2", &vec![70, 8, 90]),
377+
);
370378
let on = vec![(
371379
Arc::new(Column::new("b1", 1)) as _,
372380
Arc::new(Column::new("b2", 1)) as _,
@@ -406,9 +414,9 @@ fn join_and_projection_for_pushdown(
406414
Ok((join, projection))
407415
}
408416

409-
#[test]
410-
fn projection_pushdown_remaps_filter() -> Result<()> {
411-
let filter = JoinFilter::new(
417+
/// `c1 < c2`, referencing the last column of each child.
418+
fn filter_for_pushdown() -> JoinFilter {
419+
JoinFilter::new(
412420
Arc::new(BinaryExpr::new(
413421
Arc::new(Column::new("c1", 0)),
414422
Operator::Lt,
@@ -428,8 +436,13 @@ fn projection_pushdown_remaps_filter() -> Result<()> {
428436
Field::new("c1", DataType::Int32, false),
429437
Field::new("c2", DataType::Int32, false),
430438
])),
431-
);
432-
let (join, projection) = join_and_projection_for_pushdown(Some(filter))?;
439+
)
440+
}
441+
442+
#[test]
443+
fn projection_pushdown_remaps_filter() -> Result<()> {
444+
let (join, projection) =
445+
join_and_projection_for_pushdown(Some(filter_for_pushdown()))?;
433446

434447
let swapped = join
435448
.try_swapping_with_projection(&projection)?
@@ -458,6 +471,41 @@ fn projection_pushdown_remaps_filter() -> Result<()> {
458471
Ok(())
459472
}
460473

474+
#[tokio::test]
475+
async fn projection_pushdown_remaps_filter_execute() -> Result<()> {
476+
let (join, projection) =
477+
join_and_projection_for_pushdown(Some(filter_for_pushdown()))?;
478+
let expected_schema = projection.schema();
479+
480+
let swapped = join
481+
.try_swapping_with_projection(&projection)?
482+
.expect("projection should be pushed below the join");
483+
assert!(
484+
swapped.downcast_ref::<SortMergeJoinExec>().is_some(),
485+
"projection should not be embedded in the join"
486+
);
487+
assert_eq!(swapped.schema(), expected_schema);
488+
489+
// The pushed-down children keep only `c*` and `b*`, so the filter must run
490+
// against the remapped indices: `c1 < c2` filters out the (8, 8) and (9, 8)
491+
// pairs of the `b1 = b2 = 5` group.
492+
let batches =
493+
common::collect(swapped.execute(0, Arc::new(TaskContext::default()))?).await?;
494+
495+
// The output order is important as SMJ preserves sortedness
496+
assert_snapshot!(batches_to_string(&batches), @r"
497+
+----+----+----+----+
498+
| c1 | b1 | c2 | b2 |
499+
+----+----+----+----+
500+
| 7 | 4 | 70 | 4 |
501+
| 8 | 5 | 90 | 5 |
502+
| 9 | 5 | 90 | 5 |
503+
+----+----+----+----+
504+
");
505+
506+
Ok(())
507+
}
508+
461509
#[test]
462510
fn projection_pushdown_without_filter() -> Result<()> {
463511
let (join, projection) = join_and_projection_for_pushdown(None)?;

‎datafusion/sqllogictest/test_files/joins.slt‎

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2857,6 +2857,36 @@ NULL 1970-01-04T00:00:00 789 ghi 1970-01-04 NULL 789 qwe
28572857
NULL NULL NULL NULL NULL 1970-01-04T00:00:00 0 qwerty
28582858
NULL NULL NULL NULL NULL NULL 100000 abcdefg
28592859

2860+
# Pushing the projection below the sort merge join must not drop a column that
2861+
# the join filter still needs (t2.c2 here). Instead the join applies the
2862+
# projection itself.
2863+
query TT
2864+
explain select t1.c1, t2.c1, t2.c3 from hashjoin_datatype_table_t1 t1 right join hashjoin_datatype_table_t2 t2 on t1.c1 = t2.c1 and t1.c2 < t2.c2
2865+
----
2866+
logical_plan
2867+
01)Projection: t1.c1, t2.c1, t2.c3
2868+
02)--Right Join: t1.c1 = t2.c1 Filter: t1.c2 < t2.c2
2869+
03)----SubqueryAlias: t1
2870+
04)------TableScan: hashjoin_datatype_table_t1 projection=[c1, c2]
2871+
05)----SubqueryAlias: t2
2872+
06)------TableScan: hashjoin_datatype_table_t2 projection=[c1, c2, c3]
2873+
physical_plan
2874+
01)SortMergeJoinExec: join_type=Right, on=[(c1@0, c1@0)], filter=c2@0 < c2@1, projection=[c1@0, c1@2, c3@4]
2875+
02)--SortExec: expr=[c1@0 ASC], preserve_partitioning=[true]
2876+
03)----RepartitionExec: partitioning=Hash([c1@0], 2), input_partitions=1
2877+
04)------DataSourceExec: partitions=1, partition_sizes=[1]
2878+
05)--SortExec: expr=[c1@0 ASC], preserve_partitioning=[true]
2879+
06)----RepartitionExec: partitioning=Hash([c1@0], 2), input_partitions=1
2880+
07)------DataSourceExec: partitions=1, partition_sizes=[1]
2881+
2882+
query DDR rowsort
2883+
select t1.c1, t2.c1, t2.c3 from hashjoin_datatype_table_t1 t1 right join hashjoin_datatype_table_t2 t2 on t1.c1 = t2.c1 and t1.c2 < t2.c2
2884+
----
2885+
NULL 1970-01-02 -123.12
2886+
NULL 1970-01-04 789
2887+
NULL NULL 0
2888+
NULL NULL 100000
2889+
28602890
# Regression test: projection optimization through SortMergeJoinExec must keep
28612891
# JoinFilter columns available when the output projection does not select them.
28622892
statement ok

‎datafusion/sqllogictest/test_files/sort_merge_join_spill.slt‎

Lines changed: 9 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -140,7 +140,7 @@ EXPLAIN ANALYZE
140140
SELECT p.k, w.v, length(w.p) FROM probe p JOIN wide w ON p.k = w.k
141141
----
142142
Plan with Metrics
143-
<slt:ignore>SortMergeJoinExec: join_type=Inner, on=[(k@0, k@0)], metrics=[output_rows=2.00 K,<slt:ignore>spill_count=10, spilled_bytes=<slt:ignore>spilled_rows=2.00 K, peak_mem_used=<slt:ignore>
143+
<slt:ignore>SortMergeJoinExec: join_type=Inner, on=[(k@0, k@0)], projection=[k@0, v@2, p@3], metrics=[output_rows=2.00 K,<slt:ignore>spill_count=10, spilled_bytes=<slt:ignore>spilled_rows=2.00 K, peak_mem_used=<slt:ignore>
144144

145145
query III rowsort
146146
SELECT p.k, w.v, length(w.p) FROM probe p JOIN wide w ON p.k = w.k
@@ -152,7 +152,7 @@ EXPLAIN ANALYZE
152152
SELECT p.k, w.v, length(w.p) FROM probe p LEFT JOIN wide w ON p.k = w.k
153153
----
154154
Plan with Metrics
155-
<slt:ignore>SortMergeJoinExec: join_type=Left, on=[(k@0, k@0)], metrics=[output_rows=2.00 K,<slt:ignore>spill_count=10, spilled_bytes=<slt:ignore>spilled_rows=2.00 K, peak_mem_used=<slt:ignore>
155+
<slt:ignore>SortMergeJoinExec: join_type=Left, on=[(k@0, k@0)], projection=[k@0, v@2, p@3], metrics=[output_rows=2.00 K,<slt:ignore>spill_count=10, spilled_bytes=<slt:ignore>spilled_rows=2.00 K, peak_mem_used=<slt:ignore>
156156

157157
query III rowsort
158158
SELECT p.k, w.v, length(w.p) FROM probe p LEFT JOIN wide w ON p.k = w.k
@@ -164,7 +164,7 @@ EXPLAIN ANALYZE
164164
SELECT p.k, w.v, length(w.p) FROM wide w RIGHT JOIN probe p ON p.k = w.k
165165
----
166166
Plan with Metrics
167-
<slt:ignore>SortMergeJoinExec: join_type=Right, on=[(k@0, k@0)], metrics=[output_rows=2.00 K,<slt:ignore>spill_count=10, spilled_bytes=<slt:ignore>spilled_rows=2.00 K, peak_mem_used=<slt:ignore>
167+
<slt:ignore>SortMergeJoinExec: join_type=Right, on=[(k@0, k@0)], projection=[k@3, v@1, p@2], metrics=[output_rows=2.00 K,<slt:ignore>spill_count=10, spilled_bytes=<slt:ignore>spilled_rows=2.00 K, peak_mem_used=<slt:ignore>
168168

169169
query III rowsort
170170
SELECT p.k, w.v, length(w.p) FROM wide w RIGHT JOIN probe p ON p.k = w.k
@@ -176,7 +176,7 @@ EXPLAIN ANALYZE
176176
SELECT p.k, w.v, length(w.p) FROM probe p FULL JOIN wide w ON p.k = w.k
177177
----
178178
Plan with Metrics
179-
<slt:ignore>SortMergeJoinExec: join_type=Full, on=[(k@0, k@0)], metrics=[output_rows=2.00 K,<slt:ignore>spill_count=10, spilled_bytes=<slt:ignore>spilled_rows=2.00 K, peak_mem_used=<slt:ignore>
179+
<slt:ignore>SortMergeJoinExec: join_type=Full, on=[(k@0, k@0)], projection=[k@0, v@2, p@3], metrics=[output_rows=2.00 K,<slt:ignore>spill_count=10, spilled_bytes=<slt:ignore>spilled_rows=2.00 K, peak_mem_used=<slt:ignore>
180180

181181
query III rowsort
182182
SELECT p.k, w.v, length(w.p) FROM probe p FULL JOIN wide w ON p.k = w.k
@@ -192,7 +192,7 @@ SELECT p.k, w.v, length(w.p) FROM probe p
192192
JOIN wide w ON p.k = w.k AND p.x < w.x
193193
----
194194
Plan with Metrics
195-
<slt:ignore>SortMergeJoinExec: join_type=Inner, on=[(k@0, k@0)], filter=x@0 < x@1, metrics=[output_rows=900,<slt:ignore>spill_count=10, spilled_bytes=<slt:ignore>spilled_rows=2.00 K, peak_mem_used=<slt:ignore>
195+
<slt:ignore>SortMergeJoinExec: join_type=Inner, on=[(k@0, k@0)], filter=x@0 < x@1, projection=[k@0, v@3, p@5], metrics=[output_rows=900,<slt:ignore>spill_count=10, spilled_bytes=<slt:ignore>spilled_rows=2.00 K, peak_mem_used=<slt:ignore>
196196

197197
query III rowsort
198198
SELECT p.k, w.v, length(w.p) FROM probe p
@@ -206,7 +206,7 @@ SELECT p.k, w.v, length(w.p) FROM probe p
206206
LEFT JOIN wide w ON p.k = w.k AND p.x < w.x
207207
----
208208
Plan with Metrics
209-
<slt:ignore>SortMergeJoinExec: join_type=Left, on=[(k@0, k@0)], filter=x@0 < x@1, metrics=[output_rows=902,<slt:ignore>spill_count=10, spilled_bytes=<slt:ignore>spilled_rows=2.00 K, peak_mem_used=<slt:ignore>
209+
<slt:ignore>SortMergeJoinExec: join_type=Left, on=[(k@0, k@0)], filter=x@0 < x@1, projection=[k@0, v@3, p@5], metrics=[output_rows=902,<slt:ignore>spill_count=10, spilled_bytes=<slt:ignore>spilled_rows=2.00 K, peak_mem_used=<slt:ignore>
210210

211211
query III rowsort
212212
SELECT p.k, w.v, length(w.p) FROM probe p
@@ -220,7 +220,7 @@ SELECT p.k, w.v, length(w.p) FROM wide w
220220
RIGHT JOIN probe p ON p.k = w.k AND p.x < w.x
221221
----
222222
Plan with Metrics
223-
<slt:ignore>SortMergeJoinExec: join_type=Right, on=[(k@0, k@0)], filter=x@1 < x@0, metrics=[output_rows=902,<slt:ignore>spill_count=10, spilled_bytes=<slt:ignore>spilled_rows=2.00 K, peak_mem_used=<slt:ignore>
223+
<slt:ignore>SortMergeJoinExec: join_type=Right, on=[(k@0, k@0)], filter=x@1 < x@0, projection=[k@4, v@1, p@3], metrics=[output_rows=902,<slt:ignore>spill_count=10, spilled_bytes=<slt:ignore>spilled_rows=2.00 K, peak_mem_used=<slt:ignore>
224224

225225
query III rowsort
226226
SELECT p.k, w.v, length(w.p) FROM wide w
@@ -234,7 +234,7 @@ SELECT p.k, w.v, length(w.p) FROM probe p
234234
FULL JOIN wide w ON p.k = w.k AND p.x < w.x
235235
----
236236
Plan with Metrics
237-
<slt:ignore>SortMergeJoinExec: join_type=Full, on=[(k@0, k@0)], filter=x@0 < x@1, metrics=[output_rows=2.00 K,<slt:ignore>spill_count=10, spilled_bytes=<slt:ignore>spilled_rows=2.00 K, peak_mem_used=<slt:ignore>
237+
<slt:ignore>SortMergeJoinExec: join_type=Full, on=[(k@0, k@0)], filter=x@0 < x@1, projection=[k@0, v@3, p@5], metrics=[output_rows=2.00 K,<slt:ignore>spill_count=10, spilled_bytes=<slt:ignore>spilled_rows=2.00 K, peak_mem_used=<slt:ignore>
238238

239239
query III rowsort
240240
SELECT p.k, w.v, length(w.p) FROM probe p
@@ -249,7 +249,7 @@ EXPLAIN ANALYZE
249249
SELECT p.k, w.v, length(w.p) FROM probe_nomatch p FULL JOIN wide w ON p.k = w.k
250250
----
251251
Plan with Metrics
252-
<slt:ignore>SortMergeJoinExec: join_type=Full, on=[(k@0, k@0)], metrics=[output_rows=2.00 K,<slt:ignore>spill_count=10, spilled_bytes=<slt:ignore>spilled_rows=2.00 K, peak_mem_used=<slt:ignore>
252+
<slt:ignore>SortMergeJoinExec: join_type=Full, on=[(k@0, k@0)], projection=[k@0, v@2, p@3], metrics=[output_rows=2.00 K,<slt:ignore>spill_count=10, spilled_bytes=<slt:ignore>spilled_rows=2.00 K, peak_mem_used=<slt:ignore>
253253

254254
query III rowsort
255255
SELECT p.k, w.v, length(w.p) FROM probe_nomatch p FULL JOIN wide w ON p.k = w.k

0 commit comments

Comments
 (0)