How to find first free start times from reservations in Postgres

Question

People work from 10:00AM to 21:00PM except Sundays and public holidays.

Jobs for them are reserved at 15 minute intervals. Job duration is from 15 minutes to 4 hours. Whole job must fit to single day.

How to find first nearest free start times which are not reserved for given duration in Postgres 9.3 starting from current date and time ?

For example, Mary has already reservation at 12:30 .. 16:00 and John has already reservation at 12:00 to 13:00

Reservat table contains reservations, yksus2 table contains workes and pyha table contains public holidays. Table structures are below. Reservat structure can changed if this helps.

Query for ealiest start times for duration of 1.5 hours should return

John 2014-10-28 10:00
Mary 2014-10-28 10:00
John 2014-10-28 10:15
Mary 2014-10-28 10:15
John 2014-10-28 10:30
Mary 2014-10-28 10:30
Mary 2014-10-28 11:00
John 2014-10-28 13:00
Mary 2014-10-28 16:00
Mary 2014-10-28 16:15
Mary 2014-10-28 16:30
... etc and also starting from next days

I tried query based on answer in How to return only work time from reservations in PostgreSql? below but it returns wrong result:

MARY  2014-10-28 13:00:00
MARY  2014-10-29 22:34:40.850255
JOHN  2014-10-30 22:34:40.850255
MARY  2014-10-31 22:34:40.850255
MARY  2014-11-03 22:34:40.850255

Also sliding start times 10:00, 10:30 etc are not returned.
How to get proper first reservations?

Query which returns wrong result is:

insert into reservat (objekt2, during) values 
('MARY', '[2014-10-28 11:30:00,2014-10-28 13:00:00)'), 
('JOHN', '[2014-10-28 10:00:00,2014-10-28 11:30:00)');

with gaps as (
    select
        yksus, 
        upper(during) as start,
        lead(lower(during),1,upper(during)) over (ORDER BY during) - upper(during) as gap
    from (
        select 
           yksus2.yksus,
           during
          from reservat join yksus2 on reservat.objekt2=yksus2.yksus 
          where  upper(during)>= current_date
        union all
        select
            yksus2.yksus,
            unnest(case
                when pyha is not null then array[tsrange1(d, d + interval '1 day')]
                when date_part('dow', d) in (0, 6) then array[tsrange1(d, d + interval '1 day')]
                when d::date =  current_Date then array[
                            tsrange1(d, current_timestamp ), 
                            tsrange1(d + interval '20 hours', d + interval '1 day')]
                else array[tsrange1(d, d + interval '8 hours'), 
                           tsrange1(d + interval '20 hours', d + interval '1 day')]
            end)
        from yksus2, generate_series(
            current_timestamp,
            current_timestamp + interval '1 month',
            interval '1 day'
        ) as s(d) 
        left join pyha on pyha = d::date
    ) as x 
)

select yksus, start
  from gaps 
where gap >= interval'1hour 30 minutes'
order by start
limit 30

Schema:

CREATE EXTENSION btree_gist;
CREATE TABLE Reservat (
      id serial primary key,
      objekt2 char(10) not null references yksus2 on update cascade deferrable,
      during tsrange not null check(
         lower(during)::date = upper(during)::date
         and lower(during) between current_date and current_date+ interval'1 month'

         and (lower(during)::time >= '10:00'::time and upper(during)::time < '21:00'::time) 
         AND EXTRACT(MINUTE FROM lower(during)) IN (0, 15, 30,45)
         AND EXTRACT(MINUTE FROM upper(during)) IN (0, 15, 30, 45)
         and (date_part('dow', lower(during)) in (1,2,3,4,5,6) 
         and date_part('dow', upper(during)) in (1,2,3,4,5,6)) 
      ),

      EXCLUDE USING gist (objekt2 WITH =, during WITH &&)
    );  

create or replace function holiday_check() returns trigger language plpgsql stable as $$
    begin
        if exists (select * from pyha  where pyha in (lower(NEW.during)::date, upper(NEW.during)::date)) then
            raise exception 'public holiday %', lower(NEW.during) ;
        else
            return NEW;
        end if;
    end;
    $$;

create trigger holiday_check_i before insert or update on Reservat for each row execute procedure holiday_check();

CREATE OR REPLACE FUNCTION public.tsrange1(start timestamp with time zone,
    finish timestamp with time zone ) RETURNS tsrange AS
$BODY$
SELECT tsrange(start::timestamp without time zone, finish::timestamp without time zone );
$BODY$ language sql immutable;


-- Workers
create table yksus2( yksus char(10) primary key);
insert into yksus2 values ('JOHN'), ('MARY');

-- public holidays
create table pyha( pyha date primary key);

Also posted to the pgsql-general mailing list.

Answer 1

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