returning free numbers

[ArielR]

I need to make a procedure that return free numbers from a secuential table. Could somebody help me?. for ex: 1, 2, 3, 4, 5, 7, 8, 9, 10 Its mast be return 6. Thank

[kubben]

If you have another table that has all of the numbers you could do a left join. So if table1 is missing numbers and table2 has all the numbers you could do:

select t2.id from table2 t2
left join table1 t1 on t2.id = t1.id
where t2.id is null

This would return all the missing numbers. Ben

[Michael Potter]

Interesting Problem. Here is a solution to find the missing holes in your data. It will even find a leading hole if you know the expected start number. In this example the start number is set to ONE (t.[MyID] != 1 & the ISNULL result set to 0). This works with SQL Server 2000, there is more than likely an easier solution with SQL Server 2005. Replace [MyId] with your id column name. Replace [MyTable] with your table name.

SELECT 
    ISNULL((SELECT MAX([MyID]) FROM [MyTable] WHERE [MyID] < t.[MyID]),0) + 1  AS FirstMissingNumber,
    t.[MyID] - 1 AS LastMissingNumber
FROM 
    [MyTable] t
WHERE 
    (t.[MyID] - 1) NOT IN (SELECT [MyID] FROM [MyTable]) AND
    t.[MyID] != 1

[ArielR]

Thank you. You make magic with this code. I'm trying to understand it. Its works fantastic!!.

[Michael Potter]

You are welcome. Finding the 'last' missing number was pretty easy. The query just subtracts one from every ID and sees if it is already there and that it isn't the first assigned id.

SELECT     
    [MyID] - 1 AS MissingNumber
FROM     
    [MyTable] 
WHERE     
    [MyID] - 1) NOT IN (SELECT [MyID] FROM [MyTable]) AND    
    [MyID] != 1

Finding the first missing number uses a correlated subquery. If you look at that query by itself it is pretty clear. I added the ISNULL because the first record will have no preceeding records and therefore, return NULL.

[DQNOK]

I agree with ArielR. Very nice. I'd have said it wasn't possible if I hadn't seen your solution. Correct me if I'm wrong, but doesn't your solution only return the first and last numbers from a missing block... 1,2,3,9,10 It won't return all the missing numbers: 4 thru 8, will it? Just 4 and 8; right? I also found it difficult to see how it was working, so I dumbed it down for my own understanding:

SELECT (T.ID - 1) AS MissingID
FROM tblMyTable AS T
WHERE (T.ID - 1) NOT IN (SELECT ID FROM tblMyTable);

Of course, this will pick up numbers that don't belong in the table, like 0 (zero), so I added a predicate similar to yours:

SELECT (T.ID - 1) AS MissingID
FROM tblMyTable AS T
WHERE (T.ID - 1) NOT IN (SELECT ID FROM tblMyTable)
AND T.ID > @startnum;

Of course this ONLY picks up numbers of the form (ID-1) where ID IS in the table, and ID-1 is not. It won't pick up others numbers from a block of missing numbers. Now a concern: I *THINK* that each element from the (T.ID - 1) set will be subject to a linear scan of the entire (SELECT ID FROM tblMyTable) result set (well, it should stop as soon as a hit occurs). This will be an O(N^2) operation. I also *THINK* that if we just sorted the exclusion set:

WHERE (T.ID - 1) NOT IN (SELECT ID FROM tblMyTable ORDER BY ID)

the DBMS should recognize the order, and do a binary search instead of a linear scan, reducing the overall select to O(N*ln(N)) (of course the ordering operation itself may be an O(N*ln(N)) operation). This may seem insignificant, but if you're searching a million record table, N^2 could be huge! In this case, N*ln(N) could be 50,000 times faster than N^2. Then I began wondering if it could be reduced it to an O(N) operation just like a person would code it manually in a procedural language if they knew the two sets were ordered. Perhaps a LEFT JOIN like kubben suggested would do it:

SELECT Missing.ID FROM
(SELECT (ID - 1) AS ID
FROM tblMyTable
WHERE ID > @startnum
ORDER BY ID) AS Missing
LEFT JOIN
(SELECT ID
FROM tblMyTable
ORDER BY ID) AS Includes ON Missing.ID = Includes.ID
WHERE Includes.ID IS NULL;

Maybe someone who knows more about the guts of a DBMS (like Mike Dimmick) could set me straight here. I'd have liked to run some speed tests with huge tables, but just don't have the resources available to me. David

[Michael Potter]

You are correct in your speed assumptions. When used on an primary key, my code would result in a binary search of the index. Your method would be significantly faster on larger tables especially since NOT IN is a very slow operation. You would still have to acquire the first ID in a missing hole. It would be easy enough to re-insert the correlated subquery (will slow it down a bit) by using your final query as the source for a new query. The only way I can see for locating all missing IDs is to use a while loop, a cursor or building a table of integers as the first respondent mentioned. Normally, I would leave further analysis to a client application where iteration through the result set is a simplistic operation.