Семантическая оптимизация запросов СУБД — процесс валидации и преобразования синтаксического дерева запроса в форму, пригодную для дальнейших шагов оптимизации.
На этой стадии выполняется: Преобразование запросов в каноническую форму; Раскрытие представлений; Преобразование подзапросов в соединения; Спуск предикатов Упрощение условий и распределение предикатов; Преобразование дерева условий в пути выборки.
Преобразование запросов в каноническую форму Запросы приводятся в каноническую форму, то есть переписываются так, чтобы они содержали минимальное количество операторов SELECT (соединение-фильтрация-проекция). Везде, где возможно, запрос должен быть приведен к форме единственного оператора SELECT. Это может позволить последующим фазам оптимизации сгенерировать значительно более эффективный (на 2-3 порядка) план выполнения для сложных запросов.
Раскрытие представлений Раскрытие представлений применяется для того, чтобы итоговый запрос содержал ссылки только на материализованные отношения (таблицы) и было возможным использовать конвейерную обработку данных.
+Исходный запросРезультат select a from V where cond2 где V as select a, b from T where cond1 select a from 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)+
Упрощение условий и распределение предикатов
Упрощение условий Выполняется путём преобразования дерева логических операций в КНФ и упрощения полученной логической функции.
Преобразования дерева логических операций в КНФ выполняется следующим образом: Для всех дизъюнкций, входящих в прямом виде, применяется распределительный закон: 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
Категория:СУБД