План выполнения запроса

План выполне́ния запро́са — последовательность операций, необходимых для получения результата SQL-запроса в реляционной СУБД.

План в целом разделяется на две стадии:

• Выборка результатов;
• Сортировка и группировка, выполнение агрегаций.

Сортировка и группировка — это опциональная стадия, которая выполняется, если не найдено путей доступа для получения результата в запрошенном порядке.

Выборка результатов выполняется следующими способами:

• Вложенные циклы;
• Слияние.

Вложенные циклы

Основная статья: Алгоритм соединения вложенными циклами

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

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

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

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

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

Слияние

Основная статья: Алгоритм соединения слиянием сортированных списков

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

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

За счет того, что в индексах данные отсортированы, слияние дешевле вложенных циклов, но план выполнения не может начинаться со слияния.

Пример

Например, для такого запроса, как

SELECT 
  FROM Продажи
  ORDER BY Номер_продавца

может быть создан такой план выполнения:

1. Сканирование кластерного индекса для первичного ключа таблицы Продажи.
2. Сортировка результатов шага 1 по столбцу Номер_продавца.
3. Возврат приложению результатов шага 2.

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

Изучение планов выполнения запросов, созданных оптимизатором, позволяет решить, как ускорить выполнение запроса — изменить сам запрос или создать в базе данных дополнительный индекс. Некоторые СУБД позволяют явно влиять на то, как именно оптимизатор формирует план, для чего имеется особый язык подсказок.

См. также

• Оптимизация запросов
• Кэш запросов

Литература

• Майкл Оутей, Поль Конте Эффективная работа: SQL Server 2000. — СПб.: Питер, 2002, с. 992. ISBN 966-552-111-X, ISBN 5-94723-056-9

Ссылки

• С. Кузнецов. Методы оптимизации выполнения запросов в реляционных СУБД (рус.)