Sql Server – Finding next gap in a numeric column

I was recently tasked with improving the performance of one of our Sql Server Stored Procedures which found and returned next available Profile Number for new Profiles to be created in the application. Although the actual circumstances were considerably more complex, for simplicity sake, let’s just assume that the Profile Number column in our case was an numerical integral column.

Agents who used our application could either input a Profile Number manually that they wanted to assign to a new Profile being created, or they can let the application return the next available Profile Number (in which case the application started its search from Profile Number ‘1’). In both cases, the application verified and returned the inputted Profile Number (or ‘1’) if it was available. Otherwise the system found the next higher value that is available and returned it for consumption by the Agent.

Because the application allowed Agents to manually request and get assigned a desired Profile Number, the Profile Number column in the database was essentially fragmented with contagious blocks of numbers that were already assigned interspersed with unused Profile Numbers.

And our problem hence translated to the following statement:

Given a Profile Number (defaulting to 1 if not explicitly entered by the Agent), find the next available Profile Number which is equal to or greater than the provided Profile Number and is unused in the database.

This SP was ages old, dating back to something like 2009 when it went live and was not originally written by myself. The developer who originally wrote it used a crude CURSOR to iterate over all the rows of the table in ascending order of Profile Number to find a vacant one. The application is being used by hundreds of corporate clients since some of whom have millions of rows in the Profiles table.

The original CURSOR-based SP had fizzled out a few years ago, when it started taking 25+ seconds for a single execution, and needed optimisation. At that time, I did away with the CURSOR approach and used the following Sql which caused the SP to return in less than 2-3 seconds then for the largest of our clients:

SELECT MIN(ProfileNumber) + 1
FROM Profiles po WITH (NOLOCK)
WHERE ProfileNumber >= @sStartNumeric
	AND NOT EXISTS
   (
       SELECT 1
	   FROM Profiles pi WITH (NOLOCK)
	   WHERE pi.ProfileNumber = po.ProfileNumber + 1
	);

Here @sStartNumeric was either the explicitly entered Profile Number by the Agent or defaulted to 1. Everything else should be self-explanatory. We basically use an inner query on the same Profiles table to figure out the minimum ProfileNumber for which a row with ProfileNumber + 1 did not exist in the Profiles table and returned that ProfileNumber. We added an index on ProfileNumber column on Profiles table and this query then performed really well for all of our clients over the last 3 years or so.

However, recently one of our clients moved their production database to a new UAT environment where they were supposed to test a major new application upgrade we delivered to the client. The UAT database server it seemed had significantly lesser resources than the prod database server and the above query started behaving pretty badly on the UAT environment, taking upwards of 35-40 seconds for execution.

I was tasked again to optimise the query / Stored Procedure encapsulating this query to make it workable on the UAT environment. I tried a lot of approaches using JOIN’s, tweaked inner query, and other such things, but the performance did not improve. During my research then, I landed on LAG / LEAD Sql Server Analytic functions which I was unaware of previously.

And I saw my solution right there using the LEAD function. I quickly re-wrote my query using the LEAD function to the following:

SELECT TOP 1 ProfileNumber + 1
FROM
(
	SELECT  ProfileNumber,
			--We are specifying Default value as 2 ahead for the last row, so the last row satisfies the WHERE clause of outer SELECT statement
			--when @sStartNumeric equals ProfileNumber of the last row. The ProfileNumber + 1 in outer SELECT ensures the value returned is
			--1 number ahead of the last row (and not 2 numbers ahead).
			LEAD(ProfileNumber, 1, ProfileNumber + 2) OVER (ORDER BY ProfileNumber) AS NextProfileNumber
	FROM Profiles
	WHERE ProfileNumber IS NOT NULL
		AND ProfileNumber >= @sStartNumeric
) q
WHERE NextProfileNumber > ProfileNumber + 1
ORDER BY ProfileNumber

And yeah, the performance improved dramatically. The average execution time went to 3.25 seconds on the UAT environment which was pretty acceptable considering the UAT server resources were lesser than the production one.

In this query, we use the LEAD function to figure out 2-consecutive Profiles table rows ordered by ProfileNumber where ProfileNumber varied by more than 1 between the 2 rows.
To handle the edge-case where there was no gap between the Profile Numbers essentially meaning the query won’t find any row where its ProfileNumber varied by more than 1 than the subsequent row, we provided a default value of ProfileNumber + 2. As per Sql Server docs for the default value:

The value to return when offset is beyond the scope of the partition.

LEAD (Transact-SQL) – SQL Server | Microsoft Learn

This meant for the last row, we artificially created a ProfileNumber which exceeded the last row’s ProfileNumber by 2 thus ensuring the last row would match if no other rows matched. And the outer SELECT statement than returned the ProfileNumber which is 1 greater than the last row’s ProfileNumber.

There were a few other edge cases like when there’s no row in the table, or the Profile Number explicitly passed by the Agent itself did not exist that we handled in the SP rather than trying to handle those edge cases in this query in order to aid performance by not making the query too complex.

In the end, it was a Happy learning experience adding a few more Sql functions to my arsenal for use in the future. Happy coding!!!