Кафедра ИУ5 МГТУ им. Н.Э.Баумана, студенческое сообщество - Вклад [ru]

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

2013-01-11T10:51:12Z

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

{{Tabli4ka warning undone summary|text=   - схемы [[#Механизм сортировки таблиц | образования файлов со второго уровня и до последнего]].<br>А также не все [[#Формулы оценки стоимости соединения SMJ | формулы из раздела оценки SMJ]] верные.}}
{{Backward|l=ТОРА (9) - Лекция №11 - Оценки}}
Оригинал всего раздела, посвящённого оптимизации SQL-запросов, от самого [[Григорьев Ю.А. | Григорьева]] можно загрузить [http://yadi.sk/d/VjjMs6ww1HH2D здесь].
__TOC__
== Оптимизация SQL-запросов ==

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

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

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

[[Файл:9sTORAl11pic4.png|500px|center]]

Зависит от:

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

[[Файл:9sTORAl12pic1.png|600px|center]]

Если на 3 операции блоков будет больше {{Формула|f=b}}, то лишние сохраняются на диск.

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

{{Формула|f=C^{JOIN} = C_{CPU} + C_{I/O} }}

{{Формула|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=T(Q_1)}}, {{Формула|f=T(Q_2)}} оценка числа записей в таблицах подзапросов {{Формула|f=Q_1}} и {{Формула|f=Q_2}};
:{{Формула|f=B(Q_1)}} - число блоков ввода/вывода для получения таблицы {{Формула|f=Q_1}};
:{{Формула|f=C_{I/O}(Q_2)}} - время ввода/вывода для получения таблицы {{Формула|f=Q_2}};
:{{Формула|f=b}} - число блоков в буферах 1 и 3 (''из рисунка выше'');
:{{Формула|f=C_{comp} }} - время сравнения двух кортежей из {{Формула|f=Q_1}} и {{Формула|f=Q_2}} в оперативной памяти;

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

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

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

# соединяемые таблицы сортируются по атрибуту соединения, будем обозначать его через {{Формула|f=a}};
# организуется вложенный цикл, где выполняется сравнение значения атрибута соединения в записях таблиц {{Формула|f=Q_1}} и {{Формула|f=Q_2}}. Условием соединения может быть только равенство атрибутов соединения.

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

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

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

[[Файл:9sTORAl12pic2.png|500px|center]]

Результат соединения {{Формула|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_{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\log_b\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^{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(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)}{Q_2, 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)\cdot C_B}}

здесь:

:{{Формула|f=T(Q_1)}}, {{Формула|f=T(Q_2)}} - оценка числа записей в таблицах {{Формула|f=Q_1}} и {{Формула|f=Q_2}};
:{{Формула|f=B(Q_1)}}, {{Формула|f=B(Q_2)}} - оценка числа блоков в этих же таблицах;
:{{Формула|f=I(Q_1, a)}}, {{Формула|f=I(Q_2, a)}} - мощности атрибутов в соединении {{Формула|f=a}} тех же таблиц;
:{{Формула|f=b}} - число блоков в оперативной памяти, отводимое под сортировку этих таблиц, а также для выполнения соединения;
:{{Формула|f=C_{comp} }} - среднее время соединения двух кортежей из записей этих таблиц в оперативной памяти;
:{{Формула|f=C_{move} }} - время перемещения одной записи в оперативной памяти при сортировке;
:{{Формула|f=C_B}} - время чтения/записи одного блока на диск;
:верхние неполные квадратные скобки - округление с избытком;
:нижние неполные квадратные скобки - округление с недостатком;
:обычные квадратные скобки - необязательность, значит уже отсортировано.

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

Механизм сортировки таблиц {{Формула|f=Q_1}} и {{Формула|f=Q_2}}:
# блоки таблицы {{Формула|f=R}} читаются в буфер и там сортируются. Получается файл, который сохраняется на диск;
# в буфер читаются ещё блоки.

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

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

{{Формула|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) - Лекция №12 - Оценки (продолжение)

2013-01-11T10:50:04Z

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

{{Tabli4ka warning undone summary|text=   - схемы [[#Механизм сортировки таблиц | образования файлов со второго уровня и до последнего]].<br>А также не все [[#Формулы оценки стоимости соединения SMJ | формулы из раздела оценки SMJ]] верные.}}
{{Backward|l=ТОРА (9) - Лекция №11 - Оценки}}
Оригинал всего раздела, посвящённого оптимизации SQL-запросов, от самого [[Григорьев Ю.А. | Григорьева]] можно загрузить [http://yadi.sk/d/VjjMs6ww1HH2D здесь].
__TOC__
== Оптимизация SQL-запросов ==

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

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

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

[[Файл:9sTORAl11pic4.png|500px|center]]

Зависит от:

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

[[Файл:9sTORAl12pic1.png|600px|center]]

Если на 3 операции блоков будет больше {{Формула|f=b}}, то лишние сохраняются на диск.

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

{{Формула|f=C^{JOIN} = C_{CPU} + C_{I/O} }}

{{Формула|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=T(Q_1)}}, {{Формула|f=T(Q_2)}} оценка числа записей в таблицах подзапросов {{Формула|f=Q_1}} и {{Формула|f=Q_2}};
:{{Формула|f=B(Q_1)}} - число блоков ввода/вывода для получения таблицы {{Формула|f=Q_1}};
:{{Формула|f=C_{I/O}(Q_2)}} - время ввода/вывода для получения таблицы {{Формула|f=Q_2}};
:{{Формула|f=b}} - число блоков в буферах 1 и 3 (''из рисунка выше'');
:{{Формула|f=C_{comp} }} - время сравнения двух кортежей из {{Формула|f=Q_1}} и {{Формула|f=Q_2}} в оперативной памяти;

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

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

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

# соединяемые таблицы сортируются по атрибуту соединения, будем обозначать его через {{Формула|f=a}};
# организуется вложенный цикл, где выполняется сравнение значения атрибута соединения в записях таблиц {{Формула|f=Q_1}} и {{Формула|f=Q_2}}. Условием соединения может быть только равенство атрибутов соединения.

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

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

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

[[Файл:9sTORAl12pic2.png|500px|center]]

Результат соединения {{Формула|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_{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\log_b\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^{JOIN}_{CPU}(Q_1, Q_2) = \Bigl(\Bigl(\frac{T(Q_1)}{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(Q_2)}{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)}{Q_2, 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)\cdot C_B}}

здесь:

:{{Формула|f=T(Q_1)}}, {{Формула|f=T(Q_2)}} - оценка числа записей в таблицах {{Формула|f=Q_1}} и {{Формула|f=Q_2}};
:{{Формула|f=B(Q_1)}}, {{Формула|f=B(Q_2)}} - оценка числа блоков в этих же таблицах;
:{{Формула|f=I(Q_1, a)}}, {{Формула|f=I(Q_2, a)}} - мощности атрибутов в соединении {{Формула|f=a}} тех же таблиц;
:{{Формула|f=b}} - число блоков в оперативной памяти, отводимое под сортировку этих таблиц, а также для выполнения соединения;
:{{Формула|f=C_{comp} }} - среднее время соединения двух кортежей из записей этих таблиц в оперативной памяти;
:{{Формула|f=C_{move} }} - время перемещения одной записи в оперативной памяти при сортировке;
:{{Формула|f=C_B}} - время чтения/записи одного блока на диск;
:верхние неполные квадратные скобки - округление с избытком;
:нижние неполные квадратные скобки - округление с недостатком;
:обычные квадратные скобки - необязательность, значит уже отсортировано.

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

Механизм сортировки таблиц {{Формула|f=Q_1}} и {{Формула|f=Q_2}}:
# блоки таблицы {{Формула|f=R}} читаются в буфер и там сортируются. Получается файл, который сохраняется на диск;
# в буфер читаются ещё блоки.

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

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

{{Формула|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 семестр)]]
[[Категория:Конспекты лекций и семинаров]]
[[Категория:Незаконченные конспекты]]