从起始范围选择所有重叠范围

Question

我的问题与这个问题类似，但（我认为）有足够大的差异。我有一个基本范围，我想在一个表中找到所有其他范围与它和彼此冲突。或者更确切地说是形成范围的项目，但它并没有真正产生影响。

带星号的那一行是起始范围。范围 1,2 和 3 是应该扩展它的范围。结果范围应该是 X。

1 | 
3 |    ===1====            ====
5 | ==2==    ====*====           ====
6 |             ====3====     =====          
--+-------------------------------------
  | |<--------X-------->|

我写过这个：

WITH   cte
AS (
    SELECT DATA1.ID, DATA1.STARTDATE, DATA1.ENDDATE
    FROM DATA1
    WHERE 
    DATA1.ID = @PARID AND 
    DATA1.STARTDATE > @STARTDATE AND 
    DATA1.ENDDATE < @ENDDATE 

    UNION ALL

    SELECT DATA1.ID, DATA1.STARTDATE, DATA1.ENDDATE
    FROM cte 
    INNER JOIN DATA1 ON (DATA1.ID = cte.ID)
    WHERE 
    DATA1.ID = @PARID AND 
    (cte.STARTDATE < DATA1.ENDDATE AND cte.ENDDATE > DATA1.ENDDATE)
)
SELECT *
FROM cte

但经过一番摆弄意识到了这一点并不能真正工作，因为第二个SELECT不知道是什么STARTDATE以及ENDDATE它应该从使用cte。而且我不能在递归 SQL 中使用子查询。

我们之前已经通过一组递归函数在 .NET 的客户端中计算过这个，但是在 O(N^2) 上它非常慢。此处的目的是将计算移至服务器并优化计算。

我在这里尝试做的事情完全可行吗？

---

SQL小提琴。我在让查询像在我的机器上一样运行时遇到了一些麻烦（我使用了不太简单的数据结构），但至少我添加了示例数据。我会继续努力让它产生与我在我的机器上得到的结果相同的结果。

输入范围从2018-08-24 12:00:00到2018-08-31 12:00:00，正确的输出应该是 IDs 2, 3, 4, 6。

Answer 1

一个简单的递归解决方案将任务分为两部分：

\n\n

\n
1. 通过遵循重叠范围链查找最早的开始日期
\n
2. 通过遵循重叠范围链查找最新结束日期
\n

\n\n

详情如下：

\n\n

1. 遵循导致最早开始日期的重叠链

\n\n

\n
1. 找到起始范围
\n
2. 查找最近开始日期早于当前日期的重叠范围
\n
3. 转到步骤 2
\n

\n\n

示例代码：

\n\n

DECLARE @STARTDATE DATETIME = \'2018-08-24 12:00:00\';\nDECLARE @ENDDATE DATETIME = \'2018-08-31 12:00:00\';\n\nWITH MinStart AS\n(\n    -- Starting range\n    SELECT TOP (1) \n        D.ID,\n        D.STARTDATE\n    FROM dbo.DATA1 AS D\n    WHERE \n        D.STARTDATE >= @STARTDATE\n        AND D.ENDDATE <= @ENDDATE\n    ORDER BY \n        D.ID ASC\n\n    UNION ALL\n\n    SELECT\n        P1.ID,\n        P1.STARTDATE\n    FROM \n    (\n        -- Overlapping ranges with an earlier start date\n        -- Numbered starting with the highest start date\n        -- Tie-break dates using ID\n        SELECT\n            RN = ROW_NUMBER() OVER (\n                ORDER BY D.STARTDATE DESC, D.ID ASC),\n            D.ID,\n            D.STARTDATE\n        FROM MinStart AS R\n        JOIN dbo.DATA1 AS D\n            ON D.ENDDATE >= R.STARTDATE\n            AND D.STARTDATE < R.STARTDATE\n    ) AS P1\n    WHERE\n        -- Highest start date only\n        P1.RN = 1\n)\nSELECT\n    MS.ID,\n    MS.STARTDATE\nFROM MinStart AS MS\nOPTION (MAXRECURSION 0);\n

\n\n

2. 遵循导致最近结束日期的重叠链

\n\n

\n
1. 找到起始范围
\n
2. 查找结束日期最早晚于当前日期的重叠范围
\n
3. 转到步骤 2
\n

\n\n

示例代码：

\n\n

DECLARE @STARTDATE DATETIME = \'2018-08-24 12:00:00\';\nDECLARE @ENDDATE DATETIME = \'2018-08-31 12:00:00\';\n\nWITH MaxEnd AS\n(\n    -- Starting range\n    SELECT TOP (1) \n        D.ID, \n        D.ENDDATE\n    FROM dbo.DATA1 AS D\n    WHERE\n        D.STARTDATE >= @STARTDATE\n        AND D.ENDDATE <= @ENDDATE\n    ORDER BY \n        D.ID ASC\n\n    UNION ALL\n\n    SELECT\n        P1.ID,\n        P1.ENDDATE\n    FROM \n    (\n        -- Overlapping ranges with a later end date\n        -- Numbered starting with the lowest end date\n        -- Tie-break dates using ID\n        SELECT\n            RN = ROW_NUMBER() OVER (\n                ORDER BY D.ENDDATE ASC, D.ID ASC),\n            D.ID,\n            D.ENDDATE\n        FROM MaxEnd AS R\n        JOIN dbo.DATA1 AS D\n            ON D.ENDDATE > R.ENDDATE\n            AND D.STARTDATE < R.ENDDATE\n    ) AS P1\n    WHERE \n        -- Lowest end date only\n        P1.RN = 1\n)\nSELECT\n    ME.ID,\n    ME.ENDDATE\nFROM MaxEnd AS ME\nOPTION (MAXRECURSION 0);\n

\n\n

通过适当的索引，两个查询都使用如下执行计划：

\n\n

\n\n

给出的样本数据的结果是：

\n\n

\n\xe2\x95\x94\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\xa6\xe2\x95\x90\xe2\x95\x90 \xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2 \x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95 \x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x97\n\xe2\x95 \x91 ID \xe2\x95\x91 开始日期 \xe2\x95\x91\n\xe2\x95\xa0\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2 \x95\xac\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95 \x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90 \xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2 \x95\x90\xe2\x95\xa3\n\xe2\x95\x91 3 \xe2\x95\x91 2018-08-24 12:00:00.000 \xe2\x95\x91\n\xe2\x95\x91 6 \xe2\x95\x91 2018-08-23 12:00:00.000 \xe2\x95\x91\n\xe2\x95\x91 2 \xe2\x95\x91 2018-08-22 12:00:00.000 \xe2\ x95\x91\n\xe2\x95\x9a\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\xa9\xe2\x95\x90\xe2\ x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\ x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\ xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x9d\n\ xe2\x95\x94\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\xa6\xe2\x95\x90\xe2\x95\x90\xe2\ x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\ x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\ xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x97\n\xe2\x95\x91 ID \xe2\x95\x91 结束日期 \xe2\x95\x91\n\xe2\x95\xa0\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\ xac\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\ xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\ x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\ x90\xe2\x95\xa3\n\xe2\x95\x91 3 \xe2\x95\x91 2018-08-29 12:00:00.000 \xe2\x95\x91\n\xe2\x95\x91 6 \xe2\ x95\x91 2018-08-30 12:00:00.000 \xe2\x95\x91\n\xe2\x95\x91 4 \xe2\x95\x91 2018-09-02 12:00:00.000 \xe2\x95\x91 \n\xe2\x95\x9a\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\xa9\xe2\x95\x90\xe2\x95\x90 \xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2 \x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95 \x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x90\xe2\x95\x9d\n

\n\n

因此使用了 ID 2、3、4 和 6。最终范围是2018-08-22 12:00:00.000（找到的最低开始日期）到2018-09-02 12:00:00.000（找到的最高结束日期）。

\n\n

ID注意：由于示例数据中存在重复项，上面的代码包含日期上的平局（使用列）。这可能是解决实际问题所必需的，也可能不是。

\n\n

使用的索引是：

\n\n

CREATE TABLE dbo.DATA1\n(\n  ID integer PRIMARY KEY,\n  STARTDATE datetime NOT NULL,\n  ENDDATE datetime NOT NULL,\n);\n\nCREATE UNIQUE INDEX i1 ON dbo.DATA1 (STARTDATE DESC, ID ASC) INCLUDE (ENDDATE);\nCREATE UNIQUE INDEX i2 ON dbo.DATA1 (ENDDATE ASC, ID DESC) INCLUDE (STARTDATE);\n

\n\n

演示： db<>fiddle

\n\n

请注意，为这些类型的查询建立真正的最佳索引可能很困难。即便如此，上述方法对于该领域的许多实际任务通常表现良好。

\n\n

在 SQL Server 中添加对间隔查询和谓词的适当支持之前，更高性能的解决方案需要大量的额外工作。看：

\n\n

\n
• SQL Server 中的间隔查询第 4 部分作者：Dejan Sarka
\n
• SQL Server 中的间隔查询作者：Itzik Ben-Gan
\n

\n