6767//!
6868//! Rows whose join key is NULL never satisfy a comparison predicate. Buffered NULLs sort to
6969//! the front, so the scan starts past them and null-keyed buffered rows are left unmarked —
70- //! correctly excluded from `LeftSemi` and included in `LeftAnti`. Each streamed batch is
71- //! sorted NULLs-*last* instead, so the extreme key taken from it is non-null unless the whole
72- //! batch is.
70+ //! correctly excluded from `LeftSemi` and included in `LeftAnti`. The extreme key is picked
71+ //! from each streamed batch with NULLs ignored, so it is non-null unless the whole batch is.
7372//!
7473//! # Output
7574//!
@@ -91,11 +90,12 @@ use std::sync::atomic::Ordering as AtomicOrdering;
9190use std:: task:: { Poll , ready} ;
9291
9392use arrow:: array:: { Array , ArrayRef , RecordBatch } ;
94- use arrow:: compute:: { BatchCoalescer , sort_to_indices , take } ;
93+ use arrow:: compute:: BatchCoalescer ;
9594use arrow_schema:: { SchemaRef , SortOptions } ;
9695use datafusion_common:: { NullEquality , Result , internal_err} ;
9796use datafusion_execution:: { RecordBatchStream , SendableRecordBatchStream } ;
9897use datafusion_expr:: { JoinType , Operator } ;
98+ use datafusion_functions_aggregate_common:: min_max:: { max_batch, min_batch} ;
9999use datafusion_physical_expr:: PhysicalExprRef ;
100100use futures:: { Stream , StreamExt } ;
101101
@@ -109,7 +109,7 @@ use crate::stream::EmptyRecordBatchStream;
109109pub ( super ) enum ExistencePWMJStreamState {
110110 /// Load the buffered side into memory.
111111 WaitBufferedSide ,
112- /// Fetch, sort and scan streamed batches, lowering the watermark. Emits nothing.
112+ /// Fetch and scan streamed batches, lowering the watermark. Emits nothing.
113113 ScanStreamBatches ,
114114 /// Emit the result. Reached only by the last streamed partition.
115115 EmitMatched ,
@@ -210,7 +210,8 @@ impl ExistencePWMJStream {
210210 Poll :: Ready ( Ok ( StatefulStreamResult :: Continue ) )
211211 }
212212
213- /// Fetches one streamed batch, sorts it, and marks the buffered rows it matches.
213+ /// Fetches one streamed batch, reduces it to its extreme compare key, and marks the
214+ /// buffered rows that key matches.
214215 /// Never produces output: existence results come from the watermark in `emit_matched`.
215216 fn scan_stream_batch (
216217 & mut self ,
@@ -237,23 +238,10 @@ impl ExistencePWMJStream {
237238 self . join_metrics . input_batches . add ( 1 ) ;
238239 self . join_metrics . input_rows . add ( batch. num_rows ( ) ) ;
239240
240- // Only the batch's extreme key is ever compared against the buffered
241- // side, so ask arrow for just that one index. `nulls_first: false` makes
242- // the chosen row non-null whenever the batch holds any non-null key, and
243- // leaves a null row only for an all-null batch, which marks nothing.
244- //
245- // The limit truncates the returned indices, not the work: `sort_impl`
246- // feeds it into the sort only when `nulls_first` is true, so this still
247- // fully sorts the batch's non-null keys.
248- let indices = sort_to_indices (
249- stream_values. as_ref ( ) ,
250- Some ( SortOptions {
251- descending : self . sort_option . descending ,
252- nulls_first : false ,
253- } ) ,
254- Some ( 1 ) ,
255- ) ?;
256- let stream_values = take ( stream_values. as_ref ( ) , & indices, None ) ?;
241+ // Only the batch's extreme key is ever compared against the buffered side,
242+ // so reduce the batch to that one key.
243+ let stream_values =
244+ extreme_key ( & stream_values, self . sort_option . descending ) ?;
257245
258246 self . mark_matched_buffered_rows ( & stream_values) ?;
259247 }
@@ -451,6 +439,26 @@ impl ExistencePWMJStream {
451439 }
452440}
453441
442+ /// Reduces `values` to a one-row array holding the batch's extreme compare key: the maximum
443+ /// when the batch's sort is `descending`, the minimum otherwise. Nulls are ignored, so that
444+ /// row is null only when every key in the batch is (or the batch is empty), which marks
445+ /// nothing.
446+ ///
447+ /// Ordered the same way as [`JoinKeyComparator`]: both use IEEE 754 totalOrder for floats,
448+ /// and the comparator normalizes `-0.0` on either side of it.
449+ ///
450+ /// Numeric, temporal, string, binary and boolean keys get a typed arrow kernel -- a linear
451+ /// scan that allocates nothing. Dictionary and nested keys fall to `min_max_batch_generic`, a
452+ /// `ScalarValue`-per-row comparator loop; specializing those is left to a follow-up.
453+ fn extreme_key ( values : & ArrayRef , descending : bool ) -> Result < ArrayRef > {
454+ let extreme = if descending {
455+ max_batch ( values) ?
456+ } else {
457+ min_batch ( values) ?
458+ } ;
459+ extreme. to_array_of_size ( 1 )
460+ }
461+
454462impl RecordBatchStream for ExistencePWMJStream {
455463 fn schema ( & self ) -> SchemaRef {
456464 Arc :: clone ( & self . schema )
0 commit comments