Skip to content

Commit ede2bac

Browse files
mikamikasukiOmega359
authored andcommitted
fix: align nested piecewise merge join sorting and comparison (apache#26043)
## Which issue does this PR close? - Closes apache#25957. ## Rationale for this change Piecewise merge joins can return incorrect results for nested range keys containing inner NULLs, and fail when sorting Struct or List-of-List keys. Sorting, extreme-key selection, and comparison must use the same ordering. ## What changes are included in this PR? - Sort `<`/`<=` keys descending with NULLs last, reversing both value and inner-NULL ordering to agree with SQL comparisons. - Bound classic and left existence scans to non-null keys, preserving trailing NULL rows in outer, anti, and mark results. - Select nested min/max keys with Arrow's comparator. - Sort streamed keys with `lexsort_to_indices`, supporting Struct and List-of-List keys. - Execute nested range joins with `PiecewiseMergeJoinExec`. ## What is the testing strategy for this PR? SQL logic tests compare complete result multisets against NestedLoopJoin for List, Struct, and List-of-List keys, all four range operators, classic joins, semi/anti joins, and an EXISTS mark expression. The matrix covers batch sizes 1, 2, and 8192 and partition counts 1 and 4. Plan assertions check that Struct and List-of-List classic joins use PWMJ. Validation passed: PWMJ SQL logic tests and fuzz tests, the extended workspace suite (including all 527 SQL test files), formatting, Clippy with all targets/features, and the repository lint checks. ## Are there any user-facing changes? Nested range joins produce correct results and support Struct and List-of-List keys with piecewise merge joins enabled. No public API changes. --------- Co-authored-by: mikamikasuki <[email protected]>
1 parent 14e920f commit ede2bac

8 files changed

Lines changed: 748 additions & 77 deletions

File tree

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

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1604,14 +1604,14 @@ fn pwmj_plan(
16041604
join_type: JoinType,
16051605
) -> Arc<dyn ExecutionPlan> {
16061606
// Matches `PiecewiseMergeJoinExec::required_input_ordering`: descending for `<`/`<=`,
1607-
// ascending for `>`/`>=`, NULLs first either way. Right existence joins require no
1607+
// ascending for `>`/`>=`, reversing NULL placement too. Right existence joins require no
16081608
// ordering at all -- they only read the buffered side's min/max -- so they are fed the
16091609
// left side unsorted, which is the input shape they will see in a real plan.
16101610
let buffered = match join_type {
16111611
JoinType::RightSemi | JoinType::RightAnti | JoinType::RightMark => left,
16121612
_ => {
16131613
let sort_options = match op {
1614-
Operator::Lt | Operator::LtEq => SortOptions::new(true, true),
1614+
Operator::Lt | Operator::LtEq => SortOptions::new(true, false),
16151615
Operator::Gt | Operator::GtEq => SortOptions::new(false, true),
16161616
other => panic!("not a range operator: {other:?}"),
16171617
};

‎datafusion/physical-plan/src/joins/piecewise_merge_join/classic_join.rs‎

Lines changed: 30 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -17,12 +17,12 @@
1717

1818
//! Stream Implementation for PiecewiseMergeJoin's Classic Join (Left, Right, Full, Inner)
1919
20-
use arrow::array::{Array, PrimitiveBuilder, new_null_array};
20+
use arrow::array::{PrimitiveBuilder, new_null_array};
2121
use arrow::compute::{BatchCoalescer, take};
2222
use arrow::datatypes::UInt32Type;
2323
use arrow::{
2424
array::{ArrayRef, RecordBatch, UInt32Array},
25-
compute::{sort_to_indices, take_record_batch},
25+
compute::{SortColumn, lexsort_to_indices, take_record_batch},
2626
};
2727
use arrow_schema::{Schema, SchemaRef, SortOptions};
2828
use datafusion_common::NullEquality;
@@ -37,7 +37,9 @@ use std::{sync::Arc, task::Poll};
3737

3838
use crate::handle_state;
3939
use crate::joins::piecewise_merge_join::exec::{BufferedSide, BufferedSideReadyState};
40-
use crate::joins::piecewise_merge_join::utils::need_produce_result_in_final;
40+
use crate::joins::piecewise_merge_join::utils::{
41+
need_produce_result_in_final, non_null_range, unmatched_buffered_batch,
42+
};
4143
use crate::joins::utils::JoinKeyComparator;
4244
use crate::joins::utils::{BuildProbeJoinMetrics, StatefulStreamResult};
4345
use crate::stream::EmptyRecordBatchStream;
@@ -244,9 +246,11 @@ impl ClassicPWMJStream {
244246
self.join_metrics.input_rows.add(batch.num_rows());
245247

246248
// Sort stream values and change the streamed record batch accordingly
247-
let indices = sort_to_indices(
248-
stream_values.as_ref(),
249-
Some(self.sort_option),
249+
let indices = lexsort_to_indices(
250+
&[SortColumn {
251+
values: Arc::clone(&stream_values),
252+
options: Some(self.sort_option),
253+
}],
250254
None,
251255
)?;
252256
let stream_batch = take_record_batch(&batch, &indices)?;
@@ -336,16 +340,11 @@ impl ClassicPWMJStream {
336340
let buffered_data = Arc::clone(&self.buffered_side.try_as_ready()?.buffered_data);
337341
let buffered_batch = buffered_data.batch();
338342

339-
// Every match marks the suffix `[k, buffered_len)`, so the buffered rows that were
340-
// never matched are exactly the complementary prefix `[0, min_marked)` -- which
341-
// includes the null-keyed rows, since nulls sort first and the scan starts past
342-
// them. That makes the final pass a zero-copy slice instead of building an index
343-
// array and running `take` over it.
344-
let min_marked = buffered_data
345-
.min_marked
346-
.load(AtomicOrdering::SeqCst)
347-
.min(buffered_batch.num_rows());
348-
let new_buffered_batch = buffered_batch.slice(0, min_marked);
343+
let (_, non_null_end) =
344+
non_null_range(buffered_data.values().as_ref(), self.sort_option);
345+
let min_marked = buffered_data.min_marked.load(AtomicOrdering::SeqCst);
346+
let new_buffered_batch =
347+
unmatched_buffered_batch(buffered_batch, min_marked, non_null_end)?;
349348
let mut buffered_columns = new_buffered_batch.columns().to_vec();
350349

351350
let streamed_columns: Vec<ArrayRef> = self
@@ -444,7 +443,8 @@ fn resolve_classic_join(
444443
join_type: JoinType,
445444
batch_process_state: &mut BatchProcessState,
446445
) -> Result<RecordBatch> {
447-
let buffered_len = buffered_side.buffered_data.values().len();
446+
let (buffered_start, buffered_len) =
447+
non_null_range(buffered_side.buffered_data.values().as_ref(), sort_options);
448448
let stream_values = stream_batch.compare_key_values();
449449

450450
// Build comparator once for the batch pair
@@ -459,26 +459,28 @@ fn resolve_classic_join(
459459
let mut stream_idx = batch_process_state.start_stream_idx;
460460

461461
if !batch_process_state.processed_null_count {
462-
let buffered_null_idx = buffered_side.buffered_data.values().null_count();
463-
let stream_null_idx = stream_values[0].null_count();
464-
buffer_idx = buffered_null_idx;
465-
stream_idx = stream_null_idx;
462+
let (stream_start, stream_end) =
463+
non_null_range(stream_values[0].as_ref(), sort_options);
464+
buffer_idx = buffered_start;
465+
stream_idx = stream_start;
466466
batch_process_state.processed_null_count = true;
467467

468-
// The scan below starts past the streamed side's NULL-keyed rows, which
469-
// sit at the front (`nulls_first`). A NULL join key never matches under
470-
// `NullEqualsNothing`, so for `Right`/`Full` those rows are unmatched and
471-
// must still be emitted; record them here since the scan will skip them.
468+
// NULL keys never match, but outer joins must emit them on either end.
472469
if matches!(join_type, JoinType::Right | JoinType::Full) {
473-
for row_idx in 0..stream_null_idx as u32 {
474-
batch_process_state.unmatched_indices.append_value(row_idx);
470+
for row_idx in
471+
(0..stream_start).chain(stream_end..stream_batch.batch.num_rows())
472+
{
473+
batch_process_state
474+
.unmatched_indices
475+
.append_value(row_idx as u32);
475476
}
476477
}
477478
}
478479

479480
// Our buffer_idx variable allows us to start probing on the buffered side where we last matched
480481
// in the previous stream row.
481-
for row_idx in stream_idx..stream_batch.batch.num_rows() {
482+
let (_, stream_end) = non_null_range(stream_values[0].as_ref(), sort_options);
483+
for row_idx in stream_idx..stream_end {
482484
while buffer_idx < buffered_len {
483485
let compare = cmp.compare(row_idx, buffer_idx);
484486

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

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -330,7 +330,7 @@ impl PiecewiseMergeJoinExec {
330330
// Take the operator and enforce a sort order on the streamed + buffered side based on
331331
// the operator type.
332332
let sort_options = match operator {
333-
Operator::Lt | Operator::LtEq => SortOptions::new(true, true),
333+
Operator::Lt | Operator::LtEq => SortOptions::new(true, false),
334334
Operator::Gt | Operator::GtEq => SortOptions::new(false, true),
335335
_ => {
336336
return internal_err!(
@@ -1034,14 +1034,14 @@ pub(super) struct BufferedSideData {
10341034
pub(super) batch: RecordBatch,
10351035
values: ArrayRef,
10361036
pub(super) remaining_partitions: AtomicUsize,
1037-
/// The start of the matched suffix of the buffered side, or `usize::MAX` before the
1038-
/// first match. `[min_marked, len)` *is* the matched set and `[0, min_marked)` the
1039-
/// unmatched one -- no bitmap is allocated.
1037+
/// The start of the matched non-null suffix, or `usize::MAX` before the
1038+
/// first match. `[min_marked, non_null_end)` is the matched set; the prefix
1039+
/// and any trailing NULL keys are unmatched. No bitmap is allocated.
10401040
///
10411041
/// Both stream kinds only ever mark a suffix, which is what makes one index enough:
1042-
/// - `ExistencePWMJStream` marks `[k, len)` for the first buffered row `k` matching
1042+
/// - `ExistencePWMJStream` marks `[k, non_null_end)` for the first row `k` matching
10431043
/// a streamed batch's extreme key.
1044-
/// - `ClassicPWMJStream` emits `buffered[k..] x streamed_row` on each match, so the
1044+
/// - `ClassicPWMJStream` emits `buffered[k..non_null_end] x streamed_row`, so the
10451045
/// rows it marks are exactly that same suffix.
10461046
///
10471047
/// Shared so each partition benefits from what the others have marked; it only ever

‎datafusion/physical-plan/src/joins/piecewise_merge_join/existence_join.rs‎

Lines changed: 64 additions & 33 deletions
Original file line numberDiff line numberDiff line change
@@ -65,22 +65,22 @@
6565
//! so a partition that starts late reads nothing at all.
6666
//!
6767
//! Rows whose join key is NULL never satisfy a comparison predicate. Buffered NULLs sort to
68-
//! the front, so the scan starts past them and null-keyed buffered rows are left unmarked —
68+
//! either end, outside the searched range, and null-keyed buffered rows are left unmarked —
6969
//! correctly excluded from `LeftSemi` and included in `LeftAnti`. The extreme key is picked
7070
//! from each streamed batch with NULLs ignored, so it is non-null unless the whole batch is.
7171
//!
7272
//! # Output
7373
//!
7474
//! Marking only ever covers a suffix, and each mark lowers the watermark to its own start,
75-
//! so the matched set is always exactly `[min_marked, buffered_len)`. A bitmap would be a
75+
//! so the matched set is always exactly `[min_marked, non_null_end)`. A bitmap would be a
7676
//! less compact encoding of that one index, so none is allocated. `ClassicPWMJStream` marks
7777
//! the same way, which is why the watermark lives in `BufferedSideData` rather than here.
7878
//!
7979
//! Once every streamed partition has been consumed, the last one to finish slices the
80-
//! buffered batch: `LeftSemi` takes `[min_marked, len)`, `LeftAnti` the complementary
81-
//! prefix `[0, min_marked)`, which is where the null-keyed rows live. `LeftMark` takes
80+
//! buffered batch: `LeftSemi` takes `[min_marked, non_null_end)`, `LeftAnti` the complementary
81+
//! prefix `[0, min_marked)` plus any trailing null-keyed rows. `LeftMark` takes
8282
//! neither slice: every buffered row is preserved, with a `mark` column built from the same
83-
//! watermark (`true` from `min_marked` on, `false` before it) appended instead of any row
83+
//! watermark (`true` in the matched range, `false` elsewhere) appended instead of any row
8484
//! being dropped. Only the buffered (left) columns, plus that `mark` column for `LeftMark`,
8585
//! are produced.
8686
//!
@@ -91,8 +91,12 @@ use std::sync::Arc;
9191
use std::sync::atomic::Ordering as AtomicOrdering;
9292
use std::task::{Poll, ready};
9393

94-
use arrow::array::{Array, ArrayRef, BooleanArray, BooleanBufferBuilder, RecordBatch};
95-
use arrow::compute::BatchCoalescer;
94+
use arrow::array::{
95+
Array, ArrayRef, BooleanArray, BooleanBufferBuilder, RecordBatch, UInt32Array,
96+
new_null_array,
97+
};
98+
use arrow::compute::{BatchCoalescer, take};
99+
use arrow_ord::ord::make_comparator;
96100
use arrow_schema::{SchemaRef, SortOptions};
97101
use datafusion_common::{NullEquality, Result, internal_err};
98102
use datafusion_execution::{RecordBatchStream, SendableRecordBatchStream};
@@ -101,6 +105,7 @@ use datafusion_functions_aggregate_common::min_max::{max_batch, min_batch};
101105
use datafusion_physical_expr::PhysicalExprRef;
102106
use futures::{Stream, StreamExt};
103107

108+
use super::utils::{non_null_range, unmatched_buffered_batch};
104109
use crate::handle_state;
105110
use crate::joins::piecewise_merge_join::exec::{BufferedSide, BufferedSideReadyState};
106111
use crate::joins::utils::{
@@ -265,7 +270,8 @@ impl ExistencePWMJStream {
265270
let min_marked = buffered_data.min_marked.load(AtomicOrdering::SeqCst);
266271
let buffered_values = buffered_data.values();
267272

268-
Ok(min_marked.min(buffered_values.len()) <= buffered_values.null_count())
273+
let (start, end) = non_null_range(buffered_values.as_ref(), self.sort_option);
274+
Ok(min_marked.min(end) <= start)
269275
}
270276

271277
/// Marks this partition done with the streamed side: releases the input pipeline and,
@@ -301,20 +307,18 @@ impl ExistencePWMJStream {
301307
{
302308
let buffered_data = &self.buffered_side.try_as_ready()?.buffered_data;
303309
let buffered_values = buffered_data.values();
304-
let buffered_len = buffered_values.len();
305310

306-
// NULL keys can never match, and `sort_options` uses `nulls_first` for every
307-
// operator (see `try_new`), so buffered nulls sit at the front -- skip past them.
308-
let first_non_null_buffered = buffered_values.null_count();
311+
let (first_non_null_buffered, non_null_end) =
312+
non_null_range(buffered_values.as_ref(), sort_option);
309313

310-
// `[min_marked, buffered_len)` was already marked, by this partition or
314+
// `[min_marked, non_null_end)` was already marked, by this partition or
311315
// another, so a match found there would write nothing. Stop the scan at the
312316
// watermark: that bounds the comparisons this batch performs, not just the
313317
// bits it writes.
314318
let scan_limit = buffered_data
315319
.min_marked
316320
.load(AtomicOrdering::SeqCst)
317-
.min(buffered_len);
321+
.min(non_null_end);
318322

319323
// The extreme key is the only one that can decide anything: it reaches the
320324
// smallest matching `buffer_idx`, and every other row in the batch matches a
@@ -370,7 +374,7 @@ impl ExistencePWMJStream {
370374
if buffer_idx < scan_limit {
371375
// Everything from `buffer_idx` on matches, so lowering the
372376
// watermark to it records the match: the marked set is exactly
373-
// `[min_marked, buffered_len)` and needs no bitmap.
377+
// `[min_marked, non_null_end)` and needs no bitmap.
374378
//
375379
// INVARIANT: sound only because the buffered side and each
376380
// streamed batch are sorted the same way for this operator
@@ -403,42 +407,43 @@ impl ExistencePWMJStream {
403407
let buffered_batch = buffered_data.batch();
404408
let buffered_len = buffered_batch.num_rows();
405409

406-
// The marked rows are always the contiguous suffix `[min_marked, len)`: each
407-
// match covers `[k, previous min_marked)` and then lowers the watermark to
408-
// `k`, so the union is `[k, len)`. The result is therefore a slice, with no
409-
// index array to materialize and no `take`.
410+
// The matched non-null suffix is `[min_marked, non_null_end)`.
411+
// Each match lowers the watermark; trailing NULL keys stay unmarked.
412+
let (_, non_null_end) =
413+
non_null_range(buffered_data.values().as_ref(), self.sort_option);
410414
let min_marked = buffered_data
411415
.min_marked
412416
.load(AtomicOrdering::SeqCst)
413-
.min(buffered_len);
417+
.min(non_null_end);
414418

415419
let (num_rows, columns) = match self.join_type {
416420
JoinType::LeftSemi => {
417421
let sliced =
418-
buffered_batch.slice(min_marked, buffered_len - min_marked);
422+
buffered_batch.slice(min_marked, non_null_end - min_marked);
419423
(sliced.num_rows(), sliced.columns().to_vec())
420424
}
421425
// `LeftMark` keeps every buffered row -- nothing to slice -- and appends
422-
// the watermark as a `mark` column instead of using it to drop rows: `false`
423-
// for the unmatched prefix `[0, min_marked)`, `true` for the matched suffix
424-
// `[min_marked, len)` -- the same split `LeftSemi`/`LeftAnti` slice the
425-
// buffered batch on, just kept as one column instead of used to drop rows.
426+
// the watermark as a `mark` column: true only within the matched
427+
// non-null range, false for the prefix and any trailing NULL keys.
426428
JoinType::LeftMark => {
427429
let mut mark = BooleanBufferBuilder::new(buffered_len);
428430
mark.append_n(min_marked, false);
429-
mark.append_n(buffered_len - min_marked, true);
431+
mark.append_n(non_null_end - min_marked, true);
432+
mark.append_n(buffered_len - non_null_end, false);
430433

431434
let mut columns = buffered_batch.columns().to_vec();
432435
columns.push(
433436
Arc::new(BooleanArray::new(mark.finish(), None)) as ArrayRef
434437
);
435438
(buffered_len, columns)
436439
}
437-
// `LeftAnti`: the unmarked prefix, which includes every null-keyed row --
438-
// nulls sort first and the watermark never drops below the buffered null
439-
// count.
440+
// `LeftAnti` includes the unmarked prefix and any trailing NULL keys.
440441
JoinType::LeftAnti => {
441-
let sliced = buffered_batch.slice(0, min_marked);
442+
let sliced = unmatched_buffered_batch(
443+
buffered_batch,
444+
min_marked,
445+
non_null_end,
446+
)?;
442447
(sliced.num_rows(), sliced.columns().to_vec())
443448
}
444449
other => {
@@ -478,10 +483,36 @@ impl ExistencePWMJStream {
478483
/// Ordered the same way as [`JoinKeyComparator`]: both use IEEE 754 totalOrder for floats,
479484
/// and the comparator normalizes `-0.0` on either side of it.
480485
///
481-
/// Numeric, temporal, string, binary and boolean keys get a typed arrow kernel -- a linear
482-
/// scan that allocates nothing. Dictionary and nested keys fall to `min_max_batch_generic`, a
483-
/// `ScalarValue`-per-row comparator loop; specializing those is left to a follow-up.
486+
/// Nested keys use Arrow's comparator, so inner NULLs have the same ordering as
487+
/// sorting and range comparisons. Other keys use the typed min/max kernels.
484488
pub(super) fn extreme_key(values: &ArrayRef, descending: bool) -> Result<ArrayRef> {
489+
if values.data_type().is_nested() {
490+
// Reverse both value and inner-NULL ordering for max, matching SQL's
491+
// ascending NULLS FIRST nested comparison order.
492+
let cmp = make_comparator(
493+
values.as_ref(),
494+
values.as_ref(),
495+
SortOptions::new(descending, !descending),
496+
)?;
497+
let nulls = values.logical_nulls();
498+
let mut extreme = None;
499+
for idx in 0..values.len() {
500+
if nulls.as_ref().is_some_and(|n| n.is_null(idx)) {
501+
continue;
502+
}
503+
if extreme.is_none_or(|current| cmp(idx, current) == Ordering::Less) {
504+
extreme = Some(idx);
505+
}
506+
}
507+
return match extreme {
508+
Some(idx) => Ok(take(
509+
values.as_ref(),
510+
&UInt32Array::from(vec![idx as u32]),
511+
None,
512+
)?),
513+
None => Ok(new_null_array(values.data_type(), 1)),
514+
};
515+
}
485516
let extreme = if descending {
486517
max_batch(values)?
487518
} else {

‎datafusion/physical-plan/src/joins/piecewise_merge_join/utils.rs‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -15,8 +15,36 @@
1515
// specific language governing permissions and limitations
1616
// under the License.
1717

18+
use arrow::array::{Array, RecordBatch};
19+
use arrow::compute::concat_batches;
20+
use arrow_schema::SortOptions;
21+
use datafusion_common::Result;
1822
use datafusion_expr::JoinType;
1923

24+
/// Bounds of the non-null keys in an array sorted with `options`.
25+
pub(super) fn non_null_range(values: &dyn Array, options: SortOptions) -> (usize, usize) {
26+
let null_count = values.logical_null_count();
27+
if options.nulls_first {
28+
(null_count, values.len())
29+
} else {
30+
(0, values.len() - null_count)
31+
}
32+
}
33+
34+
/// Keep the unmatched prefix and any trailing NULL keys outside the matching range.
35+
pub(super) fn unmatched_buffered_batch(
36+
batch: &RecordBatch,
37+
min_marked: usize,
38+
non_null_end: usize,
39+
) -> Result<RecordBatch> {
40+
let prefix = batch.slice(0, min_marked.min(non_null_end));
41+
if non_null_end == batch.num_rows() {
42+
return Ok(prefix);
43+
}
44+
let nulls = batch.slice(non_null_end, batch.num_rows() - non_null_end);
45+
Ok(concat_batches(&batch.schema(), [&prefix, &nulls])?)
46+
}
47+
2048
// Returns boolean for whether the join is a right existence join served by
2149
// `RightExistencePWMJStream`, which reads nothing but a single min/max off the buffered side.
2250
//

0 commit comments

Comments
 (0)