Skip to content

Commit 05b4c9f

Browse files
viiryaIsaac
andcommitted
fix: find the rest of the probe rows from where they start
A cross product reads one probe row past the kept ones. Only if it exists is the rest of the probe rows produced again for a chunk with unmarked rows, and from that row on rather than from the start of the batch. Co-authored-by: Isaac <[email protected]>
1 parent 853f419 commit 05b4c9f

2 files changed

Lines changed: 136 additions & 52 deletions

File tree

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

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -11015,6 +11015,57 @@ mod tests {
1101511015
Ok(())
1101611016
}
1101711017

11018+
/// A probe batch with more NULL-valued rows than the batch size, spread
11019+
/// among other rows. The NULL-valued rows past the first batch of them
11020+
/// decide `(3, 7)` and `(4, 9)`, so the pairing must find them again at
11021+
/// their own rows for every chunk of build rows that the first batch
11022+
/// leaves undecided.
11023+
#[apply(hash_join_exec_configs)]
11024+
#[tokio::test]
11025+
async fn test_null_aware_left_anti_multi_column_null_probe_rows_past_batch(
11026+
batch_size: usize,
11027+
) -> Result<()> {
11028+
let task_ctx = prepare_task_ctx(batch_size, false);
11029+
let left = build_table_two_cols(
11030+
("a", &vec![Some(3), Some(4), Some(6)]),
11031+
("b", &vec![Some(7), Some(9), Some(6)]),
11032+
);
11033+
let right = build_table_two_cols(
11034+
("a", &vec![Some(1), None, None, Some(5), None, None]),
11035+
(
11036+
"b",
11037+
&vec![Some(1), Some(8), Some(8), Some(5), Some(7), Some(9)],
11038+
),
11039+
);
11040+
let on = ["a", "b"]
11041+
.into_iter()
11042+
.map(|name| {
11043+
Ok((
11044+
Arc::new(Column::new_with_schema(name, &left.schema())?) as _,
11045+
Arc::new(Column::new_with_schema(name, &right.schema())?) as _,
11046+
))
11047+
})
11048+
.collect::<Result<JoinOn>>()?;
11049+
// Both elements are value keys, so the NULL-valued probe rows are
11050+
// paired with every build row.
11051+
let join = HashJoinExecBuilder::new(left, right, on, JoinType::LeftAnti)
11052+
.with_partition_mode(PartitionMode::CollectLeft)
11053+
.with_null_aware(true)
11054+
.with_null_aware_value_keys(2)
11055+
.build()?;
11056+
let batches = common::collect(join.execute(0, task_ctx)?).await?;
11057+
allow_duplicates! {
11058+
assert_snapshot!(batches_to_sort_string(&batches), @r"
11059+
+---+---+
11060+
| a | b |
11061+
+---+---+
11062+
| 6 | 6 |
11063+
+---+---+
11064+
");
11065+
}
11066+
Ok(())
11067+
}
11068+
1101811069
/// Swaps a null-aware `LeftAnti` into the `RightAnti` that `JoinSelection`
1101911070
/// plans, with its own build state so that both can be executed.
1102011071
fn swap_for_separate_execution(

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

Lines changed: 85 additions & 52 deletions
Original file line numberDiff line numberDiff line change
@@ -43,6 +43,7 @@ use arrow::array::{
4343
};
4444
use arrow::buffer::{BooleanBuffer, NullBuffer};
4545
use arrow::compute::{filter, filter_record_batch, take};
46+
use arrow::util::bit_iterator::BitIndexIterator;
4647
use arrow::util::bit_util;
4748
use datafusion_common::hash_utils::{RandomState, create_hashes};
4849
use 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

Comments
 (0)