SQL Server - 使用聚集索引时如何存储数据页

Question

John Eisbrener

Asked: 2017-07-27 11:52:51 +0800 CST2017-07-27 11:52:51 +0800 CST 2017-07-27 11:52:51 +0800 CST

差距和岛屿 - 寻找最近的岛屿

772

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

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

2此数据是连续的，除了 ID和之间存在的间隙，7时间段为。2017-07-26 00:03:002017-07-26 00:07:00

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

如果我有一个事件落在这个间隔内，GapWindowStart/ Endtimes 将决定我需要将事件与哪个岛相关联。因此，例如，如果我有一个事件发生在2017-07-26 00:03:20，我会将该事件与 ID 相关联，2反之，如果我有一个事件发生在，2017-07-26 00:05:35我会将该事件与 ID 相关联7。

到目前为止，我能够编写我的方法的最有效方法是使用Itzik Ben-Gan通过ROW_NUMBER窗口函数从 SQL Server MVP Deep Dives 书中的第 3 个解决方案来组装间隙，然后按照执行的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

问题：（@MaxVernon）

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

回答：

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

1 个回答

Voted

Joe Obbish · Answer 1 · 2017-07-27T19:38:12+08:00

这里有很多不同的问题。当谈到生成完整的结果集（时间到 ID 的映射）时，你所拥有的就是我会做的方式，尽管我会在WindowStart其中添加一个非聚集索引 include 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;

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

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;

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

如果要求实际上是为一小部分行找到最近的岛，例如您的示例中的十个，那么可以使用索引编写更高效的代码。这里的想法是从表中的每一行中找到上一行和下一行，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);

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

这是查询计划：

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

（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 毫秒。

差距和岛屿 - 寻找最近的岛屿

连接到 PostgreSQL 服务器：致命：主机没有 pg_hba.conf 条目

如何让sqlplus的输出出现在一行中？

选择具有最大日期或最晚日期的日期

如何列出 PostgreSQL 中的所有模式？

列出指定表的所有列

如何在不修改我自己的 tnsnames.ora 的情况下使用 sqlplus 连接到位于另一台主机上的 Oracle 数据库

你如何mysqldump特定的表？

使用 psql 列出数据库权限

如何从 PostgreSQL 中的选择查询中将值插入表中？

如何使用 psql 列出所有数据库和表？

差距和岛屿 - 寻找最近的岛屿

1 个回答

相关问题