Wybierz najdłuższą ciągłą sekwencję

Próbuję zbudować zapytanie w PostgreSQL 9.0, które pobiera najdłuższą sekwencję ciągłych wierszy dla określonej kolumny.

Rozważ następującą tabelę:

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

Gdzie lap_nojest unikalny dla każdego (race_id, car_type).

Chciałbym z zapytania najdłuższy sekwencja dana race_ida car_type, więc nie zwracać int(lub długości), która jest największa.

Z następującymi danymi:

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

Dla car_type = red and race_id = 1zapytania wróci 5jak najdłuższej sekwencji lap_nodziedzinie.

Znalazłem tutaj podobne pytanie , jednak moja sytuacja jest nieco prostsza.

_{(Chciałbym również znać najdłuższą sekwencję dla danego car_typewyścigu, ale planowałem to samodzielnie.)}

Twój opis daje następującą definicję tabeli :

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

Ogólne rozwiązanie dla tej klasy problemów

Aby uzyskać najdłuższą sekwencję (1 wynik, najdłuższy ze wszystkich, arbitralny wybór, jeśli istnieją remisy):

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)liczy się tylko TRUE(= krok do następnej grupy), co daje nową liczbę dla każdej nowej grupy.

Powiązane pytanie dotyczące SO, jedna odpowiedź zawierająca rozwiązanie proceduralne z plpgsql :

• GROUP BY i agreguj kolejne wartości liczbowe

Jeśli najwyższym wymaganiem jest wydajność, funkcja plpgsql jest zazwyczaj szybsza w tym konkretnym przypadku, ponieważ może obliczyć wynik w jednym skanie.

Szybciej dla kolejnych numerów

Możemy wykorzystać fakt, że kolejne lap_no definiują sekwencję dla znacznie prostszej i szybszej wersji :

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;

Kolejne okrążenia kończą się tak samo grp. Każde brakujące okrążenie powoduje zmniejszenie grpliczby partycji.

To zależy od (race_id, car_type, lap_no)bycia UNIQUE NOT NULL. Wartości NULL lub duplikaty mogą uszkodzić logikę.

Omówienie prostszej alternatywy Jacka

@ Wersja Jacka skutecznie zlicza wszystkie okrążenia (wiersze), gdzie poprzednie lap_now ten race_idmiał takie same car_type. To jest prostsze, szybsze i poprawne - o ile każdy car_typemoże mieć tylko jedną sekwencję na race_id.

Jednak w przypadku tak prostego zadania zapytanie może być jeszcze prostsze. Logiczne byłoby, że wszystkie lap_nona (car_type, race_id)muszą być w sekwencji , i moglibyśmy po prostu policzyć okrążenia:

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

Z drugiej strony, jeśli car_typemożna mieć wiele oddzielnych sekwencji na identyfikator_ wyścigu (a pytanie nie określa inaczej), wersja Jacka się nie powiedzie.

Szybciej dla danego typu wyścigu / samochodu

W odpowiedzi na komentarz / wyjaśnienia w pytaniu: ograniczenie zapytania do jednego (race_id, car_type) poda go , oczywiście, znacznie szybciej :

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 <> skrzypce tutaj
Old SQL Fiddle

Indeks

Kluczem do najwyższej wydajności jest indeks dopasowania (z wyjątkiem wspomnianego rozwiązania proceduralnego pracującego z pojedynczym skanem sekwencyjnym). Taki indeks wielokolumnowy najlepiej służy:

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

Jeśli twoja tabela ma UNIQUEograniczenie, które założyłem u góry, jest ono implementowane tylko z tym (unikalnym) indeksem wewnętrznie i nie musisz tworzyć kolejnego indeksu.

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|
*/