Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 26)

Подсистема выполнения запросов реализует набор физических операций. На вход каждой операции поступают один или несколько потоков данных, и на выходе формируется поток данных. Примерами физических операций являются сортировка (внешняя), последовательное сканирование, индексное сканирование, соединение методом вложенных циклов и соединение сортировкой и слиянием. Эти операции называются физическими, поскольку они не обязательно связаны один к одному с реляционными операциями. Проще всего представлять физические операции как куски кода, которые используются в качестве строительных блоков для обеспечения возможности выполнения SQL-запросов. Абстрактным представлением такого выполнения является дерево физических операций, пример которого показан на рис. 1. Дуги в дереве операций представляют потоки данных между операциями. «Дерево физических операций» и «план выполнения» (или просто план) имеют одинаковый смысл. Подсистема выполнения отвечает за выполнение плана, что приводит к формированию ответов на запросы. Следовательно, возможности подсистемы выполнения запросов определяют структуру допустимых деревьев операций.

Рис. 1. Дерево операций.

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

• Алгебраическое представление данного запроса может быть преобразовано во многие другие логически эквивалентные алгебраические представления; например, Join (Join (A,B),C) = Join (Join (B,C),A)

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

Кроме того, пропускная способность, или время ответа системы при выполнении этих планов может весьма различаться. Поэтому верный выбор плана выполнения, производимый оптимизатором, имеет критическое значение. Таким образом, к оптимизации запросов можно относиться как к сложной поисковой проблеме. Для того чтобы решить эту проблему, нам требуется обеспечить:

• Пространство планов (пространство поиска).

• Метод оценки стоимости, чтобы можно было оценить каждый план в каждом пространстве поиска. Интуитивно, это оценка ресурсов, требуемых для выполнения плана.

• Алгоритм перебора, который может осуществлять поиск в пространстве планов выполнения.

Желаемым оптимизатором является такой, в котором
1) пространство поиска включает планы с низкой стоимостью;
2) метод оценок является точным;
3) алгоритм перебора эффективен.

Каждая из этих трех задача нетривиальна, и из-за этого построение хорошего оптимизатора является громадной работой.

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

1. Оптимизатор System R

Проект System R существенно улучшил состояние оптимизации запросов в реляционных системах. Идеи , внедренные во многие коммерческие оптимизаторы, продолжают оставаться удивительно современными. Представим здесь некоторые из этих важных идей в контексте запросов Select-Project-Join (SPJ). Класс SPJ-запросов тесно связан с конъюнктивными запросами, которые обычно изучаются в теории баз данных, и включает эти запросы.

Пространство поиска оптимизатора System R в контексте SPJ-запросов состоит из деревьев операций, которые соответствуют линейной последовательности операций соединения; например, последовательность Join (Join (Join (A, B), C), D) проиллюстрирована на рис. 2(a). Такие последовательности логически эквивалентны, поскольку соединения обладают свойствами ассоциативности и коммутативности. Для реализации операции соединения могут быть использованы методы вложенных циклов или сортировки и слияния. В каждом узле сканирования может использоваться индексное сканирование (на основе кластеризованного или некластеризованного индекса) или последовательное сканирование. Наконец, предикаты вычисляются как можно раньше.

Рис. 2. Линейное (a) и кустовое (b) соединения.

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

В оценочной модели механизмы (a)-(c) используются для вычисления для операций плана и связывания с этими операциями следующей информации (вычисление и связывание происходят в направлении от листьев к корню дерева):
1) размер выходного потока данных узла-операции;
2) любая упорядоченность кортежей, создаваемая или сохраняемая в выходном потоке данных узла-операции;
3) оценочная стоимость выполнения операции (и общая стоимость произведенного к этому моменту частичного плана).

Алгоритм перебора в оптимизаторе System R демонстрирует два важных метода: использование динамического программирования и использование интересных упорядочений.

Суть подхода динамического программирования основывается на предположении, что оценочная модель удовлетворяет принципам оптимальности. Более точно - предполагается, что для получения оптимального плана SPJ-запроса Q, состоящего из k соединений, достаточно рассматривать только оптимальные планы для подвыражений Q, которые состоят из (k-1) соединений, и расширять эти планы добавочным соединением. Другими словами, для определения оптимального плана выполнения Q не требуется рассматривать не самые оптимальные планы для подвыражений Q (называемых также подзапросами) с (k-1) соединениями. Соответственно, основанный на динамическом программировании алгоритм перебора представляет SPJ-запрос Q как множество соединяемых отношений { R1, ..., Rn }. Алгоритм перебора работает снизу вверх. В конце j-го шага алгоритм производит оптимальные планы для всех подзапросов размера j. Для получения оптимального плана для подзапроса, включающего (j+1) соединение, мы рассматриваем все возможные способы конструирования плана путем расширения планов, построенных на j-ом шаге. Например, оптимальный план для {R1, R2, R3, R4} получается выбором плана с наименьшей стоимостью из оптимальных планов для:

1) Join ( {R1, R2, R3}, R4} )
2) Join ( {R1, R2, R4}, R3} )
3) Join ( {R1, R3, R4}, R2} )
4) Join ( {R2, R3, R4}, R1} )

Остальные планы для {R1, R2, R3, R4} можно отбросить. Подход динамического программирования работает существенно быстрее, чем "наивный" перебор, поскольку требуется перебрать O(n2n-1) планов вместо O(n!).

Вторым важным аспектом оптимизатора System R является рассмотрение интересных упорядочений. Возьмем теперь запрос, представляющий соединение между {R1, R2, R3} с предикатами R1.a = R2.b = R3.c. Предположим, что стоимости планов для подзапроса {R1, R2} оценены в x и y для методов вложенных циклов и сортировки и слияния соответственно, причем x < y. В таком случае при рассмотрении плана для {R1, R2, R3} мы не принимаем во внимание план, согласно которому R1 и R2 соединяются методом сортировки и слияния. Однако заметим, что если для соединения R1 и R2 используется метод сортировки и слияния, то результат соединения упорядочен по a. Этот порядок сортировки может существенно уменьшить стоимость соединения с R3. Следовательно, отбрасывание плана, включающего соединение сортировкой и слиянием R1 и R2, может привести к неоптимальности глобального плана. Проблема возникает по той причине, что в выходном потоке результата соединения R1 и R2 имеется упорядоченность кортежей, которая полезна для последующего соединения. Однако соединение методом вложенных циклов не обеспечивает такого упорядочения. Поэтому для заданного запроса System R определяет порядок кортежей, который потенциально важен для планов выполнения запроса (отсюда название "интересные упорядочения"). К тому же в оптимизаторе System R два плана являются сравнимыми только в том случае, когда они представляют одно и то же выражение и, кроме того, обеспечивают одно и то же интересное упорядочение. Идея интересных упорядочений позже была обобщена до идеи физических свойств и интенсивно используется в современных оптимизаторах. На интуитивном уровне физическое свойство - это любая характеристика плана, не являющаяся общей для всех планов одного и того же выражения, но могущая влиять на последующие операции. Наконец, заметим, что подход System R принятия во внимание физических свойств демонстрирует простой механизм управления любым отклонением от принципа оптимальности, не обязательно связанным с физическими свойствами.

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

2. Пространство поиска

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

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

Рис. 3. Дерево запроса.

2.1 Коммутативность операций

2.1.1 Обобщение последовательности соединений

Во многих системах последовательность операций соединения синтаксически ограничивается для ограничения размеров пространства поиска. Например, в проекте System R рассматриваются только линейные последовательности операций соединения, и декартово произведение отношений вычисляется только после всех соединений.

Поскольку операции соединения коммутативны, последовательность соединений в дереве операций не обязательно должна быть линейной. В частности, запрос, состоящий в соединении отношений R1, R2, R3, R4, может быть алгебраически представлен и вычислен как Join ( Join (A,B), Join (C,D) ). Соответствующие деревья операций (и запросов) называются кустовыми, пример такого дерева приведен на рис. 2(b). Кустовые последовательности соединений требуют реализации промежуточных отношений. Хотя кустовые деревья могут привести к более дешевому плану выполнения запроса, они значительно увеличивают расходы на перебор пространства поиска. (Наиболее велика не стоимость генерации синтаксических порядков соединений. Интенсивные вычисления требуются для выбора физических операций и оценки стоимости каждого возможного плана.) При наличии некоторых исследований достоинств использования кустовых последовательностей соединений, до сих пор в большинстве систем используются линейные последовательности соединений и только ограниченные подмножества кустовых деревьев соединения.

Характеристики

Список файлов домашнего задания