Интервалы и счетчики. Часть 3

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

Отличие данной статьи — в определении индексов idx_start и idx_end. Списки ключей такие же, как в предыдущих статьях серии, но на этот раз индексы дополнены предложением INCLUDE. Индекс idx_start охватывает столбец endtime, а индекс idx_end — столбец starttime. Новые индексы более эффективны для решений, описываемых в данной статье.

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

На этот раз наша задача — вычислить максимальное число одновременных сеансов в течение каждого фиксированного интервала внутри указанного периода, отдельно для каждого приложения. Например, предположим, что нужный период начинается в 8:00 12 февраля 2013 г. и заканчивается в 17:00 12 февраля 2013 г. Для каждого приложения и часа внутри данного периода необходимо вычислить максимальное число одновременных сеансов. Условимся, что если один сеанс заканчивается точно после начала другого, то два сеанса считаются одновременными. Также предположим, что сеанс начинается в 15.00 и заканчивается в 16.00. Такой сеанс считается активным во время фиксированного часового интервала, начинающегося в 15.00 и заканчивающегося в 16.00, но неактивным в течение фиксированного интервала с 16.00 до 17.00. На рисунке 1 показано, что необходимо вычислить для малого набора тестовых данных, сформированного программным кодом в листинге 1.

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

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

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

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

Для простоты в листинге 4 приведен исходный текст решения только для приложения app3. После разъяснения решения для одного приложения я покажу, как применить его ко всем приложениям. Шаги в решении разъясняются для отдельных обобщенных табличных выражений (CTE), начиная с CTE с именем C1.

Аналогично методам, описанным в предыдущих статьях, решение начинается с формирования хронологической последовательности событий. Это выполняется в теле табличного выражения (CTE) C1. В прошлом хронологическая последовательность событий строилась путем объединения только событий начала и завершения. Но этот случай особый: необходимо возвратить информацию о каждом фиксированном часовом интервале, даже если в течение интервала не произошло никаких событий (начала и завершения). Напомню, что события начала отмечаются инкрементом +1, так как эти события увеличивают подсчет активных сеансов, а события завершения отмечаются декрементом -1, так как они уменьшают подсчет. Чтобы учесть особенности нашей задачи, решение добавляет ложные записи во время начала всех фиксированных часовых интервалов, отмечая их инкрементом 0, чтобы событие не повлияло на подсчет. Таким образом решение обеспечивает наличие хотя бы одного события в каждом фиксированном интервале.

Для обработки случаев, когда события различных типов происходят в одно время, запросы в C1 назначают различное порядковое значение (ord) каждому типу событий. Событиям завершения назначается значение ord, равное 1, так как их следует рассмотреть первыми, событиям начала назначается значение 2, ложным событиям — 3.

Помните, что следует учитывать только интервалы, попадающие в определенный входной период; поэтому первые два запроса в теле C1 содержат фильтр starttime < @endtime AND endtime >= @starttime (включая @starttime и исключая @endtime), а третий запрос содержит фильтр ts >= @starttime AND ts < @endtime.

Второй шаг решения реализован обобщенным табличным выражением (CTE) с именем C2. Запрос в теле CTE запрашивает C1 и вычисляет текущий итог столбца инкрементов (значения 1, -1 и 0) с учетом порядка ts и ord. Результирующий столбец получает имя cnt:

SELECT
ts,
increment,
SUM(increment) OVER(ORDER BY ts, ord
ROWS UNBOUNDED PRECEDING) AS cnt
FROM C1

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

Следующий шаг реализуется в CTE C3. Вот запрос в теле CTE:

SELECT
DATEADD( hour, DATEDIFF(hour, @starttime, ts), @starttime )
AS starttime,
cnt
FROM C2
WHERE increment <> -1

Максимальный подсчет в течение каждого часа обязательно состоится после события начала или после ложного события (если в течение часа не произошло события начала), поэтому запрос фильтрует только события, которые не являются событиями завершения. Запрос также вычисляет для каждой метки времени соответствующее начало часа с использованием выражения DATEADD( hour, DATEDIFF(hour, @starttime, ts), @starttime ) и присваивает результирующему столбцу имя starttime.

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

SELECT
starttime,
DATEADD(hour, 1, starttime) AS endtime,
MAX(cnt) AS mx
FROM C3
GROUP BY starttime;

Решение в листинге 4 применяется к одному входному приложению. Затем эта логика инкапсулируется во встроенную табличную функцию, которая принимает в качестве входных данных приложение и период. В листинге 5 дано определение такой функции с именем IntervalCounts.

Чтобы применить функцию ко всем приложениям из таблицы Apps, применяется оператор APPLY. Ниже приведен пример использования малого набора тестовых данных с входным периодом, который начинается в 8:00 12 февраля 2013 года и завершается в 17:00 12 февраля 2013 года.

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

Этот программный код формирует желаемый результирующий набор, показанный на рисунке 2.

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

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

На рисунке 3 показан план этого запроса (с использованием Plan Explorer программы SQL Sentry).

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

Для выполнения данного запроса на моем компьютере потребовалось 13 секунд. План неплох, но его можно улучшить. Во-первых, как мы видим, SQL Server выбрал последовательный план. Без сомнения, время выполнения можно сократить с помощью параллелизма. Во-вторых, поскольку группирование основывается на вычислениях, оптимизатор не использует порядок индекса для вычисления статистического выражения; вместо этого применяется статистическое выражение Hash Match. Для хэширования требуется предоставление памяти для выполнения запроса (как и сортировки, когда оптимизатор выполняет сортировку перед использованием статистического выражения потока).

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

DECLARE @n AS BIGINT = 1;
SELECT A.app, IC.*
FROM dbo.Apps AS A
CROSS APPLY dbo.IntervalCounts(A.app, '20130101', '20130201')
AS IC
CROSS JOIN (SELECT TOP (@n) * FROM dbo.Apps) AS B
OPTION (OPTIMIZE FOR (@n = 100));

На этот раз был получен параллельный план, показанный на рисунке 4.

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

При использовании параллельного плана запрос на моем компьютере был выполнен за 7 секунд. Существует также способ избежать хэширования и сортировки. О нем будет рассказано в следующем разделе.

Избавляемся от хэширования и сортировки

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

1. Вычисляемые столбцы с именами fstartime и fendtime, содержащие приведенные к началу часа значения starttime и endtime, соответственно:

ALTER TABLE dbo.Sessions ADD
fstarttime AS
DATEADD( hour,
DATEDIFF(hour, CONVERT(DATETIME2(0),
'19000101', 112), starttime),
CONVERT(DATETIME2(0), '19000101', 112) ),
fendtime AS
DATEADD( hour,
DATEDIFF(hour, CONVERT(DATETIME2(0),
'19000101', 112), endtime),
CONVERT(DATETIME2(0), '19000101', 112) );
Indexes similar to idx_start and idx_end, but with the column holding the floored time preceding the column holding the original time. Namely, fstarttime before startime, and fendtime before endtime:
CREATE UNIQUE INDEX idx_fstart
ON dbo.Sessions(app, fstarttime, starttime, keycol)
INCLUDE(endtime);
CREATE UNIQUE INDEX idx_fend
ON dbo.Sessions(app, fendtime, endtime, keycol)
INCLUDE(starttime);

2. Изменение реализации функции IntervalCounts с использованием новых столбцов fstarttime и fendtime, как показано в листинге 6.

Приведенные столбцы добавляются в списки SELECT двух первых запросов в теле C1, а результирующему столбцу присваивается имя fts (floored timestamp). Что касается третьего запроса, который возвращает ложные события, опрашивая таблицу TimeStamps, то столбец ts уже представляет начало часа, поэтому он просто добавляется как столбец fts.

Затем вы полностью пропускаете шаг, на котором вычисляются приведенные метки времени в предшествующем решении в листинге 5, так как столбец fts в новом решении в листинге 6 уже содержит приведенные метки времени. CTE C2 в новом решении выполняет вычисление увеличения с нарастающим итогом текущего подсчета, но на этот раз fts предшествует ts в предложении порядка окна. Это позволяет оптимизатору выполнить упорядоченный просмотр индексов idx_fstart и idx_fend и использовать данный порядок на последнем шаге, реализованном внешним запросом, вычисляющим максимальный подсчет для каждой часовой группы.

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

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

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

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

У этого плана есть две интересные особенности. Во-первых, при вычислении статистического выражения не применяется хэширование или сортировка; вместо этого оптимизатор использует статистическое выражение потока на основе существующего порядка данных из индексов. Во-вторых, SQL Server выбирает параллельный план, не предполагающий участия программиста. Время выполнения этого решения на моем компьютере составило 7 секунд. Это слегка меня разочаровало, поскольку время выполнения оказалось таким же, как в предшествующем решении после применения хитрости, приведшей к параллельному плану. Однако у этого плана все же есть преимущества: не нужно никаких уловок, чтобы получить параллельный план, и запросу не требуется особого предоставления памяти для сортировки и хэширования.

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

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
— Заполнение таблицы TimeStamps
DECLARE
@s AS DATETIME2(0) = '20130101', — inclusive
@e AS DATETIME2(0) = '20140101'; — exclusive
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 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,
SUM(increment) OVER(ORDER BY ts, ord
ROWS UNBOUNDED PRECEDING) AS cnt
FROM C1
),
C3 AS
(
SELECT
DATEADD( hour, DATEDIFF(hour, @starttime, ts), @starttime ) AS starttime,
cnt
FROM C2
WHERE increment <> -1
)
SELECT
starttime,
DATEADD(hour, 1, starttime) AS endtime,
MAX(cnt) AS mx
FROM C3
GROUP BY starttime;

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,
SUM(increment) OVER(ORDER BY ts, ord
ROWS UNBOUNDED PRECEDING) AS cnt
FROM C1
),
C3 AS
(
SELECT
DATEADD( hour, DATEDIFF(hour, @starttime, ts), @starttime ) AS starttime,
cnt
FROM C2
WHERE increment <> -1
)
SELECT
starttime,
DATEADD(hour, 1, starttime) AS endtime,
MAX(cnt) AS mx
FROM C3
GROUP BY starttime;
GO

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
fendtime AS fts,
endtime AS ts,
-1 AS increment,
1 AS ord
FROM dbo.Sessions
WHERE app = @app
AND fstarttime < @endtime
AND fendtime >= @starttime
UNION ALL
SELECT
fstarttime AS fts,
starttime AS ts,
1 AS increment,
2 AS ord
FROM dbo.Sessions
WHERE app = @app
AND fstarttime < @endtime
AND fendtime >= @starttime
UNION ALL
SELECT
ts AS fts,
ts,
0 AS increment,
3 AS ord
FROM dbo.TimeStamps
WHERE ts >= @starttime AND ts < @endtime
),
C2 AS
(
SELECT
fts,
increment,
SUM(increment) OVER(ORDER BY fts, ts, ord
ROWS UNBOUNDED PRECEDING) AS cnt
FROM C1
)
SELECT
fts AS starttime,
DATEADD(hour, 1, fts) AS endtime,
MAX(cnt) AS mx
FROM C2
WHERE increment <> -1
GROUP BY fts;
GO