Join Algorithms: Nested-Loop

A join combines tuples from two relations, `r` (with `n_r` tuples occupying `b_r` disk blocks) and `s` (with `n_s` tuples occupying `b_s` disk blocks), that satisfy a predicate `θ`. The nested-loop join family evaluates this by nesting two loops: an outer loop that iterates over one relation, and an inner loop that iterates over the other, testing `θ` on every pair `(t_r, t_s)` encountered. Any pair satisfying `θ` is emitted as an output tuple. The relation driving the outer loop is called the outer relation; the other is the inner relation. This naming matters for cost: the inner relation may be scanned from disk many times (once per outer tuple, or once per outer block), while the outer relation is scanned exactly once. A correct implementation must guarantee two properties: completeness — every tuple pair satisfying `θ` is produced exactly once — and soundness — no pair violating `θ` is produced. Both follow immediately from the fact that the double loop enumerates the full Cartesian product `r × s` and filters by `θ`, so nested-loop join is correct for any predicate `θ`, including inequalities, disjunctions, and non-equijoins where sort-merge and hash join do not directly apply. There are three standard variants, distinguished by how much work is redone on the inner relation: simple nested-loop join re-reads the inner relation from disk for every single outer tuple; block nested-loop join re-reads the inner relation only once per outer block (or once per buffer-full of outer tuples), amortizing the cost; and index nested-loop join replaces inner scanning entirely with lookups into a pre-built index on the inner relation's join attribute, turning an O(b_s) inner search into an O(log b_s) or O(1)-ish probe.

Simple nested-loop join (SNLJ). For each tuple of the outer relation, scan the entire inner relation and test the predicate against every inner tuple. ``` function SimpleNestedLoopJoin(r, s, θ): for each tuple t_r in r: # outer loop, |r| iterations for each tuple t_s in s: # inner loop, |s| iterations each time if θ(t_r, t_s) is true: output the concatenated tuple (t_r, t_s) ``` Correctness is immediate: the double loop visits every ordered pair `(t_r, t_s) ∈ r × s` exactly once, and emits it iff `θ` holds — this is literally the definition of `r ⋈_θ s`. The cost problem is that `s` must be re-read from disk `n_r` times (once per outer tuple) unless `s` fits entirely in the buffer pool.

Block nested-loop join (BNLJ). The key optimization: instead of iterating tuple-by-tuple, iterate block-by-block. For every block of `r` held in the buffer, scan `s` once and match every tuple in that block of `r` against every tuple in that block of `s`. ``` function BlockNestedLoopJoin(r, s, θ): for each block B_r of r: # outer loop, b_r iterations for each block B_s of s: # inner loop, b_s iterations each time for each tuple t_r in B_r: for each tuple t_s in B_s: if θ(t_r, t_s) is true: output the concatenated tuple (t_r, t_s) ``` This reduces the number of times `s` is scanned from `n_r` down to `b_r` — a large win because `b_r ≪ n_r` (many tuples pack into one block). A further refinement uses all available buffer pages: if `M` buffer pages are available, reserve one for the inner scan, one as output buffer, and load `M − 2` blocks of `r` at a time, so `s` is scanned only `⌈b_r / (M−2)⌉` times.

Index nested-loop join (INLJ). If an index already exists on the join attribute of the inner relation, replace the inner scan with an index probe: for each outer tuple, use the index to jump directly to matching inner tuples instead of testing every inner tuple. ``` function IndexNestedLoopJoin(r, s, index_on_s, θ): for each tuple t_r in r: # outer loop, n_r iterations matches = index_on_s.lookup(t_r.join_key) # cost c per lookup for each t_s in matches: if θ(t_r, t_s) is true: # extra check for non-key predicates output the concatenated tuple (t_r, t_s) ``` Here `c` is the cost of one index lookup: for a B+-tree index this is typically `O(height of tree) + (blocks holding matching records)`, i.e. very cheap relative to a full scan of `s`. If `r` also has an index that can be scanned in the outer loop, the outer relation can likewise be traversed via its own index rather than a full table scan, further lowering cost when only a fraction of `r` is relevant.

Notation. Let `n_r, n_s` be the tuple counts and `b_r, b_s` the block (page) counts of `r` and `s` respectively; `M` is the number of buffer pages available to the join operator; `c` is the cost of one index lookup on the inner relation (index height plus matching leaf/data blocks).

Simple nested-loop join. For each of the `n_r` outer tuples, the algorithm re-scans all `b_s` blocks of `s`. Reading `r` itself costs `b_r` block transfers (one pass). Hence: ``` Cost(SNLJ) = b_r + n_r · b_s (block transfers, worst case, 3 buffer pages: 1 for r, 1 for s, 1 output) ``` This is the dominant cost because `n_r` (tuple count) is typically far larger than `b_r` (block count) — a table with 1,000,000 tuples might occupy only 10,000 blocks, so re-reading `s` per tuple rather than per block is roughly 100× more expensive than necessary. CPU cost is `O(n_r · n_s)` comparisons in the worst case, since every tuple pair is tested.

Block nested-loop join. With the minimal 3-buffer-page assumption (1 page for scanning `r` block by block, 1 for scanning `s`, 1 for output), the inner relation `s` is re-scanned once per block of `r`, not once per tuple: ``` Cost(BNLJ) = b_r + b_r · b_s (minimal buffer, 3 pages) ``` If `M > 3` buffer pages are available, `M − 2` blocks of `r` can be held at once (reserving one page for scanning `s` and one for output), so `s` is scanned only `⌈b_r / (M − 2)⌉` times: ``` Cost(BNLJ, M buffers) = b_r + ⌈b_r / (M − 2)⌉ · b_s ``` As `M` grows to hold all of `r` in memory (`M − 2 ≥ b_r`), this collapses to `Cost = b_r + b_s`, i.e. one pass over each relation — the best possible I/O cost for any join algorithm that must read both relations at all. This is the theoretical floor that sort-merge and hash join also aim for, but block nested-loop reaches it without needing a build phase or a sort, at the price of `O(n_r · n_s)` worst-case comparisons (CPU-bound, not I/O-bound, when buffer is generous). Why the block grouping is correct: every tuple `t_r` in block `B_r` is still compared against every tuple `t_s` in every block `B_s` across the full outer loop over all blocks of `s`, so the union over all iterations still enumerates all of `r × s` — completeness and soundness are preserved; only the order and grouping of comparisons changed, not the set of pairs tested.

Index nested-loop join. The outer relation is scanned once (`b_r` block transfers, or fewer if the outer relation is itself accessed via an index scanning only relevant blocks). For each of `n_r` outer tuples, one index probe costs `c`: ``` Cost(INLJ) = b_r + n_r · c ``` For a B+-tree index with `n_s` inner entries, `c ≈ (height of the tree) + (number of matching blocks)`, typically `O(log_F n_s)` for fanout `F`, plus one block read per matching tuple if the index is not clustering. When the join attribute is a key (at most one match per lookup) and the index is small relative to the table (few levels), `c` can be as low as 2–4 block transfers — vastly cheaper than scanning all of `b_s`. This is why INLJ dominates whenever a suitable index exists and the outer relation is not enormous, since its cost scales with `n_r` (number of probes) rather than `n_r · b_s`.

Correctness invariant, formally. Define the processed set `P` after some number of loop iterations as the set of pairs `(t_r, t_s)` that have been compared so far. Every nested-loop variant maintains the invariant that after the algorithm terminates, `P = r × s` (the full Cartesian product has been enumerated), and a pair is output iff it is in `P` and satisfies `θ`. Simple, block, and index variants only differ in how `P` grows to cover `r × s` (tuple-by-tuple, block-by-block, or via index lookups covering exactly the matching subset) — index NLJ in fact never materializes non-matching pairs at all, restricting `P` to only pairs the index proves cannot fail an equality predicate, then applying `θ` to filter any residual conditions.

Tradeoffs, honestly. Nested-loop joins need essentially no extra memory (3 buffer pages suffice for correctness), unlike hash join's build-phase memory requirement or sort-merge's need to materialize sorted runs. But without an index and without a huge buffer pool, SNLJ and even the minimal-buffer BNLJ can be dramatically slower — quadratic in the number of tuples — than the `O(b_r + b_s)` I/O achievable by sort-merge or hash join when both operands are large and unindexed. The optimizer should choose nested-loop join primarily when: (a) one relation is small enough to fit in the buffer (turning BNLJ into a one-pass algorithm), (b) a usable index exists on the inner join attribute (INLJ), or (c) the join predicate is not an equality (sort-merge and hash join require equijoin-style predicates, but nested-loop handles any `θ`).

Suppose `Orders` (`r`) has `n_r = 10,000` tuples stored in `b_r = 100` blocks, and `Customers` (`s`) has `n_s = 1,000` tuples stored in `b_s = 20` blocks. The buffer pool has `M = 5` pages available to the join operator. There is a B+-tree index on `Customers.id` (the join key) with lookup cost `c = 3` block transfers per probe (2 levels of tree traversal plus 1 data block).

A few things jump out. First, moving from SNLJ to minimal-buffer BNLJ is already a ~95× improvement (200,100 → 2,100), purely from grouping the inner scan by block instead of by tuple — no extra memory required, just a smarter loop order. Second, giving BNLJ two extra buffer pages (`M = 5` instead of 3) cuts cost further to 780, illustrating that BNLJ's cost is highly sensitive to available memory: at the limit `M − 2 ≥ b_r = 100`, i.e. `M ≥ 102`, the cost would collapse to `b_r + b_s = 120`. Third, and perhaps counter-intuitively, INLJ (30,100) is here worse than the memory-rich BNLJ (780) despite having an index — because the outer relation `Orders` has 10,000 tuples, so even a cheap 3-block probe per tuple adds up (`10,000 × 3 = 30,000`). INLJ shines when the outer relation is comparatively small, or when the index lets you skip probes for tuples that clearly cannot match (e.g., a range predicate narrowing the outer scan itself). If we swap which table drives the outer loop — using `Customers` (1,000 tuples) as outer and probing an index on `Orders.cid` — INLJ's cost becomes `b_s + n_s · c = 20 + 1,000 × 3 = 3,020`, much more competitive, showing that outer/inner relation choice matters as much as the algorithm choice itself. This example is exactly the kind of arithmetic a query optimizer performs internally, using statistics gathered as described in Cost Estimation for Query Plans, before choosing between nested-loop, sort-merge, or hash join for a given query plan.

Nested-loop join is less tied to a single named inventor than to the broader development of relational query processing, since the algorithm itself is a direct generalization of the mathematical Cartesian product — but its systematic cost analysis and its coupling to buffer management emerged from foundational relational database research in the 1970s.

Every production relational database — PostgreSQL, MySQL, Oracle, SQL Server, SQLite — includes nested-loop join as one of its physical join operators, and the query optimizer chooses among nested-loop, sort-merge, and hash join based on estimated costs exactly like those derived above. Index nested-loop join in particular is the workhorse behind highly selective queries: when a query filters one table down to a handful of rows and then joins against a much larger indexed table (a common OLTP pattern, e.g., "find all orders for this one customer"), INLJ using the primary or foreign-key index is typically the fastest possible plan, far outperforming a hash join that would need to build a hash table over the entire large relation. Nested-loop join is also indispensable whenever the join predicate is not an equality — range joins, spatial joins using bounding-box predicates, or `theta`-joins in temporal databases — because sort-merge and hash join fundamentally rely on equality-comparable keys (or at least sortable/hashable keys), while nested-loop join places no such restriction on `θ`. Distributed and parallel database systems also use nested-loop join as a building block for broadcast joins, where a small relation is replicated to every partition and joined via nested loops against local partitions of a large relation — a pattern seen in systems like Apache Spark SQL and distributed OLAP engines. Finally, nested-loop join's minimal memory footprint makes it the fallback of choice in memory-constrained embedded or mobile database engines, where the buffer pool may be too small to support a hash join's build phase.

Ask the tutor: How would the cost formulas change if the inner relation's index were a hash index instead of a B+-tree, and when would that make index nested-loop join even more attractive?