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

Расчёт числа формул: l = B (R) bl =1,

отсюда l =log bB (R)

T (R)=log bB (R)−1

Для каждой записи нужно выполнить b ⋅ CCOMP + Cmove - это объясняет второе слагаемое.

Число уровней: log Bb (R)

Число блоков: B (R). Так как пишем и читаем, то B (R)×2

Теперь разбираемся со следующей формулой:

I (Q 1, a)> I (Q 2, a) - мощность у первого больше.

Смотрим первое слагаемое: (T (Q 1) I (Q 2, a)+2)⋅ T (Q 2) - происходит соединение каждой записи из Q 2 с каждой из Q 1

Смотрим второе слагаемое: T (Q 1) I (Q 2, ar)⋅(I (Q 1, a)− I (Q 2, a))

Следующая формула:

[ B (Q 1)]... T (Q 1) I (Q 1, a)⋅⌊ B (Q 1) I (Q 2, a)⋅ b ⌋⋅ b ⋅ min (I (Q 1, a), I (Q 2, a))

На каждую запись нужно выполнить такое число операций чтения и записи в буфер.

Метод хешированных соединений (Hash Join)

Осуществляется по следующим шагам:

1. Выполняется хеш-функция, где a - атрибут соединяемых таблиц;
2. Записи соединяемых таблицы хешируются, то есть создаются разделы (Ri и Si);
3. Выполняется соединение соответствующих разделов (Ri ⋈ Si) по алгоритму NLJ или SMJ.

Пример хешированного соединения

Предположим, заданы две таблицы (после выполнения подзапросов).

По шагам:

1)

в качестве хеш-функции выберем остаток от деления на 10: h (a)= a mod 10

2)

Ri - подмножество номеров счетов из таблицы R, у которых значение хэш-функции равно i =0..9

Si - подмножество номеров счетов из таблицы S, у которых значение хэш-функции равно i =0..9

представим эти разделы в виде таблицы. Будет 9 разделов.

 

Разделы соединяются по диагонали. Потому что если остатки от деления разные, то и номера счетов разные. Остальные смотреть не смысла, потому что разные остатки.

При значительных объёмах таблиц выигрыш от использования соединения методом хэширования может быть очень значительным, так как соединяемые разделы имеют намного меньшую размерность, чем сами таблицы.

Реализация метода может быть различной.

Однопроходной вариант реализации

Разделы опорной таблицы R хранятся в оперативной памяти.

Алгоритм:

1. читаются блоки таблицы S из внешней записи;
2. для каждой записи из S выполняется хеширование атрибута соединения (i);
3. значение атрибута a сравниваются со значениями атрибута соединения в разделе Ri.