andygrove opened a new pull request, #27530: URL: https://github.com/apache/datafusion/pull/27530
> [!NOTE] > Stacked on #27528, which adds the `hj` Q28 benchmark. Only the last commit needs review here. This is the first half of #26447, split out as suggested in that PR's review. It covers the hash maps (`JoinHashMapU32`, `JoinHashMapU64`). #26447 now holds the `ArrayMap` half on top of this PR. ## Which issue does this PR close? - Part of #17494. ## Rationale for this change When a build-side key repeats, `HashJoinExec` keeps the build rows of each key in a chain. The map holds the first row and `next[row]` holds the one after it. A probe row follows the chain with one load for every match, and each load depends on the one before, so nothing overlaps them. Once the build side no longer fits in the cache, most of those loads are misses. This is what makes joins with many build rows per key, such as the join of `catalog_sales` and `inventory` in TPC-DS q72, several times slower than a sort-merge join. ## What changes are included in this PR? `JoinHashMapU32` and `JoinHashMapU64` store the build rows of each hash value next to each other, so that a probe row reads its matches in order: - After the last build batch is inserted, the rows are grouped when the hash values have at least two rows each on average. The map then holds the position of each hash value's group, which starts with its number of rows, and the chain is freed. Rows left out of the map, such as those with NULL keys, count towards neither the threshold nor the groups. - The groups take one more index per distinct hash value than the chain. The build reserves that memory first, and keeps the chain if it can't. Grouping happens after every other reservation the build needs, so it never makes the build fail. - Grouping follows 16 chains at once, so that their loads overlap. It holds up to 4096 rows of each chain until the chain ends, and measures longer chains to place them in a second pass. So it holds at most 16 x 4096 indices besides the groups. - The probe copies a probe row's matches with one slice copy. `ProbeOffset::MidChain::next` is then the position in the groups to resume from. - A new `grouped_map_count` metric counts the maps that were grouped. Matches come out in the same order as before, so the join's output does not change. `ArrayMap` keeps its chain in this PR. ## Benchmarks The numbers in #26447 cover both halves together. The rows that apply to this PR alone are the ones for sparse keys (`JoinHashMap`), from the reproduction in #17494 (64M build rows over 640K keys, 96M probe rows, 16 partitions): | Keys | main | #26447 | | ------------------------------ | -------------- | -------------- | | Sparse (`JoinHashMap`) | 76.4 s, 75.5 s | 33.5 s, 33.2 s | | Unique, sparse, 64M build rows | 1.82 s, 1.62 s | 1.78 s, 1.68 s | I'll run `hj` with the benchmark bot once #27528 has merged, so Q28 has a baseline on `main`. ## What is the testing strategy for this PR? - New unit tests in `join_hash_map.rs` compare grouped maps with the chain or with a brute-force result. They cover rows inserted in batches from the last to the first, a row left out as for a NULL key, limits from 1 to 8192, NULL probe keys, chains long enough for the second pass, the size of the groups, the memory freed, and short chains that stay ungrouped. - `grouping_never_fails_the_build` in `hash_join/exec.rs` checks that a build that fits without its groups never fails for them, and groups its rows once the memory for them is available. - The `.slt` changes only add the new metric to `EXPLAIN ANALYZE` output. ## Are there any user-facing changes? There's a new `grouped_map_count` metric, documented in `metrics.md`. `JoinHashMapType`, which is public for internal use only, gains `group_rows` with a default implementation. This PR was prepared with AI assistance (Claude Code) and reviewed by me. 🤖 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]
