С начала 70-х была выполнена значительная работа в области оптимизации запросов. В короткой статье трудно охватить всю эту большую работу вширь и вглубь. Поэтому я решил сосредоточиться прежде всего на оптимизации SQL-запросов в реляционных системах баз данных и представить свое пристрастное и неполное видение этой области. Целью данной статьи не является представление исчерпывающего обзора, а скорее объяснение основ и демонстрация образцов значительных работ в этой области. Я хотел бы принести извинения многим людям, внесшим свой вклад в оптимизацию запросов, которых явно не упоминаю по своему недосмотру или из-за недостатка места. В обзоре для простоты изложения опущены технические детали.

Введение

Реляционные языки запросов обеспечивают высокоуровневый «декларативный» интерфейс для доступа к данным, хранимым в реляционных базах данных. Со временем появился язык SQL [41] как стандарт реляционных языков запросов. Двумя ключевыми подкомпонентами компонента вычисления запросов в SQL-ориентированной системе баз данных являются оптимизатор запросов и подсистема выполнения запросов.

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

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

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

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

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

Мы начинаем с обсуждения подхода к оптимизации в System R, поскольку это был необыкновенно элегантный подход, который питал многие последующие работы в области оптимизации. В разделе 4 мы обсудим, что представляет собой пространство поиска, анализируемое оптимизатором. В этом разделе представлены алгебраические преобразования, включаемые в пространство поиска. Раздел 5 посвящается проблеме оценки стоимости. В разделе 6 мы сосредоточимся на теме перебора пространства поиска. Это завершает обсуждение базовых основ оптимизации. В разделе 7 мы обсудим некоторые современные разработки в области оптимизации запросов.

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

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

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

Стоимостная модель присваивает оценочную стоимость любому частичному или полному плану в пространстве поиска. Она также определяет оценочный размер потока данных для вывода каждой операции плана. Эти оценки базируются на следующем:

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} получается выбором плана с наименьшей стоимостью из оптимальных планов для:

Остальные планы для {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 два плана являются сравнимыми только в том случае, когда они представляют одно и то же выражение и, кроме того, обеспечивают одно и то же интересное упорядочение. Идея интересных упорядочений позже была обобщена до идеи физических свойств [22] и интенсивно используется в современных оптимизаторах. На интуитивном уровне физическое свойство - это любая характеристика плана, не являющаяся общей для всех планов одного и того же выражения, но могущая влиять на последующие операции. Наконец, заметим, что подход System R принятия во внимание физических свойств демонстрирует простой механизм управления любым отклонением от принципа оптимальности, не обязательно связанным с физическими свойствами.

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

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

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

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

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

Большой и важный класс преобразований основан на коммутативности операций. В этом подразделе мы рассмотрим примеры таких преобразований.

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

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

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

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

В расширяемых системах поведение компонента перебора соединений может адаптироваться к конкретному запросу, ограничивая «кустистость» деревьев соединений или разрешая/запрещая вычисление декартовых произведений [46]. Однако нетривиально заранее определить воздействие такой настройки на качество и стоимость поиска.

2.1.2 Внешние и обычные соединения

Одностороннее внешнее соединение - это несимметричная операция языка SQL, которая сохраняет все кортежи одного из отношений-операндов. Симметричное внешнее соединение сохраняет кортежи обоих отношений-операндов. Например, (R LOJ S), где LOJ обозначает левое внешнее соединение R и S, сохраняет все кортежи R. В результирующем отношении этой операции, кроме кортежей, получаемых при естественном соединении, содержатся все кортежи R, которые не удалось соединить с S (заполненные неопределенными значениями для всех атрибутов S). В отличие от естественных соединений последовательность внешних и обычных соединений нельзя произвольно изменять. Однако если имеются предикат обычного соединения между R и S и предикат внешнего соединения между S и T, то действует следующее тождество:
Join (R, S LOJ T) = Join (R,S) LOJ T

Если продолжать применять это правило ассоциативности, мы получим эквивалентное выражение, в котором вычисление «блока обычных соединений» предшествует «блоку внешних соединений». Впоследствии обычные соединения могут произвольно переупорядочиваться. Как и другие преобразования, это тождество следует применять на основе оценок. Тождества, приведенные в [53], определяют класс запросов, в которых можно изменять порядок обычных и внешних соединений.

2.1.3 Группировки и соединения

При традиционном выполнении SPJ-запроса с группировкой вычисление SPJ-компонента запроса предшествует группировке. Набор преобразований, описываемых в этом подразделе, делает возможным выполнять операцию группировки до соединения. Эти преобразования применимы к запросам с SELECT DISTINCT, так что это специальный случай группировки. Выполнение операции GROUP BY потенциально может привести к значительному сокращению числа кортежей, поскольку для каждого раздела отношения, выделяемого операцией группировки, она генерирует только один кортеж. Поэтому в некоторых случаях при выполнении сначала группировки стоимость соединения может быть существенно уменьшена. Более того, при наличии подходящего индекса операция группирования может быть выполнена недорого. Для случая, когда операцию группирования можно выполнить после соединения, существуют двойники таких преобразований. Эти преобразования описаны в [5, 60, 25, 6] (см. обзор в [4]).

В этом подразделе мы кратко обсудим конкретные случаи, в которых применимы преобразования, вызывающие выполнение группировки до соединения. Рассмотрим дерево запроса на рис. 4(a). Пусть R1 и R2 соединяются по внешнему ключу, столбцы агрегирования G все взяты из R1, а в состав набора столбцов группировки входит внешний ключ R1. Для такого запроса рассмотрим соответствующее дерево операций на рис. 4(b), где G1 = G. В этом дереве завершающее соединение может только сократить набор потенциальных разделов R1, созданных G1, но не может повлиять на разделы и на агрегаты, вычисляемые G1 на этих разделах, поскольку каждый кортеж R1 соединяется не более чем с одним кортежем R2. Следовательно, мы можем протолкнуть группировку вниз, как показано на рис. 4(b), и сохранить эквивалентность для произвольных агрегатных функций без побочного эффекта. На рис. 4(c) иллюстрируется пример, где преобразование вводит группировку, и представляется класс полезных примеров, где операция группировки выполняется поэтапно. Например, предположим, что в запросе, дерево операций которого показано на рис. 4(a), агрегатные функции вычисляются только на столбцах R1. В этих случаях введенный оператор группировки G1 разделяет отношение по столбцам R1 и вычисляет агрегатные функции на этих разделах. Однако на рис. 4(a) могут потребоваться истинные разделы, чтобы объединить несколько разделов, образованных G1, в один раздел (отображение много-к-одному). Это обеспечивает оператор группирования G. Такое поэтапное вычисление может быть полезным для уменьшения стоимости соединения по причине сокращения объема данных операцией группировки G1. Для возможности такой поэтапной агрегации требуется, чтобы агрегатные функции обладали тем свойством, что Agg (S U S") можно вычислить на основе AGG (S) и AGG(S"). Например, чтобы вычислить общий объем продаж для всех продуктов каждого отделения, мы можем использовать преобразование с рис. 4(c) для выполнения ранней агрегации и получения общего объема продаж для каждого продукта. Затем нам потребуется еще одна группировка, чтобы сложить объемы продаж всех продуктов, относящихся к одному отделению.

2.2 Сведение запросов с несколькими блоками к одноблочным запросам

Описанная в этом подразделе техника в некоторых случаях позволяет сжать SQL-запрос с несколькими блоками в одноблочный запрос.

2.2.1 Слияние представлений

Рассмотрим конъюнктивный запрос с SELECT ANY. Если одно или несколько отношений, к которым адресуется запрос, являются представлениями, но каждое из них определено через конъюнктивный запрос, то определения представлений могут быть просто «раскрыты» для получения одноблочного SQL-запроса. Например, если запрос выглядит как Q = Join (R, V), а представление V определено как V = Join (S, T), то запрос Q может быть раскрыт в Join (R, Join (S,T) ), и его можно свободно переупорядочить. Для выполнения такого шага может потребоваться некоторое переименование переменных в определении представления.

К сожалению, это простое раскрытие не работает, когда представления более сложны, чем SPJ-запросы. Если одно или несколько представлений содержат SELECT DISTINCT, преобразования, перемещающие или поднимающие DISTINCT, нужно производить очень осторожно, чтобы корректно сохранить число дубликатов [49]. В более общем случае, когда представление содержит операцию группировки, для раскрытия требуется возможность поднятия операции группировки и затем свободного переупорядочения не только соединений, но и операции группировки для достижения оптимальности. Например, нам задается запрос типа того, который показан на рис. 4(b), и мы стараемся понять, как преобразовать его к форме рис. 4(a), чтобы R1 и R2 можно было свободно переупорядочивать. Хотя в этом случае могут использоваться преобразования из подраздела 4.1.3, это только подчеркивает сложность проблемы [6].

2.2.2 Слияние вложенных подзапросов

Рассмотрим следующий пример запроса с вложенными подзапросами из [13], где Emp# и Dept# - ключи соответствующих отношений.

Если для ответа на запрос используется семантика последовательного просмотра кортежей, то внутренний запрос вычисляется один раз для каждого кортежа отношения Emp. Очевидная оптимизация применима в том случае, когда внутренний блок запроса не содержит переменных из внешнего блока запроса (отсутствует корреляция). В таких случаях внутренний запрос требуется вычислить только один раз. Если во внутреннем блоке присутствует переменная из внешнего блока, мы говорим, что блоки запроса коррелируют. Например, в приведенном выше запросе Emp.Emp# действует как корреляционная переменная. Ким [35] и впоследствии другие исследователи [16, 13, 44] выявили методы устранения вложенности в SQL-запросе с корреляцией и «уплощения» его до запроса с одним блоком. Например, приведенный запрос со вложенностью приводится к
SELECT E.Name FROM Emp.E, Dept D WHERE E.Dept# = D.Dept# AND D.Loc = "Denver" AND E.Emp# = D.Mgr

Дайал [13] был первым, кто предложил алгебраическую трактовку устранения вложенности. Сложность проблемы зависит от структуры вложенности, т. е. от того, содержит ли вложенный запрос кванторы (например, ALL, EXISTS) и агрегаты. В простейшем случае, примером которого является приведенный выше пример, семантика перебора кортежей может моделироваться конструкцией Semijoin (Emp, Dept, Emp.Dept # = Dept.Dept#)(Semijoin (A,B,P) обозначает полусоединение A и B, сохраняющее атрибуты A; P - предикат полусоединения.). Опираясь на этот подход, нетрудно заметить, почему может быть произведено слияние запроса, поскольку:

Здесь предикатом соединения для Join (Emp, Dept) является Emp.Dept# = Dept.Dept#. Второй операнд операции Project (Я предполагаю, что эта операция не устраняет дубликаты.) означает, что должны быть оставлены все столбцы отношения Emp.

Проблема становится гораздо более сложной, когда во вложенном подзапросе присутствуют агрегаты, поскольку теперь для слияния блоков требуется вытягивание наверх агрегации без нарушения семантики запроса со вложенными подзапросами. Эту дополнительную сложность иллюстрирует приводимый ниже пример из [44]:

Особенно сложно сохранить дубликаты и неопределенные отношения. Чтобы оценить эти тонкости, обратите внимание, что если для конкретного значения Dept.name (скажем, d) отсутствуют кортежи с совпадающим значением Emp.Dept_name, т. е. если значением предиката Dept.name = Emp.Dept_name является false для всех кортежей Emp, то кортеж отношения Dept со значением d войдет в результат запроса. Однако, если мы применим преобразование, использованное в первой части этого подраздела, то для dept d в результате запроса кортеж не появится, поскольку предикат соединения примет значение false. Поэтому при наличии агрегации мы должны сохранять все кортежи внутреннего блока запроса, используя левое внешнее соединение. В частности, приведенный запрос может быть корректно преобразован к виду

Так что для этого класса запросов единственный слитый блок запроса содержит внешние соединения. Если структура вложенности блоков линейна, то этот подход применим и преобразования производят один блок с линейной последовательностью соединений и внешних соединений. Оказывается, что последовательность соединений и внешних соединений такова, что мы можем использовать правило ассоциативности, описанное в подразделе 4.2.1, для вычисления сначала всех соединений, а затем всех внешних соединений из этой последовательности. Другой подход к устранению вложенных подзапросов состоит в преобразовании запроса к такому виду, в котором используются табличные выражения или представления (и, конечно, это не одноблочный запрос). Это было направление работы Kim [35], которая впоследствии была усовершенствована в [44].

2.3 Использование техники полусоединений для оптимизации запросов с несколькими блоками

В предыдущем разделе я представил примеры того, как запросы, содержащие несколько блоков, могут быть свернуты к одному блоку. В этом разделе я обсуждаю дополнительный подход. Цель этого подхода состоит в использовании селективности предикатов за пределами одного блока. (Хотя эта техника исторически является производной от Магических Множеств и побочной передачи информации, я нахожу связь с полусоединениями более интуитивной и менее таинственной.) На концептуальном уровне подход напоминает идею использования полусоединения для распространения из узла A в удаленный узел B информации о подходящих значениях A, чтобы из B в A не посылались ненужные кортежи. В контексте запросов с несколькими блоками A и B находятся в разных блоках запроса, но являются частями одного и того же запроса, и поэтому не стоит вопрос о стоимости передачи данных. Информация, «получаемая от A», используется для сокращения объема вычислений в B, а также для гарантии того, что результаты, производимые в B, являются подходящими для A. Эта техника требует введения новых табличных выражений и представлений. Например, рассмотрим следующий запрос из [56]:

Метод распознает, что мы можем создать множество подходящих E.did, выполняя соединение E и D в приведенном выше запросе и выполняя проекцию результата на E.did (с устранением дубликатов). Это множество можно передать представлению DepAvgSal для ограничения его вычисления. Это достигается с помощью следующих трех соединений:

В приводимом ниже переформулированном запросе эти представления используются для ограничения вычислений.

Эта техника может быть использована в запросах с несколькими блоками, содержащими представления (включая рекурсивные представления) и вложенные подзапросы [42, 43, 56, 57]. В каждом случае целью является избежание избыточных вычислений в представлениях или вложенных подзапросах. Важно также осознавать соотношение стоимостей вычисления представлений (представления PartialResult в приведенном примере) и использования таких представлений для снижения стоимости вычислений.

Формальная связь описанных преобразований с полусоединениями была недавно представлена в [56] и может служить основой для интеграции этой стратегии с основанными на оценках оптимизаторами. Заметим, что вырожденное применение этой техники состоит в передаче между блоками предикатов, а не результатов представлений. Этот упрощенный метод используется в распределенных и неоднородных базах данных и получил обобщение в [36].

3. Статистики и оценка стоимости

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

1. Собирать статистические сводки по поводу хранимых данных.

2. Для данной операции на основе статистической информации о входных потоках операции данных определять:

a) статистическую информацию о выходном потоке данных;

b) оценочную стоимость выполнения операции.

Шаг 2 может применяться итерационно для дерева операций произвольной глубины для определения стоимости каждой из операций. Как только мы имеем оценки стоимости для каждого узла-операции, стоимость плана может быть получена путем комбинирования стоимостей узлов-операций дерева. В разделе 5.1 мы обсуждаем используемые при оптимизации на основе оценок статистические параметры хранимых данных и эффективные способы получения такой статистической информации. Мы также обсуждаем, как распространять такую статистическую информацию. Вопрос оценки стоимости физических операций обсуждается в разделе 5.2.

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

3.1 Статистические сводки данных

3.1.1 Статистическая информация о базовых данных

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

В большом числе систем информация о распределении данных в столбце обеспечивается с помощью гистограмм. В гистограмме значения столбца делятся на k порций. Во многих случаях k является константой и представляет степень точности гистограммы. Однако k определяет также и использование памяти, поскольку при оптимизации запроса подходящие столбцы гистограммы загружаются в основную память. Имеется несколько вариантов разбиения значений на порции. Во многих системах баз данных для представления распределения данных в столбце используются равноглубокие гистограммы (по-другому их называют равновысокими). Если в таблице содержится n записей и гистограмма состоит из k порций, то в равноглубокой гистограмме набор значений этого столбца делится на k диапазонов, в каждом из которых присутствует одно и то же число значений, т. е. n/k. В сжатых гистограммах часто встречающиеся значения помещаются в отдельные порции. Число таких отдельных порций может настраиваться. Как показано в [52], такие гистограммы эффективны для сильно или слабо скошенных распределений данных. Одним из аспектов гистограмм, отноящихся к оптимизации, является предположение о данных внутри одной порции. Например, для равноглубоких гистограмм можно предположить, что данные на границах порций распределены равномерно. Это предположение, так же как и широкая таксономия гистограммного подхода и влияние структуры гистограмм на точность, обсуждаются в [52]. При отсутствии гистограмм может использоваться такая информация, как минимальное и максимальное значения столбца. Однако на практике используются следующее за минимальным и предыдущее максимальному значения, потому что минимум и максимум с большой вероятностью являются отдаленными значениями. Гистограммная информация дополняется информацией о таких параметрах, как число различных значений в данном столбце.

Хотя гистограммы обеспечивают информацию об одном столбце, они не обеспечивают информации о корреляции между столбцами. Для принятия в учет корреляций нам требуется совместное распределение значений. Один из вариантов состоит в использовании двухмерных гистограмм [45, 51]. К сожалению, пространство возможностей очень велико. Во многих системах вместо детального совместного распределения используется только сводная информация, такая как число различных пар значений. Например, статистическая информация, ассоциированная с индексом на нескольких столбцах, может состоять из гистограммы на первом столбце и общего числа различных комбинаций существующих в таблице значений столбцов.

3.1.2 Оценка статистики базовых данных

Базы данных масштаба предприятия часто имеют большую схему и содержат большие объемы данных. Поэтому для наличия гибкости при получении статистики для улучшения точности важно иметь возможность точно и эффективно оценивать статистические параметры. Один из возможных подходов основывается на взятии проб данных. Однако задачей является ограничение ошибки оценки. В [48] Шапиро и Коннелл показывают, что при наличии заданного запроса требуется только небольшая проба, чтобы построить гистограмму, которая с большой вероятностью будет точной для этого запроса. Но этот подход не достигает цели, которая состоит в том, чтобы построить гистограмму, являющуюся достаточно точной для большого класса запросов. Эту проблему затрагивает наша недавняя работа [11]. Мы также показали, что задача оценки различных значений, вероятно, подвержена ошибкам, т. е. для любой схемы оценок существует база данных, для которой ошибка будет существенной. Этот результат объясняет возникавшие в прошлом трудности в оценке числа различных значений [50, 27]. В одной из недавних работ рассматривается также проблема поддержки статистики в инкрементальной манере [18].

3.1.3 Распространение статистической информации

Недостаточно использовать только информацию о базовых данных, поскольку запрос обычно содержит много операций. Поэтому важно иметь возможность распространять статистическую информацию через операции. Простейший случай такой операции - это селекция. Если имеется гистограмма на столбце A, и запрос состоит из единственной селекции на столбце A, то гистограмму можно модифицировать таким образом, чтобы она отражала действие селекции. На этом шаге такие предположения, как равномерное распределение данных внутри порции данных гистограммы, приводят к некоторой неточности. Более того, ключевым источником ошибок является невозможность учета корреляции. В приведенном примере это выражается в том, что не модифицируются распределения значений других атрибутов таблицы (кроме A), а это подвергает значительным ошибкам последующие операции. Подобно этому, если в запросе присутствует несколько предикатов, то принимается предположение об их независимости и общей селективностью условия считается произведение селективностей предикатов. Однако в некоторых системах используется селективность наиболее селективного предиката, и они могут установить наличие потенциальной корреляции [17]. При наличии гистограмм на столбцах, участвующих в предикате соединения, гистограммы могут «соединяться». Однако это порождает вопрос о выравнивании границ соответствующих порций. Наконец, если гистограммная информация недоступна, то для оценки селективности используются специально подобранные константы, как в [55].

3.2 Вычисление стоимости

На шаге оценки стоимости производится попытка определить стоимость операции. Модуль стоимости оценивает время центрального процессора, число операций ввода/вывода и, в случае параллельных или распределенных систем, коммуникационные расходы. В большинстве систем эти параметры комбинируются на основе общей метрики, и эта комбинированная оценка стоимости используется для сравнения возможных планов. Проблема выбора соответствующего набора параметров для определения стоимости заслуживает значительного внимания. В ранних исследованиях [40] было установлено, что в дополнение к учету физических и логических свойств входных потоков данных и вычислению селективности - ключевую роль в точных оценках играет моделирование использования буферизации в основной памяти. Для этого требуется использование разных коэффициентов предпочтительности содержания в буферном пуле в зависимости от уровней индекса, а также регулирование использования буфера за счет учета свойств методов соединения, например, относительно явной локальности ссылок при индексном сканировании в индексном методе соединения с помощью вложенных циклов [17]. В оценочных моделях учитываются уместные аспекты физического проекта, например, относительное расположение страниц данных и индексных страниц. Однако обеспечение возможности произведения действительно точных оценок стоимости и распространения статистической информации потоков данных остаются трудными открытыми вопросами оптимизации запросов.

4. Архитектуры перебора

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

Мы сосредоточимся на двух представительных примерах таких расширяемых оптимизаторов: Starburst и Volcano/Cascades. Несмотря на имеющиеся различия, можно выделить некоторые общие характеристики этих оптимизаторов.

a) использование обобщенных стоимостных функций и физических свойств вершин-операций;

b) использование подсистемы обработки правил, дающей возможность изменять выражения запросов или деревья операций. Такие подсистемы обеспечивают также возможность прямого поиска для достижения эффективности;

c) большое количество доступных «кнопок», которые можно использовать для настройки поведения оптимизатора. К сожалению, установка этих кнопок для достижения оптимальной эффективности является пугающей задачей.

4.1 Starburst

Оптимизация запросов в проекте Starburst исследовательского центра Almaden компании IBM начинается со структурного представления SQL-запроса, которое используется в течение всего жизненного цикла оптимизации. Это представление называется графовой моделью запроса (Query Graph Model - QGM). В QGM бокс представляет блок запроса, а помеченные дуги между боксами представляют ссылки на таблицы между блоками. Каждый бокс содержит информацию о структуре предиката, а также о том, упорядочен ли поток данных. На фазе оптимизации переписывания запроса [49] используются правила для преобразования QGM в другую эквивалентную QGM. Правила оформляются как пары произвольных функций. Первая функция проверяет условие применимости, вторая - проводит преобразование. Правилами управляет подсистема, основанная на построении цепочек правил. Правила могут группироваться в классы, и можно настраивать порядок вычисления классов правил для ориентации поиска. Поскольку любое применение правила приводит к допустимой QGM, любой набор применений правил гарантирует эквивалентность (в предположении, что сами правила законны). Фаза переписывания запроса не приводит к появлению информации о стоимости. Это вынуждает модуль переписывания запросов либо оставлять варианты, получаемые при применении правил, либо использовать правила эвристическим образом (и тем самым рисковать оптимальностью).

Вторая фаза оптимизации запроса называется оптимизацией плана. На этой фазе выбирается план выполнения для данной QGM. В Starburst физические операторы (называемые LOLEPOP) могут комбинироваться различными способами для реализации операций более высокого уровня. Такие комбинации выражаются в грамматике языка, похожего на языки продукций [37]. Реализация высокоуровневой операции выражается путем описания ее происхождения в терминах физических операций. При вычислении таких описаний сравнимые планы, обладающие одними и теми же физическими и логическими свойствами, но имеющие более высокую стоимость, удаляются. Для каждого плана имеются реляционное описание, соответствующее представляемому алгебраическому выражению, оценочная стоимость и физические свойства (например, наличие упорядоченности). Эти свойства распространяются по мере построения планов снизу-вверх. Таким образом, с каждой физической операцией ассоциирована функция, которая показывает воздействие физической операции на каждое из указанных свойств. Алгоритм перебора соединений в этой системе похож на схему перебора снизу-вверх System R.

4.2 Volcano/Cascades

Расширяемые архитектуры Volcano [23] и Cascades [21] происходят от Exodus [22]. В этих системах правила используются универсально для представления знаний о пространстве поиска. Применяются два вида правил. Правила преобразования отображают одно алгебраическое выражение в другое. Правила реализации отображают алгебраическое выражение в дерево операций. Правила могут иметь условия применимости. Логические свойства, физические свойства и оценки стоимости ассоциируются с планами. Физические свойства и стоимость зависят от алгоритмов, используемых для реализации операций, и от их входных потоков данных. В целях эффективности в Volcano/Cascades используется динамическое программирование в манере «сверху/вниз» («запоминание»). Сталкиваясь с задачей оптимизации, оптимизатор проверяет, не выполнялась ли уже такая задача, производя поиск ее логических и физических свойств в таблице планов, которые оптимизировались в прошлом. Если этот поиск не приводит к результату, то оптимизатор применяет правила преобразования, правила реализации или насильственно изменяет свойства потока данных. На каждой стадии используется перспектива действия для определения следующего шага. Параметр перспективы является программируемым и отражает параметры стоимости.

Volcano/Cascades отличается от подхода Starburst алгоритмом перебора:

a) не применяются две разные фазы оптимизации, поскольку все преобразования являются алгебраическими и основаны на оценках;

b) отображение алгебраического представления в дерево физических операций выполняется за один шаг;

c) вместо применения правил в манере цепочек, как это происходит на фазе переписывания запросов в Starburst, в Volcano/Cascades применение правил управляется целью.

5. За пределами основ

До сих пор я рассматривал основы программных компонентов оптимизатора. В этом разделе обсуждаются более передовые темы. Каждая из них существенно важна для коммерческих систем.

5.1 Распределенные и параллельные базы данных

Распределенные базы данных вводят в рассмотрение вопросы стоимости коммуникаций и расширения пространства поиска в связи с возможностью при оптимизации запросов учитывать допустимые перемещения данных и выбор узлов для выполнения промежуточных операций. Хотя в некоторых из ранних работ основной упор делался на сокращение стоимости коммуникаций [1, 3] (например, с использованием полусоединений), результаты System R* показывают доминирующую роль локальной обработки [39] (см. обзор в [38]). Со временем архитектуры распределенных баз данных эволюционировали к реплицированным базам данных, в которых поддерживается управление физическим распределением данных, и к параллельным базам данных, основной эффект которых состоит в увеличении масштабируемости. В архитектурах, поддерживающих репликацию, важным вопросом является поддержание согласованности реплик, но это находится за пределами темы данной статьи.

В отличие от распределенных систем параллельные базы данных ведут себя как единая система, но используют множественные процессорные элементы для сокращения времени ответа (В однопроцессорных системах основное внимание уделяется сокращению общего объема работы. При параллельном выполнении стремятся скорее сократить время ответа, а не общую работу. На самом деле, во многих случаях, хотя это не необходимо, параллельное выполнение увеличивает общую работу.) на запросы. Преимущества параллелизма могут быть использованы несколькими способами. Например, физическое распределение данных, когда таблица (в общем случае - поток данных) разделяется или реплицируется между узлами, позволяет процессорам работать над независимыми наборами данных. Параллелизм можно также использовать для выполнения независимых операций или конвейерных операций (путем размещения узла-производителя и узла-потребителя на разных процессорах). Достоинства параллелизма уравновешиваются потребностью в коммуникации процессоров для обмена данными, например, в том случае, когда требуется перераспределение данных после выполнения операции. Кроме того, эффективное планирование выполнения физических операций вносит новое измерение в проблему оптимизации. В проекте XPRS [31, 32] поддерживается двухфазный подход, в котором в первой фазе для генерации плана выполнения используется традиционная однопроцессорная оптимизация. На второй фазе определяется планирование процессоров. В работе над оптимизацией запросов в XPRS не изучались эффекты межпроцессорных коммуникаций. В работе Хасана [28] было показана важность учета расходов на коммуникацию. Хасан оставил двухфазный подход, использовавшийся в XPRS, но включил в первую фазу учет расходов и доходов от разделения данных с целью определения порядка соединений и используемых методов доступа. Атрибут разделения потока данных рассматривался как физическое свойство потока данных. На выходе первой фазы формировалось дерево операций, раскрывающее ограничения предшествования (например, для сортировки) и конвейерность выполнения. Для второй фазы оптимизации он предложил алгоритмы планирования, учитывающие коммуникационные расходы.

5.2 Определяемые пользователями функции

Хранимые процедуры (называемые также определяемыми пользователями функциями) получили широкое распространение в реляционных системах. Хотя в разных продуктах поддержка таких функций производится по-разному, они обеспечивают мощный механизм для сокращения коммуникаций клиентов и серверов и предоставляют средства включения в запросы семантики приложений. Новые вопросы оптимизации возникают в тех случаях, когда вызовы хранимых процедур рассматриваются как полноправные компоненты запросов. Проблема определения стоимостной модели определяемой пользователем функции остается трудной проблемой. Интересные аспекты возникают в контексте алгоритма перебора. Например, рассмотрим случай, когда хранимая процедура действует как определенный пользователем предикат в разделе WHERE запроса. В отличие от других предикатов такие предикаты могут быть дорогостоящими (например, они могут быть предикатами на BLOB, содержащих графический образ), и поэтому для них отсутствует здравая эвристика вычисления предикатов как можно раньше. Проблема оптимизации запросов с определенными пользователями предикатами была поставлена в [12, 29]. Подход, предложенный в [12] заключается в том, что к определенным пользователями предикатам следует относиться как к отношениям с точки зрения динамической оптимизации запросов. В подходах [29, 30] используется следующее наблюдение: если отсутствуют соединения, то дорогостоящие предикаты могут быть эффективно упорядочены в соответствии с их рангами, вычисляемыми на основе селективности предикатов и стоимости их вычисления для одного кортежа. К сожалению, попытки расширить использование рангов для запросов с соединениями могут привести к выбору неоптимальных планов. Этот недостаток был устранен в [8] путем представления определенных пользователем предикатов наподобие физических свойств плана, так что основанный на динамическом программировании алгоритм перебора гарантирует оптимальность. Более того, при использовании реалистических предположений о стоимостной модели было показано, что эта проблема имеет полиномиальную сложность в зависимости от числа определенных пользователями предикатов.

Решение проблемы оптимизации определяемых пользователями предикатов - это только первый шаг в решении более широкой проблемы представления семантики ADT (Abstract Data Type) в системе запросов и оптимизация запросов при наличии абстрактных типов данных. Эта проблема близко соприкасается с областью семантической оптимизации запросов.

5.3 Материализованные представления

Материализованные представления - это результаты представлений (т. е. запросов), кэшируемые подсистемой запросов и прозрачно используемые оптимизатором. Проблема оптимизации формулируется следующим образом. Для заданного набора материализованных представлений и запроса целью является оптимизация запроса с учетом имеющихся материализованных представлений. Эта проблема порождает две фундаментальные задачи. Первая состоит в потребности переформулировки запроса таким образом, чтобы для его выполнения можно было использовать одно или несколько материализованных представлений. Эта задача рассматривалась в [15, 61, 59, 9] в контексте SQL-запросов только с одним блоком, и решение должно быть обобщено для сложных запросов. Вторая задача связана с тем, что подход к решению проблемы оптимизации на основе двухфазового процесса, когда генерируются все логически эквивалентные выражения и затем каждое из них оптимизируется индивидуально, может увеличить стоимость оптимизации, поскольку подвыражения не устраняются способом, основанным на оценках. В [9] мы показали, каким образом могут перекрываться шаги перебора и генерации эквивалентных выражений при наличии материализованных представлений.

5.4 Другие вопросы оптимизации

В этой статье я коснулся только некоторых фундаментальных вопросов оптимизации. Имеется много важных областей, которые я не обсуждал. Одним из интересных направлений является то, в котором допускается отложенная генерация полных планов при условии доступности информации времени выполнения [19, 33]. Кроме того, открытой остается проблема учета других ресурсов (в особенности памяти) при определении планов выполнения. Работа [58] посвящена вопросам оптимизации использования порядка при оптимизации запросов. Технология оптимизации в объектно-ориентированных системах является важной областью, заслуживающей отдельного обсуждения. Кроме того, когда базы данных стали использоваться в контекстах мультимедиа и Web, появилось интересное направление работы в связи с нечеткими (неточными) запросами [14, 10]. Существующее повышенное внимание к системам поддержки принятия решений побудило также проведение работ в области расширений SQL. Такие работы, как CUBE [24], мотивируются не потребностью повышения выразительной мощности, а скорее связаны с поиском таких расширений языка, которые позволили бы оптимизатору лучше оптимизировать запросы систем поддержки принятия решений.

6. Заключение

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

Благодарности

Мои многочисленные неформальные дискуссии с Umesh Dayal, Goetz Graefe, Waqar Hasan, Ravi Krishnamurthy, Guy Lohman, Hamid Pirahesh, Kyuseok Shim и Jeff Ullman значительно помогли становлению моего понимания оптимизации SQL-запросов. Многие из этих людей своими комментариями помогли мне также улучшить рукопись этой статьи. Я также признателен Latha Colby, William McKenna, Vivek Narasayya и Janet Wiener за их глубокие комментарии. И как всегда, мои благодарности Debjani за ее терпение.

7. Литература

1. Apers P. M. G., Hevner A. R., Yao S. B. Optimization Algorithms for Distributed Queries. IEEE Transactions on Software Engineering, Vol. 9:1, 1983.

2. Bancilhon F., Maier D., Sagiv Y., Ullman J. D. Magic sets and other strange ways to execute logic programs. In Proc. Of ACM PODS, 1986.

3. Bernstein F., Goodman N., Wong E., Reeve C. L., Rothnie J. Query Processing in a System for Distributed Databases (SDD-1), ACM TODS 6:4 (Dec. 1981).

4. Chaudhuri S., Shim K. An Overview of Cost-based Optimization of Queries with Aggregates. IEEE DE Bulletin, Sep. 1995. (Special Issue on Query Processing.)

5. Chaudhuri S., Shim K. Including Group-By in Query Optimization. In Proc. of VLDB. Santiago, 1994.

6. Chaudhuri S., Shim K. Query Optimization with Aggregate Views. In Proc. of EDBT. Avignon, 1996.

7. Chaudhuri S., Dayal U. An Overview of Data Warehousing and OLAP Technology. In ACM SIGMOD Record, March 1997.

8. Chaudhuri S., Shim K. Optimization of Queries with User-Defined Predicates. In Proc. of VLDB. Mumbai, 1996.

9. Chaudhuri S., Krishnamurthy R., Potamianos S., Shim R. Optimizing Queries with Materialized Views. In Proc. of IEEE Data Engineering Conference. Taipei, 1995.

10. Chaudhuri, S., Gravano, L. Optimizing Queries over Multimedia Repositories. In Proc. of ACM SIGMOD. Montreal, 1996.

11. Chaudhuri, S., Motwani, R., Narasayya, V. Random Sampling for Histogram Construction: How much is enough? In Proc. of ACM SIGMOD. Seattle, 1998.

12. Chimenti D., Gamboa R., Krishnamurthy R. Towards an Open Architecture for LDL. In Proc. of VLDB. Amsterdam, 1989.

13. Dayal U. Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates and Quantifiers. In Proc. of VLDB, 1987.

14. Fagin R. Combining Fuzzy Information from Multiple Systems. In Proc. of ACM PODS, 1996.

15. Finkelstein S. Common Expression Analysis in Database Applications. In Proc. of ACM SIGMOD, Orlando, 1982.

16. Ganski R.A., Long H.K.T. Optimization of Nested SQL Queries Revisited. In Proc. of ACM SIGMOD. San Francisco, 1987.

17. Gassner P., Lohman G., Schiefer, K.B. Query Optimization in the IBM DB2 Family. IEEE Data Engineering Bulletin, Dec. 1993.

18. Gibbons P.B., Matias Y., Poosala V. Fast Incremental Maintenance of Approximate Histograms. In Proc. of VLDB. Athens, 1997.

19. Graefe G., Ward K. Dynamic Query Evaluation Plans. In Proc. of ACM SIGMOD. Portland, 1989.

20. Graefe G. Query Evaluation Techniques for Large Databases. In ACM Computing Surveys: Vol. 25, No 2, June 1993.

21. Graefe G. The Cascades Framework for Query Optimization. In Data Engineering Bulletin. Sept. 1995.

22. Graefe G., Dewitt D. J. The Exodus Otimizer Generator. In Proc. of ACM SIGMOD. San Francisco, 1987.

23. Graefe G., McKenna W. J. The Volcano Optimizer Generator: Extensibility and Efficient Search. In Proc. of the IEEE Conference on Data Engineering. Vienna, 1993.

24. Gray J., Bosworth A., Pirahesh H. Data Cube: A Relational Aggregation Operator Generalizing Gpoup-by, Cross, Tab, and Sub-Totals. In Proc. of IEEE Conference on Data Engineering. New Orleans, 1996.

25. Gupta A., Harinarayan V., Quass D. Aggregate-query processing in data warehousing environment. In Proc. of VLDB. Zurich, 1995.

26. Haas L., Freytag J. C., Lohman G. M., Pirahesh, H. Extensible Query Processing in Starburst. In Proc. of ACM SIGMOD. Portland, 1989.

27. Haas P. J., Naughton J. F., Seshadri S., Stokes L. Sampling-Based Estimation of the Number of Distinct Values of an Attribute. In Proc. of VLDB. Zurich, 1995.

28. Hasan W. Optimization of SQL Queries for Parallel Machines. LNCS 1182. Springer-Verlag, 1996.

29. Hellerstein J. M., Stonebraker M. Predicate Migration: Optimization queries with expensive predicates. In Proc. of ACM SIGMOD. Washington D.C., 1993.

30. Hellerstein J. M. Predicate Migration Placement. In Proc. of ACM SIGMOD. Minneapolis, 1994.

31. Hong W., Stonebraker M. Optimization of Parallel Query Execution Plans in XPRS. In Proc. of Conference on Parallel and Distributed Information Systems, 1991.

32. Hong W. Parallel Query Processing Using Shared Memory and Disk Arrays. Ph.D. Thesis, University of California. Berkeley, 1992.

33. Ioannidis Y., Ng R. T., Shim R., Sellis T. Parametric Query Optimization. In Proc. of VLDB. Vancouver, 1992.

34. Ioannidis Y. E. Universality of Serial Histograms. In Proc. of VLDB. Dublin, Ireland, 1993.

35. Kim W. On Optimizing an SQL-like Nested Query. ACM TODS, Vol. 9, No. 3, 1982.

36. Levy, A., Mumick, I.S., Sagiv, Y. Query Optimization by Predicate Move-Around In Proc. of VLDB. Santiago, 1994.

37. Lohman, G.M. Grammar-like Functional Rules for Representing Query Optimization Alternatives. In Proc. of ACM SIGMOD, 1988.

38. Lohman G., Mohan C., Haas L., Daniels D., Lindsay,B., Selinger P., Wilms P. Query Processing in R*. In Qury Processing in Database Systems. Springer-Verlag, 1985.

39. Mackert L. F., Lohman G. M. R* Optimizer Validation and Performance Evaluation For Distributed Queries. In Readings in Database Systems. Morgan Kaufman.

40. Mackert L. F., Lohman G. M. R* Optimizer Validation and Performance Evaluation for Local Queries. In Proc. of ACM SIGMOD, 1986.

41. Melton, J., Simon A. Understanding The New SQL: A Complete Guide. Morgan Kaufman.

42. Mumick I. S., Finkelstein S., Pirahesh H., Ramakrishnan R. Magic is Relevant. In Proc. of ACM SIGMOD, Atlantic City, 1990.

43. Mumick, I.S., Pirahesh, H. Implementation of Magic Sets in Relational Database System. In Proc. of ACM SIGMOD Montreal, 1994.

44. Muralikrishna M. Improved Unnesting Algorithms for Join Aggregate SQL Queries. In Proc. of VLDB. Vancouver, 1992.

45. Muralikrishna M., Dewitt D. J. Equi-Depth Histograms for Estimating Selectivity Factors for Multi-Dimensional Queries, Proc. of ACM SIGMOD. Chicago, 1988.

46. Ono K., Lohman G. M. Measuring the Complexity of Join Enumeration in Query Optimization. In Proc. of VLDB. Brisbane, 1990.

47. Ozsu M.T., Valduriez P. Pronciples of Distributed Database Systems. Prentice-Hall, 1991.

48. Piatetsky-Shapiro G., Connel C. Accurate Estimation of the Number of Tuples Satisfying a Condition. In Proc. of ACM SIGMOD, 1984.

49. Pirahesh H., Hellerstein J. M., Hasan W. Extensible/Rule Based Query Rewrite Optimization in Starburst. In Proc. of ACM SIGMOD, 1992.

50. Poosala V., Ioannidis Y., Haas P., Shekita E. Improved Histograms for Selectivity Estimation. In Proc. of ACM SIGMOD. Montreal, Canada, 1996.*

51. Poosala V., Ioannidis, Y.E. Selectivity Estimation Without the Attribute Value Independence Assumption. In Proc. of VLDB. Athens, 1997.

52. Poosala V., Ioannidis Y., Haas P., Shekita E. Improved Histograms for Selectivity Estimation of Range Predicates.. In Proc. of ACM SIGMOD. Montreal, 1996.

53. Rosental A., Galindo-Legaria C. Query Graphs, Implementing Trees, and Freely Reropderable Outerjoins. In Proc. of ACM SIGMOD. Atlantic City, 1990.

54. Schneider, D.A. Complex Query Processing in Multiprocessor Database Machines. Ph.D. Thesis, University of Wisconsin, Madison, Sept. 1990. Computer Sciences Technical Report 965.

55. Selinger P. G., Astrahan M. M., Chamberlin D. D., Lorie R. A., Price T. G. Access Path Selection in a Relational Database System. In Reading in Database Systems. Morgan Kaufman.

56. Seshardi P., et al. Cost Based Optimization for Magic: Algebra and Implementation. In Proc. of ACM SIGMOD. Montreal, 1996.

57. Seshardi P., Pirahesh H., Leung T. Y. C. Decorrelating complex queries. In Proc. of the IEEE International Conference on Data Engineering, 1996.

58. Simmen D., Shekita E., Malkemus T. Fundamental Techniques for Order Optimization. In Proc. of ACM SIGMOD. Montreal, 1996.

59. Srvastava D., Dar S., Jagadish H. V., Levy A. Answering Queries with Aggregation Using Views. Proc. of VLDB. Mumbai, 1996.

60. Yan Y. P., Larson P. A. Eager aggregation and lazy aggregation. In Proc. of VLDB Conference. Zurich, 1995.

61. Yang H. Z., Larson P. A. Query Transformation for PSJ-Queries. In Proc. of VLDB, 1987.

* В списке литературы, составленном автором, [50] и [52] представляют собой одну и ту же ссылку, причем правильное название статьи приведено в [52]. Мы не стали исправлять эту небольшую погрешность. (Прим. переводчика.)

Copyright © Microsoft Corporation, 1998. Все права защищены. Полное или частичное воспроизведение данного материала допускается только с письменного разрешения Microsoft Corporation.