SQL 107 🛢️ Join Algorithms: Nested Loop, Hash Join, and Merge Join - KandZ

⏱️ Estimated read: 16 min | |

A join is the operation that combines rows from two tables based on a condition. The SQL statement says what to join; the optimizer chooses how to join it. That choice is one of three physical algorithms: nested loop, hash join, or merge join. Each has a different cost profile, a different set of conditions under which it is optimal, and a different failure mode when the optimizer chooses it for the wrong input sizes. The difference is not academic. A nested loop join on two million-row tables is a quadratic disaster; a hash join on a tiny indexed lookup is unnecessary memory pressure; a merge join without sorted inputs pays for a sort that a hash join would have avoided entirely .

The choice is driven by the statistics covered in the previous chapter. The optimizer estimates the cardinality of each input, the presence of indexes, and whether the inputs are already sorted. From those estimates it assigns a cost to each algorithm and picks the lowest. This chapter explains what each algorithm does, when the optimizer chooses it, and what the plan looks like when it does.

Key point: Nested loop joins are for small outer inputs with an indexed inner input; hash joins are for large, unsorted, non-indexed equijoins where the smaller input fits in memory; merge joins are for inputs that are already sorted on the join key or where the output must be sorted.

Why three algorithms exist

The size problem. The three algorithms have different complexity. A nested loop join is O(n*m) in the worst case: for each row of the outer table, it scans the inner table. That is fine when the outer table has ten rows and the inner table has an index, because the inner scan is an index lookup, not a table scan. It is catastrophic when both tables are large and unsorted. A hash join is O(n+m): it scans each input once, builds a hash table on one side, and probes it with the other. A merge join is also O(n+m), but it requires both inputs to be sorted on the join key .

The memory problem. A hash join needs memory for the hash table. If the build side fits in memory, the hash join is fast and scans each input once. If it does not fit, the hash join partitions the data and spills to disk, which adds I/O. A merge join needs no hash table, only buffers for the merge, but it pays for sorting if the inputs are not already sorted. A nested loop join needs almost no memory, only the buffer for the current outer row and the index traversal on the inner side .

The sort problem. A merge join has a property the other two do not: it produces output in join-key order. If the query has an ORDER BY on the join key, or if the next operation in the plan requires sorted input, the merge join’s sort cost is not wasted. A hash join destroys the order. A nested loop join produces rows in the order of the outer table, which may or may not be useful .

a. Nested loop join: the index-driven algorithm

A nested loop join has two inputs: the outer (driving) input and the inner (driven-to) input. For each row of the outer input, the algorithm scans the inner input for matching rows. In the naive form, the inner scan is a full table scan, which is O(n*m). In the indexed form, the inner scan is an index lookup on the join column, which is O(n log m) or better .

-- A query that is a candidate for a nested loop join
-- The WHERE clause filters the outer table to a small number of rows
-- The inner table has an index on the join column
SELECT o.id, o.total, c.name
FROM orders o
JOIN customers c ON c.id = o.customer_id
WHERE o.created_at > NOW() - INTERVAL '1 day'
  AND o.status = 'PENDING';

The optimizer estimates that the orders filter returns a small number of rows. For each of those rows, it looks up customers by primary key. The index lookup is cheap, and the total cost is the number of outer rows multiplied by the index lookup cost. If the estimate is wrong and the outer filter returns a million rows, the nested loop becomes a million index lookups, which is slower than a single hash join .

-- The plan for the nested loop join
-- The outer input is the filtered orders
-- The inner input is the customers index lookup
EXPLAIN SELECT o.id, o.total, c.name
FROM orders o
JOIN customers c ON c.id = o.customer_id
WHERE o.created_at > NOW() - INTERVAL '1 day'
  AND o.status = 'PENDING';

-- Output:
-- Nested Loop
--   -> Index Scan on orders (created_at, status)
--   -> Index Scan on customers (id)

The key property of the nested loop is its startup latency. It produces the first row as soon as the first outer row finds a match. It does not need to read the entire inner table first. This is why it is the right choice for a LIMIT 1 query or an interactive pagination query where the user wants the first page immediately .

b. Hash join: the memory-driven algorithm

A hash join has two phases. The build phase reads the smaller input and constructs an in-memory hash table keyed on the join column. The probe phase reads the larger input, computes the hash of each row’s join key, and looks up the matching rows in the hash table. Each input is scanned exactly once .

-- A query that is a candidate for a hash join
-- Both tables are large and have no useful index on the join column
-- The join is an equijoin
SELECT o.id, o.total, c.name
FROM orders o
JOIN customers c ON c.id = o.customer_id
WHERE o.total > 1000;

The optimizer estimates that neither input is small, and neither has a sorted index on the join column. The hash join builds a hash table on customers (the smaller side) and probes it with orders. The cost is a single scan of each table plus the hash computation, which is O(n+m) .

-- The plan for the hash join
-- The Hash node builds the table from customers
-- The probe side is orders
EXPLAIN SELECT o.id, o.total, c.name
FROM orders o
JOIN customers c ON c.id = o.customer_id
WHERE o.total > 1000;

-- Output:
-- Hash Join
--   Hash Cond: (o.customer_id = c.id)
--   -> Seq Scan on orders (filter: total > 1000)
--   -> Hash
--         -> Seq Scan on customers

The hash join’s weakness is memory. If the build side does not fit in the available memory, the join partitions the data and spills to disk, which adds I/O that the plan did not account for. The optimizer’s cost model includes a memory grant estimate, but the estimate can be wrong, and the runtime spill is a common cause of unpredictable hash join performance .

The hash join is the workhorse of the data warehouse. It handles large, unsorted, non-indexed inputs efficiently, which is exactly the profile of an analytical query joining fact and dimension tables .

c. Merge join: the sorted-input algorithm

A merge join requires both inputs to be sorted on the join key. It scans both inputs in parallel, advancing the pointer on the side with the smaller key until it finds a match. When the keys are equal, it outputs the joined rows and advances both sides .

-- A query that is a candidate for a merge join
-- Both tables have indexes on the join column
-- The indexes provide the sorted order without an explicit sort
SELECT o.id, o.total, c.name
FROM orders o
JOIN customers c ON c.id = o.customer_id
ORDER BY o.customer_id;

The optimizer sees that orders has an index on customer_id and customers has an index on id. Both indexes deliver rows in sorted order, so the merge join needs no sort operation. The join scans both indexes once, which is O(n+m) with no hash table and no memory grant .

-- The plan for the merge join
-- Both inputs are index scans that deliver sorted output
EXPLAIN SELECT o.id, o.total, c.name
FROM orders o
JOIN customers c ON c.id = o.customer_id
ORDER BY o.customer_id;

-- Output:
-- Merge Join
--   Merge Cond: (o.customer_id = c.id)
--   -> Index Scan on orders (customer_id)
--   -> Index Scan on customers (id)

The merge join’s cost is dominated by the sort. If the inputs are already sorted by an index, the sort is free. If they are not, the optimizer must insert a Sort node before the merge, and that sort is a blocking operation: it reads the entire input, sorts it, and only then produces the first row. This is why a merge join without sorted inputs has high startup latency and is often not the right choice for an interactive query .

The merge join is the right choice when the query has an ORDER BY on the join key, because the join delivers the rows in the required order and the sort is shared between the join and the ordering . It is also the right choice when both inputs are large but already sorted by their indexes, because it avoids the memory grant that a hash join would need .

Complete Example Session

The following session runs the same logical query three times, forcing each join algorithm, and shows the plan and the cost difference.

-- ============================================
-- PART 1: THE DATA
-- ============================================
-- orders: 1,000,000 rows, indexed on customer_id
-- customers: 10,000 rows, primary key on id
-- The join is equijoin on customer_id = id

-- ============================================
-- PART 2: THE DEFAULT PLAN (OPTIMIZER CHOICE)
-- ============================================
EXPLAIN ANALYZE
SELECT o.id, o.total, c.name
FROM orders o
JOIN customers c ON c.id = o.customer_id
WHERE o.total > 1000;

-- The optimizer likely chooses a hash join
-- Hash Join (cost=... rows=...)
--   -> Seq Scan on orders (filter: total > 1000)
--   -> Hash -> Seq Scan on customers

-- ============================================
-- PART 3: FORCING A NESTED LOOP
-- ============================================
SET enable_hashjoin = off;
SET enable_mergejoin = off;
EXPLAIN ANALYZE
SELECT o.id, o.total, c.name
FROM orders o
JOIN customers c ON c.id = o.customer_id
WHERE o.total > 1000;

-- Nested Loop
--   -> Seq Scan on orders (filter: total > 1000)
--   -> Index Scan on customers (id)
-- The cost is high because the orders filter is not selective

-- ============================================
-- PART 4: FORCING A MERGE JOIN
-- ============================================
SET enable_hashjoin = off;
SET enable_nestloop = off;
EXPLAIN ANALYZE
SELECT o.id, o.total, c.name
FROM orders o
JOIN customers c ON c.id = o.customer_id
WHERE o.total > 1000;

-- Merge Join
--   Merge Cond: (o.customer_id = c.id)
--   -> Sort on orders (customer_id)
--   -> Sort on customers (id)
-- The sort is the cost; the join itself is cheap

-- ============================================
-- PART 5: THE SORTED CASE
-- ============================================
-- The same query with an ORDER BY on the join key
-- The merge join avoids the sort because the index provides the order
SET enable_hashjoin = off;
SET enable_nestloop = off;
EXPLAIN ANALYZE
SELECT o.id, o.total, c.name
FROM orders o
JOIN customers c ON c.id = o.customer_id
WHERE o.total > 1000
ORDER BY o.customer_id;

-- Merge Join
--   -> Index Scan on orders (customer_id)
--   -> Index Scan on customers (id)
-- No sort node; the merge join is now the cheapest plan

The five parts cover the data profile, the default hash join, the forced nested loop, the forced merge join with sort, and the merge join with index-provided order. What the session demonstrates is that the algorithm choice is a function of the input sizes, the indexes, and the required output order.

Quick Reference

Algorithm Comparison

Aspect	Nested Loop	Hash Join	Merge Join
Complexity	O(n*m) naive; O(n log m) indexed	O(n+m)	O(n+m) after sort
Memory	Low	High (hash table)	Low (buffers)
Startup latency	Low	High (build phase)	High if sort needed
Requires index	Inner side (for efficiency)	No	No (but sort needed)
Requires sort	No	No	Yes, or sorted index
Equijoin only	No	Yes	Yes (or range)
Output order	Outer table order	None	Join-key order

When the Optimizer Chooses

Condition	Algorithm
Small outer input, indexed inner	Nested Loop
Large inputs, no index, equijoin	Hash Join
Both inputs sorted on join key	Merge Join
Query has `ORDER BY` join key	Merge Join
`LIMIT 1` or first-row priority	Nested Loop
Memory constrained	Nested Loop or Merge

Plan Operators

Database	Nested Loop	Hash Join	Merge Join
PostgreSQL	`Nested Loop`	`Hash Join`	`Merge Join`
MySQL	`Nested loop`	`Hash join`	`Sort merge`
SQL Server	`Nested Loops`	`Hash Match`	`Merge Join`
Oracle	`NESTED LOOPS`	`HASH JOIN`	`SORT MERGE JOIN`

Best Practices

✅ Do This:

-- Let the optimizer choose; it usually gets it right
EXPLAIN ANALYZE SELECT ...;

-- Ensure the inner side of a nested loop has an index
CREATE INDEX ON customers (id);

-- Use an ORDER BY on the join key to make merge join free
SELECT ... ORDER BY o.customer_id;

❌ Don’t Do This:

-- Force a nested loop on two large tables
SET enable_hashjoin = off; -- quadratic disaster

-- Force a hash join when the build side does not fit in memory
-- The hash join spills to disk

-- Use a merge join without sorted inputs
-- The sort dominates the cost

Common Pitfalls

Pitfall	Why It Happens	Fix
Nested loop on large outer	Estimate wrong; filter not selective	Update statistics
Hash join spills to disk	Build side too large	Increase memory or use merge
Merge join sort dominates	No index on join key	Create index or use hash
Plan changes after data growth	Stale statistics	Update statistics
`ORDER BY` forces sort	Hash join loses order	Merge join with index

Real-World Examples

1. Nested loop with index

SELECT * FROM orders o JOIN customers c ON c.id = o.customer_id
WHERE o.id = 123;

2. Hash join for large equijoin

SELECT * FROM fact JOIN dim ON dim.id = fact.dim_id;

3. Merge join with sorted indexes

SELECT * FROM a JOIN b ON a.id = b.id ORDER BY a.id;

4. Nested loop for first row

SELECT * FROM orders o JOIN customers c ON c.id = o.customer_id LIMIT 1;

5. Hash join with filter

SELECT * FROM orders o JOIN customers c ON c.id = o.customer_id
WHERE o.total > 1000;

6. Merge join with explicit sort

SELECT * FROM a JOIN b ON a.id = b.id ORDER BY b.id;

7. Nested loop with composite index

CREATE INDEX ON orders (customer_id, status);

8. Hash join build side

-- The smaller table is the build side
-- The optimizer chooses automatically

9. Merge join for range

SELECT * FROM a JOIN b ON a.id BETWEEN b.lo AND b.hi;

10. Force plan for testing

SET enable_hashjoin = off;

Visual

Nested Loop

┌──────────────────────────────────────────────┐
│  Outer table (small)                         │
│  ┌─────┐                                     │
│  │ R1  │──▶ Index lookup on inner ──▶ match  │
│  │ R2  │──▶ Index lookup on inner ──▶ match  │
│  │ R3  │──▶ Index lookup on inner ──▶ match  │
│  └─────┘                                     │
│  Inner table scanned via index per outer row │
└──────────────────────────────────────────────┘

Hash Join

┌──────────────────────────────────────────────┐
│  Build phase: smaller table                  │
│  ┌─────┐                                     │
│  │ R1  │──▶ hash(R1.key) ──▶ hash table      │
│  │ R2  │──▶ hash(R2.key) ──▶ hash table      │
│  └─────┘                                     │
│         │                                    │
│         ▼                                    │
│  Probe phase: larger table                   │
│  ┌─────┐                                     │
│  │ S1  │──▶ hash(S1.key) ──▶ lookup ──▶ match│
│  │ S2  │──▶ hash(S2.key) ──▶ lookup ──▶ match│
│  └─────┘                                     │
└──────────────────────────────────────────────┘

Merge Join

┌──────────────────────────────────────────────┐
│  Both inputs sorted on join key              │
│  ┌─────┐     ┌─────┐                         │
│  │ 1   │     │ 1   │──▶ match                │
│  │ 3   │     │ 2   │                         │
│  │ 5   │     │ 4   │                         │
│  └─────┘     └─────┘                         │
│  Advance the smaller key; output matches     │
└──────────────────────────────────────────────┘

Summary

Item	Value
Nested loop	O(n*m) naive; indexed inner for efficiency
Hash join	O(n+m); build hash on smaller side
Merge join	O(n+m) after sort; requires sorted inputs
Nested loop best	Small outer, indexed inner
Hash join best	Large inputs, equijoin, no index
Merge join best	Sorted inputs, `ORDER BY` join key
Hash join memory	Build side must fit in memory
Merge join sort	Blocking; high startup latency
Nested loop startup	Low; first row fast
Hash join equijoin	Yes
Merge join equijoin	Yes

Key takeaways:

Nested loop joins are for small outer inputs with an indexed inner input. The algorithm is O(n*m) in the worst case, but the index turns the inner scan into a lookup. It has the lowest startup latency and is the right choice for LIMIT 1 or interactive pagination .
Hash joins are for large, unsorted, non-indexed equijoins. The algorithm scans each input once, builds a hash table on the smaller side, and probes it with the larger side. It is the workhorse of the data warehouse, but it needs memory for the hash table and spills to disk when the build side does not fit .
Merge joins are for sorted inputs. The algorithm scans both inputs in parallel and merges them. It avoids the hash table’s memory grant, but it pays for a sort when the inputs are not already sorted by an index. It is the right choice when the query has an ORDER BY on the join key .
The optimizer chooses based on statistics. The cardinality estimates from the previous chapter determine the input sizes, and the index metadata determines the access paths. When the estimates are wrong, the optimizer chooses the wrong algorithm, and the query runs orders of magnitude slower .
The plan is a function of the data, not the SQL. The same SELECT can use a hash join on Monday and a nested loop on Tuesday, because the data changed and the statistics were updated. The EXPLAIN output is the only way to know which algorithm is actually running .

Remember: The three join algorithms are the physical implementations of the logical join. The optimizer picks one based on the statistics, the indexes, and the required output order. Nested loop is the index-driven algorithm for small inputs. Hash join is the memory-driven algorithm for large, unsorted equijoins. Merge join is the sort-driven algorithm for inputs that are already ordered. The plan tells you which one the database chose, and the statistics tell you why. When a query is slow, the first question is not “how do I rewrite the SQL?” but “which join algorithm is running, and is it the right one for these inputs?”

Was this helpful?

Stop using slow, ad-bloated tool sites! 🤮

🔎 Search “KandZ Tools” on Google to use many professional utilities for free.

KandZ.me is the ultimate minimalist hub for:
✅ Finance (Mortgage, Interest, Inflation)
✅ Tech (Base64, JSON, Dev Suite, IP)
✅ Health (BMI, BMR, TDEE)
✅ Productivity (Timer, Workspace, QR)

⚡️ Fast & Private
🔒 No data leaves your device
💎 100% Free

🔗 Use it now: https://tools.kandz.me
🔖 Bookmark it—you’ll need it later!