Набросок реализации расширенных магических множеств (EMS)
Мы реализуем EMS в Starburst. У нас имеется псевдокод, и C-код, выполняющий преобразования в простых случаях. В этом разделе мы приводим набросок своей реализации.
EMS является частью фазы перезаписи запросов в оптимизаторе Starburst. Перезаписи выполняются (продукционной) системой, основанной на правилах, в которой каждое преобразование запроса кодируется в виде правила перезаписи [HP88]. Процессор прямого построения цепочек обходит граф запроса (обычно) в глубину, применяя правила перезаписи. EMS применяется к элементам графа, представляющим табличные выражения, к одному табличному выражению за раз. Многочисленные возбуждения правила EMS по мере обхода графа совокупно производят преобразованный запрос.
В системе правил Starburst, кроме правила магических множеств, имеется ряд других правил перезаписи. Правила проталкивания предикатов определяют, какие предикаты и в какой форме выталкиваются из табличных выражений в таблицы, на которые в них имеются ссылки. После этого правило EMS размещает предикаты в правильных местах (как магические множества).
Способ применения магических множеств к таблице может зависеть от операции в табличном выражении. Например, магия не может быть применена к такой операции как GROUPBY (к плохим операциям), а к такой операции как SELECT – применима (к хорошим операциям).
Когда производится магическая обработка табличного выражения для таблицы t, предыдущая обработка обеспечивает украшение заголовка t, наличие магической таблицы mt для t и (для хороших операций) то, что mt является опорной и присоединенной к телу табличного выражения. Кроме того, должен быть известен порядок SIPS внутри табличного выражения.
В течение магической обработки t все предикаты в табличном выражении проталкиваются в каждую таблицу r, на которую имеются ссылки из табличного выражения (с использованием правил проталкивания предикатов). Для каждой r определяется украшение α, и создается табличное выражение для rα с телом, идентичным телу табличного выражения для r.
Для rα на основе его использования в t формируется магическое множество m_rα и, если r является хорошей, оно делается опорным и добавляется к табличному выражению для rα.
Магическая обработка производится для каждого табличного выражения, проходимого при обходе графа запроса. Мы избегаем повторной обработки табличного выражения, за исключением плохих табличных выражений при особых условиях. Для нашего алгоритма EMS справедлива следующая теорема (в предположении, что сначала мы избавляемся ото всех циклов в запросе Q, состоящем исключительно из плохих таблиц).
Теорема 5.1 Для любого графа запроса Q алгоритм EMS завершается, и EMS(Q) эквивалентен Q при применении стратегии выполнения Starburst.
Украшения и магические преобразования объединяются в однофазный алгоритм (разд. 4.3). По большей части используется простое bcf-украшение, хотя для плохих операций требуются специальные улучшенные украшения. Алгоритм EMS является расширяемым по отношению к (1) новым операциям в табличных выражениях и (2) стратегии обхода (в глубину, в ширину, снизу-вверх и т.д.).
