Início / dba / Perguntas / 181900
Accepted
John Eisbrener
Asked: 2017-07-27 11:52:51 +0800 CST

Gaps and Islands - Encontrando a ilha mais próxima

  • 772

Estou trabalhando com o seguinte cenário onde tenho dados temporais que se enquadram em ilhas e lacunas . De vez em quando, preciso associar um evento que esteja dentro de uma lacuna existente à ilha mais próxima com base no horário do evento.

Para demonstrar, digamos que eu tenha os seguintes dados definindo meus períodos de tempo:

insira a descrição da imagem aqui

Esses dados são contíguos, exceto por uma lacuna que existe entre os IDs 2e 7, para o período de tempo 2017-07-26 00:03:00até 2017-07-26 00:07:00.

Para identificar a ilha mais próxima, atualmente estou dividindo a lacuna em dois períodos da seguinte forma:

insira a descrição da imagem aqui

Se eu tiver um evento que se enquadre nessa lacuna, os GapWindowStart/ Endtimes determinarão com qual ilha eu preciso associar o evento. Então, por exemplo, se eu tivesse um evento que ocorresse em 2017-07-26 00:03:20, eu associaria esse evento a ID 2e, inversamente, se eu tivesse um evento ocorrendo em 2017-07-26 00:05:35eu associaria esse evento a ID 7.

A maneira mais eficiente que consegui codificar minha abordagem, até agora, é montar as lacunas usando a 3ª solução de Itzik Ben-Gan do livro SQL Server MVP Deep Dives por meio da ROW_NUMBERfunção window e, em seguida, dividir as lacunas por uma CROSS APPLYinstrução que atua como uma operação simples UNPIVOT.

Aqui está o plano db<>fiddle da abordagem que estou usando para montar o conjunto de ilhas mais próximo.

Com as ilhas mais próximas identificadas, uso o tempo de evento de um evento para identificar a ilha mais próxima à qual associar esse evento. Como essas ilhas são voláteis ao longo do dia, não posso criar uma tabela mestre estática, mas preciso confiar na construção de tudo em tempo de execução quando os eventos são encontrados.

Aqui está um plano db<>fiddle mostrando qual valor NearestIsland deve ser usado em um evento aleatório.

Existem maneiras melhores de descobrir a ilha mais próxima para um determinado evento que normalmente cairia em uma lacuna? Por exemplo, existe um método mais eficiente para identificar as lacunas ou uma maneira mais eficiente de identificar a ilha mais próxima? Será que estou fazendo isso da melhor maneira lógica? Não há nada crítico sobre essa questão, mas estou sempre tentando descobrir se há uma abordagem "melhor" para as coisas e acho que esse problema se presta a alguma criatividade, então adoraria ver outras opções de desempenho.

O ambiente atual em que estou trabalhando é o SQL 2012, mas estaremos migrando para um ambiente SQL 2016 em breve, então estou aberto a praticamente qualquer coisa.

O código subjacente ao segundo link db<>fiddle é o seguinte:

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

Perguntas: (@MaxVernon)

  • O resultado desejado é uma tabela contendo as lacunas?

  • Ou você está tentando atribuir linhas de entrada ao vizinho mais próximo?

  • Ou você está procurando reproduzir a saída exata que você mostra no seu exemplo?

Responda:

Resumindo, sim, sim e não. O resultado desejado é identificar qualquer forma (outra/mais) eficiente de identificar a ilha mais próxima para um tempo de evento que normalmente cairia dentro de um intervalo. Tentei expandir a questão para mostrar qual seria um resultado final desejável.

sql-server sql-server-2012

1 respostas

  1. Best Answer

    Há muitas perguntas diferentes aqui. Quando se trata de gerar o conjunto de resultados completo (o mapeamento de tempos para IDs), o que você tem é a maneira que eu faria, embora eu adicione um índice não clusterizado WindowStartque inclua WindowEnd. O SQL Server pode varrer o índice de cobertura, encontrar o próximo IDe os WindowStartvalores usando LEAD()(ou a abordagem dupla ROW_NUMBER(), se você preferir) e adicionar duas linhas usando o ponto intermediário entre os tempos, se o próximo WindowStartnão corresponder ao WindowEnd.

    Eu preparei os mesmos dados que você fez para o seu "grande" conjunto de dados, mas de uma maneira diferente para terminar mais rápido na minha máquina:

    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;

    O código a seguir implementa o algoritmo que descrevi:

    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;

    Isso tem um plano bom e limpo, sem classificação, que funciona de maneira semelhante ao que você tem:

    Plano DOP 1 para todas as linhas

    Se o requisito for realmente encontrar a ilha mais próxima para um pequeno subconjunto de linhas, como dez em seu exemplo, é possível escrever um código muito mais eficiente usando o índice. A ideia aqui é encontrar a linha anterior e a próxima da tabela para cada linha tmpEvente fazer um pouco de matemática para encontrar a mais próxima. Se houver Nlinhas tmpEvent, esse código fará no máximo 2 * Nbuscas de índice. É tão rápido que STATISTICS TIMEnão consegue detectar nada:

    (10 linhas afetadas)

    Tempos de execução do SQL Server: tempo de CPU = 0 ms, tempo decorrido = 0 ms.

    Aqui está o código que usei, que acho que corresponde muito bem à sua lógica. Comentei cada peça:

    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);

    Aqui está o conjunto de resultados, que será diferente para você porque estamos gerando dados aleatórios:

    insira a descrição da imagem aqui

    E aqui está o plano de consulta:

    insira a descrição da imagem aqui

    Como outro teste coloquei 10k linhas na tmpEventtabela e até as devolvi ao cliente. No meu sistema, tudo bem, mas é claro que você pode ver um desempenho diferente:

    (10.000 linhas afetadas)

    Tabela 'tmp'. Contagem de varredura 18864, leituras lógicas 60419, leituras físicas 0, leituras antecipadas 0, leituras lógicas lob 0, leituras físicas lob 0, leituras antecipadas lob 0. Tabela 'tmpEvent'. Contagem de varredura 1, leituras lógicas 22, leituras físicas 0, leituras antecipadas 0, leituras lógicas lob 0, leituras físicas lob 0, leituras antecipadas lob 0.

    Tempos de execução do SQL Server:

    Tempo de CPU = 47 ms, tempo decorrido = 131 ms.

    • 6

relate perguntas