adriangb opened a new pull request, #25679: URL: https://github.com/apache/datafusion/pull/25679
> [!IMPORTANT] > **Stacked on https://github.com/apache/datafusion/pull/25560.** GitHub cannot base a PR on another fork's branch, so the diff here shows both. **Review only the last commit** (`perf: stop re-pairing marked build rows in the scope-key null-aware join`). Draft until #25560 lands; I will rebase then. ## Which issue does this PR close? - Closes https://github.com/apache/datafusion/issues/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, with `outer_t` and `inner_t` at 100,000 rows each: ```sql -- (a) non-equality correlation only SELECT count(*) FROM outer_t o WHERE o.id_n50 NOT IN (SELECT i.id_n0 FROM inner_t i WHERE i.z < o.z); -- (b) the same, plus an equality correlation on k SELECT count(*) FROM outer_t o WHERE o.z > 900 OR o.id_n50 NOT IN (SELECT i.id_n0 FROM inner_t i WHERE i.k = o.k AND i.z < o.z); ``` Release `datafusion-cli`, Apple M4 Pro, median of 10 runs: | Query | Before | After | |---|---|---| | (a) | 13 ms | 13 ms | | (b) | 415 ms | 10 ms | Query (b) is now as fast as query (a). Both queries return the same results as before. The `null_aware_join` benchmark suite, default sizes, median of 3 interleaved runs of each side (`CARGO_PROFILE_RELEASE_LTO=thin` for both sides): | Query | Before (ms) | After (ms) | Change | |---|---|---|---| | Q01 | 3.71 | 3.70 | 1.00x | | Q02 | 2.63 | 2.66 | 1.01x | | Q03 | 2.27 | 2.27 | 1.00x | | Q04 | 0.30 | 0.31 | 1.02x | | Q05 | 0.54 | 0.55 | 1.02x | | Q06 | 0.54 | 0.55 | 1.02x | | Q07 | 0.49 | 0.49 | 1.00x | | Q08 | 12.85 | 0.90 | 0.07x | | Q09 | 0.41 | 0.42 | 1.01x | Only Q08 is a null-aware join with a correlation scope key. The other queries do not reach the changed code, and their changes are noise. ## What changes are included in this PR? A correlated null-aware join marks a build row UNKNOWN when a candidate pair passes the join filter. A marked build 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 found all the build rows in its scope, and the marked build rows were removed only after the lookup made the pairs. A marked build row was thus paired again with every later probe row in its scope. The change is in `UnmarkedPairs::scope_matches` in `hash_join/stream.rs`: 1. The lookup drops the matches whose build row is marked, before it makes pairs. The check is one bit per match. 2. That alone is not sufficient. Each probe row still walks its whole scope, so (b) went only from 1.8 s to 1.0 s of CPU. So the join counts the matches it skipped in a probe batch. When they cost more than a sort of the probe rows, the join sorts the rest of the probe rows by scope hash. Then each hash is looked up once, and its group of probe rows is paired like the cross product of the path without scope keys: the marked build rows are dropped after each chunk of pairs, and the pairing of a group stops when no unmarked build row is left. 3. A build row belongs to one scope hash only. So the join refreshes the build rows of a group only after a chunk that can contain that group's pairs. It does not take the bitmap lock once per group. 4. The pairs from a scope lookup now carry full build and probe row indices, and the join checks the scope-key equality on each chunk. So `NullValueBuildRows` no longer keeps a copy of the scope values. The cross product of the path without scope keys and the new grouped pairing share one struct, `UnmarkedPairs`, which holds the chunk buffers and the refresh logic. **Why not the alternative in the issue.** The issue also proposes a choice per probe batch between the lookup and the cross product, with the scope equality applied to the cross-product pairs. That choice must be made before any build row is marked, so the estimate is wrong exactly in the case that matters: in Q08 the cross product is 16 times larger than the lookup, but it stops after a few probe rows. The switch in this PR is made during the batch, from the matches the join actually skipped. The cost before the switch is bounded, and shapes that never re-pair a marked build row never pay for a sort. **Why not a sort in every batch.** I measured that first. The pairs of the plain lookup are cheap, about 5 ns each, so a sort of every probe batch costs the same as a few pairs per probe row. With a unique scope key, that made the join 40–70% slower in CPU. A fixed threshold on the average scope size did not work either: 8 build rows per scope, with one probe row each, still cost 70% more. **Cost on shapes that do not gain.** I measured shapes with a scope key that is unique, or nearly unique, on the build side (2M × 2M rows, 1–50% NULL, no filter or a filter that is never or always true, 1 or 2 probe rows per scope). These never switch to grouping. CPU is 3–15% higher and wall time 0–10% higher. This comes from the bit check at lookup time, which runs in addition to the check before the join filter. ## What is the testing strategy for this PR? - No result changes. `null_aware_anti_join.slt`, `null_aware_mark_join.slt`, `subquery.slt`, the full sqllogictest suite and the `hash_join` unit tests pass. - I compared eight scope-key queries against DuckDB 1.5.2: anti and mark joins, NULLs on both sides, NULL scope keys, one and two scope keys, residual filters, and 7 to 9 scope groups. I ran them at batch sizes 8192, 7 and 1, with 1 and 4 partitions, and on a larger variant (30k × 25k rows) where each scope holds hundreds of build rows. All results match. - New unit test `unmarked_pairs_stop_pairing_marked_scope_rows` in `hash_join/stream.rs`. It gives 100 build rows in two scopes and 1000 probe rows to `UnmarkedPairs::scope_matches`, and marks every pair that it gets. It checks that all build rows are marked and that fewer than 200 pairs are made, at batch sizes 1 and 16. With the old behavior (no marked build row skipped at the lookup) it makes 50,000 pairs and fails. I added no sqllogictest, because the change does not change any result, so a new `.slt` case would pass before and after the change. ## Are there any user-facing changes? No. Correlated `NOT IN` queries with an equality correlation are faster. 🤖 Generated with [Claude Code](https://claude.com/claude-code) -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
