Окончательный результат

Проекция по атрибуту SNAME

Выборка кортежей, в которых Р = Р2

Соединение по атрибуту S

SP S

Рис. 17.2. Дерево реализации запроса Определить имена поставщиков детали с номером Р2

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

( ( SP JOIN S ) WHERE PI = Р( Р2 ) ) { SNAME }

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

На этой стадии оптимизатор выполняет несколько операций оптимизации, которые гарантированно являются хорошими независимо от реальных значений данных и существующих путей доступа к ним. Суть в том, что обычно реляционные языки позволяют сформулировать любые запросы (за исключением разве что простейших) несколькими разными (по крайней мере, внешне) способами. Например, даже простой запрос Определить имена поставщиков детали с номером Р2 на языке SQL может быть записан буквально десятками способов, не считая таких тривиальных вариантов, как замена А = В на В = А или р AND q на q AND p. Производительность вычисления запроса не должна зависеть от формы записи запроса, которую выбрал пользователь. Поэтому следующий этап в обработке запроса - преобразование его внутреннего представления в некоторую эквивалентную каноническую форму (см. ниже). Назначением данного преобразования является исключение внешних различий в эквивалентных представлениях запроса и, что более важно, поиск представления запроса, в некотором смысле более эффективного по сравнению с исходным представлением.

Следует заметить, что язык SOL исключительно предрасположен к этому (см. упр. 7.12 в главе 7, а также [4.18]). Другие языки (например, языки реляционной алгебры или исчисления) обычно не позволяют создать такое .же количество эквивалентных по результату выражений. Эта излишняя гибкость языка SQL на самом деле усложняет жизнь разработчикам (а не пользователям), поскольку существенно усложняет алгоритм оптимизатора.

Замечание о канонической форме. Понятие канонической формы является центральным во многих разделах математики и связанных с ней дисциплинах. Каноническая форма может быть определена следующим образом. Пусть Q - множество объектов (запросов), и пусть существует понятие об их эквивалентности (а именно: запросы ql и q2 эквивалентны тогда и только тогда, когда дают идентичные результаты). Тогда подмножество С множества Q является подмножеством канонических форм для запросов из множества Q в смысле определенной выще эквивалентности тогда и только тогда, когда каждому объекту q из множества Q соответствует только один объект с из множества С. В этом случае говорят, что объект с является канонической формой объекта q. Все интересующие свойства, которыми обладает объект q, также присущи объекту с. Поэтому, чтобы доказать различные интересующие результаты, достаточно изучить менее мощное множество объектов С, а не более мощное множество Q.

Вернемся к основной теме обсуждения. Чтобы преобразовать результаты выполнения стадии 1 в некоторую эквивалентную, но более эффективную форму, оптимизатор использует определенные и хорошо известные правила преобразования, или законы. Ниже приведен пример такого правила. Здесь выражение

( А JOIN В ) WHERE <выборка из> А

может быть преобразовано в эквивалентное, но более эффективное выражение ( А WHERE <выборка из> А ) JOIN В

Подобное преобразование кратко рассматривалось в разделе 6.6. Кроме того, оно было приведено несколько выше, при обсуждении примера в разделе 17.2, который ясно продемонстрировал, зачем нужны подобные преобразования. Многие другие правила преобразования описываются ниже, в разделе 17.4.

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

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

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

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

ключа; на основе индексированного атрибута, по которому выполняется выборка; на основе хешированного атрибута и т.д. Примеры таких процедур приведены ниже, в разделе 17.7 (см. также [17.8H17.14]).

С каждой процедурой связана и параметризованная формула стоимости, позволяющая оценить стоимость выполнения процедуры (т.е. уровень затрат, требуемых для ее выполнения). Чаще всего стоимость определяется на основе подсчета количества необходимых дисковых операций ввода-вывода, но некоторые системы учитывают также время использования процессора и другие факторы. Эти формулы стоимости применяются на стадии 4. В [17.8]-[17.14] обсуждаются и анализируются формулы стоимости для различных процедур реализации при разных исходных предположениях.

Далее, используя сохраняемую в каталоге информацию о состоянии базы данных (существующие индексы, текущую кардинальность переменных-отношений и т.п.) и сведения о взаимозависимостях, упоминавшихся выше, оптимизатор выбирает одну или несколько процедур-кандидатов для каждой низкоуровневой операции в запросе. Этот процесс обычно называют выбором пути доступа (см. также [17.34], [17.35]).

Замечание. Следует отметить, что в [17.34], [17.35] приведенный термин используется для ссылки на определенные в данной главе стадии 3 и 4, а не только на стадию 3. Действительно, на практике очень трудно разграничить, где заканчивается одна стадия и начинается другая: просто стадия 3 плавно переходит в стадию 4.

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

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

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