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

20

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 |           ==
--+---------------------------
  | ====== == ===============>
Villiers Strauss
quelle

Antworten:

22

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.)

  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:

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 .

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:

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:

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

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.

Erwin Brandstetter
quelle
@Villiers: Mich würde sehr interessieren, wie jede dieser Lösungen mit Ihren Daten funktioniert. Vielleicht können Sie eine andere Antwort mit Testergebnissen und einigen Informationen zu Ihrem Tischdesign und Ihren Kardinalitäten posten? Am besten mit EXPLAIN ( ANALYZE, TIMING OFF)und vergleichen Sie das Beste aus fünf.
Erwin Brandstetter
Der Schlüssel für diese Art von Problemen ist die Verzögerungs-SQL-Funktion (Blei kann auch verwendet werden), mit der die Werte sortierter Zeilen verglichen werden. Dadurch sind keine Selbstverknüpfungen mehr erforderlich, mit denen sich auch überlappende Bereiche zu einem einzigen Bereich zusammenfassen lassen. Anstelle von range kann bei Problemen mit zwei Spalten some_star, some_end diese Strategie angewendet werden.
Kemin Zhou
@ErwinBrandstetter Hey, ich versuche diese Abfrage zu verstehen (die mit CTEs), aber ich kann nicht herausfinden, wofür (CTE A) max(COALESCE(upper(range), 'infinity')) OVER (ORDER BY range) AS enddateist. Kann es nicht einfach sein COALESCE(upper(range), 'infinity') as enddate? AFAIK max() + over (order by range)wird gleich upper(range)hierher zurückkehren.
user606521
1
@ user606521: Was Sie beobachten, ist der Fall, wenn die Obergrenze kontinuierlich wächst, wenn Sie nach Bereich sortiert werden - was für einige Datenverteilungen garantiert sein kann und Sie dann vereinfachen können, wie Sie vorschlagen. Beispiel: Feste Längenbereiche. Für Bereiche beliebiger Länge kann der nächste Bereich eine größere Untergrenze, aber immer noch eine untere Obergrenze haben. Wir brauchen also die bisher größte Obergrenze aller Bereiche.
Erwin Brandstetter
6

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
dezso
quelle
Es scheint mir ziemlich teuer zu sein, generate_series()für jede Reihe zu laufen , besonders wenn es offene Bereiche geben kann ...
Erwin Brandstetter
@ErwinBrandstetter ja, das ist ein Problem, das ich testen wollte (nachdem mein erstes Extrem 9999-12-31 war :). Gleichzeitig frage ich mich, warum meine Antwort mehr positive Stimmen hat als Ihre. Dies ist möglicherweise einfacher zu verstehen ... Also, zukünftige Wähler: Erwins Antwort ist meiner überlegen! Stimmen Sie dort ab!
Dezso
3

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.

dnoeth
quelle
Ist es ausreichend, nur zu Beginn des Sortiments zu bestellen? Funktioniert es, wenn Sie drei Bereiche mit jeweils gleichem Anfang und unterschiedlichem Ende haben?
Salman A
1
Es funktioniert nur mit dem Startdatum, ohne dass das Enddatum absteigend sortiert hinzugefügt werden muss (Sie prüfen nur, ob eine Lücke vorhanden ist, damit die erste Zeile für ein bestimmtes Datum übereinstimmt)
Donnerstag,
-1

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;
Evan Carroll
quelle
1
Die Fensterfunktion berücksichtigt jeweils nur zwei benachbarte Werte und übersieht Ketten. Versuchen Sie es mit ('2015-01-01', '2015-01-03'), ('2015-01-03', '2015-01-05'), ('2015-01-05', '2015-01-06').
Erwin Brandstetter