Метод оптимизации, основанный на стоимости

При использовании этого метода оптимизатор сначала строит несколько возможных планов выполнения запроса (обычно, 2-3 плана). Для выбора наиболее перспективных планов он применяет некоторые эвристики, т.е. правила, полученные опытным путем. Эти правила позволяют сузить пространство поиска оптимального плана благодаря тому, что неэффективные планы отбрасываются в самом начале и не рассматриваются. Примером эвристики может послужить такое правило: хорошим является такой план, в котором селекция производится на раннем этапе выполнения запроса. Эвристики часто основаны на законах преобразования операций реляционной алгебры.

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

Из множества возможных планов выполнения запроса оптимизатор в соответствии с критерием выбирает лучший план (рис. 7.3).

В качестве критерия оптимизации может выступать:

Наилучшая общая производительность системы. Вообще говоря, её можно достичь, если из всех планов выбирать те, которые требуют меньше всего ресурсов (памяти и центрального процессора). Это позволит увеличить степень параллельности работы системы и повысить общую производительность, хотя при этом время выполнения отдельных запросов увеличится.

Рис.7.3. Построение плана выполнения запроса в методе оптимизации по стоимости

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

Стоимость плана выполнения запроса определяется на основании сведений о распределении данных в таблицах, к которым обращается команда, и связанных с ними кластеров и индексов. Эти сведения о распределении значений данных называются статистикой и хранятся в словаре-справочнике данных. Для таблицы статистика может включать в се-бя:

общее количество блоков данных (страниц памяти), выделенных таблице;
количество пустых блоков данных (страниц памяти);
количество записей в таблице;
среднюю длину записи в таблице;
среднее количество записей на блок (страницу) памяти.

Для каждого индекса статистика может содержать такие данные, как:

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

Распределение значений в столбце может быть отражено с помощью гистограммы, которая также входит в статистику. Для этого всё множество значений столбца упорядочивается и разбивается на N интервалов. На рис. 7.4 приведено разбиение на N =10 интервалов множества значений некоторого столбца F. Для равномерного распределения это означает, что в первых 10% записей это поле имеет значение от 1 до 10, в следующих 10% записей – от 11 до 20 и т.д.

Рис.7.4. Примеры равномерного (а) и неравномерного (б) распределения значений

Гистограмма помогает оценить объём данных, удовлетворяющих усло-вию запроса. На рис. 7.4,б представлено неравномерное распределение дан-ных для некоторого столбца F. В словарь-справочник данных записываются полученные значения (1, 4, 4, 5, 6, 10, 11, 20, 35, 60, 100). При анализе запроса, например, с условием (F<=5) система сможет по этой гистограмме определить, что через индекс придётся выбрать не менее 30% записей таблицы.

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

Построение гистограммы бесполезно в следующих случаях:

значения столбца распределены равномерно;
столбец не используется в предикатах запросов;
значения столбца уникальны и используются только в предикатах эквива-лентности.

Существуют различные подходы к порядку сбора статистики. Неко-торые СУБД постоянно собирают статистическую информацию, но это может уменьшить быстродействие системы. Другие позволяют осуществлять сбор статистики периодически, например, в период минимальной загрузки системы. Третьи предлагают администратору специальные средства для сбора статистики, которые запускаются интерактивно по его команде. В последнем случае в обязанность администратора (администратора данных или приложений) входит выбор таблиц для анализа и периодическое обновление статистики данных.