skip to content

What is a block nested loop join, and which weakness of the row-at-a-time version does it address?

level: middleimportance: should knowfreq 40%

answer

  1. buffer a block of outer rows
  2. inner scanned once per block, not per row
  3. I/O: P_o + (P_o/B) * P_i
  4. comparison count unchanged — still the product
  5. equality predicate? prefer hash join

basics

~20 s

Instead of one outer row at a time, it buffers a block of outer rows that fits in memory and scans the inner input once per block, comparing each inner row against every buffered outer row. Inner scans drop from the outer row count to the number of blocks; the comparison count stays the same.

solid answer

~50 s

The naive form re-reads the entire inner input once per outer row, so I/O scales with outer row count. The block variant fills a memory buffer with as many outer rows as fit, then scans the inner input once, checking each inner row against every outer row in the buffer, then refills the buffer with the next batch. If the outer input occupies P pages and the buffer holds B pages, the inner input is scanned about P/B times instead of once per row, so I/O becomes roughly P_outer + (P_outer/B) * P_inner. The CPU comparison count is still the product of the two input sizes, since every pair is still examined — the win is purely in I/O. It is the fallback when the inner side has no usable index, and larger buffers monotonically reduce inner rescans. Modern engines increasingly replace it with a hash join when the predicate is an equality.

code

text · 5 lines
text
while OUTER has rows:
    block = read next B pages of OUTER
    for each row s in INNER:        # one full inner scan per block
        for each row r in block:
            if predicate(r, s): emit (r, s)

go deeper

for a junior

Say it processes outer rows in batches so the inner table is scanned once per batch instead of once per row.

for a middle

Give the cost formula, note the comparison count is unchanged, and state that the smaller input belongs on the outer side.

for a senior

Treat it as a diagnostic signal: no index and no usable equality; discuss the index or hash-join rewrite rather than tuning the buffer.

for a principal

Weigh memory grants against the fact that only the I/O term improves, and decide whether the schema or the predicate should change instead.

## The problem it solves In a naive nested loop, the inner input is read from scratch for every outer row. If the outer input has a million rows and the inner table is a hundred pages, that is a hundred million page reads even though the inner table is tiny. The comparisons were never the bottleneck; the repeated reading was. ## The idea Buffer the outer side. Read as many outer rows as the join buffer holds, then scan the inner input once. For each inner row, compare it against all buffered outer rows and emit any matches. Refill the buffer and repeat. The inner input is now read once per buffer-load rather than once per row. ## The cost model Let the outer input span P_o pages, the inner P_i pages, and the buffer hold B pages of outer rows. The outer input is read once: P_o. The inner input is read once per block, and there are ceil(P_o / B) blocks: ceil(P_o/B) * P_i. Total I/O is P_o + ceil(P_o/B) * P_i. Two consequences follow. First, more join-buffer memory directly reduces I/O, with diminishing returns. Second, the smaller input should be the outer one, because it determines the number of blocks. If the whole outer input fits in the buffer, the inner side is scanned exactly once and the join is close to two sequential scans. ## What does not improve The number of predicate evaluations is unchanged: every outer row is still compared with every inner row, so CPU cost stays proportional to the product of the input sizes. For an equality predicate this is precisely where a hash join is strictly better — it also reads each input once, but replaces the quadratic comparison count with hash-table probes. Some engines organise the buffered block into an in-memory hash table for equality predicates, which is the conceptual bridge to hash join; several engines have removed the block variant for equality joins entirely in favour of a real hash join. ## When it is still the right operator When the predicate is not an equality — range overlaps, inequalities, expressions — hashing is unavailable, and if no index supports the inner side either, the block form is the best remaining plan. It is also reasonable when both inputs are small enough that the quadratic comparison count is irrelevant. ## Reading it operationally Seeing a block nested loop over two large tables in a plan is a warning: the join is quadratic in comparisons and the engine could not find an index or an equality to exploit. The usual fixes are adding an index on the inner join column so the plan becomes an index nested loop, rewriting the predicate so an equality is exposed for a hash join, or reducing the outer side with a more selective filter. Raising the join-buffer memory helps the I/O term but never removes the quadratic comparison term, so it is a mitigation rather than a fix.

  • If you double the join-buffer memory, what happens to the cost of a block nested loop join?
    The number of inner scans roughly halves, so the I/O term drops by about half, with diminishing returns once the whole outer input fits in the buffer. The number of predicate evaluations does not change at all, because every outer row is still compared with every inner row.

saying these in an interview costs you the question

  • Claiming the block variant reduces the number of comparisons — it only reduces inner-input rescans
  • Confusing it with a hash join because both buffer one side; the block form still compares every pair
  • Putting the larger input on the outer side, which maximises the number of blocks
  • Treating a bigger join buffer as a fix for a quadratic join rather than a mitigation

context

resolving links…