Calculate number of concurrent events in SQL
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 ct
FROM calls_nov t1
LEFT JOIN calls_nov t2 ON t1.starttime <= t2.endtime
AND t1.endtime >= t2.starttime
WHERE t1.starttime >= '2011-11-02 0:0'::timestamp
AND t1.starttime < '2011-11-03 0:0'::timestamp
GROUP BY 1
ORDER 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.
- Select calls starting on the day in question. -> CTE
x - Calculate the latest end of those calls. (subquery in CTE
y) - Select only calls that overlap with the total range of CTE
x. -> CTEy - 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_overlaps
FROM x
LEFT JOIN y ON x.starttime <= y.endtime
AND x.endtime >= y.starttime
GROUP BY 1
ORDER 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 happens
SELECT x.sid, count(*) AS ct
FROM x
LEFT JOIN y ON x.starttime <= y.endtime
AND x.endtime >= y.starttime
GROUP BY 1
ORDER 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;
BEGIN
SET 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 QUERY
SELECT x.sid, count(*)::int -- AS ct
FROM x
LEFT JOIN y ON x.starttime <= y.endtime AND x.endtime >= y.starttime
GROUP BY 1
ORDER 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 fully
ANALYZE calls_nov;
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 t1
inner 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:10
A 08:00:00 08:00:10 D 07:59:57 08:00:03
A 08:00:00 08:00:10 E 08:00:01 08:00:04
A 08:00:00 08:00:10 F 08:00:07 08:00:10
A 08:00:00 08:00:10 G 08:00:07 08:00:13
B 07:50:00 07:50:03 B 07:50:00 07:50:03
C 07:59:57 08:00:00 C 07:59:57 08:00:00
C 07:59:57 08:00:00 D 07:59:57 08:00:03
D 07:59:57 08:00:03 A 08:00:00 08:00:10
D 07:59:57 08:00:03 C 07:59:57 08:00:00
D 07:59:57 08:00:03 D 07:59:57 08:00:03
D 07:59:57 08:00:03 E 08:00:01 08:00:04
E 08:00:01 08:00:04 A 08:00:00 08:00:10
E 08:00:01 08:00:04 D 07:59:57 08:00:03
E 08:00:01 08:00:04 E 08:00:01 08:00:04
F 08:00:07 08:00:10 A 08:00:00 08:00:10
F 08:00:07 08:00:10 F 08:00:07 08:00:10
F 08:00:07 08:00:10 G 08:00:07 08:00:13
G 08:00:07 08:00:13 A 08:00:00 08:00:10
G 08:00:07 08:00:13 F 08:00:07 08:00:10
G 08:00:07 08:00:13 G 08:00:07 08:00:13
G 08:00:07 08:00:13 H 08:00:10 08:00:13
H 08:00:10 08:00:13 G 08:00:07 08:00:13
H 08:00:10 08:00:13 H 08:00:10 08:00:13
I 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_concurrent
from calls_nov t1
inner join calls_nov t2 on (t2.starttime, t2.endtime)
overlaps (t1.starttime, t1.endtime)
group by t1.sid
order by num_concurrent desc;
A 5
D 4
G 4
E 3
F 3
H 2
C 2
I 1
B 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.endtime
from calls_nov t1
inner 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_concurrent
from interval_table
group by sid_1
order by num_concurrent desc;
Try this in lieu of your between and a cross join:
select
t1.sid,
count(1) as CountSimultaneous
from
calls_nov t1
inner join nov t2 on
t1.starttime <= t2.endtime
and t1.endtime >= t2.starttime
where
t1.starttime between '2011-11-02' and '2011-11-03'
group by
t1.sid
order by CountSimultaneous desc
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 a
SELECT sid, StartTime, EndTime
FROM calls_nov
WHERE StartTime between '2011-11-02' and '2011-11-03';
CREATE TEMPORARY TABLE b
SELECT *
FROM a;
SET @i := 0;
SELECT *, @i := @i + c.delta AS concurrent
FROM (
SELECT StartTime AS time, 1 AS delta
FROM a
UNION ALL
SELECT EndTime AS time, -1 AS delta
FROM b
ORDER BY time
) AS c
ORDER 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.