andygrove opened a new pull request, #26415: URL: https://github.com/apache/datafusion/pull/26415
## Which issue does this PR close? - Closes #22854. ## Rationale for this change For a `RightSemi` or `RightAnti` hash join the build side only has to answer "does this probe row have a match?". The current probe path instead produces every `(probe, build)` match pair by walking each probe row's whole hash chain, compares the keys of every pair, and then removes duplicate probe indices afterwards. With duplicate build keys that is a lot of wasted work: a probe row whose key has 10 build rows costs 10 key comparisons and creates 10 pairs, for a single output row. This PR stops at the first key-equal build row instead. This is a re-implementation against current `main` of the approach in #22914 by @neilconway, which has been open for a while and now conflicts heavily with `main` (null-aware `RightAnti`, `valid_keys` NULL handling, the cached key comparator, the build-side range bitmap). The design and the expanded benchmark are his, so I have credited him as co-author. I'm happy to close this in favour of #22914 if he would rather rebase that. ## What changes are included in this PR? For `RightSemi`/`RightAnti` joins **without a join filter**, `process_probe_batch` takes a new path that returns the sorted indices of the probe rows that have a match, without materializing match pairs: - **`HashMap`**: new `FirstMatchProbe` trait on `JoinHashMapU32`/`U64` (reached through `JoinHashMapType::first_match_probe`, which defaults to `None` so other implementors such as `PruningJoinHashMap` are unaffected). The probe walks hash chains one link per round: gather each probe row's chain head, check key equality for the round's candidates in one vectorized call to the existing `equal_rows_arr_with_normalized_left`, then advance only the rows that did not match. Hash collisions are rare, so nearly every row resolves in round 1. When every hash has exactly one build row (`has_unique_hashes`), there is only ever one round and no per-row bookkeeping. - **`ArrayMap`**: `get_probe_indices_with_any_match` does one bucket lookup per probe row. - `RightAnti` takes the complement of the matched indices, built from ranges rather than a per-row scan. - If every probe row is emitted, the probe columns are reused as-is instead of being gathered. - Null-aware `RightAnti` (`NOT IN`) is handled: the existing skip-if-build-has-NULL check still runs before the new path, and `drop_null_probe_keys` is applied to its result. - NULL probe keys are skipped via the existing `valid_keys` mask. - The benchmark is expanded (from #22914) to cover hit rate, key density, build-side fanout, skew and Utf8 keys. Behavior change: these joins no longer report `avg_fanout`, because the probe stops at the first match so the fanout is not known. `probe_hit_rate` is unchanged. Noted in `docs/source/user-guide/metrics.md`. Not done here (all possible follow-ups): the same treatment for `RightMark` (#22880), and for joins with a filter, which need every candidate pair. ## Benchmarks `cargo bench -p datafusion-physical-plan --features test_utils --bench hash_join_semi_anti`, `main` vs this branch, one run each on an Apple-silicon laptop (noise is roughly ±5%): ``` right_semi_d100_h100 5.66 ms 0.81 ms -85.6% right_anti_d100_h100 1.93 ms 1.47 ms -23.6% right_semi_d100_h10 1.20 ms 0.55 ms -54.3% right_anti_d100_h10 3.88 ms 0.64 ms -83.6% right_semi_d100_h50 3.15 ms 0.86 ms -72.8% right_anti_d100_h50 3.05 ms 1.24 ms -59.5% right_semi_d50_h100 5.46 ms 0.83 ms -84.8% right_anti_d50_h100 1.91 ms 1.46 ms -23.7% right_semi_d50_h10 1.18 ms 0.56 ms -52.8% right_anti_d50_h10 3.92 ms 0.63 ms -83.9% right_semi_d10_h100 9.66 ms 5.72 ms -40.8% right_anti_d10_h100 6.03 ms 5.88 ms -2.5% right_semi_d10_h10 9.04 ms 8.88 ms -1.7% right_anti_d10_h10 12.41 ms 8.75 ms -29.5% right_semi_d10_h50 9.18 ms 6.86 ms -25.3% right_anti_d10_h50 9.31 ms 7.40 ms -20.5% right_semi_fanout100_h1 3.20 ms 0.56 ms -82.5% right_anti_fanout100_h1 6.75 ms 0.80 ms -88.2% right_semi_fanout10_h50 10.97 ms 2.26 ms -79.4% right_anti_fanout10_h50 10.62 ms 2.61 ms -75.4% right_semi_fanout10_h50_hashmap 24.46 ms 5.89 ms -75.9% right_anti_fanout10_h50_hashmap 21.77 ms 6.38 ms -70.7% right_semi_skewed_h50_hashmap 10.87 ms 11.81 ms +8.6% right_anti_skewed_h50_hashmap 11.95 ms 12.09 ms +1.2% right_semi_utf8_h50 12.26 ms 8.02 ms -34.6% right_anti_utf8_h50 12.13 ms 8.63 ms -28.8% right_semi_utf8_fanout10_h50 32.48 ms 8.64 ms -73.4% right_anti_utf8_fanout10_h50 31.81 ms 8.91 ms -72.0% ``` The only benchmark that is not clearly better is `skewed_h50_hashmap`, which was repeated three times with the branch 5–10% faster each time. ## What is the testing strategy for this PR? - `first_match_*` unit tests in `stream.rs` drive the round loop over a real `JoinHashMapU32` with forced hash collisions (chains of 4 colliding keys, a colliding non-matching key, a missing hash, a NULL key, duplicate build keys). I checked that breaking `next_candidates` makes `first_match_walks_hash_collision_chains` fail. The existing suite does not exercise later rounds: the same break passed all 597 `hash_join` tests under `--features force_hash_collisions`. - `complement_indices_returns_unmatched_rows` and `test_array_map_probe_indices_with_any_match`. - `join_right_semi_anti_duplicate_build_keys_and_null_probe_keys`: end-to-end on the `HashMap` and `ArrayMap` configurations, several batch sizes, both null equalities. - Existing coverage: all `joins` unit tests, including with `--features force_hash_collisions`; the null-aware `RightAnti` tests; the `join_fuzz` cases (`--features extended_tests`, 44 passed, which compare against other join implementations); and the `joins`, `subquery`, `tpch`, `explain`, `push_down_filter` and `dynamic` sqllogictests. I did not run the full workspace extended test command from CLAUDE.md. ## Are there any user-facing changes? No result changes. `EXPLAIN ANALYZE` for `RightSemi`/`RightAnti` hash joins without a filter no longer shows a value for `avg_fanout`. -- 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]
