Sélectionnez efficacement le début et la fin de plusieurs plages contiguës dans la requête Postgresql

J'ai environ un milliard de lignes de données dans une table avec un nom et un entier compris entre 1 et 288. Pour un nom donné , chaque int est unique, et non tout entier possible dans la plage est présente - donc il y a des lacunes.

Cette requête génère un exemple de cas:

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

Je voudrais générer une table de recherche avec une ligne pour chaque nom et séquence d'entiers contigus. Chacune de ces lignes contiendrait:

nom - la valeur du début de la colonne de nom - le premier entier de la fin de séquence contiguë - la valeur finale dans la plage de séquence contiguë -


fin - début + 1

Cette requête génère un exemple de sortie pour l'exemple ci-dessus:

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

Parce que j'ai tellement de lignes, plus efficace c'est mieux. Cela dit, je ne dois exécuter cette requête qu'une seule fois, ce n'est donc pas une exigence absolue.

Merci d'avance!

Éditer:

Je dois ajouter que les solutions PL / pgSQL sont les bienvenues (veuillez expliquer toutes les astuces - je suis encore nouveau sur PL / pgSQL).

Que diriez-vous d'utiliser with recursive

vue de test:

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

requete:

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;

résultat:

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

Je serais intéressé de savoir comment cela fonctionne sur votre table de milliards de lignes.

Vous pouvez le faire avec des fonctions de fenêtrage. L'idée de base est d'utiliser leadet de lagfonctions de fenêtrage pour tirer des lignes avant et en arrière de la ligne actuelle. Ensuite, nous pouvons calculer si nous avons le début ou la fin de la séquence:

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)

(J'ai utilisé une vue pour que la logique soit plus facile à suivre ci-dessous.) Alors maintenant, nous savons si la ligne est un début ou une fin. Nous devons réduire cela en ligne:

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)

Ça me semble correct :)

Une autre solution de fonction de fenêtre. Aucune idée de l'efficacité, j'ai ajouté le plan d'exécution à la fin (bien qu'avec si peu de lignes, il n'a probablement pas beaucoup de valeur). Si vous voulez jouer: test SQL-Fiddle

Tableau et données:

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

Requete:

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 de requête

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)

Sur SQL Server, j'ajouterais une autre colonne nommée 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")

J'utiliserais une contrainte CHECK pour m'assurer que previousInt <int, et une contrainte FK (nom, previousInt) font référence à (nom, int), et quelques contraintes supplémentaires pour garantir l'intégrité des données étanche. Cela fait, la sélection des écarts est triviale:

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

Pour l'accélérer, je pourrais créer un index filtré qui n'inclurait que les lacunes. Cela signifie que toutes vos lacunes sont précalculées, les sélections sont donc très rapides et les contraintes garantissent l'intégrité de vos données précalculées. J'utilise beaucoup de telles solutions, elles sont partout dans mon système.

Vous pouvez rechercher la méthode 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/

Fondamentalement:

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.

Je pense que cette performance est meilleure:

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

un plan approximatif:

• Sélectionnez le minimum pour chaque nom (grouper par nom)
• Sélectionnez le minimum2 pour chaque nom, où min2> min1 et n'existe pas (sous-requête: SEL min2-1).
• Sel max val1> min val1 où max val1 <min val2.

Répétez de 2. jusqu'à ce qu'aucune mise à jour ne se produise. À partir de là, cela se complique, Gordien, avec un regroupement sur max de min et min de max. Je suppose que j'irais pour un langage de programmation.

PS: Un joli exemple de table avec quelques valeurs d'échantillon serait bien, ce qui pourrait être utilisé par tout le monde, donc tout le monde ne crée pas ses données de test à partir de zéro.

Cette solution est inspirée de la réponse de nate c en utilisant les fonctions de fenêtrage et la clause OVER. Chose intéressante, cette réponse revient aux sous-requêtes avec des références externes. Il est possible de terminer la consolidation de ligne en utilisant un autre niveau de fonctions de fenêtrage. Il peut ne pas sembler trop joli, mais je suppose qu'il est plus efficace car il utilise la logique intégrée des puissantes fonctions de fenêtrage.

J'ai réalisé à partir de la solution de nate que l'ensemble initial de lignes avait déjà produit des drapeaux nécessaires pour 1) sélectionner les valeurs de plage de début et de fin ET 2) pour éliminer les lignes supplémentaires entre les deux. La requête a imbriqué des sous-requêtes à deux profondeurs uniquement en raison des limitations des fonctions de fenêtrage, qui limitent la façon dont les alias de colonne peuvent être utilisés. Logiquement, j'aurais pu produire les résultats avec une seule sous-requête imbriquée.

Quelques autres notes : Le code suivant est pour SQLite3. Le dialecte SQLite est dérivé de postgresql, il est donc très similaire et peut même fonctionner sans modification. J'ai ajouté une restriction de cadrage aux clauses OVER, car les fonctions lag()et lead()n'ont besoin que d'une fenêtre à une seule ligne, respectivement avant et après (il n'était donc pas nécessaire de conserver l'ensemble par défaut de toutes les lignes précédentes). J'ai aussi opté pour les noms firstet lastpuisque le mot endest réservé.

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

Les résultats sont comme les autres réponses, comme on s'y attend:

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