Combinaison de plages distinctes en plus grandes plages contiguës possibles

J'essaie de combiner plusieurs plages de dates (ma charge est d'environ 500 max, la plupart des cas 10) qui peuvent ou non se chevaucher dans les plus grandes plages de dates contiguës possibles. Par exemple:

Les données:

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

Le tableau ressemble à:

 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)

Résultats désirés:

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

Représentation visuelle:

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

Hypothèses / clarifications

1. Pas besoin de différencier entre infinityet d'ouvrir la limite supérieure ( upper(range) IS NULL). (Vous pouvez l'avoir de toute façon, mais c'est plus simple de cette façon.)

   • NULL vs infinitydans les types de plage PostgreSQL

2. Puisque datec'est un type discret, toutes les plages ont des [)limites par défaut . Par documentation:

   Le haut-types de plage int4range, int8rangeet daterangetoute utilisation d' une forme canonique qui comprend la borne inférieure et la borne supérieure ne comprend pas; c'est-à-dire [),.

   Pour d'autres types (comme tsrange!) J'appliquerais la même chose si possible:

   • Empêcher les entrées adjacentes / se chevauchant avec EXCLUDE dans PostgreSQL

Solution avec SQL pur

Avec les CTE pour plus de clarté:

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 , la même chose avec les sous-requêtes, plus rapide mais moins facile à lire aussi:

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 avec un niveau de sous-requête en moins, mais en inversant l'ordre de tri:

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;

• Triez la fenêtre dans la deuxième étape avec ORDER BY range DESC NULLS LAST(avec NULLS LAST) pour obtenir un ordre de tri parfaitement inversé. Cela devrait être moins cher (plus facile à produire, correspond parfaitement à l'ordre de tri de l'index suggéré) et précis pour les cas d'angle avec rank IS NULL.
  • Tri PostgreSQL par datetime asc, null first?

Explique

a: Lors de la commande par range, calculez le maximum courant de la limite supérieure ( enddate) avec une fonction de fenêtre.
Remplacez les limites NULL (sans limite) par +/- infinityjuste pour simplifier (pas de cas NULL spéciaux).

b: Dans le même ordre de tri, si le précédent enddateest antérieur, startdatenous avons un écart et commençons une nouvelle plage ( step).
_{N'oubliez pas que la limite supérieure est toujours exclue.}

c: Formez des groupes ( grp) en comptant les étapes avec une autre fonction de fenêtre.

Dans la SELECTconstruction externe s'étend de la limite inférieure à la limite supérieure dans chaque groupe. Voilá.
Réponse étroitement liée à SO avec plus d'explications:

• Comparer plusieurs plages de dates

Solution procédurale avec plpgsql

Fonctionne pour n'importe quel nom de table / colonne, mais uniquement pour le type daterange.
Les solutions procédurales avec boucles sont généralement plus lentes, mais dans ce cas particulier, je m'attends à ce que la fonction soit sensiblement plus rapide car elle n'a besoin que d'un seul balayage séquentiel :

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;

Appel:

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

La logique est similaire aux solutions SQL, mais nous pouvons nous contenter d'un seul passage.

SQL Fiddle.

En relation:

• GROUP BY et valeurs numériques séquentielles agrégées

L'exercice habituel pour gérer les entrées utilisateur en SQL dynamique:

• Injection SQL dans les fonctions Postgres vs requêtes préparées

Indice

Pour chacune de ces solutions, un index btree simple (par défaut) rangeserait déterminant pour les performances dans les grandes tables:

CREATE INDEX foo on test (range);

Un index btree est d'une utilité limitée pour les types de plage , mais nous pouvons obtenir des données pré-triées et peut-être même une analyse d'index uniquement.

Je suis venu avec ceci:

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

A encore besoin d'un peu de perfectionnement, mais l'idée est la suivante:

1. exploser les plages à des dates individuelles
2. ce faisant, remplacez la limite supérieure infinie par une valeur extrême
3. sur la base de la commande de (1), commencer à construire les gammes
4. lorsque l'union ( +) échoue, retourne la plage déjà construite et réinitialise
5. Enfin, retournez le reste - si la valeur extrême prédéfinie est atteinte, remplacez-la par NULL pour obtenir une limite supérieure infinie

Il y a quelques années, j'ai testé différentes solutions (parmi d'autres similaires à celles de @ErwinBrandstetter) pour fusionner des périodes qui se chevauchent sur un système Teradata et j'ai trouvé la suivante la plus efficace (en utilisant les fonctions analytiques, une version plus récente de Teradata a des fonctions intégrées pour cette tâche).

1. trier les lignes par date de début
2. recherchez la date de fin maximale de toutes les lignes précédentes: maxEnddate
3. si cette date est inférieure à la date de début actuelle, vous avez trouvé un écart. Conservez uniquement ces lignes plus la première ligne dans la PARTITION (qui est indiquée par un NULL) et filtrez toutes les autres lignes. Vous obtenez maintenant la date de début de chaque plage et la date de fin de la plage précédente.
4. Ensuite , vous obtenez simplement la ligne suivante est à l' maxEnddateaide LEADet vous avez presque terminé. Uniquement pour la dernière ligne LEADrenvoie un NULL, pour résoudre ce problème, calculez la date de fin maximale de toutes les lignes d'une partition à l'étape 2 et COALESCEainsi de suite.

Pourquoi c'était plus rapide? En fonction des données réelles, l'étape # 2 pourrait réduire considérablement le nombre de lignes, de sorte que l'étape suivante doit fonctionner uniquement sur un petit sous-ensemble, en outre, elle supprime l'agrégation.

violon

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;  

Comme c'était le plus rapide sur Teradata, je ne sais pas si c'est la même chose pour PostgreSQL, ce serait bien d'obtenir des chiffres de performances réels.

Pour le plaisir, je lui ai donné un coup de feu. J'ai trouvé que c'était la méthode la plus rapide et la plus propre pour ce faire. D'abord, nous définissons une fonction qui fusionne s'il y a un chevauchement ou si les deux entrées sont adjacentes, s'il n'y a pas de chevauchement ou d'adjacence, nous renvoyons simplement la première daterange. Hint +est une union de plage dans le contexte des plages.

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;

Ensuite, nous l'utilisons comme ça,

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;