Pilih awal dan akhir beberapa rentang yang berdampingan secara efisien dalam kueri Postgresql

Saya punya sekitar satu miliar baris data dalam sebuah tabel dengan nama dan bilangan bulat dalam kisaran 1-288. Untuk nama yang diberikan , setiap int adalah unik, dan tidak setiap bilangan bulat yang mungkin ada dalam jajaran - jadi ada celah.

Kueri ini menghasilkan contoh kasus:

--what I have:
SELECT *
FROM ( VALUES ('foo', 2),
              ('foo', 3),
              ('foo', 4),
              ('foo', 10),
              ('foo', 11),
              ('foo', 13),
              ('bar', 1),
              ('bar', 2),
              ('bar', 3)
     ) AS baz ("name", "int")

Saya ingin membuat tabel pencarian dengan baris untuk setiap nama dan urutan bilangan bulat yang berdekatan. Setiap baris akan berisi:

nama - nilai awal kolom nama - bilangan bulat pertama di akhir urutan yang berdekatan - nilai akhir dalam rentang urutan yang berdekatan - akhir - mulai + 1

Kueri ini menghasilkan contoh output untuk contoh di atas:

--what I need:
SELECT * 
FROM ( VALUES ('foo', 2, 4, 3),
              ('foo', 10, 11, 2),
              ('foo', 13, 13, 1),
              ('bar', 1, 3, 3)
     ) AS contiguous_ranges ("name", "start", "end", span)

Karena saya memiliki begitu banyak baris, lebih efisien lebih baik. Yang mengatakan, saya hanya perlu menjalankan permintaan ini sekali, jadi itu bukan persyaratan mutlak.

Terima kasih sebelumnya!

Edit:

Saya harus menambahkan bahwa solusi PL / pgSQL dipersilakan (tolong jelaskan Trik Fancy - Saya masih baru untuk PL / pgSQL).

Bagaimana kalau menggunakan with recursive

tampilan tes:

create view v as 
select *
from ( values ('foo', 2),
              ('foo', 3),
              ('foo', 4),
              ('foo', 10),
              ('foo', 11),
              ('foo', 13),
              ('bar', 1),
              ('bar', 2),
              ('bar', 3)
     ) as baz ("name", "int");

pertanyaan:

with recursive t("name", "int") as ( select "name", "int", 1 as span from v
                                     union all
                                     select "name", v."int", t.span+1 as span
                                     from v join t using ("name")
                                     where v."int"=t."int"+1 )
select "name", "start", "start"+span-1 as "end", span
from( select "name", ("int"-span+1) as "start", max(span) as span
      from ( select "name", "int", max(span) as span 
             from t
             group by "name", "int" ) z
      group by "name", ("int"-span+1) ) z;

hasil:

 name | start | end | span
------+-------+-----+------
 foo  |     2 |   4 |    3
 foo  |    13 |  13 |    1
 bar  |     1 |   3 |    3
 foo  |    10 |  11 |    2
(4 rows)

Saya tertarik untuk mengetahui bagaimana kinerjanya di meja baris miliar Anda.

Anda dapat melakukannya dengan fungsi windowing. Ide dasarnya adalah menggunakan leaddan lagfungsi windowing untuk menarik baris ke depan dan di belakang baris saat ini. Kemudian kita dapat menghitung jika kita memiliki awal atau akhir urutan:

create temp view temp_view as
    select
        n,
        val,
        (lead <> val + 1 or lead is null) as islast,
        (lag <> val - 1 or lag is null) as isfirst,
        (lead <> val + 1 or lead is null) and (lag <> val - 1 or lag is null) as orphan
    from
    (
        select
            n,
            lead(val, 1) over( partition by n order by n, val),
            lag(val, 1) over(partition by n order by n, val ),
            val
        from test
        order by n, val
    ) as t
;  
select * from temp_view;
 n  | val | islast | isfirst | orphan 
-----+-----+--------+---------+--------
 bar |   1 | f      | t       | f
 bar |   2 | f      | f       | f
 bar |   3 | t      | f       | f
 bar |  24 | t      | t       | t
 bar |  42 | t      | t       | t
 foo |   2 | f      | t       | f
 foo |   3 | f      | f       | f
 foo |   4 | t      | f       | f
 foo |  10 | f      | t       | f
 foo |  11 | t      | f       | f
 foo |  13 | t      | t       | t
(11 rows)

(Saya menggunakan tampilan sehingga logikanya akan lebih mudah untuk diikuti di bawah ini.) Jadi sekarang kita tahu apakah barisnya adalah awal atau akhir. Kita harus memecahnya menjadi baris:

select
    n as "name",
    first,
    coalesce (last, first) as last,
    coalesce (last - first + 1, 1) as span
from
(
    select
    n,
    val as first,
    -- this will not be excellent perf. since were calling the view
    -- for each row sequence found. Changing view into temp table 
    -- will probably help with lots of values.
    (
        select min(val)
        from temp_view as last
        where islast = true
        -- need this since isfirst=true, islast=true on an orphan sequence
        and last.orphan = false
        and first.val < last.val
        and first.n = last.n
    ) as last
    from
        (select * from temp_view where isfirst = true) as first
) as t
;

 name | first | last | span 
------+-------+------+------
 bar  |     1 |    3 |    3
 bar  |    24 |   24 |    1
 bar  |    42 |   42 |    1
 foo  |     2 |    4 |    3
 foo  |    10 |   11 |    2
 foo  |    13 |   13 |    1
(6 rows)

Terlihat benar bagi saya :)

Solusi fungsi jendela lainnya. Tidak tahu tentang efisiensi, saya telah menambahkan rencana eksekusi pada akhirnya (walaupun dengan begitu sedikit baris, mungkin tidak banyak nilainya). Jika Anda ingin bermain-main: SQL-Fiddle test

Tabel dan data:

CREATE TABLE baz
( name VARCHAR(10) NOT NULL
, i INT  NOT NULL
, UNIQUE  (name, i)
) ;

INSERT INTO baz
  VALUES 
    ('foo', 2),
    ('foo', 3),
    ('foo', 4),
    ('foo', 10),
    ('foo', 11),
    ('foo', 13),
    ('bar', 1),
    ('bar', 2),
    ('bar', 3)
  ;

Pertanyaan:

SELECT a.name     AS name
     , a.i        AS start
     , b.i        AS "end"
     , b.i-a.i+1  AS span
FROM
      ( SELECT name, i
             , ROW_NUMBER() OVER (PARTITION BY name ORDER BY i) AS rn
        FROM baz AS a
        WHERE NOT EXISTS
              ( SELECT * 
                FROM baz AS prev
                WHERE prev.name = a.name
                  AND prev.i = a.i - 1
              ) 
      ) AS a
    JOIN
      ( SELECT name, i 
             , ROW_NUMBER() OVER (PARTITION BY name ORDER BY i) AS rn
        FROM baz AS a
        WHERE NOT EXISTS
              ( SELECT * 
                FROM baz AS next
                WHERE next.name = a.name
                  AND next.i = a.i + 1
              )
      ) AS b
    ON  b.name = a.name
    AND b.rn  = a.rn
 ; 

Rencana Kueri

Merge Join (cost=442.74..558.76 rows=18 width=46)
Merge Cond: ((a.name)::text = (a.name)::text)
Join Filter: ((row_number() OVER (?)) = (row_number() OVER (?)))
-> WindowAgg (cost=221.37..238.33 rows=848 width=42)
-> Sort (cost=221.37..223.49 rows=848 width=42)
Sort Key: a.name, a.i
-> Merge Anti Join (cost=157.21..180.13 rows=848 width=42)
Merge Cond: (((a.name)::text = (prev.name)::text) AND (((a.i - 1)) = prev.i))
-> Sort (cost=78.60..81.43 rows=1130 width=42)
Sort Key: a.name, ((a.i - 1))
-> Seq Scan on baz a (cost=0.00..21.30 rows=1130 width=42)
-> Sort (cost=78.60..81.43 rows=1130 width=42)
Sort Key: prev.name, prev.i
-> Seq Scan on baz prev (cost=0.00..21.30 rows=1130 width=42)
-> Materialize (cost=221.37..248.93 rows=848 width=50)
-> WindowAgg (cost=221.37..238.33 rows=848 width=42)
-> Sort (cost=221.37..223.49 rows=848 width=42)
Sort Key: a.name, a.i
-> Merge Anti Join (cost=157.21..180.13 rows=848 width=42)
Merge Cond: (((a.name)::text = (next.name)::text) AND (((a.i + 1)) = next.i))
-> Sort (cost=78.60..81.43 rows=1130 width=42)
Sort Key: a.name, ((a.i + 1))
-> Seq Scan on baz a (cost=0.00..21.30 rows=1130 width=42)
-> Sort (cost=78.60..81.43 rows=1130 width=42)
Sort Key: next.name, next.i
-> Seq Scan on baz next (cost=0.00..21.30 rows=1130 width=42)

Pada SQL Server, saya akan menambahkan satu kolom lagi bernama beforeInt:

SELECT *
FROM ( VALUES ('foo', 2, NULL),
              ('foo', 3, 2),
              ('foo', 4, 3),
              ('foo', 10, 4),
              ('foo', 11, 10),
              ('foo', 13, 11),
              ('bar', 1, NULL),
              ('bar', 2, 1),
              ('bar', 3, 2)
     ) AS baz ("name", "int", "previousInt")

Saya akan menggunakan batasan PERIKSA untuk memastikan bahwa beforeInt <int, dan batasan FK (nama, priorInt) merujuk ke (nama, int), dan beberapa kendala lagi untuk memastikan integritas data kedap air. Itu dilakukan, memilih celah itu sepele:

SELECT NAME, PreviousInt, Int from YourTable WHERE PreviousInt < Int - 1;

Untuk mempercepatnya, saya dapat membuat indeks yang difilter yang hanya menyertakan celah. Ini berarti bahwa semua celah Anda sudah dikomputasi, jadi pilihannya sangat cepat, dan kendala memastikan integritas data Anda yang sudah dikomputasi. Saya banyak menggunakan solusi seperti itu, semuanya ada di sistem saya.

Anda dapat mencari Metode Tabibitosan:

https://community.oracle.com/docs/DOC-915680
http://rwijk.blogspot.com/2014/01/tabibitosan.html
https://www.xaprb.com/blog/2006/03/22/find-contiguous-ranges-with-sql/

Pada dasarnya:

SQL> create table mytable (nr)
  2  as
  3  select 1 from dual union all
  4  select 2 from dual union all
  5  select 3 from dual union all
  6  select 6 from dual union all
  7  select 7 from dual union all
  8  select 11 from dual union all
  9  select 18 from dual union all
 10  select 19 from dual union all
 11  select 20 from dual union all
 12  select 21 from dual union all
 13  select 22 from dual union all
 14  select 25 from dual
 15  /

 Table created.

 SQL> with tabibitosan as
 2  ( select nr
 3         , nr - row_number() over (order by nr) grp
 4      from mytable
 5  )
 6  select min(nr)
 7       , max(nr)
 8    from tabibitosan
 9   group by grp
10   order by grp
11  /

   MIN(NR)    MAX(NR)
---------- ----------
         1          3
         6          7
        11         11
        18         22
        25         25

5 rows selected.

Saya pikir kinerja ini lebih baik:

SQL> r
  1  select min(nr) as range_start
  2    ,max(nr) as range_end
  3  from (-- our previous query
  4    select nr
  5      ,rownum
  6      ,nr - rownum grp
  7    from  (select nr
  8       from   mytable
  9       order by 1
 10      )
 11   )
 12  group by grp
 13* order by 1

RANGE_START  RANGE_END
----------- ----------
      1      3
      6      7
     11     11
     18     22
     25     25

rencana kasar:

• Pilih minimum untuk setiap nama, (grup dengan nama)
• Pilih minimum2 untuk setiap nama, di mana min2> min1 dan tidak ada (subquery: SEL min2-1).
• Sel max val1> min val1 di mana max val1 <min val2.

Ulangi dari 2. hingga tidak ada lagi pembaruan yang terjadi. Dari sana semakin rumit, Gordian, dengan pengelompokan lebih dari maks menit dan minimal maks. Saya kira saya akan memilih bahasa pemrograman.

PS: Tabel sampel yang bagus dengan beberapa nilai sampel akan baik-baik saja, yang bisa digunakan oleh semua orang, jadi tidak semua orang membuat data testdinya dari awal.

Solusi ini terinspirasi dari jawaban nate c menggunakan fungsi windowing dan klausa OVER. Cukup menarik, jawaban itu kembali ke subqueries dengan referensi eksternal. Dimungkinkan untuk menyelesaikan konsolidasi baris menggunakan level lain dari fungsi windowing. Ini mungkin tidak terlihat terlalu cantik, tapi saya menganggapnya lebih efisien karena menggunakan logika built-in dari fungsi windowing yang kuat.

Saya menyadari dari solusi nate bahwa set awal baris sudah menghasilkan flag yang diperlukan untuk 1) memilih nilai rentang mulai & berakhir DAN 2) untuk menghilangkan baris tambahan di antaranya. Kueri telah membuat subqueries dua mendalam hanya karena keterbatasan fungsi windowing, yang membatasi bagaimana alias kolom dapat digunakan. Secara logis saya bisa menghasilkan hasilnya hanya dengan satu subquery bersarang.

Beberapa catatan lain : Berikut ini adalah kode untuk SQLite3. Dialek SQLite berasal dari postgresql, sehingga sangat mirip dan bahkan dapat bekerja tanpa diubah. Saya menambahkan batasan pembingkaian pada klausa OVER, karena fungsi lag()dan lead()hanya perlu satu baris jendela, sebelum dan sesudah masing-masing (sehingga tidak perlu untuk menjaga set default semua baris sebelumnya). Saya juga memilih nama-nama firstdan lastkarena kata enditu dicadangkan.

create temp view test as 
with cte(name, int) AS (
select * from ( values ('foo', 2),
              ('foo', 3),
              ('foo', 4),
              ('foo', 10),
              ('foo', 11),
              ('foo', 13),
              ('bar', 1),
              ('bar', 2),
              ('bar', 3) ))
select * from cte;


SELECT name,
       int AS first, 
       endpoint AS last,
       (endpoint - int + 1) AS span
FROM ( SELECT name, 
             int, 
             CASE WHEN prev <> 1 AND next <> -1 -- orphan
                  THEN int
                WHEN next = -1 -- start of range
                  THEN lead(int) OVER (PARTITION BY name 
                                       ORDER BY int 
                                       ROWS BETWEEN CURRENT ROW AND 1 FOLLOWING)
                ELSE null END
             AS endpoint
        FROM ( SELECT name, 
                   int,
                   coalesce(int - lag(int) OVER (PARTITION BY name 
                                                 ORDER BY int 
                                                 ROWS BETWEEN 1 PRECEDING AND CURRENT ROW), 
                            0) AS prev,
                   coalesce(int - lead(int) OVER (PARTITION BY name 
                                                  ORDER BY int 
                                                  ROWS BETWEEN CURRENT ROW AND 1 FOLLOWING),
                            0) AS next
              FROM test
            ) AS mark_boundaries
        WHERE NOT (prev = 1 AND next = -1) -- discard values within range
      ) as raw_ranges
WHERE endpoint IS NOT null
ORDER BY name, first

Hasilnya sama seperti jawaban lainnya, seperti yang diharapkan:

 name | first | last | span
------+-------+------+------
 bar  |     1 |    3 |   3
 foo  |     2 |    4 |   3
 foo  |    10 |   11 |   2
 foo  |    13 |   13 |   1