imported>Avocado: Adding short description: "Computing algorithm"

2025-05-18T20:42:11Z

Adding short description: "Computing algorithm"

New page

{{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 [[loop (computing)|loop]]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]] 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 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 <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 (computing)|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}}

Nested loop join - Revision history

imported>Avocado: Adding short description: "Computing algorithm"