Этапы обработки запроса. Перезапись запросов — различия между версиями
Fadeev (обсуждение | вклад) (→Коммутативность операций) |
|||
(не показана 41 промежуточная версия этого же участника) | |||
Строка 2: | Строка 2: | ||
== Обработка запроса == | == Обработка запроса == | ||
− | |||
− | |||
=== Мотивирующий пример === | === Мотивирующий пример === | ||
+ | От выбора плана '''сильно''' зависит производительность | ||
+ | ==== Пример базы данных: ==== | ||
− | + | *<var>Students(SId, FirstName, LastName, GId, Year)</var> | |
+ | ** $10^4$ записей | ||
+ | ** Индексы: <var>(SId)</var> (кластеризованный), <var>(GId)</var> | ||
− | <var> | + | *<var>Groups(GId, Name)</var> |
− | * $10^ | + | ** $10^3$ записей |
− | * Индексы: <var>( | + | ** Индексы: <var>(GId)</var> (кластеризованный), <var>(Name)</var> |
− | + | ==== Запрос: ==== | |
− | |||
− | |||
− | |||
− | |||
Фамилии студентов группы M3439 | Фамилии студентов группы M3439 | ||
− | |||
select LastName | select LastName | ||
from Students natural join Groups | from Students natural join Groups | ||
− | where Name = 'M34391' | + | 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}(σ_{Name=M34391}( | + | ** $π_{Name}(S ⋈ σ_{Name=M34391}(G))$ |
− | * $10 | + | ** $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))$ | + | ** $π_{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|Планировщик запроса]] | ||
=== Обработка запроса === | === Обработка запроса === | ||
− | Перезапись и планировщик | + | ==== Перезапись и планировщик ==== |
− | * Статические правила оптимизации запроса | + | *Перезапись запроса |
− | * Считается, что полезны всегда | + | ** Статические правила оптимизации запроса |
+ | ** Считается, что полезны всегда | ||
− | Планировщик запроса | + | *Планировщик запроса |
− | * Оптимизация в зависимости от данных | + | ** Оптимизация в зависимости от данных |
− | * Перебор вариантов | + | ** Перебор вариантов |
− | Выбор структуры и метода | + | ==== Выбор структуры и метода ==== |
− | Выбор структуры | + | *Выбор структуры |
− | * Преобразование запроса | + | ** Преобразование запроса |
− | * Порядок выполнения операций | + | ** Порядок выполнения операций |
− | * Порядок соединений | + | ** Порядок соединений |
− | Выбор метода исполнения | + | *Выбор метода исполнения |
− | * Как исполняется каждая операция | + | ** Как исполняется каждая операция |
− | Оценка плана | + | ==== Оценка плана ==== |
− | Модель стоимости | + | *Модель стоимости |
− | * Стоимость операции | + | ** Стоимость операции |
− | * Размер операндов | + | ** Размер операндов |
− | * Размер результата | + | ** Размер результата |
− | Оценка размера и распределения | + | *Оценка размера и распределения |
− | * Статистика по данным | + | ** Статистика по данным |
− | * Статистика предыдущих запросов | + | ** Статистика предыдущих запросов |
== Перезапись запроса == | == Перезапись запроса == | ||
Строка 89: | Строка 91: | ||
=== Минимизация набора операций === | === Минимизация набора операций === | ||
− | Преобразование подзапросов | + | ==== Преобразование подзапросов ==== |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | * Преобразуются в реляционную алгебру | |
+ | ** Запись в реляционном исчислении | ||
+ | ** Вынос кванторов | ||
+ | ** Преобразование в алгебру | ||
− | + | ==== Преобразование соединений ==== | |
− | + | *Внешние соединения | |
+ | **$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$ | + | *Декартово соединение |
+ | **$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))$ | |
− | |||
− | Правило | ||
− | |||
− | Фильтрация осуществляется до проекции | ||
− | |||
− | $σ_{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 > b ∧ b = c ⇒ a > b ∧ b = c ∧ a > c$ | ||
+ | **$a > b ∧ b > c ⇒ a > b ∧ b > c ∧ a > c$ | ||
− | $σ_{P_1.p > P_2.p ∧ P_2.p ≥ 60 ∧ P_1.p > 60}(P_1 ⋈_{P_1.SId = P_2.SId} P_2) ⇒$ | + | *Пример |
+ | **$σ_{P_1.p > P_2.p ∧ P_2.p ≥ 60}(P_1 ⋈_{P_1.SId = P_2.SId} P_2) ⇒ σ_{P_1.p > P_2.p ∧ P_2.p ≥ 60 ∧ P_1.p > 60}(P_1 ⋈_{P_1.SId = P_2.SId} P_2) ⇒ σ_{P_1.p > P_2.p}(σ_{p > 60}(P_1) ⋈_{P_1.SId = P_2.SId} σ_{p ≥ 60}(P_2))$ | ||
− | + | ==== КНФ и ДНФ ==== | |
− | + | *Преобразование предикатов | |
+ | **Конъюнктивная нормальная форма | ||
+ | **Дизъюнктивная нормальная форма | ||
− | + | *Вычисление КНФ | |
− | + | **Слева направо, до первой лжи | |
− | + | *Вычисление ДНФ | |
− | + | **Слева направо, до первой истины | |
− | |||
− | |||
− | |||
− | Вычисление КНФ | ||
− | |||
− | Слева направо, до первой лжи | ||
− | |||
− | Вычисление ДНФ | ||
− | |||
− | Слева направо, до первой истины | ||
=== Семантические оптимизации === | === Семантические оптимизации === | ||
− | Семантическая оптимизация | + | ==== Семантическая оптимизация ==== |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | *Применение знания об ограничениях | |
+ | **Неэквивалентные запросы | ||
+ | **Тот же результат | ||
− | + | *Пример | |
+ | **$π_{FirstName}(Students ⋈ Groups) ⇒ π_{FirstName}(Students)$, если $Students.GId ⊂ Groups.GId$ | ||
− | + | ==== Пример оптимизации ==== | |
− | |||
− | $σ_{HasScolarship ∧ CId = 10}(Students ⋈ Points)$ | + | *Ограничение |
+ | **У всех, кто получает стипендию все оценки $≥ 60$ | ||
+ | **<pre class="prettyprint lang-sql">check not HasScolarship or 60 <= 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) | ||
+ | [[Категория: Базы данных]] |
Версия 15:47, 20 декабря 2021
В этом разделе будут рассмотрен этап обработки запросов, а именно перезапись запросов
Содержание
Обработка запроса
Мотивирующий пример
От выбора плана сильно зависит производительность
Пример базы данных:
- Students(SId, FirstName, LastName, GId, Year)
- $10^4$ записей
- Индексы: (SId) (кластеризованный), (GId)
- Groups(GId, Name)
- $10^3$ записей
- Индексы: (GId) (кластеризованный), (Name)
Запрос:
Фамилии студентов группы 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. Students(GId)
- $π_{Name}(S ⋈ σ_{Name=M34391}(G))$
- $10^3 + (3 + 20) + 20 ≈ 10^3$ операций
- План 5. Groups(Name), Students(GId)
- $π_{Name}(S ⋈ σ_{Name=M34391}(G))$
- $2 + (3 + 20) + 20 ≈ 45$ операций
Результат
$2·10^7$ операций — наиболее медленный план
$45$ операций — наиболее быстрый план
Обработка запроса
Перезапись и планировщик
- Перезапись запроса
- Статические правила оптимизации запроса
- Считается, что полезны всегда
- Планировщик запроса
- Оптимизация в зависимости от данных
- Перебор вариантов
Выбор структуры и метода
- Выбор структуры
- Преобразование запроса
- Порядок выполнения операций
- Порядок соединений
- Выбор метода исполнения
- Как исполняется каждая операция
Оценка плана
- Модель стоимости
- Стоимость операции
- Размер операндов
- Размер результата
- Оценка размера и распределения
- Статистика по данным
- Статистика предыдущих запросов
Перезапись запроса
Минимизация набора операций
Преобразование подзапросов
- Преобразуются в реляционную алгебру
- Запись в реляционном исчислении
- Вынос кванторов
- Преобразование в алгебру
Преобразование соединений
- Внешние соединения
- $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 > b ∧ b = c ⇒ a > b ∧ b = c ∧ a > c$
- $a > b ∧ b > c ⇒ a > b ∧ b > c ∧ a > c$
- Пример
- $σ_{P_1.p > P_2.p ∧ P_2.p ≥ 60}(P_1 ⋈_{P_1.SId = P_2.SId} P_2) ⇒ σ_{P_1.p > P_2.p ∧ P_2.p ≥ 60 ∧ P_1.p > 60}(P_1 ⋈_{P_1.SId = P_2.SId} P_2) ⇒ σ_{P_1.p > P_2.p}(σ_{p > 60}(P_1) ⋈_{P_1.SId = P_2.SId} σ_{p ≥ 60}(P_2))$
КНФ и ДНФ
- Преобразование предикатов
- Конъюнктивная нормальная форма
- Дизъюнктивная нормальная форма
- Вычисление КНФ
- Слева направо, до первой лжи
- Вычисление ДНФ
- Слева направо, до первой истины
Семантические оптимизации
Семантическая оптимизация
- Применение знания об ограничениях
- Неэквивалентные запросы
- Тот же результат
- Пример
- $π_{FirstName}(Students ⋈ Groups) ⇒ π_{FirstName}(Students)$, если $Students.GId ⊂ Groups.GId$
Пример оптимизации
- Ограничение
- У всех, кто получает стипендию все оценки $≥ 60$
check not HasScolarship or 60 <= all(select Points from Points where Points.SId = Id)
- Запрос
- Оценки стипендиатов группы M34391 по СУБД
select Points from Students natural join Points where HasScolarship and CId = 10 and GId = M34391
- $σ_{HasScolarship ∧ CId = 10}(Students ⋈ Points)$
- Оптимизированный запрос
- $σ_{GId=M34391 ∧ HasScolarship}(Students) ⋈ σ_{60 ≥ Points ∧ CId = 10}(Points)$
Литература
- Дейт К. Введение в системы баз данных (глава 18)