Kombinieren separater Bereiche zu größtmöglichen zusammenhängenden Bereichen

Ich versuche, mehrere Datumsbereiche zu kombinieren (meine Last beträgt ungefähr 500, in den meisten Fällen 10), die sich möglicherweise mit den größtmöglichen zusammenhängenden Datumsbereichen überschneiden oder nicht. Beispielsweise:

Daten:

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

Tabelle sieht so aus:

 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)

Gewünschten Erfolge:

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

Visuelle Darstellung:

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

Annahmen / Erläuterungen

1. Es ist nicht erforderlich, zwischen einer infinityoberen Schranke und einer offenen oberen Schranke zu unterscheiden ( upper(range) IS NULL). (Sie können es so oder so haben, aber auf diese Weise ist es einfacher.)

   • NULL infinityim Vergleich zu PostgreSQL-Bereichstypen

2. Da datees sich um einen diskreten Typ handelt, haben alle Bereiche Standardgrenzen [). Per Dokumentation:

   Die Einbau-Bereichstypen int4range, int8rangeund die daterangegesamte Nutzung eine kanonische Form , die die untere Grenze , und umfasst nicht die obere Grenze enthält; das heißt [),.

   Für andere Typen (wie tsrange!) Würde ich dasselbe nach Möglichkeit durchsetzen:

   • Verhindern von benachbarten / überlappenden Einträgen mit EXCLUDE in PostgreSQL

Lösung mit reinem SQL

Mit CTEs zur Klarheit:

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;

Oder , wie bei Unterabfragen, schneller, aber nicht so einfach zu lesen:

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;

Oder mit einer Unterabfrageebene weniger, aber umgekehrter Sortierreihenfolge:

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;

• Sortieren Sie das Fenster im zweiten Schritt mit ORDER BY range DESC NULLS LAST(mit NULLS LAST), um eine perfekt umgekehrte Sortierreihenfolge zu erhalten. Dies sollte billiger (einfacher herzustellen, passt perfekt zur Sortierreihenfolge des vorgeschlagenen Index) und für Eckfälle mit genau seinrank IS NULL .
  • PostgreSQL-Sortierung nach Datum / Uhrzeit aufsteigend, null zuerst?

Erklären

a: rangeBerechnen Sie während der Bestellung nach das laufende Maximum der oberen Schranke ( enddate) mit einer Fensterfunktion.
Ersetzen Sie NULL-Grenzen (unbegrenzt) durch +/- infinity, um dies zu vereinfachen (keine speziellen NULL-Fälle).

b: In der gleichen Sortierreihenfolge, wenn die vorherige enddatefrüher ist als startdatewir eine Lücke haben und einen neuen Bereich beginnen ( step).
_{Denken Sie daran, dass die Obergrenze immer ausgeschlossen ist.}

c: Bilden Sie Gruppen ( grp), indem Sie Schritte mit einer anderen Fensterfunktion zählen.

Im äußeren SELECTBuild reicht die Unter- bis Obergrenze in jeder Gruppe. Voilá.
Eng verwandte Antwort auf SO mit mehr Erklärung:

• Vergleichen Sie mehrere Datumsbereiche

Verfahrenslösung mit plpgsql

Funktioniert für jeden Tabellen- / Spaltennamen, jedoch nur für Typ daterange.
Prozedurale Lösungen mit Schleifen sind normalerweise langsamer, aber in diesem speziellen Fall erwarte ich, dass die Funktion wesentlich schneller ist, da sie nur einen einzigen sequentiellen Scan benötigt :

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;

Anruf:

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

Die Logik ist ähnlich wie bei den SQL-Lösungen, aber wir können mit einem einzigen Durchgang auskommen.

SQL-Geige.

Verbunden:

• GROUP BY und aggregierte fortlaufende numerische Werte

Der übliche Drill zum Behandeln von Benutzereingaben in dynamischem SQL:

• SQL-Injection in Postgres-Funktionen im Vergleich zu vorbereiteten Abfragen

Index

Für jede dieser Lösungen wäre ein einfacher (Standard-) Btree-Index rangefür die Leistung in großen Tabellen von entscheidender Bedeutung:

CREATE INDEX foo on test (range);

Ein Btree-Index ist für Bereichstypen von begrenztem Nutzen , aber wir können vorsortierte Daten und möglicherweise sogar einen Nur-Index-Scan abrufen.

Das habe ich mir ausgedacht:

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

Muss noch etwas geschliffen werden, aber die Idee ist folgende:

1. explodieren die Bereiche zu einzelnen Daten
2. Ersetzen Sie dabei die unendliche Obergrenze durch einen Extremwert
3. Beginnen Sie, basierend auf der Bestellung von (1), mit dem Aufbau der Bereiche
4. Wenn union ( +) fehlschlägt, geben Sie den bereits erstellten Bereich zurück und initialisieren Sie ihn neu
5. Geben Sie zum Schluss den Rest zurück. Wenn der vordefinierte Extremwert erreicht ist, ersetzen Sie ihn durch NULL, um eine unendliche Obergrenze zu erhalten

Vor einigen Jahren habe ich verschiedene Lösungen (unter anderem ähnliche Lösungen wie bei @ErwinBrandstetter) zum Zusammenführen überlappender Zeiträume auf einem Teradata-System getestet und die folgende als die effizienteste herausgefunden (unter Verwendung von Analytical Functions, neuere Version von Teradata haben integrierte Funktionen für diese Aufgabe).

1. sortieren Sie die Zeilen nach dem Startdatum
2. Finden Sie das maximale Enddatum aller vorherigen Zeilen: maxEnddate
3. Wenn dieses Datum kleiner als das aktuelle Startdatum ist, haben Sie eine Lücke gefunden. Behalten Sie nur diese Zeilen plus der ersten Zeile in der PARTITION (die durch NULL gekennzeichnet ist) und filtern Sie alle anderen Zeilen. Jetzt erhalten Sie das Startdatum für jeden Bereich und das Enddatum des vorherigen Bereichs.
4. Dann erhalten Sie einfach die nächste Zeile ist maxEnddatemit LEADund Sie sind fast fertig. Nur für die letzte Zeile LEADgibt a zurück NULL, um dies zu lösen, berechnen Sie das maximale Enddatum aller Zeilen einer Partition in Schritt 2 und COALESCEes.

Warum war es schneller? Abhängig von den tatsächlichen Daten kann Schritt 2 die Anzahl der Zeilen erheblich reduzieren, sodass der nächste Schritt nur eine kleine Teilmenge verarbeiten muss und zusätzlich die Aggregation entfernt.

Geige

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;  

Da dies bei Teradata am schnellsten war, weiß ich nicht, ob es bei PostgreSQL dasselbe ist. Es wäre schön, wenn Sie einige tatsächliche Leistungszahlen erhalten würden.

Zum Spaß habe ich es ausprobiert. Ich fand dies die schnellste und sauberste Methode, um dies zu tun. Zuerst definieren wir eine Funktion, die zusammengeführt wird, wenn es eine Überlappung gibt oder wenn die beiden Eingänge benachbart sind, wenn es keine Überlappung oder Nachbarschaft gibt, geben wir einfach den ersten Datumsbereich zurück. Hinweis +ist eine Bereichsvereinigung im Kontext von Bereichen.

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;

Dann verwenden wir es so,

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;