Метод вложенных циклов (NLJ – Nested Loop Join)

При этом методе каждая запись первой таблицы сравнивается с каждой записью второй таблицы (рис. 1.13, сравнение выполняется по номеру счёта). В общем случае условие сравнения может быть произвольным.

Рис. 1.13. Метод соединения NLJ.

Формулы оценки стоимости соединения при использовании метода NLJ зависят от:

1) используемого дерева соединений; в дальнейшем будем полагать, что используются левосторонние деревья и применяются каналы,

2) назначения буферов ввода-вывода (рис. 1.14).

Рис. 1.14.Схема назначения буферов ввода-вывода.

В этом случае формулы для вычисления стоимости соединения NLJ следующий вид:

(5.8)

где

T(Q₁), T(Q₂) – число кортежей в таблицах подзапросов Q₁ и Q₂;

B(Q₁) – число блоков в таблице Q₁;

С_I/O(Q₂) – время ввода-вывода для получения таблицы Q₂;

b – число блоков в буфере для Q₁;

C_comp – время соединения (сравнения) двух кортежей из таблиц Q₁ и Q₂ в оперативной памяти (ОП);

- округление с недостатком.

Во второй формуле учитывается возможность многопроходного варианта соединения таблицы Q₂, если таблица Q₁ не умещается в "b" блоках буфера оперативной памяти. Округление берётся с недостатком, так как одно чтение таблиц с диска учитывается в стоимости выбора записей из исходных таблиц.