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;
9191use std:: sync:: atomic:: Ordering as AtomicOrdering ;
9292use 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;
96100use arrow_schema:: { SchemaRef , SortOptions } ;
97101use datafusion_common:: { NullEquality , Result , internal_err} ;
98102use datafusion_execution:: { RecordBatchStream , SendableRecordBatchStream } ;
@@ -101,6 +105,7 @@ use datafusion_functions_aggregate_common::min_max::{max_batch, min_batch};
101105use datafusion_physical_expr:: PhysicalExprRef ;
102106use futures:: { Stream , StreamExt } ;
103107
108+ use super :: utils:: { non_null_range, unmatched_buffered_batch} ;
104109use crate :: handle_state;
105110use crate :: joins:: piecewise_merge_join:: exec:: { BufferedSide , BufferedSideReadyState } ;
106111use 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.
484488pub ( 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 {
0 commit comments