Алгоритм соединения вложенными циклами

Алгоритм соединения вложенными циклами (Nested loops join) — разновидность алгоритма соединения.

Общее представление об алгоритме

В общем случае алгоритм получает на вход n таблиц и условия соединения. Результатом его работы является набор строк с результатами соединения.

Упрощая до двух таблиц, алгоритм можно описать следующим образом: для каждой строки одной из таблиц (ведущей) выполняется поиск в другой таблице (ведомой) строк, соответствующих условию соединения.

В самом общем случае это постепенное построение декартова произведения исходных таблиц с анализом условия соединения для каждой из комбинаций строк. На псевдокоде это можно записать так:

 Для каждой строки [r] из [Ведущая таблица]
    Для каждой строки [s] из [Ведомая таблица]
       Если УдовлетворяетУсловию ([r],[s],[Условие соединения])
      	   Вывести ([r],[s]);		

Если для ведомой таблицы есть индекс, применимый для выбранного условия соединения, то соединение можно осуществить значительно более эффективно. На псевдокоде это можно выразить так:

Для каждой строки [r] из [Ведущая таблица]
    Вывести ([r], ИскатьПоИндексу ([Ведомая таблица], [r], [Условие соединения]));

Подробное описание алгоритма

Алгоритм состоит из произвольного числа вложенных итераций поиска данных в каждой из соединяемых таблиц.

Внешним циклом выполняется поиск строк в ведущей таблице. Если часть или все ограничения для ведущей таблицы могут быть использованы для поиска по индексу, то на каждой итерации цикла в индексе ищутся расположения всех необходимых строк и выполняется прямой доступ к таблице. В противном случае таблица сканируется целиком. Оставшиеся ограничения используются для фильтрации выбранных строк. Для каждой оставшейся строки вызывается внутренний цикл.

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

На каждой итерации самого глубокого цикла выбранные из таблиц строки конкатенируются, для получения строк итогового результата.

В общем случае циклы могут вкладываться произвольное число раз, в зависимости от числа таблиц, участвующих в соединении.

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

Преимущества

• Самый общий и поэтому незаменимый алгоритм соединения. При помощи соединения вложенными циклами можно реализовать любое условие соединения. (Остальные алгоритмы имеют ограничения по реализуемым с их помощью условиям соединения. Например, когда условие выражается неравенством).
• Самый быстрый алгоритм, если необходимо получить только первую строку результата. (Например в SQL выражениях типа EXISTS).
• При использовании поиска по индексу алгоритм лучше всех масштабируется. То есть при увеличении объёма данных в соединяемых таблицах время выполнения запроса увеличивается практически линейно при тех же аппаратных ресурсах.

Недостатки

• Самый медленный алгоритм. Все остальные алгоритмы имеют преимущество в скорости (но только в строго определённых обстоятельствах). Впрочем, некоторые авторы указывают, что проигрыш в скорости на реальных системах по сравнению с другими алгоритмами крайне несущественен.

См. также

• Оптимизация запросов
• План выполнения запроса

Ссылки

• Craig Freedman:Материалы статьи Nested Loops Join