How a database runs a join: nested loop, hash join, merge join

Step 1 Understand it

Why you need it. In senior interviews you may be asked why a join is slow or what a plan line like "Hash Join" means. Knowing the three methods tells you which index or memory setting will help.

Watch it happen

Picture it

flowchart TD
  J["a join"] --> NL["nested loop<br/>small outer side + index on inner"]
  J --> HJ["hash join<br/>big inputs, equality, no useful index"]
  J --> MJ["merge join<br/>both inputs already sorted on the key"]

The idea

Nested loop: for each row of the outer table, find matching rows in the inner table — fast when the outer side is small and the inner side has an index on the join key (that is what SQLite did in the last lesson). Hash join: read the smaller table into a hash table keyed on the join column, then stream the bigger table past it, checking each row — great for big, unindexed equality joins, but it needs memory. Merge join: if both sides are sorted on the key (by an index, or by sorting first), walk them side by side like zipping a zip — good for big inputs already in order.

How it works, step by step

1. Nested loop: outer has N rows, and each inner lookup is an index search, so the cost is about N × log(M). Bad if there is no index on the inner side: N × M.
2. Hash join: build a hash table on the smaller input (one pass), probe it with the larger (one pass): about N + M, using memory.
3. Merge join: if both inputs are already sorted, one pass over each: about N + M; otherwise a sort first.
4. Equality joins can use any method; only nested loops handle conditions like a.x < b.y.
5. You influence the choice through indexes, statistics and (in PostgreSQL) memory settings like work_mem.

Analogy

Matching wedding guests to tables. Nested loop: take each guest and look their name up in the seating plan. Hash join: first make a quick lookup card per surname, then let every guest find their card. Merge join: line up the guests alphabetically and the seating list alphabetically, then walk down both together.

Where the analogy breaks

At a wedding you would pick the method by eye. A database picks it from estimates of how many rows each side has — wrong estimates are the main reason it picks badly.

Worked example

EXPLAIN QUERY PLAN
SELECT p.category, SUM(oi.quantity * p.price)
FROM order_items oi
JOIN products p ON p.product_id = oi.product_id
GROUP BY p.category;

Must-know points

• Nested loop: best for a small outer input with an index on the inner join key.
• Hash join: best for large, unsorted equality joins; needs memory for the hash table.
• Merge join: best when both inputs are already sorted on the join key.
• The optimiser chooses using row-count estimates; stale statistics cause bad choices.
• Indexing join keys (especially foreign keys) is the single most useful join optimisation.

Common mistakes

• Thinking an index always makes a join faster: for a hash join over whole tables it may not be used at all.
• Ignoring a nested loop over two large tables without an index — it grows as N × M.
• Forcing a join method with hints instead of fixing the statistics or indexes.

In other databases

• PostgreSQL, SQL Server and Oracle use all three methods. SQLite uses nested loops (with automatic temporary indexes). MySQL added hash joins in 8.0.18.

Step 2 Go further (free, optional)

Optional. The notes above are written to be enough on their own. These free resources give a second explanation and more practice.

• Watch

  Nested loop, hash and merge joins (video)

  YouTube search, free

• Read

  PostgreSQL docs — Planner/Optimizer (join methods)

  official documentation, free

• Read

  Use The Index, Luke — a guide to database performance for developers

  Markus Winand, free

Step 3 Practise

Try each one yourself first: out loud, or written and run in the practice box below, which saves every query you run. Then open the answer and compare.

1. ExplainSay what it does and when to use it, in plain words, with no notes.

   Explain the three join methods with the wedding-guest analogy.

   Show answer

   Matching wedding guests to their tables:

   • Nested loop: take each guest in turn and look their name up in the seating plan. Quick if the seating plan has an index (sorted by name, so each lookup is fast) or if there are only a few guests. Without an index, every guest reads the whole plan: very slow for big lists.
   • Hash join: first make a quick lookup card for every name in the seating plan (a hash table, kept in memory), then let each guest find their card in one step. Great for two big lists with no index; it needs memory for the cards.
   • Merge join: line the guests up alphabetically, line the seating plan up alphabetically, then walk down both lists together, matching as you go. Great when both are already sorted (by an index); otherwise both must be sorted first.

   The optimiser picks one per join, from the sizes, the indexes and the memory available.

2. Writefrom a blank page, then run it

   Write a query joining orders and customers, run EXPLAIN QUERY PLAN, and name the join method SQLite used.

   Show answer

   The plan reads: SCAN o, then SEARCH c using the primary key. That is a nested loop: for each order (the outer loop), look up its customer by key (the inner step). SQLite only does nested loops; it makes them fast with indexes, and builds a temporary index itself when none exists. PostgreSQL would show "Nested Loop", "Hash Join" or "Merge Join" by name.

   sqlCopy

   EXPLAIN QUERY PLAN
   SELECT o.order_id, c.name
   FROM orders o
   JOIN customers c ON c.customer_id = o.customer_id;

   Try it

   2 rows

   id	parent	notused	detail
   3	0	216	SCAN o
   5	0	45	SEARCH c USING INTEGER PRIMARY KEY (rowid=?)

3. Predictsay it before you run it

   Joining a 10-row table to a 10-million-row table with an index on the big table's join key — which method would you expect?

   Show answer

   A nested loop, with the small table outside. Loop over the 10 rows, and for each one search the big table's index: 10 index lookups of a few steps each, a few dozen page reads in all.

   A hash join would have to read all 10 million rows of the big table (to build or to probe), and a merge join would need it sorted. Neither can compete with 10 index lookups.

4. Edge casesSay what happens with NULLs, ties, duplicates or no rows at all, and fix it.

   Two 100-million-row tables are joined on a column with no index on either side. Which method should the optimiser pick, and what resource does it need?

   Show answer

   A hash join. A nested loop with no index would compare every row with every row: 100 million × 100 million = 10¹⁶ comparisons, which never finishes. A merge join would first have to sort both 100-million-row tables.

   A hash join reads one side (ideally the smaller after filters) and builds a hash table on the join column, then reads the other side once and probes it: about two passes over the data.

   The resource it needs is memory, for the hash table. If it doesn't fit, the database splits both sides into batches by hash and writes them to temporary disk space, then joins batch by batch (a "grace" hash join), which is slower but still linear. Big analytical joins are often limited by memory, so the work_mem (PostgreSQL) or join buffer settings matter.

Step 4 Interview-ready, then prove it

Your interview answer

About 20 to 40 seconds, said out loud.

There are three main physical join algorithms. Nested loop iterates the outer input and looks up matches in the inner — ideal when the outer side is small and the inner join key is indexed. Hash join builds an in-memory hash table on the smaller input and probes it with the larger — ideal for big equality joins without useful indexes. Merge join walks two inputs sorted on the key. The optimiser chooses based on estimated cardinalities, so bad statistics are a common cause of a poor join plan.

Follow-up questions

Tick each check when you can do it without notes