Методы оптимизации выполнения запросов в реляционных СУБД


Логическая оптимизация запросов - часть 13


3c) Уничтожим в этом блоке ключевые слова SELECT и FROM.

3d) Включим Rt3 в список раздела FROM внешнего запроса.

В результате работы этого алгоритма запрос будет преобразован к канонической форме

SELECT R1.C1 FROM R1, Rt3 WHERE R1.Cm+1 = Rt3.Cm+1 AND ... AND R1.Cn = Rt3.Cn.

Ким в [57] обосновывает разумность произведения таких преобразований тем, что оптимизатор получает возможность выбора большего числа способов выполнения запросов. Показано, что достаточно часто открывающиеся после преобразований способы выполнения являются более эффективными в соответствии с оценками планов выполнения запросов, применяемыми в System R, чем планы, используемые в традиционном оптимизаторе этой системы. Приводится обобщенный алгоритм преобразования, пригодный для обработки запроса общего вида.

Естественно, что при использовании в оптимизаторе запросов подобного подхода совсем не обязательно производить формальные преобразования запросов. Основная идея в том, чтобы оптимизатор в большей степени использовал семантику обрабатываемого запроса, а каким образом она будет распознаваться это уже вопрос применяемой техники. Исправления и уточнения подхода Кима, содержащиеся в [65], и касаются главным образом более корректной семантики запросов, выразимых на языке SQL. По ходу изложения подхода Кима мы уже отмечали некоторые семантические некорректности. Для их исправления в [65] преобразования описываются в терминах расширенной реляционной алгебры, более точно соответствующей специфике SQL.

Наряду с базовыми операторами расширенная реляционная алгебра включает оператор проецирования, не устраняющий дубликаты кортежей в результирующем отношении (обычный для реляционной алгебры оператор проецирования, устраняющий дубликаты, называется в [65] оператором дельта-проецирования). Введены также следующие операции: Полусоединение отношений R и S по предикату J (Semijoin (R,S;J)) определяется как подмножество кортежей r, принадлежащих R, для каждого из которых существует кортеж s, принадлежащий S, такой, что предикат J(r,s) - истинен.


Начало  Назад  Вперед