Finding missing numbers in a sequence

From http://www.sqlservercentral.com/articles/Datetime+Manipulation/61822/

Find Missing Numbers

It is obvious that, to find missing numbers, we need to have a table or resultset which contains all the numbers. Then we can apply a NOT IN clause and identify the missing numbers.

If you are wondering, why I needed missing numbers, here is the reason. In one of my applications, there is an entity that we call coordinator. Each coordinator has a 4 digit numeric code. The code starts at 1000 and ends at 9999. (There is no chance that we will have more than 9000 coordinators at any point of time, so a 4 digit code is sufficient). When the user creates a new coordinator, the system automatically generates a new coordinator number. However, the user can still edit it. The system will allow the user to edit the coordinator number (during a new entry) as long as it does not produce a duplicate code.

With the above functionality, we needed a way to reuse un-used/missing numbers. When we create a new coordinator, we need to find the lowest unused coordinator code. For this purpose we needed a way to identify the missing numbers.

As mentioned earlier in this article, I did not want to keep a temp table. I want to generate the numbers on the fly. There are several ways to do this. I like to use a CTE to do this.

In one of my previous articles, I had presented a way to generate a sequence of numbers by using a CTE. It was fast. But a faster code fragment was posted by Kathi Kellenberger in the discussion forum. It was taken from Itzik Ben-Gan’s book “Inside Microsoft SQL Server 2005 T-SQL Querying”. Here is the code fragment which generates 1 million records in the fraction of a second. [code]

WITH
L0 AS (SELECT 1 AS C UNION ALL SELECT 1), --2 rows
L1 AS (SELECT 1 AS C FROM L0 AS A, L0 AS B),--4 rows
L2 AS (SELECT 1 AS C FROM L1 AS A, L1 AS B),--16 rows
L3 AS (SELECT 1 AS C FROM L2 AS A, L2 AS B),--256 rows
L4 AS (SELECT 1 AS C FROM L3 AS A, L3 AS B),--65536 rows
L5 AS (SELECT 1 AS C FROM L4 AS A, L4 AS B),--4294967296 rows
num AS (SELECT ROW_NUMBER() OVER(ORDER BY C) AS N FROM L5)
SELECT N FROM NUM WHERE N <= 1000000;

This code is VERY VERY fast and I find it to be the best candidate for generating a sequence of numbers on the fly. I wanted to re-use this code and hence I created a function that takes a Minimum and Maximum value and returns a resultset containing sequence numbers within the given range. [code]

CREATE FUNCTION dbo.GetNumbers
(
@Start BIGINT,
@End BIGINT
)
RETURNS @ret TABLE(Number BIGINT)
AS
BEGIN
WITH
L0 AS (SELECT 1 AS C UNION ALL SELECT 1), --2 rows
L1 AS (SELECT 1 AS C FROM L0 AS A, L0 AS B),--4 rows
L2 AS (SELECT 1 AS C FROM L1 AS A, L1 AS B),--16 rows
L3 AS (SELECT 1 AS C FROM L2 AS A, L2 AS B),--256 rows
L4 AS (SELECT 1 AS C FROM L3 AS A, L3 AS B),--65536 rows
L5 AS (SELECT 1 AS C FROM L4 AS A, L4 AS B),--4294967296 rows
num AS (SELECT ROW_NUMBER() OVER(ORDER BY C) AS N FROM L5)

INSERT INTO @ret(Number)
SELECT N FROM NUM WHERE N BETWEEN @Start AND @End
RETURN
END

Once we have the function to generate the sequence number, we can easily write the code to identify the missing numbers. [code]

    1 SELECT MIN(Number)

    2 FROM dbo.GetNumbers(1000, 9999)

    3 WHERE Number NOT IN (SELECT CoordinatorID FROM Coordinators)

Find Missing Dates

I guess the requirement to find missing dates must be more common than the missing number requirement I mentioned above. To find the missing dates (Dates at which no sales took place, Dates at which a given employ was absent etc) we need to have a table or resultset which contains all the dates within a given range.

The following example shows how to generate a sequence of dates using the same logic we discussed earlier. [code]

--Generate a sequence of all the dates for the month of October, 2007

SELECT
CAST('2007-10-01' AS DATETIME) + Number-1
FROM dbo.GetNumbers(1, 30)
--Generate a sequence of all the dates for year 2007

SELECT
CAST('2007-01-01' AS DATETIME) + Number-1
FROM dbo.GetNumbers(1, 365)

Once we have a sequence of dates, we can easily apply a NOT IN clause and find the missing dates based on the specific requirement.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

A WordPress.com Website.

Up ↑

%d bloggers like this: