Block Nested Loop Join: The Simple Double Loop

Concept. Block nested loop join reads the inner table once into a RAM-sized block, then scans the outer table once for each block, matching rows with the predicate as it goes.

Intuition. When you need to join a small Songs table to a big Listens table, load Songs into RAM in one block, then scan Listens once and check each listen against every song in the block. Cost: read Songs once, read Listens ⌈P(Songs)/B⌉ times.

The Algorithm: Load Blocks, Scan Everything

A double-for-loop in disguise. Outer loop loads blocks of B pages from the smaller table; inner loop scans the entire larger table for each block; the join predicate fires on every pair.

Block Nested Loop Join: the smaller table R is loaded into RAM once. The larger table S is then streamed page-by-page; each S page is probed against the R block in RAM. Cost when R fits in 1 block: P(R) + P(S) page reads.

Figure 1. Block Nested Loop Join, R ⋈ S. The smaller table R is read from disk and held entirely in RAM for the whole join; the larger table S streams past in 4 pages, each loaded into a one-page slot, probed against R, then discarded, producing 8 joined rows (2 per S page here). Best case, when R fits in B pages, is P(R) + P(S) + OUT; if R is bigger than B it becomes P(R) + ⌈P(R)/B⌉ × P(S) + OUT because S is re-scanned once per R-block, so always make the smaller table the outer one.

BNLJ(R, S, B):                        // R = smaller table (outer), S = larger (inner), B = RAM pages

    // Outer loop: read R one block at a time
    for each block of B pages in R:
        load the block into RAM

        // Inner loop: scan all of S once for this block
        for each page s of S:
            load s into RAM
            for each row r in block, row t in s:
                if r matches t:               // any predicate: equality, range, similarity
                    emit (r, t)

Example: Songs ⋈ Listens

Find all listens for each song. P(Songs) = 100 pages, P(Listens) = 10,000 pages, buffer B = 10 pages. Put the smaller table (Songs) on the outer loop.

Step	IOs
Read Songs once	100
Blocks of Songs: ⌈100 / 10⌉	10
Scan Listens, once per block: 10 × 10,000	100,000
Total (plus OUT for the result)	100,100

Compared to a row-by-row nested loop, which rereads Listens once per Songs row (millions of scans), block nested loop is orders of magnitude cheaper just by buffering a block at a time.

Wrong Choice: Listens as Outer

If we used BNLJ(Listens, Songs):

Blocks: ⌈10,000/10⌉ = 1,000
Scan Songs: 1,000 × 100 = 100,000
Total: 110,000 IOs (10% worse)

Non-Equality Joins: Where BNLJ Shines

BNLJ handles any join condition

Unlike other JOIN algorithms, BNLJ supports:

Similarity: similarity(s.features, a.style) > 0.8
Complex conditions: s.duration > a.avg_length * 1.5 AND s.genre = a.genre

Real Example: Find Songs Similar to Artist's Style

-- Find songs similar to what the artist usually makes
SELECT s.song_id, a.artist_id
FROM Songs s
JOIN Artists a ON distance(s.audio_vector, a.style_vector) < 0.2
                  AND s.duration BETWEEN a.min_duration AND a.max_duration;

-- Only BNLJ can handle this complex join!

When BNLJ Wins

Use BNLJ when	Avoid BNLJ when
Non-equality joins (range, similarity, distance)	Both tables are huge
One table is small	Simple equality join
Large buffer available (few blocks, few scans)	Tables already sorted
No indexes exist	Small buffer

BNLJ rescans the inner table once per block of the outer, so when both tables dwarf RAM the cost turns quadratic. That is exactly the case the next algorithm removes.

Hash Partition Join → When both tables are too big for BNLJ and the join is an equality, hash partitioning turns a quadratic problem into a linear one.