Советы по оптимизации для нескольких предикатов принадлежности диапазону, часть 1

Оптимальной производительности запросов невозможно добиться без правильно выбранных индексов для фильтров запроса. Если фильтр запроса имеет единственный предикат, который является аргументом поиска (SARG), то все просто: вы создаете индекс с фильтрованным столбцом в качестве ключа. Однако при наличии нескольких конъюнктивных предикатов (разделенных операторами AND) ситуация усложняется. Например, необходимо определить оптимальный порядок ключей индекса. Кроме того, если задействовано более одного предиката принадлежности диапазону, то вам не удастся создать по-настоящему безупречный индекс. И все же необходимо найти оптимальный подход к индексации и лучшие методы записи запросов. Иногда, чтобы повысить производительность, приходится переделывать существующее решение.

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

Образец данных

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

Используйте исходный текст листинга 2, чтобы создать таблицы TStrNum и TNumStr, а также вспомогательные индексы и статистику. Две таблицы имеют одинаковую структуру и заполняются одинаковыми тестовыми данными; только определенные в них индексы разные.

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

В таблицах есть строковый столбец, именуемый string, и целочисленный столбец с именем number. Программный код вводит в каждую таблицу 1 000 000 строк, с четырьмя несовпадающими значениями в строке (A, B, C и D) и десятью несовпадающими значениями в number (от 1 до 10). Существует 40 различных комбинаций значений в string, number, которые равномерно распределены (25 000 вхождений в каждом). На практике такое чистое, ровное распределение редкость, но для целей нашей статьи оно приемлемо.

Программный код создает индекс idx_str_num в TStrNum(string, number, keycol) и индекс idx_num_str в TNumStr(number, string, keycol). Далее будут рассмотрены различные типы фильтров запроса с использованием двух предикатов, один из которых основан на string, а другой — на number. При обсуждении оптимизации со столбцом string в качестве ведущего ключа запрос направляется к таблице TStrNum. Аналогично при обсуждении оптимизации со столбцом number в качестве ведущего ключа запрос направляется к таблице TNumStr.

Строки индекса очень короткие; в среднем на конечной странице умещается приблизительно 366 строк. В моем случае индекс idx_str_num имеет 2730 страниц в leaf, а индекс idx_num_str имеет 2732 страницы.

Несколько предикатов равенства

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

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

SET STATISTICS IO ON;
SELECT keycol, string, number
FROM dbo.TStrNum
WHERE string = 'C' AND number = 9;
SELECT keycol, string, number
FROM dbo.TNumStr
WHERE string = 'C' AND number = 9;

Каким будет оптимальный подход к индексации в данном случае? Все предикаты являются предикатами равенства, независимо от порядка столбцов в списке ключа индекса, подходящие строки находятся в последовательном диапазоне на конечной странице индекса. С этой точки зрения порядок списка ключа не имеет значения. Но вам, вероятно, приходилось слышать распространенную рекомендацию сделать так, чтобы главный ключ был самым селективным столбцом. В нашем случае это number. Предположительно (в соответствии с рекомендацией) SQL Server создает гистограмму по главному ключу, но не по другим столбцам; поэтому, если последовать этому совету, оптимизатор сможет дать более удачные оценки, что в большинстве случаев приводит к оптимальному выбору.

Действительно, SQL Server создаст гистограмму по главному ключу, когда пользователь выбирает индекс. Но помимо этого будут созданы гистограммы с одним столбцом по другим столбцам, если нужно выполнить запрос к данным, при условии, что свойство базы данных AUTO_CREATE_STATISTICS включено (состояние по умолчанию).

Более того, оценку для нескольких предикатов равенства можно выполнить с использованием различных методов. Выбор метода оптимизатором зависит от версии SQL Server, эвристики и других факторов. Эта тема отлично раскрыта в публикациях Пола Уайта и Бенджамина Невареза. Например, в статье «Cardinality Estimation for Multiple Predicates» Пол Уайт объясняет, как выполнить оценки для нескольких предикатов (www.sqlperformance.com/2014/01/sql-plan/cardinality-estimation-for-multiple-predicates).

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

На рисунке 1 показаны планы, полученные мною для ранее упомянутых запросов, когда я запускал их в среде SQL Server 2014. Обратите внимание, что в обоих случаях оценки одинаковые (хотя и не совсем точные).

Рисунок 1. Планы для двух предикатов равенства

Метод оценки, используемый SQL Server 2014 в нашем примере (если режим совместимости базы данных 120 или если используется флаг трассировки 2312), называется экспоненциальным алгоритмом отсрочки (backoff). Его формула:

S1 * SQRT(S2) *. .. * SQRT(SQRT(Sn)). .. * input_cardinality
S1 — наиболее селективный предикат, S2 — второй по уровню селективности и т.д. В нашем случае S1 имеет значение 0.1 (number = 9), а S2 — 0.25 (string = 'C'). Таким образом, наша формула выглядит так:
0.1 * SQRT(0.25) * 1000000 = 50000

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

Даже при использовании оценщика кратности, существовавшего до 2014 года (режим совместимости базы данных <120, или при использовании флага трассировки 9481), я получил такие же оценки для обоих запросов — 25 000. Такая оценка получается с нашими равномерно распределенными данными при использовании вектора плотности (среднего) или предположения независимости (данные в столбцах не связаны). В случае с вектором плотности вы получите такую же плотность 1/40000 = 0.025 (единица, разделенная на число отдельных вариантов), где вектор представляет собой (string, number) или (number, string). Тогда 0.025 * 1000000 = 25000. При предположении независимости окончательная оценка представляет собой произведение оценок селективности различных предикатов:

S1 * S2 *. .. * Sn * input_cardinality

В нашем случае — 0.1 * 0.25 * 1000000 = 25000. Очевидно, независимо от порядка столбцов в индексе, оценка остается неизменной.

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

Очевидно, чтобы поиск в индексе был эффективно выполнен оптимизатором, необходима фильтрация по первым ключам индекса. Поэтому поиск в индексе может быть выполнен в индексе idx_str_num, даже при фильтрации только по строковому столбцу, но не в индексе idx_num_str. Например, рассмотрим следующие запросы:

SELECT keycol, string, number
FROM dbo.TStrNum
WHERE string = 'C';
SELECT keycol, string, number
FROM dbo.TNumStr
WHERE string = 'C';

На рисунке 2 показаны планы для этих запросов.

Рисунок 2. Планы для одного предиката

План для первого запроса выполняет эффективный поиск в индексе idx_str_num, при котором выполняется 690 операций логического чтения. План для второго запроса не может применить поиск в индексе idx_num_str, так как фильтрованный столбец не является первым ключом. Поэтому в конце концов оптимизатор переходит к полному сканированию индекса, для которого требуется 2732 операции логического чтения.

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

Равенство и диапазон

При наличии одного или нескольких предикатов равенства и одного предиката диапазона их можно обеспечить оптимальным индексом. Столбцы, показанные в предикатах равенства, должны быть представлены первыми в списке ключа индекса, а столбец диапазона — последним. Таким образом, вы получаете подходящие строки в последовательном диапазоне в конечной странице индекса. Это также не имеет отношения к селективности предикатов.

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

SELECT keycol, string, number
FROM dbo.TStrNum
WHERE string = 'C' AND number >= 9;
SELECT keycol, string, number
FROM dbo.TNumStr
WHERE string = 'C' AND number >= 9;

Первый запрос обеспечивается индексом, в котором учитывается эта рекомендация, а второй запрос — нет. На рисунке 3 показаны планы для этих запросов.

Рисунок 3. Планы для предиката равенства и предиката диапазона

Первый план оптимален. Оба предиката показаны как предикаты поиска (Seek Predicates). Начало сканирования диапазона в конечной странице индекса зависит от комбинации свойств Prefix (string = @1) и Start (number >= @2), а конец сканирования диапазона определяется только Prefix. Требуется сканировать исключительно конечные страницы индекса, содержащие подходящие строки. Для выполнения плана потребовалось 142 операции логического чтения.

В таблице 1 строки расположены в том порядке, в котором они приведены в индексе idx_str_num, причем проверенные строки отмечены символом S, а возвращенные строки символом R. Обратите внимание, что нужно сканировать только возвращенные строки.

Второй план не оптимален, так как подходящие строки в последовательном диапазоне в индексе отсутствуют. Предикат диапазона number >= @2 отображается в свойстве Start свойства Seek Predicates. Это означает, что должны быть сканированы все строки в конечных страницах индекса idx_num_str, соответствующие данному предикату. Затем предикат равенства string = @1 появляется как свойство Predicate. Можно подумать, что это остаточный предикат — он применяется к сканированным строкам, чтобы определить, нужно ли их возвращать.

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

Несколько предикатов диапазона

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

Рассмотрим два запроса:

SELECT keycol, string, number
FROM dbo.TStrNum
WHERE string >= 'C' AND number >= 9;
SELECT keycol, string, number
FROM dbo.TNumStr
WHERE string >= 'C' AND number >= 9;

На рисунке 4 показаны планы для этих запросов.

Рисунок 4. Планы для нескольких предикатов диапазона

Обратите внимание, что свойство Start свойства Seek Predicates в обоих случаях основывается на двух предикатах диапазона, но все оставшиеся строки справа от начальной точки в индексе должны быть проверены. Предикат с ключом, отличным от первого, применяется как остаточный к проверенным строкам, чтобы определить, какие строки следует возвратить.

Предикат number >= 9, очевидно, более селективен, чем string >= 'C'. Поэтому план для второго запроса, использующего индекс idx_num_str, более эффективен (413 операций чтения), чем план для второго запроса, использующего индекс isx_str_num (822 операции чтения).

В таблице 3 показан доступ к данным (просканированные строки и возвращенные строки) для первого запроса, а в таблице 4 — доступ к данным для второго запроса.

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

Что дальше?

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

SET NOCOUNT ON;
USE tempdb;
IF OBJECT_ID(N'dbo.GetNums', N'IF') IS NOT NULL DROP FUNCTION dbo.GetNums;
GO
CREATE FUNCTION dbo.GetNums(@low AS BIGINT, @high AS BIGINT) RETURNS TABLE
AS
RETURN
WITH
L0 AS (SELECT c FROM (SELECT 1 UNION ALL SELECT 1) AS D(c)),
L1 AS (SELECT 1 AS c FROM L0 AS A CROSS JOIN L0 AS B),
L2 AS (SELECT 1 AS c FROM L1 AS A CROSS JOIN L1 AS B),
L3 AS (SELECT 1 AS c FROM L2 AS A CROSS JOIN L2 AS B),
L4 AS (SELECT 1 AS c FROM L3 AS A CROSS JOIN L3 AS B),
L5 AS (SELECT 1 AS c FROM L4 AS A CROSS JOIN L4 AS B),
Nums AS (SELECT ROW_NUMBER() OVER(ORDER BY (SELECT NULL)) AS rownum
FROM L5)
SELECT TOP(@high — @low + 1) @low + rownum — 1 AS n
FROM Nums
ORDER BY rownum;
GO

IF OBJECT_ID(N'dbo.TStrNum', N'U') IS NOT NULL DROP TABLE dbo.TStrNum;
IF OBJECT_ID(N'dbo.TNumStr', N'U') IS NOT NULL DROP TABLE dbo.TNumStr;
CREATE TABLE dbo.TStrNum
(
keycol INT NOT NULL IDENTITY,
string VARCHAR(10) NOT NULL,
number INT NOT NULL
);
CREATE TABLE dbo.TNumStr
(
keycol INT NOT NULL IDENTITY,
string VARCHAR(10) NOT NULL,
number INT NOT NULL
);
INSERT INTO dbo.TStrNum WITH (TABLOCK) (string, number)
SELECT
CHAR(ASCII('A') + S.n) AS string,
N.n AS number
FROM dbo.GetNums(0, 3) AS S
CROSS JOIN dbo.GetNums(1, 10) AS N
CROSS JOIN dbo.GetNums(1, 25000) AS M;
INSERT INTO dbo.TNumStr WITH (TABLOCK) (string, number)
SELECT
CHAR(ASCII('A') + S.n) AS string,
N.n AS number
FROM dbo.GetNums(0, 3) AS S
CROSS JOIN dbo.GetNums(1, 10) AS N
CROSS JOIN dbo.GetNums(1, 25000) AS M;
— Индексы
CREATE UNIQUE CLUSTERED INDEX idx_str_num ON dbo.TStrNum(string, number, keycol);
CREATE UNIQUE CLUSTERED INDEX idx_num_str ON dbo.TNumStr(number, string, keycol);
— Создание триггеров гистограммы на втором ключе индекса
SELECT keycol, string, number
FROM dbo.TStrNum
WHERE number = 9 AND number % 2 = 0;
SELECT keycol, string, number
FROM dbo.TNumStr
WHERE string = 'C' AND LEFT(string, 1) = 'A';
— Обновление статистики с полным просмотром
UPDATE STATISTICS dbo.TStrNum WITH FULLSCAN;
UPDATE STATISTICS dbo.TNumStr WITH FULLSCAN;
GO