Skip to content

Commit a60e1af

Browse files
viiryaIsaac
andcommitted
perf: build the null-aware scope map on the first NULL-valued probe row
Only probe rows with a NULL NOT IN value key look up the hash table over the build rows' correlation scope keys. Building it with the build side made every multi-column NOT IN with a NOT NULL element pay for a second hash table over the build side, even when the probe side has no NULL. Co-authored-by: Isaac <[email protected]>
1 parent d0bbf66 commit a60e1af

2 files changed

Lines changed: 131 additions & 37 deletions

File tree

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

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -10579,6 +10579,66 @@ mod tests {
1057910579
Ok(())
1058010580
}
1058110581

10582+
/// The hash table over the build rows' correlation scope keys is only
10583+
/// looked up for probe rows with a NULL value key, so a probe side
10584+
/// without one never builds it, and the result is the same either way.
10585+
#[tokio::test]
10586+
async fn null_aware_scope_map_built_only_for_null_probe_values() -> Result<()> {
10587+
async fn run(probe_ids: Vec<Option<i32>>) -> Result<(usize, usize)> {
10588+
let build_rows = 10_000;
10589+
let left = build_table_two_cols(
10590+
("id", &(0..build_rows).map(|i| Some(i * 2)).collect()),
10591+
("grp", &(0..build_rows).map(|i| Some(i % 100)).collect()),
10592+
);
10593+
let probe_grps = (0..probe_ids.len() as i32).map(Some).collect();
10594+
let right = build_table_two_cols(("id", &probe_ids), ("grp", &probe_grps));
10595+
let on = vec![
10596+
(
10597+
Arc::new(Column::new_with_schema("id", &left.schema())?) as _,
10598+
Arc::new(Column::new_with_schema("id", &right.schema())?) as _,
10599+
),
10600+
(
10601+
Arc::new(Column::new_with_schema("grp", &left.schema())?) as _,
10602+
Arc::new(Column::new_with_schema("grp", &right.schema())?) as _,
10603+
),
10604+
];
10605+
let join = HashJoinExec::try_new(
10606+
left,
10607+
right,
10608+
on,
10609+
None,
10610+
&JoinType::LeftAnti,
10611+
None,
10612+
PartitionMode::CollectLeft,
10613+
NullEquality::NullEqualsNothing,
10614+
true,
10615+
)?;
10616+
let batches =
10617+
common::collect(join.execute(0, prepare_task_ctx(8192, false))?).await?;
10618+
let rows = batches.iter().map(|b| b.num_rows()).sum();
10619+
let build_mem_used = join
10620+
.metrics()
10621+
.unwrap()
10622+
.sum_by_name("build_mem_used")
10623+
.unwrap()
10624+
.as_usize();
10625+
Ok((rows, build_mem_used))
10626+
}
10627+
10628+
// `(0, 0)` matches the build row `(0, 0)`; `(1, 1)` matches nothing.
10629+
let (rows, without_null) = run(vec![Some(0), Some(1)]).await?;
10630+
assert_eq!(rows, 9_999);
10631+
// `(NULL, 1)` makes the 100 build rows with `grp = 1` UNKNOWN.
10632+
let (rows, with_null) = run(vec![Some(0), None]).await?;
10633+
assert_eq!(rows, 9_899);
10634+
// The scope map holds a bucket and a chain entry for every build row.
10635+
assert!(
10636+
with_null >= without_null + 10_000 * size_of::<u32>(),
10637+
"{without_null} -> {with_null}"
10638+
);
10639+
Ok(())
10640+
}
10641+
1058210642
/// `left.z > right.z` over the second column of two-column tables: the
1058310643
/// non-equality correlation of
1058410644
/// `id NOT IN (SELECT r.id FROM r WHERE r.z < l.z)`.

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

Lines changed: 71 additions & 37 deletions
Original file line numberDiff line numberDiff line change
@@ -33,7 +33,7 @@
3333
//! - [`NotInBuild::final_chunk`] on each chunk of build rows emitted after
3434
//! the probe side is exhausted.
3535
36-
use std::sync::Arc;
36+
use std::sync::{Arc, OnceLock};
3737

3838
use parking_lot::Mutex;
3939

@@ -59,7 +59,7 @@ use crate::joins::join_hash_map::{JoinHashMapType, ProbeOffset};
5959
use crate::joins::probe_completion::ProbeSideSummary;
6060
use crate::joins::utils::{
6161
BuildProbeJoinMetrics, JoinFilter, apply_join_filter_to_indices,
62-
equal_rows_arr_with_normalized_left, matchable_join_keys, update_hash,
62+
equal_rows_arr_with_normalized_left, matchable_join_keys,
6363
};
6464

6565
/// Which `NOT IN` a null-aware join computes, derived from
@@ -181,9 +181,9 @@ pub(super) enum NotInBuild {
181181
/// One bit per build row, set once its mark is UNKNOWN; shared by
182182
/// every probe partition, and never cleared.
183183
unknown: SharedBitmapBuilder,
184-
/// Hash table over the scope keys (`on[value_keys..]`) of all build
185-
/// rows, probed with NULL-valued probe rows. `None` without scope keys.
186-
scope_map: Option<Box<dyn JoinHashMapType>>,
184+
/// Hash table over the scope keys of all build rows, probed with
185+
/// NULL-valued probe rows. `None` without scope keys.
186+
scope_map: Option<BuildScopeMap>,
187187
/// The build rows with a NULL value key, `None` when there are none.
188188
null_value_rows: Option<NullValueBuildRows>,
189189
},
@@ -200,7 +200,7 @@ pub(super) enum NotInBuild {
200200
/// The fields are those of [`Self::BuildRowsCorrelated`].
201201
ProbeRowsCorrelated {
202202
value_keys: usize,
203-
scope_map: Option<Box<dyn JoinHashMapType>>,
203+
scope_map: Option<BuildScopeMap>,
204204
null_value_rows: Option<NullValueBuildRows>,
205205
},
206206
/// Uncorrelated [`NotIn::ProbeRows`].
@@ -229,7 +229,6 @@ impl NotInBuild {
229229
let correlated_row_state = |value_keys, reservation: &mut MemoryReservation| {
230230
correlated_row_state(
231231
on_left,
232-
batch,
233232
keys,
234233
normalized,
235234
value_keys,
@@ -478,7 +477,7 @@ impl NotInProbe {
478477
mark_null_candidates_for_probe_batch(
479478
left_data,
480479
UnknownMarks::Build(unknown),
481-
scope_map.as_deref(),
480+
scope_map.as_ref(),
482481
null_value_rows.as_ref(),
483482
probe_batch,
484483
probe_values,
@@ -516,7 +515,7 @@ impl NotInProbe {
516515
mark_null_candidates_for_probe_batch(
517516
left_data,
518517
UnknownMarks::Probe(&unknown),
519-
scope_map.as_deref(),
518+
scope_map.as_ref(),
520519
null_value_rows.as_ref(),
521520
probe_batch,
522521
probe_values,
@@ -601,42 +600,23 @@ fn retain_probe_rows(
601600
}
602601

603602
/// The scope map and NULL-valued build rows of a correlated `NOT IN`.
604-
#[expect(clippy::too_many_arguments, clippy::type_complexity)]
605603
fn correlated_row_state(
606604
on_left: &[PhysicalExprRef],
607-
batch: &RecordBatch,
608605
keys: &[ArrayRef],
609606
normalized: &[ArrayRef],
610607
value_keys: usize,
611608
random_state: &RandomState,
612609
reservation: &mut MemoryReservation,
613610
metrics: &BuildProbeJoinMetrics,
614-
) -> Result<(Option<Box<dyn JoinHashMapType>>, Option<NullValueBuildRows>)> {
615-
let num_rows = batch.num_rows();
611+
) -> Result<(Option<BuildScopeMap>, Option<NullValueBuildRows>)> {
616612
// `on_left[..V]` are the value keys and `on_left[V..]` the (possibly
617613
// empty) correlation scope keys.
618614
let scope_keys = &on_left[value_keys..];
619-
let scope_map = if scope_keys.is_empty() {
620-
None
621-
} else {
622-
// Scope-only NULL marking uses a HashMap (the primary join map may
623-
// use ArrayMap for full-key matches, but scope keys have arbitrary
624-
// shape).
625-
let mut scope_map = new_join_hashmap(num_rows, reservation, metrics)?;
626-
let mut hashes_buffer = vec![0; num_rows];
627-
update_hash(
628-
scope_keys,
629-
batch,
630-
&mut *scope_map,
631-
0,
632-
random_state,
633-
&mut hashes_buffer,
634-
0,
635-
true,
636-
NullEquality::NullEqualsNothing,
637-
)?;
638-
Some(scope_map)
639-
};
615+
let scope_map = (!scope_keys.is_empty()).then(|| BuildScopeMap {
616+
map: OnceLock::new(),
617+
reservation: Mutex::new(reservation.new_empty()),
618+
metrics: metrics.clone(),
619+
});
640620

641621
let Some(null_mask) = null_value_key_mask(&keys[..value_keys]) else {
642622
return Ok((scope_map, None));
@@ -672,6 +652,54 @@ fn correlated_row_state(
672652
))
673653
}
674654

655+
/// Hash table over the correlation scope keys (`on[value_keys..]`) of all
656+
/// build rows, used by correlated `NOT IN` (see [`NotInScope::Correlated`]).
657+
///
658+
/// Only the probe rows with a NULL value key look it up, so it is built on
659+
/// the first such probe row rather than with the build side: a probe side
660+
/// without NULLs never pays for a second hash table over the build side.
661+
pub(super) struct BuildScopeMap {
662+
map: OnceLock<Box<dyn JoinHashMapType>>,
663+
/// Charged for the map once it is built. Its lock also makes the probe
664+
/// partitions build the map only once.
665+
reservation: Mutex<MemoryReservation>,
666+
metrics: BuildProbeJoinMetrics,
667+
}
668+
669+
impl BuildScopeMap {
670+
/// Returns the map, building it on first use from `scope_values`, the
671+
/// build side's scope keys (`JoinLeftData::values()[value_keys..]`).
672+
fn get_or_try_init(
673+
&self,
674+
scope_values: &[ArrayRef],
675+
random_state: &RandomState,
676+
) -> Result<&dyn JoinHashMapType> {
677+
if let Some(map) = self.map.get() {
678+
return Ok(map.as_ref());
679+
}
680+
let mut reservation = self.reservation.lock();
681+
if let Some(map) = self.map.get() {
682+
return Ok(map.as_ref());
683+
}
684+
// Scope-only NULL marking uses a HashMap (the primary join map may
685+
// use ArrayMap for full-key matches, but scope keys have arbitrary
686+
// shape).
687+
let num_rows = scope_values[0].len();
688+
let mut map = new_join_hashmap(num_rows, &mut reservation, &self.metrics)?;
689+
let mut hashes_buffer = vec![0; num_rows];
690+
create_hashes(scope_values, random_state, &mut hashes_buffer)?;
691+
map.extend_zero(num_rows);
692+
// A build row whose scope keys hold a NULL is in no scope.
693+
let valid = matchable_join_keys(scope_values, NullEquality::NullEqualsNothing);
694+
let hashes = hashes_buffer
695+
.iter()
696+
.enumerate()
697+
.filter(|(i, _)| valid.as_ref().is_none_or(|valid| valid.is_valid(*i)));
698+
map.update_from_iter(Box::new(hashes.rev()), 0);
699+
Ok(self.map.get_or_init(|| map).as_ref())
700+
}
701+
}
702+
675703
/// The build rows with a NULL `NOT IN` value key (in any element of a
676704
/// multi-column key), used by correlated `NOT IN` (see [`NotInScope::Correlated`]).
677705
///
@@ -763,7 +791,7 @@ impl<'a> UnknownMarks<'a> {
763791
fn mark_null_candidates_for_probe_batch(
764792
left_data: &JoinLeftData,
765793
marks: UnknownMarks<'_>,
766-
scope_map: Option<&dyn JoinHashMapType>,
794+
scope_map: Option<&BuildScopeMap>,
767795
null_value_build_rows: Option<&NullValueBuildRows>,
768796
probe_batch: &RecordBatch,
769797
probe_values: &[ArrayRef],
@@ -893,14 +921,20 @@ fn mark_null_candidates_for_probe_batch(
893921
// Case 2: NULL-valued probe rows paired with the build rows in their
894922
// correlation scope.
895923
if let Some(null_mask) = probe_null_value_mask {
896-
let null_probe_rows = null_mask
924+
let mut null_probe_rows = null_mask
897925
.values()
898926
.set_indices()
899927
.map(|i| i as u32)
900-
.filter(in_scope);
928+
.filter(in_scope)
929+
.peekable();
901930

902931
match scope_map {
932+
// No NULL-valued probe row is in any scope: nothing to look up,
933+
// so the scope map need not be built.
934+
Some(_) if null_probe_rows.peek().is_none() => {}
903935
Some(scope_map) => {
936+
let scope_map =
937+
scope_map.get_or_try_init(build_scope_values, random_state)?;
904938
let mut pairs =
905939
UnmarkedPairs::new(marks, batch_size, &mut mark_scope_matches);
906940
pairs.scope_matches(

0 commit comments

Comments
 (0)