Семантична оптимізація запитів СУБД - процес валідації та перетворення синтаксичного дерева запиту в форму, яка придатна для подальших кроків оптимізації.
На цій стадії виконується: Перетворення запитів у канонічну форму; Розкриття уявлень; Перетворення підзапитів у сполуки; Спуск предикатів; Спрощення умов і розподіл предикатів; Перетворення дерева умов до шляхів вибірки.
Перетворення запитів до канонічної форми Запити зводяться до канонічної форми, тобто переписуються так, щоб вони містили мінімальну кількість операторів 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
Див. також План запиту