@@ -667,10 +667,12 @@ fn correlated_row_state(
667667/// rows in their scope. So when the memory pool cannot hold it, the join
668668/// pairs them with every build row instead, and compares their scope keys.
669669/// That is the pairing of a join whose tuple elements are all value keys,
670- /// which needs no map either.
670+ /// which needs no map either. The next probe batch with such rows tries to
671+ /// build the map again.
671672pub ( super ) struct BuildScopeMap {
672- /// `None` when the memory pool could not hold the map.
673- map : OnceLock < Option < Box < dyn JoinHashMapType > > > ,
673+ /// Set once the memory pool holds the map. Until then each use tries to
674+ /// reserve it again, as the pool may have freed memory since.
675+ map : OnceLock < Box < dyn JoinHashMapType > > ,
674676 /// Charged for the map once it is built. Its lock also makes the probe
675677 /// partitions build the map only once.
676678 reservation : Mutex < MemoryReservation > ,
@@ -680,28 +682,26 @@ pub(super) struct BuildScopeMap {
680682impl BuildScopeMap {
681683 /// Returns the map, building it on first use from `scope_values`, the
682684 /// build side's scope keys (`JoinLeftData::values()[value_keys..]`).
683- /// Returns `None` when the memory pool cannot hold it.
685+ /// Returns `None` when the memory pool cannot hold it yet .
684686 fn get_or_try_init (
685687 & self ,
686688 scope_values : & [ ArrayRef ] ,
687689 random_state : & RandomState ,
688690 ) -> Result < Option < & dyn JoinHashMapType > > {
689691 if let Some ( map) = self . map . get ( ) {
690- return Ok ( map. as_deref ( ) ) ;
692+ return Ok ( Some ( map. as_ref ( ) ) ) ;
691693 }
692694 let mut reservation = self . reservation . lock ( ) ;
693695 if let Some ( map) = self . map . get ( ) {
694- return Ok ( map. as_deref ( ) ) ;
696+ return Ok ( Some ( map. as_ref ( ) ) ) ;
695697 }
696698 // Scope-only NULL marking uses a HashMap (the primary join map may
697699 // use ArrayMap for full-key matches, but scope keys have arbitrary
698700 // shape).
699701 let num_rows = scope_values[ 0 ] . len ( ) ;
700702 let mut map = match new_join_hashmap ( num_rows, & mut reservation, & self . metrics ) {
701703 Ok ( map) => map,
702- Err ( DataFusionError :: ResourcesExhausted ( _) ) => {
703- return Ok ( self . map . get_or_init ( || None ) . as_deref ( ) ) ;
704- }
704+ Err ( DataFusionError :: ResourcesExhausted ( _) ) => return Ok ( None ) ,
705705 Err ( e) => return Err ( e) ,
706706 } ;
707707 let mut hashes_buffer = vec ! [ 0 ; num_rows] ;
@@ -717,7 +717,7 @@ impl BuildScopeMap {
717717 true ,
718718 NullEquality :: NullEqualsNothing ,
719719 ) ?;
720- Ok ( self . map . get_or_init ( || Some ( map) ) . as_deref ( ) )
720+ Ok ( Some ( self . map . get_or_init ( || map) . as_ref ( ) ) )
721721 }
722722}
723723
@@ -2067,19 +2067,49 @@ mod tests {
20672067 Ok ( ( ) )
20682068 }
20692069
2070- /// A hot scope among rare ones: a batch of rare probe rows, then hot
2071- /// ones , then rare ones again, as the review of
2072- /// <https://github.com/apache/datafusion/pull/26214> found. The rare rows
2073- /// keep the estimated groups small, but the hot group alone saves much
2074- /// work, so the pairing must still switch to groups instead of walking the
2075- /// hot scope once per probe row.
2070+ /// A hot scope among rare ones: ` rare` probe rows of their own scope
2071+ /// each , then `hot` probe rows of the hot scope, then `rare` more of their
2072+ /// own scope. Each rare scope holds one build row, and the hot scope 7,679.
2073+ /// The rare rows keep the estimated groups small, but the hot group alone
2074+ /// saves much work, so the pairing must still switch to groups instead of
2075+ /// walking the hot scope once per probe row.
20762076 #[ test]
20772077 fn hot_scope_among_rare_ones_is_grouped ( ) -> Result < ( ) > {
20782078 // With marks on the probe rows, the average group fills no chunk. With
20792079 // marks on the build rows, the groups hold fewer than two rows on
20802080 // average.
20812081 for ( mark_build_rows, rare, hot) in [ ( false , 256 , 7680 ) , ( true , 4096 , 2048 ) ] {
2082- let stats = hot_scope_among_rare_ones ( mark_build_rows, rare, hot, 7679 ) ?;
2082+ let rare_scopes = rare as u64 ;
2083+ // Scope 0 is hot.
2084+ let build_keys: Vec < u64 > = ( 1 ..=2 * rare_scopes)
2085+ . chain ( std:: iter:: repeat_n ( 0 , 7679 ) )
2086+ . collect ( ) ;
2087+ let probe_keys: Vec < u64 > = ( 1 ..=rare_scopes)
2088+ . chain ( std:: iter:: repeat_n ( 0 , hot) )
2089+ . chain ( rare_scopes + 1 ..=2 * rare_scopes)
2090+ . collect ( ) ;
2091+ let num_marked = if mark_build_rows {
2092+ build_keys. len ( )
2093+ } else {
2094+ probe_keys. len ( )
2095+ } ;
2096+ // Every pair passes, and every scope is on both sides.
2097+ let case = Case {
2098+ mark_build_rows,
2099+ through_scope_map : true ,
2100+ batch_size : 8192 ,
2101+ hash_modulus : u64:: MAX ,
2102+ probe_rows : ( 0 ..probe_keys. len ( ) as u32 ) . collect ( ) ,
2103+ build_rows : ( 0 ..build_keys. len ( ) as u64 ) . collect ( ) ,
2104+ build_keys,
2105+ probe_keys,
2106+ marked_before : vec ! [ false ; num_marked] ,
2107+ filter_seed : 0 ,
2108+ filter_one_in : 1 ,
2109+ foreign_marks : false ,
2110+ } ;
2111+ let ( marks, stats) = case. run ( ) ?;
2112+ assert ! ( marks. iter( ) . all( |marked| * marked) ) ;
20832113 assert ! ( stats. grouped, "marks on build rows: {mark_build_rows}" ) ;
20842114 // The matches of two rounds of lookups per probe row, each until
20852115 // it wastes enough matches to pay for a sort, and a few chunks of
@@ -2097,6 +2127,41 @@ mod tests {
20972127 Ok ( ( ) )
20982128 }
20992129
2130+ /// A scope map that the memory pool declines is built on a later use,
2131+ /// once the pool has room for it.
2132+ #[ test]
2133+ fn declined_scope_map_is_built_once_memory_is_free ( ) -> Result < ( ) > {
2134+ use crate :: metrics:: ExecutionPlanMetricsSet ;
2135+ use datafusion_execution:: memory_pool:: {
2136+ GreedyMemoryPool , MemoryConsumer , MemoryPool ,
2137+ } ;
2138+
2139+ let pool: Arc < dyn MemoryPool > = Arc :: new ( GreedyMemoryPool :: new ( 1 << 20 ) ) ;
2140+ let other = MemoryConsumer :: new ( "other" ) . register ( & pool) ;
2141+ other. try_grow ( 1 << 20 ) ?;
2142+ let scope_map = BuildScopeMap {
2143+ map : OnceLock :: new ( ) ,
2144+ reservation : Mutex :: new ( MemoryConsumer :: new ( "scope map" ) . register ( & pool) ) ,
2145+ metrics : BuildProbeJoinMetrics :: new ( 0 , & ExecutionPlanMetricsSet :: new ( ) ) ,
2146+ } ;
2147+ let scope_values: Vec < ArrayRef > =
2148+ vec ! [ Arc :: new( arrow:: array:: Int32Array :: from( vec![ 1 , 2 , 3 ] ) ) ] ;
2149+ let random_state = RandomState :: with_seed ( 0 ) ;
2150+ assert ! (
2151+ scope_map
2152+ . get_or_try_init( & scope_values, & random_state) ?
2153+ . is_none( )
2154+ ) ;
2155+ other. free ( ) ;
2156+ assert ! (
2157+ scope_map
2158+ . get_or_try_init( & scope_values, & random_state) ?
2159+ . is_some( )
2160+ ) ;
2161+ assert ! ( scope_map. reservation. lock( ) . size( ) > 0 ) ;
2162+ Ok ( ( ) )
2163+ }
2164+
21002165 /// A cross product with marks on the build rows holds at most a batch of
21012166 /// build rows at once, however many build rows there are. No pair passes,
21022167 /// so no row is marked and every build row is paired.
@@ -2151,49 +2216,6 @@ mod tests {
21512216 Ok ( ( ) )
21522217 }
21532218
2154- /// `rare` probe rows of their own scope each, `hot` probe rows of the hot
2155- /// scope, and `rare` more of their own scope, in that order. Each rare
2156- /// scope holds one build row, and the hot scope `hot_build`. Every pair
2157- /// passes, and every scope is on both sides, so every row is marked.
2158- fn hot_scope_among_rare_ones (
2159- mark_build_rows : bool ,
2160- rare : usize ,
2161- hot : usize ,
2162- hot_build : usize ,
2163- ) -> Result < Stats > {
2164- let rare = rare as u64 ;
2165- // Scope 0 is hot.
2166- let build_keys: Vec < u64 > = ( 1 ..=2 * rare)
2167- . chain ( std:: iter:: repeat_n ( 0 , hot_build) )
2168- . collect ( ) ;
2169- let probe_keys: Vec < u64 > = ( 1 ..=rare)
2170- . chain ( std:: iter:: repeat_n ( 0 , hot) )
2171- . chain ( rare + 1 ..=2 * rare)
2172- . collect ( ) ;
2173- let num_marked = if mark_build_rows {
2174- build_keys. len ( )
2175- } else {
2176- probe_keys. len ( )
2177- } ;
2178- let case = Case {
2179- mark_build_rows,
2180- through_scope_map : true ,
2181- batch_size : 8192 ,
2182- hash_modulus : u64:: MAX ,
2183- probe_rows : ( 0 ..probe_keys. len ( ) as u32 ) . collect ( ) ,
2184- build_rows : ( 0 ..build_keys. len ( ) as u64 ) . collect ( ) ,
2185- build_keys,
2186- probe_keys,
2187- marked_before : vec ! [ false ; num_marked] ,
2188- filter_seed : 0 ,
2189- filter_one_in : 1 ,
2190- foreign_marks : false ,
2191- } ;
2192- let ( marks, stats) = case. run ( ) ?;
2193- assert ! ( marks. iter( ) . all( |marked| * marked) ) ;
2194- Ok ( stats)
2195- }
2196-
21972219 /// One scope holds every row, and every pair passes. Returns the matches
21982220 /// that the scope map lookups walked.
21992221 fn walked_matches_in_one_scope (
0 commit comments