Skip to content

Commit 2aab973

Browse files
refactor: replace MapOffset tuple with ProbeOffset enum (apache#26203)
## Which issue does this PR close? - Closes apache#25332 . ## Rationale for this change `MapOffset` was a `(usize, Option<u64>)` tuple that encoded the resume point of chunked hash map lookups by convention. One position had two encodings (`(row, Some(0))` and `(row + 1, None)`), the unique-key fast paths read only `offset.0`, and `HashJoinStream` relied on an undocumented invariant (`offset == (0, None)` only before the first chunk). ## What changes are included in this PR? - Replace the tuple with `pub enum ProbeOffset { AtRow { row }, MidChain { row, next } }` in `join_hash_map.rs`, re-exported from `joins::utils` next to `JoinHashMapType`. - Normalize at the producer: `traverse_chain` returns `AtRow { row: row + 1 }` once a row's chain is finished, so every position has one encoding and readers no longer handle `Some(0)`. | Old | New | |---|---| | `(row, None)` | `AtRow { row }` | | `(row, Some(next))`, `next != 0` | `MidChain { row, next }` | | `(row, Some(0))` | `AtRow { row: row + 1 }` | - Unique-key fast paths (`JoinHashMap`, `ArrayMap`) `debug_assert!` that they only receive `AtRow`. The invariant holds by construction (`unique` is fixed when the build side is built, and every chunk of a probe batch uses the same map), so a check in debug builds and CI is enough to catch a regression without adding a panic path to query execution. - Add `ProcessProbeBatchState::is_first_chunk()` and use it at the three first-chunk checks. The invariant it relies on (a returned offset is never `AtRow { row: 0 }`) is documented on `ProbeOffset`. ## What is the testing strategy for this PR? Covered by existing tests, with expected offsets updated to the new encoding. `test_unique_fast_path_with_uninserted_row` (apache#26018) told the fast path apart from the chain walk by their different offset encodings, which this PR removes. This PR added an unmatched probe row so the two paths now emit different results (the fast path limits by probe rows, the chain walk by matches), and checked that the test fails when the fast path is disabled. cc @jayzhan211 ## Are there any user-facing changes? No behavior change. API change: `JoinHashMapType::get_matched_indices_with_limit_offset` and the public `get_matched_indices_with_limit_offset` function now take and return `ProbeOffset` instead of `(usize, Option<u64>)`. Co-authored-by: Jay Zhan <[email protected]>
1 parent 53232ba commit 2aab973

8 files changed

Lines changed: 138 additions & 80 deletions

File tree

‎datafusion/physical-plan/src/joins/array_map.rs‎

Lines changed: 33 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -19,8 +19,9 @@ use arrow_schema::DataType;
1919
use num_traits::AsPrimitive;
2020
use std::mem::size_of;
2121

22-
use crate::joins::MapOffset;
2322
use crate::joins::chain::traverse_chain;
23+
use crate::joins::join_hash_map::ProbeOffset;
24+
use crate::joins::join_hash_map::ProbeOffset::{AtRow, MidChain};
2425
use arrow::array::{Array, ArrayRef, AsArray, BooleanArray};
2526
use arrow::buffer::BooleanBuffer;
2627
use arrow::datatypes::ArrowNumericType;
@@ -248,10 +249,10 @@ impl ArrayMap {
248249
&self,
249250
prob_side_keys: &[ArrayRef],
250251
limit: usize,
251-
current_offset: MapOffset,
252+
current_offset: ProbeOffset,
252253
probe_indices: &mut Vec<u32>,
253254
build_indices: &mut Vec<u64>,
254-
) -> Result<Option<MapOffset>> {
255+
) -> Result<Option<ProbeOffset>> {
255256
if prob_side_keys.len() != 1 {
256257
return internal_err!(
257258
"ArrayMap expects 1 join key, but got {}",
@@ -287,10 +288,10 @@ impl ArrayMap {
287288
&self,
288289
array: &ArrayRef,
289290
limit: usize,
290-
current_offset: MapOffset,
291+
current_offset: ProbeOffset,
291292
probe_indices: &mut Vec<u32>,
292293
build_indices: &mut Vec<u64>,
293-
) -> Result<Option<MapOffset>>
294+
) -> Result<Option<ProbeOffset>>
294295
where
295296
T::Native: Copy + AsPrimitive<u64>,
296297
{
@@ -302,9 +303,17 @@ impl ArrayMap {
302303
let have_null = arr.null_count() > 0;
303304

304305
if self.next.is_empty() {
305-
for prob_idx in current_offset.0..arr.len() {
306+
debug_assert!(
307+
matches!(current_offset, AtRow { .. }),
308+
"since the next offset is empty, mid-chain is not possible"
309+
);
310+
let rows = match current_offset {
311+
AtRow { row } => row,
312+
MidChain { row, .. } => row,
313+
};
314+
for prob_idx in rows..arr.len() {
306315
if build_indices.len() == limit {
307-
return Ok(Some((prob_idx, None)));
316+
return Ok(Some(AtRow { row: prob_idx }));
308317
}
309318

310319
// short circuit
@@ -322,14 +331,14 @@ impl ArrayMap {
322331
} else {
323332
let mut remaining_output = limit;
324333
let to_skip = match current_offset {
325-
// None `initial_next_idx` indicates that `initial_idx` processing hasn't been started
326-
(idx, None) => idx,
327-
// Zero `initial_next_idx` indicates that `initial_idx` has been processed during
328-
// previous iteration, and it should be skipped
329-
(idx, Some(0)) => idx + 1,
330-
// Otherwise, process remaining `initial_idx` matches by traversing `next_chain`,
334+
// `AtRow` indicates that `idx` processing hasn't been started
335+
AtRow { row: idx } => idx,
336+
// Otherwise, process remaining `idx` matches by traversing `next_chain`,
331337
// to start with the next index
332-
(idx, Some(next_idx)) => {
338+
MidChain {
339+
row: idx,
340+
next: next_idx,
341+
} => {
333342
let is_last = idx == arr.len() - 1;
334343
if let Some(next_offset) = traverse_chain(
335344
&self.next,
@@ -348,7 +357,7 @@ impl ArrayMap {
348357

349358
for prob_side_idx in to_skip..arr.len() {
350359
if remaining_output == 0 {
351-
return Ok(Some((prob_side_idx, None)));
360+
return Ok(Some(AtRow { row: prob_side_idx }));
352361
}
353362

354363
if have_null && arr.is_null(prob_side_idx) {
@@ -433,7 +442,7 @@ mod tests {
433442

434443
let mut prob_idx = Vec::new();
435444
let mut build_idx = Vec::new();
436-
let mut next = Some((0, None));
445+
let mut next = Some(AtRow { row: 0 });
437446
let mut results = vec![];
438447

439448
while let Some(o) = next {
@@ -448,8 +457,8 @@ mod tests {
448457
}
449458

450459
let expected = vec![
451-
(vec![0], vec![0], Some((0, Some(2)))),
452-
(vec![0], vec![1], Some((0, Some(0)))),
460+
(vec![0], vec![0], Some(MidChain { row: 0, next: 2 })),
461+
(vec![0], vec![1], Some(AtRow { row: 1 })),
453462
(vec![1], vec![2], None),
454463
];
455464
assert_eq!(results, expected);
@@ -467,13 +476,13 @@ mod tests {
467476
let next = map.get_matched_indices_with_limit_offset(
468477
&probe,
469478
1,
470-
(0, None),
479+
AtRow { row: 0 },
471480
&mut p_idx,
472481
&mut b_idx,
473482
)?;
474483
assert_eq!(p_idx, vec![1]);
475484
assert_eq!(b_idx, vec![0]);
476-
assert_eq!(next, Some((2, None)));
485+
assert_eq!(next, Some(AtRow { row: 2 }));
477486

478487
// Find 2, end
479488
let next = map.get_matched_indices_with_limit_offset(
@@ -504,14 +513,14 @@ mod tests {
504513
let result_offset = array_map.get_matched_indices_with_limit_offset(
505514
&prob_side_keys,
506515
3,
507-
(0, None),
516+
AtRow { row: 0 },
508517
&mut prob_indices,
509518
&mut build_indices,
510519
)?;
511520

512521
assert_eq!(prob_indices, vec![1, 1, 3]);
513522
assert_eq!(build_indices, vec![0, 1, 0]);
514-
assert_eq!(result_offset, Some((3, Some(2))));
523+
assert_eq!(result_offset, Some(MidChain { row: 3, next: 2 }));
515524
Ok(())
516525
}
517526

@@ -542,7 +551,7 @@ mod tests {
542551
let next = map.get_matched_indices_with_limit_offset(
543552
&probe,
544553
10,
545-
(0, None),
554+
AtRow { row: 0 },
546555
&mut matched_probe_indices,
547556
&mut matched_build_indices,
548557
)?;
@@ -579,7 +588,7 @@ mod tests {
579588
let result_offset = array_map.get_matched_indices_with_limit_offset(
580589
&prob_side_keys,
581590
10, // A batch size larger than number of probes
582-
(0, None),
591+
AtRow { row: 0 },
583592
&mut prob_indices,
584593
&mut build_indices,
585594
)?;

‎datafusion/physical-plan/src/joins/chain.rs‎

Lines changed: 11 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -20,7 +20,8 @@ use std::ops::Sub;
2020

2121
use arrow::datatypes::ArrowNativeType;
2222

23-
use crate::joins::MapOffset;
23+
use crate::joins::join_hash_map::ProbeOffset;
24+
use crate::joins::join_hash_map::ProbeOffset::{AtRow, MidChain};
2425

2526
/// Traverses the chain of matching indices, collecting results up to the remaining limit.
2627
/// Returns `Some(offset)` if the limit was reached and there are more results to process,
@@ -34,7 +35,7 @@ pub(crate) fn traverse_chain<T>(
3435
input_indices: &mut Vec<u32>,
3536
match_indices: &mut Vec<u64>,
3637
is_last_input: bool,
37-
) -> Option<MapOffset>
38+
) -> Option<ProbeOffset>
3839
where
3940
T: Copy + TryFrom<usize> + PartialOrd + Into<u64> + Sub<Output = T>,
4041
<T as TryFrom<usize>>::Error: Debug,
@@ -56,8 +57,15 @@ where
5657
return if is_last_input && next == zero {
5758
// Finished processing the last input row
5859
None
60+
} else if next == zero {
61+
// `prob_idx` has been processed during this iteration, so the
62+
// next call should start with the next input row
63+
Some(AtRow { row: prob_idx + 1 })
5964
} else {
60-
Some((prob_idx, Some(next.into())))
65+
Some(MidChain {
66+
row: prob_idx,
67+
next: next.into(),
68+
})
6169
};
6270
}
6371
if next == zero {

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

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -3982,6 +3982,7 @@ mod tests {
39823982
test::exec::MockExec,
39833983
};
39843984

3985+
use crate::joins::join_hash_map::ProbeOffset::AtRow;
39853986
use arrow::array::{
39863987
Array, ArrayRef, AsArray, BinaryViewArray, Date32Array, DictionaryArray,
39873988
Float32Array, Float64Array, Int32Array, Int64Array, StringArray, StringViewArray,
@@ -7403,7 +7404,7 @@ mod tests {
74037404
&hashes_buffer,
74047405
None,
74057406
8192,
7406-
(0, None),
7407+
AtRow { row: 0 },
74077408
&mut probe_indices_buffer,
74087409
&mut build_indices_buffer,
74097410
&mut None,
@@ -7466,7 +7467,7 @@ mod tests {
74667467
&hashes_buffer,
74677468
None,
74687469
8192,
7469-
(0, None),
7470+
AtRow { row: 0 },
74707471
&mut probe_indices_buffer,
74717472
&mut build_indices_buffer,
74727473
&mut None,

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

Lines changed: 22 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -25,14 +25,15 @@ use std::task::Poll;
2525

2626
use crate::coalesce::{LimitedBatchCoalescer, PushBatchStatus};
2727
use crate::joins::Map;
28-
use crate::joins::MapOffset;
2928
use crate::joins::PartitionMode;
3029
use crate::joins::hash_join::exec::{JoinLeftData, NullAwareMode, null_value_key_mask};
3130
use crate::joins::hash_join::probe_completion::ProbeSideSummary;
3231
use crate::joins::hash_join::shared_bounds::{
3332
PartitionBounds, PartitionBuildData, SharedBuildAccumulator,
3433
};
3534
use crate::joins::integer_prefilter::PrefilterState;
35+
use crate::joins::join_hash_map::ProbeOffset;
36+
use crate::joins::join_hash_map::ProbeOffset::AtRow;
3637
use crate::joins::utils::{
3738
JoinKeyComparator, OnceFut, equal_rows_arr_with_normalized_left, matchable_join_keys,
3839
};
@@ -194,7 +195,7 @@ pub(super) struct ProcessProbeBatchState {
194195
/// Original validity combined with integer membership, for lookup only.
195196
lookup_keys: Option<NullBuffer>,
196197
/// Starting offset for JoinHashMap lookups
197-
offset: MapOffset,
198+
offset: ProbeOffset,
198199
/// Max joined probe-side index from current batch
199200
joined_probe_idx: Option<usize>,
200201
/// Max probe-side index with a join-key match from current batch, before
@@ -208,7 +209,7 @@ pub(super) struct ProcessProbeBatchState {
208209
}
209210

210211
impl ProcessProbeBatchState {
211-
fn advance(&mut self, offset: MapOffset, joined_probe_idx: Option<usize>) {
212+
fn advance(&mut self, offset: ProbeOffset, joined_probe_idx: Option<usize>) {
212213
self.offset = offset;
213214
if joined_probe_idx.is_some() {
214215
self.joined_probe_idx = joined_probe_idx;
@@ -231,6 +232,15 @@ impl ProcessProbeBatchState {
231232
}
232233
count
233234
}
235+
236+
/// Returns whether the next lookup is the first chunk of this probe batch.
237+
///
238+
/// A probe batch starts at `AtRow { row: 0 }`, and a lookup never returns
239+
/// that offset (see [`ProbeOffset`]), so this holds only before the first
240+
/// lookup.
241+
fn is_first_chunk(&self) -> bool {
242+
self.offset == AtRow { row: 0 }
243+
}
234244
}
235245

236246
/// Container for HashJoinStreamState::EmitUnmatchedBuildRows related data
@@ -492,11 +502,11 @@ pub(super) fn lookup_join_hashmap(
492502
hashes_buffer: &[u64],
493503
valid_keys: Option<&NullBuffer>,
494504
limit: usize,
495-
offset: MapOffset,
505+
offset: ProbeOffset,
496506
probe_indices_buffer: &mut Vec<u32>,
497507
build_indices_buffer: &mut Vec<u64>,
498508
key_comparator: &mut Option<JoinKeyComparator>,
499-
) -> Result<(UInt64Array, UInt32Array, Option<MapOffset>)> {
509+
) -> Result<(UInt64Array, UInt32Array, Option<ProbeOffset>)> {
500510
let next_offset = build_hashmap.get_matched_indices_with_limit_offset(
501511
hashes_buffer,
502512
valid_keys,
@@ -875,7 +885,7 @@ impl HashJoinStream {
875885
values: keys_values,
876886
valid_keys,
877887
lookup_keys,
878-
offset: (0, None),
888+
offset: AtRow { row: 0 },
879889
joined_probe_idx: None,
880890
matched_probe_idx: None,
881891
key_comparator: None,
@@ -897,8 +907,8 @@ impl HashJoinStream {
897907
let build_side = self.build_side.try_as_ready_mut()?;
898908

899909
// A probe batch may be processed in several chunks; count its rows once,
900-
// on the first chunked lookup (offset == (0, None)).
901-
if state.offset == (0, None) {
910+
// on the first chunked lookup (offset == AtRow {row: 0}).
911+
if state.is_first_chunk() {
902912
self.join_metrics
903913
.probe_hit_rate
904914
.add_total(state.batch.num_rows());
@@ -915,11 +925,11 @@ impl HashJoinStream {
915925

916926
// For correlated null-aware joins, record this batch's UNKNOWN
917927
// candidates once, before the first chunked lookup
918-
// (offset == (0, None)).
928+
// (offset == AtRow {row: 0}).
919929
//
920930
// Must precede the empty-build-map return below: an all-NULL-key
921931
// build side has an empty full-key map but still needs UNKNOWN marks.
922-
if mode.is_correlated() && state.offset == (0, None) {
932+
if mode.is_correlated() && state.is_first_chunk() {
923933
mark_null_candidates_for_probe_batch(
924934
build_side,
925935
state,
@@ -1347,7 +1357,7 @@ fn null_aware_skip_probe_batch(
13471357
correlated: false, ..
13481358
} => {
13491359
let is_anti = matches!(mode, NullAwareMode::LeftAnti { .. });
1350-
if state.offset == (0, None) {
1360+
if state.is_first_chunk() {
13511361
// `on[0]` is the `NOT IN` value key for both modes. A probe
13521362
// batch may resume lookup many times, but its summary is
13531363
// invariant and only needs to be computed once.
@@ -1729,7 +1739,7 @@ fn for_each_scope_match(
17291739
build_indices_buffer: &mut Vec<u64>,
17301740
mut f: impl FnMut(UInt64Array, UInt32Array) -> Result<()>,
17311741
) -> Result<()> {
1732-
let mut offset = (0, None);
1742+
let mut offset = AtRow { row: 0 };
17331743
let mut key_comparator = None;
17341744
loop {
17351745
let (build_indices, probe_indices, next_offset) = lookup_join_hashmap(

0 commit comments

Comments
 (0)