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

Материал из Википедии — свободной энциклопедии

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

Для каждой строки ведущей таблицы делается поиск в ведомой строк соответствующих условию соединения.

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

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

В более простых частных случаях вместо полного перебора ведомой таблицы используют некую операцию поиска по ведомой таблице, более эффективную чем перебор (обычно поиск по индексу)

На псевдокоде это можно выразить например так:

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

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

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

Недостатки:

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