Łączenie oddzielnych zakresów w możliwie największe ciągłe zakresy

Próbuję połączyć wiele zakresów dat (moje obciążenie wynosi około 500, w większości przypadków 10), które mogą, ale nie muszą, pokrywać się z największymi możliwymi ciągłymi zakresami dat. Na przykład:

Dane:

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

Tabela wygląda następująco:

 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)

Pożądane wyniki:

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

Reprezentacja wizualna:

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

Założenia / wyjaśnienia

1. Nie ma potrzeby rozróżniania infinityi otwierania górnej granicy ( upper(range) IS NULL). (Możesz to zrobić w obie strony, ale w ten sposób jest to prostsze.)

   • NULL vs. infinityw typach zakresów PostgreSQL

2. Ponieważ datejest to dyskretny typ, wszystkie zakresy mają domyślne [)granice. Według dokumentacji:

   Wbudowany rodzaju zakres int4range, int8rangei daterangecałkowitego zużycia postaci kanonicznej, który zawiera dolną granicę i górną granicę obejmuje; to znaczy [),.

   W przypadku innych typów (jak tsrange!) Egzekwowałbym to samo, jeśli to możliwe:

   • Zapobieganie sąsiednim / nakładającym się wpisom za pomocą EXCLUDE w PostgreSQL

Rozwiązanie z czystym SQL

Z CTE dla jasności:

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;

Lub to samo z podkwerendami, szybsze, ale mniej łatwe do odczytania:

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;

Lub z jednym poziomem podkwerend mniejszym, ale z odwróconą kolejnością sortowania:

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;

• Posortuj okno w drugim kroku za pomocą ORDER BY range DESC NULLS LAST(z NULLS LAST), aby uzyskać idealnie odwróconą kolejność sortowania. Powinno to być tańsze (łatwiejsze w produkcji, idealnie pasuje do kolejności sortowania sugerowanego indeksu) i dokładne dla przypadków narożnych rank IS NULL.
  • Sortuj PostgreSQL według daty i godziny, najpierw zerowy?

Wyjaśnić

a: Przy zamawianiu przez range, oblicz maksymalną liczbę górną granicę ( enddate) za pomocą funkcji okna.
Zastąp granice NULL (niezwiązane) +/- infinitytylko dla uproszczenia (bez specjalnych przypadków NULL).

b: W tym samym porządku sortowania, jeśli poprzedni enddatejest wcześniejszy niż startdatemamy przerwę i rozpoczynamy nowy zakres ( step).
_{Pamiętaj, że górna granica jest zawsze wykluczona.}

c: Utwórz grupy ( grp), licząc kroki za pomocą innej funkcji okna.

W zewnętrznej SELECTkompilacji waha się od dolnej do górnej granicy w każdej grupie. Voilá.
Ściśle związana odpowiedź na SO z dodatkowymi wyjaśnieniami:

• Porównaj wiele zakresów dat

Rozwiązanie proceduralne z plpgsql

Działa dla dowolnej nazwy tabeli / kolumny, ale tylko dla typu daterange.
Rozwiązania proceduralne z pętlami są zwykle wolniejsze, ale w tym szczególnym przypadku oczekuję, że funkcja będzie znacznie szybsza, ponieważ wymaga tylko jednego sekwencyjnego skanowania :

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;

Połączenie:

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

Logika jest podobna do rozwiązań SQL, ale możemy zrobić to za jednym przejściem.

SQL Fiddle.

Związane z:

• GROUP BY i agreguj kolejne wartości liczbowe

Zwykłe ćwiczenie do obsługi danych wejściowych użytkownika w dynamicznym SQL:

• Wstrzyknięcie SQL w funkcjach Postgres a przygotowane zapytania

Indeks

Dla każdego z tych rozwiązań zwykły (domyślny) indeks btree rangebyłby kluczowy dla wydajności w dużych tabelach:

CREATE INDEX foo on test (range);

Indeks btree ma ograniczone zastosowanie dla typów zakresów , ale możemy uzyskać wstępnie posortowane dane, a może nawet skanowanie tylko indeksu.

Wymyśliłem to:

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

Nadal wymaga trochę szlifowania, ale pomysł jest następujący:

1. rozbić zakresy na poszczególne daty
2. robiąc to, zastąp nieskończoną górną granicę jakąś ekstremalną wartością
3. na podstawie kolejności od (1) zacznij budować zakresy
4. gdy union ( +) zawiedzie, zwróć już zbudowany zakres i ponownie zainicjuj
5. na koniec zwróć resztę - jeśli osiągnięta zostanie wstępnie zdefiniowana wartość ekstremalna, zastąp ją wartością NULL, aby uzyskać nieskończoną górną granicę

Kilka lat temu przetestowałem różne rozwiązania (między innymi podobne do tych z @ErwinBrandstetter) do łączenia nakładających się okresów w systemie Teradata i znalazłem następujące najbardziej wydajne (przy użyciu funkcji analitycznych, nowsza wersja Teradata ma wbudowane funkcje dla to zadanie).

1. posortuj wiersze według daty rozpoczęcia
2. znajdź maksymalną datę zakończenia wszystkich poprzednich wierszy: maxEnddate
3. jeśli ta data jest krótsza niż bieżąca data rozpoczęcia, oznacza to lukę. Zachowaj tylko te wiersze plus pierwszy wiersz w PARTYCJI (co jest oznaczone wartością NULL) i filtruj wszystkie pozostałe wiersze. Teraz masz datę początkową dla każdego zakresu i datę końcową poprzedniego zakresu.
4. Wtedy po prostu dostać następny wiersz jest maxEnddateprzy użyciu LEADi jesteś prawie gotowy. Tylko dla ostatniego wiersza LEADzwraca a NULL, aby rozwiązać ten problem, oblicz maksymalną datę zakończenia wszystkich wierszy partycji w kroku 2 i COALESCEto.

Dlaczego było szybciej? W zależności od rzeczywistych danych krok # 2 może znacznie zmniejszyć liczbę wierszy, więc następny krok musi działać tylko na małym podzbiorze, a dodatkowo usuwa agregację.

skrzypce

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;  

Ponieważ było to najszybsze na Teradata, nie wiem, czy to samo dla PostgreSQL, byłoby miło uzyskać jakieś rzeczywiste liczby wydajności.

Dla zabawy spróbowałem. Przekonałem się, że jest to najszybsza i najczystsza metoda, aby to zrobić. Najpierw definiujemy funkcję, która łączy się, jeśli zachodzi na siebie nakładka lub jeśli dwa wejścia są sąsiednie, jeśli nie ma nakładania się lub sąsiedztwa, po prostu zwracamy pierwszą datę zmiany. Wskazówka +jest związkiem zasięgu w kontekście zakresów.

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;

Następnie używamy tego w ten sposób,

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;