Skip to content

perf: store the build rows of repeated hash join keys together - #27530

Open
andygrove wants to merge 5 commits into
apache:mainfrom
andygrove:hash-join-grouped-rows
Open

andygrove wants to merge 5 commits into
apache:mainfrom
andygrove:hash-join-grouped-rows

Conversation

@andygrove

@andygrove andygrove commented Nov 17, 2026 •

Copy link
Copy Markdown
Member

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 the ArrayMap half on top of this PR.

Which issue does this PR close?

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

andygrove and others added 2 commits November 17, 2026 07:49
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>
@andygrove

Copy link
Copy Markdown
Member Author

Split out of #26447. Earlier review discussion is there.

@github-actions github-actions Bot added documentation Improvements or additions to documentation sqllogictest SQL Logic Tests (.slt) physical-plan Changes to the physical-plan crate labels Nov 17, 2026

@comphead comphead left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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 Partitioned mode 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 mandatory try_grow, such as in concat_build_batches, can then fail where it fits on main. grouping_never_fails_the_build only covers one partition. Is this worth a sentence in the group_rows doc, 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 pays 1 + 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 } => {

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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);
    }
}
None

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Done in dd8ecf4. The resume position goes into the loop, and the emit helper is inlined.

match_indices,
)
}
KeyRows::Grouped { groups } => grouped_matched_indices(

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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.

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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();

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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.

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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,

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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().

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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 {

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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.

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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>
@andygrove

Copy link
Copy Markdown
Member Author

Thanks @comphead. All inline points are addressed in dd8ecf4, along with the group_rows_range visibility nit.

Concurrent builds: I added a paragraph to the group_rows doc. It says that while grouping, the reservation holds both the chain and the groups. Afterwards it holds one more index per distinct key, so sibling partitions sharing the pool can find less memory than on main. I'd rather not guess a headroom margin without a case that shows the failure. Happy to add one if you have a figure in mind.

Skew in CollectLeft: agreed, this belongs in a follow-up. I'll open an issue for the hot-key case, with your idea of keeping single-row keys in the map behind a tag bit, and link it from the PR body. The hj hot-key query from #27528 gives it a baseline.

# Conflicts:
#	datafusion/physical-plan/src/joins/hash_join/exec.rs
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

documentation Improvements or additions to documentation physical-plan Changes to the physical-plan crate sqllogictest SQL Logic Tests (.slt)

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants