The Nested Loop Join

Why the nested loop join matters

Every relational database ships three workhorse join algorithms — nested loop, hash, and sort-merge — and the nested loop is the foundation the other two are measured against. It is the join you can write on a napkin: two for loops. Yet despite its brutal worst case, it remains the algorithm the optimizer picks most often in real OLTP workloads, because the typical transactional query filters the outer table down to a handful of rows and joins them against an indexed inner. In that regime the nested loop is not a fallback — it is optimal.

Understanding it well is the difference between a query that returns in a millisecond and one that never finishes. The classic production incident is a plan that "flips" to a nested loop join on two large tables because the optimizer's row estimate was wrong: instead of a hash join over a few million rows, you get billions of index probes or, worse, a full inner scan per outer row. Reading a query plan and recognizing a dangerous nested loop is a core database skill.

How it works, step by step

Label the two inputs the outer (or driving) table and the inner (or probed) table. The algorithm is exactly two loops:

• Outer loop. Iterate over every row r of the outer table, once.
• Inner loop. For each r, iterate over every row s of the inner table.
• Predicate test. If join_predicate(r, s) is true, emit the combined row (r, s).

The inner table is therefore read once for every outer row. If the outer has n rows and the inner has m rows, the number of predicate evaluations is exactly n·m — the Cartesian product, filtered. That product is the whole story of its cost, and also of its danger: it is quadratic when n ≈ m.

The choice of which table drives matters enormously. Because the inner is rescanned n times, you want the smaller table on the outside when neither is indexed (fewer rescans of the inner), but the indexed table on the inside when one has an index (so each probe is a cheap seek). A good optimizer decides this for you using row and index statistics; a bad plan gets it backwards.

Counting I/O, not just comparisons

CPU comparisons are only half the picture. Databases live and die by disk I/O, and the nested loop's I/O cost depends on which variant you run. Let n_p and m_p be the number of disk pages in the outer and inner tables, and let B be the number of buffer-pool pages available to the join.

• Tuple-at-a-time nested loop. Read the inner table once per outer row — I/O cost n_p + n · m_p. This is the pathological version and is essentially never used as-is.
• Page nested loop. Read the inner table once per outer page — I/O cost n_p + n_p · m_p. Better, but the inner is still re-read n_p times.
• Block nested loop. Buffer B − 2 pages of the outer at a time (one page reserved for the inner scan, one for output). The inner is now scanned only ⌈n_p / (B − 2)⌉ times, giving I/O cost n_p + ⌈n_p / (B − 2)⌉ · m_p.

The block variant is why the join scales with memory: hand it a bigger buffer and the inner-table re-reads drop proportionally. In the limit where the entire outer fits in the buffer (B − 2 ≥ n_p), the inner is scanned exactly once and the cost collapses to n_p + m_p — a single sequential pass over each table. That is the best a block nested loop can do, and it explains why "put the smaller table on the outside" is the standard rule: a small outer is more likely to fit in the buffer whole.

The index nested loop join

The block variant fixes the I/O of the inner rescan, but it still touches every inner page. The index nested loop join avoids the scan entirely. If the inner table has a B-tree index on the join column, then for each outer row you take the join key and perform an index lookup — retrieving only the matching inner rows instead of scanning all m.

A B-tree lookup is O(log m), so the total cost becomes O(n log m) in comparisons, and in I/O it is roughly n_p + n · (cost of one index probe), where a probe is typically 2–4 page reads (the B-tree height plus a heap fetch). When n is small this is astonishingly cheap — which is exactly why adding an index to a foreign-key column so often turns a multi-second join into a sub-millisecond one. The optimizer notices the index exists, switches from a block nested loop to an index nested loop, and the plan cost drops by orders of magnitude.

There is a subtlety: an index nested loop does one random-access probe per outer row, and random I/O is far more expensive than sequential. If the outer is large, thousands of scattered index seeks can be slower than a single sequential hash-join build. This is precisely the threshold the optimizer's cost model tries to find — and the threshold it most often gets wrong when statistics are stale.

Nested loop vs hash vs sort-merge join

	Nested loop (naive)	Index nested loop	Hash join	Sort-merge join
Time	O(n · m)	O(n log m)	O(n + m)	O(n log n + m log m)
Extra memory	O(1)	O(1)	O(min(n, m)) for build	O(1) if pre-sorted
Join predicate	Any (=, <, BETWEEN)	Any indexable	Equality only	Equality / range
Needs an index?	No	Inner must be indexed	No	No (but likes sorted input)
Streams first rows early?	Yes	Yes	No (blocking build)	No (blocking sort)
Optimizer picks it when	Both tables tiny	Small outer + indexed inner	Large unindexed equijoin	Inputs already sorted

The headline: hash join is the linear-time champion for large equijoins, and sort-merge wins when the data is already ordered (or when you need sorted output anyway). The nested loop's niche is the small-and-selective case and the non-equijoin case that neither competitor can serve. Note too that hash and sort-merge both block — they must build a hash table or sort before emitting a single row — whereas a nested loop streams results immediately, which is why LIMIT / first-row-fast queries often prefer it.

Implementation

The three variants in Python-flavoured pseudocode. Note how little changes between them — the outer loop is identical; only the inner access path differs.

# 1. Naive (tuple-at-a-time) nested loop join
def nested_loop_join(outer, inner, match):
    for r in outer:              # n rows
        for s in inner:          # m rows, re-scanned every time
            if match(r, s):      # any predicate: =, <, BETWEEN, ...
                yield (r, s)     # streams results immediately
    # Comparisons: n * m


# 2. Block nested loop join — buffer B-2 pages of the outer at a time
def block_nested_loop_join(outer_pages, inner_pages, match, B):
    block_size = B - 2           # 1 page for inner scan, 1 for output
    for block in chunks(outer_pages, block_size):
        rows_in_block = [row for page in block for row in page]
        for page in inner_pages:            # inner scanned once PER BLOCK
            for s in page:
                for r in rows_in_block:
                    if match(r, s):
                        yield (r, s)
    # Inner re-reads: ceil(n_pages / (B-2))  — memory buys fewer scans


# 3. Index nested loop join — probe a B-tree on the inner join key
def index_nested_loop_join(outer, inner_index, match):
    for r in outer:                          # n rows
        for s in inner_index.lookup(r.key):  # O(log m) B-tree probe
            if match(r, s):                  # index gives candidates only
                yield (r, s)
    # Comparisons: n * log(m)  — the small-outer / indexed-inner sweet spot

In a real engine, outer and inner are iterators over pages, match is the compiled join predicate, and inner_index.lookup descends a B⁺-tree. PostgreSQL's nodeNestloop.c and MySQL/InnoDB's Batched Key Access (a block-plus-index hybrid) are the production embodiments of the third form.

When the optimizer chooses a nested loop

• Tiny outer input. After filtering, the outer produces only a few rows. A nested loop with an indexed inner does a few cheap probes and wins outright — no build phase, no sort, minimal memory.
• Selective index on the inner join column. When the inner has a B-tree on the join key and each key matches few rows, the index nested loop's O(n log m) beats a hash join's build cost.
• Non-equijoins. Range predicates (a.ts BETWEEN b.start AND b.end), inequalities, and spatial matches cannot drive a hash join. The nested loop is the fallback and often the only option.
• Correlated subqueries. A subquery that references the outer row is, semantically, a nested loop — evaluate the inner query once per outer row.
• First-row-fast queries. With LIMIT 10 or an interactive cursor, the nested loop's ability to stream results without a blocking build is a decisive advantage.

Common misconceptions and pitfalls

• "Nested loop join is always slow." False. It is the optimal plan for small-outer / indexed-inner joins, which dominate OLTP. It is only catastrophic on large, unindexed inputs.
• Confusing the naive and block variants. The block nested loop does the same O(n·m) comparisons but drastically less I/O. Almost every "nested loop" in a real engine is really a block or index nested loop.
• Forgetting that driving-table choice matters. Put the smaller table on the outside for un-indexed joins, but the indexed table on the inside. Getting it backwards can be 100× slower.
• A plan that flips to nested loop on two big tables. This is the classic stale-statistics incident: the optimizer under-estimates the outer row count, picks a nested loop, and the query does billions of probes. Fix with fresher statistics or a join hint.
• Assuming an index always helps. If the outer is large, thousands of scattered random index seeks can be slower than one sequential hash-join scan. Random I/O has a real cost the cost model must weigh.
• Ignoring cache effects. A small inner table that fits in the buffer pool is re-scanned from memory, not disk — so a "nested loop over a big product" can still be fast if the inner is hot in cache.

A worked example

Join orders (outer, 50 rows after a WHERE customer_id = 42 filter) to line_items (inner, 5,000,000 rows) on order_id.

• Naive nested loop: 50 × 5,000,000 = 250,000,000 comparisons, plus a full scan of line_items for every one of the 50 orders. Unusable.
• Index nested loop (B-tree on line_items.order_id): 50 probes × ~3 page reads each = ~150 page reads. Sub-millisecond. This is the plan every optimizer picks — and why a foreign-key index on order_id is mandatory.

Now flip it: join all orders (5,000,000 rows) to all customers (5,000,000 rows) on customer_id with no filter. A nested loop — even indexed — pays 5,000,000 random probes. Here a hash join that builds a hash table on the smaller side in one pass and streams the larger side through it wins decisively. Same operator family, opposite algorithm — and the boundary between them is exactly what the query optimizer exists to find.