Skip to content

Commit 9bc5cd9

Browse files
SubhamSinghalOmega359
authored andcommitted
perf(pwmj):settle never-matching streamed rows against the buffered extreme… (apache#25840)
## Which issue does this PR close? - Part of apache#18221 (and the PWMJ epic apache#17427). It doesn't close apache#18221. On the issue's 100K × 100K shape, the join's time goes to its huge output, so this change leaves it about the same. See the benchmarks below. ## Rationale for this change The classic `PiecewiseMergeJoin` stream (`INNER` / `LEFT` / `RIGHT` / `FULL`) sorts each streamed batch, then walks the sorted buffered side row by row to find each streamed row's first match. Two costs are avoidable: - **Rows that can't match anything still pay full price.** They are sorted, gathered and walked through the buffered side like every other row. This covers keys below every buffered key for `<`, and NULL keys. When most streamed rows can't match, which is common for a selective range predicate, the operator does all this work and outputs nothing for them. - **The first match is found by a linear walk.** Every match set is a suffix `[k, len)` of the sorted buffered side, so `k` can be found with a binary search instead of stepping over every non-matching buffered row. ## What changes are included in this PR? All changes are in `joins/piecewise_merge_join/`, plus a new benchmark. - **Rows that can't match are removed before the sort (`classic_join.rs`).** Because every match set is a suffix, a streamed row matches anything at all only if it matches the last buffered key. - One vectorized comparison against that key, cached once when the buffered side is ready, finds those rows. - They are emitted as unmatched rows for `Right`/`Full` and dropped for `Inner`/`Left`. Only the remaining rows are sorted, gathered and scanned. - When no rows were removed, the path is unchanged except for that one comparison per batch. When some were, the sort indices are mapped back to positions in the batch, so it is still gathered only once. - An empty buffered side, or one whose keys are all NULL, short-circuits without the comparison. - **The comparison must agree exactly with the scan, or it would change results.** - Flat keys use one `apply_cmp`, which normalizes `-0.0`/`+0.0` just as the scan's `JoinKeyComparator` does. - Nested keys are decided with the scan's own comparator. `apply_cmp` orders NULL elements inside a key ascending, while the comparator applies the sort options, descending for `<`/`<=`, at every nesting level. - The scan's nested ordering for `<`/`<=` gives different results from `NestedLoopJoinExec` when keys contain NULL elements. That is a pre-existing bug on `main`, which I'll file and fix separately. This PR keeps PWMJ's current results unchanged. - **Binary search for each row's first match (`utils.rs`).** - `first_match(lo, hi, matches)` replaces the linear walk in `resolve_classic_join`. - It searches `[previous row's match, len)`. The streamed batch is sorted, so each row's first match is at or after the previous row's. - The existence stream already did an inline binary search. It now calls the same helper, with no change in behavior. - The operator dispatch moves into two small helpers, `matches_on_equal` and `is_match`, used by both streams. - **Streamed NULL keys never reach the scan now,** since the new pre-sort step removes them. The scan's streamed-NULL skip was dead code and is replaced by a `debug_assert`. The buffered-side NULL skip stays. ### Benchmarks The `pwmj` suite from apache#25839 (100K buffered keys, 2M streamed rows, five match regimes × `INNER`/`LEFT`/`RIGHT`/`FULL`). Reproduce with: ``` cargo run -p datafusion-benchmarks --release --bin benchmark_runner -- pwmj ``` | regime | `main` (median) | Inner | Left | Right | Full | |---|---|---|---|---|---| | `no_match`: no streamed row matches | 47–50 ms | −95.9% (25×) | −95.9% (24×) | −94.0% (17×) | −93.7% (16×) | | `null_heavy`: half NULL, rest `no_match` | 45–50 ms | −95.7% (23×) | −95.7% (23×) | −94.0% (17×) | −93.7% (16×) | | `half_match`: half `no_match`, half `selective` | 371–375 ms | −9.2% | −8.7% | −8.2% | −8.4% | | `selective`: every row matches the 1–4 smallest buffered keys | 694–699 ms | −2.9% | −3.9% | −3.6% | −3.2% | | `all_match`: every row matches every buffered key | 162–163 ms | +0.1% | −0.6% | −0.0% | +0.3% | ## What is the testing strategy for this PR? - `first_match_agrees_with_linear_scan` (`utils.rs`): exhaustive over every range, answer and start position up to 40. It checks the result against a linear scan and bounds the number of comparisons by `⌈log2(hi − lo + 1)⌉`. - `matchable_rows_agrees_with_scan` (`classic_join.rs`): the pre-sort check against a brute-force version of the scan's own definition of a match. It covers 12 key types, 4 operators, and a normal, all-NULL and empty buffered side. - The key types: Int32, Float64 with `±0.0`/NaN/`±inf`, Utf8, Utf8View, Binary, Dictionary, Decimal128, Date32, Timestamp, Boolean, and two List cases with NULL elements. - With the nested-key branch removed, this test fails. - `join_right_less_than_signed_zero_prefilter_agrees_with_scan`: end to end with `-0.0`/`+0.0` keys. - Existing tests: - all PWMJ unit tests; - the NLJ differential fuzz test `fuzz_pwmj_matches_nested_loop` (`--features extended_tests`), covering Inner/Left/Right/Full, NULL keys, small batches and multiple partitions; - the PWMJ and join sqllogictests. ## Are there any user-facing changes? No API or configuration changes.
1 parent 27ee884 commit 9bc5cd9

6 files changed

Lines changed: 1347 additions & 214 deletions

File tree

‎datafusion/core/tests/fuzz_cases/join_fuzz.rs‎

Lines changed: 44 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -1487,7 +1487,7 @@ fn make_staggered_batches_binary(
14871487
//
14881488
// What only randomization reaches: `LeftSemi`/`LeftAnti` record matches in a shared
14891489
// `AtomicUsize` watermark and emit once, from whichever streamed partition finishes last. The
1490-
// streamed side below is spread round-robin over several partitions as one-row batches, so
1490+
// streamed side below is spread round-robin over several partitions in small batches, so
14911491
// batches arrive in an order no static test pins down, and the counter that gates the final
14921492
// pass is seeded from a partition count that deliberately disagrees with the `num_partitions`
14931493
// argument. `RightSemi`/`RightAnti` take the mirror path -- every partition emits its own
@@ -1575,25 +1575,39 @@ fn pwmj_single_exec<K: PwmjFuzzKey>(
15751575
.unwrap()
15761576
}
15771577

1578-
/// Rows spread round-robin across `nparts` partitions, one row per batch, with any partition
1579-
/// that draws no row left holding a single empty batch. Used for the streamed side throughout,
1580-
/// and for the buffered side of the right existence joins, which place no single-partition
1581-
/// requirement on it.
1578+
/// Rows spread round-robin across `nparts` partitions, with any partition that draws no row
1579+
/// left holding a single empty batch. With `stagger_seed`, each partition's rows are cut into
1580+
/// random-size batches, empty ones included, by [`stagger_batch_with_seed`]; without it, one
1581+
/// row per batch. Used for the streamed side throughout, and for the buffered side of the
1582+
/// right existence joins, which place no single-partition requirement on it.
15821583
fn pwmj_parts_exec<K: PwmjFuzzKey>(
15831584
ids: &[i32],
15841585
keys: &[Option<K>],
15851586
nparts: usize,
1587+
stagger_seed: Option<u64>,
15861588
) -> Arc<dyn ExecutionPlan> {
15871589
let nparts = nparts.max(1);
1588-
let mut partitions: Vec<Vec<RecordBatch>> = vec![Vec::new(); nparts];
1590+
let mut part_rows: Vec<(Vec<i32>, Vec<Option<K>>)> = vec![Default::default(); nparts];
15891591
for (row, (&id, key)) in ids.iter().zip(keys.iter()).enumerate() {
1590-
partitions[row % nparts].push(pwmj_kv_batch(&[id], &[*key]));
1591-
}
1592-
for p in partitions.iter_mut() {
1593-
if p.is_empty() {
1594-
p.push(pwmj_kv_batch::<K>(&[], &[]));
1595-
}
1596-
}
1592+
part_rows[row % nparts].0.push(id);
1593+
part_rows[row % nparts].1.push(*key);
1594+
}
1595+
let partitions: Vec<Vec<RecordBatch>> = part_rows
1596+
.iter()
1597+
.enumerate()
1598+
.map(|(part, (ids, keys))| match stagger_seed {
1599+
// `stagger_batch_with_seed` panics on a batch with no rows.
1600+
_ if ids.is_empty() => vec![pwmj_kv_batch::<K>(&[], &[])],
1601+
Some(seed) => {
1602+
stagger_batch_with_seed(pwmj_kv_batch(ids, keys), seed + part as u64)
1603+
}
1604+
None => ids
1605+
.iter()
1606+
.zip(keys)
1607+
.map(|(&id, key)| pwmj_kv_batch(&[id], &[*key]))
1608+
.collect(),
1609+
})
1610+
.collect();
15971611
MemorySourceConfig::try_new_exec(&partitions, pwmj_kv_schema::<K>(), None).unwrap()
15981612
}
15991613

@@ -1820,6 +1834,9 @@ async fn run_pwmj_fuzz<K: PwmjFuzzKey + std::fmt::Debug>(task_ctx: &Arc<TaskCont
18201834
let left_keys = gen_keys(left_len, &mut rng);
18211835
let right_ids: Vec<i32> = (0..right_len as i32).collect();
18221836
let right_keys = gen_keys(right_len, &mut rng);
1837+
// Staggered streamed batches mix rows that can and cannot match, so the classic joins
1838+
// set some aside before the sort and map the rest back to their rows.
1839+
let stagger_seed = Some(seed);
18231840

18241841
for op in ops {
18251842
for join_type in join_types {
@@ -1828,7 +1845,7 @@ async fn run_pwmj_fuzz<K: PwmjFuzzKey + std::fmt::Debug>(task_ctx: &Arc<TaskCont
18281845
// single-partition shape below never reaches.
18291846
let buffered = match join_type {
18301847
JoinType::RightSemi | JoinType::RightAnti | JoinType::RightMark => {
1831-
pwmj_parts_exec(&left_ids, &left_keys, buffered_nparts)
1848+
pwmj_parts_exec(&left_ids, &left_keys, buffered_nparts, None)
18321849
}
18331850
_ => pwmj_single_exec(&left_ids, &left_keys),
18341851
};
@@ -1840,7 +1857,12 @@ async fn run_pwmj_fuzz<K: PwmjFuzzKey + std::fmt::Debug>(task_ctx: &Arc<TaskCont
18401857
let got = pwmj_collect_mark_pairs(
18411858
pwmj_plan(
18421859
buffered,
1843-
pwmj_parts_exec(&right_ids, &right_keys, nparts),
1860+
pwmj_parts_exec(
1861+
&right_ids,
1862+
&right_keys,
1863+
nparts,
1864+
stagger_seed,
1865+
),
18441866
op,
18451867
join_type,
18461868
),
@@ -1872,7 +1894,7 @@ async fn run_pwmj_fuzz<K: PwmjFuzzKey + std::fmt::Debug>(task_ctx: &Arc<TaskCont
18721894
let got = pwmj_collect_id_pairs(
18731895
pwmj_plan(
18741896
buffered,
1875-
pwmj_parts_exec(&right_ids, &right_keys, nparts),
1897+
pwmj_parts_exec(&right_ids, &right_keys, nparts, stagger_seed),
18761898
op,
18771899
join_type,
18781900
),
@@ -2000,7 +2022,12 @@ async fn pwmj_watermark_nulls_duplicates_multi_partition() {
20002022
let got = pwmj_collect_id_pairs(
20012023
pwmj_plan(
20022024
pwmj_single_exec(&left_ids, &left_keys),
2003-
pwmj_parts_exec(&case.streamed_ids, &case.streamed_keys, nparts),
2025+
pwmj_parts_exec(
2026+
&case.streamed_ids,
2027+
&case.streamed_keys,
2028+
nparts,
2029+
None,
2030+
),
20042031
Operator::Lt,
20052032
join_type,
20062033
),

0 commit comments

Comments
 (0)