Database Joins: Nested, Hash, Sort-Merge

WHY IT EXISTS: Relational databases store data in separate tables to avoid duplication, but meaningful answers require combining them. The join operation is the mechanism for combining rows from two or more tables based on a related column. Because tables can range from a few rows to billions, and because memory is always smaller than disk, a single strategy cannot work for every size and shape of data. Join algorithms exist to minimize the total cost of reading, transferring, and comparing rows across storage and memory hierarchies.

THE MENTAL MODEL: Think of a join as a matching problem at a library. You have two piles of index cards, one for books and one for borrowers, and you need to pair every book with the person who checked it out. If one pile is tiny, you can flick through the big pile and check each card against the small one. If both piles are huge and unsorted, you might alphabetize them first and then walk through both in lockstep. Or you could photocopy the smaller pile into a quick-lookup notebook and scan the larger pile once. Each method is a different algorithm optimized for a different constraint.

HOW IT WORKS: There are three canonical strategies. The nested loop join iterates over every row in the outer table and searches the inner table for matches. It is simple and needs almost no memory, but its cost grows with the product of the two table sizes. The hash join reads the smaller table into memory, builds a hash table on the join key, then streams the larger table and probes the hash table for each row. It is fast and linear but requires enough RAM to hold the smaller input. The sort-merge join sorts both inputs by the join key, then scans both sorted streams in parallel, emitting matches as it goes. It avoids building a large in-memory structure but pays an upfront sorting cost.

WHEN TO USE IT: Nested loops shine when the outer table is small or when an index on the inner table lets the database jump directly to matching rows. Hash joins are the default for large unsorted datasets in analytical queries where memory can absorb the smaller relation. Sort-merge joins are ideal when both inputs are already sorted on the join key, such as when retrieving ranges from clustered indexes, or when memory is too constrained to host a hash table and the database must stream results from disk.

WHEN NOT TO USE IT: Nested loops become catastrophic when both tables are large and unindexed, turning a query into billions of random comparisons. Hash joins fail or spill to disk when the smaller table does not fit in memory, causing expensive temporary writes and re-reads. Sort-merge joins are wasteful when the data is small enough that sorting both inputs costs more than simply hashing or looping, and they struggle with highly selective inequality joins that do not map cleanly to ordered scans.

ONE CANONICAL EXAMPLE: Imagine an e-commerce report that joins a one-million-row orders table with a ten-million-row line_items table on order_id. If order_id is indexed on both sides, the optimizer likely chooses a nested loop or index merge. If neither is indexed but memory holds one million rows easily, a hash join loads orders into a hash table and scans line_items once. If both tables are pre-sorted on order_id in a data warehouse, a sort-merge join streams both tables in a single pass without ever materializing the full smaller table in RAM.