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

Материал из Кафедра ИУ5 МГТУ им. Н.Э.Баумана, студенческое сообщество
Перейти к навигации Перейти к поиску
Этот конспект ещё не дописан.
Здесь не хватает:
   - схемы образования файлов со второго уровня и до последнего.
А также не все формулы из раздела оценки 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}$$. Перемножая их, получаем общее число операций.

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

Источник — https://iu5bmstu.ru/index.php?title=ТОРА_(9)_-_Лекция_№12_-_Оценки_(продолжение)&oldid=5728