Skip to content

Commit 9a94e6a

Browse files
committed
.
1 parent 107713f commit 9a94e6a

3 files changed

Lines changed: 174 additions & 18 deletions

File tree

‎benchmarks/src/hj.rs‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -405,6 +405,27 @@ const HASH_QUERIES: &[HashJoinQuery] = &[
405405
build_size: "100K",
406406
probe_size: "60M_RightAnti",
407407
},
408+
// Q22: RightSemi, Medium build (100K rows), ~1% Hit rate, fanout ~100
409+
//
410+
// Build Side: supplier (100K rows) collapsed onto 1K distinct keys
411+
// Probe Side: lineitem (60M rows). Each matching probe row produces many
412+
// duplicate probe indices before RightSemi deduplication.
413+
HashJoinQuery {
414+
sql: r###"SELECT l.k
415+
FROM (
416+
SELECT CAST(((s_suppkey - 1) % 1000) + 1 AS INT) as k
417+
FROM supplier
418+
) s
419+
RIGHT SEMI JOIN (
420+
SELECT CAST(l_suppkey AS INT) as k
421+
FROM lineitem
422+
) l
423+
ON s.k = l.k"###,
424+
density: 1.0,
425+
prob_hit: 0.01,
426+
build_size: "100K_(fanout_100)",
427+
probe_size: "60M_RightSemi",
428+
},
408429
];
409430

410431
impl RunOpt {

‎datafusion/physical-plan/benches/hash_join_semi_anti.rs‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -272,6 +272,26 @@ fn bench_hash_join_semi_anti(c: &mut Criterion) {
272272
});
273273
}
274274

275+
// RightSemi - 100% Density, ~1% hit rate, fanout ~100
276+
// Build keys are duplicated: 100K rows over 1K distinct keys. Matching
277+
// probe rows produce many duplicate probe indices before RightSemi
278+
// deduplication.
279+
{
280+
let fanout_keys = 1_000;
281+
let left_batches = build_batches(build_rows, fanout_keys, 0, &s);
282+
let right_batches = build_batches(probe_rows, build_rows, 0, &s);
283+
group.bench_function(
284+
BenchmarkId::new("right_semi_fanout100_h1", probe_rows),
285+
|b| {
286+
b.iter(|| {
287+
let left = make_exec(&left_batches, &s);
288+
let right = make_exec(&right_batches, &s);
289+
do_hash_join(left, right, JoinType::RightSemi, &rt)
290+
})
291+
},
292+
);
293+
}
294+
275295
// =========================================================================
276296
// RightAnti Join benchmarks
277297
// =========================================================================

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

Lines changed: 133 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -42,8 +42,8 @@ pub use crate::joins::{JoinOn, JoinOnRef};
4242

4343
use arrow::array::{
4444
Array, ArrowPrimitiveType, BooleanBufferBuilder, NativeAdapter, PrimitiveArray,
45-
RecordBatch, RecordBatchOptions, UInt32Array, UInt32Builder, UInt64Array,
46-
builder::UInt64Builder, downcast_array, new_null_array,
45+
PrimitiveBuilder, RecordBatch, RecordBatchOptions, UInt32Array, UInt32Builder,
46+
UInt64Array, builder::UInt64Builder, downcast_array, new_null_array,
4747
};
4848
use arrow::array::{
4949
ArrayRef, BinaryArray, BinaryViewArray, BooleanArray, Date32Array, Date64Array,
@@ -1555,39 +1555,78 @@ pub(crate) fn append_right_indices(
15551555
}
15561556
}
15571557

1558-
/// Returns `range` indices which are not present in `input_indices`
1558+
/// Returns `range` indices which are not present in `input_indices`.
1559+
///
1560+
/// `input_indices` must be sorted ascending.
15591561
pub(crate) fn get_anti_indices<T: ArrowPrimitiveType>(
15601562
range: Range<usize>,
15611563
input_indices: &PrimitiveArray<T>,
15621564
) -> PrimitiveArray<T>
15631565
where
15641566
NativeAdapter<T>: From<<T as ArrowPrimitiveType>::Native>,
15651567
{
1566-
let bitmap = build_range_bitmap(&range, input_indices);
1567-
let offset = range.start;
1568+
debug_assert!(
1569+
input_indices
1570+
.values()
1571+
.windows(2)
1572+
.all(|w| w[0].as_usize() <= w[1].as_usize()),
1573+
"get_anti_indices requires ascending input_indices"
1574+
);
15681575

1569-
// get the anti index
1570-
(range)
1571-
.filter_map(|idx| {
1572-
(!bitmap.get_bit(idx - offset)).then_some(T::Native::from_usize(idx))
1573-
})
1574-
.collect()
1576+
let mut next_unmatched_idx = range.start;
1577+
let mut output = PrimitiveBuilder::<T>::new();
1578+
1579+
for v in input_indices.iter().flatten() {
1580+
let idx = v.as_usize();
1581+
1582+
if idx < range.start {
1583+
continue;
1584+
}
1585+
if idx >= range.end {
1586+
break;
1587+
}
1588+
1589+
if next_unmatched_idx < idx {
1590+
for value in next_unmatched_idx..idx {
1591+
output.append_option(T::Native::from_usize(value));
1592+
}
1593+
}
1594+
next_unmatched_idx = idx + 1;
1595+
}
1596+
1597+
if next_unmatched_idx < range.end {
1598+
for value in next_unmatched_idx..range.end {
1599+
output.append_option(T::Native::from_usize(value));
1600+
}
1601+
}
1602+
output.finish()
15751603
}
15761604

1577-
/// Returns intersection of `range` and `input_indices` omitting duplicates
1605+
/// Returns the intersection of `range` and `input_indices`, omitting duplicates.
1606+
///
1607+
/// `input_indices` must be sorted ascending.
15781608
pub(crate) fn get_semi_indices<T: ArrowPrimitiveType>(
15791609
range: Range<usize>,
15801610
input_indices: &PrimitiveArray<T>,
15811611
) -> PrimitiveArray<T>
15821612
where
15831613
NativeAdapter<T>: From<<T as ArrowPrimitiveType>::Native>,
15841614
{
1585-
let bitmap = build_range_bitmap(&range, input_indices);
1586-
let offset = range.start;
1587-
// get the semi index
1588-
(range)
1589-
.filter_map(|idx| {
1590-
(bitmap.get_bit(idx - offset)).then_some(T::Native::from_usize(idx))
1615+
debug_assert!(
1616+
input_indices
1617+
.values()
1618+
.windows(2)
1619+
.all(|w| w[0].as_usize() <= w[1].as_usize()),
1620+
"get_semi_indices requires ascending input_indices"
1621+
);
1622+
1623+
let mut prev_idx: Option<usize> = None;
1624+
input_indices
1625+
.iter()
1626+
.flatten()
1627+
.filter_map(|v| {
1628+
let idx = v.as_usize();
1629+
(range.contains(&idx) && prev_idx.replace(idx) != Some(idx)).then_some(v)
15911630
})
15921631
.collect()
15931632
}
@@ -2353,6 +2392,82 @@ mod tests {
23532392

23542393
use rstest::rstest;
23552394

2395+
fn assert_u32_values(array: &UInt32Array, expected: &[u32]) {
2396+
assert_eq!(array.values().as_ref(), expected);
2397+
}
2398+
2399+
#[test]
2400+
fn get_anti_indices_returns_unmatched_range_indices() {
2401+
let input = UInt32Array::from(vec![3, 5, 5]);
2402+
2403+
let result = get_anti_indices(2..8, &input);
2404+
2405+
assert_u32_values(&result, &[2, 4, 6, 7]);
2406+
}
2407+
2408+
#[test]
2409+
fn get_anti_indices_ignores_out_of_range_indices() {
2410+
let input = UInt32Array::from(vec![0, 1, 3, 5, 8, 12]);
2411+
2412+
let result = get_anti_indices(2..8, &input);
2413+
2414+
assert_u32_values(&result, &[2, 4, 6, 7]);
2415+
}
2416+
2417+
#[test]
2418+
fn get_anti_indices_handles_dense_matches() {
2419+
let input = UInt32Array::from(vec![2, 3, 4, 5]);
2420+
2421+
let result = get_anti_indices(2..6, &input);
2422+
2423+
assert!(result.is_empty());
2424+
}
2425+
2426+
#[test]
2427+
fn get_anti_indices_handles_sparse_matches() {
2428+
let input = UInt32Array::from(vec![0, 8]);
2429+
2430+
let result = get_anti_indices(2..6, &input);
2431+
2432+
assert_u32_values(&result, &[2, 3, 4, 5]);
2433+
}
2434+
2435+
#[test]
2436+
fn get_semi_indices_returns_distinct_matches_in_range() {
2437+
let input = UInt32Array::from(vec![1, 3, 3, 3, 5, 8]);
2438+
2439+
let result = get_semi_indices(2..7, &input);
2440+
2441+
assert_u32_values(&result, &[3, 5]);
2442+
}
2443+
2444+
#[test]
2445+
fn get_semi_indices_ignores_out_of_range_indices() {
2446+
let input = UInt32Array::from(vec![0, 1, 3, 5, 8, 12]);
2447+
2448+
let result = get_semi_indices(2..8, &input);
2449+
2450+
assert_u32_values(&result, &[3, 5]);
2451+
}
2452+
2453+
#[test]
2454+
fn get_semi_indices_handles_dense_matches() {
2455+
let input = UInt32Array::from(vec![2, 3, 4, 5]);
2456+
2457+
let result = get_semi_indices(2..6, &input);
2458+
2459+
assert_u32_values(&result, &[2, 3, 4, 5]);
2460+
}
2461+
2462+
#[test]
2463+
fn get_semi_indices_handles_empty_input() {
2464+
let input = UInt32Array::from(Vec::<u32>::new());
2465+
2466+
let result = get_semi_indices(2..6, &input);
2467+
2468+
assert!(result.is_empty());
2469+
}
2470+
23562471
fn check(
23572472
left: &[Column],
23582473
right: &[Column],

0 commit comments

Comments
 (0)