Этапы обработки запроса. Перезапись запросов

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

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

Мотивирующий пример

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

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

• 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$ операций — наиболее быстрый план

---

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

Планировщик запроса

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

По большому счету sql базы данных отличаются двумя вещами - то, как они поддерживают транзакции и то, насколько хорошо у них умеет работать планировщик запросов. Общий план:

• На вход приходит sql.
• Отправляем его в разборщик запросов(парсер). Он на выходе выдаст реляционную алгебру.
• Затем планировщик запроса снабжает операции реляционной алгебры информацией о том как он собирается их исполнять и в каком порядке.
• Реляционная алгебра передается в исполнитель запроса, который ее исполняет. Исполнитель запроса взаимодействует с источником данных в тот момент, когда ему понадобились данные для исполнения запросов.

Планировщики делятся на две части:

Перезапись и планировщик

Перезапись запроса. Составляет некоторый набор фиксированных правил, которые не зависят от конкретного запроса

• Перезапись запроса
  • Статические правила оптимизации запроса
  • СУДБ считает, что оптимизации полезны всегда. Если видит возможность применить правило, то применяет всегда.

Планировщик запроса. Занимается более интеллектуальными вещами, например выбор структуры, выбор методов исполнения. Он очень сильно зависит от модели оценки, которая позволяет ему достаточно точно оценивать объем результатов, которые он должен получить.

• Планировщик запроса
  • Принимает решение об оптимизации в зависимости от данных. Может посмотреть например на информацию из индексов.
  • В отличии от перезаписи запросов, когда у нас есть формальные правила что и когда нужно делать, планировщику часто приходится перебирать различные варианты исполнения

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

• При выборе структуры:
  • Планировщик преобразует запрос. Тут сильно помогают свойства реляционной алгебры, которые позволяют строить альтернативные эквивалентные варианты исполнения
  • Планировщик выбирает порядок выполнения операций
  • Планировщик выбирает порядок соединений

• Выбор метода исполнения
  • Для каждой операции планировщик решает каким конкретно способом операция должна быть исполнена

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

Оценка плана

Для оценки эффективности плана у планировщика есть модель стоимости

• Модель стоимости
  • Есть стоимость операции
  • Есть формулы, которые пересчитывают стоимость операций в зависимости от входных
  • Есть формулы, которые пересчитывают стоимость в зависимости от ожидаемых выходных данных

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

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

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

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

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

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

• Внешние соединения
  • $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)