Sql-server – Gaps and Islands – Finding the Nearest Island

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 2 and 7, for the time period 2017-07-26 00:03:00 through 2017-07-26 00:07:00.

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 GapWindowStart/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 7.

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 UNPIVOT operation.

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

Questions: (@MaxVernon)

• 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?

Answer:

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.