Sql-server – Finding all date ranges that overlap a target date range

database-designoracleperformancequery-performancesql server

Say I wish to store when staff are on holiday (FromDate, ToDate) and then I wish to find all staff that are on holiday between two given dates (QFromDate, QToDate).

Now assume that I have many such records (more than will fit in the server’s RAM) and need to do this query often.

Now assume that I also have sick_leave tables, shift_pattern tables, pay_rate tables, etc – all that have FromDate and ToDate with the requirement to join them based on overlapping dates.

How should I store the date ranges and how can the queries be written to run fast?

(The choice of RDBMS is not fixed, but being able to run on any “standard” RDBMS is of value unless doing so has a large adverse effect.)

I have posted some answers that I have considered, but don't like! However they may help other people.

Best Answer

You can generate a customized index table, for example, that has a row for all year&week pairs that the date range (a certain vacation etc) encompasses. Then you can join dateranges by going through that index table. It will be large, but does avoid large scans as you can just list all vacations that have any weeks that are in common with another vacation, as an inner join.

pseudo example:

create table rangeindex (
  vacation_id bigint, 
  year int, 
  week int, 
  primary key (year,week,vacation_id), 
  index (vacation_id))

select v2.* 
    from vacation v1 
    join rangeindex r1 on r1.vacation_id = v1.vacation_id 
    join rangeindex r2 on r2.year = r1.year and r2.week = r1.week
    join vacation v2 on v2.vacation_id = r2.vacation_id
where v1.vacation_user = ?
    -- and the usual start/end comparisons to filter unwanted pseudo hits

Similar things are used for example spatial coordinate stuff, dividing linear coordinates to grid cells that can be indexed and scanned more easily.

Update: fixed primary key

Related Solutions

Sql-server – 2 Date Ranges – How many days from one range excluding weekends overlap

Create date tables or table variables with your ranges and do the join query. Assuming SQL Server as the database, my sample solution is given below.

Declare @Range1Begin date = '10/16/2014',
        @Range1End   date = '10/28/2014',
        @Range2Begin date = '9/22/2014',
        @Range2End   date = '10/21/2014';

Declare @DateTable1 table (Date1 date);

Insert into @DateTable1
select dateadd(day, number, @Range1Begin)
from 
    (select distinct number from master.dbo.spt_values
     where name is null) n
where dateadd(day, number, @Range1Begin) <= @Range1End;

Declare @DateTable2 table (Date2 date);

Insert into @DateTable2
select dateadd(day, number, @Range2Begin)
from 
    (select distinct number from master.dbo.spt_values
     where name is null ) n
where dateadd(day, number, @Range2Begin) <= @Range2End;


-- Get individual dates
select dt1.Date1 as date, datename(w, dt1.date1) as weekday from @DateTable1 dt1
inner join @DateTable2 dt2
on dt1.date1 = dt2.date2
where datepart(w, dt1.date1) not in (1,7);


-- Get total days
select count(*) as TotalDays from @DateTable1 dt1
inner join @DateTable2 dt2
on dt1.date1 = dt2.date2
where datepart(w, dt1.date1) not in (1,7);

Without declaring table variables, following is the solution.

Declare @Range1Begin date = '10/16/2014',
        @Range1End   date = '10/28/2014',
        @Range2Begin date = '9/22/2014',
        @Range2End   date = '10/21/2014';

-- Get total days
select count(*) as TotalDays from (select dateadd(day, number, @Range1Begin) date1
from 
    (select distinct number from master.dbo.spt_values
     where name is null) n
where dateadd(day, number, @Range1Begin) <= @Range1End) dt1
inner join (select dateadd(day, number, @Range2Begin) date2
from 
    (select distinct number from master.dbo.spt_values
     where name is null ) n
where dateadd(day, number, @Range2Begin) <= @Range2End) dt2
on dt1.date1 = dt2.date2
where datepart(w, dt1.date1) not in (1,7);

PostgreSQL – Datetime ranges overlap

I suggest a couple of important improvements for dealing with a million rows:

SELECT br.duration
FROM  (
   VALUES 
      ('[2016-09-06 03:45:00+00, 2016-09-06 14:45:00+00)'::tstzrange)  
    , ('[2016-09-06 14:45:00+00, 2016-09-06 15:45:00+00)')
      -- more items
   ) br(duration)
WHERE EXISTS (
   SELECT FROM booking
   WHERE  tstzrange(ts_start, ts_end) && br.duration
   );

While providing your list of values with the needlessly verbose and expensive form SELECT ... UNION ..., make that UNION ALL, or Postgres will waste time trying to fold duplicates. And you would only need to declare column name(s) and data type(s) for the first SELECT of the UNION query.
But a VALUES expression is simpler and faster. Or provide an array tstzrange[] and use unnest():
- Optimizing a Postgres query with a large IN
The query you have would return one row for every overlapping row in booking, while you probably want each overlapping value from the list once, most likely. You could add DISTINCT or GROUP BY to get unique rows, but that would still be a waste of time. An EXISTS semi-join is one of the much simpler and cheaper alternatives for your case: Each row from duration is returned exactly once if an overlapping entry is found and Postgres can stop looking further for this row.
The query would still be slow without index support. Create a functional GiST or SP-GiST index. The latter probably performing best:
```
CREATE INDEX booking_ts_range_idx on booking USING spgist (tstzrange(ts_start, ts_end));
```

Optimizing queries on a range of timestamps (two columns)
Native way of performing this hours of operation query in PostgreSQL
Help with adding a time filter to Postgres query
Perform this hours of operation query in PostgreSQL (incl. SP-GiST index example and benchmark comparing alternatives)

Best Answer

Related Solutions

Sql-server – 2 Date Ranges – How many days from one range excluding weekends overlap

PostgreSQL – Datetime ranges overlap

Related Question