Магия сохраняет силу


Набросок реализации расширенных магических множеств (EMS)


Мы реализуем EMS в Starburst. У нас имеется псевдокод, и C-код, выполняющий преобразования в простых случаях. В этом разделе мы приводим набросок своей реализации.

EMS является частью фазы перезаписи запросов в оптимизаторе Starburst. Перезаписи выполняются (продукционной) системой, основанной на правилах, в которой каждое преобразование запроса кодируется в виде правила перезаписи [HP88]. Процессор прямого построения цепочек обходит граф запроса (обычно) в глубину, применяя правила перезаписи. EMS применяется к элементам графа, представляющим табличные выражения, к одному табличному выражению за раз. Многочисленные возбуждения правила EMS по мере обхода графа совокупно производят преобразованный запрос.

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

Способ применения магических множеств к таблице может зависеть от операции в табличном выражении. Например, магия не может быть применена к такой операции как GROUPBY (к плохим операциям), а к такой операции как SELECT – применима (к хорошим операциям).

Когда производится магическая обработка табличного выражения для таблицы t, предыдущая обработка обеспечивает украшение заголовка t, наличие магической таблицы mt для t и (для хороших операций) то, что mt является опорной и присоединенной к телу табличного выражения. Кроме того, должен быть известен порядок SIPS внутри табличного выражения.

В течение магической обработки t все предикаты в табличном выражении проталкиваются в каждую таблицу r, на которую имеются ссылки из табличного выражения (с использованием правил проталкивания предикатов). Для каждой r определяется украшение α, и создается табличное выражение для с телом, идентичным телу табличного выражения для r.


Начало  Назад  Вперед



Книжный магазин