Describe how a naive nested loop join produces its result, and what its cost is in terms of the sizes of the two inputs.
answer
- for each outer row, scan all of inner
- O(n*m) comparisons
- inner re-read once per outer row
- any predicate; cross join = nested loop
- pipelined, no memory, no spill
basics
~20 sFor each row of the outer input, scan the entire inner input and emit the pairs that satisfy the join predicate. Comparisons are O(n*m), and the naive form re-reads the inner input once per outer row, so I/O is the real problem.
solid answer
~50 sIt is two nested loops: take a row from the outer input, walk the whole inner input, emit every pair whose join predicate is true, then take the next outer row. Cost is the product of the input sizes in comparisons — O(n*m) — and in the naive form the inner input is re-read once per outer row, so I/O is roughly outer rows times the size of the inner input. Its virtues are generality and pipelining. It supports any join predicate, including inequalities and expressions that hashing and sorting cannot handle, so it is the universal fallback and the only way to evaluate a cross join. It also emits its first result rows immediately and needs almost no memory. Its weakness is that cost grows multiplicatively, so it is only acceptable when the outer input is small or the inner side can be probed by an index instead of scanned.
code
text · 4 linesfor each row r in OUTER:
for each row s in INNER: # inner restarted for every r
if predicate(r, s):
emit (r, s)go deeper
Give the two loops, the O(n*m) cost, and that the inner side is re-read per outer row.
Add why it is the universal fallback (any predicate), that it pipelines, and that block and index variants exist to fix the rescan cost.
Talk about outer-side choice, early-stop queries, and recognising the naive form as a risk in a plan over growing tables.
Position it as the operator with the best latency-to-first-row and worst asymptotics, and reason about when that tradeoff is deliberately worth it.
## The algorithm A nested loop join is the direct translation of the definition of a join into code. One input is designated the outer and the other the inner. For each outer row, the operator iterates over the inner input, evaluates the join predicate on the pair, and emits the pair if it holds. When the inner input is exhausted it is restarted for the next outer row. ## Cost With n outer rows and m inner rows, the predicate is evaluated n*m times. That is the CPU cost. The cost that actually kills queries is I/O: the naive version reads the whole inner input for every outer row, so if the inner table occupies P pages, the operator reads roughly n*P pages. Doubling both tables makes it four times slower, which is why a plan whose runtime explodes with data growth is often a nested loop over an unindexed inner side. ## Why it exists at all Hash join needs an equality predicate to hash on; classic merge join needs sortable equality on the join key. A nested loop needs nothing: any boolean expression over the pair works, including inequalities, ranges, expressions on both sides, and function calls. That makes it the only universally applicable join operator and the fallback whenever no equality predicate is usable. A cross join, which pairs everything with everything, is exactly a nested loop with a predicate of true. ## Other virtues It is fully pipelined: the first matching pair can be returned before most of the input has been read, which is ideal for a query that stops early, such as one asking for the first few rows. It uses almost no memory — no hash table, no sort area — so it never spills. It is also trivially correct for outer joins: track whether the current outer row found any match, and emit a padded row if it found none. ## Which side should be outer The optimizer picks. For the naive form the smaller input should generally be the outer one, because the number of inner rescans equals the number of outer rows. For outer joins the choice is constrained by semantics: the side whose rows must all be preserved cannot simply be swapped without changing the join type. ## The two improvements Because the naive form is so expensive, real engines use one of two variants. The block form reads the outer input in chunks that fit in memory and scans the inner input once per chunk instead of once per row, cutting the number of inner scans by the chunk size. The index form replaces the inner scan entirely with an index lookup per outer row, changing the cost from n times the inner table size to n times the cost of one lookup. In practice, when a plan shows a nested loop over a large inner table, the question to ask is which of these two it is — the naive version over big inputs is a bug in the making.
- Why can a nested loop join evaluate predicates that a hash join cannot?A hash join must derive a hash value from each side independently and match on equality of that value, so it only supports equality predicates on precomputed keys. A nested loop evaluates an arbitrary boolean expression on an actual pair of rows, so inequalities, range overlaps, and function-based conditions all work.
- Which input should generally be the outer one in a naive nested loop, and why?The smaller input, because the inner side is rescanned once per outer row, so the number of expensive rescans equals the outer row count. Outer-join semantics can constrain the choice, since the preserved side cannot be swapped freely without changing the query's meaning.
Checking a guest list against a badge box by taking one name and rifling the whole box for it, then putting every badge back and starting over for the next name.
saying these in an interview costs you the question
- Saying nested loop is always the worst algorithm — with a small outer input and an indexed inner side it is usually the fastest
- Quoting the cost of the naive form as O(n+m) or O(n log m)
- Forgetting that the dominant cost is repeated I/O over the inner input, not the comparisons
- Claiming it needs an equality predicate the way hash join does