Методы оптимизации выполнения запросов в реляционных СУБД


Оптимизаторы с гибкой структурой - часть 4


Коротко рассмотрим, как реально обрабатывается запрос в оптимизаторе СУБД Starburst под управлением заданного набора правил.

Работа компонента оптимизатора, генерирующего альтернативные планы выполнения запроса и производящего оценки порождаемых планов на основе набора правил (STAR-процессора), основывается на наличии четырех структур памяти: массива, в котором хранятся STAR во внутреннем представлении; области, содержащей сгенерированные "хорошие" планы с разными свойствами (понятие хорошего плана и его свойств мы уточним ниже); дерева вызовов, хранящего структуру вызовов STAR; списка указателей еще не обработанных вызовов. Первые две структуры сохраняются в процессе оптимизации в то время, как две последние создаются в рабочей области, выделяемой при каждом вызове STAR-процессора. Массив STAR - внешний параметр оптимизатора, остающийся неизменным в процессе оптимизации; "хорошие" планы, т.е. наиболее дешевые планы выполнения с разными свойствами, порождаются в ходе оптимизации.

Опишем алгоритм, с помощью которого STAR-процессор преобразует вызов STAR в набор альтернативных планов, каждый со своим вектором свойств. Алгоритм состоит из двух фаз: фазы редукции STAR к вложенным LOLEPOP (построение альтернативных планов) и фазы определения свойств каждого плана.

На первой фазе производятся действия, аналогичные действиям макропроцессоров: каждый узел в дереве вызовов заменяется на его определение применением соответствующего правила из STAR-массива с подстановкой аргументов старого узла вместо параметров определения. Все аргументы, являющиеся вызовами, обрабатываются таким же образом. Этот процесс продолжается, пока не будут обработаны все вызовы. Порядок обработки узлов определяется приоритетами, присваиваемыми каждому вызову в списке необработанных вызовов.

При вызове STAR-процессора с TableAccess (EMP, {NAME, ADDRESS}, {EMP.SAL < 30.000, EMP.AGE > 45}) дерево вызовов инициализируется таким образом, как показано на Рис.4. Далее в STAR-массиве ищется STAR с именем TableAccess.


Начало  Назад  Вперед