Главная » SQL, Базы данных » ОПТИМИЗАЦИЯ ЗАПРОСОВ

0

Рассмотрим четыре стадии процесса оптимизации запросов, который схематически представлен на рис. 18.1.

Рис. 18.1. Общая схема процесса оптимизации запроса

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

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

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

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

Перейдем к подробному рассмотрению каждой стадии процесса оптимизации.

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

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

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

Возникает очевидный вопрос: "Какое формальное представление должно  использоваться для внутреннего представления запроса?". Независимо от того, какой именно вариант формального представления будет выбран, он должен быть  достаточно полным, чтобы допускать представление любых запросов, которые  могут быть определены на внешнем языке запросов. Кроме того, выбранный  способ формального представления должен быть нейтральным, насколько это возможно, в том смысле, что он не должен заранее предопределять последующие  оптимизационные решения. Чаще всего для внутреннего представления запросов используется та или иная модификация  абстрактного синтаксического дерева, которое в этом случае называют деревом запроса. Например, на рис. 18.2 показано дерево для запроса, рассматривавшегося выше в этой же главе в разделе

18.2 ("Определить имена поставщиков детали с номером Р2").

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

Однако для наших целей удобнее всего предположить, что для внутреннего представления запросов используется один из тех формальных методов, с которыми мы уже знакомы: реляционная алгебра или реляционное исчисление. В этом случае дерево запроса, подобное представленному на рис. 18.2, можно рассматривать просто как альтернативный схематический вариант представления некоторого выражения, записанного в системе

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

( { SP JOIN S ) WHERE P# = Р# (‘Р2′) ) { SNAME }

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

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

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

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

1  Фактически некоторые коммерческие оптимизаторы SQL предназначены именно для преобразо вания подобного первоначального запроса в эквивалентное выражение реляционной алгебры.

2  Но следует заметить, что особенно восприимчивым к этой проблеме является язык SQL (см. упр. 8.12 в главе 8, а также [4.18]). Другие языки (например, языки реляционной алгебры или исчисления) обычно не предоставляют такое же количество способов создания эквивалентных выражений. Такая излишняя "гибкость" языка SQL на самом деле значительно усложняет жизнь разработчикам СУБД (не говоря уже о пользователях), поскольку осуществление функций оптимизатора становится намного сложнее.

(   A  JOIN  В   )   WHERE   ограничение,   распространяющееся на   А может быть преобразовано в эквивалентное, но более эффективное выражение

(  A WHERE   ограничение,  распространяющееся на   А   )   JOIN В

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

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

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

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

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

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

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

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

3  Безусловно, что в данном контексте понятие уровня является относительным! По сути,  упомянутые здесь операторы "низкого уровня" являются операторами реляционной алгебры  (соединение, ограничение и т.д.), а они обычно рассматриваются как операторы высокого уровня.

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

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

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

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

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

Источник: Дейт К. Дж., Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — 1328 с.: ил. — Парал. тит. англ.

По теме:

  • Комментарии