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