4. 32.План выполнения запросов. Выбор плана.

Выбор и оценка альтернативных планов выполнения запроса.

До этого этапа все логические преобразования оставляли внутренне представление запроса непроцедурным.

Процедурным представлением или планом выполнения запроса называется такое его представление, в котором детализирован порядок выполнения операций доступа к базе данных физического уровня. До выполнения запроса необходимо сформировать процедурное представление запроса; однако, исходя из специфики языка SQL, выбор процедурного представления запроса является неоднозначным (могут существовать варианты решения), целесообразно найти вреди альтернативных вариантов лучший, определяемый построенной функцией оптимальности.

Критерием выбора плана выполнения запроса является минимизация функции стоимости. При обработке запроса на стадии, следующей за логической оптимизацией, решаются две задачи:

1. исходя из внутреннего представления запроса и информации, характеризующей управляющие структуры базы данных, выбрать набор потенциально возможных планов выполнения данного запроса;

2. оценить стоимость выполнения запроса для каждого альтернативного плана в соответствие с заданным набором критериев и выбрать план с наименьшей стоимостью.

Генерация планов.

Компонент оптимизатора, ведающий порождением множества альтернативных планов выполнения запроса, базируется на стратегиях декомпозиции запроса на элементарные составляющие и стратегиях выполнения этих составляющих. Первая группа стратегий определяет пространство поиска оптимального плана выполнения запроса, вторая направлена на то, чтобы в этом пространстве действительно находились эффективные планы выполнения запроса. Ключом к обеспечение эффективного выполнения сложного запроса является наличие элементарных составляющих (однако оптимизатор пользуется заданными стратегиями).

Оценка стоимости плана запроса (метод cost-based).

После генерации множества планов выполнения запроса на основе разумных стратегий декомпозиции и эффективных стратегий выполнения элементарных операций нужно выбрать один план, в соответствии с которым будет происходить реальное выполнение запроса. В случае неверно выбранного плана выполнения запроса работа системы будет неэффективна.

В одних условиях можно считать, что эффективность выполнения запроса определяется временем его выполнения, т.е. реактивностью системы по отношению к обрабатываемым ею запросам. В других условиях определяющей является общая пропускная способность системы по отношению к группе параллельно выполняемых запросов.

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

Общая оценка плана выполнения запроса производится в итерационном процессе, начиная с элементарных операций над хранимыми отношениями.