Nested loop join

<h2 id="algorithm">Algorithm</h2>
Two relations 
 
 
 
 R
 
 
 {\displaystyle R}
 
 and 
 
 
 
 S
 
 
 {\displaystyle S}
 
 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 nr*bs+ br block transfers and nr+br seeks, where br and bs are number of blocks in relations R and S respectively, and nr is the number of tuples in relation R.
The algorithm runs in 
 
 
 
 O
 (
 
 |
 
 R
 
 |
 
 
 |
 
 S
 
 |
 
 )
 
 
 {\displaystyle O(|R||S|)}
 
 I/Os, where 
 
 
 
 
 |
 
 R
 
 |
 
 
 
 {\displaystyle |R|}
 
 and 
 
 
 
 
 |
 
 S
 
 |
 
 
 
 {\displaystyle |S|}
 
 is the number of tuples contained in 
 
 
 
 R
 
 
 {\displaystyle R}
 
 and 
 
 
 
 S
 
 
 {\displaystyle S}
 
 respectively and can easily be generalized to join any number of relations ...
The <a href="/facts/Block_nested_loop/74nCrNKl">block nested loop</a> join algorithm<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> is a generalization of the simple nested loops algorithm that takes advantage of additional <a href="/facts/Memory_(computing)/hQKVQ51J">memory</a> to reduce the number of times that the 
 
 
 
 S
 
 
 {\displaystyle S}
 
 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.

<h2 id="index-join-variation">Index join variation</h2>
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 
 
 
 
 O
 (
 
 |
 
 R
 
 |
 
 
 |
 
 S
 
 |
 
 )
 
  to 
 
 O
 (
 
 |
 
 R
 
 |
 
 log
 ⁡
 
 |
 
 S
 
 |
 
 )
 
 
 {\displaystyle O(|R||S|){\text{ to }}O(|R|\log |S|)}

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Hash_join/WryEJk9d">Hash join</a></li>
<li><a href="/facts/Sort-merge_join/S8NMJ6e7">Sort-merge join</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">"Understanding Nested Loops Joins". 4 October 2012. <a href="https://technet.microsoft.com/en-us/library/ms191318(v=sql.105).aspx" target="_blank">https://technet.microsoft.com/en-us/library/ms191318(v=sql.105).aspx</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">http://www.databaselecture.com/slides/9_Operator_Implementations.pdf [bare URL PDF] <a href="http://www.databaselecture.com/slides/9_Operator_Implementations.pdf" target="_blank">http://www.databaselecture.com/slides/9_Operator_Implementations.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
</ol>

Nested loop join open-in-new

Nested loop join