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

В статье «Советы по оптимизации для нескольких предикатов принадлежности диапазону, часть 1», опубликованной в предыдущем номере журнала, был описан метод оптимизации нескольких конъюнктивных предикатов (то есть предикатов, разделенных оператором AND). Мы выяснили, что нетрудно упорядочить эффективный индекс, если имеется всего один столбец с предикатом принадлежности диапазону, а все остальные — предикаты равенства. Разместите столбец с предикатом принадлежности диапазону последним в списке ключа индекса. Однако если имеется несколько предикатов принадлежности диапазону, охватывающих различные столбцы, то идеального индекса просто не существует. Например, рассмотрим следующий классический тест пересечения интервалов:

WHERE startdate <= @end AND enddate >= @start

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

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

Пересечение интервалов: недавний период

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

Предположим, что в таблице Intervals содержатся закрытые интервалы (то есть в них входят оба крайних значения), представляющие периоды договоров аренды автомобилей. Запрос, подлежащий оптимизации, предназначен для поиска договоров, активных в течение входного периода, представленного входными значениями @start и @end.

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

Сложность в том, что большинство пользователей интуитивно создают индекс для запросов пересечений, выбирая startdate в качестве главного ключа и enddate в качестве вторичного ключа, например:

CREATE INDEX idx_sart_end ON dbo.Intervals(startdate, enddate);

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

SET STATISTICS IO, TIME ON;

Затем запустите следующий запрос для поиска активных интервалов в течение последнего месяца:

DECLARE
@start AS DATE = '20141201',
@end AS DATE = '20141231';
SELECT id
FROM dbo.Intervals
WHERE startdate <= @end AND enddate >= @start;

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

Рисунок 1. План для запроса пересечений с индексом по?(startdate, enddate)

Обратите внимание, что предикат поиска основан на главном ключе индекса: startdate <= @end, а остаточный предикат основан на вторичном ключе: enddate >= @start. Теперь вспомним о предикате поиска. Большинство строк в таблице (около 99%) удовлетворяют этому предикату, что приводит к сканированию диапазонов почти всех конечных страниц индекса. SQL Server представил следующую статистику производительности для этого запроса: число операций логического чтения — 20 012, время процессора – 1156 мс, время — 527 мс.

Как объясняется в предыдущей статье, гораздо более эффективный подход к индексации при наличии нескольких предикатов принадлежности диапазону — поместить более селективный столбец первым в списке ключей. При запросах, аналогичных показанному выше, охватывающих в основном недавний период, имеется около 99% совпадений для предиката startdate <= @end, но лишь примерно 1% совпадений для предиката enddate >= @start. Поэтому гораздо лучше определить индекс по enddate в качестве главного ключа, например:

DROP INDEX idx_sart_end ON dbo.Intervals;
CREATE INDEX idx_end_start ON dbo.Intervals(enddate, startdate);

Запустите повторно запрос пересечений после создания нового индекса:

DECLARE
@start AS DATE = '20141201',
@end AS DATE = '20141231';
SELECT id
FROM dbo.Intervals
WHERE startdate <= @end AND enddate >= @start;

На рисунке 2 показан план для данного запроса.

Рисунок 2. План для запроса пересечений с индексом по?(enddate, startdate)

Обратите внимание, что на этот раз в качестве предиката поиска используется более точный предикат. Это приводит к следующей статистике производительности: число операций логического чтения — 93, время процессора — 47 мс, время — 302 мс.

Пересечение интервалов: оптимизация Сарка для коротких интервалов

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

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

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

DECLARE
@start AS DATE = '20090101',
@end AS DATE = '20090107';
SELECT id
FROM dbo.Intervals
WHERE startdate <= @end AND enddate >= @start;

Независимо от того, определен ли индекс для (enddate, startdate) или наоборот, необходимо проверить примерно половину данных на конечной странице индекса. В данный момент индекс определен для (enddate, startdate), поэтому план аналогичен показанному на рисунке 2. Только на этот раз сканируется примерно половина конечной страницы индекса, поэтому статистика производительности следующая: число операций логического чтения — 12 036, время процессора — 655 мс, время — 581 мс.

В результате оптимизации Сарка добавляется предикат для главного ключа индекса, и тот ограничивается замкнутым диапазоном. Таким образом существенно сокращается число просматриваемых строк. Например, имеется индекс для (enddate, startdate). Вспомните, что в первоначальном тесте пересечения используется предикат enddate >= @start. Этот предикат уже ограничивает начальную точку для enddate. Известно, что максимальная разница между началом и концом интервала (назовем ее maxdiff) — 30 дней; ее можно даже жестко задать ограничением. Вы вычисляете разницу между началом и концом входного интервала (назовем ее inputdiff). Самая дальняя конечная точка интервала, пересекающегося с входным интервалом, — @start + inputdiff + maxdiff, поэтому можно добавить предикат enddate <= DATEADD(day, DATEDIFF(day, @start, @end) + @max, @start), чтобы ограничить конечную точку сканирования диапазона. Можно использовать предикат BETWEEN с исходной начальной точкой и новой конечной точкой в качестве ограничителей, например:

DECLARE
@start AS DATE = '20090101',
@end AS DATE = '20090107',
@max AS INT = 30;
SELECT id
FROM dbo.Intervals
WHERE enddate BETWEEN @start
AND DATEADD(day, DATEDIFF(day, @start, @end) + @max, @start)
AND startdate <= @end;

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

Рисунок 3. План для? решения Сарка, когда максимальная продолжительность интервала малая и постоянная

Обратите внимание, что существует конечная точка для предиката поиска. Сведения о производительности, полученные после выполнения данного запроса: число операций логического чтения — 200, время процессора — 47 мс, время — 370 мс.

Если индекс был определен для (startdate, enddate), то применяется обратное вычисление. Значения inputdiff и maxdiff вычитаются из @end, чтобы задать минимальную начальную точку для startdate, например:

DECLARE
@start AS DATE = '20090101',
@end AS DATE = '20090107',
@max AS INT = 30;
SELECT id
FROM dbo.Intervals
WHERE startdate BETWEEN
DATEADD(day, -DATEDIFF(day, @start, @end) — @max, @end)
AND @end
AND enddate >= @start;

Ситуация усложняется, если интервалы короткие, но максимальная длина не ограничена, поэтому неизвестно заранее, какой будет максимальная длина. Необходимо вычислить максимальную длину при запросе данных. Чтобы повысить эффективность такого запроса, можно добавить вычисленный столбец в таблицу для вычисления разницы между startdate и enddate (назовем его ilen — сокращенно от interval length) и индексировать его, например:

ALTER TABLE dbo.Intervals ADD ilen AS DATEDIFF(day, startdate, enddate);
CREATE INDEX idx_ilen ON dbo.Intervals(ilen);

Затем вместо назначения постоянной величины переменной @max следует запросить максимальное значение ilen из данных. Ниже приводится программный код решения. Предполагается наличие индекса для (enddate, startdate):

DECLARE
@start AS DATE = '20090101',
@end AS DATE = '20090107',
@max AS INT = (SELECT MAX(ilen) FROM dbo.Intervals);
SELECT id
FROM dbo.Intervals
WHERE enddate BETWEEN @start
AND DATEADD(day, DATEDIFF(day, @start, @end) + @max, @start)
AND startdate <= @end;

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

Рисунок 4. План для решения Сарка, если максимальная длина интервала мала, но неизвестна

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

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

Поддерево/дочерние объекты в модели вложенных множеств в виде графа

Еще один пример снижения производительности, связанного с наличием нескольких предикатов принадлежности диапазону — запрос к поддереву/дочерним объектам в модели вложенных множеств в виде графа. На рисунке 5 показано дерево сотрудников с целыми значениями справа и слева на основе модели вложенных множеств.

Рисунок 5. Дерево с левыми и правыми значениями

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

Чтобы вернуть поддерево данного узла (назовем его @root), чаще всего используют запрос с двумя предикатами принадлежности диапазону (P представляет родительский экземпляр, а C — дочерний экземпляр):

P.nodeid = @root AND C.lft >= P.lft AND C.rgt <= P.rgt

Запустите программный код листинга 2, чтобы создать таблицу Tree и заполнить ее 1 000 000 строк. Обратите внимание, что индекс idx_lft_rgt имеет список ключей (lft, rgt).

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

DECLARE @root AS INT = 11112;
SELECT C.*
FROM dbo.Tree AS P
INNER JOIN dbo.Tree AS C
ON P.nodeid = @root
AND C.lft >= P.lft AND C.rgt <= P.rgt;

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

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

Обратите внимание, что только один из предикатов принадлежности диапазону используется в качестве предиката поиска: C.lft >= P.lft. Другой предикат используется в качестве остаточного предиката: C.rgt <= P.rgt. Несмотря на наличие всего 11 совпадающих строк, для выполнения запроса потребовалось 5241 операция логического чтения.

Однако существует простой обходной прием. Левое и правое значения можно рассматривать как ограничители интервала. Применяя терминологию из алгебры интервалов Аллена, интервал предка содержит интервалы всех потомков. Поэтому если интервал узла P содержит левый ограничитель узла C, то он обязательно является предком C и также содержит его правый ограничитель. На этой основе можно видоизменить запрос для потомков следующим образом:

DECLARE @root AS INT = 11112;
SELECT C.*
FROM dbo.Tree AS P
INNER JOIN dbo.Tree AS C
ON P.nodeid = @root
AND C.lft BETWEEN P.lft AND P.rgt;

Теперь у запроса только один предикат принадлежности диапазону для главного ключа индекса (lft). Результат — чрезвычайно эффективный план, показанный на рисунке 7.

Рисунок 7. План для оптимизированного запроса к поддереву

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

Продолжение следует

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

SET NOCOUNT ON;
USE tempdb;
GO
— Создание вспомогательной функции dbo.GetNums
— Цель: возвратить последовательность целочисленных значений в диапазоне от @low до @high
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
— Построение и заполнение таблицы Intervals
IF OBJECT_ID(N'dbo.Intervals', N'U') IS NOT NULL DROP TABLE dbo.Intervals;
GO
CREATE TABLE dbo.Intervals
(
id INT NOT NULL,
startdate DATE NOT NULL,
enddate DATE NOT NULL,
CONSTRAINT CHK_Intervals_end_gteq_start CHECK(enddate >= startdate)
);
GO
DECLARE
@numintervals AS INT = 10000000,
@minstartdate AS DATE = '20050101',
@maxenddate AS DATE = '20141231',
@maxdiff AS INT = 30;
WITH C AS
(
SELECT
n AS id,
DATEADD(day,
(ABS(CHECKSUM(NEWID())) % (DATEDIFF(day, @minstartdate, @maxenddate) — @maxdiff + 1)),
@minstartdate) AS startdate,
ABS(CHECKSUM(NEWID())) % (@maxdiff + 1) AS diff
FROM dbo.GetNums(1, @numintervals) AS Nums
)
INSERT INTO dbo.Intervals WITH(TABLOCK) (id, startdate, enddate)
SELECT id, startdate, DATEADD(day, diff, startdate) AS enddate
FROM C;
ALTER TABLE dbo.Intervals ADD CONSTRAINT PK_Intervals PRIMARY KEY(id);

CREATE TABLE #Tree
(
nodeid INT NOT NULL,
parentid INT NULL,
val NUMERIC(12, 2)
);
INSERT INTO #Tree(nodeid, parentid, val)
SELECT
n AS nodeid,
NULLIF((n+8) / 10, 0) AS parentid,
CAST(1 + ABS(CHECKSUM(NEWID())) % 100 AS NUMERIC(12, 2)) AS val
FROM dbo.GetNums(1, 1000000) AS Nums;
CREATE UNIQUE CLUSTERED INDEX idx_pid_nid ON #Tree(parentid, nodeid);
ALTER TABLE #Tree ADD PRIMARY KEY NONCLUSTERED(nodeid);
GO
— Материализация отношений вложенных множеств в таблице
IF OBJECT_ID(N'dbo.Tree', N'U') IS NOT NULL DROP TABLE dbo.Tree;
WITH TwoNums AS
(
SELECT n FROM (VALUES(1),(2)) AS D(n)
),
SortPath AS
(
SELECT nodeid, 0 AS lvl, n, CAST(CAST(n AS BINARY(4)) AS VARBINARY(MAX)) AS sort_path
FROM #Tree CROSS JOIN TwoNums
WHERE nodeid = 1
UNION ALL
SELECT C.nodeid, P.lvl + 1, TN.n,
P.sort_path + CAST(
(-1 + ROW_NUMBER() OVER(PARTITION BY C.parentid
ORDER BY C.nodeid)) / 2 * 2 + TN.n
AS BINARY(4))
FROM SortPath AS P
INNER JOIN #Tree AS C
ON P.n = 1
AND C.parentid = P.nodeid
CROSS JOIN TwoNums AS TN
),
Sort AS
(
SELECT nodeid, lvl, ROW_NUMBER() OVER(ORDER BY sort_path) AS sortval
FROM SortPath
),
NestedSets AS
(
SELECT nodeid, lvl, MIN(sortval) AS lft, MAX(sortval) AS rgt
FROM Sort
GROUP BY nodeid, lvl
)
SELECT E.nodeid, E.val, NS.lvl, NS.lft, NS.rgt
INTO dbo.Tree
FROM NestedSets AS NS
INNER JOIN #Tree AS E
ON E.nodeid = NS.nodeid;
CREATE UNIQUE CLUSTERED INDEX idx_uc_lft_rgt ON dbo.Tree(lft, rgt);
ALTER TABLE dbo.Tree ADD CONSTRAINT PK_Tree PRIMARY KEY NONCLUSTERED(nodeid);
GO
DROP TABLE #Tree;