Hash Join

Hook: Interviewers love Hash Join because it reveals whether you understand how SQL engines match rows fast without scanning everything twice.

Question: What is a hash join in SQL?

Answer: A hash join is a way for the database to combine two tables by building a hash table from one side, then looking up matching rows from the other side. A hash table is a lookup structure that groups rows by join key, so matches can be found quickly. It is especially good for equality joins like a.id = b.id when one input is small enough to fit in memory.

Interview-Ready Answer: I think of a hash join as a two-step join strategy: first I build a hash table from the smaller input using the join key, then I probe it with rows from the other input to find matches. That gives expected linear performance, roughly O(build + probe), instead of comparing every row to every other row. It is a great choice for equality joins, but if the hash table does not fit in memory, the engine may spill to disk and get slower.

What a hash join is

Detailed Explanation: A hash join is a join algorithm, meaning it is one of the engine's internal ways to execute a JOIN. Instead of comparing every row from table A with every row from table B, the engine turns one input into a hash table keyed by the join column. Then it scans the other input and uses the same key to jump directly to the matching bucket.

How it works under the hood

1. Choose a build side. The optimizer usually picks the smaller input as the build side, because it will be stored in memory as the hash table.
2. Hash the join key. For each build-row, the engine computes a hash value from the join key and places the row into a bucket. A bucket is just a slot where rows with the same hash value are grouped.
3. Scan the probe side. The other input is called the probe side. For each probe row, the engine hashes its join key the same way.
4. Check candidate matches. Hash collisions are normal, so the engine compares actual join key values inside the bucket to confirm true matches.
5. Emit joined rows. When keys match, the engine returns the combined row. For a LEFT JOIN, unmatched probe rows still come out with NULLs on the right side.
6. Spill if needed. If the build side is too large for memory, many engines partition rows into batches and write some partitions to disk. This is called spilling, and it can turn a fast join into an I/O-heavy one.

When and why to use it

• Best fit: equality joins, like customer ID to customer ID.
• Strong choice: large unsorted tables, especially when no helpful indexes or ordering exist.
• Good sign: one side is much smaller, so the hash table stays compact.
• Poor fit: range joins like a.date < b.date; hash joins are built for equality, not ordering.

Hash join vs other join types

Performance notes

Expected time is roughly O(B + P), where B is build rows and P is probe rows. Space is roughly O(B) for the hash table. In real systems, if the build side fits in memory, a hash join can be extremely fast; if it spills into many batches, the same query can become much slower because of disk reads and writes. A classic interview detail: the optimizer depends on statistics, so stale row counts can make it pick the wrong build side or estimate memory badly.

Important edge cases

• NULLs: for equality joins, NULL never matches NULL in standard SQL.
• Duplicates: if multiple build rows share a key, all matching rows are returned; this can multiply output size.
• Order: hash join does not preserve row order.
• Collisions: collisions do not break correctness; they only add comparison work.

Memory model: think “make a phone book from the smaller side, then look up every caller.” That is the whole mental model you want on a whiteboard.

Real-World Story: Imagine a checkout service in an e-commerce platform that joins orders to customers for a nightly revenue report. The report is fast when the optimizer builds the hash table from the smaller customers table and probes it with millions of orders.

One night, a schema change and stale statistics make the optimizer underestimate the size of customers. It chooses a bad plan, the hash table grows too large, and the engine starts spilling to temp files. The dashboard slows from seconds to minutes, logs show hash batching or temp-file activity, and analysts see timeouts instead of fresh revenue numbers.

What went wrong from a learning point of view? The team thought “hash join = always fast,” but the real rule is “hash join is fast when the build side is small enough to stay in memory and the join is an equality match.” That is why production DBAs care so much about up-to-date statistics and memory settings.

Follow-up & Tricky Questions:

• How does the optimizer decide between hash join, nested loop, and merge join? It looks at estimated row counts, available indexes, sort order, join type, and memory. Good statistics matter because the choice is cost-based, not random.
• Why is hash join usually fast? Because it avoids comparing every row to every other row. Once the hash table is built, lookups are close to constant time on average.
• Can hash join be used for outer joins? Yes. The engine can still build and probe a hash table, but it must also preserve unmatched rows from the outer side and fill the missing columns with NULL.
• What happens when the hash table does not fit in memory? The engine may partition data into batches and spill to disk. That keeps the query correct, but the extra I/O can make it much slower.
• Does a hash join preserve row order? No. If order matters, add an explicit ORDER BY.
• Why does a hash join sometimes appear even when indexes exist? Because the optimizer may still decide that scanning and hashing is cheaper than many random index lookups, especially for large result sets.
• Tricky: can a hash join solve a non-equality predicate like <? Not as the primary join condition. Hash joins are for equality matching; range conditions usually need nested loop or merge join logic.
• Tricky: if both tables are huge, is hash join always best? No. If the data is already sorted, a merge join can be better, and if the join is highly selective with good indexes, nested loop may win.

Common Mistakes:

• Thinking it needs an index. Correction: hash join does not require an index; it relies on hashing and scanning.
• Assuming the smaller table is always chosen. Correction: the optimizer tries to choose the smaller build side, but bad statistics can lead to a worse plan.
• Forgetting about memory spills. Correction: a hash join can become slow if the hash table is too large and batches spill to disk.
• Expecting sorted output. Correction: hash join does not preserve order, so use ORDER BY when you need it.

Memory Hook: “Build a bucket, then probe the bucket.” Picture one table being sorted into labeled mail slots, then the other table walking past and checking the same label to find a match.

Cheat Sheet:

• Equality joins: yes.
• Range joins: usually no.
• Build side: usually smaller input.
• Probe side: scan and look up.
• Expected cost: O(B + P).
• Big risk: memory spill to disk.

Practice Tasks:

• Run the SQL example and confirm the plan contains Hash Join.
• Add 100,000 more employee rows and observe when the plan starts to struggle or spill.
• Change the join to a LEFT JOIN and identify which rows become NULL-extended.