Find the smallest unused number in SQL Server

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

SELECT TOP 1 t1.Id+1 FROM table t1WHERE 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)) otORDER BY 1

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.

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 2Find Id                                     Find IdId = 42                                     Id = 42Insert (42..)                        Insert (42..)                      Error!

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