Skip to content

Commit d3ae55e

Browse files
authored
refactor: build the hash join hash map from the concatenated build batch (apache#26793)
## Which issue does this PR close? - Closes apache#26792. ## Rationale for this change `build_in_memory` had two build paths that only shared a concat. The `ArrayMap` path concatenated first. The `JoinHashMap` path hashed each buffered batch with its own offset and concatenated afterwards, and apache#26226 came from those offsets and the concat order disagreeing. After apache#26228 both paths concatenate the same way, so they can share one concat (as @jayzhan211 suggested and @comphead pointed out on apache#26228). Building after the concat also lowers the build-side peak on the non-prepared path. The inputs are released once their copy exists, so the hash map is no longer allocated while the inputs and the copy are both alive: the peak goes from about `inputs + map + copy` to `max(2 * inputs, copy + map)`. ## What changes are included in this PR? - `build_in_memory` concatenates once, then picks the map. `array_map_key_range` gets the single concatenated batch, and the key arrays are evaluated once for both paths. - The hash map is filled by walking zero-copy slices of the concatenated batch from the last slice to the first. Rows are still inserted from the highest index down, so the chains, and therefore the join output, are identical. An empty build is guarded (`max_batch_rows` is 0 there). - Slice length: `create_hashes` hashes everything beneath a dictionary or list view key (at any depth) on every call, and after the concat those values are shared by every slice. A slice is therefore at least `max_batch_rows` rows and 16 times the shared values, up to the whole build side, so the shared values are hashed a bounded number of times. Without this, builds on dictionary keys were up to 2x slower than main. - Outside prepared mode, the hashes buffer is reserved once a slice is longer than a batch, since it then grows with the build side. Prepared mode already reserved its scratch, now sized by the same slice length. - The `HashJoinExec` doc and diagram describe the new build. ## What is the testing strategy for this PR? Existing order tests still pass unchanged (`join_left_anti_keeps_build_order_across_batches`, `join_inner_one_two_parts_left_randomly_ordered`, `prepared_build_matches_collect_left`). New tests: - `join_keeps_build_order_across_uneven_batches`: build batches of 2, 3 and 2 rows, so the slices do not line up with the batches, with duplicate and NULL keys, Inner and LeftAnti, under both null equalities, over the hash map and array map configs. - `join_keeps_build_order_with_dictionary_keys`: the same check on dictionary keys, where slices are longer than a batch. - `join_build_side_without_batches`: an empty build on the hash map path. - `join_build_concat_is_reserved` now checks the lower peak per map type: limits that fit the new order but not the old one, plus a case that fails at the copy (array map) or at the map once the inputs are gone (hash map). These fail on the previous code. - `join_build_hashes_buffer_is_reserved`: a dictionary key build whose slice spans all batches fails with "Resources exhausted" when the limit leaves room for only half the hashes buffer. - `unsliced_hash_len_counts_shared_values_at_any_depth` and `hash_chunk_rows_amortizes_shared_values`: unit tests for the slice sizing, including nested dictionaries and list views. ## Are there any user-facing changes? No API changes. Lower build-side peak memory for in-memory hash join builds. Builds on dictionary keys close to the memory limit can now fail with "Resources exhausted" where they used to go over the limit unaccounted, as prepared mode already did.
1 parent 68808c9 commit d3ae55e

2 files changed

Lines changed: 602 additions & 87 deletions

File tree

0 commit comments

Comments
 (0)