Nested Loop Join¶

Nested Loop Join (соединение вложенными циклами) — это один из базовых алгоритмов соединения (join) двух наборов данных в системах управления базами данных (СУБД), реляционных и нереляционных. Он основан на последовательном переборе всех строк одного набора (внешнего) и для каждой из них — поиске соответствующих строк во втором наборе (внутреннем). Алгоритм является универсальным, но его эффективность сильно зависит от размера данных и наличия индексов.

¶Принцип работы

Алгоритм Nested Loop Join работает по следующей схеме:

1. Выбирается внешний набор (обычно меньший по размеру или не имеющий индекса). Для каждой строки этого набора выполняется итерация.
2. Для каждой строки внешнего набора выполняется полный или частичный обход внутреннего набора.
3. Для каждой пары строк проверяется условие соединения (например, a.id = b.id). Если условие выполняется, строка добавляется в результирующий набор.

В классическом варианте (без индексов) алгоритм выполняет полный перебор внутреннего набора для каждой строки внешнего. Временная сложность такого алгоритма — O(N × M), где N — количество строк во внешнем наборе, M — количество строк во внутреннем. Это делает его неэффективным для больших неиндексированных таблиц.

¶Разновидности

¶1. Простой Nested Loop Join (без индекса)

Используется, когда оба набора данных не имеют индексов по условию соединения. Для каждой строки внешнего набора выполняется полное сканирование внутреннего. Применяется редко, только для очень маленьких таблиц (обычно до 10–100 строк).

¶2. Indexed Nested Loop Join

Наиболее распространённая и эффективная разновидность. Внутренний набор имеет индекс (например, B-дерево или хеш-индекс) по столбцу, участвующему в условии соединения. Вместо полного сканирования внутреннего набора для каждой строки внешнего выполняется быстрый поиск по индексу. Временная сложность снижается до O(N × log M) (для B-дерева) или O(N) (для хеш-индекса). Этот вариант является основным для соединений, где внутренний набор велик, но хорошо проиндексирован.

¶3. Block Nested Loop Join

Модификация, предназначенная для уменьшения количества операций ввода-вывода. Внешний набор считывается не по одной строке, а блоками (страницами). Для каждого блока выполняется полное сканирование внутреннего набора. Это позволяет эффективнее использовать кэш и уменьшить число обращений к диску, особенно при работе с большими таблицами.

¶Применение

Nested Loop Join применяется в следующих сценариях:

• Соединение малых таблиц — когда обе таблицы содержат небольшое количество строк (например, справочники, конфигурации).
• Соединение с индексом — когда внутренняя таблица имеет индекс по условию соединения, а внешняя — мала. Это типичный случай для запросов, где одна таблица — это несколько записей, а другая — миллионы строк с индексом.
• Неравные соединения — условия, отличные от равенства (например, a.date > b.date или a.value BETWEEN b.min AND b.max). Для таких условий другие алгоритмы (Hash Join, Merge Join) часто неприменимы или неэффективны.
• Соединения с ограничением по количеству строк — если ожидается, что внешний набор вернёт всего несколько строк (например, после фильтрации WHERE), Nested Loop Join может быть быстрее, чем полное сканирование, необходимое для Hash Join.

¶Сравнение с другими алгоритмами

¶Оптимизация

Оптимизаторы запросов в современных СУБД (например, PostgreSQL, MySQL, Oracle, Microsoft SQL Server) автоматически выбирают Nested Loop Join, когда он оценивается как наиболее дешёвый. Для повышения производительности разработчики могут:

• Создавать индексы по столбцам, участвующим в условии соединения, особенно на внутренней таблице.
• Уменьшать размер внешнего набора с помощью фильтров WHERE или подзапросов.
• Использовать подсказки (hints) — в некоторых СУБД можно принудительно указать алгоритм соединения (например, /+ USE_NL(a b) / в Oracle).
• Анализировать статистику — актуальная статистика по таблицам помогает оптимизатору точнее оценить стоимость.

¶Пример (SQL)

Рассмотрим запрос:

``sql SELECT * FROM orders o JOIN customers c ON o.customer_id = c.id WHERE c.country = 'Russia'; ``

Если таблица customers мала (например, 1000 строк) и имеет индекс по id, а таблица orders велика (1 млн строк), оптимизатор может выбрать:

• Внешний набор: customers (после фильтрации по стране остаётся, например, 50 строк).
• Внутренний набор: orders с индексом по customer_id.
• Для каждой из 50 строк клиентов выполняется быстрый поиск по индексу в orders, что даёт примерно 50 × log(1 млн) операций.

Если бы использовался Hash Join, пришлось бы строить хеш-таблицу по всем 1 млн строк orders, что потребовало бы больше памяти и времени.

¶Недостатки

• Высокая стоимость при отсутствии индекса — полный перебор внутреннего набора для каждой строки внешнего приводит к квадратичной сложности.
• Чувствительность к размеру внешнего набора — если внешний набор велик (например, 100 000 строк), даже с индексом на внутреннем наборе количество операций может быть значительным.
• Неэффективность для больших неиндексированных таблиц — в таких случаях Hash Join или Merge Join обычно предпочтительнее.

¶Источники

• Гарсиа-Молина, Г., Ульман, Дж., Уидом, Дж. «Системы баз данных. Полный курс» (Database Systems: The Complete Book), 2008.
• Ramakrishnan, R., Gehrke, J. «Database Management Systems», 3rd edition, 2003.
• Документация PostgreSQL: «Chapter 11. Indexes» и «Chapter 14. Performance Tips».
• Документация MySQL: «Optimizing Queries with EXPLAIN».
• Документация Oracle Database: «Optimizer Join Methods».