Поиск эффективных перекрывающихся записей в таблице SQL

Question

Какой самый эффективный способ найти все записи, которые пересекаются с другими в одной таблице? Каждая запись имеет дату начала и окончания. Например, у меня есть следующие настройки базы данных:

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');

Мой запрос выглядит следующим образом:

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

Проблема в том, что когда в моей демонстрационной таблице есть, например, 20 000 строк, запрос занимает слишком много времени. Моя среда MS SQL Server 2008. Спасибо за более эффективное решение

Answer 1

Поздний ответ, но интересно, поможет ли это:

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

Answer 2

Использовать функцию или хранимую процедуру:

Сначала Порядок Записи по началу и окончанию

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

Затем проверьте наложения с предыдущая и следующая запись:

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

Вам нужно измерить , чтобы убедиться, что это быстрее. В любом случае мы не будем сравнивать поля даты всех записей со всеми остальными записями, поэтому это может быть быстрее для больших наборов данных.

Answer 3

Это проще и выполняется за 2 секунды для более чем 20000 записей

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 4

Вы можете переписать запрос немного:

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

Избавление от ключевого слова DISTINCT может сделать вещи дешевле, потому что Sql Server будет выполнять сортировку по возвращаемому столбцу (и все они при использовании DISTINCT *) для устранения дубликатов.

Вам также следует рассмотреть возможность добавления индекса. В Sql Server 2008 я бы рекомендовал индекс START, END, содержащий DEMO_ID.