В данной статье рассматриваются особенности запросов на выборку данных, виды индексов, использование планов запросов, различные подходы к оптимизации запросов. Во второй части статьи «Оптимизация SQL-запросов (Часть 2)» рассматриваются рекомендации по разработке оптимальной структуры БД.
Введение
Все более-менее сложные веб-приложения взаимодействуют с базами данных. Причем получение данных из базы является одним из узких мест приложения. Таким образом, оптимизация запросов к базе способна существенно повысить производительность веб-приложения в целом.
1. Демонстрационная база данных
Для демонстрации запросов в данном докладе потребуется база данных. Допустим, необходимо автоматизировать следующую предметную область: у торгового предприятия есть различные товары, которые продаются различным заказчикам. Необходимо обеспечить хранение данных по заказам клиентам, включая заказанные товары, и о статусах заказа, развернутых во времени. Создадим упрощенную базу данных.
БД имеет следующую структуру: 
База наполнена тестовыми данными:
- Status — 3 записи
- Customer — 3 записи
- Product — 10 записей
- Order — 3 млн. записей.
- OrderStatus — 9 млн. записей.
- OrderProduct — 2,5 млн. записей
2. Запросы на выборку данных
Запросы на выборку данных реализуются с помощью конструкции SELECT языка SQL.
Запрос в MS SQL имеет следующий синтаксис:
2.1. Типы соединений таблиц
Если запрос адресован к нескольким таблицам БД, то выполняется соединение этих таблиц по определенным полям.
Существует несколько типов соединений:
Внутреннее (INNER JOIN)
Внешнее левое/правое (LEFT/RIGHT JOIN)
Перекрестное (CROSS JOIN)
(Используется редко)
2.2. Вложенные запросы
Вложенный запрос представляет собой запрос типа select from select
Пример:
2.3. Короткие и соотнесенные запросы
Пример короткого селекта:
Пример соотнесенного запроса:
В MS SQL короткие и соотнесенные запросы могут быть реализованы с помощью конструкции OUTER/CROSS APPLY.
Существует два типа оператора APPLY: CROSS APPLY и OUTER APPLY. Оператор CROSS APPLY возвращает только строки из внешней таблицы, которые создают результирующий набор из возвращающей табличное значение функции. Оператор OUTER APPLY возвращает и строки, которые формируют результирующий набор, и строки, которые этого не делают, со значениями NULL в столбцах, созданных возвращающей табличное значение функцией.
3. Индексы
3.1. Виды индексов MS-SQL
В MS SQL Индексы могут быть двух типов: кластерные и не кластерные.
Если упрощенно, то кластерный индекс отличается от не кластерного тем, что в листьях этого индекса содержатся не ссылки на записи в таблице, а сами записи. Таким образом, для таблицы допустим только один кластерный индекс.
Скорость доступа к строкам при указании условия where, совпадающего с условием индексирования для кластерного индекса, будет выше, чем при поиске записей по простому индексу.
Если в кластерный индекс включены часто обновляемые поля, то это отрицательно скажется на производительности, т. к. обновления будут приводить к логическому переупорядочиванию данных.
Если из таблицы, имеющей кластерный индекс, часто удаляются записи, то это приводит к сильной фрагментации таблицы.
MS SQL по умолчанию создает кластерные индексы по первичному ключу.
3.2. Ограничения MS SQL при создании индексов
При создании индекса максимальная суммарная длина полей допускается равной 900 байт. Причем индекс может быть создан по полям, типы которых допускают большую длину полей, но при этом хранящиеся данные обязательно должны быть меньше.
Т.е., например, в таблице имеется 2 поля varchar(500) , MSSQL допускает создание индекса при условии, что реальная длина записей по этим полям не превышает 900. При наличии такого индекса в таблице, при попытке вставки (или обновления) данных, если сумма реальных полей будет превышать 500 байт, то будет выдано сообщение об ошибке.
Для хранения каждого символа в типах nvarchar и nchar MS SQL использует 2 байта.
4. Планы запросов
В реляционной СУБД оптимальный план выполнения запроса — это такая последовательность применения операторов реляционной алгебры к исходным и промежуточным отношениям, которое для конкретного текущего состояния БД (её структуры и наполнения) может быть выполнено с минимальным использованием вычислительных ресурсов.
4.1. Анализ плана запроса
Ядро SQL Server Database Engine может показывать, каким образом оно переходит к таблицам и использует индексы для доступа к данным. Это называется выводом плана выполнения. Для проведения анализа медленно выполняемого запроса полезно изучить план выполнения запроса, чтобы определить причину проблемы.
Планы выполнения запросов в MS SQL отображаются cредой SQL Server Management Studio. При этом отображается наилучший план выполнения, используемый ядром Database Engine для отдельных инструкций языка DML и Transact-SQL. В этом плане содержатся сведения о процессе компиляции хранимых процедур и о вызовах хранимых процедур произвольной глубины вложенности. Например, при выполнении инструкции SELECT можно увидеть, что Database Engine выполняет просмотр таблицы для получения данных. Выполнение инструкции SELECT может также показать, что просмотр индекса будет использоваться, если Database Engine определит, что просмотр индекса является наиболее быстрым способом получения данных из таблицы.
Таким образом, выбор оптимального плана во многом зависит от наличия в базе индексов и их оптимальности. 
При выполнении запроса в MSSQL есть возможность поиска “отсутствующих” индексов. Т. е. MS SQL подсказывает, какие индексы можно создать, чтобы данный конкретный запрос выполнялся быстрее.
Пример:
Запрос выдает рекомендации на создание индекса:
4.2. Способы применения индекса в планах запроса
Основные типы получения записей индекса это Seek и Scan.
Index Scan получает все записи индекса, указанного в столбце Argument. Если необязательный предикат WHERE:() появится в столбце Argument, то возвращаются только те строки, которые удовлетворяют условию, указанному в этом предикате.
Оператор Index Seek использует возможности поиска по индексам для получения строк из индекса. С самого начала поиск обрабатывает только те строки, которые квалифицированы, и страницы, которые содержат эти квалифицированные строки, поэтому стоимость пропорциональна числу квалифицированных строк и содержащих их страниц, а не к общему числу строк в таблице. Таким образом, поиск является более эффективной стратегией, если мы имеем дело с очень селективным поисковым предикатом; то есть если мы имеем поисковый предикат, который отсекает большую часть таблицы.
4.3. Способы изменения плана
В MS SQL при выполнении запросов можно указать специальные «подсказки» (hint), с помощью которых можно повлиять на план запроса.
Оптимизатор запросов SQL Server обычно автоматически выбирает наилучший план выполнения запроса. Поэтому подсказки, в том числе , рекомендуется использовать только опытным пользователям и администраторам базы данных в случае крайней необходимости.
Примечание. В некоторых СУБД, например Firebird, можно косвенно влиять на план запроса, например добавлением «+0» к полю таблицы. В этом случае оптимизатор перестает использовать индекс.
4.4. Кэширование и повторное использование плана
В SQL Server есть пул памяти, предназначенный для хранения планов выполнения и буферов данных. Процентное соотношение размера пула, выделенного для планов выполнения и буферов данных, динамически изменяется в зависимости от состояния системы. Часть пула памяти, используемого для хранения планов выполнения, называется кэшем процедур.
В SQL Server планы выполнения состоят из следующих основных компонентов.
План запроса. Тело плана выполнения является структурой данных только для чтения, которая предназначена для использования любым числом пользователей. Оно называется планом запроса. План запроса не содержит контекста пользователя.
Контекст выполнения. Для каждого пользователя, который в настоящий момент выполняет запрос, имеется структура данных, которая содержит данные, относящиеся к данному выполнению, например значения параметров. Эта структура данных называется контекстом выполнения. Структуры данных контекста выполнения являются повторно используемыми. Если пользователь выполняет запрос и одна из структур не используется, она повторно инициализируется контекстом нового пользователя.
4.5. Проблема параметров при кэшировании запросов
Если к серверу выполняется несколько однотипных параметризованных запросов, то сервер строит план только для первого запроса, далее этот план попадает в кэш, и остальные запросы выполняются с уже кэшированным планом.
Рассмотрим 2 запроса:
Для выполнения этих запросов используются разные планы, т. к. при построении плана, MS SQL анализирует количество возвращаемых данных.
Если данный запрос сделать параметризованным:
то план запроса будет определятся самым первым запросом.
Это демонстрирует следующий скрипт:
Таким образом, оптимальный план, построенный по первому параметризованному запросу, из-за кэширования будет распространен на остальные запросы, где этот план может оказаться, мягко говоря, не совсем оптимальным.
5. Подходы к оптимизации запросов
5.1. Поиск неоптимальных запросов
Критичные запросы. Выполняются достаточно редко, но их длительное время выполнения заметно невооруженным взглядом.
Часто выполняемые запросы, которые сами по себе не занимают много времени, но из-за того, что выполняются часто, общее время их выполнения становится критичным.
К сожалению, самый надежный метод довольно сложен и предусматривает отслеживание всех выполненных запросов к серверу с их последующей группировкой.
Существует более простой, но не столь надежный метод. Можно положиться на статистику всех запросов, которая хранится в кэше плана выполнения, и опросить их с использованием динамических административных представлений.
5.2. Статистика индексов
Для индекса существует понятие плотности распределения. Если каждое значение в таблице уникальное, то плотность будет 1/ . Например, если в таблице 100 записей, то плотность будет равна 1%. Теория говорит, что чем меньше плотность, тем лучше – это увеличивает избирательность, а, следовательно, и ценность построенного индекса.
Например, если колонка содержит только 3 значения, плотность распределения будет равна 33.3%, что показывает бесполезность построения индекса по данному полю. Индексы занимают место на диске и в оперативной памяти и отнимают быстродействие. В идеале, самый лучший индекс имеет плотность распределения равную единице, деленной на количество записей в таблице — все записи уникальны.
При построении индексов, обращайте внимание на плотность распределения – если она превышает 10%, то индекс можно считать бесполезным. Сканирование по таблице в таком случае будет более эффективным.
Для просмотра статистики индекса используется команда:
5.3. Фильтрация в индексах
Фильтруемый индекс — это оптимизированный некластеризованный индекс, особенно подходящий для запросов, осуществляющих выборку из хорошо определенного подмножества данных. Он использует предикат фильтра для индексирования части строк в таблице. Хорошо спроектированный фильтруемый индекс позволяет повысить производительность запросов, а также снизить затраты на обслуживание и хранение индексов по сравнению с полнотабличными индексами.
Пример. Отберем все строки продуктов, где количество больше 9900.
Создадим индекс по полю Quantity:
Создадим фильтрованный индекс:
Кроме того, фильтрованный индекс создается гораздо быстрее.
5.4. Индексы с включенными полями
Индекс с неключевыми столбцами может значительно повысить производительность запроса, когда все столбцы запроса включены в индекс как ключевые или неключевые. Производительность повышается благодаря тому, что оптимизатор запросов может найти все значения столбцов в этом индексе. При этом нет обращения к данным таблиц или кластеризованных индексов, что приводит к меньшему количеству дисковых операций ввода-вывода.
Пример. Допустим, необходимо найти номера и даты заказов по определенному поставщику.
Запрос:
Создаем индекс на поле CustomerId:
Результат такой же. MSSQL индекс не использует. Оптимизатор решает, что быстрее сделать Scan по первичному ключу, т.к. селективность индекса маленькая.
Создаем индекс с включенными полями:
Время выполнения запроса уменьшается, индекс попадает в план:
5.5. Дополнительные команды при создании индексов
Команда CREATE INDEX имеет дополнительные параметры. Рассмотрим некоторые из них, которые в дальнейшем могут повлиять на производительность запросов.
ASC|DESC
ASC значит что индекс будет построен по возрастанию ключей. DESC соответственно – по убыванию. Эта опция не дает никакой разницы на поиск данных, но оказывает существенное влияние на скорость выполнения ORDER BY опции в запросах.
Пример.
SORT_IN_TEMPDB
Полезна при создании индексов. Эта опция может увеличить производительность системы во время создания индексов. Индексы создаются в два этапа. На первом создается временный набор данных с отсортированными ключами для некластерного индекса. На втором – окончательный результат переносится на место его хранения в базе данных. Без указания данной опции временный результат создается в той же file group, где и будет создан индекс. При указанной опции временный результат будет находиться в базе данных Tempdb. Преимущества: индекс будет менее фрагментирован, временную базу можно поместить на другой диск и тем самым увеличить скорость чтения/записи. Недостаток: требуется больше памяти на дисках и надо уделять дополнительное внимание базе данных Tempdb.
5.6. Оптимизация композитных индексов
В создании композитного (сложного) индекса участвуют несколько полей таблицы. При создании индекса следует обращать внимание на порядок следования полей в индексе.
Например, если создается индекс по полям Field1, Field2, то он может быть применен только в запросе, где в критериях используются оба этих поля. Также этот индекс будет полезен для условий, построенных для одного Field1. Для одного Field2 этот индекс не может быть применен.
Если в дополнение к индексу по полям Field1, Field2 добавить индекс по полям Field2, Field1, то SQL Server при построении плана запроса будет анализировать, какой из них более селективен в применении к ограничениям на условия запроса. Последний момент в построении композитного индекса по полям Field1, Field2 – он не равен сумме индексов по указанным полям. В случае, когда в запросе могут быть использованы оба поля как критерий поиска при раздельных индексах по полям, будет построено пересечение по индексам, что медленнее чем выборка из композитного индекса.
Примечание. В некоторых СУБД, например Firebird, применение нескольких индексов в запросе для одной таблицы ведет к существенному снижению производительности.
Пример. Отберем заказы определенного клиента, начиная с указанной даты.
План показывает сканирование по первичному ключу. MS SQL рекомендует создание композитного индекса по коду поставщика и дате. 
Создадим индекс:
Тот же самый запрос стал выполняться быстрее.
Уберем из условия отбор по дате:
Индекс по-прежнему используется.
Теперь вернем условие по дате, но уберем условие по клиенту:
Индекс используется, только вместо более быстрой операции Seek используется Scan.
5.7. Общие рекомендации по проектированию индексов
Большое количество индексов в таблице снижает производительность инструкций INSERT, UPDATE, DELETE и MERGE, потому что при изменении данных в таблице все индексы должны быть изменены соответствующим образом.
Большое число индексов может повысить производительность запросов, которые не изменяют данных, таких как инструкции SELECT, поскольку у оптимизатора запросов будет больший выбор индексов при определении самого быстрого способа доступа.
Индексирование маленьких таблиц может оказаться не лучшим выбором, так как поиск данных в индексе может потребовать у оптимизатора запросов больше времени, чем простой просмотр таблицы. Следовательно, для маленьких таблиц индексы могут вообще не использоваться, но тем не менее их необходимо поддерживать при изменении данных в таблице.
5.8. Выбор типа соединения таблиц
Выбор типа соединения таблиц в запросе (INNER/LEFT/RIGHT) зависит от задачи. Практика показывает, что если в запросе, который подразумевает однозначное соединение одной таблицы с другой, нет большой разницы, использовать INNER или LEFT JOIN. Оптимизатор генерирует для таких запросов одинаковый план.
Пример:
5.9. Рекомендации по оптимизации запросов от Microsoft
Ниже перечислены случаи, когда SQL Server не в состоянии точно вычислить мощность. Это приводит к неточному определению стоимости, что, в свою очередь, может привести к созданию неоптимальных планов запросов. Если избегать применения таких конструкций, можно повысить производительность выполнения запросов. Иногда в таких случаях доступны альтернативные формулировки запросов и другие средства, помогающие решить эту проблему.
- Запросы с предикатами, которые содержат операторы сравнения столбцов одной и той же таблицы.
- Запросы с предикатами, использующими операторы, и выполнение одного из следующих условий:
- отсутствует статистика для столбца, указанного с любой стороны от оператора;
- распределение значений в статистике неоднородно, а запрос выполняет поиск весьма ограниченного набора значений. Эта ситуация особенно вероятна, если оператор не является оператором равенства (=);
- предикат использует оператор неравенства (!=) или логический оператор NOT.
Для повышения производительности перечисленных типов запросов можно попробовать предпринять следующие меры:
Постройте индексы или статистику для столбцов, участвующих в запросе.
Попробуйте использовать вычисляемые столбцы или перепишите запрос, если он содержит операторы, которые сравнивают или производят арифметические операции над двумя и более столбцами. Например, в следующем запросе сравниваются значения в двух столбцах:
Можно повысить производительность, добавив вычисляемый столбец Col3 к таблице MyTable, который подсчитывает разницу между Col1 и Col2 (Col1 минус Col2). Затем переписать запрос:
Возможно, производительность еще больше повысится, если построить индекс для столбца MyTable.Col3.
Во второй части статьи «Оптимизация SQL-запросов (Часть 2)» рассматриваются рекомендации по разработке оптимальной структуры БД.
Дата поста: 01-10-2012
Порыскав на досуге по тырнету, удивился, что специальных статей-руководств по оптимизации SQL-запросов нет. Перелистав различную информацию и книги, я постараюсь дать некоторое руководство к действию, которое поможет научиться писать правильные запросы.
1. Оптимизация таблиц.
Необходима, когда было произведено много изменений в таблице: либо удалена большая часть данных, либо много изменений со строками переменной длины — text, varchar, blob. Дело в том, что удалённые записи продолжают поддерживаться в индексном файле, и при последующей вставке новых записей используются позиции старых записей. Чтобы дефрагментировать файл с данными, используюется команда OPTIMIZE.
Не стоит забывать, что во время выполнения оптимизации, доступ к таблице блокируется.
2. Перестройка данных в таблице.
После частых изменений в таблице, данная команда может повысить производительность работы с данными. Она перестраивает их в таблице и сортирует по определённому полю.
3. Тип данных.
Лучше не индексировать поля, имеющие строковый тип, особенно поля типа TEXT. Для таблиц, данные которых часто изменяются, желательно избегать использования полей типа VARCHAR и BLOB, так как данный тип создаёт динамическую длину строки, тем самым увеличивая время доступа к данным. При этом советуют использовать поле VARCHAR вместо TEXT, так как с ним работа происходит быстрее.
4. NOT NULL и поле по умолчанию.
Лучше всего помечать поля как NOT NULL, так как они немного экономят место и исключают лишние проверки. При этом стоит задавать значение полей по умолчанию и новые данные вставлять только в том случае, если они от него отличаются. Это ускорит добавление данных и снизит время на анализ таблиц. И стоит помнить, что типы полей BLOB и TEXT не могут содержать значения по умолчанию.
5. Постоянное соединение с сервером БД.
Позволяет избежать потерь времени на повторное соединение. Однако стоит помнить, что у сервера может быть ограничение на количество соединений, и в том случае, если посещаемость сайта очень высокая, то постоянное соединение может сыграть злую шутку.
6. Разделение данных.
Длинные не ключевые поля советуют выделить в отдельную таблицу в том случае, если по исходной таблице происходит постоянная выборка данных и которая часто изменяется. Данный метод позволит сократить размер изменяемой части таблицы, что приведёт к сокращению поиска информации.
Особенно это актуально в тех случаях, когда часть информации в таблице предназначена только для чтения, а другая часть — не только для чтения, но и для модификации (не забываем, что при записи информации блокируется вся таблица). Яркий пример — счётчик посещений.
Есть таблица (имя first) с полями id, content, shows. Первое ключевое с auto_increment, второе — текстовое, а третье числовое — считает количество показов. Каждый раз загружая страницу, к последнему полю прибавляется +1. Отделим последнее поле во вторую таблицу. Итак, первая таблица (first) будет с полями id, content, а вторая (second) с полями shows и first_id. Первое поле понятно, второе думаю тоже — отсыл к ключевому полю id из первой таблицы.
Теперь постоянные обновления будут происходить во второй таблице. При этом изменять количество посещений лучше не программно, а через запрос:
А выборка будет происходить усложнённым запросом, но одним, двух не нужно:
Стоит помнить, что это не очень актуально для сайтов с малой посещаемостью и малым количеством информации.
7. Имена полей,
по которым происходит связывание, к примеру, двух таблиц, желательно, чтобы имели одинаковое название. Тогда одновременное получение информации из разных таблиц через один запрос будет происходить быстрее. Например, из предыдущего пункта желательно, чтобы во второй таблице поле имело имя не first_id, а просто id, аналогично первой таблице. Однако при одинаковом имени становится внешне не очень наглядно что, куда и как. Поэтому совет на любителя.
8. Требовать меньше данных.
При возможности избегать запросов типа:
Запрос не эффективен, так как скорее всего возвращает больше данных, чем необходимо для работы. Вариантом лучше будет конструкция:
Тут же сделаю добавление о желательности использования LIMIT. Данная команда ограничивает количество строк, возвращаемых запросом. То есть запрос становится "легче"; и производительнее.
Если стоит LIMIT 10, то после получения десяти строк запрос прерывается.
Если в запросе применяется сортировка ORDER BY, то она происходит не по всей таблице, а только по выборке.
Если использовать LIMIT совместно с DISTINCT, то запрос прервётся после того, как будет найдено указанное количество уникальных строк.
Если использовать LIMIT 0, то возвращено будет пустое значение (иногда нужно для определения типа поля или просто проверки работы запроса).
9. Ограничить использование DISTINCT.
Эта команда исключает повторяющиеся строки в результате. Команда требует повышенного времени обработки. Лучше всего комбинировать с LIMIT.
Есть маленькая хитрость. Если необходимо просмотреть две таблицы на тему соответствия, то приведённая команда остановится сразу же, как только будет найдено первое соответствие.
10. Ограничить использование SELECT для постоянно изменяющихся таблиц.
11. Не забывайте про временные таблицы типа HEAP.
Несмотря на то, что таблица имеет ограничения, в ней удобно хранить промежуточные данные, особенно когда требуется сделать ещё одну выборку из таблицы без повторного обращения. Дело в том, что эта таблица хранится в памяти и поэтому доступ к ней очень быстрый.
12. Поиск по шаблону.
Зависит от размера поля и если уменьшить размер с 400 байтов до 300, то время поиска сократиться на 25%
13. Команда LOAD DATA INFILE
позволяет быстро загружать большой объём данных из текстового файла
14. Хранение изображений в БД нежелательно.
Лучше их хранить в папке на сервере, а в базе сохранять полный путь к ним. Дело в том, что веб-сервер лучше кэширует графические файлы, чем содержимое базы, что значит, что при последующем обращении к изображению, оно будет отображаться быстрее.
15. Максимально число запросов при генерации страницы,
как мне думается, должно быть не более 20 (+- 5 запросов). При этом оно не должно зависеть от переменных параметров.
На недавнем мероприятии SQL Saturday 178, мне задали вопрос, можно ли сделать так, чтобы оптимизатор не прекращал оптимизацию, когда посчитает что уже нашел хороший план или наступит таймаут, а исследовал все альтернативы. Я ответил, что документированных средств нет, либо я о таких не знаю. И это действительно так, однако, возможно есть какие-то недокументированные флаги трассировки, которыми можно влиять на этот процесс. Я решил провести небольшое исследование и в этой заметке расскажу о его результатах.
Забегая вперед, сразу сообщу об итогах исследования, для тех кому не важны технические подробности, а важны выводы. Оказывается, действительно можно сделать так, чтобы оптимизатор продолжал поиски «до упора», но вероятность, что он действительно найдет гораздо более удачный план невелика. Это логично, иначе, если бы оптимизатор очень часто «недооптимизировал» запросы, прекращая поиски раньше положенного, то следовало бы поменять механизм определения того самого момента, когда считается, что искать план дальше не имеет смысла. Между тем, оптимизатор довольно неплохо справляется со своей задачей, а когда не справляется, причина очень часто кроется не в самом оптимизаторе, а в том с чем ему приходится работать (неактуальная статистика, плохо написанный код и т.д.). Хотя, ради справедливости, стоит сказать, что бывают случаи, когда причина в самом оптимизаторе.
Далее, я расскажу о том, как заставить оптимизатор отбросить ограничения и продолжать оптимизацию до конца.
Основные понятия
Дерево логических операторов — дерево объектов, в котором каждым узлом является логический оператор, соответствующий той или иной операции в запросе. Это дерево — результат того, во что был превращен запрос после того как он попал на сервер и прошел некоторые стадии упрощения и преобразования. Короче говоря, это то с чем начинает работать оптимизатор.
Transformation Rule — правило преобразования. Это объект который содержит в себе методы по преобразованию одних логических операторов в другие логические (или физические) операторы.
Optimization Task — дословно, задача оптимизации, это операция предпринимаемая оптимизатором в процессе поиска плана. Это может быть например, применение правила преобразования к узлу дерева операторов.
Memo — структура в памяти сервера, которая используется для хранения и анализа получаемых в результате преобразований деревьев операторов.
Group — группа эквивалентности, часть структуры Memo, в которой хранятся эквивалентные выражения (операторы), например — Group 1: (A join B) , (B join A).
Group Expression — выражение в группе эквивалентности, например — Group 1: (A join B) , (B join A). (A join B) — одно из выражений группы Group 1.
Timeout — определенное количество задач оптимизации (Optimization Task), которое отводит себе оптимизатор перед тем, как начинает оптимизировать запрос («Я угадаю эту мелодию с 5 нот»!), т.е. некий бюджет на количество преобразований. По мере выполнения преобразований оптимизатор смотрит на этот счетчик, и как только потратил всё отведенное количество — прекращает оптимизацию и выдает тот план, который у него есть на данный момент. При этом, если в SSMS посмотреть на полученный план, выбрать корневой оператор SELECT и посмотреть свойства, то можно увидеть «Reason For Early Termination: Time Out».
Good Enough Plan — достаточно хороший план, это еще одно условие при котором оптимизация прекращается. Происходит это в том случае, если запас преобразований еще есть, но найденный на данном этапе план уже удовлетворяет внутреннему порогу оптимизатора. Это условие, также можно увидеть в свойствах плана в SSMS — «Reason For Early Termination: Good Enough Plan Found».
Алгоритм генерации альтернатив
Допустим есть запрос:
Соответствующее ему дерево логических операторов выглядит следующим образом: 
Дерево копируется в начальное Memo (Copy In): 
Теперь, на этом этапе, начинается процесс оптимизации.
Начинают применяться правила, генерироваться альтернативы, оцениваться стоимость, достаточно хороший план и таймаут.
Укрупнено, алгоритм работы по поиску плана можно представить так: 
Optimize Group
- На входе: группа, верхняя граница, требуемые свойства
- Сохранение лучшего плана в memo
Explore Group
- Итеративное исследование каждого выражения
Explore Expression
- Применение правил
- Генерирование альтернативных выражений
- Работа с memo, чтобы избежать повторов (e.g. JoinCommute)
- Битовая карта pattern memory определяет уже примененные правила
Apply Rule
- Предшественник – Потомок
- Привязка предшественников к правилам
- Применение правила
- Сохранение в memo (в том числе новых групп)
- Запуск следующего задания в зависимости от типа потомка
- Логический – Explore Expression
- Физический – Optimize Inputs
Optimize Inputs
- Подсчет наилучшего плана
- Форсирование физических свойств
- Отброс неэффективных ветвей
Все начинается с того, что на вход алгоритму, поступает корневая группа, на вход также поступают требуемые физические свойства, верхняя граница, выше которой (если стоимость превысит порог) не имеет смысла искать план. Поскольку план должен содержать физические операторы, то группа должна содержать физические операторы. Рекурсивно вызывается оптимизация дочерних групп.
В процессе оптимизации каждой из групп происходит исследование группы (Explore Group), если группа содержит несколько выражений, то исследование группы заключается в итеративном вызове (Explore Expression).
На этапе Explore Expression определяются правила, которые могут быть применены к этому выражению, ведется учет повторов, чтобы избежать одних и тех же преобразований, идет применение правил (Apply Rule). Важный момент: правила применяются не все подряд. А только те, что соответствуют некоторому шаблону для конкретного выражения группы (оператора). Правило применяется к выражению (предшественник) и генерирует новое выражение (потомок).
В зависимости от потомка, запускается либо задача Explore Expression, если потомок логический оператор. Либо Optimize Inputs, если потомок физический оператор. Либо Optimize Group, если применение правила породило потомка, который не входит ни в какую существующую группу, а образует новую.
Этап Optimize Inputs в свою очередь обеспечивает стратегию отброса (Discarding) неэффективных ветвей плана (Cost Based Pruning Factor), подсчет наилучшего плана и форсирование физических свойств (например, если у нас есть Merge join, который требует отсортированного входа, то будет форсирована операция сортировки).
В результате всего этого, в Memo сохраняются физические операторы, реализующие наиболее эффективный план. 
После этого наиболее эффективный план копируется из Memo (Copy Out): 
На протяжении всего этого процесса активно применяются две следующие концепции: Timeout, Cost Based Pruning Factor, Discarding.
Именно они влияют на то, как будет выбран план, и именно на них можно повлиять флагами трассировки.
Перейдем от теории к практике.
Отключаем Timeout
Первый флаг трассировки: 8780. Он позволяет «отключить» Timeout.
Для демонстрации, я буду использовать ту же простую БД opt, что использую в примерах почти всегда.
Для удобства приведу еще раз скрипт ее генерации:
Теперь, давайте выполним следующий умозрительный запрос, для того, чтобы получить Timeout.
Примечание: Для просмотра информации я использую недокументированный флаг трассировки 8675, который выводит информацию по стадиям оптимизации. Я уже неоднократно использовал этот флаг в рассказах про оптимизатор. Например, тут Оптимизатор (ч.3): Optimization: Full Optimization: Search 0.
