Calculating Concurrent Sessions

Usually, set-based solutions perform better than iterative solutions that use cursors and loops, but there are exceptions. One problem for which I haven't found a set-based solution that performs better than the iterative one is the subject of this month's exercise. Performance aside, the problem is quite a brainteaser, and I urge you to try to find set-based solutions for it to test your T-SQL skills. I'd like to thank Assaf Fraenkel, a senior consultant at Microsoft Consulting Services, who got me acquainted with the puzzle and suggested one approach to solving it. Thanks also to Dejan Sarka and Dieter Nöth, whose ideas are embedded in the solutions I present.

The Max Concurrent Sessions Problem

The problem involves calculating the maximum number of concurrent sessions for each application that an organization uses. For this problem, a table called Sessions stores information about application use. Each row contains one session's worth of data, including the application, user, host, start time, and end time. Run the script that Listing 1 shows to create the Sessions table and populate it with sample data.

To distinguish between the rows in the Sessions table, I used the key_col column, a surrogate key that has the IDENTITY property. Theoretically, one user can open more than one session at the same time against the same application from the same host. Your task is to calculate the maximum number of concurrent sessions per application, regardless of user, host, or period. In other words, calculate the maximum number of sessions that were active at any time for each application.

Table 1 shows the desired results. The IT department uses this information to calculate payments to the applications' suppliers, which charge by the maximum number of concurrent sessions. You can assume that the table doesn't contain more than 1 month's worth of sessions. You now have all the information required to solve the problem.

Solution 1: Custom Time Slots

One approach to solving the problem is to generate all possible time slots between the minimum and maximum existing start times in the table, then count the number of sessions in which each time slot occurs for each application. A time slot is the start time of a time slice. Because the table stores session start and end times as a smalldatetime data type, they're accurate to the minute. For example, after you populate the Sessions table, the minimum and maximum session start times should be 2003-02-12 08:30 and 2003-02-12 15:30, respectively. The code you write should split the period between the minimum and maximum start times into 1-minute slots: 2003-02-12 08:30, 2003-02-12 08:31, 2003-02-12 08:32, ..., 2003-02-12 15:29, 2003-02-12 15:30. Next, count the number of sessions that took place during each time slot for each application. To verify that a certain session took place during a given time slot, use the following expression:

timeslot >= session_starttime ANDtimeslot < session_endtime

Finally, of all the counts you got for each application and time slot, return the maximum count for each application.

To generate all possible time slots in the table, first create an auxiliary table with as many numbers as the maximum number of minute slots you anticipate. Because the table contains no more than a month's worth of data, you have no more than 44,640 (60*24*31) minute slices. If you want to test the solution against, for example, 3 years' worth of data, make sure you populate the Nums table with 3 years' worth of numbers (60*24*365*3= 1,576,800). Running the script that Listing 2 shows creates the Nums auxiliary table with a month's worth of numbers.

The code that Listing 3 shows creates the VTimeSlots view, which calculates the actual minute time slots in the period between the minimum and maximum start times in the Sessions table. The query that Listing 4 shows calculates the desired result. The innermost subquery matches each time slot in the VTimeSlots view with all sessions that took place at that time. The query groups the result—derived table TSAPP—by the timeslot and app columns to count the number of concurrent sessions per application. The query then groups the result—derived table C—by app to calculate the maximum number of concurrent sessions per application.

This solution implements a fairly simple concept; however, it isn't scalable. The problem is in the potentially huge number of time slots generated; a 31-day month has 44,640 minute time slots, and the query looks for matching sessions for each of those. Think of the implications of handling longer periods or using the datetime data type, which has an accuracy of 3 1/3 milliseconds.

Solution 2: Existing Time Slices

Solution 2 uses an approach similar in concept to the one in the first solution; it also matches time slots to sessions. However, instead of generating all possible time slices and using their start times as time slots, this approach uses the existing start times in the Sessions table, so you don't need an auxiliary table or a view. Listing 5's query gives the desired results for this solution.

The S1 instance of Sessions represents the time slots. The code matches each time slot with all sessions in the S2 instance of Sessions in which the time slot falls. A derived table called C is generated by a query that groups the result of the join by the app and key_col columns to count the number of occurrences per time slot. I used key_col, not starttime, in the GROUP BY clause because different sessions of the same application can start at the same time. In such a case, the count of concurrent sessions would be wrong. The outer query groups the time slots in C by app value and calculates the maximum number of concurrent sessions per application.

This approach is an optimization of the previous approach. Yet it still has performance problems no matter what combination of indexes you try. A large number of time slots might exist in the table, and the query looks for a matching session for each. If you prefer using subqueries instead of joins, you can use the query that Listing 6 shows, which implements the same logic as the query in Listing 5 but with a subquery. Often, the optimizer generates the same plan for two queries that perform the same task, one using a join and the other using a subquery, in which case the approach you use is a matter of personal preference. In this case, the subquery approach performs better.

Solution 3: Summarizing Event Types

The third approach is completely different from the other two. It treats session starts and ends as different events, each incrementing or decrementing a count of sessions, respectively. The following VStartEnd view definition splits each session into start and end events, adding 1 to a start event and -1 to an end event:

CREATE VIEW VStartEndASSELECT app, starttime AS ts, 1 AS setype FROM SessionsUNION ALLSELECT app, endtime, -1 AS setype FROM Sessions

The query that Listing 7 shows produces the desired results for this solution. It matches each session in the Sessions table with all events from VStartEnd for the same application that have an event time less than or equal to the session's start time. The code then groups the result of the join by session (key_col) and app and calculates the number of concurrent sessions by summarizing the event type (setype). Finally, the code groups the result—derived table C—by app and calculates the maximum number of concurrent sessions per application.

This solution is probably the most elegant of those I've presented so far, but it's a performance nightmare. For every session, the query needs to scan all events that took place before or at the session start time. This solution isn't scalable; the performance problem gets worse exponentially as the table grows.

Solution 4: Cumulative Running Count

The fourth solution, which Listing 8 shows, uses an iterative approach involving a cursor and a loop. The code declares a cursor on a query that returns event types similar to the ones I used in the previous solution, sorted by application and event timestamp. The code forms a loop that iterates through all rows returned by the query I declared in the cursor. In each iteration, the code increments a counter called @concurrent when the current record contains a start event and decrements it when the current record contains an end event. I used 1 and -1 as event types, but you can choose other symbols—such as S and E—to help you distinguish between start and end events. You just have to examine the event type to determine whether to increment or decrement the counter instead of simply adding the event type to it.

A variable called @mx holds the maximum number of concurrent sessions the code has counted in the loop for the application so far. If @concurrent is greater than @mx, @mx receives the current value in @concurrent. When the application in the current record is different than the previous one, the code writes a row to a table variable called @AppsMx, which contains the previous application name (@prevapp) and maximum concurrent sessions (@mx).

About Performance

To test the performance of the different solutions, I populated the Sessions table with 16,000 rows by running the following code:

INSERT INTO Sessions(app, usr,   host, starttime, endtime)  SELECT app, usr, host,     starttime+n, endtime+n  FROM Sessions JOIN Nums    ON n <= 999

Note that to test the first solution, you also need to populate the Nums auxiliary table with enough rows for 1000 days (60*24*1000).

I tested various index combinations, but all the set-based solutions ran for such a long time, I eventually stopped them. The iterative solution ran for only 2 seconds on my laptop. The iterative solution is the only scalable solution that I came up with—the performance degradation of the cursor-based solution is linear as the table grows larger; with the set-based solutions, it's exponential. If you find a set-based solution that beats the iterative one, I'd love to hear about it.