1 Answers
A block-nested loop is an algorithm used to join two relations in a relational database.
This algorithm is a variation on the simple nested loop join used to join two relations R {\displaystyle R} and S {\displaystyle S} . Suppose | R | < | S | {\displaystyle |R|<|S|}. In a traditional nested loop join, S {\displaystyle S} will be scanned once for every tuple of R {\displaystyle R}. If there are many qualifying R {\displaystyle R} tuples, and particularly if there is no applicable index for the join key on S {\displaystyle S} , this operation will be very expensive.
The block nested loop join algorithm improves on the simple nested loop join by only scanning S {\displaystyle S} once for every group of R {\displaystyle R} tuples. For example, one variant of the block nested loop join reads an entire page of R {\displaystyle R} tuples into memory and loads them into a hash table. It then scans S {\displaystyle S} , and probes the hash table to find S {\displaystyle S} tuples that match any of the tuples in the current page of R {\displaystyle R}. This reduces the number of scans of S {\displaystyle S} that are necessary.
A more aggressive variant of this algorithm loads as many pages of R {\displaystyle R} as can be fit in the available memory, loading all such tuples into a hash table, and then repeatedly scans S {\displaystyle S}. This further reduces the number of scans of S {\displaystyle S} that are necessary. In fact, this algorithm is essentially a special-case of the classic hash join algorithm.