Архитектуры перебора
Алгоритм перебора должен выбрать недорогой план выполнения данного запроса на основе исследования пространства поиска. Алгоритм перебора System R, который мы обсуждали в , был разработан в расчете на выбор только оптимального порядка линейных соединений. По соображениям технологии программирования желательно создать такой алгоритм перебора, который мог бы легко приспосабливаться к изменениям пространства поиска по причине добавления новых преобразований, добавления новых физических операций (например, новых реализаций соединений) и к изменениям методов оценки стоимости. Современные архитектуры оптимизации построены на основе этой парадигмы и называются расширяемыми оптимизаторами. Построение расширяемого оптимизатора - это трудная задача, поскольку от него требуется не только наличие улучшенного алгоритма перебора. На самом деле, эта технология обеспечивает инфраструктуру для развития техники оптимизации. Однако общность архитектуры должна быть сбалансирована с потребностью эффективного перебора.
Мы сосредоточимся на двух представительных примерах таких расширяемых оптимизаторов: Starburst и Volcano/Cascades. Несмотря на имеющиеся различия, мы можем выделить некоторые общие характеристики этих оптимизаторов:
- Использование обобщенных стоимостных функций и физических свойств вершин-операций.
- Использование подсистемы обработки правил, дающей возможность изменять выражения запросов или деревья операций. Такие подсистемы обеспечивают также возможность прямого поиска для достижения эффективности.
- Большое количество доступных "кнопок", которые можно использовать для настройки поведения оптимизатора. К сожалению, установка этих кнопок для достижения оптимальной эффективности является пугающей задачей.
- -
