Repository navigation
Commit d3ae55e
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
0 commit comments