Want to improve SQL query

Question

I have a table called "world". It has some empty IDs:

id - data
1 - ...
2 - ...
(no 3,4 IDs after 2)
5 - ...

And I have a query to select the lowest unused ID in this table. It looks like:

SELECT MIN(t1.id)
FROM 
(
 SELECT 1 AS id
 UNION ALL
 SELECT id + 1
 FROM world
) t1
LEFT OUTER JOIN world t2
ON t1.id = t2.id
WHERE t2.id IS NULL;

I want to find a way how to improve this query to make it execute faster.

Answer 1

This will give you the first unused ID after the first used one (i.e. it won't give you ID 1 if it's unused but will work for the rest).

SELECT id + 1 FROM world WHERE (id + 1) NOT IN (
    SELECT id FROM world
) ORDER BY id ASC LIMIT 1

To include ID 1 you could do a specific check first to see if it exists, or do something like:

SELECT IF(
    NOT EXISTS(SELECT id FROM world WHERE id = 1),
    1,
    (SELECT id + 1 FROM world WHERE (id + 1) NOT IN (
        SELECT id FROM world
    ) ORDER BY id ASC LIMIT 1)
) AS min_unused

Answer 2

You can do something like this:

select (w.id + 1)
from world w left join
     world w2
     on w.id = w2.id - 1
where w2.id is null
order by w.id
limit 1

This should have reasonable performance with an index on world(id).

SQLFiddle for the same SQL