Menggabungkan rentang terpisah menjadi rentang berdekatan terbesar yang mungkin

Saya mencoba untuk menggabungkan beberapa rentang tanggal (beban saya sekitar maks 500, sebagian besar kasus 10) yang mungkin tumpang tindih dengan rentang tanggal bersebelahan terbesar yang mungkin. Sebagai contoh:

Data:

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

Tabelnya terlihat seperti:

 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)

Hasil yang diinginkan:

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

Representasi visual:

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

Asumsi / Klarifikasi

1. Tidak perlu membedakan antara infinitydan membuka batas atas ( upper(range) IS NULL). (Anda bisa mendapatkannya dengan cara lain, tetapi lebih sederhana dengan cara ini.)

   • NULL vs. infinitydalam tipe rentang PostgreSQL

2. Karena datemerupakan tipe diskrit, semua rentang memiliki [)batas default . Per dokumentasi:

   Jenis rentang bawaan int4range,, int8rangedan daterangesemua menggunakan bentuk kanonik yang mencakup batas bawah dan mengecualikan batas atas; itu adalah [),.

   Untuk tipe lain (seperti tsrange!) Saya akan menerapkan hal yang sama jika memungkinkan:

   • Mencegah entri yang berdekatan / tumpang tindih dengan EXCLUDE di PostgreSQL

Solusi dengan SQL murni

Dengan CTE untuk kejelasan:

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;

Atau , sama dengan subqueries, lebih cepat tetapi juga tidak terlalu mudah dibaca:

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;

Atau dengan satu tingkat subquery yang lebih sedikit, tetapi membalik urutan:

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;

• Sortir jendela pada langkah kedua dengan ORDER BY range DESC NULLS LAST(dengan NULLS LAST) untuk mendapatkan urutan sortir yang terbalik sempurna . Ini harus lebih murah (lebih mudah diproduksi, cocok dengan urutan indeks yang disarankan dengan sempurna) dan akurat untuk kasus sudut dengan rank IS NULL.
  • PostgreSQL urutkan berdasarkan datetime asc, null dulu?

Menjelaskan

a: Saat memesan oleh range, hitung maksimum berjalan dari batas atas ( enddate) dengan fungsi jendela.
Ganti batas NULL (tanpa batas) dengan +/- infinityhanya untuk menyederhanakan (tidak ada kasus NULL khusus).

b: Dalam urutan sortir yang sama, jika sebelumnya enddatelebih awal dari startdatekami memiliki celah dan memulai rentang baru ( step).
_{Ingat, batas atas selalu dikecualikan.}

c: Bentuk grup ( grp) dengan menghitung langkah-langkah dengan fungsi jendela lain.

Di luar SELECTmembangun berkisar dari batas bawah ke batas atas di setiap kelompok. Voa.
Jawaban terkait erat pada SO dengan penjelasan lebih lanjut:

• Bandingkan beberapa rentang tanggal

Solusi prosedural dengan plpgsql

Berfungsi untuk nama tabel / kolom apa saja, tetapi hanya untuk tipe daterange.
Solusi prosedural dengan loop biasanya lebih lambat, tetapi dalam kasus khusus ini saya berharap fungsi menjadi jauh lebih cepat karena hanya membutuhkan pemindaian sekuensial tunggal :

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;

Panggilan:

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

Logikanya mirip dengan solusi SQL, tetapi kita bisa puas dengan satu pass.

SQL Fiddle.

Terkait:

• KELOMPOK OLEH dan agregat nilai numerik berurutan

Bor biasa untuk menangani input pengguna dalam SQL dinamis:

• Injeksi SQL dalam fungsi Postgres vs kueri yang disiapkan

Indeks

Untuk masing-masing solusi ini, indeks btree (default) polos rangeakan sangat berperan untuk kinerja dalam tabel besar:

CREATE INDEX foo on test (range);

Indeks btree terbatas penggunaannya untuk tipe rentang , tetapi kita bisa mendapatkan data pra-disortir dan bahkan mungkin hanya pemindaian indeks.

Saya datang dengan ini:

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

Masih perlu sedikit diasah, tetapi idenya adalah sebagai berikut:

1. meledak rentang ke tanggal individual
2. melakukan ini, ganti batas atas tak terbatas dengan beberapa nilai ekstrim
3. berdasarkan pemesanan dari (1), mulailah membangun rentang
4. ketika union ( +) gagal, kembalikan kisaran yang sudah dibangun dan inisialisasi ulang
5. akhirnya, kembalikan sisanya - jika nilai ekstrem yang ditentukan tercapai, ganti dengan NULL untuk mendapatkan batas atas tak terbatas

Beberapa tahun yang lalu saya menguji berbagai solusi (antara lain beberapa serupa dengan yang dari @ErwinBrandstetter) untuk menggabungkan periode yang tumpang tindih pada sistem Teradata dan saya menemukan yang berikut ini yang paling efisien (menggunakan Fungsi Analitik, versi Teradata yang lebih baru memiliki fungsi bawaan untuk tugas itu).

1. urutkan baris berdasarkan tanggal mulai
2. temukan tanggal akhir maksimum semua baris sebelumnya: maxEnddate
3. jika tanggal ini kurang dari tanggal mulai saat ini, Anda menemukan celah. Hanya pertahankan baris-baris itu ditambah baris pertama dalam PARTISI (yang ditandai dengan NULL) dan filter semua baris lainnya. Sekarang Anda mendapatkan tanggal mulai untuk setiap rentang dan tanggal akhir dari rentang sebelumnya.
4. Maka Anda cukup maxEnddatemenggunakan baris berikutnya LEADdan Anda hampir selesai. Hanya untuk baris terakhir LEADmengembalikan a NULL, untuk menyelesaikan ini menghitung tanggal akhir maksimum semua baris partisi di langkah 2 dan COALESCEitu.

Kenapa lebih cepat? Tergantung pada langkah data aktual # 2 mungkin sangat mengurangi jumlah baris, sehingga langkah selanjutnya perlu beroperasi pada subset kecil saja, selain itu menghilangkan agregasi.

biola

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;  

Karena ini tercepat di Teradata, saya tidak tahu apakah itu sama untuk PostgreSQL, akan menyenangkan untuk mendapatkan beberapa angka kinerja aktual.

Untuk bersenang-senang, saya mencobanya. Saya menemukan ini menjadi metode tercepat dan terbersih untuk melakukan ini. Pertama kita mendefinisikan fungsi yang menggabungkan jika ada tumpang tindih atau jika dua input berdekatan, jika tidak ada tumpang tindih atau kedekatan kita hanya mengembalikan daterange pertama. Petunjuk +adalah rentang serikat dalam konteks rentang.

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;

Lalu kami menggunakannya seperti ini,

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;