Find the smallest unused number in SQL Server

Question

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

I am about to import a large number of manually recorded records from Excel into a SQL Server 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

Nereus

Nice article: xaprb.com/blog/2005/12/06/… – Chagres

Answer 1

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

Edit:

To handle the special case where the lowest existing id is not 1, here is a ugly solution:

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

Krisha

This will miss any contiguous block of ids starting at the beginning of the range. For example, if table has ids (5,6,8,9,10) this will return 7, not any of 1-4. – Festive

@Festive You are right. I missed the comment about wanting to fill all id's greater than zero. I added an ugly fix. Maybe someone will suggest an improvement. – Krisha

+1 Very helpful, thanks! Most of the other answers here have been "you don't need to do that, let the system increment the key," but my case isn't for the primary key but instead another unique numeric field where empty slots are a problem but can occur, and not as the result of a delete. – Mumble

For the first part there is way simplier version. SELECT MAX(t1.Id + 1) FROM t1 it gives you the new highest ID. if before it was 3 it will return 4. – Cyd

@DarrelMiller, you requested an improvement - see my answer :) – Willock

@DarrelMiller Couldn't you just add a CASE statement in the first query? SELECT TOP 1 CASE WHEN t1.Id + 1 < 1 THEN 1 ELSE t1.Id + 1 END – Liuka

I'd put select null from table in the not exists to speed it up a bit – Sacking

Answer 2

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.

Po

+1 good SQL Server-specific trick. Could this be done in a subselect to pick off the first non-matching, then union'ed with max(id)+1 to do it in one go? – Renaldorenard

Got a SQL example? – Chagres

@niico: SELECT TOP 1 q.r FROM ( SELECT id, ROW_NUMBER() OVER (ORDER BY id ASC) AS r FROM <table> ORDER BY id OFFSET 0 ROWS ) q WHERE q.id <> q.r – Trela

Answer 3

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

Smaragdine

Answer 4

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!

Lipid

I admit this doesn't find a missing value of 1. However, it's a bogus problem, which is my real point, so I'm not interested in coming up with a solution! :-P – Lipid

Document numbers are never deleted. I'll agree with you, though, that this is a poor way to identify docs. I'm picking my battles, though and there are bigger fish to fry. – Nereus

Answer 5

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

Onerous

much faster then the Top answer +1! – Nabal

Answer 6

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)

Kaddish

It's a business rule. These document numbers are then handed out to users and actually used. I asked the same question, but they are standing firm on this one. :) – Nereus

That's unfortunate... The only way I know of would be to loop through them all until you find an unused ID. Sorry bout your luck. – Kaddish

Answer 7

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.

Germicide

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

Topmast

Answer 9

Here is a simple approach. It may no be fast. It will not find missing numbers at the beginning.

SELECT MIN(MT1.MyInt+1)
FROM MyTable MT1
LEFT OUTER JOIN MyTable MT2 ON (MT1.MyInt+1)=MT2.MyInt
WHERE MT2.MyInt Is Null

Wisla

Answer 10

Let's assume your IDs should always start with 1:

SELECT MIN(a.id) + 1 AS firstfree
FROM (SELECT id FROM table UNION SELECT 0) a
LEFT JOIN table b ON b.id = a.id + 1
WHERE b.id IS NULL

This handles all cases I can think of - including no existing records at all.

The only thing I don't like about this solution is that additional conditions have to be included twice, like that:

SELECT MIN(a.id) + 1 AS firstfree
FROM (SELECT id FROM table WHERE column = 4711 UNION SELECT 0) a
LEFT JOIN table b ON b.column = 4711 AND b.id = a.id + 1
WHERE b.id IS NULL

Please also notice the comments about locking and concurrency - the requirement to fill gaps is in most cases bad design and can cause problems. However, I had a good reason to do it: the IDs are to be printed and typed by humans and we don't want to have IDs with many digits after some time, while all the low ones are free...

Willock

Answer 11

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.

Primm

Answer 12

I know this answer is late but you can find the smallest unused number by using a recursive table expression:

CREATE TABLE Test
(
    ID int NOT NULL
)

--Insert values here

;WITH CTE AS
(
    --This is called once to get the minimum and maximum values
    SELECT nMin = 1, MAX(ID) + 1 as 'nMax' 
    FROM Test
    UNION ALL
    --This is called multiple times until the condition is met
    SELECT nMin + 1, nMax 
    FROM CTE
    WHERE nMin < nMax
)

--Retrieves all the missing values in the table. Removing TOP 1 will
--list all the unused numbers up to Max + 1
SELECT TOP 1 nMin
FROM CTE
WHERE NOT EXISTS
(
    SELECT ID
    FROM Test
    WHERE nMin = ID
)

Cheke

Answer 13

I faced a similar problem and came up with this:

Select Top 1 IdGapCheck
From (Select Id, ROW_NUMBER() Over (Order By Id Asc) AS IdGapCheck
    From dbo.table) F
Where Id > IdGapCheck
Order By Id Asc

Babettebabeuf

Answer 14

For Oracle DB this should do the Job:

SELECT MIN(NI) FROM
        (SELECT ROWNUM AS NI,YOUR_ID
         FROM (SELECT YOUR_ID
               FROM YOUR_TABLE 
               ORDER BY YOUR_ID ASC))
WHERE NI<>YOUR_ID

Excision

Answer 15

ROW_NUMBER() function example:

IF NOT EXISTS (SELECT TOP 1 row_num FROM (SELECT ROW_NUMBER() OVER (ORDER BY Id) row_num, Id FROM table) t WHERE t.Id > t.row_num) SELECT MAX (Id)+1 FROM table ELSE SELECT TOP 1 row_num FROM (SELECT ROW_NUMBER() OVER (ORDER BY Id) row_num, Id FROM table) t WHERE t.Id > t.row_num;

Tunstall

Answer 16

For those who are really care about the "smallest" unused number, i.e., must be smallest, then you can take a look at https://mcmap.net/q/373103/-get-minimum-unused-value-in-mysql-column, I have converted it to SQLSever syntax:

(Assuming the minimum number is 1)

from (
    select
        sequence,
        case
        when sequence <> IsNull(lag(sequence) over (order by sequence), 0) + 1      -- when seq <> prev_seq_add_1
            then IsNull(lag(sequence) over (order by sequence), 0) + 1              -- then prev_seq_add_1
        when sequence <> IsNull(lead(sequence) over (order by sequence), 0) - 1     -- when seq <> next_seq_dec_1
            then sequence + 1                                                       -- then seq + 1
        end
        as unused_seq
    from (
        select 3 as sequence
        union select 2 as sequence
        union select 5 as sequence
        union select 1 as sequence
        union select 7 as sequence
    ) as unique_sequences
) as t
where unused_seq is not null
    order by sequence

Please replace the unique_sequences subquery with yours.

You can paste the sql to sqlfiddle to have a test without installing anything. sqlfiddle: http://sqlfiddle.com/#!18/9eecb/164624

Tested results:

• 1,2,3,4,5 -> 6
• 3,4,5,7 -> 1
• 1,2,4,5 -> 3

Note that No Record means 1.

The query could be further simplified if you can find some inline sequence table then it would be like that in mysql

SELECT * FROM seq_1_to_32767
   EXCEPT
   SELECT sequence from .... order by sequence.

but I could not find appropriate one.

Berwickupontweed