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

Сураджит Чаудхари

Перевод: Сергей Кузнецов

Предыдущий раздел - Содержание - Следующий раздел

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

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

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

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

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

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

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

4.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], определяют класс запросов, в которых можно изменять порядок обычных и внешних соединений.

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

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

Рис. 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) для выполнения ранней агрегации и получения общего объема продаж для каждого продукта. Затем нам потребуется еще одна группировка, чтобы сложить объемы продаж всех продуктов, относящихся к одному отделению.

---

¹ Наиболее велика не стоимость генерации синтаксических порядков соединений. Интенсивные вычисления требуются для выбора физических операций и оценки стоимости каждого возможного плана.

Предыдущий раздел - Содержание - Следующий раздел