Алгоритм соединения вложенными циклами
Материал из Википедии — свободной энциклопедии
Алгоритм соединения вложенными циклами (Nested loops join) —- разновидность алгоритма соединения.
Содержание |
[править] Общее представление об алгоритме
В общем случае алгоритм получает на вход n таблиц и условия соединения. Результатом его работы является набор строк с результатами соединения.
Упрощая до двух таблиц, алгоритм можно описать следующим образом: для каждой строки одной из таблиц (ведущей) выполняется поиск в другой таблице (ведомой) строк соответствующих условию соединения.
В самом общем случае это постепенное построение декартова произведения исходных таблиц с анализом условия соединения для каждой из комбинаций строк. На псевдокоде это можно записать так:
Для каждой строки [r] ИЗ [Ведущая таблица]
Для каждой строки [s] из [Ведомая таблица]
Если УдовлетоворяетУсловию ([r],[s],[Условие соединения])
Вывести ([r],[s]);
Если для ведомой таблицы есть индекс применимый для выбранного условия соединения, то соединение можно осуществить значительно более эффективно. На псевдокоде это можно выразить так:
Для каждой строки [r] ИЗ [Ведущая таблица]
Вывести ([r], ИскатьПоИндексу ([Ведомая таблица], [r], [Условие соединения]));
[править] Подробное описание алгоритма
Алгоритм состоит из произвольного числа вложенных итераций поиска данных в каждой из соединяемых таблиц.
Внешним циклом выполняется поиск строк в ведущей таблице. Если часть или все ограничения для ведущей таблицы могут быть использованы для поиска по индексу, то на каждой итерации цикла в индексе ищутся расположения всех необходимых строк и выполняется прямой доступ к таблице. В противном случае таблица сканируется целиком. Оставшиеся ограничения используются для фильтрации выбранных строк. Для каждой оставшейся строки вызывается внутренний цикл.
Внутренний цикл по условиям соединения и данным внешнего цикла ищет строки в ведомой таблице. Если часть или все ограничения для ведомой таблицы вместе с ограничениями, полученными от внешнего цикла, могут быть использованы для поиска по индексу, то на каждой итерации цикла в индексе ищутся расположения всех необходимых строк и выполняется прямой доступ к ведомой таблице. В противном случае таблица сканируется целиком. Оставшиеся ограничения используются для фильтрации выбранных строк.
На каждой итерации самого глубокого цикла выбранные из таблиц строки конкатенируются, для получения одной строки итогового результата.
В общем случае циклы могут вкладываться произвольное число раз, в зависимости от числа таблиц, участвующих в соединении.
Если в некотором цикле выполняется поиск по индексу, и всех колонок в индексе достаточно для получения итогового результата, то прямой доступ к таблице в этом цикле не выполняется.
[править] Преимущества
- Самый общий и поэтому незаменимый алгоритм соединения. При помощи соединения вложенными циклами можно реализовать любое условие соединения. (Остальные алгоритмы имеют ограничения по реализуемым с их помощью условиям соединения. Например, когда условие выражается неравенством).
- Самый быстрый алгоритм, если необходимо получить только первую строку результата. (Например в SQL выражениях типа EXISTS).
- При использовании поиска по индексу алгоритм лучше всех масштабируется. То есть при увеличении объёма данных в соединяемых таблицах время выполнения запроса увеличивается практически линейно при тех же аппаратных ресурсах.
[править] Недостатки
- Самый медленный алгоритм. Все остальные алгоритмы имеют преимущество в скорости (но только в строго определённых обстоятельствах). Впрочем, некоторые авторы указывают, что проигрыш в скорости на реальных системах по сравнению с другими алгоритмами крайне несущественен.
