Оценочная оптимизация для магии: алгебра и реализация

Правин Сешарди (Praveen Seshadri, Univ. of Wisconsin, Madison)
Джозеф Хеллерстейн (Joseph M. Hellerstein, Univ. of California, Berkeley)
Хамид Пирамеш (Hamid Pirahesh, IBM Almaden Research Ctr.)
Клифф Леюнг (T. Y. Cliff Leung, IBM Santa Teresa Lab.)
Раджу Рамакришнан (Raghu Ramakrishnan, Univ. of Wisconsin, Madison)
Дивеш Сривастава (Divesh Srivastava, AT&T Research)
Питер Стюки (Peter J. Stuckey, Univ. of Melbourne)
С. Сударшан (S. Sudarshan, IIT, Bombay)
SIGMOD Conference 1996: 435-446

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

Назад Содержание Вперёд

7. Алгебра Θ-полусоединений

В своей реализации мы использовали перезапись на основе магических множеств путем ее «встраивания» («piggybacking») в существующие механизмы оптимизатора. Если бы система основывалась на алгебраическом, управляемом правилами оптимизаторе, таком как Volcano [GM93], был бы возможен и подход к расширению алгебры запросов для моделирования магических множеств. В этом разделе мы представляем такое алгебраическое расширение, помогающее охарактеризовать точное пространство возможных вариантов. Алгебраические эквивалентности приводят к преобразованию запросов, которые могут применяться в оценочном стиле, возможно, с использованием уже представленных методов оценки, или с использованием тщательного исследования пространства поиска.

7.1 Нотация

Мы используем символы R (с нижним регистром или без него) для обозначения отношений, Θ (с нижним регистром или без него) для обозначения предикатов, E (с нижним регистром или без него) для обозначения реляционных выражений, attrs(E) для обозначения атрибутов результата E и a для обозначения кортежа атрибутов. В соответствии с семантикой SQL мы трактуем отношения как мультимножества кортежей и используем мультимножественный вариант реляционной алгебры [DGK82]. Мы предполагаем знакомство читателей с этой алгеброй и описываем только операцию группирования/агрегации и мультимножественную операцию Θ-полусоединения. Мы используем операцию группирования/агрегации _gℑ _f , где g обозначает атрибуты группирования, а f – агрегатные операции, которые выполняются над группами, определяемыми атрибутами группирования. (Эта нотация заимствована из [EN94, Klu82]; такая операция требуется для работы с группировкой и агрегированием в стиле SQL.)

Определение 7.1 (Мультимножественное Θ-полусоединение) Мультимножественный вариант операции Θ-полусоединения ⊳<_Θ определяется следующим образом. Для двух заданных отношений R₁ и R₂

где Θ(t₂) обозначает предикат Θ, в котором имена атрибутов из R₂ заменены их значениями из кортежа t₂.

Определение Θ-полусоединения сохраняет семантику семантику мультимножеств, т.е. кратность каждого кортежа, присутствующего в результате, совпадает с кратностью этого кортежа в R₁. Например, если отношение R₁(A,B) является мультимножеством кортежей {(1,2), (1,2), (1,4), и R₂(C,D) состоит из {(3,5), (3,6), (3,7)}, то R₁ ⊳<_C≥D R₂ = {(1,2), (1,2)}.

В мультимножественной реляционной алгебре Θ-полусоединение является выводимой операцией, выражаемой через операции Θ-соединения, проекции (π) и удаления дубликатов (δ) следующим образом:⁴

где ⊳⊲ _Nat обозначает естественное соединение. Интуитивно понятно, что выражение

содержит все кортежи результата Θ-полусоединения, но, возможно, с неверной кратностью. Следующая за естественным соединением операция удаления дубликатов используется для восстановления желаемой кратности.

В некоторых из описываемых нами правил эквивалентности Θ-полусоединений используются присутствующие в отношениях функциональные зависимости; мы обозначаем функциональные зависимости, присутствующие в отношении R, как FD(R). Кроме того, в правилах эквивалентности также используются функциональные зависимости, следующие из предикатов (таких как предикаты Θ-соединения и Θ-полусоединения). Например, из предиката x = y * y следует функциональная зависимость {y} → x, а из предиката x = y + z следуют функциональные зависимости {y,z} → x, {x,y} → z и {x,z} → y. Мы используем нотацию FD(Θ) для обозначения множества всех функциональных зависимостей, следующих из предиката Θ.

7.2 Правила преобразований для Θ-полусоединения

Оптимизация SQL-запросов на основе использования Θ-полусоединений включает спецификацию правил эквивалентности выражений с полусоединениями и другими операциями расширенной мультимножественной реляционной алгебры. При наличии набора правил эквивалентности может быть использован трансформационный оптимизатор, такой как Volcano [GM93], для перечисления и компактного представления логического пространства поиска. Для вычисления оценок стоимости и выбора оптимального способа вычисления запроса используются оценочные формулы.

Ниже мы обсудим некоторые наиболее интересные преобразования выражений с операциями Θ-полусоединений и Θ-соединений; остальные правила представлены в [SSS95]. В алгебраических преобразованиях может потребоваться шаг переименования, например, при изменении структуры выражений. Как и в других подобных работах, для простоты изложения мы игнорируем шаг переименования в своих правилах эквивалентности; детали переименования можно легко разработать самостоятельно.

Введение Θ-полусоединения: Выражения реляционной алгебры, генерируемые напрямую на основе SQL-запросов, обычно не содержат операцию Θ-полусоединения.⁵ Ниже мы иллюстрируем, как операция Θ-полусоединения может быть введена в выражения с соединениями; аналогичные правила эквивалентности могут быть выведены для внешних соединений, пересечений и взятия разности.

Интуитивно ясно, что в результате выражения E₁ ⊳<_Θ E₂ участвуют только те кортежи E₂, которые соединяются с кортежами E₁ по предикату Θ. Следовательно выбор подмножества кортежей E₂, которые соединяются с E₁ по предикату Θ, до выполнения соединения с E₁ сохраняет эквивалентность. Заметим, что в результате этого шага вводятся общие подвыражения.

Проталкивание Θ-полусоединения через соединение: Ниже мы представляем правило преобразования, описывающее, как протолкнуть Θ-полусоединение через соединения.

где

Это преобразование позволяет использовать и E₁, и E₃ для ограничения кортежей, вычисляемых для E₁’. Хотя в преобразовании используется декартово произведение, оно является полезным, если в некоторой части Θ₂ используются только атрибуты из E₁ и E₃ – эта часть Θ₂ может быть использована на последующем шаге для преобразования декартова произведения в Θ-соединение. Интуитивные соображения по поводу корректности этого правила преобразования состоят в том, что требуются только те кортежи t₂ E₂, для которых существуют кортежи t₁ E₁ и t₃ E₃, для которых Θ₁(t₁, t₂) и Θ₂(t₁, t₂, t₃) вычисляются в true.

Проталкивание Θ-полусоединения через агрегирование: Следующее правило преобразования описывает, как протолкнуть Θ-полусоединение через группировку и агрегирование.

где Θ включает только атрибуты из g и atrrs(E₂).

Здесь интуитивные соображения состоят в том, что если предикат полусоединения Θ включает только атрибуты из g и atrrs(E₂), то для каждой группы кортежей из E₁ либо все кортежи будут выбраны при выполнении операции (E₁ ⊳<_Θ E₂), либо не будет выбран ни один кортеж. Кортеж в результате операции ℑ, генерируемый для каждой группы, будет выбираться или не выбираться соответственно.

Если Θ включает результаты агрегации, то операцию Θ-полусоединения, вообще говоря, нельзя протолкнуть через агрегацию. В некоторых случаях, включающих min и max, операцию Θ-полусоединения можно протолкнуть через _gℑ _f; см. [SSS95].

Упрощение: Некоторые преобразования Θ-полусоединений могут приводить к генерации выражений, в которых некоторые предикаты проверяются более одного раза; например, в правой части описанного выше преобразования, вводящего Θ-полусоединение, предикат Θ проверяется дважды. В общем случае повторяющиеся проверки неизбежны, но в некоторых частных случаях они являются избыточными, и выражения можно упростить путем устранения повторяющихся проверок. Следующее преобразование может быть использовано для устранения повторяющихся проверок при наличии возможности его применения.

где attrs(E₂) функционально определяют все атрибуты в Θ₂ над FD(Θ₁) FD(E₁).

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

Устранение Θ-полусоединения: Из интуитивных соображений Θ-полусоединение можно переписать как соединение, за которым следует проекция, если предикат соединения вместе с функциональными зависимостями правого операнда Θ-полусоединения гарантируют, что для каждого кортежа левого операнда выбирается не более одного кортежа левого операнда. Это интуитивное соображение формально фиксируется в следующем правиле преобразования:

где E₂.y является суперключом E₂, и g(attrs(E₁) – это функция от атрибутов E₁, возвращающая кортеж той же арности, что и E₂.y.

Мы представили характерный образец правил эквивалентности, включающих операцию Θ-полусоединения. Более полный набор правил эквивалентности представлен в [SSS95].

7.3 Оценочная модель для Θ-полусоединения

Операцию Θ-полусоединения R₁ ⊳<_Θ R₂ можно эффективно реализовать с использованием небольших изменений таких методов соединения, как соединение с хэшированием и индексное соединение. В одной из реализаций левый операнд R₁ Θ-полусоединения трактуется как «внешнее» отношение метода соединения. Для каждого кортежа внешнего отношения R₁, вместо того чтобы соединять его с каждым подходящим кортежем внутреннего отношения R₂, этот кортеж поступает в результат операции, как только обнаружено соответствие. Аналогичным образом для реализации Θ-полусоединений можно приспособить метод соединения сортировкой со слиянием, если предикатом соединения является равенство.

В качестве альтернативы в методе соединения можно трактовать как «внешнее» отношение правый операнд R₁ Θ-полусоединения. Для каждого кортежа внешнего отношения R₂ возвращаются все подходящие кортежи внутреннего отношения R₁. Если кортеж из R₁ уже находится в результате вследствие соответствия другому кортежу R₂, то он не добавляется к результату; для эффективной реализации в общем случае требуется наличие индекса на результате Θ-полусоединения. Если предикат Θ-полусоединения включает равенство с суперключом R₂, то это гарантирует, что любой кортеж R₁ соответствует не более чем одному кортежу R₂; в этом случае не требуется какой-либо индекс на результате Θ-полусоединения.

Оценочные формулы для различных методов соединения легко модифицируются для порождения оценочных формул для различных способов реализации операции Θ-полусоединения. Мы опускаем детали. На оценочной фазе трансформационного оптимизатора, такого как Volcano, используются оценочные формулы для операций алгебры, чтобы вычислить оценки стоимости для различных способов вычисления запроса.

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

7.4 Применение правил эквивалентности Θ-полусоединения

Перезапись с использованием правил эквивалентности Θ-полусоединения особенно полезна для сложных запросов, в которых используются представления, не развертываемые в соединения. В число примеров входят:

• Запросы, в которых используются представления, определенные с применением агрегации. Пример такого запроса был представлен в разд. 2.
• Запросы над представлениями, в определениях которых используется SELECT DISTINCT. Такие представления развертываются в некоторых, но не во всех случаях.
• Запросы с внешними соединениями. Представления, используемые в качестве аргументов внешних соединений, развернуть невозможно.

Особым преимуществом оптимизации на основе правил является простота спецификации преобразований для разнообразных операций. В действительности, набор правил преобразования, представленный в [SSS95], обеспечивает возможность протолкнуть Θ-полусоединения в представления во всех упомянутых примерах.

Если бы добавить к исчерпывающему оптимизатору полное множество правил эквивалентности Θ-полусоединения, то пространство поиска могло бы очень сильно расшириться. Представленные выше классы запросов представляют наиболее важные классы применения правил эквивалентности Θ-полусоединения, что приводит к следующей весьма полезной эвристике:

Операцию Θ-полусоединения следует вводить только имея дело и операциями агрегации, устранения дубликатов и внешнего соединения.

Правило эквивалентности для агрегации было представлено выше, а другие правила описываются в [SSS95].

---

4 В множественном варианте реляцио нной алгебры Θ-полусоединение можно выразить более просто, как . Это тождество оказывается неверным для мультимножественного варианта алгебры.

5 При трансляции SQL в реляционную алгебру, представленной в [CG85], Θ-полусоединения используются только при обработке разделов HAVING.

Назад Содержание Вперёд