A block-nested loop (BNL) is an algorithm used to join two relations in a relational database.
[1] This algorithm[2] is a variation of the simple nested loop join and joins two relations
(the "outer" and "inner" join operands, respectively).
In a traditional nested loop join,
tuples, and particularly if there is no applicable index for the join key on
The block nested loop join algorithm improves on the simple nested loop join by only scanning
Here groups are disjoint sets of tuples in
For example, one variant of the block nested loop join reads an entire page of
tuples into memory and loads them into a hash table.
, and probes the hash table to find
A more aggressive variant of this algorithm loads as many pages of
as can be fit in the available memory, loading all such tuples into a hash table, and then repeatedly scans
In fact, this algorithm is essentially a special-case of the classic hash join algorithm.
[citation needed] The block nested loop runs in
is the number of available pages of internal memory and
Note that block nested loop runs in
fits in the available internal memory.