How to find "holes" in a table

Question

I recently inherited a database on which one of the tables has the primary key composed of encoded values (Part1*1000 + Part2).
I normalized that column, but I cannot change the old values. So now I have

select ID from table order by ID
ID
100001
100002
101001
...

I want to find the "holes" in the table (more precisely, the first "hole" after 100000) for new rows.
I'm using the following select, but is there a better way to do that?

select /* top 1 */ ID+1 as newID from table
where ID > 100000 and
ID + 1 not in (select ID from table)
order by ID

newID
100003
101029
...

The database is Microsoft SQL Server 2000. I'm ok with using SQL extensions.

Answer 1

SELECT ID+1 FROM table AS t1
LEFT JOIN table as t2
ON t1.ID = t2.ID+1
WHERE t2.ID IS NULL

Answer 2

select ID +1 From Table t1
where not exists (select * from Table t2 where t1.id +1 = t2.id);

not sure if this version would be faster than the one you mentioned originally.

Answer 3

This solution should give you the first and last ID values of the "holes" you are seeking. I use this in Firebird 1.5 on a table of 500K records, and although it does take a little while, it gives me what I want.

SELECT l.id + 1 start_id, MIN(fr.id) - 1 stop_id
FROM (table l
LEFT JOIN table r
ON l.id = r.id - 1)
LEFT JOIN table fr
ON l.id < fr.id
WHERE r.id IS NULL AND fr.id IS NOT NULL
GROUP BY l.id, r.id

For example, if your data looks like this:

ID
1001
1002
1005
1006
1007
1009
1011

You would receive this:

start_id   stop_id
1003       1004
1008       1008
1010       1010

I wish I could take full credit for this solution, but I found it at Xaprb.

Answer 4

This solution doesn't give all holes in table, only next free ones + first available max number on table - works if you want to fill in gaps in id-es, + get free id number if you don't have a gap..

select numb + 1 from temp minus select numb from temp;