Repository navigation
Commit d1fe988
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
- src/joins/sort_merge_join
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
44 | 44 | | |
45 | 45 | | |
46 | 46 | | |
| 47 | + | |
| 48 | + | |
| 49 | + | |
| 50 | + | |
| 51 | + | |
| 52 | + | |
| 53 | + | |
| 54 | + | |
| 55 | + | |
| 56 | + | |
| 57 | + | |
| 58 | + | |
| 59 | + | |
| 60 | + | |
| 61 | + | |
47 | 62 | | |
48 | 63 | | |
49 | 64 | | |
| |||
64 | 79 | | |
65 | 80 | | |
66 | 81 | | |
67 | | - | |
68 | 82 | | |
69 | 83 | | |
70 | 84 | | |
| |||
197 | 211 | | |
198 | 212 | | |
199 | 213 | | |
| 214 | + | |
| 215 | + | |
| 216 | + | |
| 217 | + | |
| 218 | + | |
| 219 | + | |
| 220 | + | |
| 221 | + | |
| 222 | + | |
| 223 | + | |
| 224 | + | |
| 225 | + | |
| 226 | + | |
| 227 | + | |
| 228 | + | |
| 229 | + | |
| 230 | + | |
| 231 | + | |
| 232 | + | |
| 233 | + | |
| 234 | + | |
| 235 | + | |
| 236 | + | |
| 237 | + | |
| 238 | + | |
| 239 | + | |
| 240 | + | |
| 241 | + | |
| 242 | + | |
| 243 | + | |
| 244 | + | |
| 245 | + | |
| 246 | + | |
| 247 | + | |
200 | 248 | | |
201 | 249 | | |
202 | 250 | | |
| |||
0 commit comments