В современных системах реляционных баз
В современных системах реляционных баз данных обрабатываются сложные SQL-запросы, включающие представления, табличные выражения и подзапросы с агрегатными функциями. Такие запросы становятся все более важными в приложениях поддержки принятия решений (см., например, тестовый набор TPCD [TPCD94]). Метод перезаписи с использованием магических множеств (см., например, [BMSU86, RLK86, BR91, MFPR90, SS94]) был предложен как эвристическое преобразование для оптимизации таких запросов, и этот метод может приводить к серьезным улучшениям эффективности выполнения запросов [MFPR90]. Может быть много возможных вариантов этой перезаписи даже для одиночного запроса, основанных на решениях относительно распространений связываний. Некоторые из этих вариантов могут в действительности ухудшить эффективность. До данной работы не был продемонстрирован алгоритм эффективного выбора варианта в оценочном стиле. В этой статье устраняется важная преграда к внедрению перезаписи на основе магических множеств в коммерческие базы данных.
В статье анализируются два подхода к решению данной проблемы. Первый подход основывается на моделировании перезаписи на основе магических множеств как метода соединения, и он реализован в системе баз данных DB2 C/S V2. Второй подход представляет модель перезаписи на основе магических множеств, основанную на алгебраических преобразованиях. Оба подхода являются взаимнодополнительными и, взятые совместно, позволяют изучать соответствующие практические и теоретические вопросы.
Целью реализации является разработка алгоритма, в котором учитываются ограничения и требования полнофункциональной СУБД. Перезапись на основе магических множеств моделируется как специальный метод соединения, который может быть добавлен к любому существующему оценочному оптимизатору запросов. Выводятся оценочные формулы, позволяющие оптимизатору выбрать наилучший вариант перезаписи и определить, является ли он полезным. Исчерпывающий поиск среди всех вариантов сущетсвенно увеличивает сложность оптимизации запросов.
Чтобы сохранить порядок сложности процесса оптимизации к пространству поиска применяются разумные ограничения. Изучение производительности на основе реализации в DB2 C/S V2 демонстрирует низкие дополнительные накладные расходы и стабильность алгоритма при выполнении основанного на стоимости выбора, что приводит к существенному сокращению времени выполнения запросов. Существенно то, что результаты показывают, что для перезаписи на основе магических множеств требуется оценочный алгоритм (эффективность алгоритмов, основанных на эвристиках, изменяется при изменении статистики данных и оценок стоимости), и что предложенный оценочный алгоритм работает правильно.
Алгебраический подход к перезаписи на основе магических множеств базируется на правилах эквивалентности на мультимножественной реляционной алгебре, затрагивающих операцию ?-полусоединения. Алгебраический подход позволяет правильно определять пространство поиска и может использоваться в оптимизаторе, основанном на правилах (возможно, совместно с эвристиками для ограничения пространства поиска). Мы представляем характерный набор правил эквивалентности и показываем, как эти правила моделируют перезапись на основе магических множеств для не рекурсивных SQL-запросов.
Сначала мы мотивируем проблему с использованием примера.
View Definition
CREATE VIEW DepAvgSal AS (SELECT E.did, AVG(E.sal) AS avgsal FROM Emp E GROUPBY E.did);
Main Query Block
SELECT E.eid, E.sal FROM Emp E, Dept D, DepAvgSal V WHERE E.did = D.did AND E.did = V.did AND E.age < 30 AND D.budget > 100,000 AND E.sal > V.avgsal
Рис. 1. Исходный запрос
View Definitions
CREATE VIEW PartialResult AS (SELECT E.eid, E.sal, E.did FROM Emp E, Dept D WHERE E.did = D.did AND E.age < 30 AND D.budget > 100,000) CREATE VIEW Filter AS (SELECT DISTINCT P.did FROM PartialResult P ); CREATE VIEW LimitedDepAvgSal AS (SELECT F.did, AVG(E.sal) as avgsal FROM Filter F, Emp E WHERE E.did = F.did GROUPBY F.did);
Main Query Block
SELECT P.eid, P.sal FROM PartialResult P, LimitedDepAvgSal V WHERE P.did = V.did AND P.sal > V.avgsal
Рис. 2. Перезапись на основе магических множеств
