Checking if booking is possible in SQL (Postgresql)

Question

I have table booking with such looking records:

  id  |        from         |         to
------+---------------------+---------------------
  101 | 2015-09-24 08:00:00 | 2015-09-24 09:30:00
 2261 | 2015-09-24 09:00:00 | 2015-09-24 10:00:00
 4061 | 2015-09-24 10:00:00 | 2015-09-24 10:30:00
  204 | 2015-09-24 12:00:00 | 2015-09-24 13:30:00
 2400 | 2015-09-24 13:30:00 | 2015-09-24 14:00:00
 4224 | 2015-09-24 14:00:00 | 2015-09-24 14:30:00
  309 | 2015-09-24 16:00:00 | 2015-09-24 17:30:00
 2541 | 2015-09-24 17:00:00 | 2015-09-24 18:00:00

I am looking for optimal query to find anwser to question:

Is this possible to find a timeslot with duration x (ie. 30 minutes) in above records?

I have ideas to use postgres arrays or time ranges, but still looking for better ideas....

EDIT: I will provide 'fake' bookings as boundaries, but if you have ideas how to do it better, please write :)

The question seems incomplete. If you have no bookings, then you cannot fine time slots. In other words, you need to provide start and end information. — Gordon Linoff, Sep 26 '15 at 11:22
@GordonLinoff : You are right. I am currently assuming [ -infinity,+infinity ] — wildplasser, Sep 26 '15 at 11:53

score 1 · Answer 1 · answered Sep 26 '15 at 10:46

Something like this:

select t1.*
from tablename t1
where (select min("from") from tablename t2
       where t2."from" > t1."from") >= t1."to" + interval '30' minute

I.e. return a row if the gap to the following row is >= 30 minutes.

Note: from and to are reserved words in ANSI SQL, that's why they are delimited as "from" and "to".

score 1 · Answer 2 · answered Sep 26 '15 at 13:50

Here's one solution using analytical functions, it provides all windows with no bookings:

SELECT null as ts_from, min(ts_from) as ts_to
  FROM bookings
 UNION ALL
SELECT ts as ts_from, next_ts as ts_to
  FROM (SELECT ts, lead(ts, 1) over (order by ts) as next_ts, sum(bk) over (order by ts) as bksum
          FROM (SELECT ts_from as ts, 1 as bk
                  FROM bookings
                 UNION ALL
                SELECT ts_to as ts, -1 as bk
                  FROM bookings) as t) as tt
 WHERE bksum = 0
 ORDER BY 1 NULLS FIRST;

SQL Fiddle here.

klin · Answer 3 · 2015-09-26T11:43:05.383

You can use lag() function:

select *, book_start- previous_book_end timeslot
from (
    select id, "from" book_start, "to" book_end, 
    lag("to") over (order by "to") previous_book_end
    from test
    ) sub
order by book_end

  id  |     book_start      |      book_end       |  previous_book_end  | timeslot
------+---------------------+---------------------+---------------------+-----------
  101 | 2015-09-24 08:00:00 | 2015-09-24 09:30:00 |                     |
 2261 | 2015-09-24 09:00:00 | 2015-09-24 10:00:00 | 2015-09-24 09:30:00 | -00:30:00
 4061 | 2015-09-24 10:00:00 | 2015-09-24 10:30:00 | 2015-09-24 10:00:00 | 00:00:00
  204 | 2015-09-24 12:00:00 | 2015-09-24 13:30:00 | 2015-09-24 10:30:00 | 01:30:00
 2400 | 2015-09-24 13:30:00 | 2015-09-24 14:00:00 | 2015-09-24 13:30:00 | 00:00:00
 4224 | 2015-09-24 14:00:00 | 2015-09-24 14:30:00 | 2015-09-24 14:00:00 | 00:00:00
  309 | 2015-09-24 16:00:00 | 2015-09-24 17:30:00 | 2015-09-24 14:30:00 | 01:30:00
 2541 | 2015-09-24 17:00:00 | 2015-09-24 18:00:00 | 2015-09-24 17:30:00 | -00:30:00
(8 rows)

Select rows with timeslots >= '30m'::interval:

select *, book_start- previous_book_end timeslot
from (
    select id, "from" book_start, "to" book_end, 
    lag("to") over (order by "to") previous_book_end
    from test
    ) sub
where book_start- previous_book_end >= '30m'::interval
order by book_end

 id  |     book_start      |      book_end       |  previous_book_end  | timeslot
-----+---------------------+---------------------+---------------------+----------
 204 | 2015-09-24 12:00:00 | 2015-09-24 13:30:00 | 2015-09-24 10:30:00 | 01:30:00
 309 | 2015-09-24 16:00:00 | 2015-09-24 17:30:00 | 2015-09-24 14:30:00 | 01:30:00
(2 rows)

You can't look at previous booking only. Imagine the first booking covers entire timespan. You willl report incorrect slots ([example](http://sqlfiddle.com/#!15/b2bd2/3)). — Kombajn zbożowy, Sep 26 '15 at 13:56
Sure, I can imagine everything. Perhaps a better idea would be to leave the OP assess whether such hypothetical situations can take place? — klin, Sep 26 '15 at 14:15
Well, I made mistake, and we can assume bookings cant overlaps (in example it does but there are some foreign keys in table). — Sławosz, Sep 26 '15 at 18:37
This is consistent with how I understand the essence of booking. The query in my answer could help with avoiding such cases. Well, @Kombajnzbożowy, downvoting was a little bit premature, was not it? — klin, Sep 26 '15 at 22:47
Yes, with constraint of non-overlapping bookings your solution is fine. I just assumed worst case in the beginning. — Kombajn zbożowy, Sep 27 '15 at 11:31

wildplasser · Answer 4 · 2015-09-26T13:59:26.957

Non-standard self-join:

SELECT
    ll.ts_to AS ts_from
    , hh.ts_from AS ts_to
FROM bookings ll
JOIN bookings hh
    -- enough space 
    ON hh.ts_from >= ll.ts_to + '30 min'::interval
    -- and nothing in between
    AND NOT EXISTS (
        SELECT * FROM bookings nx
        WHERE nx.ts_from >= ll.ts_to
        AND nx.ts_to <= hh.ts_from
        )
UNION ALL   -- before the first
SELECT '-infinity'::timestamp AS ts_from
       , MIN(ts_from) AS ts_to
    FROM bookings
UNION ALL   -- after the last
SELECT MAX(ts_to) AS ts_from
       , 'infinity'::timestamp AS ts_to
    FROM bookings
ORDER BY 1,2
    ;

Slava Lenskyy · Answer 5 · 2015-09-26T20:39:14.547

Generate your slots and then left join them. http://sqlfiddle.com/#!15/12bfa

create table t (id integer, "from" timestamp, "to" timestamp);

insert into t values 
(101 , '2015-09-24 08:00:00' , '2015-09-24 09:30:00' ),
(2261 , '2015-09-24 09:00:00' , '2015-09-24 10:00:00' ),
(4061 , '2015-09-24 10:00:00' , '2015-09-24 10:30:00' ),
( 204 , '2015-09-24 12:00:00' , '2015-09-24 13:30:00' ),
(2400 , '2015-09-24 13:30:00' , '2015-09-24 14:00:00' ),
(4224 , '2015-09-24 14:00:00' , '2015-09-24 14:30:00' ),
( 309 , '2015-09-24 16:00:00' , '2015-09-24 17:30:00' ),
(2541 , '2015-09-24 17:00:00' , '2015-09-24 18:00:00' );

SELECT time_slots.t,
       time_slots.t + interval '30 minutes'
FROM generate_series(date'2015-09-24',date'2015-09-25' - interval '30 minutes' ,interval '30 minutes') AS time_slots(t)
LEFT JOIN t ON (time_slots.t BETWEEN t."from" AND t."to")
WHERE t.id IS NULL;


SELECT time_slots.t,
       time_slots.t + interval '30 minutes'
FROM generate_series(date'2015-09-24',date'2015-09-25' - interval '30 minutes',interval '30 minutes') AS time_slots(t)
LEFT JOIN t ON ((time_slots.t,
                 time_slots.t + interval '30 minutes') OVERLAPS (t."from",
                                                                 t."to"))
WHERE t.id IS NULL;

Checking if booking is possible in SQL (Postgresql)

5 Answers5