| ||||||||||||
| ||||||||||||
|
2009 г.
Оценочная оптимизация для магии: алгебра и реализацияПравин Сешарди (Praveen Seshadri, Univ. of Wisconsin, Madison) Перевод: Сергей Кузнецов 7. Алгебра Θ-полусоединенийВ своей реализации мы использовали перезапись на основе магических множеств путем ее «встраивания» («piggybacking») в существующие механизмы оптимизатора. Если бы система основывалась на алгебраическом, управляемом правилами оптимизаторе, таком как Volcano [GM93], был бы возможен и подход к расширению алгебры запросов для моделирования магических множеств. В этом разделе мы представляем такое алгебраическое расширение, помогающее охарактеризовать точное пространство возможных вариантов. Алгебраические эквивалентности приводят к преобразованию запросов, которые могут применяться в оценочном стиле, возможно, с использованием уже представленных методов оценки, или с использованием тщательного исследования пространства поиска. 7.1 НотацияМы используем символы R (с нижним регистром или без него) для обозначения отношений, Θ (с нижним регистром или без него) для обозначения предикатов, E (с нижним регистром или без него) для обозначения реляционных выражений, attrs(E) для обозначения атрибутов результата E и a для обозначения кортежа атрибутов. В соответствии с семантикой SQL мы трактуем отношения как мультимножества кортежей и используем мультимножественный вариант реляционной алгебры [DGK82]. Мы предполагаем знакомство читателей с этой алгеброй и описываем только операцию группирования/агрегации и мультимножественную операцию Θ-полусоединения. Мы используем операцию группирования/агрегации gℑ f , где g обозначает атрибуты группирования, а f – агрегатные операции, которые выполняются над группами, определяемыми атрибутами группирования. (Эта нотация заимствована из [EN94, Klu82]; такая операция требуется для работы с группировкой и агрегированием в стиле SQL.) Определение 7.1 (Мультимножественное Θ-полусоединение) Мультимножественный вариант операции Θ-полусоединения ⊳<Θ определяется следующим образом. Для двух заданных отношений R1 и R2
где Θ(t2) обозначает предикат Θ, в котором имена атрибутов из R2 заменены их значениями из кортежа t2. Определение Θ-полусоединения сохраняет семантику семантику мультимножеств, т.е. кратность каждого кортежа, присутствующего в результате, совпадает с кратностью этого кортежа в R1. Например, если отношение R1(A,B) является мультимножеством кортежей {(1,2), (1,2), (1,4), и R2(C,D) состоит из {(3,5), (3,6), (3,7)}, то R1 ⊳<C≥D R2 = {(1,2), (1,2)}. В мультимножественной реляционной алгебре Θ-полусоединение является выводимой операцией, выражаемой через операции Θ-соединения, проекции (π) и удаления дубликатов (δ) следующим образом:4
где ⊳⊲ 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-запросов, обычно не содержат операцию Θ-полусоединения.5 Ниже мы иллюстрируем, как операция Θ-полусоединения может быть введена в выражения с соединениями; аналогичные правила эквивалентности могут быть выведены для внешних соединений, пересечений и взятия разности.
Интуитивно ясно, что в результате выражения E1 ⊳<Θ E2 участвуют только те кортежи E2, которые соединяются с кортежами E1 по предикату Θ. Следовательно выбор подмножества кортежей E2, которые соединяются с E1 по предикату Θ, до выполнения соединения с E1 сохраняет эквивалентность. Заметим, что в результате этого шага вводятся общие подвыражения. Проталкивание Θ-полусоединения через соединение: Ниже мы представляем правило преобразования, описывающее, как протолкнуть Θ-полусоединение через соединения.
где
Это преобразование позволяет использовать и E1, и E3 для ограничения кортежей, вычисляемых для E1’. Хотя в преобразовании используется декартово произведение, оно является полезным, если в некоторой части Θ2 используются только атрибуты из E1 и E3 – эта часть Θ2 может быть использована на последующем шаге для преобразования декартова произведения в Θ-соединение. Интуитивные соображения по поводу корректности этого правила преобразования состоят в том, что требуются только те кортежи t2 Проталкивание Θ-полусоединения через агрегирование: Следующее правило преобразования описывает, как протолкнуть Θ-полусоединение через группировку и агрегирование.
где Θ включает только атрибуты из g и atrrs(E2). Здесь интуитивные соображения состоят в том, что если предикат полусоединения Θ включает только атрибуты из g и atrrs(E2), то для каждой группы кортежей из E1 либо все кортежи будут выбраны при выполнении операции (E1 ⊳<Θ E2), либо не будет выбран ни один кортеж. Кортеж в результате операции ℑ, генерируемый для каждой группы, будет выбираться или не выбираться соответственно. Если Θ включает результаты агрегации, то операцию Θ-полусоединения, вообще говоря, нельзя протолкнуть через агрегацию. В некоторых случаях, включающих min и max, операцию Θ-полусоединения можно протолкнуть через gℑ f; см. [SSS95]. Упрощение: Некоторые преобразования Θ-полусоединений могут приводить к генерации выражений, в которых некоторые предикаты проверяются более одного раза; например, в правой части описанного выше преобразования, вводящего Θ-полусоединение, предикат Θ проверяется дважды. В общем случае повторяющиеся проверки неизбежны, но в некоторых частных случаях они являются избыточными, и выражения можно упростить путем устранения повторяющихся проверок. Следующее преобразование может быть использовано для устранения повторяющихся проверок при наличии возможности его применения.
где attrs(E2) функционально определяют все атрибуты в Θ2 над FD(Θ1) Заметим, что использование подмножества функциональных зависимостей при выполнении этого преобразования является безопасным, так что полный механизм вывода функциональных зависимостей не существенен. Устранение Θ-полусоединения: Из интуитивных соображений Θ-полусоединение можно переписать как соединение, за которым следует проекция, если предикат соединения вместе с функциональными зависимостями правого операнда Θ-полусоединения гарантируют, что для каждого кортежа левого операнда выбирается не более одного кортежа левого операнда. Это интуитивное соображение формально фиксируется в следующем правиле преобразования:
где E2.y является суперключом E2, и g(attrs(E1) – это функция от атрибутов E1, возвращающая кортеж той же арности, что и E2.y. Мы представили характерный образец правил эквивалентности, включающих операцию Θ-полусоединения. Более полный набор правил эквивалентности представлен в [SSS95]. 7.3 Оценочная модель для Θ-полусоединенияОперацию Θ-полусоединения R1 ⊳<Θ R2 можно эффективно реализовать с использованием небольших изменений таких методов соединения, как соединение с хэшированием и индексное соединение. В одной из реализаций левый операнд R1 Θ-полусоединения трактуется как «внешнее» отношение метода соединения. Для каждого кортежа внешнего отношения R1, вместо того чтобы соединять его с каждым подходящим кортежем внутреннего отношения R2, этот кортеж поступает в результат операции, как только обнаружено соответствие. Аналогичным образом для реализации Θ-полусоединений можно приспособить метод соединения сортировкой со слиянием, если предикатом соединения является равенство. В качестве альтернативы в методе соединения можно трактовать как «внешнее» отношение правый операнд R1 Θ-полусоединения. Для каждого кортежа внешнего отношения R2 возвращаются все подходящие кортежи внутреннего отношения R1. Если кортеж из R1 уже находится в результате вследствие соответствия другому кортежу R2, то он не добавляется к результату; для эффективной реализации в общем случае требуется наличие индекса на результате Θ-полусоединения. Если предикат Θ-полусоединения включает равенство с суперключом R2, то это гарантирует, что любой кортеж R1 соответствует не более чем одному кортежу R2; в этом случае не требуется какой-либо индекс на результате Θ-полусоединения. Оценочные формулы для различных методов соединения легко модифицируются для порождения оценочных формул для различных способов реализации операции Θ-полусоединения. Мы опускаем детали. На оценочной фазе трансформационного оптимизатора, такого как Volcano, используются оценочные формулы для операций алгебры, чтобы вычислить оценки стоимости для различных способов вычисления запроса. Поскольку Θ-полусоединение является порождаемой операцией (ее можно выразить с использованием Θ-соединения, проекции и удаления дубликатов), ее можно также реализовать с использованием алгоритмов для этих операций. Однако такая реализация является неэффективной. 7.4 Применение правил эквивалентности Θ-полусоединенияПерезапись с использованием правил эквивалентности Θ-полусоединения особенно полезна для сложных запросов, в которых используются представления, не развертываемые в соединения. В число примеров входят:
Особым преимуществом оптимизации на основе правил является простота спецификации преобразований для разнообразных операций. В действительности, набор правил преобразования, представленный в [SSS95], обеспечивает возможность протолкнуть Θ-полусоединения в представления во всех упомянутых примерах. Если бы добавить к исчерпывающему оптимизатору полное множество правил эквивалентности Θ-полусоединения, то пространство поиска могло бы очень сильно расшириться. Представленные выше классы запросов представляют наиболее важные классы применения правил эквивалентности Θ-полусоединения, что приводит к следующей весьма полезной эвристике: Операцию Θ-полусоединения следует вводить только имея дело и операциями агрегации, устранения дубликатов и внешнего соединения. Правило эквивалентности для агрегации было представлено выше, а другие правила описываются в [SSS95]. 4 В множественном варианте реляцио
нной алгебры Θ-полусоединение можно выразить более просто, как 5 При трансляции SQL в реляционную алгебру, представленной в [CG85], Θ-полусоединения используются только при обработке разделов HAVING.
|
E2, для которых существуют кортежи t1 
FD(E1).
.
Это тождество оказывается неверным для мультимножественного варианта алгебры.
 | |||||||||
| |||||||||
|
CITForum © 1997–2025