Обзор методов оптимизации запросов в реляционных системах




Volcano/Cascades


Расширяемые архитектуры Volcano [23] и Cascades [21] происходят от Exodus [22]. В этих системах правила используются универсально для представления знаний о пространстве поиска. Применяются два вида правил. Правила преобразования отображают одно алгебраическое выражение в другое. Правила реализации отображают алгебраическое выражение в дерево операций. Правила могут иметь условия применимости. Логические свойства, физические свойства и оценки стоимости ассоциируются с планами. Физические свойства и стоимость зависят от алгоритмов, используемых для реализации операций, и от их входных потоков данных. В целях эффективности в Volcano/Cascades используется динамическое программирование в манере сверху-вниз ("запоминание"). Сталкиваясь с задачей оптимизации, оптимизатор проверяет, не выполнялась ли уже такая задача, производя поиск ее логических и физических свойств в таблице планов, которые оптимизировались в прошлом. Если этот поиск не приводит к результату, то оптимизатор применяет правила преобразования, правила реализации или насильственно изменяет свойства потока данных. На каждой стадии используется перспектива действия для определения следующего шага. Параметр перспективы является программируемым и отражает параметры стоимости.

Volcano/Cascades отличается от подхода Starburst алгоритмом перебора:

  1. Не применяются две разные фазы оптимизации, поскольку все преобразования являются алгебраическими и основаны на оценках.
  2. Отображение алгебраического представления в дерево физических операций выполняется за один шаг.
  3. Вместо применения правил в манере цепочек, как это происходит на фазе переписывания запросов в Starburst, в Volcano/Cascades применение правил управляются целью.

- -




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