Block nested loop

An algorithm used to join two relations in a relational database. A variation on the simple nested loop join used to join two relations $R$ and $S$. Suppose $|R|<|S|$. Instead of reading the two relations tuple by tuple as done by the simple nested loop join, block nested loop reads the relation $R$ in blocks filling all available internal memory except 2 pages. For each block of $R$ an iteration through $S$ is performed read one page at a time, for each page read from $S$ the tuple the page is compared with the tuples in the block of $R$, every pair of tuples that satisfy the join condition is added to the output page.

The block nested loop runs in $O(P_{r}P_{s}/M)$ I/Os where $M$ is the number of available pages of internal memory and $P_{r}$ and $P_{s}$ is size of $R$ and $S$ respectively in pages. Note that block nested loop runs in $O(P_{r}+P_{s})$ I/Os if $R$ fits in the available internal memory.