1. 29.Оптимизация sql-запросов. Общие сведения.

Общее назначение оптимизатора состоит в выборе наиболее эффективной стратегии вычисления реляционного выражения.

Хороший оптимизатор обладает большим объемом полезной информации, которая

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

определенными статистическими данными, в частности акими как: количество значений в

каждом домене; текущее количество значений в каждой базовой переменной-отношении; текущее количество различающихся значений для каждого атрибута в базовой переменной-отношении; количество вхождений каждого значения в каждом из атрибутов и т.п.

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

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

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

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

17.3. Оптимизация запросов

Рассмотрим четыре стадии процесса оптимизации запросов, который схематически представлен на рис. 17.1.

1.Преобразование запроса во внутреннюю форму.

2.Преобразование запроса в каноническую форму.

3.Выбор потенциальных низкоуровневых процедур.

4.Генерация различных вариантов планов вычисления запроса и выбор плана с ми­нимальными затратами.

Перейдем к подробному рассмотрению каждой стадии процесса оптимизации.

Стадия 1. Преобразование запроса во внутреннюю форму

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

Стадия 2. Преобразование запроса в каноническую форму

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

Чтобы преобразовать результаты выполнения стадии 1 в некоторую эквивалентную, но более эффективную форму, оптимизатор ис­пользует определенные и хорошо известные правила преобразования, или законы.

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

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

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

Для каждой низкоуровневой операции оптимизатор имеет набор низкоуров­невых процедур реализации.

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

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

Стадия 4. Генерация различных вариантов планов вычисления запроса и выбор плана с минимальными затратами

На последней стадии процесса оптимизации создается набор потенциальных планов запроса, после чего следует выбор лучшего (т.е. наименее дорогого) плана выполнения за­проса. Каждый план выполнения строится как комбинация некоторого набора процедур реализации, причем каждой низкоуровневой операции в запросе соответствует одна проце­дура.

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