Упаковывание интервалов — классическая задача T-SQL, в которой требуется объединить несколько пересекающихся интервалов в единственный непрерывный интервал. Я подробно рассказывал об этом в статье на SolidQ (http://blogs.solidq.com/en/sqlserver/packing-intervals/). В частности, в той статье рассматривался пример с таблицей Users и таблицей Sessions. Требовалось определить непрерывные периоды с активными сеансами для каждого пользователя. Таким образом, для каждого пользователя нужно было упаковать пересекающиеся интервалы сеансов в непрерывные интервалы. Я представил два возможных решения: одно на основе функции ROW_NUMBER, поддерживаемой в SQL Server 2005 и более новых версиях, а второе с использованием оконного агрегата с фреймом, поддерживаемого в SQL Server 2012 и более новых версиях. Кроме того, в упомянутой статье я объяснял, как еще можно оптимизировать решение путем инкапсуляции логики для одной группы (пользовательской в нашем примере) во встроенную функцию, возвращающую табличное значение, с последующей обработкой таблицы Users с помощью оператора CROSS APPLY, чтобы применить функцию к каждому пользователю.
Один из читателей обратился ко мне по поводу следующего интересного варианта задачи:
«У меня аналогичная задача, но каждому интервалу назначен приоритет. Например, рассмотрим интервал для User 2 от 08.00 до 10.30.
Предположим, что интервал
- от 08.00 до 10.30 имеет приоритет 3;
- от 08.30 до 10.00 имеет приоритет 2;
- от 09.00 до 09.30 имеет приоритет 1.
Приоритет 1 — высший или самый важный.
После объединения результат будет следующим:
- 08.00-08.30, приоритет 3;
- 08.30-09.00, приоритет 2;
- 09.00-09.30, приоритет 1;
- 09.30-10.00, приоритет 2;
- 10.00-13.30, приоритет 3.
Я перепробовал много способов, и все безуспешно. Что вы можете посоветовать?»
Как выяснилось, предложенная задача весьма сложная, но одновременно очень интересная. В этой статье я представлю свое решение, но, как всегда, рекомендую сначала попытаться решить ее самостоятельно. Предупреждаю: мне пришлось потратить несколько дней на поиск эффективного решения. Я много часов размышлял над графическим представлением задачи и желаемого результата. Но усилия мои не были напрасны.
Тестовые данные и желаемый результат
Воспользуйтесь программным кодом в листинге 1, чтобы создать таблицы Users и Sessions со вспомогательными индексами и заполнить их малым набором тестовых данных.
Интервалы в таблице Sessions — закрыто-открытые интервалы, то есть значение starttime включается, а значение endtime исключается. Условная запись таких интервалов следующая: [starttime, endtime). Квадратная скобка представляет закрытый ограничитель (включающий), а круглая скобка представляет открытый ограничитель (исключающий).
В качестве примера на рисунке 1 дано графическое представление входных данных и желательные выходные данные для User2.
.jpg) |
| Рисунок 1. Графическое представление входных данных и желательные выходные данные для User2 |
Пока не обращайте внимания на голубоватые значения ptybitmap; они являются частью решения, я объясню их позже. Как показано в средней части рисунка, предполагается упаковывать группы пересекающихся интервалов с одинаковым приоритетом. Например, обратите внимание, что четыре входных интервала, активные в период с 11:00 до 13:00, преобразуются в два упакованных интервала. Как мы видим в нижней части рисунка, при наличии перекрывающихся сегментов упакованных интервалов с различными приоритетами следует возвратить сегмент с самым высоким приоритетом (наименьшим целочисленным значением). Как и в приведенном примере читателя, обратите внимание, что входные данные содержат три интервала в период с 8:00 до 10:30:
starttime endtime pty ---------- -------- ---- 08:00 10:30 3 08:30 10:00 2 09:00 09:30 1
Эти входные интервалы преобразуются в следующие выходные интервалы:
starttime endtime pty ---------- -------- ---- 08:00 08:30 3 08:30 09:00 2 09:00 09:30 1 09:30 10:00 2 10:00 10:30 3
В таблице 1 содержится полный желаемый результат для малого набора тестовых данных.
.jpg) |
После того как будет найдено рабочее решение, нужно проверить его, сравнив результат с желаемым в таблице 1. Чтобы протестировать эффективность решения, потребуется более крупный набор тестовых данных. Выполните программный код, показанный в листинге 2, чтобы создать вспомогательную функцию GetNums, а программный код в листинге 3 заполняет таблицы более крупным набором тестовых данных.
Теперь у вас есть все необходимое, чтобы приступить к решению задачи. Желаю успеха!
Далее я изложу свое решение в четырех шагах.
Шаг 1
В листинге 4 приведен программный код, в котором реализован шаг 1, а в таблице 2 вы найдете результаты этого шага.
.jpg) |
Помимо выражений для вычисления ptybitval и ptybitmap, к которым я перейду чуть позже, остальная часть кода на этом шаге реализует метод упаковки с использованием функции ROW_NUMBER, описанной в Packing Intervals (http://blogs.solidq.com/en/sqlserver/packing-intervals/). Если вы не знакомы с этим методом упаковки, то лучше всего прочитать статью, прежде чем продолжать.
Этот шаг упаковывает пересекающиеся интервалы с одинаковыми пользователем и приоритетом, возвращая начальные и конечные точки этих упакованных интервалов в отдельных строках. Вы можете определить выходные данные на этом шаге для User2 графически в средней части рисунка 1.
Напомню, что программный код в обобщенном табличном выражении C1 возвращает начало и конец событий во входных интервалах в отдельных строках. В программном коде событие начала отмечается значением +1 как тип события (именованный тип столбца), то есть данное событие увеличивает число активных интервалов, а событие завершения отмечается значением -1 (оно уменьшает число активных интервалов). Номера строк используются для счетчика событий начала (столбец с именем s) и счетчика событий завершения (столбец с именем e). Эти счетчики фиксируют, сколько событий данного типа произошло до текущего события. Значения NULL используются как местозаполнители в столбце s для событий завершения и в столбце e для событий начала. Программный код в C1 объединяет события начала и завершения, формируя единую последовательность событий.
Код в обобщенном табличном выражении C2 использует номера строк для определения объединенного значения счетчика событий в хронологическом порядке (столбец с именем se). Величину se можно рассматривать как указатель на число событий обоих типов (начала и завершения), произошедших до текущего события.
Во внешнем запросе оператор CROSS APPLY используется для определения нескольких результирующих столбцов. Результирующий столбец cs представляет количество активных интервалов непосредственно перед текущим событием начала, а столбец ce представляет количество активных интервалов непосредственно после текущего события завершения. Столбец ce вычисляется с помощью выражения: s — (se — s) — 1. В основе данного выражения лежит следующая логика: значение счетчика объединенных событий (se) за вычетом значения счетчика событий начала (s) показывает, сколько интервалов завершилось перед текущим событием начала. Если вычесть это значение из числа интервалов, начавшихся до текущего события начала, то вы получите число интервалов, активных в данной точке, вместе с текущим событием начала. Чтобы узнать, сколько интервалов было активно непосредственно перед текущим событием начала, достаточно вычесть 1. Точно так же, для вычисления ce используется выражение (se — e) — e.
Внешний запрос фильтрует только события, отмечающие начало упакованного интервала (где cs = 0) или конец упакованного интервала (где cs = 0).
Оператор APPLY вычисляет другой столбец с именем ptybitval, который преобразует приоритет в двоичное значение в двоичном виде целого числа. В SQL Server для целых чисел используется двоичное дополненное представление для целого числа, где каждый разряд положительного целого числа (кроме крайнего левого разряда) представляет двоичное значение: POWER (2, <позиция_разряда> — 1). Таким образом, с помощью выражения POWER (2, pty — 1) приоритет преобразуется в соответствующее двоичное значение. Затем это значение умножается на тип события, чтобы получить положительное двоичное значение для событий начала и отрицательное значение для событий завершения.
Далее внешний запрос в списке SELECT вычисляет столбец ptybitmap как нарастающий итог двоичных значений событий для пользователя в хронологическом порядке. Поэтому в каждой точке разряды, присутствующие в двоичном виде числа, отмечают активные приоритеты. Событие начала включает разряд, представляющий приоритет события, а событие завершения выключает его. Решение упаковывает интервалы с одним пользователем и приоритетом перед вычислением нарастающего итога, поэтому после упаковывания невозможно иметь два события одного вида в одно время. Вычисление нарастающего итога выполняется как агрегатная поразрядная операция OR. Установленный разряд в крайней правой позиции двоичного представления числа указывает на самый высокий приоритет (помните, наименьшее число) среди активных. На следующем шаге будет показано, как изолировать этот разряд. Вы увидите, что из-за этой схемы на основе двоичного вида число приоритетов в вашем решении ограничено числом доступных разрядов в используемом типе данных (минус 1 с учетом неиспользуемого левого разряда). В моей таблице используется тип INT, поэтому максимальное число приоритетов — 31. Если вам требуется больше, используйте тип BIGINT, и число приоритетов увеличится до 63.
Шаг 2
Программный код, реализующий шаг 2, показан в листинге 5, а выходные данные этого шага приведены в таблице 3.
.jpg) |
Имейте в виду, эту часть статьи без крепкого кофе не осилить.
В программном коде определено обобщенное табличное выражение C3 на основе внешнего запроса из шага 1. Внешний запрос на шаге 2 направлен к C3 и использует два оператора CROSS APPLY для вычисления нескольких столбцов результатов. Первый оператор CROSS APPLY вычисляет пару столбцов rsb (для крайнего правого установленного разряда) и prvrsb (для предшествующего правого установленного разряда). Как уже отмечалось, крайний правый установленный разряд представляет самый высокий активный приоритет (самое малое число). При использовании дополнения двоичного числа для целого числа N крайний правый установленный разряд вычисляется по формуле N & -N, где & — поразрядный оператор AND в T-SQL. Столбец rsb часто вычисляется как ptybitmap & -ptybitmap. Чтобы выяснить, каким было двоичное представление целого до применения текущего события, достаточно вычесть ptybitval из ptybitmap. Поэтому prvrsb вычисляется следующим образом:
(ptybitmap — ptybitval) & — (ptybitmap — ptybitval).
Второй оператор APPLY вычисляет два дополнительных столбца результатов с именами startpty и endpty. Они основаны на rsb и prvrsb, и потому для их расчета требуется отдельный оператор CROSS APPLY.
Столбец startpty
Если текущее событие начала или завершения начинает новый результирующий интервал, столбец startpty возвращает приоритет этого интервала, в противном случае — NULL.
Одно условие, которое делает текущее событие началом результирующего интервала: событие является событием начала (type = 1), а самый высокий активный приоритет — приоритет текущего события (rsb = ptybitval). В таком случае startpty устанавливается равным pty (приоритет текущего события). Посмотрите на рисунок 1 и таблицу 3: можете ли вы определить случаи, относящиеся к этой категории? Один пример — событие начала интервала для User2 в 8:00 с приоритетом 3. Обратите внимание, что это событие начала является одновременно началом упакованного интервала и началом выходного интервала.
Другое условие, которое делает текущее событие началом результирующего интервала: событие представляет собой событие завершения (type = -1), а самый высокий оставшийся активный приоритет ниже приоритета только что завершившегося интервала (номер больше: rsb > -ptybitval). В этом случае для startpty установлен приоритет, который представлен rsb (вычисляется как LOG (rsb, 2) + 1). Например, в 9:30 завершается упакованный интервал для User2 с приоритетом 1. Это указывает на начало выходного интервала с приоритетом 2.
Столбец endpty
Если текущее событие начала или завершения заканчивает результирующий интервал, то столбец endpty возвращает приоритет этого интервала, в противном случае — NULL.
Одно условие, которое делает текущее событие концом результирующего интервала: событие является событием завершения (type = -1) и отсутствуют оставшиеся активные интервалы (rsb = 0) или самый высокий оставшийся активный приоритет ниже, чем приоритет только что завершившегося интервала (номер больше: rsb > -ptybitval). В этом случае endpty устанавливается равным pty (приоритет текущего события). Примеры таких событий: событие завершения для User2 в 10:30 интервала с приоритетом 3 и событие завершения для User2 в 9:30 интервала с приоритетом 1.
Другое условие, которое делает текущее событие концом результирующего интервала: событие представляет собой событие начала (type = 1), а самый высокий активный приоритет перед применением текущего события ниже, чем приоритет текущего события (номер больше: prvrsb > ptybitval). Например, в 9:00 начинается упакованный интервал для User2 с приоритетом 1. Это указывает на конец выходного интервала с приоритетом 2.
Если вы дошли до этого места и поняли все, что написано выше, то я вас поздравляю. Можете перейти от кофе к чему-нибудь покрепче.
Шаг 3
Шаг 3 довольно простой. Взглянув на результат шага 2 в таблице 3, необходимо выполнить следующие действия:
- Разделить значения startpty и endpty на отдельные строки.
- Удалить все строки, в которых startpty и endpty имеют значение NULL.
Вы можете выполнить оба действия, применив оператор UNPIVOT к результатам предыдущего шага, например:
UNPIVOT (newpty FOR newtype IN (startpty, endpty)) AS U
Затем нужно создать идентификатор результирующего интервала (назовем его grp) для каждой последовательной пары событий с одинаковыми пользователем и приоритетом. Для этого следует воспользоваться номером строки (назовем его rn) в следующей формуле: (rn — 1)/2 + 1. Ниже приведено выражение T-SQL:
(ROW_NUMBER () OVER (PARTITION BY username, newpty ORDER BY ts) - 1)/2 + 1 AS grp
В листинге 6 представлен полный программный код шага 3, а в таблице 4 содержатся выходные данные этого шага.
_(3983).jpg) |
Шаг 4
Четвертый и последний шаг определяет обобщенное табличное выражение C4 (подходящее имя) во внешнем запросе из предыдущего шага (также известном как explosive query). Последний внешний запрос группирует строки из C4 по username, newpty и grp, и для каждой группы возвращает минимальное и максимальное время событий, как время начала и завершения результирующих интервалов. Вот внешний запрос:
SELECT username, newpty AS pty, MIN (ts) AS starttime, MAX (ts) AS endtime FROM C4 GROUP BY username, newpty, grp;
В листинге 7 приведен полный код решения. Выходные данные представлены ранее в таблице 1.
Для выполнения этого решения с большим набором тестовых данных (5 000 000 строк) на моем старом ноутбуке потребовалось 45 секунд. Это неплохо, но может быть и лучше.
Оптимизация решения с использованием APPLY
Хотя программный код в листинге 1 создает вспомогательные индексы для нашего решения, существует несколько оконных функций с различными особенностями секционирования и упорядочения, поэтому нельзя обойтись без пары явных операторов сортировки в плане. Оператор сортировки масштабируется по формуле N Log N. Поэтому когда в оконных функциях присутствует элемент секционирования, можно повысить производительность с помощью метода, первоначально предложенного Адамом Махаником. Используйте оператор CROSS APPLY для таблицы, содержащей секции (Users в нашем случае), и примените запрос (или встроенную функцию, возвращающую табличное значение, которая инкапсулирует запрос) к разделу. Таким образом, одна большая операция будет разделена на несколько мелких, что в данном случае приведет к повышению производительности. В листинге 8 решение для одного пользователя инкапсулировано во встроенной функции, возвращающей табличное значение, с именем PackedIntervals.
Затем можно использовать следующий запрос, чтобы применить функцию к каждому пользователю:
SELECT U.username, S.pty, S.starttime, S.endtime FROM dbo.Users AS U CROSS APPLY dbo.PackedIntervals (U.username) AS S OPTION(QUERYTRACEON 8649);
Обратите внимание, что на моем ноутбуке без флага трассировки 8649 SQL Server создает последовательный план, выполнение которого занимает всего 15 секунд. Это лишь третья часть времени выполнения первоначального решения и уже очень высокая скорость. Метод APPLY лучше работает при параллелизации, поэтому для демонстрационных целей я применил параллельный план с флагом трассировки. После параллелизации запрос был выполнен за 8 секунд с планом, показанным на рисунке 2.
.jpg) |
| Рисунок 2. План исполнения для окончательного запроса |
В определенных условиях решение может возвращать вырожденные интервалы (где starttime = endtime). Они не имеют смысла, когда интервал закрыто-открытый, как в нашем примере. Чтобы избавиться от них, достаточно добавить к самому внешнему сгруппированному запросу следующий фильтр HAVING непосредственно после предложения GROUP BY:
HAVING MAX (ts) > MIN (ts)
Соответствующий пример можно увидеть, если использовать следующие тестовые данные:
TRUNCATE TABLE dbo.Sessions;
TRUNCATE TABLE dbo.Users;
INSERT INTO dbo.Users(username)
VALUES('User1');
INSERT INTO dbo.sessions(username,
starttime, endtime, pty) VALUES
('User1', '2015-01-01', '2015-01-05', 3),
('User1', '2015-01-02', '2015-01-03', 1),
('User1', '2015-01-03', '2015-01-04', 2);
Если выполнить код решения, приведенный в листинге 7, то одной из выходных строк будет этот вырожденный интервал:
username pty starttime endtime --------- ---- ---------- ------------ User1 3 2015-01-03 00:00:00.000 2015-01-03 00:00:00.000
Добавьте приведенное выше предложение HAVING к внешнему запросу:
SELECT username, newpty AS pty, MIN (ts) AS starttime, MAX (ts) AS endtime FROM C4 GROUP BY username, newpty, grp HAVING MAX (ts) > MIN (ts);
Итак, мы рассмотрели вариант классической задачи упаковывания интервалов, где интервалы наделены приоритетами, и в случаях перекрывания предполагается, что будет возвращен сегмент с самым высоким приоритетом. В использованном мною решении широко применяются оконные функции, в том числе для вычисления номеров строк и нарастающих итогов. Для обработки приоритетов используется двоичное представление приоритетов. Наконец, с помощью метода CROSS APPLY Адама Маханика я дополнительно усовершенствовал решение, разделив одну большую масштабируемую задачу на несколько более мелких задач.
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.Users', N'U') IS NOT NULL DROP TABLE dbo.Users;
GO
CREATE TABLE dbo.Users
(
username VARCHAR(14) NOT NULL,
CONSTRAINT PK_Users PRIMARY KEY(username)
);
CREATE TABLE dbo.Sessions
(
id INT NOT NULL IDENTITY,
username VARCHAR(14) NOT NULL,
starttime DATETIME2(3) NOT NULL,
endtime DATETIME2(3) NOT NULL,
pty INT NOT NULL,
CONSTRAINT PK_Sessions PRIMARY KEY(id),
CONSTRAINT CHK_endtime_gt_starttime
CHECK (endtime > starttime),
CONSTRAINT CHK_priority_range
CHECK (pty BETWEEN 1 AND 31)
);
-- Индексы для поддержки решений
CREATE UNIQUE INDEX idx_user_start ON dbo.Sessions(username, pty, starttime, id);
CREATE UNIQUE INDEX idx_user_end ON dbo.Sessions(username, pty, endtime, id);
-- Тестовые данные (малый набор)
TRUNCATE TABLE dbo.Sessions;
TRUNCATE TABLE dbo.Users;
INSERT INTO dbo.Users(username) VALUES('User1'), ('User2'), ('User3');
INSERT INTO dbo.Sessions(username, starttime, endtime, pty) VALUES
('User1', '20160101 08:00:00.000', '20160101 08:30:00.000', 1),
('User1', '20160101 08:05:00.000', '20160101 08:35:00.000', 2),
('User1', '20160101 08:00:00.000', '20160101 08:30:00.000', 3),
('User2', '20160101 08:00:00.000', '20160101 10:30:00.000', 3),
('User2', '20160101 08:30:00.000', '20160101 10:00:00.000', 2),
('User2', '20160101 09:00:00.000', '20160101 09:30:00.000', 1),
('User2', '20160101 11:00:00.000', '20160101 12:00:00.000', 3),
('User2', '20160101 11:30:00.000', '20160101 12:30:00.000', 2),
('User2', '20160101 11:40:00.000', '20160101 12:40:00.000', 3),
('User2', '20160101 12:00:00.000', '20160101 13:00:00.000', 2),
('User3', '20160101 08:00:00.000', '20160101 09:00:00.000', 1),
('User3', '20160101 08:00:00.000', '20160101 08:30:00.000', 2),
('User3', '20160101 08:30:00.000', '20160101 09:00:00.000', 3),
('User3', '20160101 09:30:00.000', '20160101 09:31:00.000', 1);
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
-- 2 000 пользователей, 5 000 000 интервалов
DECLARE
@num_users AS INT = 2000,
@intervals_per_user AS INT = 2500,
@start_period AS DATETIME2(3) = '20160101',
@end_period AS DATETIME2(3) = '20160107',
@max_duration_in_ms AS INT = 3600000; -- 60 nimutes
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,
ABS(CHECKSUM(NEWID())) % 3 + 1 AS pty
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, pty)
SELECT username, starttime,
DATEADD(ms, ABS(CHECKSUM(NEWID())) % @max_duration_in_ms + 1, starttime)
AS endtime,
pty
FROM C;
WITH C1 AS ( SELECT id, username, starttime AS ts, pty, +1 AS type, ROW_NUMBER() OVER(PARTITION BY username, pty ORDER BY starttime, id) AS s, NULL AS e FROM dbo.Sessions UNION ALL SELECT id, username, endtime AS ts, pty, -1 AS type, NULL AS s, ROW_NUMBER() OVER(PARTITION BY username, pty ORDER BY endtime, id) AS e FROM dbo.Sessions ), C2 AS ( SELECT *, ROW_NUMBER() OVER(PARTITION BY username, pty ORDER BY ts, type DESC, id) AS se FROM C1 ) SELECT *, SUM(ptybitval) OVER(PARTITION BY username ORDER BY ts, ptybitval ROWS UNBOUNDED PRECEDING) AS ptybitmap FROM C2 CROSS APPLY ( VALUES( s - (se - s) - 1, (se - e) - e, type * POWER(2, pty - 1) ) ) AS A(cs, ce, ptybitval) WHERE cs = 0 OR ce = 0;
WITH C1 AS ( SELECT id, username, starttime AS ts, pty, +1 AS type, ROW_NUMBER() OVER(PARTITION BY username, pty ORDER BY starttime, id) AS s, NULL AS e FROM dbo.Sessions UNION ALL SELECT id, username, endtime AS ts, pty, -1 AS type, NULL AS s, ROW_NUMBER() OVER(PARTITION BY username, pty ORDER BY endtime, id) AS e FROM dbo.Sessions ), C2 AS ( SELECT *, ROW_NUMBER() OVER(PARTITION BY username, pty ORDER BY ts, type DESC, id) AS se FROM C1 ), C3 AS ( SELECT *, SUM(ptybitval) OVER(PARTITION BY username ORDER BY ts, ptybitval ROWS UNBOUNDED PRECEDING) AS ptybitmap FROM C2 CROSS APPLY ( VALUES( s - (se - s) - 1, (se - e) - e, type * POWER(2, pty - 1) ) ) AS A(cs, ce, ptybitval) WHERE cs = 0 OR ce = 0 ) SELECT id, username, ts, pty, type, ptybitval, ptybitmap, rsb, prvrsb, startpty, endpty FROM C3 CROSS APPLY ( VALUES( ptybitmap & -ptybitmap, (ptybitmap - ptybitval) & -(ptybitmap - ptybitval) ) ) AS A1(rsb, prvrsb) CROSS APPLY ( VALUES( CASE WHEN type = 1 AND rsb = ptybitval THEN pty WHEN type = -1 AND rsb > -ptybitval THEN LOG(rsb, 2) + 1 END, CASE WHEN type = -1 AND (rsb = 0 OR rsb > -ptybitval) THEN pty WHEN type = 1 AND prvrsb > ptybitval THEN LOG(prvrsb, 2) + 1 END ) ) AS A2(startpty, endpty);
WITH C1 AS ( SELECT id, username, starttime AS ts, pty, +1 AS type, ROW_NUMBER() OVER(PARTITION BY username, pty ORDER BY starttime, id) AS s, NULL AS e FROM dbo.Sessions UNION ALL SELECT id, username, endtime AS ts, pty, -1 AS type, NULL AS s, ROW_NUMBER() OVER(PARTITION BY username, pty ORDER BY endtime, id) AS e FROM dbo.Sessions ), C2 AS ( SELECT *, ROW_NUMBER() OVER(PARTITION BY username, pty ORDER BY ts, type DESC, id) AS se FROM C1 ), C3 AS ( SELECT *, SUM(ptybitval) OVER(PARTITION BY username ORDER BY ts, ptybitval ROWS UNBOUNDED PRECEDING) AS ptybitmap FROM C2 CROSS APPLY ( VALUES( s - (se - s) - 1, (se - e) - e, type * POWER(2, pty - 1) ) ) AS A(cs, ce, ptybitval) WHERE cs = 0 OR ce = 0 ) SELECT id, username, ts, newpty, newtype, (ROW_NUMBER() OVER(PARTITION BY username, newpty ORDER BY ts) - 1) / 2 + 1 AS grp FROM C3 CROSS APPLY ( VALUES( ptybitmap & -ptybitmap, (ptybitmap - ptybitval) & -(ptybitmap - ptybitval) ) ) AS A1(rsb, prvrsb) CROSS APPLY ( VALUES( CASE WHEN type = 1 AND rsb = ptybitval THEN pty WHEN type = -1 AND rsb > -ptybitval THEN LOG(rsb, 2) + 1 END, CASE WHEN type = -1 AND (rsb = 0 OR rsb > -ptybitval) THEN pty WHEN type = 1 AND prvrsb > ptybitval THEN LOG(prvrsb, 2) + 1 END ) ) AS A2(startpty, endpty) UNPIVOT (newpty FOR newtype IN (startpty, endpty)) AS U;
WITH C1 AS ( SELECT id, username, starttime AS ts, pty, +1 AS type, ROW_NUMBER() OVER(PARTITION BY username, pty ORDER BY starttime, id) AS s, NULL AS e FROM dbo.Sessions UNION ALL SELECT id, username, endtime AS ts, pty, -1 AS type, NULL AS s, ROW_NUMBER() OVER(PARTITION BY username, pty ORDER BY endtime, id) AS e FROM dbo.Sessions ), C2 AS ( SELECT *, ROW_NUMBER() OVER(PARTITION BY username, pty ORDER BY ts, type DESC, id) AS se FROM C1 ), C3 AS ( SELECT *, SUM(ptybitval) OVER(PARTITION BY username ORDER BY ts, ptybitval ROWS UNBOUNDED PRECEDING) AS ptybitmap FROM C2 CROSS APPLY ( VALUES( s - (se - s) - 1, (se - e) - e, type * POWER(2, pty - 1) ) ) AS A(cs, ce, ptybitval) WHERE cs = 0 OR ce = 0 ), C4 AS ( SELECT *, (ROW_NUMBER() OVER(PARTITION BY username, newpty ORDER BY ts) - 1) / 2 + 1 AS grp FROM C3 CROSS APPLY ( VALUES( ptybitmap & -ptybitmap, (ptybitmap - ptybitval) & -(ptybitmap - ptybitval) ) ) AS A1(rsb, prvrsb) CROSS APPLY ( VALUES( CASE WHEN type = 1 AND rsb = ptybitval THEN pty WHEN type = -1 AND rsb > -ptybitval THEN LOG(rsb, 2) + 1 END, CASE WHEN type = -1 AND (rsb = 0 OR rsb > -ptybitval) THEN pty WHEN type = 1 AND prvrsb > ptybitval THEN LOG(prvrsb, 2) + 1 END ) ) AS A2(startpty, endpty) UNPIVOT (newpty FOR newtype IN (startpty, endpty)) AS U ) SELECT username, newpty AS pty, MIN(ts) AS starttime, MAX(ts) AS endtime FROM C4 GROUP BY username, newpty, grp;
IF OBJECT_ID(N'dbo.PackedIntervals', N'IF') IS NOT NULL DROP FUNCTION dbo.PackedIntervals; GO CREATE FUNCTION dbo.PackedIntervals(@username AS VARCHAR(14)) RETURNS TABLE AS RETURN WITH C1 AS ( SELECT id, starttime AS ts, pty, +1 AS type, ROW_NUMBER() OVER(PARTITION BY username, pty ORDER BY starttime, id) AS s, NULL AS e FROM dbo.Sessions WHERE username = @username UNION ALL SELECT id, endtime AS ts, pty, -1 AS type, NULL AS s, ROW_NUMBER() OVER(PARTITION BY username, pty ORDER BY endtime, id) AS e FROM dbo.Sessions WHERE username = @username ), C2 AS ( SELECT *, ROW_NUMBER() OVER(PARTITION BY pty ORDER BY ts, type DESC, id) AS se FROM C1 ), C3 AS ( SELECT *, SUM(ptybitval) OVER(ORDER BY ts, ptybitval ROWS UNBOUNDED PRECEDING) AS ptybitmap FROM C2 CROSS APPLY ( VALUES( s - (se - s) - 1, (se - e) - e, type * POWER(2, pty - 1) ) ) AS A(cs, ce, ptybitval) WHERE cs = 0 OR ce = 0 ), C4 AS ( SELECT *, (ROW_NUMBER() OVER(PARTITION BY newpty ORDER BY ts) - 1) / 2 + 1 AS grp FROM C3 CROSS APPLY ( VALUES( ptybitmap & -ptybitmap, (ptybitmap - ptybitval) & -(ptybitmap - ptybitval))) AS A1(rsb, prvrsb) CROSS APPLY ( VALUES( CASE WHEN type = 1 AND rsb = ptybitval THEN pty WHEN type = -1 AND rsb > -ptybitval THEN LOG(rsb, 2) + 1 END, CASE WHEN type = -1 AND (rsb = 0 OR rsb > -ptybitval) THEN pty WHEN type = 1 AND prvrsb > ptybitval THEN LOG(prvrsb, 2) + 1 END ) ) AS A2(startpty, endpty) UNPIVOT (newpty FOR newtype IN (startpty, endpty)) AS U ) SELECT newpty AS pty, MIN(ts) AS starttime, MAX(ts) AS endtime FROM C4 GROUP BY newpty, grp; GO