ТОРА (9) - Лекция №12 - Оценки (продолжение): различия между версиями
ILobster (обсуждение | вклад) мНет описания правки |
|||
(не показано 19 промежуточных версий 6 участников) | |||
Строка 1: | Строка 1: | ||
{{Tabli4ka warning undone summary|text= - схемы [[#Механизм сортировки таблиц | образования файлов со второго уровня и до последнего]].<br>А также не все [[#Формулы оценки стоимости соединения SMJ | формулы из раздела оценки SMJ]] верные.}} | |||
{{Backward|l=ТОРА (9) - Лекция №11 - Оценки}} | {{Backward|l=ТОРА (9) - Лекция №11 - Оценки}} | ||
Оригинал всего раздела, посвящённого оптимизации SQL-запросов, от самого [[Григорьев Ю.А. | Григорьева]] можно загрузить [http://yadi.sk/d/VjjMs6ww1HH2D здесь]. | |||
__TOC__ | |||
== Оптимизация SQL-запросов == | == Оптимизация SQL-запросов == | ||
=== | === Физический план === | ||
==== Метод | ==== Методы соединения таблиц ==== | ||
===== Метод вложенных циклов (NLJ, Nested Loop Join) ===== | |||
Каждая запись первой соединяемой таблицы сравнивается с каждой записью второй соединяемой таблицы. В общем случае, условие сравнения может быть произвольным. | Каждая запись первой соединяемой таблицы сравнивается с каждой записью второй соединяемой таблицы. В общем случае, условие сравнения может быть произвольным. | ||
Строка 15: | Строка 20: | ||
* назначения буферов ввода/вывода. | * назначения буферов ввода/вывода. | ||
[[Файл:9sTORAl12pic1.png| | [[Файл:9sTORAl12pic1.png|600px|center]] | ||
Если на 3 операции блоков будет больше {{Формула|f=b}}, то лишние сохраняются на диск. | Если на 3 операции блоков будет больше {{Формула|f=b}}, то лишние сохраняются на диск. | ||
===== Формулы оценки стоимости соединения ===== | ====== Формулы оценки стоимости соединения NLJ ====== | ||
{{Формула|f=C^{JOIN} = C_{CPU} + C_{I/O} }} | {{Формула|f=C^{JOIN} = C_{CPU} + C_{I/O} }} | ||
{{Формула|f=C_{CPU}\cdot T(Q_2)\cdot C_{comp} }} | {{Формула|f=C_{CPU}=T (Q_1)\cdot T(Q_2)\cdot C_{comp} }} | ||
{{Формула|f=C_{I/O} = C_{I/O}(Q_2)\cdot\Bigl\lfloor\frac{B(Q_1)}{b}\Bigr\rfloor}} | {{Формула|f=C_{I/O} = C_{I/O}(Q_2)\cdot\Bigl\lfloor\frac{B(Q_1)}{b}\Bigr\rfloor}} | ||
Строка 37: | Строка 42: | ||
:неполные квадратные скобки означают округление с недостатком, так как одно чтение с диска учитывается в стоимости выбора записей из исходных таблиц. | :неполные квадратные скобки означают округление с недостатком, так как одно чтение с диска учитывается в стоимости выбора записей из исходных таблиц. | ||
==== Метод сортировки слияния (SMJ) ==== | ===== Метод сортировки слияния (SMJ, Sort Merge Join) ===== | ||
Соединение двух таблиц этим методом выполняется по следующим шагам: | Соединение двух таблиц этим методом выполняется по следующим шагам: | ||
Строка 56: | Строка 61: | ||
Результат соединения {{Формула|f=Q_1}} и {{Формула|f=Q_2}} получается уже отсортированным. | Результат соединения {{Формула|f=Q_1}} и {{Формула|f=Q_2}} получается уже отсортированным. | ||
===== Формулы оценки стоимости соединения ===== | ====== Формулы оценки стоимости соединения SMJ ====== | ||
{{Формула|f=C_{CPU} = [C^{SORT}_{CPU}(Q_1)] + [C^{SORT}_{CPU}(Q_2)] + C^{JOIN}_{CPU}(Q_1, Q_2)}} | {{Формула|f=C_{CPU} = [C^{SORT}_{CPU}(Q_1)] + [C^{SORT}_{CPU}(Q_2)] + C^{JOIN}_{CPU}(Q_1, Q_2)}} | ||
Строка 62: | Строка 67: | ||
{{Формула|f=C_{I/O} = [C^{SORT}_{I/O}(Q_1)] + [C^{SORT}_{I/O}(Q_2)] + C^{JOIN}_{I/O}(Q_1, Q_2)}} | {{Формула|f=C_{I/O} = [C^{SORT}_{I/O}(Q_1)] + [C^{SORT}_{I/O}(Q_2)] + C^{JOIN}_{I/O}(Q_1, Q_2)}} | ||
{{Формула|f=C^{SORT}_{CPU}(R) = T(R)\cdot\ | {{Формула|f=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}) }} | ||
{{Формула|f=C^{SORT}_{I/O}(R) = 2\cdot B(R)\cdot C_B}} | {{Формула|f=C^{SORT}_{I/O}(R) = 2\cdot B(R) \cdot \log_b B(R) \cdot C_B}} | ||
Далее возможны варианты: | Далее возможны варианты: | ||
* {{Формула|f=C^{JOIN}_{CPU}(Q_1, Q_2) = \Bigl(\Bigl(\frac{T( | * {{Формула|f=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} }}, если {{Формула|f=I(Q_1, a) > I(Q_2, a)}}; | ||
* {{Формула|f=C^{JOIN}_{CPU}(Q_1, Q_2) = \Bigl(\Bigl(\frac{T( | * {{Формула|f=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} }}, если {{Формула|f=I(Q_2, a) > I(Q_1, a)}}. | ||
{{Формула|f=C^{JOIN}_{I/O} = [B(Q_1)] + [B(Q_2)] + \Bigl(\frac{T(Q_1)}{ | {{Формула|f=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}} | ||
здесь: | здесь: | ||
Строка 83: | Строка 88: | ||
:{{Формула|f=C_{move} }} - время перемещения одной записи в оперативной памяти при сортировке; | :{{Формула|f=C_{move} }} - время перемещения одной записи в оперативной памяти при сортировке; | ||
:{{Формула|f=C_B}} - время чтения/записи одного блока на диск; | :{{Формула|f=C_B}} - время чтения/записи одного блока на диск; | ||
:верхние неполные квадратные скобки - округление с | :верхние неполные квадратные скобки - округление с избытком; | ||
:нижние неполные квадратные скобки - округление с недостатком; | :нижние неполные квадратные скобки - округление с недостатком; | ||
:обычные квадратные скобки - необязательность, значит уже отсортировано. | :обычные квадратные скобки - необязательность, значит уже отсортировано. | ||
===== Механизм сортировки таблиц ===== | ====== Механизм сортировки таблиц ====== | ||
Механизм сортировки таблиц {{Формула|f=Q_1}} и {{Формула|f=Q_2}}: | Механизм сортировки таблиц {{Формула|f=Q_1}} и {{Формула|f=Q_2}}: | ||
Строка 93: | Строка 98: | ||
# в буфер читаются ещё блоки. | # в буфер читаются ещё блоки. | ||
Таким образом, на диске будет сохранено несколько файлов, и в каждом записи будут отсортированы. Эти файлы образуют первый уровень. | Таким образом, на диске будет сохранено несколько файлов, и в каждом записи будут отсортированы. Эти файлы образуют первый уровень. Каждый файл можно рассматривать как ''стек'' записей. | ||
В буфере из {{Формула|f=b}} блоков сравниваются первые записи сохранённых на предыдущем этапе файлов (то есть, {{Формула|f=b}} файлов, если все сразу сравнивать не можем, потому что их сильно много). Минимальное среди сравниваемых записей значение пишется в файл следующего уровня, а стек, из которого это значение взяли, поднимается. | |||
На следующем уровне история повторяется, и так до тех пор, пока не получится один итоговый файл. Записи в нём будут идеально отсортированы. | |||
{{Формула|f=\frac{T(R)}{\lceil B(R) / b\rceil} }} - оценка числа записей в одном файле первого уровня. | {{Формула|f=\frac{T(R)}{\lceil B(R) / b\rceil} }} - оценка числа записей в одном файле первого уровня. | ||
Строка 99: | Строка 108: | ||
{{Формула|f=\frac{T(R)}{\lceil B(R) / b\rceil}\cdot log_2\frac{T(R)}{\lceil B(R) / b\rceil} }} - число операций сравнений и перемещений записей при сортировке одного файла первого уровня. Но таких файлов {{Формула|f=\frac{B(R)}{b} }}. Перемножая их, получаем общее число операций. | {{Формула|f=\frac{T(R)}{\lceil B(R) / b\rceil}\cdot log_2\frac{T(R)}{\lceil B(R) / b\rceil} }} - число операций сравнений и перемещений записей при сортировке одного файла первого уровня. Но таких файлов {{Формула|f=\frac{B(R)}{b} }}. Перемножая их, получаем общее число операций. | ||
{{Forward|l=ТОРА (9) - Лекция №13 - Оценки (продолжение)}} | |||
[[Категория:Теоретические основы реляционной алгебры (9 семестр)]] | [[Категория:Теоретические основы реляционной алгебры (9 семестр)]] | ||
[[Категория:Конспекты лекций и семинаров]] | [[Категория:Конспекты лекций и семинаров]] |
Текущая версия от 02:43, 5 февраля 2018
Этот конспект ещё не дописан. Здесь не хватает: - схемы образования файлов со второго уровня и до последнего. А также не все формулы из раздела оценки 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)
Соединение двух таблиц этим методом выполняется по следующим шагам:
- соединяемые таблицы сортируются по атрибуту соединения, будем обозначать его через $$a$$;
- организуется вложенный цикл, где выполняется сравнение значения атрибута соединения в записях таблиц $$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$$:
- блоки таблицы $$R$$ читаются в буфер и там сортируются. Получается файл, который сохраняется на диск;
- в буфер читаются ещё блоки.
Таким образом, на диске будет сохранено несколько файлов, и в каждом записи будут отсортированы. Эти файлы образуют первый уровень. Каждый файл можно рассматривать как стек записей.
В буфере из $$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}$$. Перемножая их, получаем общее число операций.
продолжение...