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 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 2

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

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

from How do I find a "gap" in running counter with SQL?

select
    MIN(ID)
from (
    select
        100001 ID
    union all
    select
        [YourIdColumn]+1
    from
        [YourTable]
    where
        --Filter the rest of your key--
    ) foo
left join
    [YourTable]
    on [YourIdColumn]=ID
    and --Filter the rest of your key--
where
    [YourIdColumn] is null

Answer 5

The best way is building a temp table with all IDs

Than make a left join.

declare @maxId int
select @maxId = max(YOUR_COLUMN_ID) from YOUR_TABLE_HERE


declare @t table (id int)

declare @i int
set @i = 1

while @i <= @maxId
begin
    insert into @t values (@i)
    set @i = @i +1
end

select t.id
from @t t
left join YOUR_TABLE_HERE x on x.YOUR_COLUMN_ID = t.id
where x.YOUR_COLUMN_ID is null

Answer 6

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;

Answer 7

Have thought about this question recently, and looks like this is the most elegant way to do that:

SELECT TOP(@MaxNumber) ROW_NUMBER() OVER (ORDER BY t1.number) 
FROM master..spt_values t1 CROSS JOIN master..spt_values t2 
EXCEPT
SELECT Id FROM <your_table>

Answer 8

This will give you the complete picture, where 'Bottom' stands for gap start and 'Top' stands for gap end:

    select *
    from 
    ( 
       (select <COL>+1 as id, 'Bottom' AS 'Pos' from <TABLENAME> /*where <CONDITION*/>
       except
       select <COL>, 'Bottom' AS 'Pos' from <TABLENAME> /*where <CONDITION>*/)
    union
       (select <COL>-1 as id, 'Top' AS 'Pos' from <TABLENAME> /*where <CONDITION>*/
       except
       select <COL>, 'Top' AS 'Pos' from <TABLENAME> /*where <CONDITION>*/)
    ) t
    order by t.id, t.Pos

Note: First and Last results are WRONG and should not be regarded, but taking them out would make this query a lot more complicated, so this will do for now.

Answer 9

Many of the previous answer are quite good. However they all miss to return the first value of the sequence and/or miss to consider the lower limit 100000. They all returns intermediate holes but not the very first one (100001 if missing).

A full solution to the question is the following one:

select id + 1 as newid from
    (select 100000 as id union select id from tbl) t
    where (id + 1 not in (select id from tbl)) and
          (id >= 100000)
    order by id
    limit 1;

The number 100000 is to be used if the first number of the sequence is 100001 (as in the original question); otherwise it is to be modified accordingly "limit 1" is used in order to have just the first available number instead of the full sequence

Answer 10

For people using Oracle, the following can be used:

select a, b from (
  select ID + 1 a, max(ID) over (order by ID rows between current row and 1 following) - 1 b from MY_TABLE
) where a <= b order by a desc;

Answer 11

The following SQL code works well with SqLite, but should be used without issues also on MySQL, MS SQL and so on.

On SqLite this takes only 2 seconds on a table with 1 million rows (and about 100 spared missing rows)

WITH holes AS (
 SELECT 
 IIF(c2.id IS NULL,c1.id+1,null) as start,
 IIF(c3.id IS NULL,c1.id-1,null) AS stop,
 ROW_NUMBER () OVER (
  ORDER BY c1.id ASC
 ) AS rowNum
 FROM |mytable| AS c1
 LEFT JOIN |mytable| AS c2 ON c1.id+1 = c2.id
 LEFT JOIN |mytable| AS c3 ON c1.id-1 = c3.id
 WHERE c2.id IS NULL OR c3.id IS NULL
)
SELECT h1.start AS start, h2.stop AS stop FROM holes AS h1
LEFT JOIN holes AS h2 ON h1.rowNum+1 = h2.rowNum
WHERE h1.start IS NOT NULL AND h2.stop IS NOT NULL
UNION ALL                
SELECT 1 AS start, h1.stop AS stop FROM holes AS h1
WHERE h1.rowNum = 1 AND h1.stop > 0
ORDER BY h1.start ASC