Семантична оптимізація запитів СУБД

Семантична оптимізація запитів СУБД - процес валідації та перетворення синтаксичного дерева запиту в форму, яка придатна для подальших кроків оптимізації.

На цій стадії виконується:

1. Перетворення запитів у канонічну форму;
   1. Розкриття уявлень;
   2. Перетворення підзапитів у сполуки;
   3. Спуск предикатів;
2. Спрощення умов і розподіл предикатів;
3. Перетворення дерева умов до шляхів вибірки. 

Перетворення запитів до канонічної форми

Запити зводяться до канонічної форми, тобто переписуються так, щоб вони містили мінімальну кількість операторів 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. 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)

1. Для всіх диз'юнкцій, що входять у інверсному вигляді, застосовується правило де Моргана
   

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

Див. також

• План запиту