Combinando rangos separados en los rangos contiguos más grandes posibles

Estoy tratando de combinar varios rangos de fechas (mi carga es de aproximadamente 500, la mayoría de los casos 10) que pueden superponerse o no en los rangos de fechas contiguas más grandes posibles. Por ejemplo:

Datos:

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

La mesa se ve así:

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

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

Representación visual:

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

Suposiciones / aclaraciones

1. No es necesario diferenciar entre infinityy abrir el límite superior ( upper(range) IS NULL). (Puede tenerlo de cualquier manera, pero es más simple de esta manera).

   • NULL vs. infinityen tipos de rango PostgreSQL

2. Como datees un tipo discreto, todos los rangos tienen [)límites predeterminados . Por documentación:

   El incorporada en tipos de rango int4range, int8rangey daterangetodo el uso de una forma canónica que incluye el límite inferior y excluye el límite superior; es decir, [).

   Para otros tipos (como tsrange!) Haría cumplir lo mismo si es posible:

   • Prevención de entradas adyacentes / superpuestas con EXCLUDE en PostgreSQL

Solución con SQL puro

Con CTE para mayor claridad:

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;

O , lo mismo con las subconsultas, más rápido pero menos fácil de leer:

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;

O con un nivel de subconsulta menos, pero cambiando el orden de clasificación:

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;

• Ordene la ventana en el segundo paso con ORDER BY range DESC NULLS LAST(con NULLS LAST) para obtener un orden de inversión perfectamente invertido. Esto debería ser más barato (más fácil de producir, coincide perfectamente con el orden de clasificación del índice sugerido) y preciso para casos de esquina rank IS NULL.
  • PostgreSQL ordenar por fecha y hora asc, nulo primero?

Explique

a: Mientras ordena range, calcule el máximo de ejecución del límite superior ( enddate) con una función de ventana.
Reemplace los límites NULL (sin límites) con +/- infinitysolo para simplificar (sin casos especiales NULL).

b: En el mismo orden de clasificación, si la anterior enddatees anterior a la startdateque tenemos un espacio y comenzamos un nuevo rango ( step).
_{Recuerde, el límite superior siempre está excluido.}

c: Forma grupos ( grp) contando los pasos con otra función de ventana.

En la SELECTconstrucción externa, el rango va desde el límite inferior al superior en cada grupo. Voilá
Respuesta estrechamente relacionada en SO con más explicación:

• Comparar múltiples rangos de fechas

Solución de procedimiento con plpgsql

Funciona para cualquier nombre de tabla / columna, pero solo para el tipo daterange.
Las soluciones de procedimiento con bucles suelen ser más lentas, pero en este caso especial espero que la función sea sustancialmente más rápida, ya que solo necesita un escaneo secuencial único :

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;

Llamada:

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

La lógica es similar a las soluciones SQL, pero podemos hacerlo con un solo paso.

SQL Fiddle.

Relacionado:

• GROUP BY y valores numéricos secuenciales agregados

El ejercicio habitual para manejar la entrada del usuario en SQL dinámico:

• Inyección SQL en funciones de Postgres vs consultas preparadas

Índice

Para cada una de estas soluciones, un índice btree simple (predeterminado) en rangesería instrumental para el rendimiento en tablas grandes:

CREATE INDEX foo on test (range);

Un índice btree es de uso limitado para los tipos de rango , pero podemos obtener datos ordenados previamente y tal vez incluso un escaneo de solo índice.

Se me ocurrió esto:

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

Todavía necesita un poco de perfeccionamiento, pero la idea es la siguiente:

1. explotar los rangos a fechas individuales
2. haciendo esto, reemplace el límite superior infinito con algún valor extremo
3. basado en el pedido de (1), comience a construir los rangos
4. cuando la unión+ ) falla, devuelve el rango ya construido y reinicializa
5. finalmente, devuelva el resto: si se alcanza el valor extremo predefinido, reemplácelo con NULL para obtener un límite superior infinito

Hace algunos años probé diferentes soluciones (entre otras, algunas similares a las de @ErwinBrandstetter) para fusionar períodos superpuestos en un sistema Teradata y encontré la siguiente más eficiente (usando funciones analíticas, la versión más nueva de Teradata tiene funciones integradas para esa tarea).

1. ordenar las filas por fecha de inicio
2. encuentre la fecha de finalización máxima de todas las filas anteriores: maxEnddate
3. si esta fecha es menor que la fecha de inicio actual, encontró una brecha. Solo mantenga esas filas más la primera fila dentro de PARTITION (que se indica con un NULL) y filtre todas las demás filas. Ahora obtiene la fecha de inicio para cada rango y la fecha de finalización del rango anterior.
4. Luego, simplemente maxEnddateusa la siguiente fila LEADy ya casi está listo. Solo para la última fila LEADdevuelve a NULL, para resolver esto, calcule la fecha de finalización máxima de todas las filas de una partición en el paso 2 y COALESCEluego.

¿Por qué fue más rápido? Dependiendo de los datos reales, el paso n. ° 2 podría reducir en gran medida el número de filas, por lo que el siguiente paso solo debe funcionar en un pequeño subconjunto, además elimina la agregación.

violín

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 esto fue más rápido en Teradata, no sé si es lo mismo para PostgreSQL, sería bueno obtener algunos números de rendimiento reales.

Por diversión, lo probé. Encontré que este es el método más rápido y limpio para hacer esto. Primero definimos una función que se fusiona si hay una superposición o si las dos entradas son adyacentes, si no hay superposición o adyacencia, simplemente devolvemos el primer rango de fechas. Sugerencia +es una unión de rango en el contexto de rangos.

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;

Luego lo usamos así,

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;