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

       

CM-преобразование SQL-блока с использованием


?-полусоединения: Алгебраическое выражение V, генерируемое путем преобразования SQL-запроса, состоящего из одиночного блока запроса, имеет вид:

При наличии фильтрующего отношения F для V, обозначаемого V ?<? F, к V ?<? F можно применить следующую последовательность преобразований. Во-первых, определим наиболее мощное подмножество ?, обозначаемое как ?n, которое можно протолкнуть через операцию группировки/агрегации. Если в исходном запросе не использовался раздел GROUPBY, то предикат ?n является таким же, как и ?. Затем

можно протолкнуть внутрь операции проецирования и операции группировки/агрегирования, получая

Наконец, можно многократно применить шаг CMT к выражению

как это описывается ниже. Сначала определим Si, i ? 1 следующим образом:

Кроме того, пусть ?i, i < n обозначает наиболее мощное подмножество ?i+1, в котором используются только атрибуты F и Si, а ?i, i < n обозначает оставшуюся часть ?i+1. Первое применение шага CMT преобразует

в
, где
и

Посмотрим теперь на S’n-1: ?-полусоединение можно протолкнуть через определение S’n-1 точно в такой же манере, как выше. Таким образом, шаг CMT применяется для каждого Si, n ? i ? 2. Заметим, что имеются два вхождения S’n-1, т.е. это общее подвыражение двух выражений. Путем использования помеченных выражений мы можем избежать двойной оптимизации и вычисления выражений. Использование помеченных выражений является очень важным для избежания экспоненциального взрыва при спуске от Sn к S1.



Содержание раздела