Skip to content

Commit d1fe988

Browse files
authored
fix: ensure deferred-filtered outer joins preserve streamed output order (apache#24573)
## Rationale for this change `LEFT`/`RIGHT`/`FULL` sort-merge joins with a join filter could return rows out of order. These join types advertise that they preserve the ordering of one input (`maintains_input_order` is `[true, false]` for `LEFT`), so downstream operators are allowed to rely on it. Deferred-filtered joins stage their output in a second `BatchCoalescer` (`self.output`) because the filter correction step emits ragged batch sizes. The final flush at end-of-input bypassed that buffer and emitted its batch directly, so any rows still buffered in `output` from an earlier flush were emitted *after* it. A `LEFT JOIN` where some keys match large buffered groups and the trailing keys match a single row each reproduces this: the large groups trip the flush gate and push sub-threshold batches that stay buffered, while the trailing keys never trip the gate and land in the final flush. Streamed keys came back as `[5, 6, 0, 1, 2, 3, 4]` instead of `[0, 1, 2, 3, 4, 5, 6]`. ## What changes are included in this PR? Bug fix: - `on_children_exhausted` now pushes the final filtered batch into `self.output` instead of emitting it directly, so all deferred-filtered output leaves through a single buffer and stays in order. Cleanups in the same file, no behavior change: - `emit_completed_output` drains every completed batch from `self.output`; previously each flush emitted at most one and left the rest buffered. - `join_arrays` returns `Result` instead of `unwrap()`-ing. A failing join-key expression previously panicked the worker thread. `StreamedBatch::new` and `BufferedBatch::new` became `try_new`. - `materialize_right_columns` maps buffered batch indices to interleave sources with a linear scan instead of a `HashMap` — a key group spans a handful of batches at most, and this ran per matched chunk. - Extracted `new_output_coalescer`, replacing four copies of the same `BatchCoalescer::new(..).with_biggest_coalesce_batch_size(..)` construction. ## Are these changes tested? Yes. Added `left_join_with_filter_preserves_streamed_order`, which builds the mixed group-size shape described above and asserts the streamed key column comes back in order. It fails on `main` with `[5, 6, 0, 1, 2, 3, 4]`. Also ran the full `datafusion-physical-plan` test suite and the joins sqllogictests. ## Are there any user-facing changes? Yes — outer sort-merge joins with a join filter now return rows in the order the operator claims to produce them. No API changes.
1 parent 9617fdf commit d1fe988

3 files changed

Lines changed: 571 additions & 91 deletions

File tree

‎datafusion/physical-plan/benches/sort_merge_join.rs‎

Lines changed: 49 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -44,6 +44,21 @@ fn build_sorted_batches(
4444
num_rows: usize,
4545
key_mod: usize,
4646
schema: &SchemaRef,
47+
) -> Vec<RecordBatch> {
48+
build_sorted_batches_with_size(num_rows, key_mod, 8192, schema)
49+
}
50+
51+
/// Like [`build_sorted_batches`], but with an explicit output batch size.
52+
///
53+
/// `SortMergeJoinExec` takes arbitrary children, so the buffered side is not
54+
/// guaranteed to arrive in `batch_size`-sized batches. Small `batch_size`
55+
/// values make a single key group span many buffered batches, which is what
56+
/// drives `materialize_right_columns` onto its multi-source `interleave` path.
57+
fn build_sorted_batches_with_size(
58+
num_rows: usize,
59+
key_mod: usize,
60+
batch_size: usize,
61+
schema: &SchemaRef,
4762
) -> Vec<RecordBatch> {
4863
let mut rows: Vec<(i64, i64)> = (0..num_rows)
4964
.map(|i| ((i % key_mod) as i64, i as i64))
@@ -64,7 +79,6 @@ fn build_sorted_batches(
6479
)
6580
.unwrap();
6681

67-
let batch_size = 8192;
6882
let mut batches = Vec::new();
6983
let mut offset = 0;
7084
while offset < batch.num_rows() {
@@ -197,6 +211,40 @@ fn bench_smj(c: &mut Criterion) {
197211
});
198212
}
199213

214+
// Multi-source interleave path — one buffered key group spanning many
215+
// small buffered batches.
216+
//
217+
// Every other case here keeps a key group inside a single buffered batch,
218+
// so `materialize_right_columns` takes its single-source `take` fast path
219+
// and never reaches `interleave`. Shrinking the buffered batch size makes
220+
// a group span `group_rows / rows_per_batch` batches, which is what the
221+
// source-index mapping is actually paid for. Four streamed rows share each
222+
// key, so the buffered scan is re-walked per streamed row and freezes wrap
223+
// mid-group.
224+
{
225+
let keys = 8;
226+
let group_rows = 8192;
227+
let left_batches = build_sorted_batches(keys * 4, keys, &s);
228+
for rows_per_batch in [512, 64, 8] {
229+
let right_batches = build_sorted_batches_with_size(
230+
keys * group_rows,
231+
keys,
232+
rows_per_batch,
233+
&s,
234+
);
235+
group.bench_function(
236+
BenchmarkId::new("inner_group_spans_buffered_batches", rows_per_batch),
237+
|b| {
238+
b.iter(|| {
239+
let left = make_exec(&left_batches, &s);
240+
let right = make_exec(&right_batches, &s);
241+
do_join(left, right, datafusion_common::JoinType::Inner, &rt)
242+
})
243+
},
244+
);
245+
}
246+
}
247+
200248
group.finish();
201249
}
202250

0 commit comments

Comments
 (0)