11.1. Процесс оптимизации запроса

Общая схема выполнения и оптимизации запроса представлена на

Исходный запрос

Рис. 9. Схема оптимизации запроса

Процесс можно разбить на следующие стадии:

1.Декомпозиция: преобразование запроса во внутреннюю форму.

2.Преобразование запроса в каноническую форму.

3.Выбор потенциальных низкоуровневых процедур.

4.Генерация различных вариантов планов вычисления запроса и выбор плана с минимальными затратами.

Вроли метаданных, хранимых в системном каталоге, выступают различные статистические данные, например:

• Метаданные о базовых отношений

–Кардинальность (количество кортежей)

–Количество занимаемых страниц во внешней памяти

•Метаданные об атрибутах базовых отношений

–Количество различных значений атрибута

–Наибольшие и наименьшие значения атрибута

–Наиболее часто и редко встречаемые значения атрибута

•Метаданные об индексах

–Признак, является ли индекс кластеризованным

–Количество листовых страниц в индексе

–Количество уровней индекса

Преобразование запроса во внутреннюю форму

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

Чаще всего для внутреннего представления запросов используется та или иная модификация син-

таксического дерева, которое в этом случае называют деревом запроса.

74

Для визуального представления деревьев запросов могут использоваться объектные графы и гра-

фы операций:

•В объектных графах узлы представляют объекы, такие как переменные (отношений) и константы. Дуги описывают предикаты, которым эти объекты должны удовлетворять. Объектные графы содержат свойства результатов запросов и поэтому тесно связаны с реляционным исчис-

лением.

•Графы операций описывают управляемые операциями потоки данных путем представления операций как узлов, связанных дугами, указывающими направление движения данных. Графы операций используются для представления выражений реляционной алгебры.

Например, для запроса реляционного исчисления

[<e.ename> OF

EACH e IN employees:

e.status = professor

AND

SOME p IN papers

(e.enr = p.enr AND p.year = 1981)]

и эквивалентного ему запросу реляционной алгебры

ename status professor employees 'enr enr year 1981ppapersq

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

Рис. 10. Графовое представление запросов

Преобразование запроса в каноническую форму

На этой стадии оптимизатор выполняет несколько операций оптимизации, которые гарантированно являются приемлемыми независимо от реальных значений данных и существующих путей доступа к ним.

Пусть Q — множество всех возможных запросов.

75

Определение 1. Запросы Q1; q2 P Q называются эквивалентными, если в результате их работы получается одно и то же отношение (с точностью до порядка кортежей и атрибутов, если он явно не задан в запросе).

Понятно, что введенное отношение на множестве Q является отношение эквивалентности в силу выполнения свойств рефлексивности, симметричности и транзитивности. А значит, множество Q можно разбить на классы эквивалентности, в каждом из которых находятся попарно эквивалентные запросы. Из каждого класса эквивалентности можно выбрать по одному самому оптимальному запросу из всех в данном классе, образовав тем самым множество C, которое назовем множеством канонических форм запросов. Таким образом, @q P Q найдется запрос p P C, которому эквивалентно q. Поэтому, чтобы доказать различные интересующие результаты, достаточно изучить менее мощное множество объектов C, а не более мощное множество Q.

Чтобы преобразовать результаты выполнения стадии 1 в некоторую эквивалентную, но более эффективную форму, оптимизатор использует определенные правила, или законы преобразования (основная цель — уменьшение количества обрабатываемых данных):

•Свойства арифметических операций

•Свойства логических операций

–можно строить КНФ для обычных (непредикатных) логических формул

–можно строить предваренную форму с матрицей в виде КНФ для предикатных формул

–применение различных логических свойств

–...

•Свойства реляционных операций.

–последовательные выборки заменяются одной (каскад выборок)

–аналогично с последовательными проекциями (каскад проекций)

–выборка из проекции заменяется на проекцию выборки

–выборка из соединения заменяется на соединение выборок

–использование распределительных законов, ассоциативности и коммутативности, законы поглощения

–...

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

Выбор потенциальных низкоуровневых процедур

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

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

76