How to get missing values in row order?

In a table, many rows have been deleted, how to get the id of missing rows for next INSERT?

For example

id      col1
1       1
3       3
4       4
5       5
8       8
9       9

how can I get the value of first available id for next INSERT. Here I want to get the id = 2.

Something like

SELECT id+1 FROM table WHERE CLAUSE // pointing to the least available value
// or x = id +1 (after SELECT)
INSERT INTO table (id, ....) VALUES ('x', ....)

If the column is just a surrogate key and is not used for other purposes (display sorting and so forth) then I would just use your database's AUTOINCREMENT equivalent and ignore the fact that there will be gaps in the IDs, as there point is to be unique rather than serving other purposes. The much recommended "SQL Anti-Patterns" book has a chapter on this entitled "pseudokey neat-freak". This depends on what you are modelling and how of course, if the numbers do carry meaning beyond being an identifier then this point is irrelevant.

The general concept you want to read around (it is worth a little background reading as these problems crop up all over the place so knowing how to spot them and deal with them efficiently or design them out is very useful) is gaps and islands. There are many online references about this (this is the first one a quick search found, it is talking about MSSQL but the concepts are transferable).

As well as the WHERE NOT EXISTS method, which is usually suggested as the way the code reads makes your intentions more obvious, you can also do:

SELECT TOP 1 t1.id-1
FROM     yourtable t1
LEFT OUTER JOIN 
         yourtable t2 
ON       t2.id=t1.id-1 -- will match if there is a row with the next ID down from the row in t1
WHERE    t2.id IS NULL -- the next ID down not found
AND      t1.id > 0     -- assume 1 is the lowest valid ID
ORDER BY t1.id

(that is MSSQL syntax, you may need to tweak it)

Both variants should produce similar query plans so perform the same, but I've seen the above approach perform better as part of a more complex query so it may be worth trying both in your circumstances and verifying which performs best.

Also not that neither method as currently presented will return the first ID if the table is empty: you'll get no rows back instead (or NULL if you are using this as a sub-query). One method of getting around this is to have an "invalid" row with id=0 but that is quite dirty (you end up having to filter that out of many other queries) so dealing with the nothing/NULL in your logic instead instead is strongly recommended. For tables that will never be empty in production (a users table for instance, even on initial install there will be one record for the initial setup/admin user) this or course is not an issue.

edit: Corrected the query to return the first ID if not found, as ypercube noted the first version would not do

Newer mySQL Versions

Since this answer, mySQL and MariaDB have added support for window functions (in versions 8 and 10.2 respectively) such as LAG() and LEAD(). You can use these to inspect the next (or previous) row and compare the value that is intended to increment and see if there is a gap, meaning you do not need to join the table onto itself or use a sub-query with EXISTS for this comparison - with the right index(es) this can be a much more efficient way to implement some gap/island queries.

All the common SQL database engines (sqlite, postgres, SQL Server, Oracle, ...) now support window functions.

StackExchange Database Administrators Q#50016, answer score: 8