Querying for a 'run' of consecutive column

Question

I have a table:

create table table1 (event_id integer, event_time timestamp without time zone);
insert into table1 (event_id, event_time) values
(1, '2011-01-01 00:00:00'),
(2, '2011-01-01 00:00:15'),
(3, '2011-01-01 00:00:29'),
(4, '2011-01-01 00:00:58'),
(5, '2011-01-02 06:03:00'),
(6, '2011-01-02 06:03:09'),
(7, '2011-01-05 11:01:31'),
(8, '2011-01-05 11:02:15'),
(9, '2011-01-06 09:34:19'),
(10, '2011-01-06 09:34:41'),
(11, '2011-01-06 09:35:06');

I would like to construct a statement that given an event could return the length of the 'run' of events starting with that event. A run is defined by:

1. Two events are in a run together if they are within 30 seconds of one another.
2. If A and B are in a run together, and B and C are in a run together then A is in a run with C.

However my query does not need to go backwards in time, so if I select on event 2, then only events 2, 3, and 4 should be counted as part of the run of events starting with 2, and 3 should be returned as the length of the run.

Any ideas? I'm stumped.

Answer 1

Could look like this:

WITH x AS (
    SELECT event_time
          ,row_number() OVER w AS rn
          ,lead(event_time) OVER w AS next_time
    FROM   table1
    WHERE  event_id >= <start_id>
    WINDOW w AS (ORDER BY event_time, event_id)
    )
SELECT COALESCE(
      (SELECT x.rn
       FROM   x
       WHERE  (x.event_time + interval '30s') < x.next_time
       ORDER  BY x.rn
       LIMIT  1)
     ,(SELECT count(*) FROM x)
      ) AS run_length

This version does not rely on a gap-less sequence of IDs, but on event_time only.
Identical event_time's are additionally sorted by event_id to be unambiguous.

Read about the window functions row_number() and lead() and CTE (With clause) in the manual.

Edit

If we cannot assume that a bigger event_id has a later (or equal) event_time, substitute this for the first WHERE clause:

WHERE event_time >= (SELECT event_time FROM table1 WHERE event_id = <start_id>)

Rows with the same event_time as the starting row but a a smaller event_id will still be ignored.

In the special case of one run till the end no end is found and no row returned. COALESCE returns the count of all rows instead.

Answer 2

Here is the RECURSIVE CTE-solution. (islands-and-gaps problems naturally lend themselves to recursive CTE)

WITH RECURSIVE runrun AS (
    SELECT event_id, event_time
    , event_time - ('30 sec'::interval) AS low_time
    , event_time + ('30 sec'::interval) AS high_time
    FROM table1
    UNION
    SELECT t1.event_id, t1.event_time
    , LEAST ( rr.low_time, t1.event_time - ('30 sec'::interval) ) AS low_time
    , GREATEST ( rr.high_time, t1.event_time + ('30 sec'::interval) ) AS high_time
    FROM table1 t1
    JOIN runrun rr ON t1.event_time >= rr.low_time
                  AND t1.event_time < rr.high_time
    )
SELECT DISTINCT ON (event_id) *
FROM runrun rr
WHERE rr.event_time >= '2011-01-01 00:00:15'
AND rr.low_time <= '2011-01-01 00:00:15'
AND rr.high_time > '2011-01-01 00:00:15'
    ;

Result:

 event_id |     event_time      |      low_time       |      high_time      
----------+---------------------+---------------------+---------------------
        2 | 2011-01-01 00:00:15 | 2010-12-31 23:59:45 | 2011-01-01 00:00:45
        3 | 2011-01-01 00:00:29 | 2010-12-31 23:59:45 | 2011-01-01 00:01:28
        4 | 2011-01-01 00:00:58 | 2010-12-31 23:59:30 | 2011-01-01 00:01:28
(3 rows)

Answer 3

You can join a table onto itself on a date difference statement. Actually, this is postgres, a simple minus works.

This subquery will find all records that is a 'start event'. That is to say, all event records that does not have another event record occurring within 30 seconds before it:

(Select a.event_id, a.event_time from
(Select event_id, event_time from table1) a
 left join 
 (select event_id, event_time from table1) b
 on a.event_time - b.event_time < '00:00:30' and a.event_time - b.event_time > '00:00:00'
 where b.event_time is null) startevent

With a few changes...same logic, except picking up an 'end' event:

(Select a.event_id, a.event_time from
(Select event_id, event_time from table1) a
 left join 
 (select event_id, event_time from table1) b
 on b.event_time - a.event_time < '00:00:30' and b.event_time - a.event_time > '00:00:00'
 where b.event_time is null) end_event

Now we can join these together to associate which start event goes to which end event:

(still writing...there's a couple ways at going on this. I'm assuming only the example has linear ID numbers, so you'll want to join the start event time to the end event time having the smallest positive difference on the event times).

Here's my end result...kinda nested a lot of subselects

 select a.start_id, case when a.event_id is null then t1.event_id::varchar else 'single  event' end as end_id
 from
 (select start_event.event_id as start_id, start_event.event_time as start_time,      last_event.event_id, min(end_event.event_time - start_event.event_time) as min_interval   
 from
    (Select a.event_id, a.event_time from
    (Select event_id, event_time from table1) a
     left join 
    (select event_id, event_time from table1) b
   on a.event_time - b.event_time < '00:00:30' and a.event_time - b.event_time > '00:00:00'
 where b.event_time is null) start_event

inner join

   (Select a.event_id, a.event_time from
(Select event_id, event_time from table1) a
 left join 
 (select event_id, event_time from table1) b
 on b.event_time - a.event_time < '00:00:30' and b.event_time - a.event_time > '00:00:00'
 where b.event_time is null) end_event     
on end_event.event_time > start_event.event_time

--check for only event
 left join
 (Select a.event_id, a.event_time from
 (Select event_id, event_time from table1) a
  left join 
  (select event_id, event_time from table1) b
  on b.event_time - a.event_time < '00:00:30' and b.event_time - a.event_time > '00:00:00'
  where b.event_time is null) last_event
    on start_event.event_id = last_event.event_id
group by 1,2,3) a
    left join table1 t1 on t1.event_time = a.start_time + a.min_interval

Results as start_id, end_Id:

1;"4"
5;"6"
7;"single event"
8;"single event"
9;"11"

I had to use a third left join to pick out single events as a method of detecting events that were both start events and end events. End result is in ID's and can be linked back to your original table if you want different information than just the ID. Unsure how this solution will scale, if you've got millions of events...could be an issue.