Семантична оптимізація запитів СУБД
Семантична оптимізація запитів СУБД - процес валідації та перетворення синтаксичного дерева запиту в форму, яка придатна для подальших кроків оптимізації.
На цій стадії виконується:
- Перетворення запитів у канонічну форму;
- Розкриття уявлень;
- Перетворення підзапитів у сполуки;
- Спуск предикатів;
- Спрощення умов і розподіл предикатів;
- Перетворення дерева умов до шляхів вибірки.
Перетворення запитів до канонічної форми
Запити зводяться до канонічної форми, тобто переписуються так, щоб вони містили мінімальну кількість операторів SELECT (з'єднання-фільтрація-проекція). Скрізь, де можливо, запит повинен бути зведений до форми єдиного оператора SELECT. Це може дозволити наступним фазам оптимізації згенерувати значно ефективніший (на 2-3 порядки) план виконання для складних запитів.
Розкриття уявлень
Розкриття уявлень застосовується для того, щоб підсумковий запит містив посилання тільки на матеріалізовані відносини (таблиці) і можливості використовувати конвеєрну обробку даних.
| Початковий запит | Результат |
|---|---|
| ( T where cond1 ) where cond2 | T where ( cond1 and cond2) |
Перетворення підзапитів у сполуки
Перетворення підзапитів у сполуки є необхідним для застосування конвеєрної обробки даних та мінімізації обсягу результатів підзапитів, акумульованих у тимчасовій дисковій чи оперативній пам'яті.
| Початковий запит | Результат |
|---|---|
| select distinct T.a from T
where T.b in ( select T1.b from T1 where T1.c < T.c) |
select distinct T.a
from T,T1 where T.b = T1.b and T1.c < T.c |
Спуск предикатів
| Початковий запит | Результат |
|---|---|
| ( A join B) where condA and condB | (A where condA) join (B where condB) |
Спрощення умов та розподіл предикатів
Спрощення умов
Виконується шляхом перетворення дерева логічних операцій у КНФ та спрощення отриманої логічної функції.
Перетворення дерева логічних операцій у КНФ виконується наступним чином:
- 1. Для всіх диз'юнкцій, які входять у прямому вигляді, застосовується розподільний закон:
P OR (Q AND R) = (P OR Q) AND (P OR R) (P AND Q) OR R = (P OR R) AND (Q OR R)
- Для всіх диз'юнкцій, що входять у інверсному вигляді, застосовується правило де Моргана
NOT (P OR Q) = NOT P AND NOT Q
Перетворення триває рекурсивно до тих пір, поки дерево не буде складатися із кон'юнкцій конституент 0.
Отримана логічна функція знаходиться у кон’юнктивній нормальній формі, проте вона надлишкова. Для спрощення застосовують методи оптимізації логічних функцій, такі як Еспрессо (Логіка) або Куайна-Мак-Класкі.
Розподіл предикатів
Розподіл предикатів виконується
- Для всіх предикатів виду:
A.B pred C
Для яких існує предикат
A.B = D.E
Як результат - отримаємо предикат
D.B pred C
де C - константа; A, D - відношення; B, E - порівнювані атрибути. Це спрощення виконується на основі припущення, що початковий предикат A.B pred C може бути ефективнішим для відношення D.
- Для кожної умови об'єднання виду:
A.B pred D.E
генерується обернена умова
D.E inversed pred A.B
для можливості виконати з'єднання в оберненому порядку.
Перетворення дерева умов у шляху вибірки
Після спрощення дерева умов кожна кон'юнкція у дереві - це шлях вибірки. Предикати всередині кон'юнкцій групуються за належністю відносин. Для отримання підсумкового результату необхідно об'єднати результати кожного зі шляхів вибірки.
Література
- Дейт К. Дж. Введение в системы баз данных. 2001. Из-во: Вильямс. ISBN 5-8459-0138-3
- Конноли Т., Бегг К. Базы данных. Проектирование, реализация и сопровождение. Теория и практика. Из-во: Вильямс (М., 2003) ISBN 5-8459-0527-3
- Кимельман Михаил Леонидович. Исследование и разработка языковой подсистемы SQL сервера. Диссертация на соискание ученой степени кандидата физико-математических наук. Москва 1996