Block nested loop

A block-nested loop (BNL) is an algorithm used to join two relations in a relational database.^[1]

This algorithm^[2] is a variation on the simple nested loop join used to join two relations $R$ and $S$ (the "outer" and "inner" join operands, respectively). Suppose $|R| < |S|$. In a traditional nested loop join, $S$ will be scanned once for every tuple of $R$. If there are many qualifying $R$ tuples, and particularly if there is no applicable index for the join key on $S$, this operation will be very expensive.

The block nested loop join algorithm improves on the simple nested loop join by only scanning $S$ once for every group of $R$ tuples. For example, one variant of the block nested loop join reads an entire page of $R$ tuples into memory and loads them into a hash table. It then scans $S$, and probes the hash table to find $S$ tuples that match any of the tuples in the current page of $R$. This reduces the number of scans of $S$ that are necessary.

A more aggressive variant of this algorithm loads as many pages of $R$ as can be fit in the available memory, loading all such tuples into a hash table, and then repeatedly scans $S$. This further reduces the number of scans of $S$ that are necessary. In fact, this algorithm is essentially a special-case of the classic hash join algorithm.

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.

References

1. "8.2.1.14 Block Nested-Loop and Batched Key Access Joins". MySQL 5.6 Reference Manual. Oracle Corporation. Retrieved 2 August 2015.
2. "Block Nested Loop Join". MariaDB. MariaDB Corporation Ab. Retrieved 2 August 2015.