# Nested loop join

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

{{Short description|Computing algorithm}}
{{More citations needed|date=January 2021}}
A '''nested loop join''' is a naive [algorithm](/source/algorithm) that joins two relations by using two nested [loop](/source/loop_(computing))s.<ref>{{cite web | url=https://technet.microsoft.com/en-us/library/ms191318(v=sql.105).aspx | title=Understanding Nested Loops Joins | date=4 October 2012 }}</ref> Join operations are important for [database](/source/database) management.

==Algorithm==
Two relations <math>R</math> and <math>S</math> are joined as follows:

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

This algorithm will involve  n<sub>r</sub>*b<sub>s</sub>+ b<sub>r</sub> block transfers and n<sub>r</sub>+b<sub>r</sub> seeks, where b<sub>r</sub> and b<sub>s</sub> are number of blocks in relations R and S respectively, and n<sub>r</sub> is the number of tuples in relation R.

The algorithm runs in <math>O(|R||S|)</math> I/Os, where <math>|R|</math> and <math>|S|</math> is the number of tuples contained in <math>R</math> and <math>S</math> respectively and can easily be generalized to join any number of relations ...

The [block nested loop](/source/block_nested_loop) join algorithm<ref>{{Cite web| title=Query Processing Overview | url=http://www.databaselecture.com/slides/9_Operator_Implementations.pdf | archive-url=https://web.archive.org/web/20210730081820/http://databaselecture.com/slides/9_Operator_Implementations.pdf | archive-date=2021-07-30}}</ref> is a generalization of the simple nested loops algorithm that takes advantage of additional [memory](/source/memory_(computing)) to reduce the number of times that the <math>S</math> relation is scanned. It loads large chunks of relation R into main memory. For each chunk, it scans S and evaluates the join condition on all tuple pairs, currently in memory. This reduces the number of times S is scanned to once per chunk.

==Index join variation==
If the inner relation has an index on the attributes used in the join, then the naive nest loop join can be replaced with an index join.

 '''algorithm''' index_join '''is'''
     '''for each''' tuple ''r'' in ''R'' '''do'''
         '''for each''' tuple ''s'' in ''S'' in the index lookup '''do'''
             '''yield''' tuple <''r'',''s''>

The time complexity for this variation improves from <math> O(|R||S|) \text{ to } O(|R|\log|S|) </math>

==See also==
*[Hash join](/source/Hash_join)
*[Sort-merge join](/source/Sort-merge_join)

==References==
{{Reflist}}

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

{{compu-sci-stub}}

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