@@ -1376,6 +1376,11 @@ fn null_aware_left_mark_column(
13761376/// all build rows with the NULL-valued probe rows. Scope keys narrow these
13771377/// pairs through a hash lookup; without scope keys every pair is a candidate.
13781378/// The join filter, if any, then decides which candidates count.
1379+ ///
1380+ /// A build row stays UNKNOWN once it is marked, so candidates whose build row
1381+ /// is already marked are skipped, and the join filter is not evaluated for
1382+ /// them. Without scope keys this also ends the pairing as soon as no unmarked
1383+ /// build row is left.
13791384#[ expect( clippy:: too_many_arguments) ]
13801385fn mark_null_candidates_for_probe_batch (
13811386 build_side : & BuildSideReadyState ,
@@ -1407,6 +1412,11 @@ fn mark_null_candidates_for_probe_batch(
14071412 // Keeps the candidate pairs that pass the join filter and marks their
14081413 // build rows as UNKNOWN.
14091414 let mut mark = |build_indices : UInt64Array , probe_indices : UInt32Array | {
1415+ let ( build_indices, probe_indices) =
1416+ retain_unmarked ( left_data, build_indices, probe_indices) ;
1417+ if build_indices. is_empty ( ) {
1418+ return Ok ( ( ) ) ;
1419+ }
14101420 let build_indices = match filter {
14111421 Some ( filter) => {
14121422 apply_join_filter_to_indices (
@@ -1463,11 +1473,10 @@ fn mark_null_candidates_for_probe_batch(
14631473 ) ?;
14641474 }
14651475 None => {
1466- let probe_rows =
1467- UInt32Array :: from_iter_values ( 0 ..state. batch . num_rows ( ) as u32 ) ;
1468- for_each_cross_product (
1469- & null_rows. build_indices ,
1470- & probe_rows,
1476+ for_each_unmarked_cross_product (
1477+ left_data,
1478+ null_rows. build_indices . values ( ) . iter ( ) . copied ( ) ,
1479+ 0 ..state. batch . num_rows ( ) as u32 ,
14711480 batch_size,
14721481 & mut mark,
14731482 ) ?;
@@ -1518,11 +1527,10 @@ fn mark_null_candidates_for_probe_batch(
15181527 ) ?;
15191528 }
15201529 None => {
1521- let build_rows =
1522- UInt64Array :: from_iter_values ( 0 ..left_data. batch ( ) . num_rows ( ) as u64 ) ;
1523- for_each_cross_product (
1524- & build_rows,
1525- & null_probe_rows,
1530+ for_each_unmarked_cross_product (
1531+ left_data,
1532+ 0 ..left_data. batch ( ) . num_rows ( ) as u64 ,
1533+ null_probe_rows. values ( ) . iter ( ) . copied ( ) ,
15261534 batch_size,
15271535 & mut mark,
15281536 ) ?;
@@ -1575,32 +1583,70 @@ fn for_each_scope_match(
15751583 Ok ( ( ) )
15761584}
15771585
1578- /// Calls `f` with every pair of `build_rows` x `probe_rows`, as chunks of at
1579- /// most `batch_size` pairs.
1580- fn for_each_cross_product (
1581- build_rows : & UInt64Array ,
1582- probe_rows : & UInt32Array ,
1586+ /// Removes the candidate pairs whose build row is already marked UNKNOWN.
1587+ fn retain_unmarked (
1588+ left_data : & JoinLeftData ,
1589+ build_indices : UInt64Array ,
1590+ probe_indices : UInt32Array ,
1591+ ) -> ( UInt64Array , UInt32Array ) {
1592+ let bitmap = left_data. null_indices_bitmap ( ) . lock ( ) ;
1593+ let is_unmarked = |build_idx : & u64 | !bitmap. get_bit ( * build_idx as usize ) ;
1594+ if build_indices. values ( ) . iter ( ) . all ( is_unmarked) {
1595+ return ( build_indices, probe_indices) ;
1596+ }
1597+ let ( build, probe) : ( Vec < u64 > , Vec < u32 > ) = build_indices
1598+ . values ( )
1599+ . iter ( )
1600+ . zip ( probe_indices. values ( ) . iter ( ) )
1601+ . filter ( |( build_idx, _) | is_unmarked ( build_idx) )
1602+ . unzip ( ) ;
1603+ ( build. into ( ) , probe. into ( ) )
1604+ }
1605+
1606+ /// Calls `f` with the pairs of `build_rows` x `probe_rows` whose build row is
1607+ /// not marked UNKNOWN, as chunks of at most `batch_size` pairs.
1608+ ///
1609+ /// `f` marks build rows, so the unmarked build rows are found again after each
1610+ /// chunk. The pairing stops when no unmarked build row is left.
1611+ fn for_each_unmarked_cross_product (
1612+ left_data : & JoinLeftData ,
1613+ build_rows : impl Iterator < Item = u64 > ,
1614+ probe_rows : impl Iterator < Item = u32 > ,
15831615 batch_size : usize ,
15841616 mut f : impl FnMut ( UInt64Array , UInt32Array ) -> Result < ( ) > ,
15851617) -> Result < ( ) > {
1586- let chunk_size = batch_size
1587- . max ( 1 )
1588- . min ( build_rows. len ( ) . saturating_mul ( probe_rows. len ( ) ) ) ;
1589- let mut build_chunk = Vec :: with_capacity ( chunk_size) ;
1590- let mut probe_chunk = Vec :: with_capacity ( chunk_size) ;
1591- for probe_row in probe_rows. values ( ) {
1592- for build_row in build_rows. values ( ) {
1618+ let retain_unmarked_rows = |rows : & mut Vec < u64 > | {
1619+ let bitmap = left_data. null_indices_bitmap ( ) . lock ( ) ;
1620+ rows. retain ( |idx| !bitmap. get_bit ( * idx as usize ) ) ;
1621+ } ;
1622+
1623+ let mut build_rows: Vec < u64 > = build_rows. collect ( ) ;
1624+ retain_unmarked_rows ( & mut build_rows) ;
1625+
1626+ let batch_size = batch_size. max ( 1 ) ;
1627+ let mut build_chunk = Vec :: with_capacity ( batch_size) ;
1628+ let mut probe_chunk = Vec :: with_capacity ( batch_size) ;
1629+ for probe_row in probe_rows {
1630+ if build_rows. is_empty ( ) {
1631+ break ;
1632+ }
1633+ for build_row in & build_rows {
15931634 build_chunk. push ( * build_row) ;
1594- probe_chunk. push ( * probe_row) ;
1595- if build_chunk. len ( ) == chunk_size {
1635+ probe_chunk. push ( probe_row) ;
1636+ if build_chunk. len ( ) == batch_size {
15961637 f (
1597- std:: mem:: replace ( & mut build_chunk, Vec :: with_capacity ( chunk_size ) )
1638+ std:: mem:: replace ( & mut build_chunk, Vec :: with_capacity ( batch_size ) )
15981639 . into ( ) ,
1599- std:: mem:: replace ( & mut probe_chunk, Vec :: with_capacity ( chunk_size ) )
1640+ std:: mem:: replace ( & mut probe_chunk, Vec :: with_capacity ( batch_size ) )
16001641 . into ( ) ,
16011642 ) ?;
16021643 }
16031644 }
1645+ // Refresh only after a chunk was sent, so the cost of the refresh
1646+ // stays proportional to the pairs already evaluated.
1647+ if build_chunk. is_empty ( ) {
1648+ retain_unmarked_rows ( & mut build_rows) ;
1649+ }
16041650 }
16051651 if !build_chunk. is_empty ( ) {
16061652 f ( build_chunk. into ( ) , probe_chunk. into ( ) ) ?;
0 commit comments