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

Сураджит Чаудхари

Перевод: Сергей Кузнецов

Предыдущий раздел - Содержание - Следующий раздел

6. Архитектуры перебора

Алгоритм перебора должен выбрать недорогой план выполнения данного запроса на основе исследования пространства поиска. Алгоритм перебора System R, который мы обсуждали в разделе 3, был разработан в расчете на выбор только оптимального порядка линейных соединений. По соображениям технологии программирования желательно создать такой алгоритм перебора, который мог бы легко приспосабливаться к изменениям пространства поиска по причине добавления новых преобразований, добавления новых физических операций (например, новых реализаций соединений) и к изменениям методов оценки стоимости. Современные архитектуры оптимизации построены на основе этой парадигмы и называются расширяемыми оптимизаторами. Построение расширяемого оптимизатора - это трудная задача, поскольку от него требуется не только наличие улучшенного алгоритма перебора. На самом деле, эта технология обеспечивает инфраструктуру для развития техники оптимизации. Однако общность архитектуры должна быть сбалансирована с потребностью эффективного перебора.

Мы сосредоточимся на двух представительных примерах таких расширяемых оптимизаторов: Starburst и Volcano/Cascades. Несмотря на имеющиеся различия, мы можем выделить некоторые общие характеристики этих оптимизаторов:

1. Использование обобщенных стоимостных функций и физических свойств вершин-операций.
2. Использование подсистемы обработки правил, дающей возможность изменять выражения запросов или деревья операций. Такие подсистемы обеспечивают также возможность прямого поиска для достижения эффективности.
3. Большое количество доступных "кнопок", которые можно использовать для настройки поведения оптимизатора. К сожалению, установка этих кнопок для достижения оптимальной эффективности является пугающей задачей.

Предыдущий раздел - Содержание - Следующий раздел