What is a simple and efficient way to find rows with time-interval overlaps in SQL?

Question

I have two tables, both with start time and end time fields. I need to find, for each row in the first table, all of the rows in the second table where the time intervals intersect.

For example:

           <-----row 1 interval------->
<---find this--> <--and this--> <--and this-->

Please phrase your answer in the form of a SQL WHERE-clause, AND consider the case where the end time in the second table may be NULL.

Target platform is SQL Server 2005, but solutions from other platforms may be of interest also.

possible duplicate of [Determine Whether Two Date Ranges Overlap](http://stackoverflow.com/questions/325933/determine-whether-two-date-ranges-overlap) — Salman A, Sep 06 '14 at 14:53
Presumably, if the end time in the second table is NULL, it should be treated as 'the period does not have an end time and continues into the future'. That's what the accepted answer does; it is a common interpretation, but it isn't the only possible interpretation. — Jonathan Leffler, Nov 29 '15 at 16:38
[Merge Overlapping Intervals](https://www.geeksforgeeks.org/merging-intervals/) algorithm can give some leads. — RBT, May 30 '18 at 10:33
@RBT: "Please phrase your answer in the form of a SQL WHERE-clause" :-) — Steven A. Lowe, Jun 01 '18 at 00:23

score 66 · Accepted Answer · edited Nov 28 '08 at 16:36

66

SELECT * 
FROM table1,table2 
WHERE table2.start <= table1.end 
AND (table2.end IS NULL OR table2.end >= table1.start)

edited Nov 28 '08 at 16:36

Steven A. Lowe

60,273
18
132
202

answered Sep 22 '08 at 22:20

Khoth

13,068
3
28
27

1

Note that if start and end denotes instances in time, you may want to remove the equality from the comparisons, otherwise two ranges will be considered intersecting even if one end at the same instance in time as the other starts. – Oskar Berggren Aug 19 '14 at 19:21
15

Prove: If two intervals not overlap then (s2 > e1 || e2 < s1). If they overlap then invert the condition: (! (s2 > e1 || e2 < s1)). Now it can be simplified using !(a||b) = !a && !b. Hence (s2 <= e1 && e2 >= s1). – Stanislav Oct 03 '14 at 14:33

score 2 · Answer 2 · answered Jun 26 '17 at 19:49

It's sound very complicated until you start working from reverse. Below I illustrated ONLY GOOD CASES (no overlaps)! defined by those 2 simple conditions, we have no overlap ranges if condA OR condB is TRUE, so we going to reverse those: NOT condA AND NOT CondB, in our case I just reversed signs (> became <=)

/*
|--------| A                             \___  CondA: b.ddStart >  a.ddEnd
            |=========| B                /      \____ CondB:  a.ddS >  b.ddE
                          |+++++++++| A         /
*/
--DROP TABLE ran
create table ran ( mem_nbr int, ID int, ddS date, ddE date)
insert ran values  
(100, 1,  '2012-1-1','2012-12-30'),    ----\ ovl
(100, 11, '2012-12-12','2012-12-24'),  ----/
(100, 2, '2012-12-31','2014-1-1'),
(100, 3, '2014-5-1','2014-12-14') ,

(220, 1, '2015-5-5','2015-12-14') ,    ---\ovl
(220, 22, '2014-4-1','2015-5-25') ,    ---/
(220, 3, '2016-6-1','2016-12-16')  

select  DISTINCT a.mem_nbr ,  a.* , '-' [ ], b.dds, b.dde, b.id 
FROM ran a
join ran b  on  a.mem_nbr = b.mem_nbr          -- match by mem#
               AND     a.ID <> b.ID            -- itself
                  AND     b.ddS <= a.ddE        -- NOT    b.ddS >  a.ddE       
                  AND     a.ddS <= b.ddE        -- NOT    a.ddS >  b.ddE

end date can be null :/ – Steven A. Lowe Sep 07 '17 at 18:56 — Steven A. Lowe, Sep 07 '17 at 18:56

score 2 · Answer 3 · edited Jun 20 '20 at 09:12

2

"solutions from other platforms may be of interest also."

SQL Standard defines OVERLAPS predicate:

Specify a test for an overlap between two events.
<overlaps predicate> ::=
   <row value constructor 1>  OVERLAPS <row value constructor 2> 

Example:

SELECT 1
WHERE ('2020-03-01'::DATE, '2020-04-15'::DATE) OVERLAPS 
      ('2020-02-01'::DATE, '2020-03-15'::DATE) 
-- 1

db<>fiddle demo

edited Jun 20 '20 at 09:12

Community

1
1

answered May 16 '20 at 09:40

Lukasz Szozda

162,964
23
234
275

Casper · Answer 4 · 2008-09-22T23:08:14.773

select * from table_1 
right join 
table_2 on 
(
table_1.start between table_2.start and table_2.[end]
or
table_1.[end] between table_2.start and table_2.[end]
or
(table_1.[end] > table_2.start and table_2.[end] is null)
)

EDIT: Ok, don't go for my solution, it perfoms like shit. The "where" solution is 14x faster. Oops...

Some statistics: running on a db with ~ 65000 records for both table 1 and 2 (no indexing), having intervals of 2 days between start and end for each row, running for 2 minutes in SQLSMSE (don't have the patience to wait)

Using join: 8356 rows in 2 minutes

Using where: 115436 rows in 2 minutes

score 0 · Answer 5 · answered Feb 20 '20 at 10:30

0

And what, if you want to analyse such an overlap on a minute precision with 70m+ rows? the only solution i could make up myself was a time dimension table for the join

else the dublicate-handling became a headache .. and the processing cost where astronomical

answered Feb 20 '20 at 10:30

Sven

1

i recommend to see this post for those needs to take in account the performance of sql query : https://www.red-gate.com/simple-talk/databases/sql-server/t-sql-programming-sql-server/calculating-gaps-between-overlapping-time-intervals-in-sql/ – Guillaume OSTORERO Nov 05 '21 at 19:44

What is a simple and efficient way to find rows with time-interval overlaps in SQL?

5 Answers5

Linked

Related