Struburst
Оптимизация запросов в проекте Sturburst исследовательского центра Almaden компании IBM начинается со структурного представления SQL-запроса, которое используется в течение всего жизненного цикла оптимизации. Это представление называется графовой моделью запроса (Query Graph Model - QGM). В QGM бокс представляет блок запроса, а помеченные дуги между боксами представляют ссылки на таблицы между блоками. Каждый бокс содержит информацию о структуре предиката, а также о том, упорядочен ли поток данных. На фазе оптимизации переписывания запроса [49] используются правила для преобразования QGM в другую эквивалентную QGM. Правила оформляются как пары произвольных функций. Первая функция проверяет условие применимости, вторая - проводит преобразование. Правилами управляет подсистема, основанная на построении цепочек правил. Правила могут группироваться в классы, и можно настраивать порядок вычисления классов правил для ориентации поиска. Поскольку любое применение правила приводит к допустимой QGM, любой набор применений правил гарантирует эквивалентность (в предположении, что сами правила законны). Фаза переписывания запроса не приводит к появлению информации о стоимости. Это вынуждает модуль переписывания запросов либо оставлять варианты, получаемые при применении правил, либо использовать правила эвристическим образом (и тем самым рисковать оптимальностью).
Вторая фаза оптимизации запроса называется оптимизацией плана. На этой фазе выбирается план выполнения для данной QGM. В Sturburst физические операторы (называемые LOLEPOP), могут комбинироваться различными способами для реализации операций более высокого уровня. Такие комбинации выражаются в грамматике языка, похожего на языки продукций [37]. Реализация высокоуровневой операции выражается путем описания ее происхождения в терминах физических операций. При вычислении таких описаний сравнимые планы, обладающие одними и теми же физическими и логическими свойствами, но имеющие более высокую стоимость, удаляются. Для каждого плана имеются реляционное описание, соответствующее представляемому алгебраическому выражению, оценочная стоимость и физические свойства (например, наличие упорядоченности). Эти свойства распространяются по мере построения планов снизу-вверх. Таким образом, с каждой физической операцией ассоциирована функция, которая показывает воздействие физической операции на каждое из указанных свойств. Алгоритм перебора соединений в этой системе похож на схему перебора снизу-вверх System R.
- -
