Интервалы и счетчики, часть 1

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

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

Прежде всего, мне хотелось бы поблагодарить Адама Маханика, приславшего мне задачу, послужившую основой для данной статьи, а также выразить признательность Бену Фланагану, автору базового метода, применяемого в одном из описанных ниже решений.

Тестовые данные

Во всех задачах, рассматриваемых в статьях этой серии, используется один набор тестовых данных. В данные входит таблица с именем Sessions, в которой содержатся сеансы, сопоставляемые различным приложениям. Столбец app представляет приложение (назовем его элементом секционирования), а столбцы starttime и endtime представляют точки начала и завершения интервала сеанса, соответственно. В столбцах starttime и endtime используется тип DATETIME2(0) с точностью до одной секунды.

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

Индекс с именем idx_start определен на списке ключей (app, starttime, keycol), а индекс с именем idx_end определен на списке ключей (app, endtime, keycol).

С помощью программного кода в листинге 2 заполним таблицу Sessions малым набором тестовых данных.

Тестовые данные из листинга 2 можно использовать для проверки корректности решений. На рисунке 1 дано графическое представление малого набора тестовых данных.

Рисунок 1. Интервалы

Для генерации большого набора тестовых данных понадобится вспомогательная функция GetNums, которая принимает на вход параметры @low и @high и возвращает последовательность целых чисел в нужном диапазоне. Код функции GetNums приведен в листинге 3.

Используйте программный код в листинге 4 для заполнения таблицы Sessions большим набором тестовых данных.

Можно управлять числом приложений и общим число строк в тестовых данных, задавая параметры @numapps и @numrows, соответственно. Программный код в листинге 4 вносит в таблицу Apps 100 приложений, а в таблицу Sessions — 2 000 000 строк.

Задача: подсчет для дискретных интервалов

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

Рисунок 2. Подсчет по дискретным интервалам

На рисунке 3 показан желаемый выход запроса.

Рисунок 3. Подсчет перекрывающихся интервалов во время каждого дискретного интервала

В желаемом результате на рисунке 3 предполагается, что пользователь не заинтересован в интервалах, для которых результат подсчета равен нулю. Например, между 8:45 и 9:00 зарегистрировано 0 активных сеансов с подключением к app2. Иногда по каким-то причинам бывает полезно получить сведения о таких интервалах, и в этом случае в решении необходимо предусмотреть соответствующие меры.

Решение на основе агрегатов PIVOT, LEAD и SUM для окна

Первый шаг — составить одну последовательность начальных событий и событий завершения, отмечая начальные события типом события +1 (увеличивает число активных сеансов), а события завершения — -1 (число уменьшается). Чтобы сформировать такую последовательность событий, следует объединить результаты двух запросов — возвращающего начальные события и возвращающего события завершения. Например:

SELECT app, starttime AS ts, +1 AS type
FROM dbo.Sessions
UNION ALL
SELECT app, endtime AS ts, -1 AS type
FROM dbo.Sessions
ORDER BY app, ts;

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

Рисунок 4. Последовательность событий

Затем необходимо сгруппировать последовательность по приложениям и значениям в столбце ts, выполняя сведение количества событий по типу (помните, 1 для начала и -1 для завершения). Получается одна строка для каждого отдельного приложения и метки времени со столбцом, содержащим [1] для начальных событий и [-1] для событий завершения. Эта временная метка указывает на начало дискретного интервала. Затем вы применяете функцию LEAD, чтобы получить следующее значение ts, отмечающее завершение дискретного интервала. Число сеансов, перекрывающихся с текущим интервалом, представляет собой нарастающую итоговую сумму начальных событий за вычетом событий завершения. После того, как определено обобщенное табличное выражение (CTE) с именем C1 на основе предшествующего запроса, внешний запрос выглядит следующим образом:

SELECT
app,
ts AS starttime,
LEAD(ts) OVER(PARTITION BY app ORDER BY ts) AS endtime,
SUM([1]-[-1]) OVER(PARTITION BY app ORDER BY ts ROWS
UNBOUNDED PRECEDING) AS cnt
FROM C1
PIVOT(COUNT(type) FOR type IN([1],[-1])) AS P;

Код в листинге 5 объединяет запросы.

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

Рисунок 5. Результаты запроса в листинге 5

Обратите внимание, что в результат входят интервалы с подсчетом, равным нулю, а также интервал со значением starttime, равным последнему событию завершения, и NULL в столбце endtime. Естественно, желательно удалить строки со значением NULL в столбце endtime. Для этого можно определить CTE на основе внешнего запроса (с именем C2) и применить фильтр endtime IS NOT NULL в запросе к C2. Если нужно удалить интервалы с подсчетом, равным 0, используйте фильтр cnt > 0, который также удаляет строки со значением NULL в столбце endtime, так как подсчет здесь всегда нулевой. В листинге 6 приводится полное решение (предполагается, что нужно сохранить только интервалы с перекрывающимися сеансами).

Это решение сформировало план, показанный на рисунке 6, на моем компьютере для большого набора данных. Время выполнения составило 37 секунд.

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

Самая интересная особенность этого решения заключается в том, что два взаимосвязанных индекса idx_start и idx_end проверяются по очереди, но во всем плане нет ни одного явного оператора сортировки. Группирование, сведение, функции LEAD и SUM для окна и даже предложение ORDER BY — выполнение всех операций зависит от сохранения порядка данных.

Решение на основе агрегатов LEAD и ROW_NUMBER для окна

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

• порядковый номер для начальных событий (обозначается s) запроса начала;
• порядковый номер для событий завершения (обозначается e) запроса завершения;
• порядковый номер для событий начала или завершения (обозначается se) объединенного начала-завершения.

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

WITH C1 AS
(
SELECT app, starttime AS ts, +1 AS type, keycol,
ROW_NUMBER() OVER(PARTITION BY app ORDER BY starttime,
keycol) AS s, — start ordinal
NULL AS e
FROM dbo.Sessions
UNION ALL
SELECT app, endtime, -1 AS type, keycol, NULL AS s,
ROW_NUMBER() OVER(PARTITION BY app ORDER BY endtime,
keycol) AS e — end ordinal
FROM dbo.Sessions
)
SELECT *,
ROW_NUMBER() OVER(PARTITION BY app ORDER BY ts, type,
keycol) AS se — start or end ordinal
FROM C1;

На рисунке 7 показан результат этого запроса.

Рисунок 7. Последовательность событий с порядковыми номерами

Затем вычисляется число активных сеансов после каждого события. Обратите внимание (рисунок 7), что для событий начала имеется порядковый номер начала (s) и порядковые номера начала и завершения (se). Можно вычислить, сколько событий завершения произошло до этой точки, e = se — s. Затем можно вычислить число активных сеансов как cnt = s — e, или более полно как cnt = s — (se — s). Аналогично можно провести подсчет после событий завершения с использованием se и e: cnt = (se — e) — e. Чтобы получить подсчет после событий начала и завершения в одном целевом столбце, используйте формулу cnt = COALESCE(s — (se — s), s — (se — s)). Также можно возвращать вместе с каждым событием метку времени следующего события. Это достигается с помощью функции LEAD. Предположим, CTE с именем C2 определено на основе внешнего запроса в предыдущем образце программного кода. В этом случае можно задействовать следующий запрос к C2, чтобы выполнить подсчет и определить следующую метку времени:

SELECT *,
(COALESCE(
s — (se — s), — count of active intervals after start event
(se — e) — e) — count of active intervals after end event
) AS cnt,
LEAD(ts) OVER(PARTITION BY app ORDER BY ts, type, keycol)
AS nextts
FROM C2

Обратите внимание на список ORDER BY функции LEAD. Благодаря ему начальные события располагаются после событий завершения. Для разрешения конфликтов используется keycol. Точки, в которых ts отличается от nextts, представляют дискретные интервалы, и подсчеты, связанные с этими точками, охватывают все события в этих точках (то есть представляют подсчеты перекрывающихся сеансов с этими интервалами). Завершающий шаг — определить CTE на основе последнего запроса (с именем C3) и обеспечить фильтрацию с использованием внешнего запроса событий, для которых ts <> nextts. Если вы не заинтересованы в интервалах с нулевыми подсчетами, удалите их. Вот внешний запрос к C3:

SELECT
app,
ts AS starttime,
nextts AS endtime,
cnt
FROM C3
WHERE ts <> nextts
AND cnt > 0;

Листинг 7 содержит полное решение.

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

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

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

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

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

SET NOCOUNT ON;
USE tempdb;
IF OBJECT_ID(N'dbo.Sessions', N'U') IS NOT NULL DROP TABLE dbo.Sessions;
IF OBJECT_ID(N'dbo.Apps', N'U') IS NOT NULL DROP TABLE dbo.Apps;
CREATE TABLE dbo.Apps
(
app VARCHAR(10) NOT NULL,
CONSTRAINT PK_Apps PRIMARY KEY(app)
);
CREATE TABLE dbo.Sessions
(
keycol INT NOT NULL,
app VARCHAR(10) NOT NULL,
starttime DATETIME2(0) NOT NULL,
endtime DATETIME2(0) NOT NULL,
CONSTRAINT PK_Sessions PRIMARY KEY(keycol),
CONSTRAINT CHK_Sessios_et_st CHECK(endtime > starttime)
);
CREATE UNIQUE INDEX idx_start ON dbo.Sessions(app, starttime, keycol);
CREATE UNIQUE INDEX idx_end ON dbo.Sessions(app, endtime, keycol);

TRUNCATE TABLE dbo.Sessions;
TRUNCATE TABLE dbo.Apps;
INSERT INTO dbo.Apps(app) VALUES('app1'),('app2'),('app3');
INSERT INTO dbo.Sessions(keycol, app, starttime, endtime) VALUES
(2, 'app1', '20130212 08:30:00', '20130212 10:30:00'),
(3, 'app1', '20130212 08:30:00', '20130212 08:45:00'),
(5, 'app1', '20130212 09:00:00', '20130212 09:30:00'),
(7, 'app1', '20130212 09:15:00', '20130212 10:30:00'),
(11, 'app1', '20130212 09:15:00', '20130212 09:30:00'),
(13, 'app1', '20130212 10:30:00', '20130212 14:30:00'),
(17, 'app1', '20130212 10:45:00', '20130212 11:30:00'),
(19, 'app1', '20130212 11:00:00', '20130212 12:30:00'),
(23, 'app2', '20130212 08:30:00', '20130212 08:45:00'),
(29, 'app2', '20130212 09:00:00', '20130212 09:30:00'),
(31, 'app2', '20130212 11:45:00', '20130212 12:00:00'),
(37, 'app2', '20130212 12:30:00', '20130212 14:00:00'),
(41, 'app2', '20130212 12:45:00', '20130212 13:30:00'),
(43, 'app2', '20130212 13:00:00', '20130212 14:00:00'),
(47, 'app2', '20130212 14:00:00', '20130212 16:30:00'),
(53, 'app2', '20130212 15:30:00', '20130212 17:00:00'),
(61, 'app3', '20130212 08:00:00', '20130212 08:30:00'),
(62, 'app3', '20130212 08:00:00', '20130212 09:00:00'),
(63, 'app3', '20130212 09:00:00', '20130212 09:30:00'),
(64, 'app3', '20130212 09:30:00', '20130212 10:00:00');

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

TRUNCATE TABLE dbo.Sessions;
TRUNCATE TABLE dbo.Apps;
DECLARE
@numrows AS INT = 2000000, — total number of rows
@numapps AS INT = 100; — number of applications
INSERT INTO dbo.Apps WITH(TABLOCK) (app)
SELECT 'app' + CAST(n AS VARCHAR(10)) AS app
FROM dbo.GetNums(1, @numapps) AS Nums;
INSERT INTO dbo.Sessions WITH(TABLOCK)
(keycol, app, starttime, endtime)
SELECT
ROW_NUMBER() OVER(ORDER BY (SELECT NULL)) AS keycol,
D.*,
DATEADD(
second,
1 + ABS(CHECKSUM(NEWID())) % (20*60),
starttime) AS endtime
FROM
(
SELECT
'app' + CAST(1 + ABS(CHECKSUM(NEWID())) % @numapps AS VARCHAR(10)) AS app,
DATEADD(
second,
1 + ABS(CHECKSUM(NEWID())) % (30*24*60*60),
'20130101') AS starttime
FROM dbo.GetNums(1, @numrows) AS Nums
) AS D;

WITH C1 AS
(
SELECT app, starttime AS ts, +1 AS type
FROM dbo.Sessions
UNION ALL
SELECT app, endtime AS ts, -1 AS type
FROM dbo.Sessions
)
SELECT
app,
ts AS starttime,
LEAD(ts) OVER(PARTITION BY app ORDER BY ts) AS endtime,
SUM([1]-[-1]) OVER(PARTITION BY app ORDER BY ts ROWS UNBOUNDED PRECEDING) AS cnt
FROM C1
PIVOT(COUNT(type) FOR type IN([1],[-1])) AS P
ORDER BY app, starttime;

WITH C1 AS
(
SELECT app, starttime AS ts, +1 AS type
FROM dbo.Sessions
UNION ALL
SELECT app, endtime AS ts, -1 AS type
FROM dbo.Sessions
),
C2 AS
(
SELECT
app,
ts AS starttime,
LEAD(ts) OVER(PARTITION BY app ORDER BY ts) AS endtime,
SUM([1]-[-1]) OVER(PARTITION BY app ORDER BY ts ROWS UNBOUNDED PRECEDING) AS cnt
FROM C1
PIVOT(COUNT(type) FOR type IN([1],[-1])) AS P
)
SELECT *
FROM C2
WHERE cnt > 0
ORDER BY app, starttime;

WITH C1 AS
(
SELECT app, starttime AS ts, +1 AS type, keycol,
ROW_NUMBER() OVER(PARTITION BY app ORDER BY starttime, keycol) AS s, — start ordinal
NULL AS e
FROM dbo.Sessions
UNION ALL
SELECT app, endtime, -1 AS type, keycol, NULL AS s,
ROW_NUMBER() OVER(PARTITION BY app ORDER BY endtime, keycol) AS e — end ordinal
FROM dbo.Sessions
),
C2 AS
(
SELECT *,
ROW_NUMBER() OVER(PARTITION BY app ORDER BY ts, type, keycol) AS se — start or end ordinal
FROM C1
),
C3 AS
(
SELECT *,
(COALESCE(
s — (se — s), — count of active intervals after start event
(se — e) — e) — count of active intervals after end event
) AS cnt,
LEAD(ts) OVER(PARTITION BY app ORDER BY ts, type, keycol) AS nextts
FROM C2
)
SELECT
app,
ts AS starttime,
nextts AS endtime,
cnt
FROM C3
WHERE ts <> nextts
AND cnt > 0
ORDER BY app, starttime;