Finding efficient overlapped entries in a SQL table

Question

What is the most efficient way to find all entries which do overlap with others in the same table? Every entry has a start and end date. For example I have the following database setup:

CREATE TABLE DEMO
(
    DEMO_ID  int  IDENTITY ,
    START date  NOT NULL ,
    END  date  NOT NULL
);

INSERT INTO DEMO (DEMO_ID, START, END) VALUES (1, '20100201', '20100205');
INSERT INTO DEMO (DEMO_ID, START, END) VALUES (2, '20100202', '20100204');
INSERT INTO DEMO (DEMO_ID, START, END) VALUES (3, '20100204', '20100208');
INSERT INTO DEMO (DEMO_ID, START, END) VALUES (4, '20100206', '20100211');

My query looks as follow:

SELECT DISTINCT * 
FROM DEMO A, DEMO B
WHERE A.DEMO_ID != B.DEMO_ID
AND A.START < B.END
AND B.START < A.END

The problem is when my demo table has for example 20'000 rows the query takes too long. My environment is MS SQL Server 2008. Thanks for any more efficient solution

Answer 1

You could rewrite the query a bit:

SELECT A.DEMO_ID, B.DEMO_ID 
FROM DEMO A, DEMO B
WHERE A.DEMO_ID != B.DEMO_ID
AND A.START >= B.START
AND A.START <= B.END

Getting rid of the DISTINCT keyword may make things cheaper, because Sql Server will do a sort on the returned column (which is all of them when you use DISTINCT *) to eliminate duplicates.

You should also consider adding an index. With Sql Server 2008, I would recommend an index on START, END, containing DEMO_ID.

Answer 2

Use a function or stored procedure:

First, order the entries by Start and End

DECLARE @t table (
    Position int identity(1,1),
    DEMO_ID  int,
    START date  NOT NULL ,
    END  date  NOT NULL
)
INSERT INTO @t (DEMO_ID, START, END)
    SELECT DEMO_ID, START, END
    FROM DEMO
    ORDER BY START, END

Then check for overlaps with previous and next record:

SELECT t.DEMO_ID
FROM @t t INNER JOIN @t u ON t.Position + 1 = u.Position
WHERE u.Start <= t.End
UNION
SELECT t.DEMO_ID
FROM @t t INNER JOIN @t u ON t.Position - 1 = u.Position
WHERE t.Start <= u.End

You need to measure to be sure this is faster. In any case, we won't compare the date fields of all records with all the other records, so this could be faster for large datasets.

Answer 3

There is an excellent article about storing date ranges with no overlaps by Alexander Kuznetsoz

Answer 4

This is simpler and executes in about 2 seconds for over 20000 records

select * from demo a
where not exists(
select 1 from demo b 
where a.demo_id!=b.demo_id
AND A.S < B.E
AND B.S < A.E)

Answer 5

Late answer, but wondering if this would help:

create index IXNCL_Demo_DemoId on Demo(Demo_Id)

select a.demo_id, b.demo_id as [CrossingDate]
from demo a
    cross join demo b
    where a.[end] between b.start and b.[end]
    and a.demo_id <> b.demo_id