Skip to content

Commit 043950b

Browse files
viiryaIsaac
andcommitted
fix: retry a declined scope map on the next NULL-valued probe batch
A scope map that the memory pool declined was cached as `None` for the rest of the query, so every later NULL-valued probe batch paired with every build row even after the pool freed memory. Only a built map is cached now. A declined attempt costs one `try_grow`, as the map is reserved before it is allocated. Also inlines `hot_scope_among_rare_ones` into its only test and drops the PR history from that test's doc. Co-authored-by: Isaac <[email protected]>
1 parent 8f2cb12 commit 043950b

1 file changed

Lines changed: 82 additions & 60 deletions

File tree

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

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

Lines changed: 82 additions & 60 deletions
Original file line numberDiff line numberDiff line change
@@ -667,10 +667,12 @@ fn correlated_row_state(
667667
/// rows in their scope. So when the memory pool cannot hold it, the join
668668
/// pairs them with every build row instead, and compares their scope keys.
669669
/// That is the pairing of a join whose tuple elements are all value keys,
670-
/// which needs no map either.
670+
/// which needs no map either. The next probe batch with such rows tries to
671+
/// build the map again.
671672
pub(super) struct BuildScopeMap {
672-
/// `None` when the memory pool could not hold the map.
673-
map: OnceLock<Option<Box<dyn JoinHashMapType>>>,
673+
/// Set once the memory pool holds the map. Until then each use tries to
674+
/// reserve it again, as the pool may have freed memory since.
675+
map: OnceLock<Box<dyn JoinHashMapType>>,
674676
/// Charged for the map once it is built. Its lock also makes the probe
675677
/// partitions build the map only once.
676678
reservation: Mutex<MemoryReservation>,
@@ -680,28 +682,26 @@ pub(super) struct BuildScopeMap {
680682
impl BuildScopeMap {
681683
/// Returns the map, building it on first use from `scope_values`, the
682684
/// build side's scope keys (`JoinLeftData::values()[value_keys..]`).
683-
/// Returns `None` when the memory pool cannot hold it.
685+
/// Returns `None` when the memory pool cannot hold it yet.
684686
fn get_or_try_init(
685687
&self,
686688
scope_values: &[ArrayRef],
687689
random_state: &RandomState,
688690
) -> Result<Option<&dyn JoinHashMapType>> {
689691
if let Some(map) = self.map.get() {
690-
return Ok(map.as_deref());
692+
return Ok(Some(map.as_ref()));
691693
}
692694
let mut reservation = self.reservation.lock();
693695
if let Some(map) = self.map.get() {
694-
return Ok(map.as_deref());
696+
return Ok(Some(map.as_ref()));
695697
}
696698
// Scope-only NULL marking uses a HashMap (the primary join map may
697699
// use ArrayMap for full-key matches, but scope keys have arbitrary
698700
// shape).
699701
let num_rows = scope_values[0].len();
700702
let mut map = match new_join_hashmap(num_rows, &mut reservation, &self.metrics) {
701703
Ok(map) => map,
702-
Err(DataFusionError::ResourcesExhausted(_)) => {
703-
return Ok(self.map.get_or_init(|| None).as_deref());
704-
}
704+
Err(DataFusionError::ResourcesExhausted(_)) => return Ok(None),
705705
Err(e) => return Err(e),
706706
};
707707
let mut hashes_buffer = vec![0; num_rows];
@@ -717,7 +717,7 @@ impl BuildScopeMap {
717717
true,
718718
NullEquality::NullEqualsNothing,
719719
)?;
720-
Ok(self.map.get_or_init(|| Some(map)).as_deref())
720+
Ok(Some(self.map.get_or_init(|| map).as_ref()))
721721
}
722722
}
723723

@@ -2067,19 +2067,49 @@ mod tests {
20672067
Ok(())
20682068
}
20692069

2070-
/// A hot scope among rare ones: a batch of rare probe rows, then hot
2071-
/// ones, then rare ones again, as the review of
2072-
/// <https://github.com/apache/datafusion/pull/26214> found. The rare rows
2073-
/// keep the estimated groups small, but the hot group alone saves much
2074-
/// work, so the pairing must still switch to groups instead of walking the
2075-
/// hot scope once per probe row.
2070+
/// A hot scope among rare ones: `rare` probe rows of their own scope
2071+
/// each, then `hot` probe rows of the hot scope, then `rare` more of their
2072+
/// own scope. Each rare scope holds one build row, and the hot scope 7,679.
2073+
/// The rare rows keep the estimated groups small, but the hot group alone
2074+
/// saves much work, so the pairing must still switch to groups instead of
2075+
/// walking the hot scope once per probe row.
20762076
#[test]
20772077
fn hot_scope_among_rare_ones_is_grouped() -> Result<()> {
20782078
// With marks on the probe rows, the average group fills no chunk. With
20792079
// marks on the build rows, the groups hold fewer than two rows on
20802080
// average.
20812081
for (mark_build_rows, rare, hot) in [(false, 256, 7680), (true, 4096, 2048)] {
2082-
let stats = hot_scope_among_rare_ones(mark_build_rows, rare, hot, 7679)?;
2082+
let rare_scopes = rare as u64;
2083+
// Scope 0 is hot.
2084+
let build_keys: Vec<u64> = (1..=2 * rare_scopes)
2085+
.chain(std::iter::repeat_n(0, 7679))
2086+
.collect();
2087+
let probe_keys: Vec<u64> = (1..=rare_scopes)
2088+
.chain(std::iter::repeat_n(0, hot))
2089+
.chain(rare_scopes + 1..=2 * rare_scopes)
2090+
.collect();
2091+
let num_marked = if mark_build_rows {
2092+
build_keys.len()
2093+
} else {
2094+
probe_keys.len()
2095+
};
2096+
// Every pair passes, and every scope is on both sides.
2097+
let case = Case {
2098+
mark_build_rows,
2099+
through_scope_map: true,
2100+
batch_size: 8192,
2101+
hash_modulus: u64::MAX,
2102+
probe_rows: (0..probe_keys.len() as u32).collect(),
2103+
build_rows: (0..build_keys.len() as u64).collect(),
2104+
build_keys,
2105+
probe_keys,
2106+
marked_before: vec![false; num_marked],
2107+
filter_seed: 0,
2108+
filter_one_in: 1,
2109+
foreign_marks: false,
2110+
};
2111+
let (marks, stats) = case.run()?;
2112+
assert!(marks.iter().all(|marked| *marked));
20832113
assert!(stats.grouped, "marks on build rows: {mark_build_rows}");
20842114
// The matches of two rounds of lookups per probe row, each until
20852115
// it wastes enough matches to pay for a sort, and a few chunks of
@@ -2097,6 +2127,41 @@ mod tests {
20972127
Ok(())
20982128
}
20992129

2130+
/// A scope map that the memory pool declines is built on a later use,
2131+
/// once the pool has room for it.
2132+
#[test]
2133+
fn declined_scope_map_is_built_once_memory_is_free() -> Result<()> {
2134+
use crate::metrics::ExecutionPlanMetricsSet;
2135+
use datafusion_execution::memory_pool::{
2136+
GreedyMemoryPool, MemoryConsumer, MemoryPool,
2137+
};
2138+
2139+
let pool: Arc<dyn MemoryPool> = Arc::new(GreedyMemoryPool::new(1 << 20));
2140+
let other = MemoryConsumer::new("other").register(&pool);
2141+
other.try_grow(1 << 20)?;
2142+
let scope_map = BuildScopeMap {
2143+
map: OnceLock::new(),
2144+
reservation: Mutex::new(MemoryConsumer::new("scope map").register(&pool)),
2145+
metrics: BuildProbeJoinMetrics::new(0, &ExecutionPlanMetricsSet::new()),
2146+
};
2147+
let scope_values: Vec<ArrayRef> =
2148+
vec![Arc::new(arrow::array::Int32Array::from(vec![1, 2, 3]))];
2149+
let random_state = RandomState::with_seed(0);
2150+
assert!(
2151+
scope_map
2152+
.get_or_try_init(&scope_values, &random_state)?
2153+
.is_none()
2154+
);
2155+
other.free();
2156+
assert!(
2157+
scope_map
2158+
.get_or_try_init(&scope_values, &random_state)?
2159+
.is_some()
2160+
);
2161+
assert!(scope_map.reservation.lock().size() > 0);
2162+
Ok(())
2163+
}
2164+
21002165
/// A cross product with marks on the build rows holds at most a batch of
21012166
/// build rows at once, however many build rows there are. No pair passes,
21022167
/// so no row is marked and every build row is paired.
@@ -2151,49 +2216,6 @@ mod tests {
21512216
Ok(())
21522217
}
21532218

2154-
/// `rare` probe rows of their own scope each, `hot` probe rows of the hot
2155-
/// scope, and `rare` more of their own scope, in that order. Each rare
2156-
/// scope holds one build row, and the hot scope `hot_build`. Every pair
2157-
/// passes, and every scope is on both sides, so every row is marked.
2158-
fn hot_scope_among_rare_ones(
2159-
mark_build_rows: bool,
2160-
rare: usize,
2161-
hot: usize,
2162-
hot_build: usize,
2163-
) -> Result<Stats> {
2164-
let rare = rare as u64;
2165-
// Scope 0 is hot.
2166-
let build_keys: Vec<u64> = (1..=2 * rare)
2167-
.chain(std::iter::repeat_n(0, hot_build))
2168-
.collect();
2169-
let probe_keys: Vec<u64> = (1..=rare)
2170-
.chain(std::iter::repeat_n(0, hot))
2171-
.chain(rare + 1..=2 * rare)
2172-
.collect();
2173-
let num_marked = if mark_build_rows {
2174-
build_keys.len()
2175-
} else {
2176-
probe_keys.len()
2177-
};
2178-
let case = Case {
2179-
mark_build_rows,
2180-
through_scope_map: true,
2181-
batch_size: 8192,
2182-
hash_modulus: u64::MAX,
2183-
probe_rows: (0..probe_keys.len() as u32).collect(),
2184-
build_rows: (0..build_keys.len() as u64).collect(),
2185-
build_keys,
2186-
probe_keys,
2187-
marked_before: vec![false; num_marked],
2188-
filter_seed: 0,
2189-
filter_one_in: 1,
2190-
foreign_marks: false,
2191-
};
2192-
let (marks, stats) = case.run()?;
2193-
assert!(marks.iter().all(|marked| *marked));
2194-
Ok(stats)
2195-
}
2196-
21972219
/// One scope holds every row, and every pair passes. Returns the matches
21982220
/// that the scope map lookups walked.
21992221
fn walked_matches_in_one_scope(

0 commit comments

Comments
 (0)