Repository navigation
Commit 86d7a49
perf: stop re-pairing marked build rows in the scope-key null-aware join (#25679)
## Which issue does this PR close?
- Closes #25438.
## Rationale for this change
An equality correlation made a correlated `NOT IN` slower, not faster.
The cost grew with the square of the scope size. This is the
reproduction from the issue, on the `null_aware_join` benchmark tables
at 100,000 rows each:
```sql
-- (a) non-equality correlation only
SELECT count(*) FROM small_outer o
WHERE o.id_n50 NOT IN (SELECT i.id_n0 FROM small_inner i WHERE i.z < o.z);
-- (b) the same, plus an equality correlation on k
SELECT count(*) FROM small_outer o
WHERE o.z > 900
OR o.id_n50 NOT IN (SELECT i.id_n0 FROM small_inner i WHERE i.k = o.k AND i.z < o.z);
```
Release `datafusion-cli`, median of 10 runs:
| Query | `main` | This PR |
|---|---|---|
| (a) | 7 ms | 7 ms |
| (b) | 538 ms | 7 ms |
Query (b) is now as fast as query (a). Both queries return the same
results as before.
## What changes are included in this PR?
A correlated null-aware join marks a row UNKNOWN when a candidate pair
passes the join filter. `LeftAnti` and `LeftMark` mark build rows, and
`RightAnti` marks probe rows. A marked row stays marked. With a scope
key, the candidate pairs come from a hash lookup on the scope key.
Before this PR, each probe row was paired with every row of its scope,
marked or not.
The change is in `UnmarkedPairs::scope_matches` in
`hash_join/not_in.rs`:
1. The lookup drops the matches whose build row is marked, before it
makes pairs.
2. That alone still walks each scope once per probe row, and a
`RightAnti` probe row is still paired with its whole scope. So the join
counts the matches that the lookup per probe row wastes. When they cost
more than a sort, it estimates from a sample of the remaining probe rows
whether groups of equal hashes save work:
- with marks on build rows, when a group holds more than one probe row,
which then share one walk of the hash chain;
- with marks on probe rows, when the pairs of a group fill more than a
chunk, so that the later chunks can skip the marked probe rows.
3. If the groups save work, the join sorts the remaining probe rows by
hash, looks up each hash once, and pairs each group like a cross product
that drops the rows as they are marked. A group of probe rows stops
walking its hash chain when all of them are marked. Otherwise the lookup
per probe row goes on, so scopes of a few rows never pay for a sort.
4. With marks on build rows, a check of the marks that drops nothing
makes the next checks less frequent. So a filter that never passes adds
almost no cost.
The PR has three commits, for review one at a time:
1. `refactor`: no behavior change. The cross product of the path without
scope keys and the scope-key lookup share one struct, `UnmarkedPairs`.
The scope-key lookup yields full row indices, and the join checks the
scope-key equality per chunk. So `NullValueBuildRows` drops its copy of
the scope values.
2. `test`: a randomized differential test, two tests that pin how many
hash-chain matches the lookups walk today, and
`null_aware_scope_groups.slt`.
3. `perf`: the change. The test diff shows that the walk no longer grows
with the product of the rows.
**Cost on other shapes.** Release `datafusion-cli`, median of 3
interleaved runs, in ms, `main → this PR`. The outer side is all NULL,
except the unique-key shape (50% NULL). "None" has no residual filter,
"never" a filter that no pair passes, "always" one that every pair
passes. One partition unless noted. The 64-row shape comes from a
separate run, because its first run was noisy.
| Shape | `RightAnti` none | `RightAnti` never | `RightAnti` always |
`LeftMark` none | `LeftMark` never | `LeftMark` always |
|---|---|---|---|---|---|---|
| One scope, 8,192 × 8,192 | 370 → 1 | 299 → 232 | 419 → 1 | 316 → 1 |
352 → 293 | 308 → 1 |
| Unique scope keys, 2M × 2M | 55 → 55 | 54 → 53 | 57 → 54 | 65 → 66 |
65 → 68 | 66 → 67 |
| 12 inner rows per scope, 300k × 1M | 79 → 66 | 59 → 53 | 88 → 75 | 83
→ 61 | 89 → 88 | 80 → 61 |
| 16 inner rows per scope, 400k × 1M | 92 → 87 | 77 → 71 | 107 → 101 |
103 → 71 | 112 → 105 | 99 → 71 |
| 16 inner rows per scope, random scopes, 400k × 1M | 200 → 189 | 186 →
180 | 228 → 212 | 333 → 237 | 388 → 381 | 333 → 225 |
| 64 inner rows per scope, 1.6M × 2M | 892 → 871 | 814 → 758 | 1045 →
1012 | 898 → 541 | 1003 → 938 | 839 → 526 |
| 16 inner rows per scope, 400k × 1M, all partitions | 20 → 19 | 18 → 16
| 22 → 21 | 43 → 39 | 42 → 36 | 45 → 39 |
| 64 inner rows per scope, 1.6M × 2M, all partitions | 191 → 179 | 179 →
166 | 220 → 210 | 254 → 223 | 247 → 217 | 258 → 218 |
No shape is more than 5% slower, and the remaining gaps are inside the
run-to-run noise. Shapes where rows are marked are up to several hundred
times faster.
**Not in this PR.** Each probe batch walks a fully marked scope again at
least once. The path without scope keys has the same cost. Keeping each
scope's unmarked rows across batches is a possible follow-up.
## What is the testing strategy for this PR?
- No result changes. The `null_aware_*.slt` files, `subquery.slt`, the
full sqllogictest suite and the `hash_join` unit tests pass.
- `unmarked_pairs_match_brute_force` runs `UnmarkedPairs` on 3,000
random inputs and compares the marks with those of every pair. The
inputs have hash collisions between scopes, rows marked before the
pairing or during it by other partitions, filters that pass none to all
of the pairs, marks on build or probe rows, and batch sizes from 1 to
8192. More than 100 inputs of each mark kind reach the grouped pairing.
- `scope_lookups_stay_linear_in_rows` and
`marked_probe_groups_stop_walking` bound the hash-chain matches that the
lookups walk. Emitted pairs alone do not show a repeated walk.
- The cost decisions (`estimate_groups`, `groups_save_work`,
`next_unchecked_lookups`) are small pure functions with exact unit
tests. `small_scopes_are_not_grouped` and
`lookups_skip_checks_while_nothing_is_marked` check them through the
pairing.
- `null_aware_scope_groups.slt` compares `LeftMark` and `RightAnti` `NOT
IN` queries with a reference built from an outer join and an aggregate.
The scopes are large enough for the grouped pairing, and a residual
filter leaves some rows unmarked. It runs with `configMatrix` for batch
sizes 1, 7 and 8192 and 1 and 4 partitions. With an instrumented build,
I confirmed that both mark kinds reach the grouped pairing.
- Mutation testing with `cargo-mutants` on the changed lines of
`not_in.rs` catches every mutant except one, which moves the threshold
for considering groups by one wasted match.
## Are there any user-facing changes?
No. Correlated `NOT IN` queries with an equality correlation are faster.
---------
Co-authored-by: Liang-Chi Hsieh <[email protected]>1 parent 16c1f26 commit 86d7a49
2 files changed
Lines changed: 1262 additions & 228 deletions
File tree
- datafusion
- physical-plan/src/joins/hash_join
- sqllogictest/test_files
0 commit comments