Skip to content

Commit 92559af

Browse files
authored
fix: end a sort-merge join partition once its streamed side is exhausted, and release its reservations before the final output (apache#25206)
## Which issue does this PR close? - Closes apache#25205. ## Rationale for this change A sort-merge join partition whose streamed side is empty still fetches, sorts and scans its entire buffered side, because the stream loads a key group from the buffered input before comparing anything and merge-scans until both inputs are exhausted. Only a Full join can emit buffered rows without a streamed match, so for every other join type that work produces nothing. On a hash-partitioned join of a large table against a sparse one, most partitions look like this: in the production job that motivated this, 1,371 of 2,000 partitions had an empty streamed side, and the join consumed 6,231,306,982 buffered rows to emit 6,144, taking 456 s for the stage where Spark, whose `SortMergeJoinExec` exits as soon as the streamed side is empty, took 194 s. The symmetric case, an Inner join whose buffered side is exhausted with no key group left, drains and drops the remaining streamed rows for the same reason. ## What changes are included in this PR? The materializing stream (Inner/Left/Right/Full) gets a `finished()` predicate that replaces "both inputs exhausted" as the loop condition: an exhausted streamed side finishes every join but Full, and an exhausted buffered side finishes an Inner join. The first buffered key group is only loaded when the join is not already finished, so an empty streamed partition never polls the buffered input, and the `SortExec` beneath it never runs. `on_children_exhausted` now releases both inputs and every remaining buffered key group right after freezing the pending pairs, so the memory the join reserved is back in the pool before its final batches are emitted rather than when the stream is dropped; without that, a parent operator processing the final batch can fail with `ResourcesExhausted` against a reservation the finished child still holds. The bitwise stream (Semi/Anti/Mark) already returns on an empty outer side; it now also stops draining the outer side for Semi joins once the inner side is exhausted, since the remaining rows cannot be emitted. ## Are these changes tested? New tests in `joins/sort_merge_join/tests.rs`: - `join_empty_streamed_side_never_polls_buffered_side` drives the buffered side with `PanicExec`, so it passes only if that input is never polled, for Inner/Left/LeftSemi/LeftAnti/LeftMark and the mirrored Right/RightSemi/RightAnti. It fails on `main` with the `PanicExec` panic. - `join_full_empty_left_still_emits_buffered_rows` pins that Full still emits the buffered rows. - `join_inner_and_semi_finish_once_buffered_side_is_exhausted` covers the Inner and Semi exit and that Anti still emits the unmatched streamed rows. - `join_left_releases_buffered_reservation_before_final_batch` asserts the pool holds no reservation when the final batch is returned, and `join_chain_reuses_memory_released_by_completed_child` runs a two-join plan under a 2 MB pool with spilling disabled, which fails with `ResourcesExhausted` if the child keeps its reservation. All existing `joins::sort_merge_join` tests pass. ## Are there any user-facing changes? No API or result changes. Sort-merge joins read less input in the cases above, and their `input_rows` metric drops accordingly.
1 parent 448670f commit 92559af

3 files changed

Lines changed: 253 additions & 11 deletions

File tree

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

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1053,6 +1053,11 @@ impl BitwiseSortMergeJoinStream {
10531053
loop {
10541054
self.emit_outer_batch()?;
10551055
self.emit_completed_batches(emitter).await;
1056+
// The remaining outer rows can no longer match. Anti and mark joins still emit
1057+
// them; a semi join is finished without reading them.
1058+
if matches!(self.join_type, JoinType::LeftSemi | JoinType::RightSemi) {
1059+
break;
1060+
}
10561061
if !self.next_outer_batch().await? {
10571062
break;
10581063
}

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

Lines changed: 46 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -616,10 +616,12 @@ impl MaterializingSortMergeJoinStream {
616616
) -> Result<()> {
617617
// 1. Load the first streamed row and the first buffered key group.
618618
self.load_next_streamed_batch().await?;
619-
self.advance_buffered_group().await?;
619+
if !self.finished() {
620+
self.advance_buffered_group().await?;
621+
}
620622

621-
// 2. Merge-scan while either input still has rows.
622-
while !(self.streamed_exhausted && self.buffered_exhausted) {
623+
// 2. Merge-scan while the join can still produce output.
624+
while !self.finished() {
623625
// Flush the deferred-filtering pipeline once a full batch of
624626
// rows accumulated (filtered outer joins output through it).
625627
if self.deferred_filtering
@@ -844,14 +846,41 @@ impl MaterializingSortMergeJoinStream {
844846
}
845847
}
846848

847-
/// Flush everything that remains once both inputs are exhausted.
849+
/// Whether the join can produce no further output. Besides both inputs being exhausted,
850+
/// an exhausted streamed side ends every join but Full, the only one that emits buffered
851+
/// rows without a streamed match, and an exhausted buffered side (which leaves no key
852+
/// group behind) ends an Inner join, which has nothing to match the remaining streamed
853+
/// rows against. Spark's SortMergeJoinExec stops at the same points; an empty streamed
854+
/// partition therefore never polls the buffered side.
855+
fn finished(&self) -> bool {
856+
(self.streamed_exhausted
857+
&& (self.buffered_exhausted || self.join_type != JoinType::Full))
858+
|| (self.buffered_exhausted && self.join_type == JoinType::Inner)
859+
}
860+
861+
/// Drops both inputs and every buffered key group once nothing more can be joined, so the
862+
/// memory they reserve is back in the pool before the final output batches are emitted
863+
/// rather than when the stream is dropped.
864+
fn release_inputs(&mut self) {
865+
while self.pop_front_buffered_batch().is_some() {}
866+
self.streamed_buffered_cmp = None;
867+
self.buffered_equality_cmp = None;
868+
self.streamed = Box::pin(EmptyRecordBatchStream::new(self.streamed.schema()));
869+
self.buffered = Box::pin(EmptyRecordBatchStream::new(self.buffered.schema()));
870+
self.streamed_exhausted = true;
871+
self.buffered_exhausted = true;
872+
}
873+
874+
/// Flush everything that remains once the join is finished.
848875
async fn on_children_exhausted(
849876
&mut self,
850877
emitter: &mut TryEmitter<RecordBatch, DataFusionError>,
851878
) -> Result<()> {
852-
// Freeze the remaining pairs, restoring any spilled batches needed.
879+
// Freeze the remaining pairs, restoring any spilled batches needed, then release
880+
// the inputs they came from.
853881
self.restore_spilled_batches_for_freeze().await?;
854882
self.freeze_all()?;
883+
self.release_inputs();
855884

856885
// Verify metadata alignment before final output
857886
self.joined_record_batches
@@ -1073,6 +1102,17 @@ impl MaterializingSortMergeJoinStream {
10731102
}
10741103
}
10751104

1105+
/// Dequeue the head buffered batch, releasing its reservation and its share of the
1106+
/// spilled-batch count. The only way to drop a buffered batch without leaking either.
1107+
fn pop_front_buffered_batch(&mut self) -> Option<BufferedBatch> {
1108+
let buffered_batch = self.buffered_data.batches.pop_front()?;
1109+
self.free_reservation(&buffered_batch);
1110+
if matches!(buffered_batch.batch, BufferedBatchState::Spilled(_)) {
1111+
self.spilled_batch_count -= 1;
1112+
}
1113+
Some(buffered_batch)
1114+
}
1115+
10761116
fn allocate_reservation(&mut self, mut buffered_batch: BufferedBatch) -> Result<()> {
10771117
match self.reservation.try_grow(buffered_batch.size_estimation) {
10781118
Ok(_) => {
@@ -1206,12 +1246,8 @@ impl MaterializingSortMergeJoinStream {
12061246
self.restore_spilled_batches(&needed).await?;
12071247

12081248
self.freeze_dequeuing_buffered()?;
1209-
if let Some(mut buffered_batch) = self.buffered_data.batches.pop_front() {
1249+
if let Some(mut buffered_batch) = self.pop_front_buffered_batch() {
12101250
self.produce_buffered_not_matched(&mut buffered_batch)?;
1211-
self.free_reservation(&buffered_batch);
1212-
if matches!(buffered_batch.batch, BufferedBatchState::Spilled(_)) {
1213-
self.spilled_batch_count -= 1;
1214-
}
12151251
head_changed = true;
12161252
}
12171253
}

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

Lines changed: 202 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -37,7 +37,7 @@ use crate::projection::{ProjectionExec, ProjectionExpr};
3737
use crate::sorts::sort::SortExec;
3838
use crate::spill::spill_manager::SpillManager;
3939
use crate::test::TestMemoryExec;
40-
use crate::test::exec::BarrierExec;
40+
use crate::test::exec::{BarrierExec, PanicExec};
4141
use crate::test::{build_table_i32, build_table_i32_two_cols};
4242
use crate::{ExecutionPlan, RecordBatchStream, common};
4343
use crate::{
@@ -527,6 +527,207 @@ fn projection_pushdown_without_filter() -> Result<()> {
527527
Ok(())
528528
}
529529

530+
/// The buffered side panics when polled, so these pass only if an empty streamed
531+
/// partition ends the join before the buffered input is touched.
532+
fn empty_left_and_panicking_right() -> (Arc<dyn ExecutionPlan>, Arc<dyn ExecutionPlan>) {
533+
let left = build_table(
534+
("a1", &Vec::<i32>::new()),
535+
("b1", &Vec::<i32>::new()),
536+
("c1", &Vec::<i32>::new()),
537+
);
538+
let right_schema =
539+
build_table(("a2", &vec![1]), ("b1", &vec![1]), ("c2", &vec![1])).schema();
540+
let right: Arc<dyn ExecutionPlan> = Arc::new(PanicExec::new(right_schema, 1));
541+
(left, right)
542+
}
543+
544+
fn on_b1(
545+
left: &Arc<dyn ExecutionPlan>,
546+
right: &Arc<dyn ExecutionPlan>,
547+
) -> Result<JoinOn> {
548+
Ok(vec![(
549+
Arc::new(Column::new_with_schema("b1", &left.schema())?) as _,
550+
Arc::new(Column::new_with_schema("b1", &right.schema())?) as _,
551+
)])
552+
}
553+
554+
#[tokio::test]
555+
async fn join_empty_streamed_side_never_polls_buffered_side() -> Result<()> {
556+
// Left-probing joins stream the left side; the right side must stay untouched.
557+
for join_type in [Inner, Left, LeftSemi, LeftAnti, LeftMark] {
558+
let (left, right) = empty_left_and_panicking_right();
559+
let on = on_b1(&left, &right)?;
560+
let (_, batches) = join_collect(left, right, on, join_type).await?;
561+
assert_eq!(
562+
batches.iter().map(|b| b.num_rows()).sum::<usize>(),
563+
0,
564+
"{join_type:?}"
565+
);
566+
}
567+
// Right-probing joins stream the right side; the left side must stay untouched.
568+
for join_type in [Right, RightSemi, RightAnti] {
569+
let (empty, panicking) = empty_left_and_panicking_right();
570+
let on = on_b1(&panicking, &empty)?;
571+
let (_, batches) = join_collect(panicking, empty, on, join_type).await?;
572+
assert_eq!(
573+
batches.iter().map(|b| b.num_rows()).sum::<usize>(),
574+
0,
575+
"{join_type:?}"
576+
);
577+
}
578+
Ok(())
579+
}
580+
581+
#[tokio::test]
582+
async fn join_full_empty_left_still_emits_buffered_rows() -> Result<()> {
583+
let left = build_table(
584+
("a1", &Vec::<i32>::new()),
585+
("b1", &Vec::<i32>::new()),
586+
("c1", &Vec::<i32>::new()),
587+
);
588+
let right = build_table(
589+
("a2", &vec![10, 20]),
590+
("b1", &vec![4, 5]),
591+
("c2", &vec![70, 80]),
592+
);
593+
let on = on_b1(&left, &right)?;
594+
let (_, batches) = join_collect(left, right, on, Full).await?;
595+
assert_snapshot!(batches_to_string(&batches), @r"
596+
+----+----+----+----+----+----+
597+
| a1 | b1 | c1 | a2 | b1 | c2 |
598+
+----+----+----+----+----+----+
599+
| | | | 10 | 4 | 70 |
600+
| | | | 20 | 5 | 80 |
601+
+----+----+----+----+----+----+
602+
");
603+
Ok(())
604+
}
605+
606+
#[tokio::test]
607+
async fn join_inner_and_semi_finish_once_buffered_side_is_exhausted() -> Result<()> {
608+
let right = build_table(
609+
("a2", &Vec::<i32>::new()),
610+
("b1", &Vec::<i32>::new()),
611+
("c2", &Vec::<i32>::new()),
612+
);
613+
for join_type in [Inner, LeftSemi] {
614+
let left = build_table(
615+
("a1", &vec![1, 2, 3]),
616+
("b1", &vec![4, 5, 6]),
617+
("c1", &vec![7, 8, 9]),
618+
);
619+
let on = on_b1(&left, &right)?;
620+
let (_, batches) = join_collect(left, Arc::clone(&right), on, join_type).await?;
621+
assert_eq!(
622+
batches.iter().map(|b| b.num_rows()).sum::<usize>(),
623+
0,
624+
"{join_type:?}"
625+
);
626+
}
627+
// Anti and mark joins still emit every unmatched streamed row.
628+
let left = build_table(
629+
("a1", &vec![1, 2]),
630+
("b1", &vec![4, 5]),
631+
("c1", &vec![7, 8]),
632+
);
633+
let on = on_b1(&left, &right)?;
634+
let (_, batches) = join_collect(left, right, on, LeftAnti).await?;
635+
assert_snapshot!(batches_to_string(&batches), @r"
636+
+----+----+----+
637+
| a1 | b1 | c1 |
638+
+----+----+----+
639+
| 1 | 4 | 7 |
640+
| 2 | 5 | 8 |
641+
+----+----+----+
642+
");
643+
Ok(())
644+
}
645+
646+
/// One streamed row below a large buffered key group: the streamed side is exhausted
647+
/// after the first comparison, and the join must give the group's reservation back before
648+
/// it hands out its final batch, not when the stream is dropped.
649+
#[tokio::test]
650+
async fn join_left_releases_buffered_reservation_before_final_batch() -> Result<()> {
651+
let left = build_table(("a1", &vec![1]), ("b1", &vec![1]), ("c1", &vec![1]));
652+
let right = build_table_from_batches(
653+
(0..16)
654+
.map(|_| {
655+
build_table_i32(
656+
("a2", &vec![2; 4096]),
657+
("b1", &vec![2; 4096]),
658+
("c2", &vec![2; 4096]),
659+
)
660+
})
661+
.collect(),
662+
);
663+
let on = on_b1(&left, &right)?;
664+
let runtime = RuntimeEnvBuilder::new()
665+
.with_memory_limit(2_000_000, 1.0)
666+
.build_arc()?;
667+
let ctx = Arc::new(TaskContext::default().with_runtime(Arc::clone(&runtime)));
668+
let mut stream = join(left, right, on, Left)?.execute(0, ctx)?;
669+
let batch = stream.next().await.unwrap()?;
670+
assert_eq!(batch.num_rows(), 1);
671+
assert_eq!(
672+
runtime.memory_pool.reserved(),
673+
0,
674+
"reservation held at the final batch"
675+
);
676+
assert!(stream.next().await.is_none());
677+
assert_eq!(
678+
runtime.memory_pool.reserved(),
679+
0,
680+
"reservation held after EOF"
681+
);
682+
Ok(())
683+
}
684+
685+
/// The parent join consumes the child's final batch while the child stream is still alive,
686+
/// with spilling disabled so a reservation the child failed to release surfaces as an error.
687+
#[tokio::test]
688+
async fn join_chain_reuses_memory_released_by_completed_child() -> Result<()> {
689+
let left = build_table(("a1", &vec![1]), ("b1", &vec![1]), ("c1", &vec![1]));
690+
let right = build_table_from_batches(
691+
(0..16)
692+
.map(|_| {
693+
build_table_i32(
694+
("a2", &vec![2; 4096]),
695+
("b1", &vec![2; 4096]),
696+
("c2", &vec![2; 4096]),
697+
)
698+
})
699+
.collect(),
700+
);
701+
let on = on_b1(&left, &right)?;
702+
let child: Arc<dyn ExecutionPlan> = Arc::new(join(left, right, on, Left)?);
703+
let parent_right = build_table_from_batches(
704+
(0..10)
705+
.map(|_| {
706+
build_table_i32(
707+
("a3", &vec![1; 4096]),
708+
("b3", &vec![1; 4096]),
709+
("c3", &vec![1; 4096]),
710+
)
711+
})
712+
.collect(),
713+
);
714+
let on = vec![(
715+
Arc::new(Column::new("a1", 0)) as _,
716+
Arc::new(Column::new("a3", 0)) as _,
717+
)];
718+
let parent = join(child, parent_right, on, Inner)?;
719+
let runtime = RuntimeEnvBuilder::new()
720+
.with_memory_limit(2_000_000, 1.0)
721+
.with_disk_manager_builder(
722+
DiskManagerBuilder::default().with_mode(DiskManagerMode::Disabled),
723+
)
724+
.build_arc()?;
725+
let ctx = Arc::new(TaskContext::default().with_runtime(runtime));
726+
let batches = common::collect(parent.execute(0, ctx)?).await?;
727+
assert_eq!(batches.iter().map(|b| b.num_rows()).sum::<usize>(), 40_960);
728+
Ok(())
729+
}
730+
530731
#[tokio::test]
531732
async fn join_inner_one() -> Result<()> {
532733
let left = build_table(

0 commit comments

Comments
 (0)