Этапы обработки запроса. Перезапись запросов — различия между версиями
Fadeev (обсуждение | вклад) (→Алгебраические свойства операций) |
Fadeev (обсуждение | вклад) (→Коммутативность операций) |
||
(не показано 25 промежуточных версий этого же участника) | |||
Строка 2: | Строка 2: | ||
== Обработка запроса == | == Обработка запроса == | ||
− | |||
− | |||
=== Мотивирующий пример === | === Мотивирующий пример === | ||
− | + | От выбора плана '''сильно''' зависит производительность | |
− | + | ==== Пример базы данных: ==== | |
*<var>Students(SId, FirstName, LastName, GId, Year)</var> | *<var>Students(SId, FirstName, LastName, GId, Year)</var> | ||
Строка 16: | Строка 14: | ||
** Индексы: <var>(GId)</var> (кластеризованный), <var>(Name)</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 | * План 1 | ||
Строка 38: | Строка 35: | ||
** $10^3 + 10^4 + 20 ≈ 10^4$ операций | ** $10^3 + 10^4 + 20 ≈ 10^4$ операций | ||
− | Планы запросов с индексами | + | ==== Планы запросов с индексами ==== |
* План 4. <var>Students(GId)</var> | * План 4. <var>Students(GId)</var> | ||
Строка 48: | Строка 45: | ||
** $2 + (3 + 20) + 20 ≈ 45$ операций | ** $2 + (3 + 20) + 20 ≈ 45$ операций | ||
− | + | ==== Результат ==== | |
+ | |||
+ | $2·10^7$ операций — наиболее '''медленный''' план | ||
− | + | $45$ операций — наиболее '''быстрый''' план | |
− | + | ---- | |
+ | [[Файл:Structure_Query.png|430px|thumb|right|Обработка запроса]] | ||
+ | [[Файл:Structure_Planner.png|430px|thumb|right|Планировщик запроса]] | ||
=== Обработка запроса === | === Обработка запроса === | ||
− | Перезапись и планировщик | + | ==== Перезапись и планировщик ==== |
*Перезапись запроса | *Перезапись запроса | ||
** Статические правила оптимизации запроса | ** Статические правила оптимизации запроса | ||
Строка 65: | Строка 66: | ||
** Перебор вариантов | ** Перебор вариантов | ||
− | Выбор структуры и метода | + | ==== Выбор структуры и метода ==== |
*Выбор структуры | *Выбор структуры | ||
Строка 75: | Строка 76: | ||
** Как исполняется каждая операция | ** Как исполняется каждая операция | ||
− | Оценка плана | + | ==== Оценка плана ==== |
*Модель стоимости | *Модель стоимости | ||
Строка 90: | Строка 91: | ||
=== Минимизация набора операций === | === Минимизация набора операций === | ||
− | Преобразование подзапросов | + | ==== Преобразование подзапросов ==== |
* Преобразуются в реляционную алгебру | * Преобразуются в реляционную алгебру | ||
Строка 97: | Строка 98: | ||
** Преобразование в алгебру | ** Преобразование в алгебру | ||
− | Преобразование соединений | + | ==== Преобразование соединений ==== |
*Внешние соединения | *Внешние соединения | ||
Строка 109: | Строка 110: | ||
=== Унарные операции === | === Унарные операции === | ||
− | Повторная фильтрация | + | ==== Повторная фильтрация ==== |
*Правило | *Правило | ||
Строка 118: | Строка 119: | ||
**$π_{FirstName}(σ_{Name=M34391}(σ_{S.GId=G.GId}(S × G))) ⇒ π_{FirstName}(σ_{Name=M34391 ∧ S.GId=G.GId}(S × G))$ | **$π_{FirstName}(σ_{Name=M34391}(σ_{S.GId=G.GId}(S × G))) ⇒ π_{FirstName}(σ_{Name=M34391 ∧ S.GId=G.GId}(S × G))$ | ||
− | + | ==== Повторная проекция ==== | |
− | Повторная проекция | ||
*Правило | *Правило | ||
Строка 128: | Строка 128: | ||
**$π_{FirstName}(π_{FirstName, Name}(S × G)) ⇒ π_{FirstName}(S × G)$ | **$π_{FirstName}(π_{FirstName, Name}(S × G)) ⇒ π_{FirstName}(S × G)$ | ||
− | Проекция и фильтрация | + | ==== Проекция и фильтрация ==== |
*Правило | *Правило | ||
Строка 135: | Строка 135: | ||
*Пример | *Пример | ||
− | ** $π_{FirstName}(σ_{Name=M34391}(π_{FirstName, Name}(S × G))) ⇒ | + | ** $π_{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 ∪ R_2) ⇒ σ_{cond}(R_1) ∪ σ_{cond}(R_2)$ |
− | **$σ_{cond}(R_1 \cap R_2) ⇒ σ_{cond}(R_1) \cap σ_{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}(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)$ | + | ** $σ_{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(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))$ | + | ** $π_{A}(R_1 ⋈ R_2) ⇒ π_A(π_{(A ∪ R_2) ∩ R_1}(R_1) ⋈ π_{(A ∪ R_1) ∩ R_2}(R_2))$ |
− | Коммутативность операций | + | ==== Коммутативность операций ==== |
*Коммутативные операции | *Коммутативные операции | ||
− | + | **$⋈$ | |
− | **$⋈$ | + | **$∪$ |
− | **$∪$ | ||
**$∩$ | **$∩$ | ||
Строка 170: | Строка 167: | ||
**Выбор левой и правой стороны для несимметричных методов исполнения | **Выбор левой и правой стороны для несимметричных методов исполнения | ||
− | Ассоциативность операций | + | ==== Ассоциативность операций ==== |
*Ассоциативные операции | *Ассоциативные операции | ||
− | **$⋈$ | + | **$⋈$ |
− | **$∪$ | + | **$∪$ |
**$∩$ | **$∩$ | ||
Строка 186: | Строка 183: | ||
=== Обработка условий === | === Обработка условий === | ||
− | Замыкание предикатов | + | ==== Замыкание предикатов ==== |
*Примеры правил | *Примеры правил | ||
Строка 194: | Строка 191: | ||
*Пример | *Пример | ||
− | **$σ_{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_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))$ |
− | |||
− | |||
− | КНФ и ДНФ | + | ==== КНФ и ДНФ ==== |
*Преобразование предикатов | *Преобразование предикатов | ||
Строка 211: | Строка 206: | ||
=== Семантические оптимизации === | === Семантические оптимизации === | ||
− | Семантическая оптимизация | + | ==== Семантическая оптимизация ==== |
*Применение знания об ограничениях | *Применение знания об ограничениях | ||
Строка 220: | Строка 215: | ||
**$π_{FirstName}(Students ⋈ Groups) ⇒ π_{FirstName}(Students)$, если $Students.GId ⊂ Groups.GId$ | **$π_{FirstName}(Students ⋈ Groups) ⇒ π_{FirstName}(Students)$, если $Students.GId ⊂ Groups.GId$ | ||
− | Пример оптимизации | + | ==== Пример оптимизации ==== |
*Ограничение | *Ограничение | ||
Строка 231: | Строка 226: | ||
*Оптимизированный запрос | *Оптимизированный запрос | ||
− | **$σ_{GId=M34391 ∧ HasScolarship}(Students) | + | **$σ_{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)