Упаковка интервалов в T-SQL
86Работа с базами данных в .NET Framework --- Оконные функции T-SQL --- Упаковка интервалов
Исходник базы данныхУпаковка интервалов подразумевает группировку каждого набора смежных интервалов так, чтобы никакой интервал группы не перекрывался и не соседствовал (не граничил) с каким-либо интервалом других групп, и возвращение минимального начала и максимального конца каждой группы. Часто задачи упаковки в SQL Server предусматривают элемент секционирования (например, по пользователю или приложению) — тогда упаковка выполняется для каждой секции независимо.
В сценарии, который я использую для демонстрации решений задачи упаковки интервалов, применяются пользовательские сеансы приложений или служб. Используйте следующий код для создания таблиц Users (пользователи) и Sessions (сеансы) и наполнения их тестовыми данными для проверки работы решений:
SET NOCOUNT ON;
USE TSQL2012;
IF OBJECT_ID('dbo.Sessions') IS NOT NULL DROP TABLE dbo.Sessions;
IF OBJECT_ID('dbo.Users') IS NOT NULL DROP TABLE dbo.Users;
CREATE TABLE dbo.Users
(
username VARCHAR(14) NOT NULL,
CONSTRAINT PK_Users PRIMARY KEY(username)
);
GO
INSERT INTO dbo.Users(username) VALUES('User1'), ('User2'), ('User3');
CREATE TABLE dbo.Sessions
(
id INT NOT NULL IDENTITY(1, 1),
username VARCHAR(14) NOT NULL,
starttime DATETIME2(3) NOT NULL,
endtime DATETIME2(3) NOT NULL,
CONSTRAINT PK_Sessions PRIMARY KEY(id),
CONSTRAINT CHK_endtime_gteq_starttime
CHECK (endtime >= starttime)
);
GO
INSERT INTO dbo.Sessions(username, starttime, endtime) VALUES
('User1', '20121201 08:00:00.000', '20121201 08:30:00.000'),
('User1', '20121201 08:30:00.000', '20121201 09:00:00.000'),
('User1', '20121201 09:00:00.000', '20121201 09:30:00.000'),
('User1', '20121201 10:00:00.000', '20121201 11:00:00.000'),
('User1', '20121201 10:30:00.000', '20121201 12:00:00.000'),
('User1', '20121201 11:30:00.000', '20121201 12:30:00.000'),
('User2', '20121201 08:00:00.000', '20121201 10:30:00.000'),
('User2', '20121201 08:30:00.000', '20121201 10:00:00.000'),
('User2', '20121201 09:00:00.000', '20121201 09:30:00.000'),
('User2', '20121201 11:00:00.000', '20121201 11:30:00.000'),
('User2', '20121201 11:32:00.000', '20121201 12:00:00.000'),
('User2', '20121201 12:04:00.000', '20121201 12:30:00.000'),
('User3', '20121201 08:00:00.000', '20121201 09:00:00.000'),
('User3', '20121201 08:00:00.000', '20121201 08:30:00.000'),
('User3', '20121201 08:30:00.000', '20121201 09:00:00.000'),
('User3', '20121201 09:30:00.000', '20121201 09:30:00.000');Вот результат, который нужно получить на основе этих данных:
На рисунке ниже показаны как исходные интервалы из таблицы Sessions (полосы), так и упакованные интервалы (стрелки):
Следующим кодом наполните таблицу Sessions большим набором тестовых данных для проверки производительности готового решения:
DECLARE
@num_users AS INT = 2000,
@intervals_per_user AS INT = 2500,
@start_period AS DATETIME2(3) = '20120101',
@end_period AS DATETIME2(3) = '20120107',
@max_duration_in_ms AS INT = 3600000; -- 60 minutes
TRUNCATE TABLE dbo.Sessions;
TRUNCATE TABLE dbo.Users;
INSERT INTO dbo.Users(username)
SELECT 'User' + RIGHT('000000000' + CAST(U.n AS VARCHAR(10)), 10) AS username
FROM dbo.GetNums(1, @num_users) AS U;
WITH C AS
(
SELECT 'User' + RIGHT('000000000' + CAST(U.n AS VARCHAR(10)), 10) AS username,
DATEADD(ms, ABS(CHECKSUM(NEWID())) % 86400000,
DATEADD(day, ABS(CHECKSUM(NEWID())) % DATEDIFF(day, @start_period, @end_period), @start_period)) AS starttime
FROM dbo.GetNums(1, @num_users) AS U
CROSS JOIN dbo.GetNums(1, @intervals_per_user) AS I
)
INSERT INTO dbo.Sessions WITH (TABLOCK) (username, starttime, endtime)
SELECT username, starttime,
DATEADD(ms, ABS(CHECKSUM(NEWID())) % (@max_duration_in_ms + 1), starttime) AS endtime
FROM C;Этот код добавляет 5 млн строк в таблицу Sessions. Я заполнил таблицу данными 2000 пользователей с 2500 сеансами у каждого на протяжении недели, причем длительность сеанса меньше или равна часу. Но вы вправе задать свои параметры и заполнить таблицу другим объемом данных.
Традиционное решение на основе наборов
Первое решение — классический вариант, который выполняет задачу, но очень неэффективно. Для него нужны следующие два индекса:
CREATE INDEX idx_user_start_end ON dbo.Sessions(username, starttime, endtime);
CREATE INDEX idx_user_end_start ON dbo.Sessions(username, endtime, starttime);Вот код решения:
WITH StartTimes AS
(
SELECT DISTINCT username, starttime
FROM dbo.Sessions AS S1
WHERE NOT EXISTS
(SELECT * FROM dbo.Sessions AS S2
WHERE S2.username = S1.username
AND S2.starttime < S1.starttime
AND S2.endtime >= S1.starttime)
),
EndTimes AS
(
SELECT DISTINCT username, endtime
FROM dbo.Sessions AS S1
WHERE NOT EXISTS
(SELECT * FROM dbo.Sessions AS S2
WHERE S2.username = S1.username
AND S2.endtime > S1.endtime
AND S2.starttime <= S1.endtime)
)
SELECT username, starttime,
(SELECT MIN(endtime) FROM EndTimes AS E
WHERE E.username = S.username
AND endtime >= starttime) AS endtime
FROM StartTimes AS S;CTE-выражение StartTimes выделяет начала упакованных интервалов, используя запрос, который возвращает все начала интервалов, для которых не удается найти другого интервала этого же пользователя, который начался до начала текущего интервала и закончился одновременно или после начала текущего интервала. CTE-выражение EndTimes выделяет концы упакованных интервалов, используя запрос, который возвращает все концы интервалов, для которых не удается найти другого интервала этого же пользователя, который завершился после конца текущего интервала и закончился одновременно или до конца текущего интервала. После этого внешний запрос сопоставляет каждому началу упакованного интервала ближайший конец интервала и продолжает обработку, возвращая минимальное время конца, которое больше или равно текущему началу.
Как я уже говорил, это решение очень неэффективно. Для обработки тестовых данных из 5 млн строк в таблице Sessions потребовалось несколько часов. Прежде чем продолжить надо удалить ранее созданные индексы:
DROP INDEX idx_user_start_end ON dbo.Sessions;
DROP INDEX idx_user_end_start ON dbo.Sessions;Решения на основе оконных функций
Далее я расскажу о двух сравнительно новых основанных на оконных функциях способах, которые намного быстрее традиционного решения. Для новых решений надо создать такие индексы:
CREATE UNIQUE INDEX idx_user_start_id ON dbo.Sessions(username, starttime, id);
CREATE UNIQUE INDEX idx_user_end_id ON dbo.Sessions(username, endtime, id);В первом способе в основном задействована функция ROW_NUMBER. Полное решение приведено ниже. На моем ноутбуке оно обрабатывает 5 млн строк за 47 секунд:
WITH C1 AS
-- пусть e будет кол-вом событий начала, а s = завершения сеансов
(
SELECT id, username, starttime AS ts, +1 AS type, NULL AS e,
ROW_NUMBER() OVER(PARTITION BY username ORDER BY starttime, id) AS s
FROM dbo.Sessions
UNION ALL
SELECT id, username, endtime AS ts, -1 AS type,
ROW_NUMBER() OVER(PARTITION BY username ORDER BY endtime, id) AS e,
NULL AS s
FROM dbo.Sessions
),
C2 AS
-- пусть se является кол-вом событий начала или завершения интервалов,
-- то есть числом событий (начала или завершения) до текущего момента
(
SELECT C1.*, ROW_NUMBER() OVER(PARTITION BY username ORDER BY ts, type DESC, id) AS se
FROM C1
),
C3 AS
-- Для событий начала выражение s - (se - s) - 1 показывает,
-- сколько сеансов были активны непосредственно перед текущим сеансом (hence - 1)
--
-- Для событий завершения выражение (se - e) - e показывает,
-- сколько сеансов были активны непосредственно после текущего сеанса
--
-- Эти два выражения точно равны 0 в моменты соответственно
-- начала и конца упакованных интервалов
--
-- После фильтрации только событий начала или конца упакованных интервалов
-- группируем отдельные пары соседних событий начала и завершения
(
SELECT username, ts,
FLOOR((ROW_NUMBER() OVER(PARTITION BY username ORDER BY ts) - 1) / 2 + 1) AS grpnum
FROM C2
WHERE COALESCE(s - (se - s) - 1, (se - e) - e) = 0
)
SELECT username, MIN(ts) AS starttime, max(ts) AS endtime
FROM C3
GROUP BY username, grpnum;
Код CTE-выражения C1 унифицирует события начала и конца в одну хронологическую последовательность событий (начала или конца). События начата отмечаются типом события «+1», потому что в этом случае число активных сеансов увеличивается, а события конца отмечаются типом «-1», потому что они уменьшают число активных сеансов. На рисунке ниже показана хронологическая последовательность унифицированных событий, отсортированных по username, ts, type DESC, id, а столбцы справа показывают, сколько сеансов были активны до и после каждого события.
Заметьте, что упакованный интервал всегда начинается, когда число активных сеансов до события начала равно нулю, и завершается, когда число активных сеансов после события завершения равно нулю. Поэтому по отношению к каждому событию начала надо знать, сколько сеансов активны до него, а по отношению к каждому событию завершения, — сколько сеансов активны после него. Эта информация вычисляется поэтапно.
Заметьте, что код в CTE-выражении C1 вычисляет число событий начала (атрибут по имени s), при этом значения NULL используются как знаки подстановки в этот атрибут вместо событий завершения, а также вычисляет число событий завершения (атрибут по имени e), при этом значения NULL используются как знаки подстановки в этот атрибут вместо событий начала. Код CTE-выражения C2 просто суммирует число событий начала и завершения (атрибут по имени se), секционированных по username и сортированных по ts, type DESC, id. Ниже приводится результат работы C2, отсортированный по username, ts, type DESC, id:
Все самое важное происходит в коде CTE-выражения C3. Для каждого события начала известно, сколько сеансов началось до этого (s), а также мы знаем, сколько сеансов начались или закончились до этого (se). Поэтому можно легко вычислить, сколько сеансов закончились на данный момент (se - s). Заметьте, что мы знаем, сколько сеансов началось и сколько закончилось, поэтому можно определить, сколько сеансов активны после события начала: s - (se - s). Можно к этому отнестись как к вычислению, сколько человек в комнате, если в нее вошли x и вышли y человек. Наконец, чтобы определить, сколько сеансов были активны до данного события начала, просто отнимем единицу из полученной ранее величины: s - (se - s) - 1.
Аналогично определяется число активных сеансов после каждого события завершения. Имея число сеансов, завершившихся (e), а также начавшихся или завершившихся (se) до текущего момента, можно вычислить, сколько сеансов было начато: se - е. Тогда число активных сеансов равно (se - е) - е.
А теперь вспомним, что нужно отобрать только события начала, у которых число активных сеансов до этого события равно нулю, а также события завершения, после которых число активных сеансов становится нулевым. Оба фильтра можно унифицировать в один:
WHERE COALESCE(s - (se - s) - 1, (se - e) - e) = 0
После отбора получаем пары смежных событий начала и завершения, каждая из которых обозначает начало и конец упакованного интервала. Нужно назначить идентификатор группы каждой паре, чтобы можно было потом свести их в одну строку. Эту задачу можно решить, назначая номера строк (назовем это n) и вычисления (n - 1)/2 + 1, где деление выполняется нацело. Для значений n = 1,2,3,4,... получаем результат 1,1,2,2,....
В SQL Server арифметический оператор деления (/) обозначает целочисленное деление, в котором операндами являются целые числа, но в Oracle этот оператор означает десятичное деление. Я добавил функцию FLOOR, чтобы код работал корректно в обеих СУБД. Таким образом, код CTE-выражения C3 возвращает такой результат:
Внешнему запросу остается выполнить группировку строк, полученных из C3 по username и grpnum и вернуть минимальное значение ts в качестве начала и ts — в качестве конца упакованного интервала.
План, созданный оптимизатором SQL Server для этого запроса, исключительно эффективный при условии, что вы создали упомянутые выше индексы idx_user_start_id и idx_user_end_id. План показан на рисунке:
Самое замечательное в этом плане то, что в нем применяются два упорядоченных просмотра индексов, созданных для поддержки этого решения (idx_user_start_id и idx_user_end_id), причем решение полагается на эти упорядоченные просмотры при выполнении (сделайте глубокий вдох) вычисления:
номеров строк для счетчиков событий начала (s);
соединения слиянием для унификации результатов;
количества событий начала и завершения (se) в унифицированных наборах
номеров строк, которые нужны для получения grpnum после фильтрации
И все это выполняется без единого оператора сортировки! Действительно радостно видеть, что оптимизатор так точно понимает принцип представления упорядочения. Наконец хеш-агрегат используется для группировки данных по grpnum (строк, оставшихся после фильтрации). Так как у большинства операций в этом плане линейная масштабируемость, все решение должно масштабироваться примерно линейно.
В общем зачете план предусматривает только два просмотра данных (по разу на каждый индекс) в порядке индекса. Как я говорил, на выполнение этого решения на моем ноутбуке уходит всего 47 секунд. Но есть одна вещь, которая в этом решении используется недостаточно эффективно — параллелизм. И эта проблема решена в следующем решении.
Чтобы задействовать параллелизм «по полной», нужно инкапсулировать логику решения из предыдущего примера в табличное выражение, которое работает с одним пользователем, а затем применить его к каждому пользователю. Здесь предполагается, что у вас есть таблица с уникальными пользователями, что вполне справедливо. После этого очень удобно инкапсулировать логику решения для одного пользователя во встроенную табличную функцию, как в этом коде:
IF OBJECT_ID('dbo.UserIntervals', 'IF') IS NOT NULL DROP FUNCTION dbo.UserIntervals;
GO
CREATE FUNCTION dbo.UserIntervals(@user AS VARCHAR(14)) RETURNS TABLE
AS
RETURN
WITH C1 AS
(
SELECT id, starttime AS ts, +1 AS type, NULL AS e,
ROW_NUMBER() OVER(ORDER BY starttime, id) AS s
FROM dbo.Sessions
WHERE username = @user
UNION ALL
SELECT id, endtime AS ts, -1 AS type,
ROW_NUMBER() OVER(ORDER BY endtime, id) AS e,
NULL AS s
FROM dbo.Sessions
WHERE username = @user
),
C2 AS
(
SELECT C1.*, ROW_NUMBER() OVER(ORDER BY ts, type DESC, id) AS se
FROM C1
),
C3 AS
(
SELECT ts,
FLOOR((ROW_NUMBER() OVER(ORDER BY ts) - 1) / 2 + 1) AS grpnum
FROM C2
WHERE COALESCE(s - (se - s) - 1, (se - e) - e) = 0
)
SELECT MIN(ts) AS starttime, max(ts) AS endtime
FROM C3
GROUP BY grpnum;После этого можно использовать оператор CROSS APPLY для применения этой функции к каждому пользователю в таблице Users:
SELECT U.username, A.starttime, A.endtime
FROM dbo.Users AS U
CROSS APPLY dbo.UserIntervals(U.username) AS A;Для этого запроса SQL Server генерирует параллельный план, показанный на рисунке:
Как видите, в плане применяется параллельный просмотр кластеризованного индекса таблицы Users, после чего отдельные пользователи обрабатываются во внутренней ветке соединения Nested Loops. Операции во внутренней ветке что-то напоминают — это похоже на происходящее в плане из предыдущего рисунка, но на этот раз обрабатываются данные только одного пользователя. Естественно, что внутренняя ветка выполняется параллельно многими потоками. На моем мобильном компьютере выполнение этого кода заняло шесть секунд.
Второе решение на основе оконных функций показано в примере ниже. В нем используется оконная функция агрегирования SUM с использованием особенностей определения окна, появившихся в SQL Server 2012:
WITH C1 AS
(
SELECT username, starttime AS ts, +1 AS type, 1 AS sub
FROM dbo.Sessions
UNION ALL
SELECT username, endtime AS ts, -1 AS type, 0 AS sub
FROM dbo.Sessions
),
C2 AS
(
SELECT C1.*,
SUM(type) OVER(PARTITION BY username ORDER BY ts, type DESC
ROWS BETWEEN UNBOUNDED PRECEDING
AND CURRENT ROW) - sub AS cnt
FROM C1
),
C3 AS
(
SELECT username, ts,
FLOOR((ROW_NUMBER() OVER(PARTITION BY username ORDER BY ts) - 1) / 2 + 1) AS grpnum
FROM C2
WHERE cnt = 0
)
SELECT username, MIN(ts) AS starttime, max(ts) AS endtime
FROM C3
GROUP BY username, grpnum;
В этом решении применяются принципы, похожие на те, что используются в предыдущем решении, но вместо номеров строк для вычислении числа активных сеансов в каждый момент времени задействована оконная функция агрегирования SUM. Нарастающий итог типов (как вы помните, «+1» представляет событие начала сеанса, а «-1» - событие завершения) в хронологическом порядке, секционированным но username, является числом активных сеансов в каждым момент времени. А теперь вспомним, что для событий начала сеанса надо знать число активных сеансов до этих событий, а для событий завершения число активных сеансов после этих событий. Поэтому нужно отнять единицу от числа событий начала сеанса и ничего не вычитать из числа событий завершения. Это решение генерирует атрибут но имени sub, принимающий значение «1» для событий начала и «0» для событий завершения, после этого это значение вычитается из нарастающего итога с применением следующего выражения:
SUM(type) OVER(PARTITION BY username ORDER BY ts, type DESC
ROWS BETWEEN UNBOUNDED PRECEDING
AND CURRENT ROW) - sub AS cntОстальное похоже на логику предыдущего решения. Для этого решения создается план, покапанный на предыдущем рисунке, и оно выполняется на моем ноутбуке за 87 секунд.
Примененный в предыдущем решении прием создания встроенной табличной функции для одного пользователя и применения оператора APPLY для вызова этой функции для каждого пользователя в таблице Users можно использовать и в решении на основе оконного агрегата SUM. Вот код определения встроенной функции:
IF OBJECT_ID('dbo.UserIntervals', 'IF') IS NOT NULL DROP FUNCTION dbo.UserIntervals;
GO
CREATE FUNCTION dbo.UserIntervals(@user AS VARCHAR(14)) RETURNS TABLE
AS
RETURN
WITH C1 AS
(
SELECT starttime AS ts, +1 AS type, 1 AS sub
FROM dbo.Sessions
WHERE username = @user
UNION ALL
SELECT endtime AS ts, -1 AS type, 0 AS sub
FROM dbo.Sessions
WHERE username = @user
),
C2 AS
(
SELECT C1.*,
SUM(type) OVER(ORDER BY ts, type DESC
ROWS BETWEEN UNBOUNDED PRECEDING
AND CURRENT ROW) - sub AS cnt
FROM C1
),
C3 AS
(
SELECT ts,
FLOOR((ROW_NUMBER() OVER(ORDER BY ts) - 1) / 2 + 1) AS grpnum
FROM C2
WHERE cnt = 0
)
SELECT MIN(ts) AS starttime, max(ts) AS endtime
FROM C3
GROUP BY grpnum;А вот запрос, который применяет эту функцию к каждому пользователю:
SELECT U.username, A.starttime, A.endtime
FROM dbo.Users AS U
CROSS APPLY dbo.UserIntervals(U.username) AS A;Для этого решения создается план, показанный на рисунке ниже, и оно выполняется на моем ноутбуке за 13 секунд:
