@@ -43,6 +43,7 @@ use arrow::array::{
4343} ;
4444use arrow:: buffer:: { BooleanBuffer , NullBuffer } ;
4545use arrow:: compute:: { filter, filter_record_batch, take} ;
46+ use arrow:: util:: bit_iterator:: BitIndexIterator ;
4647use arrow:: util:: bit_util;
4748use datafusion_common:: hash_utils:: { RandomState , create_hashes} ;
4849use datafusion_common:: {
@@ -922,7 +923,8 @@ fn mark_null_candidates_for_probe_batch(
922923 // Case 1: NULL-valued build rows paired with the probe rows in their
923924 // correlation scope.
924925 if let Some ( null_rows) = null_value_build_rows {
925- let probe_rows = || ( 0 ..probe_batch. num_rows ( ) as u32 ) . filter ( in_scope) ;
926+ let probe_rows =
927+ |start : u32 | ( start..probe_batch. num_rows ( ) as u32 ) . filter ( in_scope) ;
926928 match & null_rows. scope {
927929 NullValueScope :: Map ( scope_map) => {
928930 let mut pairs =
@@ -932,7 +934,7 @@ fn mark_null_candidates_for_probe_batch(
932934 pairs. scope_matches (
933935 scope_map. as_ref ( ) ,
934936 |position| null_rows. build_indices . value ( position as usize ) ,
935- probe_rows ( ) ,
937+ probe_rows ( 0 ) ,
936938 hashes_buffer,
937939 lookup,
938940 ) ?;
@@ -961,26 +963,30 @@ fn mark_null_candidates_for_probe_batch(
961963 // Case 2: NULL-valued probe rows paired with the build rows in their
962964 // correlation scope.
963965 if let Some ( null_mask) = probe_null_value_mask {
964- let null_probe_rows = || {
965- null_mask
966- . values ( )
967- . set_indices ( )
968- . map ( |i| i as u32 )
969- . filter ( in_scope)
966+ let null_probe_rows = |start : u32 | {
967+ let values = null_mask. values ( ) ;
968+ let start = start as usize ;
969+ BitIndexIterator :: new (
970+ values. values ( ) ,
971+ values. offset ( ) + start,
972+ values. len ( ) - start,
973+ )
974+ . map ( move |i| ( start + i) as u32 )
975+ . filter ( in_scope)
970976 } ;
971977
972978 match scope_map {
973979 // No NULL-valued probe row is in any scope: nothing to look up,
974980 // so the scope map need not be built.
975- Some ( _) if null_probe_rows ( ) . next ( ) . is_none ( ) => { }
981+ Some ( _) if null_probe_rows ( 0 ) . next ( ) . is_none ( ) => { }
976982 Some ( scope_map) => {
977983 let mut pairs =
978984 UnmarkedPairs :: new ( marks, batch_size, & mut mark_scope_matches) ;
979985 match scope_map. get_or_try_init ( build_scope_values, random_state) ? {
980986 Some ( scope_map) => pairs. scope_matches (
981987 scope_map,
982988 |build_row| build_row,
983- null_probe_rows ( ) ,
989+ null_probe_rows ( 0 ) ,
984990 hashes_buffer,
985991 lookup,
986992 ) ?,
@@ -1239,35 +1245,42 @@ where
12391245 }
12401246 }
12411247
1242- /// Pairs each of the rows that `probe_rows` yields with each of
1243- /// `build_rows`. The pairing stops when every row that the pairs decide
1244- /// is marked.
1248+ /// Pairs each of the rows that `probe_rows(0)` yields with each of
1249+ /// `build_rows`. `probe_rows(start)` yields the probe rows from `start` on,
1250+ /// in increasing order. The pairing stops when every row that the pairs
1251+ /// decide is marked.
12451252 ///
12461253 /// When the pairs decide the build rows, the unmarked build rows are
12471254 /// paired in chunks of `batch_size` rows. Neither side is then held
12481255 /// whole: a large build side, as when this pairing stands in for a scope
12491256 /// map that the memory pool declined, or a probe batch larger than the
12501257 /// batch size. The first `batch_size` probe rows are kept for every
1251- /// chunk. The rest are produced again by calling `probe_rows` , only for
1252- /// a chunk that still has unmarked rows after the kept ones, which then
1258+ /// chunk. The rest are produced again from the first of them , only for a
1259+ /// chunk that still has unmarked rows after the kept ones, which then
12531260 /// costs less than pairing them with the chunk. A chunk is filled with
12541261 /// unmarked rows only, so a build side with few unmarked rows left pairs
12551262 /// them all at once, as a single chunk would.
12561263 fn cross_product < P : Iterator < Item = u32 > > (
12571264 & mut self ,
12581265 build_rows : impl Iterator < Item = u64 > ,
1259- probe_rows : impl Fn ( ) -> P ,
1266+ probe_rows : impl Fn ( u32 ) -> P ,
12601267 ) -> Result < ( ) > {
12611268 match self . marks {
12621269 UnknownMarks :: Build ( bitmap) => {
12631270 // The probe rows can be spread over a large probe batch, so
12641271 // keep the first ones rather than walk the batch for every
12651272 // chunk. The first ones often mark the whole chunk.
1266- let kept: Vec < u32 > = probe_rows ( ) . take ( self . batch_size ) . collect ( ) ;
1273+ let mut kept: Vec < u32 > =
1274+ probe_rows ( 0 ) . take ( self . batch_size + 1 ) . collect ( ) ;
12671275 if kept. is_empty ( ) {
12681276 return Ok ( ( ) ) ;
12691277 }
1270- let more_probe_rows = kept. len ( ) == self . batch_size ;
1278+ // The first probe row past the kept ones, if any.
1279+ let rest_start = if kept. len ( ) > self . batch_size {
1280+ kept. pop ( )
1281+ } else {
1282+ None
1283+ } ;
12711284 let mut build_rows = build_rows. peekable ( ) ;
12721285 let mut chunk = Vec :: with_capacity ( self . batch_size ) ;
12731286 while build_rows. peek ( ) . is_some ( ) {
@@ -1284,20 +1297,20 @@ where
12841297 // The chunk holds no row marked so far.
12851298 self . needs_refresh = false ;
12861299 self . pair_unmarked ( & mut chunk, kept. iter ( ) . copied ( ) , |b, p| ( b, p) ) ?;
1287- if more_probe_rows {
1288- self . pair_unmarked (
1289- & mut chunk,
1290- probe_rows ( ) . skip ( kept. len ( ) ) ,
1291- |b, p| ( b, p) ,
1292- ) ?;
1300+ if let Some ( start) = rest_start
1301+ && self . refresh ( & mut chunk)
1302+ {
1303+ self . pair_unmarked ( & mut chunk, probe_rows ( start) , |b, p| ( b, p) ) ?;
12931304 }
12941305 }
12951306 Ok ( ( ) )
12961307 }
12971308 UnknownMarks :: Probe ( _) => {
12981309 // Drop the rows that are already marked before the first pair.
12991310 self . needs_refresh = true ;
1300- self . pair_unmarked ( & mut probe_rows ( ) . collect ( ) , build_rows, |p, b| ( b, p) )
1311+ self . pair_unmarked ( & mut probe_rows ( 0 ) . collect ( ) , build_rows, |p, b| {
1312+ ( b, p)
1313+ } )
13011314 }
13021315 }
13031316 }
@@ -1711,17 +1724,7 @@ where
17111724 {
17121725 self . max_decided_rows = self . max_decided_rows . max ( decided_rows. len ( ) ) ;
17131726 }
1714- loop {
1715- // Refresh only after a chunk was sent, so the cost of the refresh
1716- // stays proportional to the pairs already evaluated.
1717- if self . needs_refresh {
1718- let bitmap = self . marks . bitmap ( ) . lock ( ) ;
1719- decided_rows. retain ( |row| !bitmap. get_bit ( ( * row) . into ( ) as usize ) ) ;
1720- self . needs_refresh = false ;
1721- }
1722- if decided_rows. is_empty ( ) {
1723- break ;
1724- }
1727+ while self . refresh ( decided_rows) {
17251728 let Some ( other_row) = other_rows. next ( ) else {
17261729 break ;
17271730 } ;
@@ -1733,6 +1736,19 @@ where
17331736 Ok ( ( ) )
17341737 }
17351738
1739+ /// Drops the rows of `decided_rows` that are marked, if a chunk was sent
1740+ /// since they were last checked, and returns whether any are left.
1741+ fn refresh < D : Copy + Into < u64 > > ( & mut self , decided_rows : & mut Vec < D > ) -> bool {
1742+ // Refresh only after a chunk was sent, so the cost of the refresh
1743+ // stays proportional to the pairs already evaluated.
1744+ if self . needs_refresh {
1745+ let bitmap = self . marks . bitmap ( ) . lock ( ) ;
1746+ decided_rows. retain ( |row| !bitmap. get_bit ( ( * row) . into ( ) as usize ) ) ;
1747+ self . needs_refresh = false ;
1748+ }
1749+ !decided_rows. is_empty ( )
1750+ }
1751+
17361752 /// Pushes the pairs of `build_rows` and `probe_rows`.
17371753 fn push_all ( & mut self , mut build_rows : & [ u64 ] , mut probe_rows : & [ u32 ] ) -> Result < ( ) > {
17381754 while !build_rows. is_empty ( ) {
@@ -1780,6 +1796,7 @@ mod tests {
17801796 use crate :: joins:: join_hash_map:: JoinHashMapU64 ;
17811797 use rand:: rngs:: StdRng ;
17821798 use rand:: { Rng , SeedableRng } ;
1799+ use std:: cell:: Cell ;
17831800
17841801 /// The input of one run of [`UnmarkedPairs`]. Each row has a scope key,
17851802 /// and the hash of a key is `key % hash_modulus`, so different scopes can
@@ -1937,7 +1954,7 @@ mod tests {
19371954 Ok ( ( ) )
19381955 } ;
19391956
1940- let probe_walks = std :: cell :: Cell :: new ( 0 ) ;
1957+ let ( probe_walks, probe_reads ) = ( Cell :: new ( 0 ) , Cell :: new ( 0 ) ) ;
19411958 let mut pairs = UnmarkedPairs :: new ( marks, self . batch_size , mark) ;
19421959 if self . through_scope_map {
19431960 let mut scope_map = JoinHashMapU64 :: with_capacity ( self . build_rows . len ( ) ) ;
@@ -1958,15 +1975,14 @@ mod tests {
19581975 & mut LookupBuffers :: default ( ) ,
19591976 ) ?;
19601977 } else {
1961- let probe_walks = & probe_walks;
1962- pairs. cross_product ( self . build_rows . iter ( ) . copied ( ) , || {
1963- let mut walked = false ;
1964- self . probe_rows . iter ( ) . copied ( ) . inspect ( move |_| {
1965- if !walked {
1966- walked = true ;
1967- probe_walks. set ( probe_walks. get ( ) + 1 ) ;
1968- }
1969- } )
1978+ let probe_reads = & probe_reads;
1979+ pairs. cross_product ( self . build_rows . iter ( ) . copied ( ) , |start| {
1980+ probe_walks. set ( probe_walks. get ( ) + 1 ) ;
1981+ let from = self . probe_rows . partition_point ( |row| * row < start) ;
1982+ self . probe_rows [ from..]
1983+ . iter ( )
1984+ . copied ( )
1985+ . inspect ( move |_| probe_reads. set ( probe_reads. get ( ) + 1 ) )
19701986 } ) ?;
19711987 }
19721988 let ( considered_groups, grouped) = ( pairs. considered_groups , pairs. grouped ) ;
@@ -1988,6 +2004,7 @@ mod tests {
19882004 sends,
19892005 sent_pairs,
19902006 probe_walks : probe_walks. get ( ) ,
2007+ probe_reads : probe_reads. get ( ) ,
19912008 foreign_marks,
19922009 } ,
19932010 ) )
@@ -2005,8 +2022,10 @@ mod tests {
20052022 /// The chunks of pairs sent, and the pairs in them.
20062023 sends : usize ,
20072024 sent_pairs : usize ,
2008- /// The walks of the `probe_rows` of a cross product that produce a row.
2025+ /// The calls of the `probe_rows` of a cross product, and the probe rows
2026+ /// they produced.
20092027 probe_walks : usize ,
2028+ probe_reads : usize ,
20102029 /// The rows that `foreign_marks` marked.
20112030 foreign_marks : Vec < usize > ,
20122031 }
@@ -2219,17 +2238,31 @@ mod tests {
22192238 assert ! ( !marks. contains( & true ) ) ;
22202239 assert_eq ! ( stats. max_decided_rows, batch_size) ;
22212240 // The three probe rows are kept for all 157 chunks.
2222- assert_eq ! ( stats. probe_walks, 1 ) ;
2223- // The probe rows past the kept ones are produced again for each chunk
2224- // that the kept ones leave with unmarked rows.
2241+ let num_chunks = num_build. div_ceil ( batch_size) ;
2242+ assert_eq ! ( ( stats. probe_walks, stats. probe_reads) , ( 1 , 3 ) ) ;
2243+ // A batch of probe rows is kept too, and nothing follows it.
2244+ let ( marks, stats) = Case {
2245+ probe_keys : vec ! [ 0 ; batch_size] ,
2246+ probe_rows : ( 0 ..batch_size as u32 ) . collect ( ) ,
2247+ ..case. clone ( )
2248+ }
2249+ . run ( ) ?;
2250+ assert ! ( !marks. contains( & true ) ) ;
2251+ assert_eq ! ( ( stats. probe_walks, stats. probe_reads) , ( 1 , batch_size) ) ;
2252+ // The probe rows past the kept ones are produced again, from the
2253+ // first of them, for each chunk that the kept ones leave with unmarked
2254+ // rows.
22252255 let ( marks, stats) = Case {
22262256 probe_keys : vec ! [ 0 ; batch_size + 1 ] ,
22272257 probe_rows : ( 0 ..=batch_size as u32 ) . collect ( ) ,
22282258 ..case. clone ( )
22292259 }
22302260 . run ( ) ?;
22312261 assert ! ( !marks. contains( & true ) ) ;
2232- assert_eq ! ( stats. probe_walks, 1 + num_build. div_ceil( batch_size) ) ;
2262+ assert_eq ! (
2263+ ( stats. probe_walks, stats. probe_reads) ,
2264+ ( 1 + num_chunks, batch_size + 1 + num_chunks)
2265+ ) ;
22332266 // When the kept probe rows mark each chunk, the rest are not produced
22342267 // again.
22352268 let ( marks, stats) = Case {
@@ -2240,7 +2273,7 @@ mod tests {
22402273 }
22412274 . run ( ) ?;
22422275 assert ! ( !marks. contains( & false ) ) ;
2243- assert_eq ! ( stats. probe_walks, 1 ) ;
2276+ assert_eq ! ( ( stats. probe_walks, stats . probe_reads ) , ( 1 , batch_size + 1 ) ) ;
22442277 Ok ( ( ) )
22452278 }
22462279
0 commit comments