MySQL - Query to find a continuous range of unused values

Question

Hi,

I have a table containing integer values from 0 to some large number N, but has some number gaps. I'm trying to write an efficient query that'll find the first set of continuous values of some length that are within 0 and N but are not contained in the said table. This has applications to find unused ids, etc.

For example, given the set

[1,2,3,4,10,11,12,13,14,15]

, find a range of continuous 5 numbers that aren't in the set. It should be

[5,6,7,8,9]

. How do I write this in a single, efficient query? thanks.

Answer 1

Here's a great chapter from SQL Server MVP Deep Dives book on this subject.

http://www.manning.com/nielsen/SampleChapter5.pdf

Here's one of solutions

WITH StartingPoints AS
(
SELECT seqval, ROW_NUMBER() OVER(ORDER BY seqval) AS rownum
FROM dbo.NumSeq AS A
WHERE NOT EXISTS
(SELECT *
FROM dbo.NumSeq AS B
WHERE B.seqval = A.seqval - 1)
),
EndingPoints AS
(
SELECT seqval, ROW_NUMBER() OVER(ORDER BY seqval) AS rownum
FROM dbo.NumSeq AS A
WHERE NOT EXISTS
(SELECT *
FROM dbo.NumSeq AS B
WHERE B.seqval = A.seqval + 1)
)
SELECT S.seqval AS start_range, E.seqval AS end_range
FROM StartingPoints AS S
JOIN EndingPoints AS E
ON E.rownum = S.rownum;