Присоединение к вложенному циклу - Nested loop join

А соединение вложенного цикла наивный алгоритм который объединяет два набора с помощью двух вложенных петли.^[1] Операции соединения важны для база данных управление.

Алгоритм

Два отношения ${\displaystyle R}$ и ${\displaystyle S}$ соединяются следующим образом:

алгоритм nested_loop_join является    для каждого кортеж р в р делать        для каждого кортеж s в S делать            если р и s удовлетворять условию соединения тогда                урожай кортеж <р,s>

Этот алгоритм будет включать n_р* б_s+ b_р блочные переводы и n_р+ b_р ищет, где b_р и б_s - количество блоков в отношениях R и S соответственно, а n_р - количество кортежей в отношении R.

Алгоритм работает в ${\displaystyle O(|R||S|)}$ Ввод / вывод, где ${\displaystyle |R|}$ и ${\displaystyle |S|}$ это количество кортежей, содержащихся в ${\displaystyle R}$ и ${\displaystyle S}$ соответственно и могут быть легко обобщены для соединения любого количества отношений ...

В блокировать вложенный цикл алгоритм присоединения^[2] является обобщением алгоритма простых вложенных циклов, в котором используются дополнительные объем памяти чтобы уменьшить количество раз, когда ${\displaystyle S}$ отношение сканируется. Он загружает большие фрагменты отношения R в основную память. Для каждого фрагмента он сканирует S и оценивает условие соединения для всех пар кортежей, находящихся в настоящее время в памяти. Это сокращает количество сканирований S до одного для каждого фрагмента.

Вариант соединения индекса

Если внутреннее отношение имеет индекс для атрибутов, используемых в соединении, тогда наивное гнездовое соединение цикла может быть заменено индексным соединением.

алгоритм index_join является    для каждого кортеж р в р делать        для каждого кортеж s в S в поиске по индексу делать            урожай кортеж <р,s>

Временная сложность этого варианта улучшается с O (M * N) тоже(M * бревно N).

Смотрите также

• Хеш-соединение
• Сортировка-слияние

Рекомендации

1. https://technet.microsoft.com/en-us/library/ms191318(v=sql.105).aspx
2. http://www.databaselecture.com/slides/9_Operator_Implementations.pdf