I am working with the following scenario where I have temporal data that falls into islands and gaps. Every once in a while I need to associate an event that falls within an existing gap to its nearest island based on the time of the event.
To demonstrate, let's say I've got the following data defining my time periods:
This data is contiguous except for a gap which exists between IDs
7, for the time period
2017-07-26 00:03:00 through
In order to identify the nearest island, I am currently splitting the gap into two periods as follows:
If I have an event that falls within this gap, the
End times will determine which island I need to associate the event with. So, for instance, if I have an event that occurs at
2017-07-26 00:03:20, I would associate that event with ID
2 and conversely if I had an event occur at
2017-07-26 00:05:35 I would associated that event with ID
The most efficient way I've been able to code my approach, thus far, is to assemble the gaps using Itzik Ben-Gan's 3rd solution from SQL Server MVP Deep Dives book via the
ROW_NUMBER window function and then split the gaps per a
CROSS APPLY statement which acts like a simple
Here is the db<>fiddle plan of the approach I'm using to assemble the nearest island set.
With the nearest islands identified, I use an event's event time to identify the nearest island to associate said event with. Because these islands are volatile throughout the day, I cannot make a static master table, but instead have to rely on constructing everything at run-time when the events are encountered.
Here is a db<>fiddle plan showing what NearestIsland value should be used against a random event time.
Are there any better ways to figure out the nearest island for a given event that would normally fall into a gap? For instance, is there a more efficient method to identify the gaps or a more efficient way to identify the nearest island? Am I even going about this in the best logical way? There's nothing critical about this question, but I'm always trying to figure out if there's a "better" approach to things and I think this problem lends itself to some creativity so I'd love to see other performant options.
The current environment I'm working on is SQL 2012, but we'll be migrating to a SQL 2016 environment shortly, so I'm open to pretty much anything.
Code underlying the second db<>fiddle link is as follows:
-- 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
Is the desired outcome a table containing the gaps?
Or are you attempting to assign incoming rows to the nearest neighbor?
Or are you looking to reproduce the exact output you show in your example?
In short, Yes, Yes and No. The desired outcome is to identify any (other/more) efficient way to identify the nearest island for an event time that would normally fall within a gap. I tried to expand the question to show what a desirable final outcome would be.