Databases · interactive

Nested loop, hash and merge joins

To join orders to customers, the database picks one of three algorithms. Step through each on a tiny table, then see how they scale to real sizes. EXPLAIN shows which one your query used.

orders

#10 cust 2
#11 cust 4
#12 cust 1
#13 cust 2
#14 cust 3

customers → hash map

id 3 Ada
id 1 Bo
id 4 Cy
id 2 Di

steps: 0 · rows: —

At scale: 100,000 orders × 1,000 customers

Nested loop100,000,000
Hash join101,000
Merge join1,771,930

Log scale. Merge join drops to 101,000 if both sides are already sorted by an index.

Build: put the smaller table in a hash map keyed by id.

Algorithm

step 0

Step 2 of 4 · read left to right

1
Nested loop
For each outer row, look through the inner table. Terrible for two big tables, great when the inner side has an index or the outer side has a few rows.
O(n × m), or O(n log m) with an index
2
Hash join
Build a hash table on the smaller side, then stream the bigger side and probe it. Needs memory for the hash table.
O(n + m), equality joins only
3
Merge join
If both sides come sorted on the key, walk them together like merging two lists.
O(n + m) after sorting
4
The planner picks from row estimates
Bad statistics mean bad estimates and the wrong join. Run ANALYZE and read EXPLAIN when a query is slow.
EXPLAIN ANALYZE SELECT …

In production

Tools and technologies

Every SQL planner chooses between these three.

Not tied to one language — use these names when you search docs or design a system.