ТОРА (9) - Лекция №13 - Оценки (продолжение)

Этот конспект ещё не дописан. Здесь не хватает:    - объяснения всех формул оценки стоимости соединений (сейчас пояснения приведены не ко всем);    - схемы чтения/записи при формировании уровней.

...начало

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

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

Метод сортировки слияния (SMJ)

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

Расчёт числа формул: $$l = \frac{B(R)}{b^l} = 1$$,

отсюда $$l = \log_bB(R)$$

$$T(R) = \log_bB(R) - 1$$

Для каждой записи нужно выполнить $$b\cdot C_{COMP} + C_{move}$$ - это объясняет второе слагаемое.

Число уровней: $$\log_Bb(R)$$

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

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

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

Смотрим первое слагаемое: $$\Bigl(\frac{T(Q_1)}{I(Q_2, a)} + 2\Bigr)\cdot T(Q_2)$$ - происходит соединение каждой записи из $$Q_2$$ с каждой из $$Q_1$$

Смотрим второе слагаемое: $$\frac{T(Q_1)}{I(Q_2, ar)\cdot (I(Q_1, a) - I(Q_2, a))}$$

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

$$[B(Q_1)]$$ ... $$\frac{T(Q_1)}{I(Q_1, a)}\cdot\Bigl\lfloor \frac{B(Q_1)}{I(Q_2, a)\cdot b}\Bigr\rfloor\cdot b\cdot min(I(Q_1, a), I(Q_2, a)\Bigr)$$

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

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

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

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

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

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

По шагам:

1)

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

2)

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

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

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

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

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

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

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

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

Алгоритм:

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

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

Оперативной памяти может не хватать. Число размеров (точнее, хэш-функция) подбирается так, чтобы максимальный раздел таблицы $$R$$ помещался в оперативной памяти.

При таком подходе после хэширования таблиц $$R$$ и $$S$$ все разделы сохраняются на диске.

Алгоритм:

1. подбирается хэш-функция;
2. хэширование таблицы;
3. раздел $$R_0$$ целиком читается в оперативную память;
4. в оперативную память поблочно читается раздел $$S_0$$;
5. для каждой записи раздела $$S_0$$ значение атрибута $$a$$ сравнивается со значением атрибута соединения в разделе $$R_0$$;
6. считываются следующие разделы ($$R_1$$, $$R_2$$ и так далее).

Отличие от методов NLJ и SMJ

Метод хэшированного соединения имеет важную особенность. В методах NLJ или SMJ соединяемые таблицы должны уже храниться на сервере перед выполнением соединения. А в этом методе соединение таблиц может выполняться асинхронно, по мере поступления записей с других серверов.

На серверах 1 и 2 выполняются подзапросы, а на сервере 0 выполняется соединение.

Предположим, с сервера 2 на сервер 0 поступила очередная запись из таблицы $$S$$. При этом СУБД на сервере 0 выполняет следующие действия:

1. вычисляется хэш-функция для атрибута соединения;
2. значение атрибута соединения сравнивается со значениями атрибутов соединения из раздела $$R_1$$. Если есть совпадения, то выводятся результаты соединения;
3. запись сохраняется в разделе $$S_i$$.
4. и так далее.