Sequences, Gaps, And Unique ID's

I have a database, where the primary key of each table is an integer.

After a few deletions, the data in the primary key column of one of these tables might look like:

If this column were an identity or autonumber field, then the next record to be added to the table would have an ItemID of 15.

But it's a kludgy database, and there's a lot of code which relies on there not being any gaps in the numbering system, so the next record to be added, needs to have an ItemID of 5 - the first available gap.

OK, so how does one use SQL to find out what data ISN'T in a table?

The following query will find the first missing number in any sequence of missing numbers:

SELECT Item.ItemID+1
FROM Item
WHERE NOT Item.ItemID+1 IN (SELECT ItemID FROM Item)

Run this query against the sample data at the beginning
of this article, and you'll get

So, to find the first gap, and therefore the ID to
use for the next record to be added, I could just use

SELECT MIN(Item.ItemID+1)
FROM Item
WHERE NOT Item.ItemID+1 IN (SELECT ItemID FROM Item)

Right?

Well almost. There's one exception (which I hope you have spotted).

What if there is no record in the table with ItemID=1 ?

The above query will only pick up a gap if it occurs after an existing record. So unless there is a record with ItemID=0, the absence of a record with ItemID=1 will go unnoticed. (I want my numbering system to start at 1, not 0).

The following query gets around that by tacking on a UNION clause to deal with that one exception:

SELECT Item.ItemID+1 AS GapStart
FROM Item
WHERE NOT Item.ItemID+1 IN (SELECT ItemID FROM Item)
UNION ALL
SELECT 1 AS GapStart
WHERE NOT EXISTS(SELECT ItemID FROM Item WHERE ItemID=1)
ORDER BY GapStart

To find just the first gap:

SELECT MIN(GapStart) FROM
(
SELECT MIN(Item.ItemID+1) AS GapStart
FROM Item
WHERE NOT Item.ItemID+1 IN (SELECT ItemID FROM Item)
UNION ALL
SELECT 1 AS GapStart
WHERE NOT EXISTS(SELECT ItemID FROM Item WHERE ItemID=1)
) AS Gaps

You might have noticed, that in my sample data, the gap which starts at 9 is three numbers long. That is, 10 and 11 are also missing from the sequence.

The query to return the last missing number from each gap is a simple variation on my first query:

SELECT Item.ItemID-1 AS GapEnd
FROM Item
WHERE NOT Item.ItemID-1 IN (SELECT ItemID FROM Item)

No convoluted UNION query is needed for this one, because
there aren't any exceptions to worry about.

The output from this query is:

Putting it all together:

You may have worked out that the query that I'm really working towards, outputs the following data:

(The last gap doesn't have an "End", because my numbering system goes on forever).

The query that outputs this data is a variation on the query for finding gap "Starts". In each half of the UNION, there is a sub-select to find the "End" which corresponds to each "Start" returned by the outer query.

SELECT Item.ItemID+1 AS GapStart,
(SELECT MIN(ItemID-1) FROM Item AS t1
WHERE t1.ItemID>Item.ItemID AND NOT ItemID-1
IN (SELECT ItemID FROM Item)) AS GapEnd
FROM Item
WHERE NOT Item.ItemID+1 IN (SELECT ItemID FROM Item)
UNION
SELECT 1 AS GapStart,
(SELECT MIN(ItemID-1) FROM Item AS t1
WHERE t1.ItemID>1 AND NOT ItemID-1
IN (SELECT ItemID FROM Item)) AS GapEnd
WHERE NOT EXISTS(SELECT ItemID FROM Item WHERE ItemID=1)
ORDER BY GapStart