Repository navigation
Commit 9bc5cd9
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
- physical-plan/src/joins/piecewise_merge_join
- sqllogictest/test_files
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
1487 | 1487 | | |
1488 | 1488 | | |
1489 | 1489 | | |
1490 | | - | |
| 1490 | + | |
1491 | 1491 | | |
1492 | 1492 | | |
1493 | 1493 | | |
| |||
1575 | 1575 | | |
1576 | 1576 | | |
1577 | 1577 | | |
1578 | | - | |
1579 | | - | |
1580 | | - | |
1581 | | - | |
| 1578 | + | |
| 1579 | + | |
| 1580 | + | |
| 1581 | + | |
| 1582 | + | |
1582 | 1583 | | |
1583 | 1584 | | |
1584 | 1585 | | |
1585 | 1586 | | |
| 1587 | + | |
1586 | 1588 | | |
1587 | 1589 | | |
1588 | | - | |
| 1590 | + | |
1589 | 1591 | | |
1590 | | - | |
1591 | | - | |
1592 | | - | |
1593 | | - | |
1594 | | - | |
1595 | | - | |
1596 | | - | |
| 1592 | + | |
| 1593 | + | |
| 1594 | + | |
| 1595 | + | |
| 1596 | + | |
| 1597 | + | |
| 1598 | + | |
| 1599 | + | |
| 1600 | + | |
| 1601 | + | |
| 1602 | + | |
| 1603 | + | |
| 1604 | + | |
| 1605 | + | |
| 1606 | + | |
| 1607 | + | |
| 1608 | + | |
| 1609 | + | |
| 1610 | + | |
1597 | 1611 | | |
1598 | 1612 | | |
1599 | 1613 | | |
| |||
1820 | 1834 | | |
1821 | 1835 | | |
1822 | 1836 | | |
| 1837 | + | |
| 1838 | + | |
| 1839 | + | |
1823 | 1840 | | |
1824 | 1841 | | |
1825 | 1842 | | |
| |||
1828 | 1845 | | |
1829 | 1846 | | |
1830 | 1847 | | |
1831 | | - | |
| 1848 | + | |
1832 | 1849 | | |
1833 | 1850 | | |
1834 | 1851 | | |
| |||
1840 | 1857 | | |
1841 | 1858 | | |
1842 | 1859 | | |
1843 | | - | |
| 1860 | + | |
| 1861 | + | |
| 1862 | + | |
| 1863 | + | |
| 1864 | + | |
| 1865 | + | |
1844 | 1866 | | |
1845 | 1867 | | |
1846 | 1868 | | |
| |||
1872 | 1894 | | |
1873 | 1895 | | |
1874 | 1896 | | |
1875 | | - | |
| 1897 | + | |
1876 | 1898 | | |
1877 | 1899 | | |
1878 | 1900 | | |
| |||
2000 | 2022 | | |
2001 | 2023 | | |
2002 | 2024 | | |
2003 | | - | |
| 2025 | + | |
| 2026 | + | |
| 2027 | + | |
| 2028 | + | |
| 2029 | + | |
| 2030 | + | |
2004 | 2031 | | |
2005 | 2032 | | |
2006 | 2033 | | |
| |||
0 commit comments