Методы соединения таблиц

Методы реализации естественного соединения ⋈.

Три метода:

• вложенных циклов (NLJ - Nested Loop Join);
• сортировки слияния (SMJ - Sort Merge Join);
• хэшированных соединений (Hash Join).

 

Лекция №12 - Оценки (продолжение)

 

Оптимизация SQL-запросов

Физический план

Методы соединения таблиц

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

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

Зависит от:

• используемого дерева соединения (но мы в дальнейшем всегда будем использовать левосторонние);
• назначения буферов ввода/вывода.

Если на 3 операции блоков будет больше b, то лишние сохраняются на диск.

Формулы оценки стоимости соединения NLJ

CJOIN = CCPU + CI / O

CCPU = T (Q 1)⋅ T (Q 2)⋅ Ccomp

CI / O = CI / O (Q 2)⋅⌊ B (Q 1) b ⌋

здесь:

T (Q 1), T (Q 2) оценка числа записей в таблицах подзапросов Q 1 и Q 2;

B (Q 1) - число блоков ввода/вывода для получения таблицы Q 1;

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

b - число блоков в буферах 1 и 3 (из рисунка выше);

Ccomp - время сравнения двух кортежей из Q 1 и Q 2 в оперативной памяти;

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