Combinando intervalos separados nos maiores intervalos contíguos possíveis

Estou tentando combinar vários períodos (minha carga é de aproximadamente 500, na maioria dos casos 10) que podem ou não se sobrepor aos maiores períodos possíveis contíguos. Por exemplo:

Dados:

CREATE TABLE test (
  id SERIAL PRIMARY KEY NOT NULL,
  range DATERANGE
);

INSERT INTO test (range) VALUES 
  (DATERANGE('2015-01-01', '2015-01-05')),
  (DATERANGE('2015-01-01', '2015-01-03')),
  (DATERANGE('2015-01-03', '2015-01-06')),
  (DATERANGE('2015-01-07', '2015-01-09')),
  (DATERANGE('2015-01-08', '2015-01-09')),
  (DATERANGE('2015-01-12', NULL)),
  (DATERANGE('2015-01-10', '2015-01-12')),
  (DATERANGE('2015-01-10', '2015-01-12'));

A tabela se parece com:

 id |          range
----+-------------------------
  1 | [2015-01-01,2015-01-05)
  2 | [2015-01-01,2015-01-03)
  3 | [2015-01-03,2015-01-06)
  4 | [2015-01-07,2015-01-09)
  5 | [2015-01-08,2015-01-09)
  6 | [2015-01-12,)
  7 | [2015-01-10,2015-01-12)
  8 | [2015-01-10,2015-01-12)
(8 rows)

Resultados desejados:

         combined
--------------------------
 [2015-01-01, 2015-01-06)
 [2015-01-07, 2015-01-09)
 [2015-01-10, )

Representação visual:

1 | =====
2 | ===
3 |    ===
4 |        ==
5 |         =
6 |             =============>
7 |           ==
8 |           ==
--+---------------------------
  | ====== == ===============>

Pressupostos / Esclarecimentos

1. Não é necessário diferenciar entre infinitye abrir o limite superior ( upper(range) IS NULL). (Você pode escolher de qualquer maneira, mas é mais simples assim.)

   • NULL vs. infinitynos tipos de intervalo do PostgreSQL

2. Como dateé um tipo discreto, todos os intervalos têm [)limites padrão . Por documentação:

   O embutido tipos de intervalo int4range, int8rangee daterangetodo o uso de uma forma canónica que inclui o limite inferior e o limite superior exclui; isto é, [).

   Para outros tipos (como tsrange!) Eu aplicaria o mesmo, se possível:

   • Impedindo entradas adjacentes / sobrepostas com EXCLUDE no PostgreSQL

Solução com SQL puro

Com CTEs para maior clareza:

WITH a AS (
   SELECT range
        , COALESCE(lower(range),'-infinity') AS startdate
        , max(COALESCE(upper(range), 'infinity')) OVER (ORDER BY range) AS enddate
   FROM   test
   )
, b AS (
   SELECT *, lag(enddate) OVER (ORDER BY range) < startdate OR NULL AS step
   FROM   a
   )
, c AS (
   SELECT *, count(step) OVER (ORDER BY range) AS grp
   FROM   b
   )
SELECT daterange(min(startdate), max(enddate)) AS range
FROM   c
GROUP  BY grp
ORDER  BY 1;

Ou , o mesmo com subconsultas, mais rápido, mas menos fácil, também leia:

SELECT daterange(min(startdate), max(enddate)) AS range
FROM  (
   SELECT *, count(step) OVER (ORDER BY range) AS grp
   FROM  (
      SELECT *, lag(enddate) OVER (ORDER BY range) < startdate OR NULL AS step
      FROM  (
         SELECT range
              , COALESCE(lower(range),'-infinity') AS startdate
              , max(COALESCE(upper(range), 'infinity')) OVER (ORDER BY range) AS enddate
         FROM   test
         ) a
      ) b
   ) c
GROUP  BY grp
ORDER  BY 1;

Ou com menos um nível de subconsulta, mas invertendo a ordem de classificação:

SELECT daterange(min(COALESCE(lower(range), '-infinity')), max(enddate)) AS range
FROM  (
   SELECT *, count(nextstart > enddate OR NULL) OVER (ORDER BY range DESC NULLS LAST) AS grp
   FROM  (
      SELECT range
           , max(COALESCE(upper(range), 'infinity')) OVER (ORDER BY range) AS enddate
           , lead(lower(range)) OVER (ORDER BY range) As nextstart
      FROM   test
      ) a
   ) b
GROUP  BY grp
ORDER  BY 1;

• Classifique a janela na segunda etapa com ORDER BY range DESC NULLS LAST(com NULLS LAST) para obter a ordem de classificação perfeitamente invertida. Isso deve ser mais barato (mais fácil de produzir, corresponde perfeitamente à ordem de classificação do índice sugerido) e preciso para os casos de canto rank IS NULL.
  • Classificação do PostgreSQL por data e hora asc, null primeiro?

Explicar

a: Ao fazer o pedido range, calcule o máximo em execução do limite superior ( enddate) com uma função de janela.
Substitua limites NULL (sem limites) por +/- infinityapenas para simplificar (sem casos NULL especiais).

b: Na mesma ordem de classificação, se o anterior enddatefor anterior startdate, temos uma lacuna e iniciaremos um novo intervalo ( step).
_{Lembre-se, o limite superior é sempre excluído.}

c: Forme grupos ( grp) contando as etapas com outra função da janela.

Na SELECTconstrução externa varia do limite inferior ao superior em cada grupo. Voilá.
Resposta intimamente relacionada ao SO, com mais explicações:

• Compare vários períodos

Solução processual com plpgsql

Funciona para qualquer nome de tabela / coluna, mas apenas para o tipo daterange.
As soluções procedurais com loops são tipicamente mais lentas, mas neste caso especial, espero que a função seja substancialmente mais rápida, pois precisa apenas de uma única varredura seqüencial :

CREATE OR REPLACE FUNCTION f_range_agg(_tbl text, _col text)
  RETURNS SETOF daterange AS
$func$
DECLARE
   _lower     date;
   _upper     date;
   _enddate   date;
   _startdate date;
BEGIN
   FOR _lower, _upper IN EXECUTE
      format($$SELECT COALESCE(lower(t.%2$I),'-infinity')  -- replace NULL with ...
                    , COALESCE(upper(t.%2$I), 'infinity')  -- ... +/- infinity
               FROM   %1$I t
               ORDER  BY t.%2$I$$
            , _tbl, _col)
   LOOP
      IF _lower > _enddate THEN     -- return previous range
         RETURN NEXT daterange(_startdate, _enddate);
         SELECT _lower, _upper  INTO _startdate, _enddate;

      ELSIF _upper > _enddate THEN  -- expand range
         _enddate := _upper;

      -- do nothing if _upper <= _enddate (range already included) ...

      ELSIF _enddate IS NULL THEN   -- init 1st round
         SELECT _lower, _upper  INTO _startdate, _enddate;
      END IF;
   END LOOP;

   IF FOUND THEN                    -- return last row
      RETURN NEXT daterange(_startdate, _enddate);
   END IF;
END
$func$  LANGUAGE plpgsql;

Ligar:

SELECT * FROM f_range_agg('test', 'range');  -- table and column name

A lógica é semelhante às soluções SQL, mas podemos nos contentar com uma única passagem.

SQL Fiddle.

Relacionado:

• GROUP BY e valores numéricos sequenciais agregados

O drill usual para manipular a entrada do usuário no SQL dinâmico:

• Injeção de SQL nas funções do Postgres x consultas preparadas

Índice

Para cada uma dessas soluções, um índice btree simples (padrão) rangeseria fundamental para o desempenho em grandes tabelas:

CREATE INDEX foo on test (range);

Um índice btree é de uso limitado para tipos de intervalo , mas podemos obter dados pré-classificados e talvez até uma varredura apenas de índice.

Eu vim com isso:

DO $$                                                                             
DECLARE 
    i date;
    a daterange := 'empty';
    day_as_range daterange;
    extreme_value date := '2100-12-31';
BEGIN
    FOR i IN 
        SELECT DISTINCT 
             generate_series(
                 lower(range), 
                 COALESCE(upper(range) - interval '1 day', extreme_value), 
                 interval '1 day'
             )::date
        FROM rangetest 
        ORDER BY 1
    LOOP
        day_as_range := daterange(i, i, '[]');
        BEGIN
            IF isempty(a)
            THEN a := day_as_range;
            ELSE a = a + day_as_range;
            END IF;
        EXCEPTION WHEN data_exception THEN
            RAISE INFO '%', a;
            a = day_as_range;
        END;
    END LOOP;

    IF upper(a) = extreme_value + interval '1 day'
    THEN a := daterange(lower(a), NULL);
    END IF;

    RAISE INFO '%', a;
END;
$$;

Ainda precisa de um pouco de aprimoramento, mas a ideia é a seguinte:

1. explodir os intervalos para datas individuais
2. fazendo isso, substitua o limite superior infinito por algum valor extremo
3. com base no pedido de (1), comece a construir os intervalos
4. quando a união ( +) falhar, retorne o intervalo já construído e reinicialize
5. finalmente, retorne o restante - se o valor extremo predefinido for atingido, substitua-o por NULL para obter um limite superior infinito

Há alguns anos, testei soluções diferentes (entre outras semelhantes às do @ErwinBrandstetter) para mesclar períodos sobrepostos em um sistema Teradata e achei o mais eficiente (usando Funções analíticas, a versão mais recente do Teradata possui funções internas para essa tarefa).

1. classifique as linhas por data de início
2. encontre a data final máxima de todas as linhas anteriores: maxEnddate
3. se essa data for menor que a data de início atual, você encontrará uma lacuna. Mantenha apenas essas linhas mais a primeira linha dentro de PARTITION (que é indicada por NULL) e filtre todas as outras linhas. Agora você obtém a data de início de cada intervalo e a data de término do intervalo anterior.
4. Então você simplesmente maxEnddateusa a próxima linha LEADe está quase pronto. Somente para a última linha LEADretorna a NULL, para resolver isso, calcule a data final máxima de todas as linhas de uma partição na etapa 2 e COALESCEnela.

Por que foi mais rápido? Dependendo dos dados reais, a etapa 2 pode reduzir bastante o número de linhas; portanto, a próxima etapa precisa operar apenas em um pequeno subconjunto, além de remover a agregação.

violino

SELECT
   daterange(startdate
            ,COALESCE(LEAD(maxPrevEnddate) -- next row's end date
                      OVER (ORDER BY startdate) 
                     ,maxEnddate)          -- or maximum end date
            ) AS range

FROM
 (
   SELECT
      range
     ,COALESCE(LOWER(range),'-infinity') AS startdate

   -- find the maximum end date of all previous rows
   -- i.e. the END of the previous range
     ,MAX(COALESCE(UPPER(range), 'infinity'))
      OVER (ORDER BY range
            ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING) AS maxPrevEnddate

   -- maximum end date of this partition
   -- only needed for the last range
     ,MAX(COALESCE(UPPER(range), 'infinity'))
      OVER () AS maxEnddate
   FROM test
 ) AS dt
WHERE maxPrevEnddate < startdate -- keep the rows where a range start
   OR maxPrevEnddate IS NULL     -- and keep the first row
ORDER BY 1;  

Como isso foi mais rápido no Teradata, não sei se é o mesmo para o PostgreSQL; seria bom obter alguns números de desempenho reais.

Por diversão, eu tentei. Eu achei que esse era o método mais rápido e limpo para fazer isso. Primeiro, definimos uma função que mescla se houver uma sobreposição ou se as duas entradas forem adjacentes, se não houver sobreposição ou adjacência, simplesmente retornamos a primeira daterange. Dica +é uma união de intervalo no contexto de intervalos.

CREATE FUNCTION merge_if_adjacent_or_overlaps (d1 daterange, d2 daterange)
RETURNS daterange AS $$
  SELECT
    CASE WHEN d1 && d2 OR d1 -|- d2
    THEN d1 + d2
    ELSE d1
    END;
$$ LANGUAGE sql
IMMUTABLE;

Então a usamos assim,

SELECT DISTINCT ON (lower(cumrange)) cumrange
FROM (
  SELECT merge_if_adjacent_or_overlaps(
    t1.range,
    lag(t1.range) OVER (ORDER BY t1.range)
  ) AS cumrange
  FROM test AS t1
) AS t
ORDER BY lower(cumrange)::date, upper(cumrange)::date DESC NULLS first;