Repository navigation
Conversation
When a build-side key repeats, a probe row follows the key's chain of build rows with one dependent load for every match, which misses the cache when the build side is large. After the build, if the hash values have at least two rows each on average and the memory pool can hold the groups, store each hash value's rows next to each other and drop the chain, so a probe row reads its matches from one place. Grouping happens after every reservation the build needs and is skipped without the memory for it, so it never fails a build. This change covers the hash maps. `ArrayMap` keeps its chain for now. Adds the `grouped_map_count` metric. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
|
Split out of #26447. Earlier review discussion is there. |
comphead
left a comment
There was a problem hiding this comment.
Thanks @andygrove. The split is much easier to follow, and the earlier points (reservation order, NULL rows, the KeyRows state, the dead get_matched_indices branch) all landed.
Design questions:
- Concurrent builds. "Never fails the build" holds for the build that groups. In
Partitionedmode every partition builds at once from the same pool, and grouping holds the chain and the groups together (about twice the index memory at the peak), then keeps one more index per distinct hash value for the whole probe. A sibling partition's mandatorytry_grow, such as inconcat_build_batches, can then fail where it fits on main.grouping_never_fails_the_buildonly covers one partition. Is this worth a sentence in thegroup_rowsdoc, or some headroom before grouping? - Skew in
CollectLeft. Could the follow-up for one hot key among unique keys get an issue linked from the PR body? One direction: every group pays1 +its row count, including hash values with a single row, which is what forces the average threshold. If single-row hash values kept their row in the map and only repeated ones pointed at a group, the cost would follow the repeated rows. The threshold could then count those instead of the average. The catch is a tag bit in the map value.
Nit: group_rows_range is pub(crate) but only used in join_hash_map.rs until the ArrayMap half lands.
| let to_skip = match offset { | ||
| AtRow { row } => row, | ||
| // Resume at position `next` of the matches of probe row `row` | ||
| MidChain { row, next } => { |
There was a problem hiding this comment.
The MidChain branch repeats the loop body for a single row. If the resume position goes into the loop instead, there is one call site and the expect goes away. emit_grouped_rows could then be inlined into the loop:
let (first_row, mut resume_pos) = match offset {
AtRow { row } => (row, None),
MidChain { row, next } => (row, Some(next as usize)),
};
for row in first_row..num_rows {
let pos = resume_pos.take();
let Some((start, end)) = rows_of(row) else {
continue;
};
if let Some(next_offset) = emit_grouped_rows(
&rows[..end],
pos.unwrap_or(start),
row,
&mut remaining,
input_indices,
match_indices,
row == num_rows - 1,
) {
return Some(next_offset);
}
}
NoneThere was a problem hiding this comment.
Done in dd8ecf4. The resume position goes into the loop, and the emit helper is inlined.
| match_indices, | ||
| ) | ||
| } | ||
| KeyRows::Grouped { groups } => grouped_matched_indices( |
There was a problem hiding this comment.
This arm, and the Chain arm above it, are identical in the JoinHashMapU64 impl. A generic free function that takes &HashTable<(u64, T)> and &KeyRows<T> and does the match itself, next to get_matched_indices_with_limit_offset, would turn both impls into one call and keep the rows_of closure in one place.
There was a problem hiding this comment.
Done in dd8ecf4. Both impls call key_rows_matched_indices.
| // inserted before it, while the rows left out of the map, such as NULL | ||
| // keys, keep `0`. | ||
| let zero = T::usize_as(0); | ||
| let chained_rows = next.iter().filter(|&&index| index != zero).count(); |
There was a problem hiding this comment.
This makes a full pass over next for every build with a repeated key, including the ones that stay chained. On main that costs nothing, and here it runs serially in CollectLeft (I haven't measured it). update_from_iter already sees each chained insert. If it returned the number of chained rows instead of bool (the symmetric hash join ignores the result), KeyRows::Chain could hold chained_rows: usize. Then !chained becomes chained_rows == 0 and this pass goes away.
There was a problem hiding this comment.
Done in dd8ecf4. update_from_iter returns the number of chained rows, and KeyRows::Chain keeps chained_rows. The pass over next is gone.
| map: &mut HashTable<(u64, T)>, | ||
| rows: &mut KeyRows<T>, | ||
| reservation: &MemoryReservation, | ||
| mem_used: &Gauge, |
There was a problem hiding this comment.
ArrayMap::try_new leaves build_mem_used to the caller (metrics.build_mem_used.add(array_map.size())). Following that here would keep metrics out of join_hash_map.rs. group_rows would take only the reservation, and build_in_memory would update the gauge from map_reservation.size() before and after. That drops the Gauge import, the unused _mem_used in the default method, the gauge half of the reserved test helper, and the mem_used assertions that repeat reservation.size().
There was a problem hiding this comment.
Done in dd8ecf4. group_rows takes only the reservation, and build_in_memory updates build_mem_used from the change in map_reservation.size().
|
|
||
| /// An unbounded pool that remembers the most it had reserved at once | ||
| #[derive(Debug, Default)] | ||
| struct PeakPool { |
There was a problem hiding this comment.
PeakRecordingPool in datafusion_execution::memory_pool already records the high-water mark. PeakRecordingPool::new(Arc::new(UnboundedMemoryPool::default())) with peak_reserved() replaces this pool and its Display impl. The aggregate tests in aggregates/mod.rs use it the same way.
There was a problem hiding this comment.
Done in dd8ecf4. Switched to PeakRecordingPool.
- Count chained rows on insert instead of scanning next before grouping - Share the probe of both hash map impls in one generic function - Resume a grouped probe in the main loop - Update build_mem_used in build_in_memory, not in group_rows - Document the effect of grouping on builds sharing the pool - Use PeakRecordingPool in grouping_never_fails_the_build - Make group_rows_range private Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
|
Thanks @comphead. All inline points are addressed in dd8ecf4, along with the Concurrent builds: I added a paragraph to the Skew in |
# Conflicts: # datafusion/physical-plan/src/joins/hash_join/exec.rs
Note
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 theArrayMaphalf on top of this PR.Which issue does this PR close?
Rationale for this change
When a build-side key repeats,
HashJoinExeckeeps the build rows of each key in a chain. The map holds the first row andnext[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 ofcatalog_salesandinventoryin TPC-DS q72, several times slower than a sort-merge join.What changes are included in this PR?
JoinHashMapU32andJoinHashMapU64store the build rows of each hash value next to each other, so that a probe row reads its matches in order:ProbeOffset::MidChain::nextis then the position in the groups to resume from.grouped_map_countmetric counts the maps that were grouped.Matches come out in the same order as before, so the join's output does not change.
ArrayMapkeeps 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):JoinHashMap)I'll run
hjwith the benchmark bot once #27528 has merged, so Q28 has a baseline onmain.What is the testing strategy for this PR?
join_hash_map.rscompare 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_buildinhash_join/exec.rschecks that a build that fits without its groups never fails for them, and groups its rows once the memory for them is available..sltchanges only add the new metric toEXPLAIN ANALYZEoutput.Are there any user-facing changes?
There's a new
grouped_map_countmetric, documented inmetrics.md.JoinHashMapType, which is public for internal use only, gainsgroup_rowswith a default implementation.This PR was prepared with AI assistance (Claude Code) and reviewed by me.
🤖 Generated with Claude Code