间隙和岛屿 - 寻找最近的岛屿

Question

间隙和岛屿 - 寻找最近的岛屿

Joh*_*ner 5 sql-server sql-server-2012 gaps-and-islands sql-server-2016

我正在处理以下场景，其中我的时间数据属于island 和 gaps。每隔一段时间，我需要根据事件发生的时间将落入现有间隙内的事件与其最近的岛屿相关联。

为了演示，假设我有以下定义我的时间段的数据：

这个数据是除了哪个ID之间存在间隙连续的2和7，对于所述时间段2017-07-26 00:03:00通过2017-07-26 00:07:00。

为了确定最近的岛屿，我目前将差距分为两个时期，如下所示：

如果我有一个属于这个差距的事件，GapWindowStart/End时间将决定我需要将事件与哪个岛相关联。因此，例如，如果我有一个发生在的事件2017-07-26 00:03:20，我会将该事件与 ID 相关联，2相反，如果我有一个事件发生在，2017-07-26 00:05:35我会将该事件与 ID 相关联7。

最有效的方法，我已经能够编写我的方法，迄今为止，是组装使用的空白伊茨克奔甘的从SQL Server MVP深海潜水书第3解决方案通过ROW_NUMBER窗口函数，然后每一个分裂的差距CROSS APPLY作用的语句就像一个简单的UNPIVOT操作。

这是我用来组装最近的岛屿集的方法的db<>fiddle计划。

确定最近的岛屿后，我使用事件的事件时间来确定与所述事件相关联的最近岛屿。因为这些岛屿全天都在变化，所以我无法制作静态主表，而是必须在遇到事件时在运行时构建所有内容。

这是一个db<>fiddle 计划，显示应该针对随机事件时间使用什么 NearestIsland 值。

对于通常会落入间隙的给定事件，是否有更好的方法来找出最近的岛屿？例如，是否有更有效的方法来识别间隙或更有效的方法来识别最近的岛屿？我什至以最好的逻辑方式来解决这个问题吗？这个问题没有什么重要的，但我总是试图弄清楚是否有一种“更好”的方法来解决问题，我认为这个问题有助于一些创造力，所以我很想看到其他高性能的选择。

我目前使用的环境是 SQL 2012，但我们很快就会迁移到 SQL 2016 环境，所以我几乎可以接受任何东西。

第二个 db<>fiddle 链接的代码如下：

-- Creation of Test Data
CREATE TABLE #tmp
(
      ID            INT PRIMARY KEY CLUSTERED
    , WindowStart   DATETIME2
    , WindowEnd     DATETIME2
)

-- Create contiguous data set
INSERT INTO #tmp
SELECT    ID
        , DATEADD(HOUR, ID, CAST('0001-01-01' AS DATETIME2))
        , DATEADD(HOUR, ID + 1, CAST('0001-01-01' AS DATETIME2))
FROM
(
    SELECT TOP (1500000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) AS ID
    --SELECT TOP (87591200) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) AS ID  -- Swap line with above for larger dataset
    FROM master.sys.configurations t1
    CROSS JOIN master.sys.configurations t2
    CROSS JOIN master.sys.configurations t3
    CROSS JOIN master.sys.configurations t4
    CROSS JOIN master.sys.configurations t5
) x


--DELETE 1000000 random records to create random gaps
DELETE FROM #tmp
WHERE ID IN (
    SELECT TOP 1000000 ID
    --SELECT TOP 77591200 ID -- Swap line with above for larger dataset
    FROM #tmp
    ORDER BY NEWID()
)


-- Create RandomEvent Times
CREATE TABLE #tmpEvent
(
    EventTime DATETIME2
)

INSERT INTO #tmpEvent
SELECT DATEADD(SECOND, X.RandomNum, Y.minWindowEnd) AS EventDate
FROM (VALUES (ABS(CHECKSUM(NEWID())))
           , (ABS(CHECKSUM(NEWID())))
           , (ABS(CHECKSUM(NEWID())))
           , (ABS(CHECKSUM(NEWID())))
           , (ABS(CHECKSUM(NEWID())))
           , (ABS(CHECKSUM(NEWID())))
           , (ABS(CHECKSUM(NEWID())))
           , (ABS(CHECKSUM(NEWID())))
           , (ABS(CHECKSUM(NEWID())))
           , (ABS(CHECKSUM(NEWID())))) AS X(RandomNum)
    CROSS JOIN (SELECT MIN(WindowEnd) AS minWindowEnd FROM #tmp) AS Y


SET STATISTICS XML ON
SET STATISTICS IO ON

--Desired Output Format - Best Execution I've found so far
;WITH rankIslands AS (
    SELECT    ID
            , WindowStart
            , WindowEnd
            , ROW_NUMBER() OVER (ORDER BY WindowStart) AS rnk
    FROM    #tmp
), rankGapsJoined AS (
    SELECT    t1.ID AS NearestIslandID_Lower
            , t1.WindowEnd AS GapStart_Lower
            , DATEADD(MINUTE, (DATEDIFF(MINUTE, t1.WindowEnd, t2.WindowStart) / 2), t1.WindowEnd) AS GapEnd_Lower
            , t2.ID AS NearestIslandID_Higher
            , DATEADD(MINUTE, -1 * (DATEDIFF(MINUTE, t1.WindowEnd, t2.WindowStart) / 2), t2.WindowStart) AS GapStart_Higher
            , t2.WindowStart AS GapEnd_Higher
    FROM rankIslands t1 INNER JOIN rankIslands t2
        ON t1.rnk + 1 = t2.rnk
            AND t1.WindowEnd <> t2.WindowStart
), NearestIsland AS (
    SELECT  xa.*
    FROM    rankGapsJoined t1
            CROSS APPLY ( VALUES (t1.NearestIslandID_Lower, t1.GapStart_Lower, t1.GapEnd_Lower)
                                ,(t1.NearestIslandID_Higher, t1.GapStart_Higher, t1.GapEnd_Higher) ) AS xa (NearestIslandId, GapStart, GapEnd)
)
-- Only return records that fall into the Gaps
SELECT e.EventTime, ni.*
FROM    #tmpEvent e INNER JOIN NearestIsland ni
                ON e.EventTime > ni.GapStart
                AND e.EventTime <= ni.GapEnd

SET STATISTICS XML OFF
SET STATISTICS IO OFF


DROP TABLE #tmp
DROP TABLE #tmpEvent

Run Code Online (Sandbox Code Playgroud)

问题：（@MaxVernon）

期望的结果是包含差距的表格吗？
或者您是否试图将传入的行分配给最近的邻居？
或者您是否希望重现您在示例中显示的确切输出？

回答：

简而言之，是、是和否。期望的结果是确定任何（其他/更多）有效方法来确定通常会落入间隙内的事件时间的最近岛屿。我试图扩展这个问题，以表明理想的最终结果是什么。

Answer 1

Joe*_*ish 6

这里有很多不同的问题。当涉及到生成完整的结果集（时间到 ID 的映射）时，您所拥有的就是我的方式，尽管我会在WindowStart包含WindowEnd. SQL Server 可以扫描覆盖索引，使用（或双重方法，如果您愿意）查找下一个ID和WindowStart值，如果下一个与当前.LEAD()ROW_NUMBER()WindowStartWindowEnd

我准备了与您为“大”数据集所做的相同的数据，但以不同的方式在我的机器上完成得更快：

CREATE TABLE tmp_181900
(
      ID            INT PRIMARY KEY CLUSTERED
    , WindowStart   DATETIME2
    , WindowEnd     DATETIME2
);

-- Create contiguous data set
INSERT INTO tmp_181900 WITH (TABLOCK)
SELECT    ID
        , DATEADD(HOUR, ID, CAST('0001-01-01' AS DATETIME2))
        , DATEADD(HOUR, ID + 1, CAST('0001-01-01' AS DATETIME2))
FROM
(
    SELECT TOP (87591200) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) AS ID  -- Swap line with above for larger dataset
    FROM master.sys.configurations t1
    CROSS JOIN master.sys.configurations t2
    CROSS JOIN master.sys.configurations t3
    CROSS JOIN master.sys.configurations t4
    CROSS JOIN master.sys.configurations t5
) x;

CREATE TABLE tmp
(
      ID            INT PRIMARY KEY CLUSTERED
    , WindowStart   DATETIME2
    , WindowEnd     DATETIME2
);

-- TABLESAMPLE would be faster, but I assume that you can't randomly sample at the page level
INSERT INTO tmp WITH (TABLOCK)
SELECT *
FROM tmp_181900
WHERE RIGHT(BINARY_CHECKSUM(ID, NEWID()), 3) < 115; -- keep 11.5% of rows

DROP TABLE tmp_181900;

Run Code Online (Sandbox Code Playgroud)

以下代码实现了我描述的算法：

SELECT t2.*
FROM
(
    SELECT 
      ID
    , WindowStart
    , WindowEnd
    , LEAD(ID) OVER (ORDER BY WindowStart) Next_Id
    , LEAD(WindowStart) OVER (ORDER BY WindowStart) Next_WindowStart
    FROM tmp
) t
CROSS APPLY (
    SELECT DATEADD(MINUTE, 0.5 * DATEDIFF(MINUTE, WindowEnd, Next_WindowStart), WindowEnd)
) ca (midpoint_time)
CROSS APPLY (
    SELECT ID, WindowEnd, ca.midpoint_time
    UNION ALL
    SELECT Next_ID, ca.midpoint_time, Next_WindowStart
) t2 (NearestIslandId, GapStart, GapEnd)
WHERE t.WindowStart <> t.Next_WindowStart
    AND t2.GapStart <> t2.GapEnd;

Run Code Online (Sandbox Code Playgroud)

这有一个不错的、干净的计划，无需排序，其性能与您所拥有的类似：

如果要求实际上是为一小部分行（例如示例中的 10 个）找到最近的岛，则可以使用索引编写更高效的代码。这里的想法是从表中为每一行找到前一行和下一行，tmpEvent并做一些数学运算来找到最接近的一行。如果有N行，tmpEvent则此代码最多执行 2 * 次N索引查找。它是如此之快，STATISTICS TIME无法检测到任何东西：

（10 行受影响）

SQL Server 执行时间：CPU 时间 = 0 毫秒，已用时间 = 0 毫秒。

这是我使用的代码，我认为它非常符合您的逻辑。我评论了每一件作品：

SELECT e.EventTime
, CASE WHEN ca2.use_previous = 1 THEN previous_event.ID ELSE later_event.ID END NEAREST_ID
, CASE WHEN ca2.use_previous = 1 THEN previous_event.WindowStart ELSE later_event.WindowStart END NEAREST_WindowStart
, CASE WHEN ca2.use_previous = 1 THEN previous_event.WindowEnd ELSE later_event.WindowEnd END NEAREST_WindowEnd
FROM tmpEvent e
OUTER APPLY ( -- find the previous island, including exact matches
    SELECT TOP 1 t.ID, t.WindowStart, t.WindowEnd
    FROM tmp t
    WHERE t.WindowStart < e.EventTime
    ORDER BY t.WindowStart DESC
) previous_event 
OUTER APPLY ( -- find the next island
    SELECT TOP 1 t.ID, t.WindowStart, t.WindowEnd
    FROM tmp t
    WHERE previous_event.WindowEnd < e.EventTime -- only do this seek if not an exact match
    AND t.WindowStart >= e.EventTime
    ORDER BY t.WindowStart ASC
) later_event
CROSS APPLY ( -- calculate differences between times so we can reuse them
    SELECT DATEDIFF_BIG(SECOND, previous_event.WindowEnd, e.EventTime) DIFF_S_TO_PREVIOUS
    , DATEDIFF_BIG(SECOND, e.EventTime, later_event.WindowStart) DIFF_S_TO_NEXT
) ca
CROSS APPLY ( -- figure out if the previous event is the closest
    SELECT CASE WHEN 
        ca.DIFF_S_TO_PREVIOUS <= 0 -- the event matches exactly
        OR ca.DIFF_S_TO_NEXT IS NULL -- no ending event
        OR ca.DIFF_S_TO_PREVIOUS < ca.DIFF_S_TO_NEXT -- previous is closer than later
    THEN 1
    ELSE 0
    END
) ca2 (use_previous);

Run Code Online (Sandbox Code Playgroud)

这是结果集，它对您来说会有所不同，因为我们正在生成随机数据：

这是查询计划：

作为另一个测试，我在tmpEvent表中放置了 10k 行，甚至将它们返回给客户端。在我的系统上这很好，但当然你会看到不同的性能：

（10000 行受影响）

表'tmp'。扫描计数 18864，逻辑读取 60419，物理读取 0，预读读取 0，lob 逻辑读取 0，lob 物理读取 0，lob 预读读取 0。表 'tmpEvent'。扫描计数 1，逻辑读取 22，物理读取 0，预读读取 0，lob 逻辑读取 0，lob 物理读取 0，lob 预读读取 0。

SQL Server 执行时间：

CPU 时间 = 47 毫秒，已用时间 = 131 毫秒。

归档时间：	8 年，11 月前
查看次数：	818 次
最近记录：	8 年，11 月前