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

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

...начало

Оригинал всего раздела, посвящённого оптимизации SQL-запросов, от самого Григорьева можно загрузить здесь.

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

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

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

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

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

Расчёт числа формул: $$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. и так далее.