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

В предыдущих статьях цикла, «Советы по оптимизации для нескольких предикатов принадлежности диапазону», части 1 и 2, я рассматривал проблемы, связанные с оценками кардинальности и индексацией, и давал советы по оптимизации. В этой статье основное внимание уделено предикатам принадлежности диапазону на основе векторов. Речь идет о концептуальном объединении многих элементов в вектор и применении сравнения на основе неравенства между двумя такими векторами, в частности между вектором столбцов и вектором входных значений.

Например, рассмотрим вектор столбцов (col1, col2,. .. , coln) и вектор входных значений(@c1, @c2,. .. , @cn). Предположим, нам нужно фильтровать только строки, в которых вектор столбцов больше вектора входных значений. В рамках концепции требуется, чтобы запрос применил следующий фильтр:

WHERE (col1, col2,. .., coln) > (@c1, @c2,. .., @cn)

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

T-SQL не поддерживает стандартный синтаксис для векторных сравнений, поэтому если требуются векторные сравнения, приходится искать альтернативные подходы. Существует два варианта с различными способами оптимизации.

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

В примерах используется содержащая 1 000 000 строк таблица с именем Orders из базы данных с именем Performance. Вы можете загрузить исходный текст для создания и заполнения базы данных Performance (http://tsql.solidq.com/books/source_code/Performance.txt).

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

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

Постраничный просмотр на основе одного столбца упорядочивания

В качестве примера перехода между страницами на основе одного столбца упорядочивания нужно спроектировать хранимую процедуру с именем GetPage, которая возвращает за один раз по одной странице строк, упорядоченных по столбцу orderid. В качестве входа передается ключ сортировки последней строки из предшествующей, уже полученной страницы. Исходя из предположения, что идентификаторы упорядочивания, используемые в системе, всегда положительны, значение по умолчанию, равное 0, используется для входной привязки идентификатора упорядочивания. Таким образом, если входное значение не указано, процедура возвращает первую страницу строк, в которых идентификаторы упорядочивания больше 0. Запрос должен возвращать столбцы orderid и filler. Последний — просто значение в 200 байт, используемое в качестве заполнителя, представляющего несколько столбцов, которые обычно нужно вернуть.

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

SET NOCOUNT ON;
USE Performance;
CREATE UNIQUE INDEX idx_oid_i_filler
ON dbo.Orders(orderid) INCLUDE(filler);

Ниже приведен программный код хранимой процедуры GetPage на основе ранее сформулированных требований:

IF OBJECT_ID(N'dbo.GetPage', N'P') IS NOT NULL
DROP PROC dbo.GetPage;
GO
CREATE PROC dbo.GetPage
@anc_oid AS INT = 0,
@pagesize AS BIGINT = 25
AS
SELECT TOP (@pagesize) orderid, filler
FROM dbo.Orders
WHERE orderid > @anc_oid
ORDER BY orderid;
GO

Запустите следующий программный код, чтобы задействовать статистику ввода-вывода:

SET STATISTICS IO ON;

Для запроса первой страницы вызывается процедура без передачи якоря идентификатора упорядочивания, например:

EXEC dbo.GetPage;

Возвращаются первые 25 строк (размер страницы по умолчанию). Ключ сортировки в последней строке — идентификатор упорядочивания 25. Для запроса следующей страницы величина 25 передается в качестве входной привязки идентификатора упорядочивания:

EXEC dbo.GetPage @anc_oid = 25;

А для запроса третьей страницы передается число 50, так как это идентификатор упорядочивания последней строки на второй странице:

EXEC dbo.GetPage @anc_oid = 50;

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

Рисунок 1. План для запроса с использованием одного столбца упорядочения

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

Постраничный просмотр на основе нескольких столбцов упорядочивания

Предположим, что упорядочивание в страничном сценарии основано на нескольких столбцах. Пусть оно основано на векторе (shipperid, orderid). Запрос должен возвратить вывод в столбцах shipperid, ordered и filler. В оптимальном индексе для вашего решения должны быть столбцы упорядочивания как список ключа индекса и остальные — как включенные столбцы. Выполните следующий программный код, чтобы создать оптимальный индекс:

CREATE UNIQUE INDEX idx_sid_oid_i_filler
ON dbo.Orders(shipperid, orderid)
INCLUDE(filler);

Если бы в T-SQL работали конструкторы строк, можно было бы использовать следующий фильтр:

WHERE (shipperid, orderid) > (@anc_sid, @anc_oid)

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

IF OBJECT_ID(N'dbo.GetPage', N'P') IS NOT NULL
DROP PROC dbo.GetPage;
GO
CREATE PROC dbo.GetPage
@anc_sid AS VARCHAR(5) = '',
@anc_oid AS INT = 0,
@pagesize AS BIGINT = 25
AS
SELECT TOP (@pagesize) shipperid, orderid, filler
FROM dbo.Orders
WHERE shipperid >= @anc_sid
AND (shipperid > @anc_sid OR orderid > @anc_oid)
ORDER BY shipperid, orderid;
GO

Выполните следующий программный код на первой странице:

EXEC dbo.GetPage;

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

EXEC dbo.GetPage @anc_sid = 'A', @anc_oid = 131;

Рисунок 2. Вывод запроса первой страницы, упорядоченного по shipperid и orderid

Полученный вывод показан на рисунке 3. Аналогично, для получения третьей страницы передаются значения из последней строки на второй странице:

EXEC dbo.GetPage @anc_sid = 'A', @anc_oid = 253;

Рисунок 3. Вывод запроса второй страницы, упорядоченный по shipperid и orderid

Полученный вывод показан на рисунке 4.

Рисунок 4. Вывод запроса третьей страницы, упорядоченный по shipperid и orderid

Оптимизация: на рисунке 5 показан план для запроса.

Рисунок 5. Первый вариант плана для запроса с?использованием двух столбцов упорядочения

Обратите внимание, что предикат поиска есть shipperid >= @anc_sid. Остальные предикаты (shipperid > @anc_sid OR orderid > @anc_oid) представляют собой остаточные предикаты. Операция поиска достигает первой строки на конечной странице индекса, которая удовлетворяет предикату поиска, а затем выполняется сканирование диапазона, пока не будут обнаружены 25 строк, удовлетворяющих остаточным предикатам. Чем дальше находится запрошенная страница внутри одного значения shipperid, тем больше несоответствующих строк приходится просмотреть, прежде чем будут обнаружены 25 подходящих строк.

Столбец shipperid в нашей таблице отличается высокой плотностью (20%, поскольку существует пять различных значений), поэтому чем дальше пользователи просматривают страницы, тем больше лишних строк приходится проверять. Последствия запросов к первым трем страницам не особенно серьезны; однако для запроса третьей страницы потребовалось четыре операции логического чтения. Но если углубиться дальше, то плата возрастает.

В качестве примера сначала найдем максимальный идентификатор упорядочивания для отправителя A, выполнив следующий запрос:

SELECT MAX(orderid) AS maxoid
FROM dbo.Orders
WHERE shipperid = 'A';

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

EXEC dbo.GetPage @anc_sid = 'A', @anc_oid = 999999;

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

Как выясняется, существует логически эквивалентная альтернатива, более эффективно обрабатываемая оптимизатором. Вместо формы

shipperid >= @anc_sid AND (shipperid > @anc_sid OR orderid > @anc_oid)

используйте форму

(shipperid = @anc_sid AND orderid > @anc_oid) OR (shipperid > @anc_sid)

Выполните следующий программный код, чтобы изменить определение процедуры с использованием новой формы предикатов:

ALTER PROC dbo.GetPage
@anc_sid AS VARCHAR(5) = '',
@anc_oid AS INT = 0,
@pagesize AS BIGINT = 25
AS
SELECT TOP (@pagesize) shipperid, orderid, filler
FROM dbo.Orders
WHERE (shipperid = @anc_sid AND orderid > @anc_oid)
OR (shipperid > @anc_sid);
GO

Выполните следующий программный код, чтобы получить первую страницу:

EXEC dbo.GetPage;

На рисунке 6 показан план для этого программного кода.

Рисунок 6. Второй вариант плана для запроса с?использованием двух столбцов упорядочения

Обратите внимание, что оптимизатор разбивает в фильтре предикаты на два дизъюнктивных (OR) предиката поиска, каждый из которых представляет только подходящие строки:

Prefix: shipperid = @anc_sid, Start: orderid > @anc_oid
Start: orderid > @anc_oid

Для каждого поиска диапазон сканирования начинается с первого совпадения для Prefix и Start, а кончается при последнем совпадении для Prefix (или на краю конечной страницы индекса, если Prefix отсутствует). Если имеется более одного предиката поиска, как в нашем случае, то они обрабатываются по порядку.

Если оператор Top является узлом, запрашивающим строки, то каждый раз при достижении нужного числа строк (25 в данном случае) выполнение сокращается. Можно проверить число просмотров в выходных данных STATSITICS IO, чтобы выяснить, произошло ли сокращение выполнения, прежде чем был применен второй поиск. Пусть вас не смущает термин «просмотры» (scan). В действительности этот показатель представляет число обращений, независимо от использованного метода доступа. Если используется только один предикат, то значение показателя будет 1; если используются оба, будет значение 2. В любом случае, затраты пренебрежимо малы. Например, для запроса первой страницы я получил число просмотров 2 и число операций логического чтения 6. Это вполне объяснимо, так как индекс имеет три уровня и поэтому стоимость каждого поиска должна быть 3 операции чтения.

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

EXEC dbo.GetPage @anc_sid = 'A', @anc_oid = 131;

Я получил число просмотров, равное 1, и число операций логического чтения — 4. Причиной дополнительной операции чтения сверх ожидаемых трех для поиска, скорее всего, стало то, что подходящий диапазон захватил дополнительную страницу.

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

EXEC dbo.GetPage @anc_sid = 'A', @anc_oid = 253;

Получено число просмотров, равное 1, и число операций логического чтения, равное 3.

Теперь попытаемся запросить ту же дальнюю страницу, которая была запрошена предыдущим решением (на моем компьютере это было с якорным идентификатором упорядочивания 999999):

EXEC dbo.GetPage @anc_sid = 'A', @anc_oid = 999999;

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

Просмотр страниц с использованием OFFSET-FETCH

Интересно сравнить предыдущие примеры решения просмотра страниц с якорем и решение на основе фильтра OFFSET-FETCH. На сегодня этот фильтр не поддерживает концепцию привязки; ему предоставляется некоторое число строк, которое нужно пропустить (значение OFFSET), и число строк, которое необходимо фильтровать (значение FETCH). Таким образом можно реализовать решение просмотра страниц, в котором число страниц и размер страницы передаются как входные величины, и фильтр OFFSET-FETCH производит вычисления на основе входных величин, указывая, сколько строк нужно пропустить и сколько фильтровать. Ниже приведен пример такого решения:

IF OBJECT_ID(N'dbo.GetPage', N'P') IS NOT NULL
DROP PROC dbo.GetPage;
GO
CREATE PROC dbo.GetPage
@pagenum AS BIGINT = 1,
@pagesize AS BIGINT = 25
AS
SELECT shipperid, orderid, filler
FROM dbo.Orders
ORDER BY shipperid, orderid
OFFSET (@pagenum — 1) * @pagesize ROWS FETCH NEXT @pagesize ROWS ONLY;
GO

Следующий программный код запрашивает первую страницу:

EXEC dbo.GetPage @pagenum = 1;

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

Рисунок 7. План для запроса с использованием OFFSET-FETCH

Не существует волшебного способа, с помощью которого SQL Server мог бы перейти к первой подходящей строке. Оператор Top извлекает строки из оператора Index Scan справа от него. Оператор Top сначала запрашивает строки OffsetExpression и отбрасывает их (0 для первой страницы, 25 для второй, 50 для третьей и т.д.). Затем запрашиваются строки Top Expression, которые передаются в оператор слева (корневой узел SELECT в нашем случае). Чем больше номер страницы, тем больше данных просматривается. Более существенный недостаток: если индекс не охватывающий, то SQL Server пришлось бы выполнить просмотры OffsetExpression + Top Expression раз, а не просто Top Expression раз.

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

EXEC dbo.GetPage @pagenum = 20000; — число операций логического чтения 11 400

Я получил 11 400 операций логического чтения, и это при охватывающем индексе без просмотров.

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

CREATE PROC dbo.GetPage
@anc_sid AS VARCHAR(5) = '',
@anc_oid AS INT = 0,
@pagesize AS BIGINT = 25,
@last_sid AS VARCHAR(5) OUTPUT,
@last_oid AS INT OUTPUT
AS
SELECT shipperid, orderid, filler
FROM dbo.Orders
ORDER BY shipperid, orderid
OFFSET AFTER (@anc_sid, @anc_oid)
FETCH NEXT @pagesize ROWS ONLY
LAST ROW INTO (@last_sid, @last_oid);
GO

Такой синтаксис можно было бы оптимизировать, и один поиск в поддерживающем индексе приводил бы к первой подходящей строке.

Оптимальная обработка

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