Просмотр исходного текста страницы Этапы обработки запроса. Перезапись запросов

В этом разделе будут рассмотрен этап обработки запросов, а именно перезапись запросов

== Обработка запроса ==
=== Мотивирующий пример ===

==== Пример базы данных: ====

*<var>Students(SId, FirstName, LastName, GId, Year)</var>
** $10^4$  записей
** Индексы: <var>(SId)</var> (кластеризованный), <var>(GId)</var>

*<var>Groups(GId, Name)</var>
** $10^3$ записей
** Индексы: <var>(GId)</var> (кластеризованный), <var>(Name)</var>

==== Запрос: ====

 -- Фамилии студентов группы M3439
 select LastName
 from Students natural join Groups
 where Name = 'M34391' 

==== Планы запросов без индексов ====

* План 1
** $π_{FirstName}(σ_{Name=M34391}(σ_{S.GId=G.GId}(S × G)))$
** $10^4·10^3 + 10^4·10^3 + 10^4 + 20 ≈ 2·10^7$ операций

*План 2
** $π_{Name}(σ_{Name=M34391}(S ⋈ G))$
** $10^4·10^3 + 10^4 + 20 ≈ 10^7$ операция

* План 3
** $π_{Name}(S ⋈ σ_{Name=M34391}(G))$
** $10^3 + 10^4 + 20 ≈ 10^4$ операций

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

* План 4. <var>Students(GId)</var>
** $π_{Name}(S ⋈ σ_{Name=M34391}(G))$
** $10^3 + (3 + 20) + 20 ≈ 10^3$ операций

* План 5. <var>Groups(Name)</var>, <var>Students(GId)</var>
** $π_{Name}(S ⋈ σ_{Name=M34391}(G))$
** $2 + (3 + 20) + 20 ≈ 45$ операций

==== Результат ====

$2·10^7$ операций — наиболее '''медленный''' план 

$45$ операций — наиболее '''быстрый''' план

От выбора плана '''сильно''' зависит производительность

----
[[Файл:Structure_Query.png|430px|thumb|right|Обработка запроса]]
[[Файл:Structure_Planner.png|430px|thumb|right|Планировщик запроса]]

=== Обработка запроса ===

Перезапись и планировщик
*Перезапись запроса
** Статические правила оптимизации запроса
** Считается, что полезны всегда

*Планировщик запроса
** Оптимизация в зависимости от данных
** Перебор вариантов

Выбор структуры и метода

*Выбор структуры
** Преобразование запроса
** Порядок выполнения операций
** Порядок соединений

*Выбор метода исполнения
** Как исполняется каждая операция

Оценка плана

*Модель стоимости
** Стоимость операции
** Размер операндов
** Размер результата

*Оценка размера и распределения
** Статистика по данным
** Статистика предыдущих запросов

== Перезапись запроса == 

=== Минимизация набора операций ===

Преобразование подзапросов

* Преобразуются в реляционную алгебру
** Запись в реляционном исчислении
** Вынос кванторов
** Преобразование в алгебру

Преобразование соединений

*Внешние соединения
**$R_1 ⟗_θ R_2 ⇒ (R_1 ⟕_θ R_2) ∪ (R_1 ⟖_θ R_2)$
**$R_1 ⟕_θ R_2 ⇒ σ_θ(R_1 × R_2) ∪ (R_1 - π_{R_1}(σ_θ(R_1 × R_2)))$
**$R_1 ⟖_θ R_2 ⇒ σ_θ(R_1 × R_2) ∪ (R_2 - π_{R_2}(σ_θ(R_1 × R_2)))$

*Декартово соединение
**$R_1 × R_2 ⇒ R_1 ⋈ R_2$

=== Унарные операции ===

Повторная фильтрация

*Правило
**Повторное применение фильтрации заменяется одинарным
**$σ_{cond_1}(σ_{cond_2}(R)) ⇒ σ_{cond_1 ∧ cond_2}(R)$

*Пример
**$π_{FirstName}(σ_{Name=M34391}(σ_{S.GId=G.GId}(S × G))) ⇒ π_{FirstName}(σ_{Name=M34391 ∧ S.GId=G.GId}(S × G))$


Повторная проекция

*Правило
**Повторное применение проекции заменяется внешней
**$π_{A}(π_{B}(R)) ⇒ π_{A}(R)$

*Пример
**$π_{FirstName}(π_{FirstName, Name}(S × G)) ⇒ π_{FirstName}(S × G)$

Проекция и фильтрация

*Правило
**Фильтрация осуществляется до проекции
**$σ_{cond}(π_{A}(R)) ⇒ π_{A}(σ_{cond}(R))$

*Пример
** $π_{FirstName}(σ_{Name=M34391}(π_{FirstName, Name}(S × G))) ⇒ π_{FirstName}(π_{FirstName, Name}(σ_{Name=M34391}(S × G))) ⇒ π_{FirstName}(σ_{Name=M34391}(S × G))$

=== Алгебраические свойства операций ===

Дистрибутивность операций

*Фильтрация
** $σ_{cond}(R_1 ∪ R_2) ⇒ σ_{cond}(R_1) ∪ σ_{cond}(R_2)$
** $σ_{cond}(R_1 \cap R_2) ⇒ σ_{cond}(R_1) \cap σ_{cond}(R_2)$
** $σ_{cond}(R_1 - R_2) ⇒ σ_{cond}(R_1) - σ_{cond}(R_2)$
** $σ_{cond_1 ∧ cond_2}(R_1 ⋈ R_2) ⇒ σ_{cond_1}(R_1) ⋈ σ_{cond_2}(R_2)$

*Проекция
** $π_A(R_1 ∪ R_2) ⇒ π_A(R_1) ∪ π_A(R_2)$
** $π_A(R_1 ∩ R_2) ⇏ π_A(R_1) ∩ π_A(R_2)$
** $π_A(R_1 - R_2) ⇏ π_A(R_1) - π_A(R_2)$
** $π_{A}(R_1 ⋈ R_2) ⇒ π_A(π_{(A ∪ R_2) ∩ R_1}(R_1) ⋈ π_{(A ∪ R_1) ∩ R_2}(R_2))$

Коммутативность операций

*Коммутативные операции
**$⋈$, 
**$∪$,  
**$∩$

*Некоммутативные операции
**$-$
**$\div$, $⋇$

*Применение коммутативности
**Выбор левой и правой стороны для несимметричных методов исполнения

Ассоциативность операций

*Ассоциативные операции
**$⋈$, 
**$∪$,  
**$∩$

*Неассоциативные операции
**$-$
**$\div$, $⋇$

*Применение ассоциативности
**Выбор порядка выполнения операций

=== Обработка условий ===

Замыкание предикатов

*Примеры правил
**$a = b ∧ b = c ⇒ a = b ∧ b = c ∧ a = c$
**$a &gt; b ∧ b = c ⇒ a &gt; b ∧ b = c ∧ a &gt; c$
**$a &gt; b ∧ b &gt; c ⇒ a &gt; b ∧ b &gt; c ∧ a &gt; c$

*Пример
**$σ_{P_1.p &gt; P_2.p ∧ P_2.p ≥ 60}(P_1 ⋈_{P_1.SId = P_2.SId} P_2) ⇒ σ_{P_1.p &gt; P_2.p ∧ P_2.p ≥ 60 ∧ P_1.p &gt; 60}(P_1 ⋈_{P_1.SId = P_2.SId} P_2) ⇒ σ_{P_1.p &gt; P_2.p}(σ_{p &gt; 60}(P_1) ⋈_{P_1.SId = P_2.SId} σ_{p ≥ 60}(P_2))$

КНФ и ДНФ

*Преобразование предикатов
**Конъюнктивная нормальная форма
**Дизъюнктивная нормальная форма

*Вычисление КНФ
**Слева направо, до первой лжи
*Вычисление ДНФ
**Слева направо, до первой истины

=== Семантические оптимизации ===

Семантическая оптимизация

*Применение знания об ограничениях
**Неэквивалентные запросы
**Тот же результат

*Пример
**$π_{FirstName}(Students ⋈ Groups) ⇒ π_{FirstName}(Students)$, если $Students.GId ⊂ Groups.GId$

Пример оптимизации

*Ограничение
**У всех, кто получает стипендию все оценки $≥ 60$
**<pre class="prettyprint lang-sql">check not HasScolarship or 60 &lt;= all(select Points from Points where Points.SId = Id)</pre>
*Запрос
**Оценки стипендиатов группы M34391 по СУБД
**<pre class="prettyprint lang-sql">select Points from Students natural join Points where HasScolarship and CId = 10 and GId = M34391</pre>
**$σ_{HasScolarship ∧ CId = 10}(Students ⋈ Points)$

*Оптимизированный запрос
**$σ_{GId=M34391 ∧ HasScolarship}(Students) ⋈ σ_{60 ≥ Points ∧ CId = 10}(Points)$

=Литература=
* ''Дейт К.'' Введение в системы баз данных (глава 18)
[[Категория: Базы данных]]