# Block nested loop

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Block_nested_loop
> Markdown URL: https://mediated.wiki/source/Block_nested_loop.md
> Source: https://en.wikipedia.org/wiki/Block_nested_loop
> Source revision: 1187531899
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{short description|Algorithm}}
A '''block-nested loop''' ('''BNL''') is an [algorithm](/source/algorithm) used to [join](/source/join_(SQL)) two relations in a [relational database](/source/relational_database).<ref name=mysql>{{cite web|title=8.2.1.14 Block Nested-Loop and Batched Key Access Joins|url=http://dev.mysql.com/doc/refman/5.6/en/bnl-bka-optimization.html|website=MySQL 5.6 Reference Manual|publisher=Oracle Corporation|accessdate=2 August 2015}}</ref>

This algorithm<ref name=MariaDB>{{cite web|title=Block Nested Loop Join|url=https://mariadb.com/kb/en/mariadb/block-based-join-algorithms/|website=MariaDB|publisher=MariaDB Corporation Ab|accessdate=2 August 2015}}</ref> is a variation of the simple [nested loop join](/source/nested_loop_join) and joins two [relations](/source/Relation_(database)) <math>R</math> and <math>S</math> (the "outer" and "inner" join operands, respectively). Suppose <math>|R| < |S|</math>. In a traditional nested loop join, <math>S</math> will be scanned once for every [tuple](/source/tuple) of <math>R</math>. If there are many qualifying <math>R</math> tuples, and particularly if there is no applicable [index](/source/Database_index) for the join key on <math>S</math>, this operation will be very expensive.

The block nested loop join algorithm improves on the simple nested loop join by only scanning <math>S</math> once for every ''group'' of <math>R</math> tuples. Here groups are [disjoint sets](/source/disjoint_sets) of tuples in <math>R</math> and the [union](/source/Union_(set_theory)) of all groups has the same tuples as <math>R</math>. For example, one variant of the block nested loop join reads an entire [page](/source/page_(computing)) of <math>R</math> tuples into [memory](/source/Computer_memory) and loads them into a [hash table](/source/hash_table). It then scans <math>S</math>, and probes the hash table to find <math>S</math> tuples that match any of the tuples in the current page of <math>R</math>. This reduces the number of scans of <math>S</math> that are necessary.

 '''algorithm''' block_nested_loop_join '''is'''
     '''for each''' page ''pr'' in ''R'' '''do'''
         '''for each''' page ''ps'' in ''S'' '''do'''
             '''for each''' tuple ''r'' in ''pr'' '''do'''
                 '''for each''' tuple ''s'' in ''ps'' '''do'''
                     '''if''' ''r'' and ''s'' satisfy the join condition '''then'''
                         '''yield''' tuple <''r'',''s''>

A more aggressive variant of this algorithm loads as many pages of <math>R</math> as can be fit in the available memory, loading all such tuples into a hash table, and then repeatedly scans <math>S</math>. This further reduces the number of scans of <math>S</math> that are necessary. In fact, this algorithm is essentially a special-case of the classic [hash join](/source/hash_join) algorithm.{{citation-needed|date=August 2015}}

The block nested loop runs in <math>O(P_r P_s/M)</math> I/Os where <math>M</math> is the number of available pages of internal memory and <math>P_r</math> and <math>P_s</math> is size of <math>R</math> and <math>S</math> respectively in pages. Note
that block nested loop runs in <math>O(P_r+P_s)</math> I/Os if <math>R</math> fits in the available internal memory.

==References==
{{Reflist}}

{{DEFAULTSORT:Block Nested Loop}}
Category:Join algorithms

---
Adapted from the Wikipedia article [Block nested loop](https://en.wikipedia.org/wiki/Block_nested_loop) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Block_nested_loop?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.