ТОРА (9) - Лекция №9 - Оптимизация запросов: различия между версиями
ILobster (обсуждение | вклад) м (ссылка на оригинал лекций по оптимизации SQL-запросов) |
ILobster (обсуждение | вклад) м (→Построение логического плана: незаконченное выражение) |
||
(не показано 9 промежуточных версий 3 участников) | |||
Строка 59: | Строка 59: | ||
==== Закон перестановки селекции и объединения ==== | ==== Закон перестановки селекции и объединения ==== | ||
{{Формула|f=\sigma_{F}(R_1\bigcup R_2) = \sigma_{ | {{Формула|f=\sigma_{F}(R_1\bigcup R_2) = \sigma_{F}(R_1)\bigcup\sigma_{F}(R_2)}} | ||
==== Закон перестановки селекции и разности отношений ==== | ==== Закон перестановки селекции и разности отношений ==== | ||
{{Формула|f=\sigma_{F}(R_1 - R_2) = \sigma_{ | {{Формула|f=\sigma_{F}(R_1 - R_2) = \sigma_{F}(R_1) - \sigma_{F}(R_2)}} | ||
==== Закон перестановки проекции и декартова произведения ==== | ==== Закон перестановки проекции и декартова произведения ==== | ||
Строка 88: | Строка 88: | ||
После выполнения этих трёх правил выражение {{Формула|f=\Pi_A(\sigma_F(R_1\times ...\times R_n))}} преобразуется к виду: | После выполнения этих трёх правил выражение {{Формула|f=\Pi_A(\sigma_F(R_1\times ...\times R_n))}} преобразуется к виду: | ||
{{Формула|f=\Pi_A(\sigma_F(}}<span style="background-color:#32CD32">{{Формула|f=\Pi_{ | {{Формула|f=\Pi_A(\sigma_F(}}<span style="background-color:#32CD32">{{Формула|f=\Pi_{A_1}(\sigma_{f_1}(R_1))}}</span>{{Формула|f=\times ...\times}}<span style="background-color:#00BFFF">{{Формула|f=\Pi_{A_n}(\sigma_{f_n}(R_n))}}</span>{{Формула|f=))}}, здесь каждый <span style="background-color:#7FFF00">{{Формула|f=\Pi_{A_i}(\sigma_{f_i}(R_i))}}</span> - это ''подзапрос''. | ||
Суть в том, что сначала выполняются подзапросы, а они имеют намного меньшую размерность, чем исходная таблица, и время выполнения будет меньше, чем по исходной формуле {{Формула|f=\Pi_A(\sigma_F(R_1\times ...\times R_n))}}. | |||
=== Логический план === | === Логический план === | ||
Строка 121: | Строка 121: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
{{Формула|f=\Pi_{фамилия}(\sigma_{P.н="винт" \wedge S.н-п=SP.н-п \wedge SP.н-д=P.н-д})}} | {{Формула|f=\Pi_{фамилия}(\sigma_{P.н="винт" \wedge S.н-п=SP.н-п \wedge SP.н-д=P.н-д}(S\times P\times SP))}} | ||
[[#Оптимизация формул реляционной алгебры | | После преобразования и выделения подзапросов (как [[#Оптимизация формул реляционной алгебры | в описании]], приведённом выше) получится выражение {{Формула|f=\Pi_A(\sigma_F(\Pi_{A_i}(\sigma_{f_2}(R_1))\times ...\times \Pi_{A_n}(\sigma_{f_n}(R_n))))}}, которое можно представить в графическом виде - это и будет ''логический план выполнения запроса'': | ||
[[Файл:9sTORAl9pic1.png|400px]] | [[Файл:9sTORAl9pic1.png|400px]] | ||
Строка 148: | Строка 148: | ||
Этот запрос преобразуется сервером в неявном виде в формулу реляционной алгебры: | Этот запрос преобразуется сервером в неявном виде в формулу реляционной алгебры: | ||
{{Формула|f=\Pi_{остаток}(\sigma_{R_2.о>1500 \wedge R_1.к-п=3 \wedge R_1.н-c=R_2.н-с})}} | {{Формула|f=\Pi_{остаток}(\sigma_{R_2.о>1500 \wedge R_1.к-п=3 \wedge R_1.н-c=R_2.н-с}(R_1\times R_2))}} | ||
Теперь оптимизируем: | Теперь оптимизируем: |
Текущая версия от 13:29, 21 января 2013
Оригинал всего раздела, посвящённого оптимизации SQL-запросов, от самого Григорьева можно загрузить здесь.
Оптимизация SQL-запросов
Запрос, поступающий в СУБД, подвергается оптимизации с целью уменьшения времени его выполнения.
Шаги оптимизатора:
- строится логический план выполнения запроса (дерево логических операций);
- на основе логического плана строится физический план выполнения запроса (дерево физических операций);
- реализация этого физического плана.
Законы реляционной алгебры
Закон коммутативности декартова произведения отношений
$$R_1\times R_2 = R_2\times R_1$$, здесь и далее $$R_1$$ и $$R_2$$ - экземпляры отношений.
Закон ассоциативности декартова произведения
$$(R_1\times R_2)\times R_3 = R_1\times (R_2\times R_3)$$
Закон каскада проекций
Допустим, $$(a_1 ... a_n)\subseteq (b_1 ... b_n)$$, $${a_i}$$, $${b_i}$$ - это атрибуты отношения $$R$$
тогда $$\Pi_{a_1 ... a_n}(\Pi_{b_1 ... b_n}(R)) = \Pi_{a_1 ... a_n}(R)$$
Закон каскада селекций
Допустим, $$F = f_1\wedge f_2$$
тогда $$\sigma_F(R) = \sigma_{f_1}(\sigma_{f_2}(R))$$
Закон перестановки проекции и селекции
1)
- Допустим, в условия поиска $$F$$ входят атрибуты только из множества $$a_1 ... a_n$$
- тогда $$\Pi_{a_1 ... a_n}(\sigma_F(R)) = \sigma_F(\Pi_{a_1 ... a_n}(R))$$
2)
- Допустим, в условия поиска $$F$$ входят атрибуты не только из множества $$a_1 ... a_n$$, но и из $$b_1 ... b_n$$
- тогда $$\Pi_{a_1 ... a_n}(\sigma_F(R)) = \Pi_{a_1 ... a_n}(\sigma_F(\Pi_{a_1 ... a_n, b_1 ... b_n}(R)))$$
Селекция декартова произведения
Отношение $$f_1$$ содержит атрибуты только из отношения $$R_1$$
тогда $$\sigma_{f_1}(R_1\times R_2) = \sigma_{f_1}(R_1)\times R_2$$
- Следствие:
- пусть $$F = f_1 \wedge f_2$$ и в $$f_1$$ входят атрибуты $$R_1$$, а в $$f_2$$ входят из $$R_2$$,
- тогда $$\sigma_{F}(R_1\times R_2) = \sigma_{f_1}(R_1)\times \sigma_{f_2}(R_2)$$
- Доказательство:
- $$\sigma_{f_1 \wedge f_2}(R_1\times R_2) = \sigma_{f_1}(\sigma_{f_2}(R_1\times R_2)) = \sigma_{f_1}(\sigma_{f_2}(R_2\times R_1))=$$
- $$= \sigma_{f_1}(R_1\times\sigma_{f_2}(R_2)) = \sigma_{f_1}(R_1)\times \sigma_{f_2}(R_2)$$
Закон перестановки селекции и объединения
$$\sigma_{F}(R_1\bigcup R_2) = \sigma_{F}(R_1)\bigcup\sigma_{F}(R_2)$$
Закон перестановки селекции и разности отношений
$$\sigma_{F}(R_1 - R_2) = \sigma_{F}(R_1) - \sigma_{F}(R_2)$$
Закон перестановки проекции и декартова произведения
$$b_1 ... b_n$$ - это атрибуты отношения $$R_1$$
$$c_1 ... c_k$$ - это атрибуты отношения $$R_2$$
$$\Pi_{b_1 ... b_n, c_1 ... c_k}(R_1\times R_2)$$ = $$\Pi_{b_1 ... b_n}(R_1)\times \Pi_{c_1 ... c_k}(R_2)$$
Закон перестановки проекции и объединения
$$\Pi_{a_1 ... a_n}(R_1\bigcup R_2) = \Pi_{a_1 ... a_n}(R_1)\bigcup\Pi_{a_1 ... a_n}(R_2)$$
Оптимизация формул реляционной алгебры
Пусть условие $$F = f_1 \wedge ... \wedge f_n$$
Правила:
- переместить каждую селекцию внутрь декартова произведения, используя законы 1, 4, 6, 7, 8;
- переместить каждую проекцию внутрь декартова произведения, используя законы 1, 3, 5, 9, 10;
- по возможности скомбинировать каждый каскад селекции в одиночную селекцию и каждый каскад проекции в одиночную проекцию. Тогда всё можно будет сделать за один проход.
После выполнения этих трёх правил выражение $$\Pi_A(\sigma_F(R_1\times ...\times R_n))$$ преобразуется к виду:
$$\Pi_A(\sigma_F($$$$\Pi_{A_1}(\sigma_{f_1}(R_1))$$$$\times ...\times$$$$\Pi_{A_n}(\sigma_{f_n}(R_n))$$$$))$$, здесь каждый $$\Pi_{A_i}(\sigma_{f_i}(R_i))$$ - это подзапрос.
Суть в том, что сначала выполняются подзапросы, а они имеют намного меньшую размерность, чем исходная таблица, и время выполнения будет меньше, чем по исходной формуле $$\Pi_A(\sigma_F(R_1\times ...\times R_n))$$.
Логический план
Построение логического плана
Порядок построения:
- запрос преобразуется в формулу реляционной алгебры;
- выполняется преобразование (оптимизация) этой формулы.
Оператор SELECT
(без агрегирования, группирования и удаления дубликатов) может быть представлен так:
$$\Pi_A(\sigma_F(R_1\times ...\times R_n))$$, где
- от $$R_1$$ до $$R_n$$ - это декартово произведение отношений (таблиц), указанных за ключевым словом
FROM
; - $$\sigma_F$$ - это селекция кортежей декартова произведения в соответствии с условием, указанным за ключевым словом
WHERE
; - $$\Pi_A$$ - это проекция селекции на множество атрибутов A, указанных за ключевым словом
SELECT
В чём суть такой логической оптимизации? Сначала надо выполнить декартово произведение, потом селекцию, потом проекцию - всё по порядку скобок в этом выражении. Потому что если таблица имеет большой размер, то это выражение будет выполняться очень долго.
Пример: найти фамилии поставщиков, поставляющих детали с названием "винт".
$$\rho = (S, P, SP)$$
SELECT фамилия
FROM S, P, SP
WHERE P.название = 'винт' AND
S.номер_поставки = SP.номер_поставки AND
SP.номер_детали = P.номер_детали;
$$\Pi_{фамилия}(\sigma_{P.н="винт" \wedge S.н-п=SP.н-п \wedge SP.н-д=P.н-д}(S\times P\times SP))$$
После преобразования и выделения подзапросов (как в описании, приведённом выше) получится выражение $$\Pi_A(\sigma_F(\Pi_{A_i}(\sigma_{f_2}(R_1))\times ...\times \Pi_{A_n}(\sigma_{f_n}(R_n))))$$, которое можно представить в графическом виде - это и будет логический план выполнения запроса:
Получается, подзапросы можно выполнять параллельно, а это тоже уменьшает время выполнения всего запроса.
Пример:
Запрос найти значение остатков больше 1500 на счетах пользователя с кодом 3:
SELECT остаток
FROM R2
WHERE остаток > 1500 AND
номер_счёта IN(
SELECT номер_счёта
FROM R1
WHERE код_пользователя = 3
);
Этот запрос преобразуется сервером в неявном виде в формулу реляционной алгебры:
$$\Pi_{остаток}(\sigma_{R_2.о>1500 \wedge R_1.к-п=3 \wedge R_1.н-c=R_2.н-с}(R_1\times R_2))$$
Теперь оптимизируем:
$$=^4\Pi_{остаток}(\sigma_{R_1.н-c=R_2.н-с}(\sigma_{R_2.о>1500 \wedge R_1.к-п=3}(R_1\times R_2)))=^6$$
$$=\Pi_{остаток}(\sigma_{R_1.н-c=R_2.н-с}(\sigma_{R_1.к-п=3}(R_1)\times\sigma_{R_2.о>1500}(R_2)=^{5, 2}$$
$$=\Pi_{остаток}(\sigma_{R_1.н-c=R_2.н-с}(\Pi_{остаток, R_1.н-с, R_2.н-с}(\sigma_{R_1.к-п=3}(R_1)\times\sigma_{R_2.о>1500}(R_2))=^9$$
$$=\Pi_{остаток}(\sigma_{R_1.н-c=R_2.н-с}($$$$\Pi_{R_1.н-с}(\sigma_{R_1.к-п=3}(R_1))$$$$\times$$$$\Pi_{R_2.н-с, остаток}(\sigma_{R_2.о>1500}(R_2))$$$$))$$
Полученное выражение - результат оптимизации. Можно построить логический план выполнения запроса.
продолжение...