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

Этот конспект ещё не дописан. Здесь не хватает:    - схемы образования файлов со второго уровня и до последнего. А также не все формулы из раздела оценки SMJ верные.

...начало

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

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

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

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

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

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

Зависит от:

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

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

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

$C^{JOIN} = C_{CPU} + C_{I/O}$

$C_{CPU}=T (Q_1)\cdot T(Q_2)\cdot C_{comp}$

$C_{I/O} = C_{I/O}(Q_2)\cdot\Bigl\lfloor\frac{B(Q_1)}{b}\Bigr\rfloor$

здесь:

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

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

$C_{I/O}(Q_2)$ - время ввода/вывода для получения таблицы $Q_2$;

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

$C_{comp}$ - время сравнения двух кортежей из $Q_1$ и $Q_2$ в оперативной памяти;

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

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

Соединение двух таблиц этим методом выполняется по следующим шагам:

1. соединяемые таблицы сортируются по атрибуту соединения, будем обозначать его через $a$;
2. организуется вложенный цикл, где выполняется сравнение значения атрибута соединения в записях таблиц $Q_1$ и $Q_2$. Условием соединения может быть только равенство атрибутов соединения.

Рассмотрим пример реализации второго шага.

Выполняется сравнение записей в таблицах $Q_1$ и $Q_2$, на которые указывают указатели. Перемещение указателей выполняется следующим образом:

• если выполняется условие $<$, то указатель перемещается в таблицу $Q_1$;
• если выполняется условие $>$, то указатель перемещается в таблицу $Q_2$;
• если выполняется условие $=$, то результат соединения перемещается в выходной буфер, указатели не перемещаются и выполняется сравнение со следующей записью из таблицы $Q_2$.

Результат соединения $Q_1$ и $Q_2$ получается уже отсортированным.

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

$C_{CPU} = [C^{SORT}_{CPU}(Q_1)] + [C^{SORT}_{CPU}(Q_2)] + C^{JOIN}_{CPU}(Q_1, Q_2)$

$C_{I/O} = [C^{SORT}_{I/O}(Q_1)] + [C^{SORT}_{I/O}(Q_2)] + C^{JOIN}_{I/O}(Q_1, Q_2)$

$C^{SORT}_{CPU}(R) = T(R)\cdot\log_2\Bigl(\frac{T(R)}{\lceil B(R)/b\rceil}\Bigr)\cdot (C_{comp} + C_{move}) + \Bigl(\log_b B(R) - 1\Bigr)\cdot T(R)\cdot (b\cdot C_{comp} + C_{move})$

$C^{SORT}_{I/O}(R) = 2\cdot B(R) \cdot \log_b B(R) \cdot C_B$

Далее возможны варианты:

• $C^{JOIN}_{CPU}(Q_1, Q_2) = \Bigl(\Bigl(\frac{T(Q_1)}{I(Q_1, a)} + 2\Bigr)\cdot T(Q_2) + T(Q_1)\cdot \Bigl(1 - \frac{I(Q_2, a)}{I(Q_1, a)}\Bigr)\Bigr)\cdot C_{comp}$, если $I(Q_1, a) > I(Q_2, a)$;

• $C^{JOIN}_{CPU}(Q_1, Q_2) = \Bigl(\Bigl(\frac{T(Q_2)}{I(Q_2, a)} + 2\Bigr)\cdot T(Q_1) + T(Q_2)\cdot \Bigl(1 - \frac{I(Q_1, a)}{I(Q_2, a)}\Bigr)\Bigr)\cdot C_{comp}$, если $I(Q_2, a) > I(Q_1, a)$.

$C^{JOIN}_{I/O} = [B(Q_1)] + [B(Q_2)] + \Bigl(\frac{T(Q_1)}{I(Q_1, a)}\cdot \Bigl\lfloor \frac{B(Q_2)}{I(Q_2, a)\cdot b}\Bigr\rfloor\cdot b\cdot min(I(Q_1, a), I(Q_2, a)\Bigr)\cdot C_B$

здесь:

$T(Q_1)$, $T(Q_2)$ - оценка числа записей в таблицах $Q_1$ и $Q_2$;

$B(Q_1)$, $B(Q_2)$ - оценка числа блоков в этих же таблицах;

$I(Q_1, a)$, $I(Q_2, a)$ - мощности атрибутов в соединении $a$ тех же таблиц;

$b$ - число блоков в оперативной памяти, отводимое под сортировку этих таблиц, а также для выполнения соединения;

$C_{comp}$ - среднее время соединения двух кортежей из записей этих таблиц в оперативной памяти;

$C_{move}$ - время перемещения одной записи в оперативной памяти при сортировке;

$C_B$ - время чтения/записи одного блока на диск;

верхние неполные квадратные скобки - округление с избытком;

нижние неполные квадратные скобки - округление с недостатком;

обычные квадратные скобки - необязательность, значит уже отсортировано.

Механизм сортировки таблиц

Механизм сортировки таблиц $Q_1$ и $Q_2$:

1. блоки таблицы $R$ читаются в буфер и там сортируются. Получается файл, который сохраняется на диск;
2. в буфер читаются ещё блоки.

Таким образом, на диске будет сохранено несколько файлов, и в каждом записи будут отсортированы. Эти файлы образуют первый уровень. Каждый файл можно рассматривать как стек записей.

В буфере из $b$ блоков сравниваются первые записи сохранённых на предыдущем этапе файлов (то есть, $b$ файлов, если все сразу сравнивать не можем, потому что их сильно много). Минимальное среди сравниваемых записей значение пишется в файл следующего уровня, а стек, из которого это значение взяли, поднимается.

На следующем уровне история повторяется, и так до тех пор, пока не получится один итоговый файл. Записи в нём будут идеально отсортированы.

$\frac{T(R)}{\lceil B(R) / b\rceil}$ - оценка числа записей в одном файле первого уровня.

$\frac{T(R)}{\lceil B(R) / b\rceil}\cdot log_2\frac{T(R)}{\lceil B(R) / b\rceil}$ - число операций сравнений и перемещений записей при сортировке одного файла первого уровня. Но таких файлов $\frac{B(R)}{b}$. Перемножая их, получаем общее число операций.

продолжение...