How Does the Hash Join Algorithm Work?
Learn how hash joins build and probe a hash table, when the optimizer picks them, and how grace hash join handles memory limits.
Expected Interview Answer
A hash join builds an in-memory hash table from the smaller input table keyed on the join column, then probes that table with each row of the larger input, matching rows whose keys hash to the same bucket, which gives roughly linear-time joining without requiring either input to be sorted.
The optimizer picks the smaller of the two inputs (by estimated row count) as the build side and constructs a hash table over its join key in memory. It then scans the probe side row by row, hashing each row's join key and looking up matching build-side rows in that bucket, emitting a joined row for every match. If the build side does not fit in memory, the engine spills partitions to disk (grace hash join), splitting both inputs into matching partitions and joining each pair separately. Hash joins are the default choice for large, unsorted equi-joins because they avoid a full sort of either input.
- Near-linear cost on large unsorted equi-joins
- Avoids sorting either input table
- Scales via disk-spill partitioning when data exceeds memory
- Works well when no useful index exists on the join key
AI Mentor Explanation
Picture a selector matching a short list of contracted players against a huge stack of scouting reports by their squad number: the selector first pins the short list onto a pegboard of numbered slots, one slot per number bucket, so a player can be found by squad number instantly. Then each scouting report is checked one at a time against the pegboard slot for its player's number, and a match is recorded immediately. This is exactly a hash join: the small side becomes the pegboard, or hash table, and the large side is probed against it one row at a time.
Step-by-Step Explanation
Step 1
Choose the build side
The optimizer picks the smaller estimated input (often after a filter) to build the in-memory hash table.
Step 2
Build the hash table
Every row of the build side is hashed on the join key and inserted into buckets in memory.
Step 3
Probe with the larger input
Each row of the probe side is hashed on the same key and checked against the matching bucket for equal keys.
Step 4
Spill to disk if needed
If the build side exceeds available memory, both inputs are partitioned to disk and joined partition by partition (grace hash join).
What Interviewer Expects
- Clear build-then-probe mechanics with a hash table
- Awareness that hash join targets equi-joins, not range conditions
- Understanding of memory pressure and disk-spill partitioning
- Comparison to when a merge or nested-loop join would be preferred instead
Common Mistakes
- Claiming hash join requires sorted inputs
- Forgetting hash join only supports equality predicates, not ranges
- Ignoring memory limits and the grace hash join spill strategy
- Assuming the larger table is always the build side
Best Answer (HR Friendly)
“A hash join takes the smaller of two tables being joined and builds a quick lookup structure from it in memory, keyed on the join column. It then streams through the larger table once, checking each row against that lookup structure to find matches. It is fast for big, unsorted joins because it avoids sorting either table first.”
Code Example
SELECT o.order_id, c.name
FROM Orders o
JOIN Customers c
ON o.customer_id = c.customer_id
WHERE o.order_date >= '2026-01-01';
-- With no useful index on customer_id and a large
-- unsorted Orders table, the optimizer typically builds
-- a hash table on the smaller Customers result and
-- probes it once per Orders row (an equi-join on =).Follow-up Questions
- When would the optimizer prefer a merge join over a hash join?
- What happens when the hash table does not fit in memory?
- Can a hash join be used for an inequality join condition?
- How does hash join performance change with data skew on the join key?
MCQ Practice
1. What structure does a hash join build from the smaller input table?
The build phase hashes the smaller input on the join key into an in-memory hash table for constant-time lookups.
2. Hash join is best suited for which type of join condition?
Hashing only makes sense for equality comparisons, since equal keys hash to the same bucket; ranges cannot be hashed this way.
3. What happens if the build-side table does not fit in memory?
A grace hash join partitions both tables to disk and joins matching partition pairs when memory is insufficient for a single build phase.
Flash Cards
What does a hash join build first? — An in-memory hash table from the smaller input, keyed on the join column.
What join conditions can a hash join handle? — Only equality (equi-join) conditions, since hashing requires exact key matches.
What is a grace hash join? — A disk-spill strategy that partitions both inputs when the build side exceeds available memory.
Why avoid hash join for range predicates? — Hashing maps equal keys to the same bucket, so it cannot efficiently locate a range of values.