Packing intervals is a classic T-SQL task that involves packing groups of intervals that intersect into single continuous intervals. I covered the topic in detail in this SolidQ article. The specific example I used in that article involved a table called Users and a table called Sessions. The task was to identify, for each user, the continuous periods with active sessions. This meant that for each user you had to pack the intersecting session intervals into single continuous intervals. I provided two possible solutions—one based on the ROW_NUMBER function, which is supported in SQL Server 2005 and later, and another using a window aggregate with a frame, which is supported in SQL Server 2012 and later. I also explained how you can further optimize your solution by encapsulating the logic for a single group (user, in our example) in an inline table-valued function (inline TVF), and then use the CROSS APPLY operator against the Users table to apply the function to each user.
A reader named Ralf posted the following question concerning an interesting variation of the task:
“I have a similar problem, but each interval has priorities.
For example, consider the interval from User 2 from 08.00 – 10.30.
suppose that from
08.00 – 10.30 has priority 3
08.30 – 10.00 has priority 2
09.00 – 09.30 has priority 1
with prio 1 is the highest / most important.
If I consolidate this, the output should be:
08.00 – 08.30, prio 3
08.30 – 09.00, prio 2
09.00 – 09.30, prio 1
09.30 – 10.00, prio 2
10.00 – 13.30, prio 3
I tried a lot with no success. Do you have a tip?
Best regards
Ralf”
As it turned out, the task was pretty challenging, but also very interesting. In this article I provide my solution, but as always, I do urge you to try solving it yourself before you look at mine. I should warn you, though, that it took me a few days to figure out an efficient solution, with many hours of staring at a graphical depiction of the problem and the desired result, but it was so worth it!
Sample data and desired result
Use the code in Listing 1 to create the Users and Sessions tables with supporting indexes, and to fill them with a small set of sample data.
Listing 1: DDL and small set of sample data
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)
);
-- Indexes to support solutions
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);
-- Sample data (small)
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);
The intervals in the Sessions table are closed-open intervals, meaning that the starttime value is included and the endtime value is excluded. The formal representation of such intervals is: [starttime, endtime). A square bracket represents a closed delimiter (inclusive), and an angle bracket represents an open delimiter (exclusive).
Figure 1 has a graphical depiction of the input and desired output for User2 as an example.
The intervals in the Sessions table are closed-open intervals, meaning that the starttime value is included and the endtime value is excluded. The formal representation of such intervals is: [starttime, endtime). A square bracket represents a closed delimiter (inclusive), and an angle bracket represents an open delimiter (exclusive).
Figure 1 has a graphical depiction of the input and desired output for User2 as an example.
For now, ignore the bluish ptybitmap values; they are part of the solution and I’ll explain them later. As you can see in the middle part of the figure, you are supposed to pack groups of intersecting intervals with the same priority. For example, notice that the four input intervals that were active during the period 11:00 – 13:00 translate to two packed intervals. As you can see in the bottom part of the figure, if you have overlapping segments of packed intervals with different priorities you should return the segment with the highest priority (lowest integer). Just like in Ralf’s example, observe that the input contains three intervals during the period 8:00 – 10:30:
starttime endtime pty
---------- -------- ----
08:00 10:30 3
08:30 10:00 2
09:00 09:30 1
These input intervals translate to the following output intervals:
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
Table 1 has the complete desired result for the small set of sample data.
Table 1: Desired result for small set of sample data
username pty starttime endtime
--------- ---- -------------------- --------------------
User1 1 2016-01-01 08:00:00 2016-01-01 08:30:00
User1 2 2016-01-01 08:30:00 2016-01-01 08:35:00
User2 1 2016-01-01 09:00:00 2016-01-01 09:30:00
User2 2 2016-01-01 08:30:00 2016-01-01 09:00:00
User2 2 2016-01-01 09:30:00 2016-01-01 10:00:00
User2 2 2016-01-01 11:30:00 2016-01-01 13:00:00
User2 3 2016-01-01 08:00:00 2016-01-01 08:30:00
User2 3 2016-01-01 10:00:00 2016-01-01 10:30:00
User2 3 2016-01-01 11:00:00 2016-01-01 11:30:00
User3 1 2016-01-01 08:00:00 2016-01-01 09:00:00
User3 1 2016-01-01 09:30:00 2016-01-01 09:31:00
Once you come up with a working solution, you will want to verify its correctness by comparing your result to the desired one in Table 1. To test the efficiency of your solution you will need a larger set of sample data. Run the code in Listing 2 to create the helper function GetNums, and the code in Listing 3 to populate the tables with a large set of sample data.
Listing 2: Helper function GetNums
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
Listing 3: Large set of sample data
-- 2,000 users, 5,000,000 intervals
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;
You should have everything you need to start working on the challenge. Good luck!
The solution, Step 1
I’ll describe my solution in four steps. Listing 4 has the code that implements step 1 and Table 2 has the result of this step.
Listing 4: Step 1
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;
Table 2: Result of step 1
id username ts pty type s e se cs ce ptybitval ptybitmap
--- --------- -------------------- ---- ----- ----- ----- --- ----- ----- ---------- ----------
1 User1 2016-01-01 08:00:00 1 1 1 NULL 1 0 NULL 1 1 (001)
3 User1 2016-01-01 08:00:00 3 1 1 NULL 1 0 NULL 4 5 (101)
2 User1 2016-01-01 08:05:00 2 1 1 NULL 1 0 NULL 2 7 (111)
3 User1 2016-01-01 08:30:00 3 -1 NULL 1 2 NULL 0 -4 3 (011)
1 User1 2016-01-01 08:30:00 1 -1 NULL 1 2 NULL 0 -1 2 (010)
2 User1 2016-01-01 08:35:00 2 -1 NULL 1 2 NULL 0 -2 0 (000)
4 User2 2016-01-01 08:00:00 3 1 1 NULL 1 0 NULL 4 4 (100)
5 User2 2016-01-01 08:30:00 2 1 1 NULL 1 0 NULL 2 6 (110)
6 User2 2016-01-01 09:00:00 1 1 1 NULL 1 0 NULL 1 7 (111)
6 User2 2016-01-01 09:30:00 1 -1 NULL 1 2 NULL 0 -1 6 (110)
5 User2 2016-01-01 10:00:00 2 -1 NULL 1 2 NULL 0 -2 4 (100)
4 User2 2016-01-01 10:30:00 3 -1 NULL 1 2 NULL 0 -4 0 (000)
7 User2 2016-01-01 11:00:00 3 1 2 NULL 3 0 NULL 4 4 (100)
8 User2 2016-01-01 11:30:00 2 1 2 NULL 3 0 NULL 2 6 (110)
9 User2 2016-01-01 12:40:00 3 -1 NULL 3 6 NULL 0 -4 2 (010)
10 User2 2016-01-01 13:00:00 2 -1 NULL 3 6 NULL 0 -2 0 (000)
11 User3 2016-01-01 08:00:00 1 1 1 NULL 1 0 NULL 1 1 (001)
12 User3 2016-01-01 08:00:00 2 1 1 NULL 1 0 NULL 2 3 (011)
12 User3 2016-01-01 08:30:00 2 -1 NULL 1 2 NULL 0 -2 1 (001)
13 User3 2016-01-01 08:30:00 3 1 1 NULL 1 0 NULL 4 5 (101)
13 User3 2016-01-01 09:00:00 3 -1 NULL 1 2 NULL 0 -4 1 (001)
11 User3 2016-01-01 09:00:00 1 -1 NULL 1 2 NULL 0 -1 0 (000)
14 User3 2016-01-01 09:30:00 1 1 2 NULL 3 0 NULL 1 1 (001)
14 User3 2016-01-01 09:31:00 1 -1 NULL 2 4 NULL 0 -1 0 (000)
Besides the expressions that compute ptybitval and ptybitmap, which I’ll get to shortly, the rest of the code in this step implements the packing technique using the ROW_NUMBER function, which I described in Packing Intervals. If you’re not familiar with this packing technique, it would be best to read about it first before you continue.
This step packs intersecting intervals with the same user and priority, returning the start and end points of those packed intervals in separate rows. You can identify the output of this step for User2 graphically in the middle section in Figure 1.
As a reminder, the code in the CTE C1 returns start and end events of the input intervals in separate rows. The code marks start events with a the value +1 as the event type (column named type), meaning that this event increases the count of active intervals, and end events with -1, meaning that this event decreases the count. The code uses row numbers to compute a start event counter (column called s) and an end event counter (column called e). These counters count how many events of that type happened until that current event. NULLs are used as place holders in s for end events and in e for start events. The code in C1 unifies start and end events to generate one sequence of events.
The code in the CTE C2 uses row numbers to compute a combined event counter in chronological order (column called se). Think of se as an indication of how many events of both kinds (start and end) happened until the current event.
The outer query uses the CROSS APPLY operator to compute a number of result columns. The result column cs represents the count of active intervals right before the current start event, and the column ce represents the count of active intervals right after the current end event. The column ce is computed with the expression: s - (se - s) - 1. The logic behind this expression is that the combined event counter (se) minus the start event counter (s) tells you how many intervals ended before the current start event. If you subtract this value from how many intervals started until the current start event, you get how many intervals are active at this point, inclusive of the current start event. To know how many intervals were active just before the current start event you simply subtract 1. In a very similar way, to compute ce you use the expression: (se - e) - e.
The outer query filters only the events that mark either a start of a packed interval (where cs is 0) or an end of a packed interval (where ce is 0).
The APPLY operator computes another column called ptybitval that converts the priority to a bit value in an integer bitmap. SQL Server uses the two’s complement representation for integers, where each bit in a positive integer (other than the leftmost bit) represent the bit value: POWER(2,
The outer query in the SELECT list then computes a column called ptybitmap as the running total of the bit values of the events per user in chronological order. So at any given point, the bits that are turned on within the bitmap mark the active priorities. A start event turns the bit representing the event’s priority on and an end event turns it off. Since the solution packs the intervals with the same user and priority before applying this running total calculation, after packing, you can’t have two events of the same kind at the same time. So the running total calculation acts as an aggregate bitwise or operation. The rightmost set bit in the bitmap represents the highest priority (remember, lowest number) among the active ones. We’ll get to how to isolate this bit in the next step. You realize that this bitmap-based scheme means that your solution is limited to as many priorities as the number of available bits in the datatype that you’re using (minus 1 for the unusable leftmost bit). In my table I use the INT type and therefore I’m limited to 31 priorities. If you need more, using BIGINT you can support up to 63 priorities.
Step 2
The code implementing step 2 is shown in Listing 5 and the output of this step is shown in Table 3.
Listing 5: Step 2
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);
Table 3: Result of Step 2
id username ts pty type ptybitval ptybitmap rsb prvrsb startpty endpty
--- --------- -------------------- ---- ----- ---------- ---------- ---- ------- --------- -------
1 User1 2016-01-01 08:00:00 1 1 1 1 1 0 1 NULL
3 User1 2016-01-01 08:00:00 3 1 4 5 1 1 NULL NULL
2 User1 2016-01-01 08:05:00 2 1 2 7 1 1 NULL NULL
3 User1 2016-01-01 08:30:00 3 -1 -4 3 1 1 NULL NULL
1 User1 2016-01-01 08:30:00 1 -1 -1 2 2 1 2 1
2 User1 2016-01-01 08:35:00 2 -1 -2 0 0 2 NULL 2
4 User2 2016-01-01 08:00:00 3 1 4 4 4 0 3 NULL
5 User2 2016-01-01 08:30:00 2 1 2 6 2 4 2 3
6 User2 2016-01-01 09:00:00 1 1 1 7 1 2 1 2
6 User2 2016-01-01 09:30:00 1 -1 -1 6 2 1 2 1
5 User2 2016-01-01 10:00:00 2 -1 -2 4 4 2 3 2
4 User2 2016-01-01 10:30:00 3 -1 -4 0 0 4 NULL 3
7 User2 2016-01-01 11:00:00 3 1 4 4 4 0 3 NULL
8 User2 2016-01-01 11:30:00 2 1 2 6 2 4 2 3
9 User2 2016-01-01 12:40:00 3 -1 -4 2 2 2 NULL NULL
10 User2 2016-01-01 13:00:00 2 -1 -2 0 0 2 NULL 2
11 User3 2016-01-01 08:00:00 1 1 1 1 1 0 1 NULL
12 User3 2016-01-01 08:00:00 2 1 2 3 1 1 NULL NULL
12 User3 2016-01-01 08:30:00 2 -1 -2 1 1 1 NULL NULL
13 User3 2016-01-01 08:30:00 3 1 4 5 1 1 NULL NULL
13 User3 2016-01-01 09:00:00 3 -1 -4 1 1 1 NULL NULL
11 User3 2016-01-01 09:00:00 1 -1 -1 0 0 1 NULL 1
14 User3 2016-01-01 09:30:00 1 1 1 1 1 0 1 NULL
14 User3 2016-01-01 09:31:00 1 -1 -1 0 0 1 NULL 1
Note to reader: the next part requires a strong coffee and a geeky mood.
The code defines a CTE called C3 based on the outer query from step 1. The outer query in step 2 is issued against C3 and uses two CROSS APPLY operators to compute a number of result columns. The first CROSS APPLY operator computes the pair of columns rsb (for rightmost set bit) and prvrsb (for previous rightmost set bit). As mentioned, the rightmost set bit represents the highest active priority (lowest number). With the two’s complement representation of an integer N, the rightmost set bit is computed as N & -N, where & is T-SQL’s bitwise AND operator. The column rsb is then computed as: ptybitmap & -ptybitmap. To know what the bitmap was before the current event was applied you simply subtract ptybitval from ptybitmap. So prvrsb is computed as: (ptybitmap - ptybitval) & -(ptybitmap - ptybitval).
The second APPLY operator computes two additional result columns called startpty and endpty. Those are based on rsb and prvrsb and therefore require a separate CROSS APPLY operator to compute them.
The startpty column:
If the current start or end event starts a new result interval, the startpty column returns the priority of that interval, otherwise a NULL.
One condition that makes the current event a start of a result interval is when the event is a start event (type = 1), and the highest active priority is the current event’s priority (rsb = ptybitval). In such a case, startpty is set to pty (the current event’s priority). Examine Figure 1 and Table 3 and see if you can identify cases that fall under this category. One such example is the start event of the interval for User2 at 8:00 with priority 3. Observe that this start event is both a start of a packed interval and a start of an output interval.
Another condition that makes the current event a start of a result interval is when the event is an end event (type = -1), and the highest remaining active priority is lower than the priority of the interval that has just ended (number is greater: rsb > -ptybitval). In such a case, startpty is set to the priority that rsb represents (computed as: LOG(rsb, 2) + 1). For example, at 9:30 the packed interval for User2 with priority 1 ends. This marks the start of an output interval with priority 2.
The endpty column:
If the current start or end event ends a result interval, the endpty column returns the priority of that interval, otherwise a NULL.
One condition that makes the current event an end of a result interval is when the event is an end event (type = -1), and either there are no remaining active intervals (rsb = 0) or the highest remaining active priority is lower than the priority of the interval that has just ended (number is greater: rsb > -ptybitval). In such a case, endpty is set to pty (the current event’s priority). Examples for such events are the end event for User2 at 10:30 of the interval with priority 3 and the end event for User2 at 9:30 of the interval with priority 1.
Another condition that makes the current event an end of a result interval is when the event is a start event (type = 1), and the highest active priority before the current event was applied is lower than the current event’s priority (number is greater: prvrsb > ptybitval). For example, at 9;00 the packed interval for User2 with priority 1 starts. This marks the end of an output interval with priority 2.
If you’ve made it this far and understood everything in this section, you can give yourself a pat on the shoulder, and perhaps switch from coffee to Lagavulin now.
Step 3
Step 3 is pretty simple. Looking at the result of step 2 in Table 3 you need to do things:
1. Unpivot the startpty and endpty values into separate rows.
2. Remove all rows where startpty and endpty are NULL.
You can achieve both things by applying the UNPIVOT operator to the result of the previous step, like so:
UNPIVOT (newpty FOR newtype IN (startpty, endpty)) AS U
You then need to create a result interval identifier (call it grp) for each consecutive pair of events with the same user and priority. For this, you use a row number (call it rn) in the following formula: (rn - 1) / 2 + 1. Here’s the T-SQL expression:
(ROW_NUMBER() OVER(PARTITION BY username, newpty ORDER BY ts) - 1) / 2 + 1 AS grp
Listing 6 has the complete code implementing step 3 and Table 4 has the output of this step.
Listing 6: Step 3
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;
Table 4: Result of Step 3
Table 4: Result of Step 3
id username ts newpty newtype grp
--- --------- -------------------- ------- --------- ----
1 User1 2016-01-01 08:00:00 1 startpty 1
1 User1 2016-01-01 08:30:00 1 endpty 1
1 User1 2016-01-01 08:30:00 2 startpty 1
2 User1 2016-01-01 08:35:00 2 endpty 1
6 User2 2016-01-01 09:00:00 1 startpty 1
6 User2 2016-01-01 09:30:00 1 endpty 1
5 User2 2016-01-01 08:30:00 2 startpty 1
6 User2 2016-01-01 09:00:00 2 endpty 1
6 User2 2016-01-01 09:30:00 2 startpty 2
5 User2 2016-01-01 10:00:00 2 endpty 2
8 User2 2016-01-01 11:30:00 2 startpty 3
10 User2 2016-01-01 13:00:00 2 endpty 3
4 User2 2016-01-01 08:00:00 3 startpty 1
5 User2 2016-01-01 08:30:00 3 endpty 1
5 User2 2016-01-01 10:00:00 3 startpty 2
4 User2 2016-01-01 10:30:00 3 endpty 2
7 User2 2016-01-01 11:00:00 3 startpty 3
8 User2 2016-01-01 11:30:00 3 endpty 3
11 User3 2016-01-01 08:00:00 1 startpty 1
11 User3 2016-01-01 09:00:00 1 endpty 1
14 User3 2016-01-01 09:30:00 1 startpty 2
14 User3 2016-01-01 09:31:00 1 endpty 2
Step 4 and Complete Solution
The fourth and last step defines a CTE called C4 (aptly named) based on the outer query from the previous step (aka, the explosive query). The final outer query groups the rows from C4 by username, newpty and grp, and for each group returns the minimum and maximum event times as the start and end times of the result intervals. Here’s the outer query:
SELECT username, newpty AS pty, MIN(ts) AS starttime, MAX(ts) AS endtime
FROM C4
GROUP BY username, newpty, grp;
Listing 7 has the complete solution code. I presented the output earlier in Table 1.
Listing 7: Complete solution
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;
When running this solution against the large set of sample data with the 5,000,000 rows, it took 45 seconds to complete on my 5-year old laptop. That’s not too bad, but there’s still room for improvement.
Optimizing the solution with APPLY
Even though the code in Listing 1 creates supporting indexes for our solution, since there are a few window functions with different partitioning and ordering specifications, you can’t escape a couple of explicit sort operators in the plan. A sort operator scales in an extra linear manner (N Log N). Therefore, when there’s a partitioning element involved in the window functions, you can often achieve better performance by using a technique initially introduced by Adam Machanic. You use a CROSS APPLY operator against the table holding the partitions (Users in our case) and apply a query (or an inline TVF encapsulating the query) per partition. This way you split one large operation to multiple smaller operations and in the aforementioned scenario get better performance. The code in Listing 8 encapsulates our solution for a single user in an inline TVF called PackedIntervals.
Listing 8: Encapsulate logic for a single user in an inline TVF
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
You then use the following query to apply the function to each user, like so:
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);
Note that on my laptop without the (undocumented and unsupported) trace flag 8649 SQL Server generates a serial plan that takes only 15 seconds to complete. That’s just a third of the run time of the original solution and already very fast. The APPLY method works even better when parallelized, so, for illustration purposes I forced a parallel plan with the trace flag. With parallelism, this query completed in 8 seconds on my laptop, producing the plan shown in Figure 2.
Conclusion
In this article I covered a variation of the classic interval packing problem where intervals have priorities and in overlapping cases you’re supposed to return the segment with the highest priority. I’d like to thank Ralf for sending this challenge. The solution I used relied mainly on window functions, including row numbers and running totals calculations. The handling of the priorities was achieved by using a bitmap representation of the priorities. Finally, using Adam Machanic’s CROSS APPLY method I further improved the solution by splitting one large task that scales extra linearly to multiple smaller tasks.
