Calculate number of concurrent events in SQL

Here's what the possible overlaps look like, where 'A' is the "reference" interval. Note that the query below (far, far below) doesn't give the same result as any of the answers yet posted.

-- A            |------|-- B |-|-- C        |---|-- D          |---|-- E             |---|-- F               |---|-- G                 |---|-- H                   |---|-- I                       |---|

"B" doesn't overlap "A" at all. "C" abuts it. {"D", "E", "F", "G"} overlaps it. "H" abuts it. "I" doesn't overlap it at all.

create table calls_nov (  sid varchar(5) primary key,  starttime timestamp not null,  endtime timestamp not null);  insert into calls_nov values('A', '2012-01-04 08:00:00', '2012-01-04 08:00:10'),('B', '2012-01-04 07:50:00', '2012-01-04 07:50:03'),('C', '2012-01-04 07:59:57', '2012-01-04 08:00:00'),('D', '2012-01-04 07:59:57', '2012-01-04 08:00:03'),('E', '2012-01-04 08:00:01', '2012-01-04 08:00:04'),('F', '2012-01-04 08:00:07', '2012-01-04 08:00:10'),('G', '2012-01-04 08:00:07', '2012-01-04 08:00:13'),('H', '2012-01-04 08:00:10', '2012-01-04 08:00:13'),('I', '2012-01-04 08:00:15', '2012-01-04 08:00:18');

You can see all the overlapping intervals like this. (I just used to_char() to make it easy to see all the data. You can omit it in production.)

select t1.sid, to_char(t1.starttime, 'HH12:MI:SS'),                to_char(t1.endtime,   'HH12:MI:SS'),        t2.sid, to_char(t2.starttime, 'HH12:MI:SS'),                to_char(t2.endtime,   'HH12:MI:SS')from calls_nov t1inner join calls_nov t2 on (t2.starttime, t2.endtime)                   overlaps (t1.starttime, t1.endtime) order by t1.sid, t2.sid;A   08:00:00   08:00:10   A   08:00:00   08:00:10A   08:00:00   08:00:10   D   07:59:57   08:00:03A   08:00:00   08:00:10   E   08:00:01   08:00:04A   08:00:00   08:00:10   F   08:00:07   08:00:10A   08:00:00   08:00:10   G   08:00:07   08:00:13B   07:50:00   07:50:03   B   07:50:00   07:50:03C   07:59:57   08:00:00   C   07:59:57   08:00:00C   07:59:57   08:00:00   D   07:59:57   08:00:03D   07:59:57   08:00:03   A   08:00:00   08:00:10D   07:59:57   08:00:03   C   07:59:57   08:00:00D   07:59:57   08:00:03   D   07:59:57   08:00:03D   07:59:57   08:00:03   E   08:00:01   08:00:04E   08:00:01   08:00:04   A   08:00:00   08:00:10E   08:00:01   08:00:04   D   07:59:57   08:00:03E   08:00:01   08:00:04   E   08:00:01   08:00:04F   08:00:07   08:00:10   A   08:00:00   08:00:10F   08:00:07   08:00:10   F   08:00:07   08:00:10F   08:00:07   08:00:10   G   08:00:07   08:00:13G   08:00:07   08:00:13   A   08:00:00   08:00:10G   08:00:07   08:00:13   F   08:00:07   08:00:10G   08:00:07   08:00:13   G   08:00:07   08:00:13G   08:00:07   08:00:13   H   08:00:10   08:00:13H   08:00:10   08:00:13   G   08:00:07   08:00:13H   08:00:10   08:00:13   H   08:00:10   08:00:13I   08:00:15   08:00:18   I   08:00:15   08:00:18

You can see from this table that "A" should count 5, including itself. "B" should count 1; it overlaps itself, but no other intervals overlap it. That seems the right thing to do.

Counting is straightforward, but runs like a ruptured turtle. That's because evaluating an overlap takes a lot of work.

select t1.sid, count(t2.sid) as num_concurrentfrom calls_nov t1inner join calls_nov t2 on (t2.starttime, t2.endtime)                   overlaps (t1.starttime, t1.endtime) group by t1.sidorder by num_concurrent desc;A   5D   4G   4E   3F   3H   2C   2I   1B   1

To get better performance, you can use the "table" above in a common table expression, and count based on that.

with interval_table as (select t1.sid as sid_1, t1.starttime, t1.endtime,       t2.sid as sid_2, t2.starttime, t2.endtimefrom calls_nov t1inner join calls_nov t2 on (t2.starttime, t2.endtime)                   overlaps (t1.starttime, t1.endtime) order by t1.sid, t2.sid) select sid_1, count(sid_2) as num_concurrentfrom interval_tablegroup by sid_1order by num_concurrent desc;

1.) Your query did not catch all overlaps - this was fixed by the other answers, already.

2.) The data type of your columns starttime and endtime is timestamp. So your WHERE clause is slightly wrong, too:

BETWEEN '2011-11-02' AND '2011-11-03'

This would include '2011-11-03 00:00'. The upper border has to be excluded.

3.) Removed the mixed case syntax without double-quotes. Unquoted identifiers are cast to lower case automatically. To put it simple: Best don't use mixed case identifiers at all in PostgreSQL.

4.) Transformed the query to use explicit JOIN which is always preferable. Actually, I made it a LEFT [OUTER] JOIN, because I want to count calls that overlap with no other calls, too.

5.) Simplified the syntax a bit to arrive at this base query:

SELECT t1.sid, count(*) AS ctFROM   calls_nov t1LEFT   JOIN calls_nov t2 ON t1.starttime <= t2.endtime                        AND t1.endtime >= t2.starttimeWHERE  t1.starttime >= '2011-11-02 0:0'::timestampAND    t1.starttime <  '2011-11-03 0:0'::timestampGROUP  BY 1ORDER  BY 2 DESC;

This query is extremely slow for a big table, because every row starting on '2011-11-02' has to be compared to every row in the whole table, which leads to (almost) O(n²) cost.

Faster

We can drastically cut down the cost by pre-selecting possible candidates. Only select columns and rows you need. I do this with two CTE.

1. Select calls starting on the day in question. -> CTE x
2. Calculate the latest end of those calls. (subquery in CTE y)
3. Select only calls that overlap with the total range of CTE x. -> CTE y
4. The final query is much faster than querying the huge underlying table.

WITH x AS (    SELECT sid, starttime, endtime    FROM   calls_nov    WHERE  starttime >= '2011-11-02 0:0'    AND    starttime <  '2011-11-03 0:0'    ), y AS (    SELECT starttime, endtime    FROM   calls_nov    WHERE  endtime >= '2011-11-02 0:0'    AND    starttime <= (SELECT max(endtime) As max_endtime FROM x)    )SELECT x.sid, count(*) AS count_overlapsFROM   xLEFT   JOIN y ON x.starttime <= y.endtime             AND x.endtime >= y.starttimeGROUP  BY 1ORDER  BY 2 DESC;

Faster yet

I have a real life table of 350.000 rows with overlapping start / end timestamps similar to yours. I used that for a quick benchmark. PostgreSQL 8.4, scarce resources because it is a test DB. Indexes on start and end. (Index on ID column is irrelevant here.) Tested with EXPLAIN ANALYZE, best of 5.

Total runtime: 476994.774 ms

CTE variant:
Total runtime: 4199.788 ms -- that's > factor 100.

After adding a multicolumn index of the form:

CREATE INDEX start_end_index on calls_nov (starttime, endtime);

Total runtime: 4159.367 ms

Ultimate Speed

If that is not enough, there is a way to speed it up yet another order of magnitude. Instead of the CTEs above, materialize the temp tables and - this is the crucial point - create an index on the second one. Could look like this:

Execute as one transaction:

CREATE TEMP TABLE x ON COMMIT DROP AS       SELECT sid, starttime, endtime    FROM   calls_nov    WHERE  starttime >= '2011-11-02 0:0'    AND    starttime <  '2011-11-03 0:0';CREATE TEMP TABLE y ON COMMIT DROP AS    SELECT starttime, endtime    FROM   calls_nov    WHERE  endtime >= '2011-11-02 0:0'    AND    starttime <= (SELECT max(endtime) FROM x);CREATE INDEX y_idx ON y (starttime, endtime); -- this is where the magic happensSELECT x.sid, count(*) AS ctFROM   xLEFT   JOIN y ON x.starttime <= y.endtime             AND x.endtime >= y.starttimeGROUP  BY 1ORDER  BY 2 DESC;

Read about temporary tables in the manual.

Ultimate solution

• Create a plpgsql function that encapsulates the magic.

• Diagnose the typical size of your temp tables. Create them standalone and measure:

    SELECT pg_size_pretty(pg_total_relation_size('tmp_tbl'));

• If they are bigger than your setting for temp_buffers then temporarily set them high enough in your function to hold both your temporary tables in RAM. It is a major speedup if you don't have to swap to disc. (Must be first use of temp tables in session to have effect.)

CREATE OR REPLACE FUNCTION f_call_overlaps(date)  RETURNS TABLE (sid varchar, ct integer) AS$BODY$DECLARE    _from timestamp := $1::timestamp;    _to   timestamp := ($1 +1)::timestamp;BEGINSET temp_buffers = 64MB'; -- example value; more RAM for temp tables;CREATE TEMP TABLE x ON COMMIT DROP AS       SELECT c.sid, starttime, endtime  -- avoid naming conflict with OUT param    FROM   calls_nov c    WHERE  starttime >= _from    AND    starttime <  _to;CREATE TEMP TABLE y ON COMMIT DROP AS    SELECT starttime, endtime    FROM   calls_nov    WHERE  endtime >= _from    AND    starttime <= (SELECT max(endtime) FROM x);CREATE INDEX y_idx ON y (starttime, endtime);RETURN QUERYSELECT x.sid, count(*)::int -- AS ctFROM   xLEFT   JOIN y ON x.starttime <= y.endtime AND x.endtime >= y.starttimeGROUP  BY 1ORDER  BY 2 DESC;END;$BODY$   LANGUAGE plpgsql;

Call:

SELECT * FROM f_call_overlaps('2011-11-02') -- just name your date

Total runtime: 138.169 ms -- that's factor 3000

What else can you do to speed it up?

General performance optimization.

CLUSTER calls_nov USING starttime_index; -- this also vacuums the table fullyANALYZE calls_nov;

I'm assuming that you want to know the amount of active calls at any given time. Other answers give you how many other calls were active while the current call was active. For very long calls, this can give you very high numbers. It was indicated to me that the amount of active calls is what you wanted from one of your comments to the other answers (additionally, I also work in telecom). Unfortunately, I don't have enough reputation to comment that answer yet, as I created my account to answer this question. To get the number of active calls, you could use a variable which increases by one when a call is started and decreases by one when it's ended. I have tested this on a MySQL database with 50+ million calls. Sorry about any syntax differences between MySQL and pgsql.

I added temporary tables for speed, but with only 2m rows and indexes, they may not be needed. MySQL cannot reference the same temporary table twice, so I had to create two.

CREATE TEMPORARY TABLE aSELECT sid, StartTime, EndTime FROM calls_novWHERE StartTime between '2011-11-02' and '2011-11-03';CREATE TEMPORARY TABLE bSELECT *FROM a;SET @i := 0;SELECT *, @i := @i + c.delta AS concurrentFROM (  SELECT StartTime AS time, 1 AS delta  FROM a  UNION ALL  SELECT EndTime AS time, -1 AS delta  FROM b  ORDER BY time) AS cORDER BY concurrent DESC;

The inner SELECT returns two columns. The time column includes each StartTime and each EndTime from the original table (twice the amount of rows), and the delta column is +1 or -1 depending on which column was put in 'time'. This set is ordered by time, which we can then iterate through in the outer SELECT.

Instead of "ORDER BY concurrent DESC" as you had in your query, I would use an additional outer SELECT where I could get MAX, MIN etc. values and I could also GROUP BY date, hour etc. This part of the query (ORDER BY concurrent DESC), I actually did not test. I used my own suggestion with an additional outer query, as ORDER BY does not perform as expected in MySQL when ordering by a variable that was set in the same SELECT. It orders by the previous value of the variable instead. If you absolutely need to order by concurrent calls (and pgsql has the same problem), I believe that you could get around this by again using an additional outer SELECT and ordering there.

The query I ran was very fast! It scans through each temporary table once, and then the combination of the of the two once (with less data per row), and for my own version with an additional outer query it scans through the combination once again and then groups it. Each table is only scanned once! This will all be done in RAM if your configuration and hardware allows it. Other answers (or questions) will help you if it does not.