How does a hash join handle memory overflow?
understanding of query execution under memory pressure.
the build table is partitioned by hash and spilled to disk, then probe rows are partitioned the same way, and pairs are joined per partition.
What's really being asked
The interviewer wants to see whether you understand that hash joins are not magic and that databases have concrete spill-to-disk algorithms for when the build side exceeds available work memory. It probes your knowledge of execution internals beyond the happy path.
The full answer
The canonical solution is the Grace hash join. Apply a hash function to the join key to split the build relation into partitions small enough that each fits in memory, writing those partitions to disk. Apply the identical hash function to the probe relation so matching keys land in corresponding partitions. Then load one build partition into memory, build its hash table, stream the matching probe partition, and emit results, repeating per partition pair. A refinement is the hybrid hash join, which keeps the first partition entirely in memory to avoid one round trip of I/O. If a single partition is still too large because of key skew, the engine recurses, repartitioning that partition with a different hash function.
The mistakes people make
Saying the query simply fails, or that the planner always switches to a sort-merge or nested loop join. Real planners may pick those at plan time, but at runtime the hash operator spills rather than aborts. Another miss is forgetting that the probe side must be partitioned by the same function, or ignoring skew handling entirely.
What usually comes next
What happens with severe data skew where one bucket dominates? How does the optimizer estimate whether a hash join fits before execution? How does work_mem or equivalent settings influence the choice? What is the I/O cost compared to a sort-merge join?
A concrete example
PostgreSQL building a hash table on a 4 GB orders table with 256 MB of work memory will batch the build side into multiple on-disk partitions, increasing nbatch dynamically as it discovers it underestimated rows. EXPLAIN ANALYZE will show Batches greater than one and a Disk usage figure, signaling the hash join spilled rather than staying purely in memory.
Interview question
When a hash join's build table cannot fit in memory, what does a Grace hash join do to still complete the join correctly?
- a.Switches to a nested loop join over the full unpartitioned tables
- b.Partitions both inputs with the same hash function and joins matching partition pairs from diskCorrect
- c.Sorts both inputs on disk and merges them instead
- d.Loads as much of the build table as fits and silently drops the remaining rows
Why? this is the answer
Grace hash join partitions both relations by the same hash so matches co-locate, then joins partition pairs that each fit in memory. Sorting and merging is a different algorithm, not what a spilling hash join does.
Just read this? Test yourself on what you have been reading.
Read the original → en.wikipedia.org
- #databases
- #query-execution
- #hash-join
- #memory
- #performance
Put your scrolling time to good use
Learn one idea, try a quiz and save useful cards for revision. Tezvyn makes it easy to learn and stay current in your tech field, a few minutes at a time.
The iPhone app is on the way
We are building it. Until it lands, nothing here is held back from you: every interview card, your saved cards, streaks and the job board all work in Safari, plus hundreds of free practice quizzes of thirty questions each. Sign in and it all carries over to the app the day it arrives.
Want it as an icon? Tap Share at the bottom of Safari, then Add to Home Screen. It opens full screen and the cards you have read stay available offline.
We are hiring for this. Open roles that interview on databases — each one lists the topics its interview covers.
See open roles