3333//! - [`NotInBuild::final_chunk`] on each chunk of build rows emitted after
3434//! the probe side is exhausted.
3535
36- use std:: sync:: Arc ;
36+ use std:: sync:: { Arc , OnceLock } ;
3737
3838use parking_lot:: Mutex ;
3939
@@ -59,7 +59,7 @@ use crate::joins::join_hash_map::{JoinHashMapType, ProbeOffset};
5959use crate :: joins:: probe_completion:: ProbeSideSummary ;
6060use crate :: joins:: utils:: {
6161 BuildProbeJoinMetrics , JoinFilter , apply_join_filter_to_indices,
62- equal_rows_arr_with_normalized_left, matchable_join_keys, update_hash ,
62+ equal_rows_arr_with_normalized_left, matchable_join_keys,
6363} ;
6464
6565/// Which `NOT IN` a null-aware join computes, derived from
@@ -181,9 +181,9 @@ pub(super) enum NotInBuild {
181181 /// One bit per build row, set once its mark is UNKNOWN; shared by
182182 /// every probe partition, and never cleared.
183183 unknown : SharedBitmapBuilder ,
184- /// Hash table over the scope keys (`on[value_keys..]`) of all build
185- /// rows, probed with NULL-valued probe rows. `None` without scope keys.
186- scope_map : Option < Box < dyn JoinHashMapType > > ,
184+ /// Hash table over the scope keys of all build rows, probed with
185+ /// NULL-valued probe rows. `None` without scope keys.
186+ scope_map : Option < BuildScopeMap > ,
187187 /// The build rows with a NULL value key, `None` when there are none.
188188 null_value_rows : Option < NullValueBuildRows > ,
189189 } ,
@@ -200,7 +200,7 @@ pub(super) enum NotInBuild {
200200 /// The fields are those of [`Self::BuildRowsCorrelated`].
201201 ProbeRowsCorrelated {
202202 value_keys : usize ,
203- scope_map : Option < Box < dyn JoinHashMapType > > ,
203+ scope_map : Option < BuildScopeMap > ,
204204 null_value_rows : Option < NullValueBuildRows > ,
205205 } ,
206206 /// Uncorrelated [`NotIn::ProbeRows`].
@@ -229,7 +229,6 @@ impl NotInBuild {
229229 let correlated_row_state = |value_keys, reservation : & mut MemoryReservation | {
230230 correlated_row_state (
231231 on_left,
232- batch,
233232 keys,
234233 normalized,
235234 value_keys,
@@ -478,7 +477,7 @@ impl NotInProbe {
478477 mark_null_candidates_for_probe_batch (
479478 left_data,
480479 UnknownMarks :: Build ( unknown) ,
481- scope_map. as_deref ( ) ,
480+ scope_map. as_ref ( ) ,
482481 null_value_rows. as_ref ( ) ,
483482 probe_batch,
484483 probe_values,
@@ -516,7 +515,7 @@ impl NotInProbe {
516515 mark_null_candidates_for_probe_batch (
517516 left_data,
518517 UnknownMarks :: Probe ( & unknown) ,
519- scope_map. as_deref ( ) ,
518+ scope_map. as_ref ( ) ,
520519 null_value_rows. as_ref ( ) ,
521520 probe_batch,
522521 probe_values,
@@ -601,42 +600,23 @@ fn retain_probe_rows(
601600}
602601
603602/// The scope map and NULL-valued build rows of a correlated `NOT IN`.
604- #[ expect( clippy:: too_many_arguments, clippy:: type_complexity) ]
605603fn correlated_row_state (
606604 on_left : & [ PhysicalExprRef ] ,
607- batch : & RecordBatch ,
608605 keys : & [ ArrayRef ] ,
609606 normalized : & [ ArrayRef ] ,
610607 value_keys : usize ,
611608 random_state : & RandomState ,
612609 reservation : & mut MemoryReservation ,
613610 metrics : & BuildProbeJoinMetrics ,
614- ) -> Result < ( Option < Box < dyn JoinHashMapType > > , Option < NullValueBuildRows > ) > {
615- let num_rows = batch. num_rows ( ) ;
611+ ) -> Result < ( Option < BuildScopeMap > , Option < NullValueBuildRows > ) > {
616612 // `on_left[..V]` are the value keys and `on_left[V..]` the (possibly
617613 // empty) correlation scope keys.
618614 let scope_keys = & on_left[ value_keys..] ;
619- let scope_map = if scope_keys. is_empty ( ) {
620- None
621- } else {
622- // Scope-only NULL marking uses a HashMap (the primary join map may
623- // use ArrayMap for full-key matches, but scope keys have arbitrary
624- // shape).
625- let mut scope_map = new_join_hashmap ( num_rows, reservation, metrics) ?;
626- let mut hashes_buffer = vec ! [ 0 ; num_rows] ;
627- update_hash (
628- scope_keys,
629- batch,
630- & mut * scope_map,
631- 0 ,
632- random_state,
633- & mut hashes_buffer,
634- 0 ,
635- true ,
636- NullEquality :: NullEqualsNothing ,
637- ) ?;
638- Some ( scope_map)
639- } ;
615+ let scope_map = ( !scope_keys. is_empty ( ) ) . then ( || BuildScopeMap {
616+ map : OnceLock :: new ( ) ,
617+ reservation : Mutex :: new ( reservation. new_empty ( ) ) ,
618+ metrics : metrics. clone ( ) ,
619+ } ) ;
640620
641621 let Some ( null_mask) = null_value_key_mask ( & keys[ ..value_keys] ) else {
642622 return Ok ( ( scope_map, None ) ) ;
@@ -672,6 +652,54 @@ fn correlated_row_state(
672652 ) )
673653}
674654
655+ /// Hash table over the correlation scope keys (`on[value_keys..]`) of all
656+ /// build rows, used by correlated `NOT IN` (see [`NotInScope::Correlated`]).
657+ ///
658+ /// Only the probe rows with a NULL value key look it up, so it is built on
659+ /// the first such probe row rather than with the build side: a probe side
660+ /// without NULLs never pays for a second hash table over the build side.
661+ pub ( super ) struct BuildScopeMap {
662+ map : OnceLock < Box < dyn JoinHashMapType > > ,
663+ /// Charged for the map once it is built. Its lock also makes the probe
664+ /// partitions build the map only once.
665+ reservation : Mutex < MemoryReservation > ,
666+ metrics : BuildProbeJoinMetrics ,
667+ }
668+
669+ impl BuildScopeMap {
670+ /// Returns the map, building it on first use from `scope_values`, the
671+ /// build side's scope keys (`JoinLeftData::values()[value_keys..]`).
672+ fn get_or_try_init (
673+ & self ,
674+ scope_values : & [ ArrayRef ] ,
675+ random_state : & RandomState ,
676+ ) -> Result < & dyn JoinHashMapType > {
677+ if let Some ( map) = self . map . get ( ) {
678+ return Ok ( map. as_ref ( ) ) ;
679+ }
680+ let mut reservation = self . reservation . lock ( ) ;
681+ if let Some ( map) = self . map . get ( ) {
682+ return Ok ( map. as_ref ( ) ) ;
683+ }
684+ // Scope-only NULL marking uses a HashMap (the primary join map may
685+ // use ArrayMap for full-key matches, but scope keys have arbitrary
686+ // shape).
687+ let num_rows = scope_values[ 0 ] . len ( ) ;
688+ let mut map = new_join_hashmap ( num_rows, & mut reservation, & self . metrics ) ?;
689+ let mut hashes_buffer = vec ! [ 0 ; num_rows] ;
690+ create_hashes ( scope_values, random_state, & mut hashes_buffer) ?;
691+ map. extend_zero ( num_rows) ;
692+ // A build row whose scope keys hold a NULL is in no scope.
693+ let valid = matchable_join_keys ( scope_values, NullEquality :: NullEqualsNothing ) ;
694+ let hashes = hashes_buffer
695+ . iter ( )
696+ . enumerate ( )
697+ . filter ( |( i, _) | valid. as_ref ( ) . is_none_or ( |valid| valid. is_valid ( * i) ) ) ;
698+ map. update_from_iter ( Box :: new ( hashes. rev ( ) ) , 0 ) ;
699+ Ok ( self . map . get_or_init ( || map) . as_ref ( ) )
700+ }
701+ }
702+
675703/// The build rows with a NULL `NOT IN` value key (in any element of a
676704/// multi-column key), used by correlated `NOT IN` (see [`NotInScope::Correlated`]).
677705///
@@ -763,7 +791,7 @@ impl<'a> UnknownMarks<'a> {
763791fn mark_null_candidates_for_probe_batch (
764792 left_data : & JoinLeftData ,
765793 marks : UnknownMarks < ' _ > ,
766- scope_map : Option < & dyn JoinHashMapType > ,
794+ scope_map : Option < & BuildScopeMap > ,
767795 null_value_build_rows : Option < & NullValueBuildRows > ,
768796 probe_batch : & RecordBatch ,
769797 probe_values : & [ ArrayRef ] ,
@@ -893,14 +921,20 @@ fn mark_null_candidates_for_probe_batch(
893921 // Case 2: NULL-valued probe rows paired with the build rows in their
894922 // correlation scope.
895923 if let Some ( null_mask) = probe_null_value_mask {
896- let null_probe_rows = null_mask
924+ let mut null_probe_rows = null_mask
897925 . values ( )
898926 . set_indices ( )
899927 . map ( |i| i as u32 )
900- . filter ( in_scope) ;
928+ . filter ( in_scope)
929+ . peekable ( ) ;
901930
902931 match scope_map {
932+ // No NULL-valued probe row is in any scope: nothing to look up,
933+ // so the scope map need not be built.
934+ Some ( _) if null_probe_rows. peek ( ) . is_none ( ) => { }
903935 Some ( scope_map) => {
936+ let scope_map =
937+ scope_map. get_or_try_init ( build_scope_values, random_state) ?;
904938 let mut pairs =
905939 UnmarkedPairs :: new ( marks, batch_size, & mut mark_scope_matches) ;
906940 pairs. scope_matches (
0 commit comments