Порядок выполнения выборки

Лекция 2

Чтобы показать, как формируется результат выполнения оператора SELECT, рассмотрим схему его выполнения.

Шаг 1. Выполняется на уровне предложения FROM. Вычисляется прямое декартово произведение всех таблиц, указанных в обязательном разделе FROM. В результате получается обобщенная таблица Table_1.

Шаг 2. Задается условиями, которые определены в предложении WHERE. Если в операторе SELECT присутствует раздел WHERE, то сканируется таблица Table_1, полученная при выполнении первого шага. При этом для каждой строки этой таблицы вычисляется условное выражение, указанное в предложении WHERE. Строка включается в результат, если для неё условное выражение возвращает значение ИСТИНА. Если в условном выражении участвуют вложенные подзапросы, то они вычисляются в соответствии с такой же концептуальной схемой. В результате шага 2 получаем таблицу Table_2. Если предложение WHERE отсутствует, то осуществляется переход к шагу 3 (принимается, что Table_1 переходит в Table_2 без изменения).

Шаг 3. Определяется предложением GROUP BY. Если присутствует GROUP BY, то строки таблицы Table_2, полученной на втором шаге, группируются в соответствии со списком группировки раздела GROUP BY. В результате выполнения третьего шага получаем таблицу Table_3. Если же данный раздел опущен, то выполняется переход к шагу 4 (принимается, что Table_2 переходит в Table_3 без изменения).

Шаг 4. Выполняется на уровне раздела HAVING. Если этот раздел присутствует, то группы, не удовлетворяющие заданному в нем условному выражению, исключаются. В результате шага 4 образуется таблица Table_4. Если раздел HAVING опущен, то идет переход к следующему шагу (принимается, что Table_3 переходит в Table_4 без изменения).

Шаг 5. Определяется на уровне оператора SELECT. Каждая группа, полученная на четвертом шаге, генерирует одну строку результата следующим образом. Вычисляются все скалярные выражения, указанные в разделе SELECT, причем они должны быть одинаковыми для всех строк внутри каждой группы. Для каждой группы вычисляются значения агрегатных функций, приведенных в разделе SELECT. Если раздел GROUP BY отсутствует, но в SELECT есть агрегатные функции, то считается, что имеется всего одна группа. Если нет ни раздела GROUP BY, ни агрегатных функций, то считается, что имеется столько групп, сколько строк отобрано к данному моменту.

В результате пятого шага образуется таблица Table_5, содержащая столько столбцов, сколько элементов приведено в списке выбора SELECT, и столько строк, сколько отобрано групп.

Шаг 6. Выполняется на уровне раздела ORDER BY. Если в операторе SELECT присутствует этот раздел, то строки таблицы Table_5, полученной на предыдущих шагах, упорядочиваются в соответствии со списком, приведенным в данном разделе.

Выполнение данного концептуального алгоритма вычисления результата оператора SELECT весьма громоздко. Поэтому на самом деле в реляционных СУБД имеется оптимизатор, основным предназначением которого является нахождение такого оптимального алгоритма выполнения запроса, который гарантирует получение правильного результата. Работа этого оптимизатора выглядит следующим образом:

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

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

3. Генерация оптимизатором планов выполнения запроса и выбор оптимального плана. Каждый план выполнения строится как комбинация низкоуровневых процедур доступа к данным таблицы. Из всех сгенерированных планов выбирается тот, который обладает минимальной стоимостью. При этом анализируются сведения о наличии у таблиц индексов, статистические данные о распределении значений в таблицах и т.д. Стоимость плана – это, как правило, сумма стоимостей выполнения отдельных низкоуровневых процедур, которые используются для его реализации. В стоимость выполнения отдельной процедуры могут входить оценки количества обращений к дискам, степень загруженности процессора, а также другие параметры.

4. Выполнение плана запроса. На этом шаге план, выбранный на предыдущем шаге, передается на реальное выполнение.

Качество конкретной СУБЯД во многом определяется качеством ее оптимизатора. Хороший оптимизатор может повысить скорость выполнения запроса на несколько порядков. Качество оптимизатора определяется тем, какие методы преобразований он может использовать, какой статистической и иной информацией о таблицах он располагает, какие методы для оценки стоимости выполнения плана он знает.

Дата добавления: 2014-01-11