ТОРА (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}$$. Перемножая их, получаем общее число операций.

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