Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

I am trying to construct a query in PostgreSQL 9.0 that gets the longest sequence of continuous rows for a specifc field.

Consider the following table:

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

Where lap_no is unique for each race

With the following data:

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

So for car_type = red and race_id = 1 the query would return 5 as the longest sequence of the lap_no field.

I found a similar question here however my situation is a bit more straightforward.

CLARIFICATION:

I would like the query to produce the longest sequence for a given race_id and car_type, so it would return an int (or long) that is highest.

(I would also like to know the longest sequence for a given car_type for all races, but I was planning on working that out myself.)

share|improve this question
1  
The longest sequence for one race? Or the longest sequence for all races? How do you want to deal with multiple equally highest sequences per race? Pick one, if yes, which? Or pick all so you can have multiple sequences per race? What should the result look like, exactly? Just the highest number? –  Erwin Brandstetter Feb 25 '13 at 17:57
    
see clarification above –  DaveB Feb 25 '13 at 18:23
3  
A reminder for those who marked this question OT: The first chapter of the FAQ clearly says otherwise: Advanced Querying including window-functions dynamic-sql and query-performance –  Erwin Brandstetter Feb 26 '13 at 0:05
add comment

2 Answers 2

up vote 4 down vote accepted

General solution for this class of problems

To get the longest sequence (1 result, longest of all, arbitrary pick if there are ties):

SELECT race_id, car_type, count(*) AS seq_len
FROM  (
   SELECT *, count(step OR NULL) 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
   ORDER BY race_id, car_type, lap_no
   ) y
GROUP  BY race_id, car_type, grp
ORDER  BY seq_len DESC
LIMIT  1;

SQLfiddle.

Why count(step OR NULL)? We only want to count TRUE (= step to next group).
FALSE OR NULL yields NULL
TRUE OR NULL yields TRUE
And count() only counts non-null values.

Find more under this related question on SO, including a similar procedural solution with plpgsql. If your top requirement is performance, the plpgsql function will be faster, because it can calculate the result in a single scan. But also see specialized faster query and the chapter on indexes below.

Discussion of Jack's simpler alternative

@Jack's version effectively counts all laps (rows) where the previous lap_no in this race_id had the same car_type. That's simpler and faster and correct - as long as each car_type can only have one sequence per race_id.

But for a task that simple the query could be even simpler. It would follow logically that all lap_no per (car_type, race_id) must be in sequence, and we could just count the laps:

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

If, on the other hand, one car_type can have multiple distinct sequences per *race_id* (and the question does not specify otherwise), Jack's version will fail.

Simpler and faster for consecutive numbers

We can capitalize on the fact that consecutive lap_no define a sequence for a much simpler and faster version:

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

Consecutive laps end up with the same grp. Every missing lap results in a lower grp. Much faster, but a plpgsql version may be faster, yet.

SQLfiddle demonstrating how the simple version fails with multiple sequences and the new version works.

Answer to question in comment / clarification in Q

Narrowing down the query to a given (race_id, car_type) will make it much faster, of course:

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;

Index

Key to top performance for any of these solutions are fitting indexes. A multicolumn index like this should serve you very well:

CREATE INDEX tbl_mult_idx ON tbl (race_id, car_type, lap_no)
share|improve this answer
    
Hi Erwin, thanks that does the job, however it takes ~17sec on my database! Dont suppose you could provide a modification so it takes race_id and car_type as parameters rather than comparing the entire table? (I have tried re-writing it and keep running into errors) –  DaveB Feb 25 '13 at 19:28
    
I can't work out if my answer is the same as yours? –  Jack Douglas Feb 25 '13 at 19:55
    
@JackDouglas: I took a closer look. The devil is in the details. –  Erwin Brandstetter Feb 25 '13 at 23:59
    
@DaveB: Something for you in the updated answer. –  Erwin Brandstetter Feb 26 '13 at 0:13
    
@ErwinBrandstetter fantastic, thanks –  DaveB Feb 26 '13 at 15:59
add comment
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;

SQLFiddle here

share|improve this answer
    
or perhaps sum((lap_no=(prev+1))::integer)+1 but I'm not sure that is easier to read –  Jack Douglas Feb 25 '13 at 20:08
    
It's not so much method how you count/sum, but what you count. –  Erwin Brandstetter Feb 26 '13 at 0:01
    
Thanks, I see I provoked you into going into even greater depth :) are you interested in a little project to help out Jake Feasel and SQLFiddle? He's currently creating a new database for each pg fiddle and I think creating a schema might be sufficient (among other thoughts)? If you have the time/inclination please ping me in The Heap –  Jack Douglas Feb 26 '13 at 10:46
    
Great! I should have mentioned that there is no rush at all... –  Jack Douglas Feb 26 '13 at 13:50
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.