Join algorithms

A join matches rows from two inputs, such as each order with its customer. The database has to find the matching pairs without comparing every row with every other row. Three algorithms do this for equality joins: nested loop, hash join and merge join. Each one is cheapest in a different situation, and the planner chooses between them using row estimates.

The big idea

Here is the setup. You join R and S on R.a = S.b.

• Nested loop: for each row of one side, look up the matches on the other side.
• Hash join: build a hash table from the smaller side, then probe it with each row from the larger side.
• Merge join: sort both sides on the join key, then walk them together, like merging two sorted lists.

Walking through a nested loop

Join 200 customers to their orders. Imagine orders are stored in a way that a lookup by customer_id costs about 3 page reads. These are illustrative numbers.

index nested loop:   200 customers × 3 page reads per lookup = 600 page reads
no index at all:     200 customers × 5,000 orders = 1,000,000 comparisons

The index turns a million comparisons into a few hundred page reads. Without the index, nested loop is the worst choice, and that is why a missing index can make a join crawl.

Nested loop wins when the outer side is small and the inner side has an index on the join key.

Walking through a hash join

Now join the same 200 customers to 5,000 orders with no useful index. The planner can read both sides once.

1. scan customers (200 rows) and insert each into a hash table keyed on id
2. scan orders (5,000 rows) and probe the hash table with each customer_id
total work ≈ 200 inserts + 5,000 probes

Every row is read once. The cost is the memory for the hash table. If the build side is larger than the memory allowed for the operation, the database splits the work into partitions and spills the extra to disk. That is slower but still works.

Hash join needs an equality condition, and it does not need the inputs to be sorted.

Walking through a merge join

A merge join needs both inputs sorted on the join key. It reads one row from each side and advances the side with the smaller key.

customers sorted by id:   1, 2, 3, 5
orders sorted by cust id: 1, 1, 2, 5, 5
walk both lists together:
  customer 1 → two matching orders
  customer 2 → one matching order
  customer 3 → no matches (skipped)
  customer 5 → two matching orders

Sorting dominates the cost unless the inputs already come sorted, for example from an index or a clustered table. Merge join is also useful when the query needs its output sorted by the join key anyway.

Choosing between them

The planner decides from row estimates. If it estimates 100 rows where 1,000,000 come back, it may choose nested loop when it should have chosen hash join. Fresh statistics are the usual fix. See statistics and cardinality.

Common mistakes

• Joining on columns with no index and no useful order. The planner has few good options. Index the join key.
• Expecting a hash join to be free. A build side larger than memory means spilling to disk.
• Reading the join type as the problem. Often the real issue is a wrong row estimate that led to the wrong join.

Check yourself

1. Why does a missing index on the join key make nested loop so expensive? Each outer row then needs a full scan of the inner side, so the work is the product of the two sizes.
2. When is a merge join a good choice even if it needs a sort? When both inputs already arrive sorted, or when the query must return rows sorted by the join key anyway.

Key takeaways

• Nested loop: cheap when the outer side is small and the inner side has an index.
• Hash join: reads each side once, and needs memory for the build side.
• Merge join: needs sorted inputs, and shines when sorting is already free.
• The planner's choice depends on row estimates, so bad estimates lead to bad joins.

Further learning

Next, read statistics and cardinality to see how the planner estimates the row counts that drive these choices.

Andy Pavlo's CMU lecture on join algorithms covers nested loop, sort-merge and hash joins, with cost models.