5

I have a table in PostgreSQL which describes some events that have a start date and an end date:

CREATE TABLE my_table
(
  event_id serial NOT NULL,
  start_date timestamp without time zone NOT NULL,
  end_date timestamp without time zone NOT NULL
)

A single event may overlap the previous and the next one. In the following table the first 3 of 4 events form a contiguous time interval:

1   '2015-04-02 22:09:03'   '2015-04-02 22:19:05'
2   '2015-04-02 22:17:38'   '2015-04-02 22:27:38'
3   '2015-04-02 22:25:21'   '2015-04-02 22:36:23'
4   '2015-04-02 22:45:23'   '2015-04-02 22:55:23'

Is it possible to write a query that checks if a contiguous date interval between two given dates exists?

I would like to have something like:

select ...
from my_table
where start_date > '2015-04-02' and end_date < '2015-04-06'
4

First, we combine intervals that overlap to find all the contiguous "islands" of the intervals:

with c as
  ( select *, max(end_date) over (order by start_date
                                  rows between unbounded preceding
                                           and 1 preceding)
                as previous_max
    from my_table
  )
select start_date, 
       coalesce(lead(previous_max) over (order by start_date),
                (select max(end_date) from my_table)
               ) as end_date
from c 
where previous_max < start_date 
   or previous_max is null ;

After that, it's easy to check if a given interval in completely surrounded by one of the found contiguous islands.

   with c as
  ( select *, max(end_date) over (order by start_date
                                  rows between unbounded preceding
                                           and 1 preceding)
                as previous_max
    from my_table
  ) ,
cont as
  ( select start_date, 
           coalesce(lead(previous_max) over (order by start_date),
                    (select max(end_date) from my_table)
                   ) as end_date
    from c 
    where previous_max < start_date 
       or previous_max is null  
   )
select *
from cont
where tsrange(start_date, end_date)
       @>                             -- contains
      tsrange('2015-04-02 22:10:00', '2015-04-02 22:30:00') 
limit 1 ;

Test at SQLfiddle

  • It might be cheaper to check for overlapping gaps than surrounding islands. – Erwin Brandstetter Apr 3 '15 at 21:00
  • @ErwinBrandstetter. I was thinking that a recursive query would be more suitable (and efficient) when one wants to search on one range only. – ypercubeᵀᴹ Apr 3 '15 at 21:23
  • Recursion comes at a price, a plain query should be faster. I updated with a query that covers all corner cases and eliminates irrelevant rows early. Maybe the OP can test the queries with EXPLAIN ANALYZE and report runtimes. – Erwin Brandstetter Apr 3 '15 at 23:00
2

This query returns all gaps in the data that overlap with the given time range. Also covers leading, trailing or total (covering) gaps:

WITH input(t1, t2) AS (SELECT '2015-04-02 22:00'::timestamp
                            , '2015-04-02 23:00'::timestamp)  -- t1 < t2
,    gap  AS (
   SELECT max(end_date) OVER (ORDER BY start_date
             ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING) AS start_gap
        , start_date AS end_gap
        , end_date  -- for possible trailing gap
   FROM   my_table
   WHERE  end_date   >= (SELECT t1 FROM input)  -- exclude rows early
   AND    start_date <= (SELECT t2 FROM input)
   )
SELECT start_gap, end_gap
FROM   gap
WHERE  end_gap > start_gap  -- gap within time range
   OR  start_gap IS NULL AND end_gap > (SELECT t1 FROM input) -- leading gap

UNION ALL
SELECT max(end_date), NULL  -- trailing gap
FROM   gap
HAVING max(end_date) < (SELECT t2 FROM input)

UNION ALL
SELECT NULL, NULL  -- total gap
WHERE  NOT EXISTS (SELECT 1 FROM gap)
ORDER  BY end_gap;

If nothing is returned, the check succeeds:

checks if a contiguous date interval between two given dates exists?

Only needs a single scan over the base table and a single window function. Should be fast.

If you are not familiar with window functions, read this chapter of the manual.

Related:

About OVERLAPS:

Function counting gaps

For a quick answer to your question without details, the query can be simplified. Also parameter handling is more convenient in a function:

CREATE OR REPLACE FUNCTION f_find_gaps(t1 timestamp, t2 timestamp)
  RETURNS int AS
$func$
WITH gap AS (
   SELECT max(end_date) OVER (ORDER BY start_date
             ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING) AS start_gap
        , start_date AS end_gap
        , end_date  -- for possible trailing gap & total gap
   FROM   my_table
   WHERE  end_date   >= t1  -- exclude rows early
   AND    start_date <= t2
   )
SELECT count(*)::int
     + CASE WHEN (SELECT max(end_date) >= t2 FROM gap) THEN 0 ELSE 1 END
     -- covers trailing gap & total gap
FROM   gap
WHERE  end_gap > start_gap  -- gap within time range
   OR  start_gap IS NULL AND end_gap > t1  -- leading gap
$func$ LANGUAGE sql;

Call:

SELECT f_find_gaps('2015-04-02 22:00', '2015-04-02 23:00');

Returns the number of gaps. 0 means, your range is covered.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.