Block nested loop

A block-nested loop (BNL) is an algorithm used to join two relations in a relational database. A block-nested loop (BNL) 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} (the 'outer' and 'inner' join operands, respectively). 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. The block nested loop runs in O ( P r P s / M ) {displaystyle O(P_{r}P_{s}/M)} I/Os where M {displaystyle M} is the number of available pages of internal memory and P r {displaystyle P_{r}} and P s {displaystyle P_{s}} is size of R {displaystyle R} and S {displaystyle S} respectively in pages. Notethat block nested loop runs in O ( P r + P s ) {displaystyle O(P_{r}+P_{s})} I/Os if R {displaystyle R} fits in the available internal memory.