SQL – execution plan

Перейдя от рассказа про основы SQL к более сложным вещам, я уже успел упомянуть план выполнения (execution plan). Чтобы не останавливаться на этой теме каждый раз, подробнее расскажу о нем в этой статье. Ведь это то, о чем многие разработчики, знакомые с Microsoft SQL Server не один год, либо не знают, либо не придают особого значения.

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

План выполнения

Движку базы данных необходимо знать, в какой последовательности и каким способом соединять таблицы, какие индексы использовать и т.п. Иными словами, перед выполнением запроса необходимо построить (или взять из кэша) план выполнения.

Актуальный план выполнения вы можете посмотреть в Management Studio, нажав “Ctrl+M”. В результате, после выполнения пакета запросов вы увидите вкладку “Execution Plan”, которая и будет использоваться далее в примерах.

Для некоторых задач больше подходит выдача плана выполнения в виде XML (в ранних версиях можно было посмотреть только в текстовом виде), однако в этой статье ограничусь графическими иллюстрациями. Более подробно про настройки вывода плана выполнения можно почитать в статье Displaying Execution Plans by Using the Showplan SET Options. Также есть статья и про графический план выполнения (на мой вкус, слишком сухо изложено и маловато примеров, зато подробно).

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

Также я надеюсь, что вы представляете, что такое кластерные и не-кластерные индексы (это не слишком важно для понимания статьи, однако, если хотите освежить свою память, можете почитать раздел Designing an Index).

План выполнения – простейший вариант

Так выглядит план выполнения простейшего запроса из одной таблицы (я навел мышку на самый левый элемент дерева для отображения информации):

Поясню основную информацию, которая доступна даже для такого простого варианта:

• Query Cost – стоимость запроса в процентном выражении относительно всего пакета запросов. По большому счету, это процентное выражение времени, которое должно потратиться на запрос с точки зрения оптимизатора запросов. В данном случае запрос один, однако для анализа нескольких запросов очень полезно окинуть взглядом их планы выполнения и выявить самые (или неоправданно) затратные.
• Clustered Index Scan – сканирование кластерного индекса часто служит тревожным сигналом (гораздо больше радует глаз Index Seek), однако, в таких случаях как наш, мы просто выбираем все записи из таблицы без фильтра.
• Estimated Subtree Cost – суммарная стоимость всех операций внутри дерева (или поддерева). Могу поделиться своими практическими наблюдениями (которые не претендуют на истину в последней инстанции). Если, как в нашем случае, стоимость порядка 0.1 или меньше, то на запрос обычно не стоит обращать внимания (кроме, конечно, случаев, когда таких запросов очень много или больше нечего оптимизировать :)). Если же стоимость больше 2.0, то, как правило, этот запрос нужно либо оптимизировать, либо хорошо представлять то, как подобные запросы могут отразиться на состоянии системы (особенно в моменты пиковой нагрузки).

План выполнения для нескольких таблиц

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

Для запуска запросов, если вы еще не заметили, потребуется база AdventureWorks. Я пользовался облегченной версией для Microsoft SQL Server 2005. В других версиях может быть разное количество записей и планы выполнения могут быть другими. Иногда может показаться, что оптимизатор при выборе плана руководствуется еще и положением планет, но это не так, чаще всего :)

Важно: SQL, как вы знаете, хорош именно тем, что скрывает от вас подробности своей работы – как именно соединяются таблицы для того или иного запроса и т.п. Обратная сторона медали в том, что у нас нет гарантий, что запрос будет выполнен именно тем способом, который нам нужен. Для обхода этого ограничения можно использовать “хинты”, однако я хочу предостеречь вас от этого – запросы, оптимизированные вручную на некотором наборе данных могут со временем стать проблемой, когда распределение данных поменяется. Поэтому, чаще всего, лучше довериться оптимизатору, только не забывать про актуальную статистику для него.

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

Nested Loops Joins

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

select p.ProductID, p.Name, c.Name
from SalesLT.Product p join SalesLT.ProductCategory c
    on c.ProductCategoryID = p.ProductCategoryID
where c.Name = 'Bike Stands'

Приводит к такому плану выполнения:

Давайте посмотрим, что происходит по этому плану:

1. Получаем набор записей для категорий по фильтру (в нашем случае одна категория). Поскольку категории индексированы по названию, происходит Index Seek, то есть быстрый поиск по индексу.
2. Проходим все записи таблицы товаров. При этом происходит сканирование всей таблицы, потому что нет индекса по категории. В случае, когда мы редко добавляем новые товары и редко меняем категорию товара, зато часто фильтруем по категориям, скорее всего будет целесообразно проиндексировать товары по категории (или даже сделать кластерный индекс, начинающийся с категории). Однако, учитывая небольшую стоимость запроса на данном этапе (я не стал ее показывать на рисунке, но у меня она была меньше 0.1), такую оптимизацию можно оставить “на потом”.
3. Во время прохождения таблицы товаров проверяем, совпадает ли идентификатор категории с результатами шага (1). И, если совпадает, добавляем к результатам запроса. Это и отображено узлом “Nested Loops”.

Прежде чем перейти к обсуждению других вариантов, хочу рассказать историю, которая может быть вам интересна. Несколько лет назад довелось общаться с сотрудником Oracle (плотно занимающимся оптимизацией этой СУБД в американском офисе). Из разговора я, в частности, узнал, что (по крайней мере на тот момент) в Microsoft SQL Server именно Nested Loops были реализованы лучше, чем в других топовых СУБД. А уж подобным заявлениям прямого конкурента обычно всегда имеет смысл верить. Другой вопрос, что про остальные типы соединения я умолчу, чтобы никого не обидеть, да и достоверной информации на сегодняшний момент у меня нет.

Hash joins

Данный вариант более сложен и используется для работы с несортированными данными средних и больших объемов.

В простом случае, когда одно из множеств прилично меньше доступной оперативной памяти, в памяти строится хэш-таблица, в которой затем ищется соответствие для каждой строки из второго множества. Когда же объемы данных становятся слишком большими, задача разбивается на более мелкие (данные предварительно секционируются на диске с помощью той же хэш-функции). Более подробно об этом механизме можно почитать в статье Understanding Hash Joins.

Пример запроса, который приводит к hash join такой:

select p.ProductID, p.Name, c.Name
from SalesLT.Product p join SalesLT.ProductCategory c
    on c.ProductCategoryID = p.ProductCategoryID
where c.Name like '%Bike%'

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

Давайте посмотрим, что происходит:

1. Сначала ищем категории по шаблону, который начинается с “%”, что автоматически не дает использовать индекс, однако, мы хотя бы не сканируем всю таблицу, а считываем только индекс (потому что фильтруем по названию, а значение кластерного ключа содержит любой не-кластерный индекс). Все значения заносим в хэш-таблицу (в данном случае, практически наверняка в оперативной памяти).
2. Затем сканируем таблицу товаров.
3. При этом получаем соответствующую категорию из хэш-таблицы.

Хотя операции получаются более сложными да и количество данных больше, чем в примере с Nested Loops, стоимость запроса все равно невысока (у меня она была чуть больше 0.1). Это объясняется небольшим количеством исходных данных – тысяча строк для промышленной СУБД – это смешно (если, конечно, железо нормальное).

Merge joins

Этот вариант применяется, когда данных слишком много для применения Nested Loops, и элементы обоих множеств отсортированы по столбцу соединения. Когда сортировка отсутствует, иногда бывает целесообразно предварительно отсортировать множество и свести ситуацию к предыдущей. В последней же ситуации, оптимизатору приходится выбирать между Merge и Hash joins (метод hash joins часто приводит к меньшей стоимости запроса, потому что сортировка довольно затратная операция).

Данный метод основан на том, что в случае сортировки обоих множеств по столбцу соединения, для “inner join”, например, мы просто можем параллельно сканировать оба множества и отбрасывать “кусок”, значение в котором меньше, чем значение из другого множества (и не встретилось в другом множестве ранее). Более подробно, можно почитать об этом в статье Understanding Merge Joins. Если же все равно останутся сомнения в правильности понимания этого метода, рекомендую написать пример на высокоуровневом языке программирования, использующий, скажем, два отсортированных массива целых чисел.

Пример использования Merje joins можно получить, убрав фильтр из предыдущего запроса:

select p.ProductID, p.Name, c.Name
from SalesLT.Product p join SalesLT.ProductCategory c 
    on c.ProductCategoryID = p.ProductCategoryID

При этом получаем такой план выполнения:

Последовательность действий здесь следующая:

1. Сканируем все товары и получаем список товаров, отсортированный по категории (операции Scan и Sort).
2. Сканируем таблицу категорий по кластерному индексу (здесь дополнительная сортировка не нужна, потому что строки уже хранятся в нужном порядке).
3. Соединяем множества по алгоритму, описанному до примера.

Обещанные подводные камни :)

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

Вот приблизительно также и получается в случае отсутствия статистики или ее неактуальности – оптимизатор запросов может выдать неправильный план выполнения, но executor, уже на этапе выполнения, может понять что что-то не так и выбрать другую стратегию. А может и не выбрать… Так что рекомендую почитать статью Using Statistics to Improve Query Performance.

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

Планы выполнения могут строиться долго и поэтому кэшируются. Это хорошая новость. Плохая новость в том, что даже сравнительно простые не параметризованные запросы могут забить весь кэш планов выполнения за счет разных значений параметра. Дело в том, что план выполнения кэшируется по полному тексту, в результате, тысячи мелких “плохих” запросов могут вытеснить из кэша планы выполнения важных и сложных запросов, что приведет к значительному падению производительности.

Частичное решение подобных проблем описано в статье Simple Parameterization и других связанных статьях раздела Execution Plan Caching and Reuse.

Резюме

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

Для более углубленного изучения темы плана выполнения и оптимизации запросов могу порекомендовать раздел MSDN Analyzing a Query (для быстрого старта хорошо подойдет Checklist for Analyzing Slow-Running Queries). Если же этого покажется недостаточным, можно подойти к делу более фундаментально, почитав раздел Performance (Database Engine) и его подразделы.

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

Если у вас есть замечания, пожелания или новые темы – пишите в комментариях или на olegaxenow.reformal.ru. Постараюсь учесть.