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

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

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

Как и в третьей статье серии, индексы idx_start и idx_end несколько отличаются от индексов в первой и второй частях. Idx_start определен для списка ключей (app, starttime, keycol) и списка включений (endtime), а индекс idx_end определен для списка ключей (app, endtime, keycol) и списка включений (starttime). В первой и второй частях индексы имеют такие же списки ключей, но не списка включений. Решениям в этой статье, как и в части 3, необходимы списки включений.

Запустите программный код в листинге 2, чтобы заполнить таблицу Sessions большим набором тестовых данных для проверки решений. В листинге 2 также создается вспомогательная функция GetNums, которая принимает низкие и высокие значения в качестве входных данных и выдает последовательность целых чисел во входном диапазоне.

Задача, на решении которой мы сосредоточимся в данной статье — выполнить подсчет активных интервалов в начале каждого фиксированного интервала в каждом периоде. Я получил этот запрос от клиента, которому требовалось подсчитать число чатов, активных в начале каждого фиксированного интервала времени. В нашем случае требовалось выполнять подсчет в начале каждого часа. Чтобы избежать путаницы, при подсчете необходимо учитывать все события конца и начала интервалов, которые произошли в соответствующий час. На рисунке 1 графически показан малый набор тестовых данных и желаемый результат для входного периода, от с '20130212 08:00:00' и до '20130212 18:00:00'.

Рисунок 1. Графическое представление подсчетов по входам фиксированных интервалов

На рисунке 2 показан желаемый результат из запроса вашего решения.

Рисунок 2. Результат выполнения подсчета по входам фиксированных интервалов

Далее будет описано два решения: одно с использованием объединения, другое с использованием оконных функций. В обоих решениях применяется вспомогательная таблица TimeStamps, как в третьей статье серии, опубликованной в предыдущем номере журнала. Используйте исходный текст в листинге 3 для создания таблицы TimeStamps и заполнения ее строками для каждого часа в 2013 г.

Решение с использованием объединений

Первое решение, вероятно, самое простое, хотя и не самое эффективное. В листинге 4 показан исходный текст решения (предполагается, что используется малый набор тестовых данных с периодом ввода от '20130212 08:00:00' и до '20130212 18:00:00').

Программный код решения выполняет перекрестное объединение между таблицей Apps (назовем ее A) и таблицей Timestamps (назовем ее T), чтобы сформировать строку для каждого приложения и начала часа. Затем выполняется левое внешнее соединение с таблицей Sessions (назовем ее S) на основе предиката A.app = S.app AND T.ts >= S.starttime AND T.ts < S.endtime. Каждая левая строка, представляющая отдельную комбинацию приложения и часа, сопоставляется по всем сеансам с тем приложением, которое было активно на момент начала сеанса. Под «активным» имеется в виду, что час начался в момент или после начала сеанса и до конца сеанса.

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

Чтобы протестировать производительность решения, примените программный код из листинга 5 к большому набору тестовых данных. Входной период начинается 1 января 2013 г. и завершается 1 февраля 2013 г.

На рисунке 3 показан план этого запроса (с использованием Plan Explorer компании SQL Sentry). Это очень обширный план. Основная ресурсоемкость приходится на объединение Hash Match, реализующее левое внешнее соединение, и агрегат Hash Match, реализующий локальный агрегат на поток. Причина высокой ресурсоемкости заключается в наличии двух предикатов диапазона, относящихся к двум различным столбцам. Для таблицы Sessions предикаты — S.starttime <= T.ts AND S.endtime > T.ts.

Рисунок 3. План исполнения для решения в листинге 5

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

Решение с использованием оконных функций

Во втором решении применяются оконные функции; оно гораздо эффективнее первого. В листинге 6 показан программный код, применяемый к малому набору тестовых данных только для одного приложения (в данном случае app1). Начало входного периода — '20130212 08:00:00', завершение — до '20130212 18:00:00'.

Вид обобщенных табличных выражений (CTE) C1 и C2 уже знаком вам по третьей статье серии. Эти два CTE — такие же, как использовавшиеся в решении в предыдущей статье. Напомню, что в программном коде CTE C1 объединены три набора событий:

1. События завершения отмечены приращением -1 и 1 в качестве позиции упорядочения (ord).
2. События начала отмечены приращением +1 и 2 в качестве позиции упорядочения.
3. Метки времени начала часа во входном периоде отмечены приращением 0 (нейтральное) и 3 в качестве позиции упорядочения. Таким образом, нейтральные события учитываются после событий начала и завершения, произошедших в одно время.

Затем программный код в CTE C2 выполняет подсчет активных интервалов после каждого события как сумму с нарастающим итогом приращений столбца, упорядоченных по метке времени события (ts) и позиции упорядочения (ord). В программном коде CTE C3 используются выражение CASE и функция LAG для подсчета активных интервалов для нейтральных событий (increment = 0). Применяемый метод к нейтральным событиям: 1 после предшествующего события, если оно существует, и 0, если его не существует. Наконец, внешний запрос фильтрует только нейтральные события и возвращает предыдущие подсчеты как текущие применимые подсчеты.

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

Используйте следующий запрос, чтобы проверить правильность решения с малым набором тестовых данных:

SELECT A.app, IC.*
FROM dbo.Apps AS A
CROSS APPLY dbo.IntervalCounts(A.app, '20130212 08:00:00', '20130212 18:00:00') AS IC;

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

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

SELECT A.app, IC.*
FROM dbo.Apps AS A
CROSS APPLY dbo.IntervalCounts(A.app, '20130101', '20130201') AS IC;

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

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

Как видите, этот план весьма эффективен. Он просматривает строки из кластеризованного индекса Apps. Для каждого приложения выполняются поиск в индексе и упорядоченная проверка диапазона в каждом из индексов: idx_start, idx_end и PK_TimeStamps. Проверяется только нужный диапазон для текущего приложения. В зависимости от результатов упорядоченных проверок диапазона, план выполняет слияние строк и вычисляет все оконные функции (ROW_NUMBER и функцию LAG) даже без явной сортировки (что удивительно). На моем компьютере это решение с большим набором данных было выполнено всего за 11 секунд.

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

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) INCLUDE(endtime);
CREATE UNIQUE INDEX idx_end ON dbo.Sessions(app, endtime, keycol) INCLUDE(starttime);
— Код для заполнения таблицы Sessions малым набором тестовых данных
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
— Код для заполнения таблицы Sessions большим набором тестовых данных
TRUNCATE TABLE dbo.Sessions;
TRUNCATE TABLE dbo.Apps;
DECLARE
@numrows AS INT = 2000000, — общее число строк
@numapps AS INT = 100; — число приложений
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;

— DDL для таблицы TimeStamps
IF OBJECT_ID(N'dbo.TimeStamps', N'U') IS NOT NULL
DROP TABLE dbo.TimeStamps;
CREATE TABLE dbo.TimeStamps
(
ts DATETIME2(0) NOT NULL
CONSTRAINT PK_TimeStamps PRIMARY KEY
);
GO
— Populate TimeStamps table
DECLARE
@s AS DATETIME2(0) = '20130101', — включительно
@e AS DATETIME2(0) = '20140101'; — исключительно
INSERT INTO dbo.TimeStamps WITH (TABLOCK) (ts)
SELECT DATEADD(hour, n-1, @s) AS ts
FROM dbo.GetNums(1, DATEDIFF(hour, @s, @e)) AS Nums;
GO

DECLARE
@app AS VARCHAR(10) = 'app1',
@starttime AS DATETIME2(0) = '20130212 08:00:00', — включительно
@endtime AS DATETIME2(0) = '20130212 18:00:00'; — исключительно
SELECT A.app, T.ts, COUNT(S.keycol) AS cnt
FROM dbo.Apps AS A
CROSS JOIN dbo.TimeStamps AS T
LEFT OUTER JOIN dbo.Sessions AS S
ON A.app = S.app
AND T.ts >= S.starttime
AND T.ts < S.endtime
WHERE ts >= @starttime AND ts < @endtime
GROUP BY A.app, T.ts
ORDER BY A.app, T.ts; — для целей презентации

DECLARE
@app AS VARCHAR(10) = 'app1',
@starttime AS DATETIME2(0) = '20130101',
@endtime AS DATETIME2(0) = '20130201';
SELECT A.app, T.ts, COUNT(S.keycol) AS cnt
FROM dbo.Apps AS A
CROSS JOIN dbo.TimeStamps AS T
LEFT OUTER JOIN dbo.Sessions AS S
ON A.app = S.app
AND T.ts >= S.starttime
AND T.ts < S.endtime
WHERE ts >= @starttime AND ts < @endtime
GROUP BY A.app, T.ts;

DECLARE
@app AS VARCHAR(10) = 'app1',
@starttime AS DATETIME2(0) = '20130212 08:00:00', — включительно
@endtime AS DATETIME2(0) = '20130212 17:00:00'; — исключительно
WITH C1 AS
(
SELECT
endtime AS ts,
-1 AS increment,
1 AS ord
FROM dbo.Sessions
WHERE app = @app
AND starttime < @endtime
AND endtime >= @starttime
UNION ALL
SELECT
starttime AS ts,
1 AS increment,
2 AS ord
FROM dbo.Sessions
WHERE app = @app
AND starttime < @endtime
AND endtime >= @starttime
UNION ALL
SELECT
ts,
0 AS increment,
3 AS ord
FROM dbo.TimeStamps
WHERE ts >= @starttime AND ts < @endtime
),
C2 AS
(
SELECT
ts,
increment,
ord,
SUM(increment) OVER(ORDER BY ts, ord
ROWS UNBOUNDED PRECEDING) AS cnt
FROM C1
),
C3 AS
(
SELECT *,
CASE
WHEN increment = 0 THEN LAG(cnt, 1, 0) OVER(ORDER BY ts, ord)
END AS prv
FROM C2
)
SELECT ts, prv AS cnt
FROM C3
WHERE increment = 0
ORDER BY ts; — для целей презентации

IF OBJECT_ID(N'dbo.IntervalCounts', N'IF') IS NOT NULL DROP FUNCTION dbo.IntervalCounts;
GO
CREATE FUNCTION dbo.IntervalCounts
(
@app AS VARCHAR(10),
@starttime AS DATETIME2(0),
@endtime AS DATETIME2(0)
) RETURNS TABLE
AS
RETURN
WITH C1 AS
(
SELECT
endtime AS ts,
-1 AS increment,
1 AS ord
FROM dbo.Sessions
WHERE app = @app
AND starttime < @endtime
AND endtime >= @starttime
UNION ALL
SELECT
starttime AS ts,
1 AS increment,
2 AS ord
FROM dbo.Sessions
WHERE app = @app
AND starttime < @endtime
AND endtime >= @starttime
UNION ALL
SELECT
ts,
0 AS increment,
3 AS ord
FROM dbo.TimeStamps
WHERE ts >= @starttime AND ts < @endtime
),
C2 AS
(
SELECT
ts,
increment,
ord,
SUM(increment) OVER(ORDER BY ts, ord
ROWS UNBOUNDED PRECEDING) AS cnt
FROM C1
),
C3 AS
(
SELECT *,
CASE
WHEN increment = 0 THEN LAG(cnt, 1, 0) OVER(ORDER BY ts, ord)
END AS prv
FROM C2
)
SELECT ts, prv AS cnt
FROM C3
WHERE increment = 0;
GO