Skutecznie wybierz początek i koniec wielu ciągłych zakresów w zapytaniu Postgresql

Mam około miliarda wierszy danych w tabeli z nazwą i liczbą całkowitą z zakresu 1-288. Dla danej nazwy , każdy int jest wyjątkowy, a nie każdy możliwy całkowitą w przedziale jest obecny - tak istnieją luki.

To zapytanie generuje przykładowy przypadek:

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

Chciałbym wygenerować tablicę przeglądową z wierszem dla każdej nazwy i sekwencji ciągłych liczb całkowitych. Każdy taki wiersz zawierałby:

Nazwa - wartość nazwa kolumny
początku - pierwszy całkowitą w ciągłej sekwencji
końca - wartość końcowa w ciągłej sekwencji
rozpiętości - koniec - początek + 1

To zapytanie generuje przykładowe dane wyjściowe dla powyższego przykładu:

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

Ponieważ mam tak wiele wierszy, bardziej wydajne jest lepsze. To powiedziawszy, muszę uruchomić to zapytanie tylko raz, więc nie jest to absolutny wymóg.

Z góry dziękuję!

Edytować:

Powinienem dodać, że rozwiązania PL / pgSQL są mile widziane (proszę wyjaśnić wszelkie fantazyjne sztuczki - wciąż jestem nowy w PL / pgSQL).

Co powiesz na używanie with recursive

widok testu:

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

pytanie:

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;

wynik:

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

Byłbym zainteresowany, aby dowiedzieć się, jak to działa w tabeli miliardów wierszy.

Możesz to zrobić za pomocą funkcji okienkowania. Podstawową ideą jest użycie leadi lagokienkowanie funkcji do ciągnięcia rzędów przed i za bieżącym rzędem. Następnie możemy obliczyć, jeśli mamy początek lub koniec sekwencji:

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)

(Użyłem widoku, więc logikę łatwiej będzie śledzić poniżej.) Teraz wiemy, czy rząd jest początkiem czy końcem. Musimy zwinąć to w wiersz:

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)

Dla mnie wygląda poprawnie :)

Kolejne rozwiązanie funkcji okna. Nie mam pojęcia o wydajności, na końcu dodałem plan wykonania (chociaż z tak małą liczbą wierszy, prawdopodobnie nie ma on dużej wartości). Jeśli chcesz się pobawić: test Fiddle SQL

Tabela i dane:

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

Pytanie:

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
 ; 

Plan zapytań

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)

Na SQL Server dodałbym jeszcze jedną kolumnę o nazwie previousInt:

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

Użyłbym ograniczenia CHECK, aby upewnić się, że previousInt <int i ograniczenie FK (name, previousInt) odnoszą się do (name, int) i kilka innych ograniczeń w celu zapewnienia wodoszczelności integralności danych. To zrobione, wybór luk jest banalny:

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

Aby przyspieszyć, mogę utworzyć filtrowany indeks, który zawierałby tylko luki. Oznacza to, że wszystkie luki są wstępnie obliczone, więc selekcje są bardzo szybkie, a ograniczenia zapewniają integralność wstępnie obliczonych danych. Często używam takich rozwiązań, są one w całym moim systemie.

Możesz poszukać metody 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/

Gruntownie:

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.

Myślę, że ten występ lepiej:

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

szorstki plan:

• Wybierz minimum dla każdej nazwy (grupa po nazwie)
• Wybierz minimum2 dla każdej nazwy, gdzie min2> min1 i nie istnieje (podzapytanie: SEL min2-1).
• Sel max val1> min val1 gdzie max val1 <min val2.

Powtarzaj od 2., aż nie będzie więcej aktualizacji. Stamtąd komplikuje się, Gordian, z grupowaniem powyżej maks. Min i maks. Min. Chyba wybrałbym język programowania.

PS: Ładna tabela próbek z kilkoma przykładowymi wartościami byłaby w porządku, z której mogliby korzystać wszyscy, więc nie wszyscy tworzą swoje dane testowe od zera.

To rozwiązanie jest inspirowane odpowiedzią Nate'a C przy użyciu funkcji okienkowania i klauzuli OVER. Co ciekawe, odpowiedź ta powraca do podkwerend z referencjami zewnętrznymi. Możliwe jest zakończenie konsolidacji wiersza za pomocą innego poziomu funkcji okienkowania. Może nie wygląda to zbyt ładnie, ale zakładam, że jest bardziej wydajny, ponieważ wykorzystuje wbudowaną logikę potężnych funkcji okienkowania.

Z rozwiązania Nate'a zdałem sobie sprawę, że początkowy zestaw wierszy już wytworzył niezbędne flagi do 1) wybrania początkowych i końcowych wartości zakresu ORAZ 2) w celu wyeliminowania dodatkowych wierszy pomiędzy nimi. W zapytaniu zagnieżdżono podzapytania dwa głębokie tylko ze względu na ograniczenia funkcji okienkowania, które ograniczają sposób użycia aliasów kolumn. Logicznie mogłem uzyskać wyniki tylko z jednym zagnieżdżonym podzapytaniem.

Kilka innych uwag : Poniżej znajduje się kod SQLite3. Dialekt SQLite pochodzi z postgresql, więc jest bardzo podobny i może nawet działać niezmieniony. Dodałem ograniczenie kadrowania do klauzul OVER, ponieważ funkcje lag()i lead()wymagają tylko okna jednorzędowego, odpowiednio przed i po (więc nie było potrzeby utrzymywania domyślnego zestawu wszystkich poprzednich wierszy). Zdecydowałem się również na nazwiska, firsta lastponieważ słowo endjest zastrzeżone.

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

Wyniki są takie same jak inne odpowiedzi, jak można się spodziewać:

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