Selecione a sequência contínua mais longa

12

Eu estou tentando construir uma consulta no PostgreSQL 9.0 que obtém a maior seqüência de linhas contínuas para uma coluna específica.

Considere a seguinte tabela:

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

Onde lap_noé único para cada um (race_id, car_type).

Gostaria que a consulta produzisse a sequência mais longa para um dado race_ide car_type, portanto, retornaria um int(ou longo) maior.

Com os seguintes dados:

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

Para car_type = red and race_id = 1a consulta retornaria 5como a sequência mais longa do lap_nocampo.

Encontrei uma pergunta semelhante aqui, no entanto, minha situação é um pouco mais direta.

(Eu também gostaria de saber a sequência mais longa de um dado car_typepara todas as corridas, mas planejava resolver isso sozinha.)

DaveB
fonte

Respostas:

20

Sua descrição resulta em uma definição de tabela como esta:

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

Solução geral para esta classe de problemas

Para obter a sequência mais longa (1 resultado, o mais longo de todos, escolha arbitrária se houver empate):

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)conta apenas TRUE(= passo para o próximo grupo), o que resulta em um novo número para cada novo grupo.

Pergunta relacionada ao SO, uma resposta que apresenta uma solução procedural com o plpgsql :

Se o principal requisito for o desempenho, a função plpgsql normalmente é mais rápida nesse caso específico, pois pode calcular o resultado em uma única varredura.

Mais rápido para números consecutivos

Podemos capitalizar o fato de definir consecutivamente lap_no uma sequência, para uma versão muito mais simples e rápida :

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;

Voltas consecutivas acabam no mesmo grp. Cada volta faltando resulta em uma menor grppor partição.

Isso depende de (race_id, car_type, lap_no)ser UNIQUE NOT NULL. Valores nulos ou duplicatas podem quebrar a lógica.

Discussão da alternativa mais simples de Jack

@ Versão de Jack conta efetivamente todas as voltas (linhas), onde o anterior lap_nonesta race_idtinham o mesmo car_type. Isso é mais simples, rápido e correto - desde que cada um car_typepossa ter apenas uma sequência por race_id.

Mas, para uma tarefa tão simples, a consulta ainda pode ser mais simples. Segue-se logicamente que todos os lap_nopor (car_type, race_id)devem estar em sequência , e poderíamos apenas contar as voltas:

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

Se, por outro lado, é car_typepossível ter várias seqüências separadas por race_id (e a pergunta não especificar de outra forma), a versão de Jack falhará.

Mais rápido para um determinado tipo de corrida / carro

Em resposta ao comentário / esclarecimentos da pergunta: restringir a consulta a uma dada (race_id, car_type) tornará muito mais rápido , é claro:

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 <> mexer aqui
Old SQL Fiddle

Índice

A chave para o desempenho superior é um índice adequado (exceto para a solução processual mencionada que trabalha com uma única varredura seqüencial). Um índice de várias colunas como este serve melhor:

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

Se sua tabela tiver a UNIQUErestrição que assumi na parte superior, isso será implementado apenas com esse índice (exclusivo) internamente e você não precisará criar outro índice.

Erwin Brandstetter
fonte
Oi Erwin, obrigado por fazer o trabalho, porém demora ~ 17s no meu banco de dados! Não suponha que você possa fornecer uma modificação para que os parâmetros race_id e car_type sejam parâmetros, em vez de comparar a tabela inteira? (Eu tentei re escrevendo-lo e continuar correndo em erros)
DaveB
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 diz que tenta topanswers.xyz
fonte
ou, talvez, sum((lap_no=(prev+1))::integer)+1mas não tenho certeza de que é mais fácil de ler
Jack diz tentativa topanswers.xyz