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 have some table with numbers like this (status is either FREE or ASSIGNED)

id_set  number  status         
-----------------------
1       000001  ASSIGNED
1       000002  FREE
1       000003  ASSIGNED
1       000004  FREE
1       000005  FREE
1       000006  ASSIGNED
1       000007  ASSIGNED
1       000008  FREE
1       000009  FREE
1       000010  FREE
1       000011  ASSIGNED
1       000012  ASSIGNED
1       000013  ASSIGNED
1       000014  FREE
1       000015  ASSIGNED

and I need to find "n" consecutive numbers, so for n = 3, query would return

1       000008  FREE
1       000009  FREE
1       000010  FREE

It should return only first possible group of each id_set (in fact, it would be executed only for id_set per query)

I was checking WINDOW functions, tried some queries like COUNT(id_number) OVER (PARTITION BY id_set ROWS UNBOUNDED PRECEDING), but that's all I got :) I couldn't think of logic, how to do that in Postgres.

I was thinking about creating virtual column using WINDOW functions counting preceding rows for every number where status = 'FREE', then select first number, where count is equal to my "n" number.

Or maybe group numbers by status, but only from one ASSIGNED to another ASSIGNED and select only groups containing at least "n" numbers

EDIT

I found this query (and changed it a little bit)

WITH q AS
(
  SELECT *,
         ROW_NUMBER() OVER (PARTITION BY id_set, status ORDER BY number) AS rnd,
         ROW_NUMBER() OVER (PARTITION BY id_set ORDER BY number) AS rn
  FROM numbers
)
SELECT id_set,
       MIN(number) AS first_number,
       MAX(number) AS last_number,
       status,
       COUNT(number) AS numbers_count
FROM q
GROUP BY id_set,
         rnd - rn,
         status
ORDER BY
     first_number

which produces groups of FREE/ASSIGNED numbers, but I would like to have all numbers from only first group which meets the condition

SQL Fiddle

share|improve this question
add comment

6 Answers

up vote 6 down vote accepted

This is a problem. Assuming there are no gaps or duplicates in the same id_set set:

WITH partitioned AS (
  SELECT
    *,
    number - ROW_NUMBER() OVER (PARTITION BY id_set) AS grp
  FROM atable
  WHERE status = 'FREE'
),
counted AS (
  SELECT
    *,
    COUNT(*) OVER (PARTITION BY id_set, grp) AS cnt
  FROM partitioned
)
SELECT
  id_set,
  number
FROM counted
WHERE cnt >= 3
;

Here's a SQL Fiddle demo* link for this query: http://sqlfiddle.com/#!1/a2633/1.

UPDATE

To return only one set, you could add in one more round of ranking:

WITH partitioned AS (
  SELECT
    *,
    number - ROW_NUMBER() OVER (PARTITION BY id_set) AS grp
  FROM atable
  WHERE status = 'FREE'
),
counted AS (
  SELECT
    *,
    COUNT(*) OVER (PARTITION BY id_set, grp) AS cnt
  FROM partitioned
),
ranked AS (
  SELECT
    *,
    RANK() OVER (ORDER BY id_set, grp) AS rnk
  FROM counted
  WHERE cnt >= 3
)
SELECT
  id_set,
  number
FROM ranked
WHERE rnk = 1
;

Here's a demo for this one too: http://sqlfiddle.com/#!1/a2633/2.

If you ever need to make it one set per id_set, change the RANK() call like this:

RANK() OVER (PARTITION BY id_set ORDER BY grp) AS rnk

Additionally, you could make the query return the smallest matching set (i.e. first try to return the first set of exactly three consecutive numbers if it exists, otherwise four, five etc.), like this:

RANK() OVER (ORDER BY cnt, id_set, grp) AS rnk

or like this (one per id_set):

RANK() OVER (PARTITION BY id_set ORDER BY cnt, grp) AS rnk

* The SQL Fiddle demos linked in this answer use the 9.1.8 instance as the 9.2.1 one doesn't appear to be working at the moment.

share|improve this answer
    
Thank you very much, this looks nice, but it's possible to change it so only first group of numbers is returned? If I change it to cnt >= 2, then I get 5 numbers (2 groups = 2 + 3 numbers) –  boobiq Mar 18 '13 at 18:22
    
@boobiq: Do you want one per id_set or just one? Please update your question if this was meant as its part from the beginning. (So that others can see the full requirements and offer their suggestions or update their answers.) –  Andriy M Mar 18 '13 at 18:29
    
I edited my question (after wanted return), it will be executed only for one id_set, so only first possible group found –  boobiq Mar 18 '13 at 20:07
add comment

This is a fairly generic way to do this.

Bear in mind it depends on your number column being consecutive. If it's not a Window function and/or CTE type-solution will probably be needed:

SELECT 
    number
FROM
    mytable m
CROSS JOIN
   (SELECT 3 AS consec) x
WHERE 
    EXISTS
       (SELECT 1 
        FROM mytable
        WHERE number = m.number - x.consec + 1
        AND status = 'FREE')
    AND NOT EXISTS
       (SELECT 1 
        FROM mytable
        WHERE number BETWEEN m.number - x.consec + 1 AND m.number
        AND status = 'ASSIGNED')
share|improve this answer
    
The declare won't work like that in Postgres. –  a_horse_with_no_name Mar 18 '13 at 17:23
    
@a_horse_with_no_name Please feel free to fix that then :) –  JNK Mar 18 '13 at 17:24
    
No window functions, very nice! Although I think it should be M.number-consec+1 (e.g. for 10 it would need to be 10-3+1=8). –  Andriy M Mar 18 '13 at 18:01
    
@AndriyM Well it's not "nice" it's fragile since it relies on sequential values of that number field. Good call on the math I'll correct it. –  JNK Mar 18 '13 at 18:04
2  
I took the liberty to fix the syntax for Postgres. the first EXISTS could be simplified. Since we only need to make sure any n earlier rows exist, we can drop the AND status = 'FREE'. And I would change the condition in the 2nd EXISTS to status <> 'FREE' to harden it against added options in the future. –  Erwin Brandstetter Mar 18 '13 at 19:04
show 3 more comments

A simple and fast variant:

SELECT min(number) AS first_number, count(*) AS ct_free
FROM (
    SELECT *, number - row_number() OVER (PARTITION BY id_set ORDER BY number) AS grp
    FROM   tbl
    WHERE  status = 'FREE'
    ) x
GROUP  BY grp
HAVING count(*) >= 3  -- minimum length of sequence only goes here
ORDER  BY grp
LIMIT  1;
  • Requires a gapless sequence of numbers in number (as provided in the question).

  • Works for any number of possible values in status besides 'FREE', even with NULL.

  • The major feature is to subtract row_number() from number after eliminating non-qualifying rows. Consecutive sequences end up in the same grp - which is also guaranteed to be in ascending order.

  • Then you can GROUP BY grp and count the members. Since you seem to want the first occurrence, ORDER BY grp LIMIT 1 and you get starting position and length of the sequence (can be >= n).

Set of rows

To get an actual set of numbers, don't look up the table another time. Much cheaper with generate_series():

SELECT generate_series(first_number, first_number + ct_free - 1)
    -- generate_series(first_number, first_number + 3 - 1) -- only 3
FROM  (
   SELECT min(number) AS first_number, count(*) AS ct_free
   FROM (
      SELECT *, number - row_number() OVER (PARTITION BY id_set ORDER BY number) AS grp
      FROM   tbl
      WHERE  status = 'FREE'
     ) x
   GROUP  BY grp
   HAVING count(*) >= 3
   ORDER  BY grp
   LIMIT  1
  ) y;

If you actually want a string with leading zeros like you display in your example values, use to_char() with the FM (fill mode) modifier:

SELECT to_char(generate_series(8, 11), 'FM000000')

-> SQLfiddle demo with extended test case and both queries.

More information in this closely related answer:
Select longest continuous sequence

share|improve this answer
add comment

This will return only the first of the 3 numbers. It does not require that the values of number are consecutive. Tested at SQL-Fiddle:

WITH cte3 AS
( SELECT
    *,
    COUNT(CASE WHEN status = 'FREE' THEN 1 END) 
        OVER (PARTITION BY id_set ORDER BY number
              ROWS BETWEEN CURRENT ROW AND 2 FOLLOWING)
      AS cnt
  FROM atable
)
SELECT
  id_set, number
FROM cte3
WHERE cnt = 3 ;

And this will show all numbers (where there are 3 or more consecutive 'FREE' positions):

WITH cte3 AS
( SELECT
    *,
    COUNT(CASE WHEN status = 'FREE' THEN 1 END) 
        OVER (PARTITION BY id_set ORDER BY number
              ROWS BETWEEN CURRENT ROW AND 2 FOLLOWING)
      AS cnt
  FROM atable
)
, cte4 AS
( SELECT
    *, 
    MAX(cnt) 
        OVER (PARTITION BY id_set ORDER BY number
              ROWS BETWEEN 2 PRECEDING AND CURRENT ROW)
      AS maxcnt
  FROM cte3
)
SELECT
  id_set, number
FROM cte4
WHERE maxcnt >= 3 ;
share|improve this answer
add comment
CREATE TABLE #ConsecFreeNums
(
     id_set BIGINT
    ,number VARCHAR(10)
    ,status VARCHAR(10)
)

CREATE TABLE #ConsecFreeNumsResult
(
     Seq    INT
    ,id_set BIGINT
    ,number VARCHAR(10)
    ,status VARCHAR(10)
)

INSERT #ConsecFreeNums
SELECT 1, '000002', 'FREE' UNION
SELECT 1, '000003', 'ASSIGNED' UNION
SELECT 1, '000004', 'FREE' UNION
SELECT 1, '000005', 'FREE' UNION
SELECT 1, '000006', 'ASSIGNED' UNION
SELECT 1, '000007', 'ASSIGNED' UNION
SELECT 1, '000008', 'FREE' UNION
SELECT 1, '000009', 'FREE' UNION
SELECT 1, '000010', 'FREE' UNION
SELECT 1, '000011', 'ASSIGNED' UNION
SELECT 1, '000012', 'ASSIGNED' UNION
SELECT 1, '000013', 'ASSIGNED' UNION
SELECT 1, '000014', 'FREE' UNION
SELECT 1, '000015', 'ASSIGNED'

DECLARE @id_set AS BIGINT, @number VARCHAR(10), @status VARCHAR(10), @number_count INT, @number_count_check INT

DECLARE ConsecFreeNumsCursor CURSOR FAST_FORWARD FOR
SELECT
       id_set
      ,number
      ,status
 FROM
      #ConsecFreeNums
WHERE id_set = 1
ORDER BY number

OPEN ConsecFreeNumsCursor

FETCH NEXT FROM ConsecFreeNumsCursor INTO @id_set, @number, @status

SET @number_count_check = 3
SET @number_count = 0

WHILE @@FETCH_STATUS = 0
BEGIN
    IF @status = 'ASSIGNED'
    BEGIN
        IF @number_count = @number_count_check
        BEGIN
            SELECT 'Results'
            SELECT * FROM #ConsecFreeNumsResult ORDER BY number
            BREAK
        END
        SET @number_count = 0
        TRUNCATE TABLE #ConsecFreeNumsResult
    END
    ELSE
    BEGIN
        SET @number_count = @number_count + 1
        INSERT #ConsecFreeNumsResult SELECT @number_count, @id_set, @number, @status
    END
    FETCH NEXT FROM ConsecFreeNumsCursor INTO @id_set, @number, @status
END

CLOSE ConsecFreeNumsCursor
DEALLOCATE ConsecFreeNumsCursor

DROP TABLE #ConsecFreeNums
DROP TABLE #ConsecFreeNumsResult
share|improve this answer
    
I am using cursor for better performance - should the SELECT return large number of rows –  Ravi Ramaswamy Mar 19 '13 at 1:54
    
I reformatted your answer by highlighting the code and pressing the { } button on the editor. Enjoy! –  jcolebrand Mar 19 '13 at 2:41
    
You might also want to edit your answer and tell why you think the cursor provides better performance. –  jcolebrand Mar 19 '13 at 2:42
    
Cursor is a sequential process. It is almost like reading a flat file one record at a time. In one of the situations, I replaced MEM TEMP table with one single cursor. This brought down the processing time from 26 hours to 6 hours. I had to use neseted WHILE to loop through the resultset. –  Ravi Ramaswamy Mar 19 '13 at 15:15
    
Have you ever tried to test case your assumptions? You may be surprised. Except for corner cases plain SQL is fastest. –  Erwin Brandstetter Mar 21 '13 at 8:15
show 1 more comment
select r1.number from some_table r1, 
some_table r2,
some_table r3,
some_table r4 
where r3.number <= r2.number 
and r3.number >= r1.number 
and r3.status = 'FREE' 
and r2.number = r1.number + 4 
and r4.number <= r2.number 
and r4.number >= r1.number 
and r4.status = 'ASSIGNED'
group by r1.number, r2.number having count(r3.number) = 5 and count(r4.number) = 0 order by r1.number asc limit 1 ;

In this case 5 consecutive numbers - therefore difference must be 4 or in other words count(r3.number) = n and r2.number = r1.number + n - 1.

With joins:

select r1.number 
from some_table r1 join 
 some_table r2 on (r2.number = r1.number + :n -1) join
 some_table r3 on (r3.number <= r2.number and r3.number >= r1.number) join
 some_table r4 on (r4.number <= r2.number and r4.number >= r1.number)
where  
 r3.status = 'FREE' and
 r4.status = 'ASSIGNED'
group by r1.number, r2.number having count(r3.number) = :n and count(r4.number) = 0 order by r1.number asc limit 1 ;
share|improve this answer
    
You think a 4-way cartesian product is an efficient way to do this? –  JNK Mar 18 '13 at 17:12
    
Alternatively can you write it with modern JOIN syntax? –  JNK Mar 18 '13 at 17:22
    
Well I didn't want to rely on window functions and gave a solution that would work on any sql-db. –  Ununoctium Mar 19 '13 at 7:01
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.