在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。 感谢任何更有效的解决方案。

- Laoneo

---

在起始/结束列中添加索引。 - bobince

我认为你应该使用A.DEMO_ID < B.DEMO_ID，而不是A.DEMO_ID != B.DEMO_ID（如果A与B重叠，那么B也会与A重叠）。 - Thierry

Answer 1

你可以稍微重写一下查询语句：

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关键字可能会使事情更便宜，因为当使用DISTINCT *时，Sql Server将对返回的列（即所有列）进行排序以消除重复项。

您还应该考虑添加索引。在Sql Server 2008中，我建议在START、END和包含DEMO_ID的列上创建一个索引。

- Sean Reilly

---

这里有一个资源，提供了有关在查询分析器中调整索引的信息：http://msdn.microsoft.com/en-us/library/aa216973%28SQL.80%29.aspx - Sean Reilly

DEMO_ID已经是唯一的事实，并不会阻止它在与另一个表连接后被多次返回。 - Tom H

True -- 我编辑了查询以使事情更清晰：每个 a.DEMO_ID、b.DEMO_ID 的组合可能会出现两次（如果 A 完全在 B 中）。虽然在这种情况下，ID 将以不同的顺序显示，因此 DISTINCT 无论如何都无法正确地删除重复项。 - Sean Reilly

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

你需要进行度量以确保这是更快的。在任何情况下，我们不会将所有记录的日期字段与所有其他记录进行比较，因此对于大型数据集来说，这可能会更快。

- marapet

---

你的解决方案非常有趣，但问题在于当u.position处的行与位置-1不重叠，而是与位置-2重叠时...该行未被返回。因此结果可能不正确。 - Laoneo

Answer 3

这个更简单，对于超过20000条记录的执行时间约为2秒

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)

- josephj1989

---

为什么NOT不存在？我选择了： select * from demo a where exists( select 1 from demo b where a.demo_id<>b.demo_id AND A.S < B.E AND B.S < A.E) - Laoneo

Answer 4

回答晚了，但不知道这是否有帮助：

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

- Zielyn