Sql-Server

差距和島嶼 - 尋找最近的島嶼

  • July 27, 2017

我正在處理以下場景，其中我的時間數據屬於孤島和間隙。每隔一段時間，我需要根據事件發生的時間將一個位於現有間隙內的事件與其最近的島嶼相關聯。

為了展示，假設我有以下數據定義我的時間段：

在此處輸入圖像描述

2該數據是連續的，除了 ID和之間存在的間隙外，在的7時間段內。2017-07-26 00:03:00``2017-07-26 00:07:00

為了確定最近的島嶼，我目前將差距分為兩個時期，如下所示：

在此處輸入圖像描述

如果我有一個事件落在此間隙內，GapWindowStart/ Endtimes 將確定我需要將事件與哪個島關聯。因此，例如，如果我有一個發生在的事件2017-07-26 00:03:20，我會將該事件與 ID 相關聯，2反之，如果我有一個事件發生在，2017-07-26 00:05:35我會將該事件與 ID 相關聯7。

到目前為止，我能夠編寫方法的最有效方法是使用SQL Server MVP Deep Dives 書中 Itzik Ben-Gan 的第 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 &lt;&gt; 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 &gt; ni.GapStart
               AND e.EventTime &lt;= ni.GapEnd

SET STATISTICS XML OFF
SET STATISTICS IO OFF


DROP TABLE #tmp
DROP TABLE #tmpEvent

問題：（@MaxVernon）

  • 期望的結果是包含差距的表格嗎？
  • 或者您是否嘗試將傳入的行分配給最近的鄰居？
  • 或者您是否希望重現您在範例中顯示的確切輸出？

回答：

簡而言之，是、是和否。期望的結果是確定任何（其他/更）有效的方法來確定通常落在間隙內的事件時間的最近島嶼。我試圖擴展這個問題，以表明理想的最終結果是什麼。

這裡有很多不同的問題。在生成完整結果集（時間到 ID 的映射）時，您所擁有的就是我會這樣做的方式，儘管我會在WindowStart其中添加一個非聚集索引WindowEnd。SQL Server 可以掃描覆蓋索引，查找下一個ID和WindowStart值使用LEAD()（或者如果您願意，可以使用雙重方法），如果下一個與目前不匹配，ROW_NUMBER()則使用時間之間的中間點添加兩行。WindowStart``WindowEnd

我準備了與您為“大”數據集所做的數據相同的數據，但採用了不同的方式，因此它可以在我的機器上更快地完成：

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) &lt; 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 &lt;&gt; t.Next_WindowStart
   AND t2.GapStart &lt;&gt; t2.GapEnd;

這有一個不錯的、乾淨的計劃，沒有排序，其性能與您所擁有的類似：

所有行的 DOP 1 計劃

如果要求實際上是為一小部分行（例如您的範例中的十行）找到最近的島，那麼可以使用索引編寫更高效的程式碼。這裡的想法是從表中為每一行找到上一行和下一行，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 &lt; 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 &lt; e.EventTime -- only do this seek if not an exact match
   AND t.WindowStart &gt;= 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 &lt;= 0 -- the event matches exactly
       OR ca.DIFF_S_TO_NEXT IS NULL -- no ending event
       OR ca.DIFF_S_TO_PREVIOUS &lt; 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 毫秒。

引用自：https://dba.stackexchange.com/questions/181900

相關問答

Sql-Server

查詢以查找指定日期之間的活動天數（狀態 = ON 的天數）

  • June 25, 2022
檢視問答
Sql-Server

關於 ISDATE 函式和 DATENAME 函式的問題

  • July 2, 2021
檢視問答
Sql-Server

兩台伺服器和從伺服器之間同步數據庫的解決方案可用於所有 DML 操作

  • June 14, 2021
檢視問答
Sql-Server

無法從連結伺服器的 OLE DB 提供程序“SQLNCLI11”獲取行

  • February 15, 2021
檢視問答
Sql-Server

將數據庫從生產環境複製到開發環境的最佳方法是什麼？

  • December 20, 2020
檢視問答
Sql-Server

授予 AD 組編輯所有 MSSQL 代理作業的權限

  • July 25, 2020
檢視問答