Início / dba / Perguntas / 102064
Accepted
jpmc26
Asked: 2015-05-21 08:34:46 +0800 CST

Como faço para encontrar lacunas entre intervalos de números?

  • 772

Considere a seguinte tabela:

T_ID | T_START | T_END
-----+---------+------
   1 | 0.25    | 0.5
   2 | 0.8     | 1
   3 | 0.4     | 0.6
   4 | 0.2     | 0.3
   5 | 0.7     | 0.8

T_IDé único. Cada linha representa um intervalo contínuo de números e é um subconjunto de 0 a 1. T_STARTé menor que T_END.

Preciso identificar quaisquer intervalos não incluídos entre 0 e 1. Observe que alguns intervalos se sobrepõem. A exclusividade dos endpoints não é relevante para meu caso de uso; Eu só preciso identificar quais são os pontos finais das lacunas. (Como tal, lacunas de ponto único não são consideradas.)

Para este conjunto de dados específico, eu esperaria que o resultado fosse

GAP_START | GAP_END
----------+--------
0         | 0.2
0.6       | 0.7

O conjunto de dados real é grande e será agregado sobre alguns outros dados (centenas de milhares de linhas, com possivelmente 100 linhas por grupo agregado), portanto, o desempenho é importante. (Respostas que não têm bom desempenho, mas podem ser melhoradas, são bem-vindas.)

Considerei tentar primeiro determinar quais são os intervalos cobertos e, em seguida, tentar reverter isso, mas não consegui descobrir como calcular os intervalos cobertos. Um simples GROUP BYé insuficiente, pois temos cadeias de intervalos sobrepostos que seriam mesclados em um único intervalo, embora nem todos os intervalos se sobreponham. Acredito que uma consulta recursiva pode ser útil, mas ainda não consegui descobrir a lógica para isso.

Eu criei um SQLFiddle com este conjunto de dados de exemplo .

Infelizmente (e improdutivamente), não tenho liberdade para modificar a representação subjacente.

oracle oracle-11g-r2

1 respostas

  1. Best Answer

    Depois de uma boa pesquisa, encontrei esta postagem no blog sobre como fazer isso para intervalos de datas e funciona igualmente bem em intervalos numéricos, com uma pequena modificação para lidar com os pontos finais 0 e 1.

    Pegando a consulta a partir daí e renomeando as colunas para ficar um pouco mais claro, temos

    SELECT * FROM
  (SELECT MAX(T_END) OVER (ORDER BY T_START) GAP_START,
          LEAD(T_START) OVER (ORDER BY T_START) GAP_END
   FROM T)
WHERE GAP_START < GAP_END

    Isso merece um pouco de explicação. Passo a passo:

    1. Para cada linha, ele obtém o máximo T_ENDde todas as linhas em que T_STARTé menor ou igual ao da linha atual T_START. Isso nos dá o maior final de intervalo de todos os intervalos que se sobrepõem ao início do intervalo desta linha.
    2. Para cada linha, obtém o T_STARTda primeira linha onde o T_STARTé maior que a linha atual. Isso nos dá o próximo maior intervalo inicial.
    3. Ele filtra todas as linhas em que o máximo T_ENDé maior ou igual ao seguinte T_START. Isso significa que o maior final de intervalo de sobreposição se estende até ou além do próximo início de intervalo. Em outras palavras, não há lacuna entre esta linha e a próxima, porque esta linha termina onde começa a próxima ou porque outras linhas sobrepostas cobrem todos os pontos entre as duas.

    No entanto, isso não atende totalmente ao requisito de todas as lacunas no intervalo de 0 a 1. Ele seleciona apenas as lacunas entre o início do intervalo mínimo e o final do intervalo máximo de todas as linhas. Para verificar se há lacunas nas extremidades do intervalo 0 e 1, podemos usar as seguintes consultas.

    Para lacunas começando em 0:

    SELECT 0 AS GAP_START, MIN(T_START) AS GAP_END
FROM T
HAVING MIN(T_START) > 0

    Para lacunas terminando em 1:

    SELECT MAX(T_END) AS GAP_START, 1 AS GAP_END
FROM T
HAVING MAX(T_END) < 1

    Ambas as consultas não retornarão nenhuma linha se não houver lacuna no ponto de extremidade.

    Juntando tudo em uma única consulta:

    SELECT * FROM
  (SELECT MAX(T_END) OVER (ORDER BY T_START) GAP_START,
          LEAD(T_START) OVER (ORDER BY T_START) GAP_END
   FROM T)
WHERE GAP_START < GAP_END
UNION ALL
SELECT 0 AS GAP_START, MIN(T_START) AS GAP_END
FROM T
HAVING MIN(T_START) > 0
UNION ALL
SELECT MAX(T_END) AS GAP_START, 1 AS GAP_END
FROM T
HAVING MAX(T_END) < 1

    O resultado é exatamente o indicado na pergunta, ignorando a ordem. SQLFiddle da consulta .

    • 5

relate perguntas