Skip to content

Commit 7162cd7

Browse files
adriangbclaude
andcommitted
perf: skip build rows already marked UNKNOWN in correlated null-aware joins
A build row stays UNKNOWN once it is marked. The candidate pairing now removes pairs whose build row is already marked before it evaluates the join filter. Without scope keys, the cross product also ends when no unmarked build row is left. Co-Authored-By: Claude Opus 5 <[email protected]>
1 parent 31f4dcd commit 7162cd7

1 file changed

Lines changed: 72 additions & 26 deletions

File tree

  • datafusion/physical-plan/src/joins/hash_join

‎datafusion/physical-plan/src/joins/hash_join/stream.rs‎

Lines changed: 72 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -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)]
13801385
fn 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

Comments
 (0)