Nested loop join

{{Short description|Computing algorithm}} {{More citations needed|date=January 2021}} A '''nested loop join''' is a naive algorithm that joins two relations by using two nested loops.<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 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_r*b_s+ b_r block transfers and n_r+b_r seeks, where b_r and b_s are number of blocks in relations R and S respectively, and n_r 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 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 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 *Sort-merge join

==References== {{Reflist}}

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

{{compu-sci-stub}}