Re: Finding gaps in scheduled events

Richard Huxton wrote:
> Marcin Stępnicki wrote:
>>
>> start | finish | type_id
>> ------+--------+--------
>> 8:30  |  8:45  |    1    -> type A
>> 9:30  | 10:00  |    2    -> type B
>
>> I have to deal with the existing schema, but if it can be done in a
>> better way please let me know so I could avoid mistakes in my own 
>> programs
>> (although I think it's quite flexible and I like the concept).
>
> The reason you're finding it difficult is that you're asking the 
> database for information based on what *isn't* stored in it. That is 
> you're asking it for all the gaps in your event data.
>
> Now, if you were doing it by hand you'd sort the events according to 
> time and compare finish/start times in order. You can do something 
> similar with PG and write a plpgsql function that returns a setof 
> (start,finish,length) for gaps.
You  wouldn't even need the sort.  In the function just loop, starting 
at the earliest possible event start time, and increment by 15 minutes 
until you've hit the last possible start time and at each time check to 
see if there is already an event scheduled for that time, if there was a 
30 minute event that is scheduled to start 15 minutes earlier, or if 
there is an event already scheduled to start at the next time (which 
would limit an event at the current time to 15 minutes).  You could make 
it  "smarter" by observing that whenever you get to an event that's 30 
minutes long you can skip checking the next start time.
> If you have a lot of events and you need to find gaps quite often it 
> might be easier to keep a separate table to track them. Triggers on 
> the events table would keep the gaps table up to date. If events can 
> be deleted/moved you'll want to consider how to merge adjacent gaps.
Also a good idea.
>
> If you don't like either of those, you'll need to figure out what the 
> "next" and "previous" events are for each event in your table. That 
> will need to be a sub-query with something like:
>
> SELECT
>   a.start,
>   a.finish,
>   (
>     SELECT start FROM test_events WHERE start>a.finish ORDER BY start 
> LIMIT 1
>   ) AS next_start
> FROM
>   test_events a
> ORDER BY start;
>
> Note the subquery is in the SELECT clause and this query-plan will 
> probably run over the table twice (via indexes).
Here your still left mostly in the dark and still need to loop through 
the results checking the gaps between a.finish and next start.  And, 
since you're working with the full result set at that point and it is 
already ordered by each event's start time, you don't need the subquery 
as at each iteration of the loop you can do a simple difference of the 
current row's a.finish and the next's a.start to get the gap (with a 
special case to handle the last scheduled event).

-- 
erik jones <erik@myemma.com>
software development
emma(r)