Sélectionner la séquence continue la plus longue

12

J'essaie de construire une requête dans PostgreSQL 9.0 qui obtient la plus longue séquence de lignes continues pour une colonne spécifique.

Considérez le tableau suivant:

lap_id (serial), lap_no (int), car_type (enum), race_id (int FK)

lap_noest unique pour chacun (race_id, car_type).

Je voudrais que la requête produise la séquence la plus longue pour une donnée race_idet car_type, ainsi, elle retournerait une int(ou une longue) qui est la plus élevée.

Avec les données suivantes:

1, 1, red, 1
2, 2, red, 1
3, 3, red, 1
4, 4, red, 1
5, 1, blue, 1
6, 5, red, 1
7, 2, blue, 1
8, 1, green, 1

Car car_type = red and race_id = 1la requête retournerait 5comme la séquence la plus longue du lap_nochamp.

J'ai trouvé une question similaire ici, mais ma situation est un peu plus simple.

(Je voudrais également connaître la séquence la plus longue pour une donnée car_typepour toutes les races, mais je prévoyais de régler cela moi-même.)

DaveB
la source

Réponses:

20

Votre description donne une définition de table comme celle-ci:

CREATE TABLE tbl (
   lap_id   serial PRIMARY KEY
 , lap_no   int NOT NULL
 , car_type enum NOT NULL
 , race_id  int NOT NULL  -- REFERENCES ...
 , UNIQUE(race_id, car_type, lap_no)
);

Solution générale pour cette classe de problèmes

Pour obtenir la séquence la plus longue (1 résultat, le plus long de tous, choix arbitraire s'il y a des liens):

SELECT race_id, car_type, count(*) AS seq_len
FROM  (
   SELECT *, count(*) FILTER (WHERE step)
                      OVER (ORDER BY race_id, car_type, lap_no) AS grp
   FROM  (
      SELECT *, (lag(lap_no) OVER (PARTITION BY race_id, car_type ORDER BY lap_no) + 1)
                 IS DISTINCT FROM lap_no AS step
      FROM   tbl
      ) x
   ) y
GROUP  BY race_id, car_type, grp
ORDER  BY seq_len DESC
LIMIT  1;

count(*) FILTER (WHERE step)ne compte que TRUE(= pas au groupe suivant), ce qui donne un nouveau numéro pour chaque nouveau groupe.

Question connexe sur SO, une réponse présentant une solution procédurale avec plpgsql :

Si la principale exigence est la performance, la fonction plpgsql est généralement plus rapide dans ce cas particulier car elle peut calculer le résultat en une seule analyse.

Plus rapide pour les numéros consécutifs

On peut capitaliser sur le fait que consécutivement lap_no définir une séquence, pour une version beaucoup plus simple et plus rapide :

SELECT race_id, car_type, count(*) AS seq_len
FROM  (
   SELECT race_id, car_type
        , row_number() OVER (PARTITION BY race_id, car_type ORDER BY lap_no) - lap_no AS grp
   FROM   tbl
   ) x
GROUP  BY race_id, car_type, grp
ORDER  BY seq_len DESC
LIMIT  1;

Des tours consécutifs finissent dans le même grp. Chaque tour manquant entraîne une baisse grppar partition.

Cela repose sur l' (race_id, car_type, lap_no)être UNIQUE NOT NULL. Les valeurs NULL ou les doublons peuvent briser la logique.

Discussion sur l'alternative plus simple de Jack

@ Version de Jack compte efficacement tous les tours (lignes) où le précédent lap_nodans ce race_idavaient le même car_type. C'est plus simple, plus rapide et correct - tant que chacun car_typene peut avoir qu'une seule séquence par race_id.

Mais pour une tâche aussi simple, la requête pourrait être encore plus simple. Il serait logique que tous les suivre lap_nopar (car_type, race_id)doit être dans l' ordre , et nous pouvions compter les tours:

SELECT race_id, car_type, count(*) AS seq_len
FROM   tbl
GROUP  BY race_id, car_type
ORDER  BY seq_len DESC
LIMIT  1;

Si, d'autre part, on car_typepeut avoir plusieurs séquences distinctes par race_id (et la question ne spécifie pas le contraire), la version de Jack échouera.

Plus rapide pour un type de course / voiture donné

En réponse aux commentaires / clarifications de la question: restreindre la requête à une donnée la (race_id, car_type) rendra beaucoup plus rapide , bien sûr:

SELECT count(*) AS seq_len
FROM  (
   SELECT row_number() OVER (ORDER BY lap_no) - lap_no AS grp
   FROM   tbl
   WHERE  race_id = 1
   AND    car_type = 'red'
   ) x
GROUP  BY grp
ORDER  BY seq_len DESC
LIMIT  1;

db <> violon ici
Old SQL Fiddle

Indice

La clé des meilleures performances est un index approprié (sauf pour la solution procédurale mentionnée fonctionnant avec un seul balayage séquentiel). Un index multicolonne comme celui-ci sert mieux:

CREATE INDEX tbl_mult_idx ON tbl (race_id, car_type, lap_no);

Si votre table a la UNIQUEcontrainte que j'ai supposée en haut, celle-ci est implémentée avec uniquement cet index (unique) en interne, et vous n'avez pas besoin de créer un autre index.

Erwin Brandstetter
la source
Salut Erwin, merci qui fait le travail, mais cela prend ~ 17sec sur ma base de données! Ne supposez pas que vous pourriez apporter une modification afin qu'il prenne race_id et car_type comme paramètres plutôt que de comparer la table entière? (J'ai essayé de le
réécrire
7

create table tbl (lap_no int, car_type text, race_id int);
insert into tbl values (1,'red',1),(2,'red',1),(3,'red',1),(4,'red',1),
                       (1,'blue',1),(5,'red',1),(2,'blue',1),(1,'green',1);
select car_type, race_id, sum(case when lap_no=(prev+1) then 1 else 0 end)+1 seq_len
from ( select *, lag(lap_no) over (partition by car_type, race_id order by lap_no) prev 
       from tbl ) z
group by car_type, race_id
order by seq_len desc limit 1;
/*
|car_type|race_id|seq_len|
|:-------|------:|------:|
|red     |      1|      5|
*/
Jack dit d'essayer topanswers.xyz
la source
ou peut-être sum((lap_no=(prev+1))::integer)+1mais je ne suis pas sûr que ce soit plus facile à lire
Jack dit d'essayer topanswers.xyz