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

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

На этой стадии выполняется:
 Преобразование запросов в каноническую форму;
 Раскрытие представлений;
 Преобразование подзапросов в соединения;
 Спуск предикатов
 Упрощение условий и распределение предикатов;
 Преобразование дерева условий в пути выборки.

Преобразование запросов в каноническую форму 
Запросы приводятся в каноническую форму, то есть переписываются так, чтобы они содержали минимальное количество операторов SELECT (соединение-фильтрация-проекция). Везде, где возможно, запрос должен быть приведен к форме единственного оператора SELECT. Это может позволить последующим фазам оптимизации сгенерировать значительно более эффективный (на 2-3 порядка) план выполнения для сложных запросов.

Раскрытие представлений 
Раскрытие представлений применяется для того, чтобы итоговый запрос содержал ссылки только на материализованные отношения (таблицы) и было возможным использовать конвейерную обработку данных.

Преобразование подзапросов в соединения 
Преобразование подзапросов в соединения необходимо для применения конвейерной обработки данных и минимизации объема результатов подзапросов, аккумулируемых во временной дисковой или в оперативной памяти.

Спуск предикатов

Упрощение условий и распределение предикатов

Упрощение условий 
Выполняется путём преобразования дерева логических операций в КНФ и упрощения полученной логической функции.

Преобразования дерева логических операций в КНФ выполняется следующим образом:
 Для всех дизъюнкций, входящих в прямом виде, применяется распределительный закон:
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

СУБД