Wählen Sie die längste fortlaufende Sequenz

12

Ich versuche, eine Abfrage in PostgreSQL 9.0 zu erstellen, die die längste Folge von fortlaufenden Zeilen für eine bestimmte Spalte abruft.

Betrachten Sie die folgende Tabelle:

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

Wo lap_noist für jeden einzigartig (race_id, car_type).

Ich möchte, dass die Abfrage die längste Sequenz für eine gegebene race_idund gibt car_type, also eine int(oder lange), die am höchsten ist.

Mit folgenden Daten:

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

Für car_type = red and race_id = 1die Abfrage würde 5als längste Sequenz des lap_noFeldes zurückkehren.

Ich habe hier eine ähnliche Frage gefunden, aber meine Situation ist etwas unkomplizierter.

(Ich würde auch gerne die längste Sequenz für car_typealle Rennen kennen, hatte aber vor, das selbst herauszufinden.)

DaveB
quelle

Antworten:

20

Ihre Beschreibung führt zu einer Tabellendefinition wie dieser:

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

Allgemeine Lösung für diese Klasse von Problemen

Um die längste Sequenz zu erhalten (1 Ergebnis, längste von allen, willkürliche Auswahl bei Gleichstand):

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)Es zählt nur TRUE(= Schritt zur nächsten Gruppe), was für jede neue Gruppe eine neue Nummer ergibt.

Verwandte Frage zu SO, eine Antwort mit einer prozeduralen Lösung mit plpgsql :

Wenn die höchste Anforderung die Leistung ist, ist die Funktion plpgsql in diesem speziellen Fall in der Regel schneller, da sie das Ergebnis in einem einzigen Scan berechnen kann.

Schneller für fortlaufende Nummern

Wir können die Tatsache nutzen, dass fortlaufend lap_no eine Sequenz definiert wird, um eine viel einfachere und schnellere Version zu erhalten :

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;

Aufeinanderfolgende Runden enden im selben grp. Jede fehlende Runde führt zu einer niedrigeren grppro Partition.

Das hängt vom (race_id, car_type, lap_no)Sein ab UNIQUE NOT NULL. NULL-Werte oder Duplikate können die Logik zerstören.

Diskussion über Jacks einfachere Alternative

@ Jack-Version effektiv alle Runden (Zeilen) zählt , wo die vorherige lap_noin dieser race_iddie gleiche hatte car_type. Das ist einfacher und schneller und korrekter - solange jede Sequenz car_typenur eine pro haben kann race_id.

Aber für eine so einfache Aufgabe könnte die Abfrage noch einfacher sein. Es würde logischerweise folgen, dass alle lap_nopro (car_type, race_id)der Reihe nach sein müssen , und wir könnten nur die Runden zählen:

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

Wenn auf der anderen Seite eine car_typehaben kann mehrere separate Sequenzen pro race_id (und die Frage nichts anderes ergibt), Jack-Version fehl.

Schneller für einen bestimmten Renntyp

Als Antwort auf den Kommentar / die Erläuterungen in der Frage: Wenn Sie die Abfrage auf einen bestimmten (race_id, car_type) Wert beschränken, wird sie natürlich viel schneller :

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 <> hier fummeln
Old SQL Fiddle

Index

Der Schlüssel zur Spitzenleistung ist ein passender Index (mit Ausnahme der erwähnten prozeduralen Lösung, die mit einem einzelnen sequentiellen Scan arbeitet). Ein mehrspaltiger Index wie dieser ist am besten geeignet :

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

Wenn Ihre Tabelle UNIQUEdie oben angenommene Einschränkung aufweist, wird diese intern nur mit diesem (eindeutigen) Index implementiert, und Sie müssen keinen weiteren Index erstellen.

Erwin Brandstetter
quelle
Hallo Erwin, danke, das macht den Job, aber es dauert ~ 17sec in meiner Datenbank! Nehmen Sie nicht an, Sie könnten eine Modifikation bereitstellen, sodass race_id und car_type als Parameter verwendet werden, anstatt die gesamte Tabelle zu vergleichen? (Ich habe versucht, es neu zu schreiben und
laufe
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 sagt, versuchen Sie es mit topanswers.xyz
quelle
oder vielleicht, sum((lap_no=(prev+1))::integer)+1aber ich bin mir nicht sicher, ob das einfacher zu lesen ist
sagt Jack, versuche topanswers.xyz