Nested Loop Join
Count page reads, not comparisons — and watch one buffer-sized change cut the cost by a third.
Skip to the animationNested loop join compares every row of one relation with every row of another; its cost is measured in page reads, and the fix is to hold as much of the outer relation in memory as possible.
Count page reads, not comparisons
A disk read costs on the order of a hundred thousand times a comparison, so an algorithm's cost is essentially the number of pages it fetches. Every join algorithm is designed around that single number.
| Variant | Page reads | Note |
|---|---|---|
| Simple nested loop (per page) | M + M×N | inner relation re-read once per outer page |
| Block nested loop | M + ⌈M/B⌉ × N | B pages of buffer for the outer relation |
| Indexed nested loop | M + m × lookup | needs an index on the inner join key |
| Sort-merge | sort + M + N | output arrives sorted |
| Hash join | ≈ 3(M + N) | equality joins only, usually the winner |
M and N are page counts; m is the number of rows in the outer relation. Simple nested loop is the only entry that grows as a product, which is why it is the one that makes a query appear to hang.
Where the waste is
In the simple version, the inner relation is read from the beginning for every page of the outer one. The pages fetched on the second pass are byte-for-byte the ones discarded on the first — the algorithm simply has no memory of having seen them.
Block nested loop changes nothing about the comparisons and only changes the read pattern: fill the buffer with as many outer pages as fit, then scan the inner relation once against all of them. Cost falls from M×N to ⌈M/B⌉ × N, so more memory buys fewer reads directly. With enough buffer for the whole outer relation, the inner one is read exactly once and the join costs M + N.
Two decisions the planner makes
- Which relation goes outside. The outer is read once and the inner repeatedly, so the smaller relation belongs on the outside. Getting this backwards can cost an order of magnitude, and it is decided from table statistics — which is why stale statistics make queries mysteriously slow.
- Which algorithm at all. Hash join usually wins for large equijoins; sort-merge wins when the output needs to be sorted anyway or the inputs already are; indexed nested loop wins when the outer relation is small and the inner is indexed.
Nested loop survives all of them for one reason: it is the only algorithm that handles non-equality join conditions. Hash join needs equality to hash on, and sort-merge needs equality to align on. For R.a < S.b, nested loop is what you get.
Advantages and disadvantages
Advantages
- Works for any join condition, including inequalities and arbitrary predicates.
- Trivial to implement and needs no preprocessing of either relation.
- With an index on the inner relation it is genuinely fast.
- Extra buffer memory translates directly into fewer reads.
Disadvantages
- Cost grows as the product of the two relation sizes without blocking.
- Beaten by hash join on almost every large equijoin.
- Very sensitive to which relation is chosen as outer.
Watch it work
Check yourself
question 1 / 4
One question at a time. Pick an answer to see why it is right or wrong, then move on — there is no score to keep and nothing is saved.