How to find first free start times from reservations in Postgres

Adapted schema

CREATE EXTENSION btree_gist; CREATE TYPE timerange AS RANGE (subtype = time); -- create type once -- Workers CREATE TABLE worker( worker_id serial PRIMARY KEY , worker text NOT NULL ); INSERT INTO worker(worker) VALUES ('JOHN'), ('MARY'); -- Holidays CREATE TABLE pyha(pyha date PRIMARY KEY); -- Reservations CREATE TABLE reservat ( reservat_id serial PRIMARY KEY , worker_id int NOT NULL REFERENCES worker ON UPDATE CASCADE , day date NOT NULL CHECK (EXTRACT('isodow' FROM day) < 7) , work_from time NOT NULL -- including lower bound , work_to time NOT NULL -- excluding upper bound , CHECK (work_from >= '10:00' AND work_to <= '21:00' AND work_to - work_from BETWEEN interval '15 min' AND interval '4 h' AND EXTRACT('minute' FROM work_from) IN (0, 15, 30, 45) AND EXTRACT('minute' FROM work_from) IN (0, 15, 30, 45) ) , EXCLUDE USING gist (worker_id WITH =, day WITH = , timerange(work_from, work_to) WITH &&) ); INSERT INTO reservat (worker_id, day, work_from, work_to) VALUES (1, '2014-10-28', '10:00', '11:30') -- JOHN , (2, '2014-10-28', '11:30', '13:00'); -- MARY -- Trigger for volatile checks CREATE OR REPLACE FUNCTION holiday_check() RETURNS trigger AS $func$ BEGIN IF EXISTS (SELECT 1 FROM pyha WHERE pyha = NEW.day) THEN RAISE EXCEPTION 'public holiday: %', NEW.day; ELSIF NEW.day < now()::date OR NEW.day > now()::date + 31 THEN RAISE EXCEPTION 'day out of range: %', NEW.day; END IF; RETURN NEW; END $func$ LANGUAGE plpgsql STABLE; -- can be "STABLE" CREATE TRIGGER insupbef_holiday_check BEFORE INSERT OR UPDATE ON reservat FOR EACH ROW EXECUTE PROCEDURE holiday_check(); 

Major points

• Don't use char(n). Rather varchar(n), or better yet, varchar or just text.

  • Any downsides of using data type "text" for storing strings?

• Don't use the name of a worker as primary key. It's not necessarily unique and can change. Use a surrogate primary key instead, best a serial. Also makes entries in reservat smaller, indexes smaller, queries faster, ...

• Update: For cheaper storage (8 bytes instead of 22) and simpler handling I save start and end as time now and construct a range on the fly for the exclusion constraint:

  EXCLUDE USING gist (worker_id WITH =, day WITH = , timerange(work_from, work_to) WITH &&) 

• Since your ranges can never cross the date border by definition, it would be more efficient to have a separate date column (day in my implementation) and a time range. The type timerange is not shipped in default installations, but easily created. This way you can largely simplify your check constraints.

• Use EXTRACT('isodow', ...) to simplify excluding sundays

  The day of the week as Monday(1) to Sunday(7)

• I assume you want to allow the upper border of '21:00'.

• Borders are assumed to be including for the lower and excluding for the upper bound.

• The check whether new / updated days lie within a month from "now" is not IMMUTABLE. Moved it from the CHECK constraint to the trigger - else you might run into problems with dump / restore! Details:

  • Disable all constraints and table checks while restoring a dump

Aside
Besides simplifying input and check constraints I expected timerange to save 8 bytes of storage as compared to tsrange since time only occupies 4 bytes. But it turns out timerange occupies 22 bytes on disk (25 in RAM), just like tsrange (or tstzrange). So you might go with tsrange as well. The principle of query and exclusion constraint are the same.

Query

Wrapped into an SQL function for convenient parameter handling:

CREATE OR REPLACE FUNCTION f_next_free(_start timestamp, _duration interval) RETURNS TABLE (worker_id int, worker text, day date , start_time time, end_time time) AS $func$ SELECT w.worker_id, w.worker , d.d AS day , t.t AS start_time ,(t.t + _duration) AS end_time FROM ( SELECT _start::date + i AS d FROM generate_series(0, 31) i LEFT JOIN pyha p ON p.pyha = _start::date + i WHERE p.pyha IS NULL -- eliminate holidays ) d CROSS JOIN ( SELECT t::time FROM generate_series (timestamp '2000-1-1 10:00' , timestamp '2000-1-1 21:00' - _duration , interval '15 min') t ) t -- times CROSS JOIN worker w WHERE d.d + t.t > _start -- rule out past timestamps AND NOT EXISTS ( SELECT 1 FROM reservat r WHERE r.worker_id = w.worker_id AND r.day = d.d AND timerange(r.work_from, r.work_to) && timerange(t.t, t.t + _duration) ) ORDER BY d.d, t.t, w.worker, w.worker_id LIMIT 30 -- could also be parameterized $func$ LANGUAGE sql STABLE; 

Call:

SELECT * FROM f_next_free('2014-10-28 12:00'::timestamp, '1.5 h'::interval); 

SQL Fiddle on Postgres 9.3 now.

Explain

• The function takes a _start timestamp as minimum starting time and _duration interval. Be careful to only rule out earlier times on the starting day, not the following days. Simplest by just adding day and time: t + d > _start.
  To book a reservation starting "now", just pass now()::timestamp:

  SELECT * FROM f_next_free(`now()::timestamp`, '1.5 h'::interval); 

• Subquery d generates days starting from the input value _day. Holidays excluded.

• Days are cross-joined with possible time ranges generated in subquery t.
• That is cross-joined to all available workers w.
• Finally eliminate all candidates that collide with existing reservations using an NOT EXISTS anti-semi-join, and in particular the overlaps operator && .

Related:

• How do you do date math that ignores the year? (for date math example)
• Preventing adjacent/overlapping entries with EXCLUDE in PostgreSQL
• Calculate working hours between 2 dates in PostgreSQL