Block Nested Loop Join

• We can fully utilize our $B$ buffer pagesPNLJ]] where one for $R$, one for $S$ and one for the output buffer.
• We want to reserve as many pages as possible, that is, read $B-2$ pagespages]] of $S$.

$$\begin{array}{rl}\text{for each block of }B-2\text{ pages }{B}_r\text{ in }R:& \\ \text{for each page }{p}_s\text{ in }S:& \\ \text{for each record }{r}_i\text{ in }{B}_r:& \\ \text{for each record }{s}_j\text{ in }{p}_s:& \\ \text{if }\theta (r_i,s_j):& \text{yield }<r_i,s_j>\end{array}$$

COST= $[R]+\lceil \frac{[R]}{B-2}\rceil [S]$