Find the smallest unused number in MS SQL

Question

How do you find the smallest unused number in a MS SQL column?

I am about to import a large number of manually recorded records from Excel into a MS SQL table. They all have a numeric ID (called document number), but they weren't assigned sequentially for reasons that no longer apply, meaning from now on when my web site records a new record, it needs to assign it the smallest possible document number (greater than zero) that has not already been taken.

Is there a way to do this through plain SQL or is this a problem for TSQL/code?

Thanks!

EDIT

Special thanks to WW for raising the issue of concurrency. Given that this is a web app, it is multi-threaded by definition and anyone faced with this same problem should consider either a code or DB level lock to prevent a conflict.

LINQ

FYI - this can be accomplished via LINQ with the following code:

var nums = new [] { 1,2,3,4,6,7,9,10};

int nextNewNum = (
    from n in nums
    where !nums.Select(nu => nu).Contains(n + 1)
    orderby n
    select n + 1
).First();

nextNewNum == 5

Answer 1

Is there a reason that it has to be the smallest possible number? Why do you need to fill the holes?

Edit to ad the answer, since it's a business rule.

DECLARE @counter int
DECLARE @max
SET @counter = 0
SET @max = SELECT MAX(Id) FROM YourTable
WHILE @counter <= @max
BEGIN
    SET @counter = @counter + 1
    IF NOT EXISTS (SELECT Id FROM YourTable WHERE Id = @counter)
        BREAK
    END
END

(I don't have a db handy, so this may not be 100% accurate, but you should be able to get it from there)

Answer 2

If there are gaps in the sequence, you can find the first gap with something like this:

select top 1 (found.id + 1) nextid from (select id from items union select 0) found
    where not exists (select * from items blocking
                          where blocking.id = found.id + 1)
    order by nextid asc

In other words, find the least ID whose successor does not exist, and return that successor. If there are no gaps, it returns one greater than the greatest extant ID. A placeholder ID of 0 is inserted to insure that IDs starting with 1 are considered.

Note that this will take at least n log n time.

Microsoft SQL permits the use of a from clause in an insert statement, so you may not need to resort to procedural code.

Answer 3

If you sort them by numeric ID, the number you are looking for will be the first one for which the ROW_NUMBER() function doesn't equal the ID.

Answer 4

Find the first row where there does not exist a row with Id + 1

SELECT TOP 1 t1.Id+1 
FROM table t1
WHERE NOT EXISTS(SELECT * FROM table t2 WHERE t2.Id = t1.Id + 1)
ORDER BY t1.Id

Answer 5

SELECT TOP 1 t1.id+1
FROM mytable t1
 LEFT OUTER JOIN mytable t2 ON (t1.id + 1 = t2.id)
WHERE t2.id IS NULL
ORDER BY t1.id;

This is an alternative to the answers using correlated subqueries given by @Jeffrey Hantlin and @Darrel Miller.

However, the policy you're describing is really not a good idea. ID values should be unique, but should not be required to be consecutive.

What happens if you email someone with a link to document #42, and then subsequently delete the document? Later, you re-use the id #42 for a new document. Now the recipient of the email will follow the link to the wrong document!

Answer 6

No mention of locking or concurrency in any of the answers so far.

Consider these two users adding a document at nearly the same time:-

User 1                User 2
Find Id               
                      Find Id
Id = 42               
                      Id = 42
Insert (42..)  
                      Insert (42..)
                      Error!

You either need to: a) Handle that error and go around the loop again looking for the next available Id, OR b) Take a lock out at the start of the process so only 1 user is looking for Ids at a particular time

Answer 7

You really should try to convert the column to IDENTITY. BACKUP first then use ROW_NUMBER to update the document ID so they start from 1 and up to the document count. You should do it in a WHILE one at the time because if the number column is used as reference in other tables (foreign keys) SQL Server will try to update the foreign keys and maybe fail because of conflicts. In the end just enable identity specifications for the column.

:) It's more work now but it will save you a lot of trouble later.

Answer 8

select MIN(NextID) NextUsableID from ( select ( case when c1 = c2 then 0 else c1 end ) NextID from ( select ROW_NUMBER() over (order by record_id) c1, record_id c2 from myTable ) )
where NextID > 0

Answer 9

declare @value int

select @value = case 
                  when @value is null or @value + 1 = idcolumn 
                    then idcolumn 
                  else @value end
   from table
   order by idcolumn

select @value + 1

Does 1 table scan rather than 2 scans a hash match and a join like the top answer