Skip to content

Commit f3e1b56

Browse files
committed
peek next probe index before binary search
1 parent 9577b06 commit f3e1b56

1 file changed

Lines changed: 11 additions & 6 deletions

File tree

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

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

Lines changed: 11 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -438,17 +438,22 @@ pub(super) fn lookup_join_hashmap(
438438
}
439439
}
440440
} else {
441-
// Collision-free build side: every bucket holds a single key, so all
442-
// pairs sharing one probe row (a contiguous run, since the chain walk
443-
// emits a probe row's matches consecutively) have identical build
444-
// keys. Check the key once per run at its head and accept or reject
445-
// the whole run — turning F key comparisons per probe row into 1.
441+
// Collision-free build side: all pairs in one probe row's run share
442+
// the same build key, so checking the key once at the run head
443+
// accepts or rejects the whole run (F comparisons per probe row -> 1).
446444
let builds = build_indices_buffer.as_slice();
447445
let probes = probe_indices_buffer.as_slice();
448446
let mut start = 0;
449447
while start < probes.len() {
450448
let probe_idx = probes[start];
451-
let end = start + probes[start..].partition_point(|&p| p == probe_idx);
449+
// Find the end of this probe row's run (equal probe indices are
450+
// contiguous). Peek the next index for the common 1:1 case; fall
451+
// back to a binary search for long runs (high fanout).
452+
let end = if start + 1 >= probes.len() || probes[start + 1] != probe_idx {
453+
start + 1
454+
} else {
455+
start + probes[start..].partition_point(|&p| p == probe_idx)
456+
};
452457
if comparator.is_equal(builds[start] as usize, probe_idx as usize) {
453458
build_out.extend_from_slice(&builds[start..end]);
454459
probe_out.extend_from_slice(&probes[start..end]);

0 commit comments

Comments
 (0)