pg.ddx.io pgsql-sql@postgresql.org mailing list archive
help / color / mirror / Atom feedFinding gaps in scheduled events
5+ messages / 4 participants
[nested] [flat]
* Finding gaps in scheduled events
@ 2006-12-12 09:08 Marcin Stępnicki <mstepnicki@gmail.com>
0 siblings, 2 replies; 5+ messages in thread
From: Marcin Stępnicki @ 2006-12-12 09:08 UTC (permalink / raw)
To: pgsql-sql
Hello.
I've been struggling with this one for over a week, but for some reason my
mind isn't compatibile with the problem - it seems simple, yet I'm unable
to find the proper solution :(.
I have a timeline divided to 15 minute periods:
start |
------+
8:00 |
8:15 |
8:30 |
8:45 |
(...)|
14:45 |
Then, I have two types of events that fit the schedule. Event A takes
15 minutes, event B takes 30 minutes. They're stored in a table like this:
start | finish | type_id
------+--------+--------
8:30 | 8:45 | 1 -> type A
9:30 | 10:00 | 2 -> type B
Now I need to create a query to find hours at which each of the type can
start. So, if it's event A (which take 15 minutes) it can start at:
8:00 (to 8:15)
8:15 (to 8:30)
( 8:30 to 8:45 is already taken )
8:45 (to 9:00)
9:00 (to 9:15)
9:15 (to 9:30)
( 9:30 to 10:00 (9:30-9:45 and 9:45-10:00) is already taken))
10:00 (to 10:15)
(...)
and if it's event B (which takes 30 minutes) it can start at:
8:00 (to 8:30)
8:45 (to 9:15)
9:00 (to 9:30)
10:00 (to 10:30)
(...)
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).
Example tables:
create table test_events (
id serial,
start time,
finish time,
type_id integer );
insert into test_events ( start,finish,type_id ) values('8:30','8:45','1');
insert into test_events ( start,finish,type_id ) values ('9:30','10:00','2');
create table test_timeline as
SELECT
('0:00'::TIME + (my_day.h || ' minutes')::INTERVAL)::TIME as my_hour
FROM
generate_series (0,1425,15) AS my_day(h);
I don't paste my tries because they've all failed and I think I miss
something fundamental here.
Thank you very much for your time.
--
| And Do What You Will be the challenge | http://apcoln.linuxpl.org
| So be it in love that harms none | http://biznes.linux.pl
| For this is the only commandment. | http://www.juanperon.info
`---* JID: Aragorn_Vime@jabber.org *---' http://www.naszedzieci.org
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: Finding gaps in scheduled events
@ 2006-12-12 20:13 Richard Huxton <dev@archonet.com>
parent: Marcin Stępnicki <mstepnicki@gmail.com>
1 sibling, 1 reply; 5+ messages in thread
From: Richard Huxton @ 2006-12-12 20:13 UTC (permalink / raw)
To: Marcin Stępnicki <mstepnicki@gmail.com>; +Cc: pgsql-sql
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.
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.
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).
HTH
--
Richard Huxton
Archonet Ltd
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: Finding gaps in scheduled events
@ 2006-12-12 22:14 Erik Jones <erik@myemma.com>
parent: Richard Huxton <dev@archonet.com>
0 siblings, 0 replies; 5+ messages in thread
From: Erik Jones @ 2006-12-12 22:14 UTC (permalink / raw)
To: Richard Huxton <dev@archonet.com>; +Cc: Marcin Stępnicki <mstepnicki@gmail.com>; pgsql-sql
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)
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: Finding gaps in scheduled events
@ 2006-12-12 22:23 Alvaro Herrera <alvherre@commandprompt.com>
parent: Marcin Stępnicki <mstepnicki@gmail.com>
1 sibling, 1 reply; 5+ messages in thread
From: Alvaro Herrera @ 2006-12-12 22:23 UTC (permalink / raw)
To: Marcin Stępnicki <mstepnicki@gmail.com>; +Cc: pgsql-sql
Marcin Stępnicki wrote:
> Now I need to create a query to find hours at which each of the type can
> start. So, if it's event A (which take 15 minutes) it can start at:
>
> 8:00 (to 8:15)
> 8:15 (to 8:30)
> ( 8:30 to 8:45 is already taken )
> 8:45 (to 9:00)
> 9:00 (to 9:15)
> 9:15 (to 9:30)
> ( 9:30 to 10:00 (9:30-9:45 and 9:45-10:00) is already taken))
> 10:00 (to 10:15)
I think something like this should help you:
select my_hour
from test_events right join test_timeline on
((start, finish) overlaps (my_hour, my_hour + 15 * '1 minute'::interval))
where start is null;
With your test data, it shows all the times except for 8:30, 9:30 and
9:45.
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: Finding gaps in scheduled events
@ 2006-12-12 23:58 Erik Jones <erik@myemma.com>
parent: Alvaro Herrera <alvherre@commandprompt.com>
0 siblings, 0 replies; 5+ messages in thread
From: Erik Jones @ 2006-12-12 23:58 UTC (permalink / raw)
To: Marcin Stępnicki <mstepnicki@gmail.com>; pgsql-sql
Alvaro Herrera wrote:
> Marcin Stępnicki wrote:
>
>
>> Now I need to create a query to find hours at which each of the type can
>> start. So, if it's event A (which take 15 minutes) it can start at:
>>
>> 8:00 (to 8:15)
>> 8:15 (to 8:30)
>> ( 8:30 to 8:45 is already taken )
>> 8:45 (to 9:00)
>> 9:00 (to 9:15)
>> 9:15 (to 9:30)
>> ( 9:30 to 10:00 (9:30-9:45 and 9:45-10:00) is already taken))
>> 10:00 (to 10:15)
>>
>
> I think something like this should help you:
>
> select my_hour
> from test_events right join test_timeline on
> ((start, finish) overlaps (my_hour, my_hour + 15 * '1 minute'::interval))
> where start is null;
>
> With your test data, it shows all the times except for 8:30, 9:30 and
> 9:45.
>
Nice! And, he can run that query again, flipping the 15 to 30, to get
the list of available 30 minute gaps. That's a heck-of-a lot simpler
than the stuff I discussed earlier.
--
erik jones <erik@myemma.com>
software development
emma(r)
^ permalink raw reply [nested|flat] 5+ messages in thread
end of thread, other threads:[~2006-12-12 23:58 UTC | newest]
Thread overview: 5+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2006-12-12 09:08 Finding gaps in scheduled events Marcin Stępnicki <mstepnicki@gmail.com>
2006-12-12 20:13 ` Richard Huxton <dev@archonet.com>
2006-12-12 22:14 ` Erik Jones <erik@myemma.com>
2006-12-12 22:23 ` Alvaro Herrera <alvherre@commandprompt.com>
2006-12-12 23:58 ` Erik Jones <erik@myemma.com>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox