Wählen Sie effizient den Anfang und das Ende mehrerer zusammenhängender Bereiche in der Postgresql-Abfrage aus

Ich habe ungefähr eine Milliarde Datenzeilen in einer Tabelle mit einem Namen und einer Ganzzahl im Bereich von 1-288. Für einen bestimmten Namen ist jedes int eindeutig, und nicht jede mögliche Ganzzahl im Bereich ist vorhanden - daher gibt es Lücken.

Diese Abfrage generiert einen Beispielfall:

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

Ich möchte eine Nachschlagetabelle mit einer Zeile für jeden Namen und jede Folge zusammenhängender Ganzzahlen generieren. Jede solche Zeile würde enthalten:

Name - der Wert des Namens
Spaltenstart - die erste Ganzzahl in der zusammenhängenden Sequenz
Ende - der letzte Wert in der zusammenhängenden Sequenz
Spanne - Ende - Anfang + 1

Diese Abfrage generiert eine Beispielausgabe für das obige Beispiel:

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

Weil ich so viele Zeilen habe, ist effizienter besser. Das heißt, ich muss diese Abfrage nur einmal ausführen, es ist also nicht unbedingt erforderlich.

Danke im Voraus!

Bearbeiten:

Ich sollte hinzufügen, dass PL / pgSQL-Lösungen willkommen sind (bitte erläutern Sie alle Fancy Tricks - ich bin noch neu in PL / pgSQL).

Wie wäre es mit with recursive

Testansicht:

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

Abfrage:

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;

Ergebnis:

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

Es würde mich interessieren, wie sich das auf Ihre Milliardenzeilentabelle auswirkt.

Sie können dies mit Fensterfunktionen tun. Die Grundidee ist , zu verwenden leadund lagFunktionen Windowing Reihen vor zu ziehen und hinter der aktuellen Zeile. Dann können wir berechnen, ob wir den Anfang oder das Ende der Sequenz haben:

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)

(Ich habe eine Ansicht verwendet, damit die Logik unten leichter zu befolgen ist.) Jetzt wissen wir also, ob die Zeile ein Anfang oder ein Ende ist. Wir müssen das in einer Reihe zusammenfassen:

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)

Sieht für mich richtig aus :)

Eine weitere Lösung für Fensterfunktionen. Keine Ahnung von Effizienz, ich habe den Ausführungsplan am Ende hinzugefügt (obwohl es bei so wenigen Zeilen wahrscheinlich keinen großen Wert hat). Wenn Sie herumspielen wollen: SQL-Fiddle-Test

Tabelle und Daten:

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

Abfrage:

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
 ; 

Abfrageplan

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)

Unter SQL Server würde ich eine weitere Spalte mit dem Namen previousInt hinzufügen:

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

Ich würde eine CHECK-Einschränkung verwenden, um sicherzustellen, dass previousInt <int und eine FK-Einschränkung (name, previousInt) auf (name, int) verweisen, und ein paar weitere Einschränkungen, um die wasserdichte Datenintegrität sicherzustellen. Die Auswahl von Lücken ist dabei trivial:

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

Um dies zu beschleunigen, könnte ich einen gefilterten Index erstellen, der nur Lücken enthält. Dies bedeutet, dass alle Ihre Lücken vorberechnet werden, sodass die Auswahl sehr schnell erfolgt und Einschränkungen die Integrität Ihrer vorberechneten Daten sicherstellen. Ich benutze solche Lösungen oft, sie sind überall auf meinem System.

Sie können nach der Tabibitosan-Methode suchen:

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/

Grundsätzlich gilt:

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.

Ich finde diese Leistung besser:

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

ein grober Plan:

• Wählen Sie das Minimum für jeden Namen (nach Namen gruppieren)
• Wählen Sie für jeden Namen das Minimum2 aus, wobei min2> min1 und nicht vorhanden ist (Unterabfrage: SEL min2-1).
• Wählen Sie max val1> min val1, wobei max val1 <min val2.

Wiederholen Sie den Vorgang ab 2., bis keine Aktualisierung mehr erfolgt. Von da an wird es kompliziert, Gordian, mit einer Gruppierung über max. Ich würde wohl eine Programmiersprache wählen.

PS: Eine schöne Beispieltabelle mit ein paar Beispielwerten wäre in Ordnung, die von jedem verwendet werden könnte, so dass nicht jeder seine Testdaten von Grund auf neu erstellt.

Diese Lösung ist inspiriert von Antwort nate c unter Verwendung von Fensterfunktionen und der OVER-Klausel. Interessanterweise kehrt diese Antwort zu Unterabfragen mit externen Referenzen zurück. Es ist möglich, die Zeilenkonsolidierung mit einer anderen Ebene von Fensterfunktionen abzuschließen. Es mag nicht besonders hübsch aussehen, aber ich gehe davon aus, dass es effizienter ist, da es die integrierte Logik der leistungsstarken Fensterfunktionen nutzt.

Ich erkannte aus Nates Lösung, dass der Anfangssatz von Zeilen bereits die erforderlichen Flags erzeugt hatte, um 1) die Werte für den Start- und Endbereich auszuwählen UND 2) die zusätzlichen Zeilen dazwischen zu eliminieren. In der Abfrage sind Unterabfragen nur aufgrund von Einschränkungen der Fensterfunktionen, die die Verwendung von Spaltenaliasnamen einschränken, zwei Mal tief verschachtelt. Logischerweise hätte ich die Ergebnisse mit nur einer verschachtelten Unterabfrage erzeugen können.

Ein paar andere Hinweise : Das Folgende ist Code für SQLite3. Der SQLite-Dialekt ist von postgresql abgeleitet, ist also sehr ähnlich und funktioniert möglicherweise sogar unverändert. Ich habe die OVER-Klauseln um Rahmeneinschränkungen erweitert, da die lag()und lead()-Funktionen vor bzw. nach jeweils nur ein einziges Zeilenfenster benötigen (es war also nicht erforderlich, den Standardsatz aller vorhergehenden Zeilen beizubehalten). Ich habe mich auch für die Namen entschieden firstund lastda ist das Wort endreserviert.

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

Die Ergebnisse sind genau wie die anderen Antworten, wie man erwartet:

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