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

ТОРА (9) - Семинар №1 - Операции реляционной алгебры

2018-02-05T19:52:40Z

91.76.160.54: /* Задача №8 */

Операции реляционной алгебры и их связь с SQL.

== Операторы SQL ==

=== SELECT ===

SELECT - выборка, DISTINCT - исключая.

<syntaxhighlight lang=sql>SELECT [DISTINCT] * | атрибуты
FROM таблицы
WHERE условие</syntaxhighlight>

=== UPDATE ===

UPDATE - обновление, изменение.

<syntaxhighlight lang=sql>UPDATE таблица
SET атрибут = выражение
WHERE условие</syntaxhighlight>

=== INSERT ===

INSERT - вставка, добавление новых записей.

<syntaxhighlight lang=sql>INSERT
INTO таблица
записи</syntaxhighlight>

=== DELETE ===

DELETE - удаление записей.

<syntaxhighlight lang=sql>DELETE
FROM таблица
WHERE условие</syntaxhighlight>

== Предметная область, используемая в задачах ==

Этого семинара, само собой.

=== Таблицы ===

Таблицы {{Формула|f=\rho=(S,P,SP)}}

*{{Формула|f=S}} - поставщики.
**SN - номер поставщика;
**SF - фамилия;
**SS - статус;
**SG - город.

*{{Формула|f=P}} - деталь.
** PN - номер детали, ключ;
** PF - название детали;
** PC - цена за единицу.

*{{Формула|f=SP}} - поставка.
** SN - номер поставщика;
** PN - номер детали;
** kol - количество поставляемых деталей.

=== Примеры экземпляров отношений ===

{|
| valign="top" |
{| class="wikitable"
|+ {{Формула|f=S}}
! SN || SF || SS || SG
|- align="center"
| S1 || Иванов || 80 || Москва
|- align="center"
| S2 || Петров || 40 || Самара
|- align="center"
| S3 || Кротов || 100 || Москва
|}
|
| valign="top" |
|
{| class="wikitable"
|+ {{Формула|f=P}}
! PN || PF || PC
|- align="center"
| P1 || болт || 20
|- align="center"
| P2 || гайка || 25
|- align="center"
| P3 || шайба || 10
|- align="center"
| P4 || гайка || 30
|}
|
| valign="top" |
|
{| class="wikitable"
|+ {{Формула|f=SP}}
! SN || PN || kol
|- align="center"
| S1 || P1 || 100
|- align="center"
| S1 || P3 || 200
|- align="center"
| S2 || P3 || 150
|- align="center"
| S3 || P3 || 50
|}
|}

== Задачи ==

=== Задача №1 ===

Проекция. Найти города, где проживают поставщики.

{{Формула|f=t=\Pi_{SG}(S)}}

Получится:

{| class="wikitable"
! SG
|- align="center"
| Москва
|- align="center"
| Самара
|}

<syntaxhighlight lang=sql>SELECT DISTINCT SG FROM S</syntaxhighlight>

=== Задача №2 ===

Селекция. Найти поставщиков со статусом больше 70.

{{Формула|f=t=\sigma_{SS>70}(S)}}

Получится:

{| class="wikitable"
! SN || SF || SS || SG
|- align="center"
| S1 || Иванов || 80 || Москва
|- align="center"
| S3 || Кротов || 100 || Москва
|}

<syntaxhighlight lang=sql>SELECT * FROM S WHERE SS > 70</syntaxhighlight>

=== Задача №3 ===

Найти номера и фамилии поставщиков со статусом меньше 80.

{{Формула|f=t=\Pi_{SN,SF}(\sigma_{SS<80}(S))}}

Получится:

{| class="wikitable"
! SN || SF
|- align="center"
| S2 || Петров
|}

<syntaxhighlight lang=sql>SELECT SN, SF
FROM S
WHERE SS < 80</syntaxhighlight>

=== Задача №4 ===

Удалить все поставки поставщика с номером S1.

{{Формула|f=SP = SP - \sigma_{SN=S1}(SP)}}

Получится:

{|+SP | class="wikitable"
! SN || PN || kol
|- align="center"
| S2 || P3 || 150
|- align="center"
| S3 || P3 || 50
|}

<syntaxhighlight lang=sql>DELETE
FROM SP
WHERE SN = S1</syntaxhighlight>

=== Задача №5 ===

Добавить в таблицу S новых поставщиков из таблицы SNEW.

{|+SNEW | class="wikitable"
! SN || SF || SS || SG
|- align="center"
| S4 || Петров || 30 || Тверь
|- align="center"
| S5 || Сидоров || 50 || Тверь
|}

{{Формула|f=S = SP\bigcup S}}

Получится:

{|+ таблица SNEW | class="wikitable"
! SN || SF || SS || SG
|- align="center"
| S1 || Иванов || 80 || Москва
|- align="center"
| S2 || Петров || 40 || Самара
|- align="center"
| S3 || Кротов || 100 || Москва
|- align="center"
| S4 || Петров || 30 || Тверь
|- align="center"
| S5 || Сидоров || 50 || Тверь
|}

<syntaxhighlight lang=sql>INSERT
INTO S
SELECT * FROM SNEW</syntaxhighlight>

=== Задача №6 ===

Найти номера поставщиков, поставляющих детали по цене меньше 30.

{{Формула|f=r = \sigma_{PC<30}(P)}}

{{Формула|f=t = SP \bowtie_{PN} r }}

Получится:

{| class="wikitable"
! PN !! PF !! PC !! SN !! kol
|- align="center"
| P1 || болт || 20 || S1 || 100
|- align="center"
| P3 || шайба || 10 || S1 || 200
|- align="center"
| P3 || шайба || 10 || S2 || 150
|- align="center"
| P3 || шайба || 10 || S3 || 50
|}

{{Формула|f=z = \Pi_{SN}(t)}}

Получится:

{| class="wikitable"
! SN
|- align="center"
| S1
|- align="center"
| S2
|- align="center"
| S3
|}

<syntaxhighlight lang=sql>SELECT DISTINCT SN
FROM SP, P
WHERE PC < 30 AND SP.PN = P.PN</syntaxhighlight>

=== Задача №7 ===

Найти номера и фамилии поставщиков, поставляющих шайбы в количестве больше 100.

{{Формула|f=w = \sigma_{PF=шайба}(P)}}

{{Формула|f=t = w \bowtie_{PN}SP }}

{{Формула|f=z = \sigma_{kol>100}(t)}}

{{Формула|f=q = z \bowtie_{SN} S}}

{{Формула|f=x = \Pi_{SN,SF}(q)}}

Получится:

{| class="wikitable"
! SN || SF
|- align="center"
| S1 || Иванов
|- align="center"
| S2 || Петров
|}

<syntaxhighlight lang=sql>SELECT SN, SF
FROM S, P, SP
WHERE PF = 'шайба' AND kol > 100 AND P.PN = SP.PN AND SP.SN = S.SN</syntaxhighlight>

=== Задача №8 ===

Все поставщики переехали из Москвы в Питер. Модифицировать таблицу S.

{{Формула|f=t = \sigma_{SS=Москва}(S)}}, получится:

{| class="wikitable"
! SN || SF || SS || SG
|- align="center"
| S1 || Иванов || 80 || Москва
|- align="center"
| S3 || Кротов || 100 || Москва
|}

{{Формула|f=f = \Pi_{SN,SF,SS}(t)}}, получится:

{| class="wikitable"
! SN || SF || SS
|- align="center"
| S1 || Иванов || 80
|- align="center"
| S3 || Кротов || 100
|}

Ввели новую таблицу spb:

{| class="wikitable"
!SG
|- align="center"
| Санкт-Петербург
|}

{{Формула|f=m = f\times spb}}, получится:

{| class="wikitable"
! SN || SF || SS || SG
|- align="center"
| S1 || Иванов || 80 || Санкт-Петербург
|- align="center"
| S3 || Кротов || 100 || Санкт-Петербург
|}

{{Формула|f=z = S - t}}, получится:

{| class="wikitable"
! SN || SF || SS || SG
|- align="center"
| S2 || Петров || 40 || Самара
|}

{{Формула|f=S = m \bigcup z}}, получится:

{| class="wikitable"
! SN || SF || SS || SG
|- align="center"
| S1 || Иванов || 80 || Санкт-Петербург
|- align="center"
| S3 || Кротов || 100 || Санкт-Петербург
|- align="center"
| S2 || Петров || 40 || Самара
|}

<syntaxhighlight lang=sql>
UPDATE S
SET SG='Санкт Петербург'
WHERE SG='Москва'
</syntaxhighlight>

[[Категория:Теоретические основы реляционной алгебры (9 семестр)|С]]
[[Категория:Конспекты лекций и семинаров]]

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

2018-02-05T16:15:55Z

91.76.160.54: /* OptPlanReturn() */

Оригинал всего раздела, посвящённого оптимизации SQL-запросов, от самого [[Григорьев Ю.А. | Григорьева]] можно загрузить [http://yadi.sk/d/VjjMs6ww1HH2D здесь].
__TOC__
== Оптимизация SQL-запросов ==

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

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

===== Число кортежей, блоков и мощности атрибутов в соединениях =====

Справедливы для [[ТОРА_(9)_-_Лекция_№12_-_Оценки_(продолжение)#Метод ложных циклов (NLJ) | NLJ]], [[ТОРА_(9)_-_Лекция_№12_-_Оценки_(продолжение)#Метод сортировки слияния (SMJ) | SMJ]] и [[ТОРА (9) - Лекция №13 - Оценки (продолжение)#Метод хешированных соединений (Hash Join) | HJ]].

1) количество кортежей в соединении:

:{{Формула|f=T(Q_1\bowtie Q_2) = \frac{T(Q_1)\cdot T(Q_2)}{max(I(Q_1, a), I(Q_2, a))} }}

2) числов блоков:

:{{Формула|f=B(Q_1\bowtie Q_2) = \Bigl\lceil\frac{T(Q_1\bowtie Q_2)}{JOIN}\Bigr\rceil}} - верхние неполные квадратные скобки означают округление с избытком;

3) мощности атрибутов:

:* атрибутов ({{Формула|f=a}}) в результирующей таблице:
::{{Формула|f=I(Q_1\bowtie Q_2, a) = min(I(Q_1, a), I(Q_2, a))}}
:* остальных атрибутов ({{Формула|f=b}}):
::два варианта:
::* {{Формула|f=I(Q_1\bowtie Q_2, b) = min(T(Q_1\bowtie Q_2, I(Q_1, b))}}, если {{Формула|f=b}} - атрибут таблицы {{Формула|f=Q_1}};
::* {{Формула|f=I(Q_1\bowtie Q_2, b) = min(T(Q_1\bowtie Q_2, I(Q_2, b))}}, если {{Формула|f=b}} - атрибут таблицы {{Формула|f=Q_2}}.

===== Алгоритмы для поиска физического плана =====

Алгоритмы описываются на псевдоязыке с заимствованиями из C++:
* комментарии обозначаются косыми:
:<code>// камент</code>
* обращение к полям структуры через точку:
:<code>структура.поле</code>

====== Алгоритм поиска физического плана с минимальной стоимостью (для левостороннего дерева) ======

Вход: логический план выполнения запроса с таблицами {{Формула|f=R_1 .. R_n}} (декартово соединение таблиц).

Выход: квазиоптимальный (потому что рассматриваем левосторонние деревья) план выполнения запроса.

'''@НАЧАЛО АЛГОРИТМА'''

ДЛЯ {{Формула|f=i = 1,n}}

:{{Формула|f=AccessPlan(R_i)}}; // определение параметров подзапроса {{Формула|f=Q_i = \Pi_{A_i}(\Sigma_{f_i}(R_i))}}.

КОНЕЦ ДЛЯ

// поиск оптимального плана

ДЛЯ {{Формула|f=i = 2,n}}

:ДЛЯ всех подмножеств {{Формула|f=P\subset {Q_1..Q_n}, |P| = i}}
:// для {{Формула|f=i = 2}}
:// {{Формула|f=P = (Q_1, Q_2)}}, {{Формула|f=P = (Q_2, Q_3)}}, {{Формула|f=P = (Q_1, Q_3)}}
:// для {{Формула|f=i = 3}}
:// {{Формула|f=P = (Q_1, Q_2, Q_3)}} и так же все варианты комбинаций
::ДЛЯ всех таблиц {{Формула|f=Q_j\in P}}
:::{{Формула|f=JoinPlan(P - Q_j, Q_j)}} // {{Формула|f=(P - Q_j)\bowtie Q_j}}
::КОНЕЦ ДЛЯ
:КОНЕЦ ДЛЯ

КОНЕЦ ДЛЯ

// вывод оптимального плана

{{Формула|f=OptPlanReturn({Q_1..Q_n})}}

'''@КОНЕЦ АЛГОРИТМА'''

====== Массив структур ======

Процедуры из алгоритма выше:
* {{Формула|f=AccessPlan()}};
* {{Формула|f=JoinPlan()}};
* {{Формула|f=OptPlanReturn()}}.

Процедуры алгоритма работают с массивом ''структур''. Формат экземпляра структуры:

{| class="wikitable"
|- align="center"
| {{Формула|f=W}} || {{Формула|f=X}} || {{Формула|f=Y}} || {{Формула|f=Z}} || {{Формула|f=ZIO}} || {{Формула|f=V}}
|}

{{Формула|f=W}}:
:если мощность {{Формула|f=W > 1}}, то {{Формула|f=W\subset {Q_i} }}, {{Формула|f=W = X\bigcup Y}};
:если мощность {{Формула|f=W = 1}}, то {{Формула|f=W}} - это имя таблицы {Q_i}}}.

{{Формула|f=X}}:
:{{Формула|f=X\subset {Q_i} }}, которые были использованы в качестве левого аргумента соединения.

{{Формула|f=Y}}:
:имя таблицы {{Формула|f=Q_i}}, которая была использована в качестве правого аргумента соединения. Если мощность {{Формула|f=W = 1}}, то {{Формула|f=X}} и {{Формула|f=Y}} пустые.

{{Формула|f=Z}}:
:если {{Формула|f=W > 1}}, {{Формула|f=Z}} - текущая стоимость выполнения плана, включающая стоимость выполнения подзапросов и промежуточных соединений;
:если {{Формула|f=W = 1}}, {{Формула|f=Z}} - оценка времени выполнения(?) {{Формула|f=Q_i}}.

{{Формула|f=ZIO}}:
:составляющая {{Формула|f=Z}}, касающаяся ввода/вывода.

{{Формула|f=V}}:
:опции. Включает в себя:
:1) число записей:
:* если мощность {{Формула|f=W > 1}}, то {{Формула|f=T(W)}} - число прогнозируемых записей;
:* если мощность {{Формула|f=W = 1}}, то {{Формула|f=T(Q_i)}} - оценка числа записей в подзапросе;
:2) {{Формула|f=B(W)}} - прогнозируемое число блоков;
:3) {{Формула|f={I(W, A_i)} }} - мощности атрибутов, по которым было выполнено или выполняется соединение;
:4) идентификатор:
:* если мощность {{Формула|f=W > 1}}, то {{Формула|f=k}} - идентификатор метода соединения таблиц;
:* если мощность {{Формула|f=W = 1}}, то {{Формула|f=k}} - идентификатор метода выбора записей из исходных таблиц.

====== AccessPlan() ======

Вход: {{Формула|f=R_i}} - имя исходной таблицы.

Выход: {{Формула|f=str[i]}} - заполненный экземпляр структуры (описанной выше).

'''@НАЧАЛО АЛГОРИТМА'''

// оценка стоимости выбора записей из {{Формула|f=R_i}} для различных методов

// {{Формула|f=j = 1}} - TableScan

// {{Формула|f=j = 2}} - IndexScan

ДЛЯ {{Формула|f=i = 1, 2}}
:{{Формула|f=C_j = C_{CPU} + C_{I/O} }} // для разных {{Формула|f=j}} разные формулы из прошлых лекций
КОНЕЦ ДЛЯ

// определение оптимального метода выбора записей из {{Формула|f=R_i}}

{{Формула|f=С = min(C_1, C_2)}} // здесь {{Формула|f=C = C_k}}

// заполнение экземпляра {{Формула|f=str[i]}}

{{Формула|f=str[i] = }}

{
:{{Формула|f={Q_i} }}, {{Формула|f=\varnothing}}, {{Формула|f=\varnothing}} // {{Формула|f=W}}, {{Формула|f=X}}, {{Формула|f=Y}}
:{{Формула|f=C}}, {{Формула|f=C_{I/O_k} }} // {{Формула|f=Z}}, {{Формула|f=ZIO}}
:{{Формула|f={T(Q_i), B(Q_i), {min(T(Q_i), I(R_i, A_i))}, k} }} // {{Формула|f=V}}
}

'''@КОНЕЦ АЛГОРИТМА'''

====== JoinPlan() ======

Вход: {{Формула|f=R = (P - Q_j)}}, {{Формула|f=S = Q}}.

Выход: {{Формула|f=str[n]}}.

'''@НАЧАЛО АЛГОРИТМА'''

1)

:// поиск в массиве структур {{Формула|f=str[]}} номеров экземпляров {{Формула|f=m_1}} и {{Формула|f=m_2}}, для которых {{Формула|f=str[m_1].W = R}} и {{Формула|f=str[m_2].W = S}}

:// оценка стоимости соединения для различных методов
:// если {{Формула|f=i = 1}}, то NLJ
:// если {{Формула|f=i = 2}}, то SMJ
:// если {{Формула|f=i = 3}}, то HJ
:// {{Формула|f=k}} - выбор оптимального из этих трёх

2)

:ДЛЯ {{Формула|f=i = 1, 3}}
::{{Формула|f=C_i = C_{CPU_i} + C_{I/O_i} }} // для разных {{Формула|f=i}} разные формулы из предыдущих лекций
:КОНЕЦ ДЛЯ

:{{Формула|f=C = min(C_1, C_2)}} // стоимость соединения {{Формула|f=R}} и {{Формула|f=S}}

:{{Формула|f=C = str[m_1].Z + str[m_2].Z + C}}

3)

:// поиск {{Формула|f=str[n].W = P}}
:// а) если такого экземпляра не существует, то заполнить очередной пустой экземпляр {{Формула|f=n}}.
:// б) если такой экземпляр найден, то сравнить стоимость выполнения плана. И если {{Формула|f=str[n].Z > C}}, то перезаписать экземпляр {{Формула|f=n}}.

:{{Формула|f=str[n] =}}
:{
::{{Формула|f=P}}, {{Формула|f=R}}, {{Формула|f=S}} // {{Формула|f=W}}, {{Формула|f=X}}, {{Формула|f=Y}}
::{{Формула|f=C}}, {{Формула|f=C_{I/O_k} }} // {{Формула|f=Z}}, {{Формула|f=ZIO}}
::{{Формула|f={T(P), B(P), {I(P, A_i)}_i, k} }} // {{Формула|f=V}}
:}

'''@КОНЕЦ АЛГОРИТМА'''

====== OptPlanReturn() ======

Вход: список таблиц {{Формула|f=Q_i = {Q_1..Q_n} }}

Выход: вывод оптимального плана.

'''@НАЧАЛО АЛГОРИТМА'''

1)

:// поиск в массиме структур {{Формула|f=str[]}} экземпляра, который {{Формула|f=str[i].W = Q}}

:печать{{Формула|f=(Q}}, " = ", {{Формула|f=str[i].X}}, " {{Формула|f=\bowtie}} ", {{Формула|f=str[i].Y}}, " метод ", {{Формула|f=str[i].V.k)}}

2)

:// если поле {{Формула|f=str[i].X}} пусто, то выйти из алгоритма
:// иначе рекурсивно вызываем сами себя, {{Формула|f=OptPlanReturn(str[i].X)}} // вывод оптимального плана для левого аргумента соединения

3)

:{{Формула|f=OptPlanReturn(str[i].Y)}} // вывод метода выбора записей из правого аргумента соединения

'''@КОНЕЦ АЛГОРИТМА'''

[[Категория:Теоретические основы реляционной алгебры (9 семестр)]]
[[Категория:Конспекты лекций и семинаров]]

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

2018-02-04T23:43:21Z

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

{{Tabli4ka warning undone summary|text=   - схемы [[#Механизм сортировки таблиц | образования файлов со второго уровня и до последнего]]. А также не все [[#Формулы оценки стоимости соединения 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_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 \log_b 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)}{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}}

здесь:

:{{Формула|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=b}} блоков сравниваются первые записи сохранённых на предыдущем этапе файлов (то есть, {{Формула|f=b}} файлов, если все сразу сравнивать не можем, потому что их сильно много). Минимальное среди сравниваемых записей значение пишется в файл следующего уровня, а стек, из которого это значение взяли, поднимается.

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

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

2018-02-04T23:34:39Z

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

{{Tabli4ka warning undone summary|text=   - схемы [[#Механизм сортировки таблиц | образования файлов со второго уровня и до последнего]]. А также не все [[#Формулы оценки стоимости соединения 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_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 \log_b 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=b}} блоков сравниваются первые записи сохранённых на предыдущем этапе файлов (то есть, {{Формула|f=b}} файлов, если все сразу сравнивать не можем, потому что их сильно много). Минимальное среди сравниваемых записей значение пишется в файл следующего уровня, а стек, из которого это значение взяли, поднимается.

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

{{Формула|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) - Лекция №10 - Логический и физический план запроса

2018-02-04T21:24:15Z

91.76.160.54: /* Чтение записей из индекса и фильтрация */

{{Backward|l=ТОРА (9) - Лекция №9 - Оптимизация запросов}}
Оригинал всего раздела, посвящённого оптимизации SQL-запросов, от самого [[Григорьев Ю.А. | Григорьева]] можно загрузить [http://yadi.sk/d/VjjMs6ww1HH2D здесь].
__TOC__
== Оптимизация SQL-запросов ==

=== Логический план ===

==== Порядок выполнения запроса на логическом уровне ====

Пример с предыдущей лекции: {{Формула|f=\Pi_{остаток}(\sigma_{R_1.н-c=R_2.н-с}(}}{{Формула|f=\Pi_{R_1.н-с}(\sigma_{R_1.к-п=3}(R_1))}}{{Формула|f=\times}}{{Формула|f=\Pi_{R_2.н-с, остаток}(\sigma_{R_2.о>1500}(R_2))}}{{Формула|f=))}}

Каждый из подзапросов - это промежуточные таблицы {{Формула|f=Q_1}} и {{Формула|f=Q_2}}.

1)

:{{Формула|f=Q_1}}:
:{| class="wikitable"
|- align="center"
| 102
|}

:{{Формула|f=Q_2}}:
:{| class="wikitable"
|- align="center"
| 101 || 2000
|- align="center"
| 102 || 3000
|}

2)

:соединение {{Формула|f=Q_1}} и {{Формула|f=Q_2}} (естественное соединение):

::декартово произведение:
::{| class="wikitable"
! {{Формула|f=R_{1_{ном.сч} } }} !! {{Формула|f=R_{2_{ном.сч} } }} !! {{Формула|f=R_{2_{ост} } }}
|- align="center"
| 102 || 101 || 2000
|- align="center"
| 102 || 102 || 3000
|}

::соединение:
::{| class="wikitable"
! {{Формула|f=R_{1_{ном.сч} } }} !! {{Формула|f=R_{2_{ном.сч} } }} !! {{Формула|f=R_{2_{ост} } }}
|- align="center"
| 102 || 102 || 3000
|}

::проекция:
::{| class="wikitable"
! Остаток
|- align="center"
| 3000
|}

Вот этот результат и передаётся от СУБД на рабочую станцию.

А теперь предположим, что таблицы {{Формула|f=R_1}} и {{Формула|f=R_2}} находятся на разных серверах. В этом случае, подзапросы {{Формула|f=Q_1}} и {{Формула|f=Q_2}} после оптимизации на сервере-оптимизаторе преобразуются в <code>SELECT</code>.

{{Формула|f=Q_1}}:
<syntaxhighlight lang="sql">
SELECT R1.ном.сч
FROM R1
WHERE R1.код.польз = 3;
</syntaxhighlight>

{{Формула|f=Q_2}}:
<syntaxhighlight lang="sql">
SELECT R2.ном.сч, R2.ост
FROM R2
WHERE R2.ост > 1500;
</syntaxhighlight>

Эти подзапросы направляются на сервера, где хранятся соответствующие таблицы, там они параллельно выполняются, результаты возвращаются серверу-оптимизатору, а от него - пользователю.

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

==== Построение физического плана ====

При построении оптимального физического плана СУБД выполняет следующие действия:
# Последовательно строится множество физических планов на основе [[ТОРА (9) - Лекция №9 - Оптимизация запросов#Логический план | логического плана]]. Эти физические планы отличаются следующим:
## методом выбора записей из исходных таблиц (методом реализации подзапросов);
## порядком соединения промежуточных таблиц {{Формула|f=Q_i}} (комбинация вариантов соединения нескольких таблиц);
## методом соединения таблиц (вложенными циклами, сортировкой слияния или ещё как);
# Для каждого физического плана оценивается его стоимость и выбирается план с наименьшей. В стоимости учитывается и процессорная составляющая, и составляющая времени ввода/вывода.

==== Методы выбора записей из исходной таблицы ====

===== Чтение всех записей и фильтрация =====

<code>TableScan + Filter</code>

[[Файл:9sTORAl10pic3.png|kink=9sTORAl10pic3.svg|right]]

Формула стоимости:

{{Формула|f=Cost_\Sigma = C_{CPU} + C_{IO} }}

{{Формула|f=C_{CPU} = T(R)\cdot C_{filter} }}

{{Формула|f=C_{IO} = B(R)\cdot C_B}}

здесь:
:{{Формула|f=T(R)}} - общее количество записей в таблице {{Формула|f=R}};
:{{Формула|f=B(R)}} - число физических блоков в таблице {{Формула|f=R}};
:{{Формула|f=C_{filter} }} - среднее время фильтрации одной записи;
:{{Формула|f=C_B}} - время чтения/записи одного блока на диск.

===== Чтение записей из индекса и фильтрация =====

<code>IndexScan + Filter</code>

[[Файл:9sTORAl10pic4.png|kink=9sTORAl10pic4.svg|right]]

Формула стоимости:

{{Формула|f=Cost_\Sigma = C_{CPU} + C_{IO} }}

{{Формула|f=C_{CPU} = \frac{T(R) \cdot k}{I(R,a)}\cdot C_{filter} }}

{{Формула|f=C_{IO} }} - как и в предыдущем методе, умножаем время чтения/записи на число записей в блоке индекса. Но тут два варианта:
# для кластеризованного: {{Формула|f=C_{IO} = \frac{B(Index(R,a)) \cdot k}{I(R,a)}\cdot C_B + \frac{B(R)\cdot k}{I(R,a)}\cdot C_B}}. В кластеризованном индексе последовательность значений в индексе и в таблице совпадает;
# для индекса без кластеризации {{Формула|f=C_{IO} = \frac{B(Index(R,a)) \cdot k}{I(R,a)}\cdot C_B + \frac{T(R)\cdot k}{I(R,a)}\cdot C_B}}. Последовательность в индексе и таблице не совпадает. Число в этом случае читаемых записей равно числу блоков. Или наоборот.

здесь:
:{{Формула|f=T(R)}} - общее количество записей в таблице {{Формула|f=R}};
:{{Формула|f=B(R)}} - число физических блоков в таблице {{Формула|f=R}};
:{{Формула|f=I(R,a)}} - мощность индексируемого атрибута {{Формула|f=a}} таблицы {{Формула|f=R}} (число разных значений, исключая пустое множество);
:{{Формула|f=B(Index(R,a))}} - число блоков на листовом уровне индекса по атрибуту {{Формула|f=a}};
:{{Формула|f=C_{filter} }} - среднее время фильтрации одной записи;
:{{Формула|f=C_B}} - время чтения/записи одного блока на диск;
:{{Формула|f=k}} - мощность атрибута {{Формула|f=a}} в запросе (число разных значений, указанных в подзапросе {{Формула|f=y}}).

Определение {{Формула|f=k}}:
* {{Формула|f=k = 1}}, если {{Формула|f=y}}: {{Формула|f=a = const}};
* {{Формула|f=k = n}}, если {{Формула|f=y}}: {{Формула|f=a}} <code>IN</code> {{Формула|f=(C_1 ... C_n)}}, {{Формула|f=C_i = const}};
* {{Формула|f=k =}} диапазон значений, если {{Формула|f=y}}: {{Формула|f=a >= C_1}} <code>AND</code> {{Формула|f=a <= C_2}};
* {{Формула|f=k =}} число атрибутов, удовлетворяющих образцу, если {{Формула|f=y}}: {{Формула|f=a}} <code>LIKE 'чтонить'</code>.

=== Отличие физического плана от логического ===

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

==== Пример логического плана ====

[[Файл:9sTORAl10pic1.png|kink=9sTORAl10pic1.svg]]

==== Пример физического плана ====

[[Файл:9sTORAl10pic2.png|kink=9sTORAl10pic2.svg]]

Данный физический план реализуется следующим образом;
# для реализации подзапроса к {{Формула|f=R_1}} читается вся таблица, записи фильтруются по {{Формула|f=f_1}} и получаемая таблица является правым аргументов в операции соединения;
# из таблицы {{Формула|f=R_2}} выделяется подусловие {{Формула|f=y}} для индексируемого атрибута, а потом выполняется чтение записей, удовлетворяющих этому условию. Полученные записи фильтруются по {{Формула|f=f_2}} и получаемая таблица является левым аргументом в операции соединения.

Как мы уже знаем, оптимизатор для каждого физического плана рассчитывает стоимость. Рассмотрим этот расчёт для данного примера: {{Формула|f= Cost_\Sigma =}}{{Формула|f=Cost(TableScan(R_1), Filter(f_1, \Pi_{A_1}))}}{{Формула|f=+}}{{Формула|f=Cost(IndexScan(R_2, y), Filter(f_2, \Pi_{A_2}))}}{{Формула|f=+}}{{Формула|f=Cost(\bowtie)}}

Каждая из {{Формула|f=Cost()}} учитывает и процессорную составляющую, и временную составляющую ввода-вывода.

{{Forward|l=ТОРА (9) - Лекция №11 - Оценки}}

[[Категория:Теоретические основы реляционной алгебры (9 семестр)]]
[[Категория:Конспекты лекций и семинаров]]