# Locate the smallest missing element based on a specific formula

I need to be able to locate a missing element from a table with tens-of-millions of rows, and has a primary key of a `BINARY(64)` column (which is the input value to calculate from). These values are mostly inserted in order, but on occasion I want to reuse a previous value that was deleted. It's infeasible to modify the deleted records with a `IsDeleted` column, as sometimes a row is inserted that is many millions of values ahead of the currently existing rows. This means the sample data would look something like:

``````KeyCol : BINARY(64)
0x..000000000001
0x..000000000002
0x..FFFFFFFFFFFF
``````

So inserting all the missing values between `0x000000000002` and `0xFFFFFFFFFFFF` is infeasible, the amount of time and space used would be undesirable. Essentially, when I run the algorithm, I expect it to return `0x000000000003`, which is the first opening.

I've come up with a binary-search algorithm in C#, which would query the database for each value at position `i`, and test if that value was expected. For context, my terrible algorithm: https://codereview.stackexchange.com/questions/174498/binary-search-for-a-missing-or-default-value-by-a-given-formula

This algorithm would run, for example, 26-27 SQL-queries on a table with 100,000,000 items. (That doesn't seem like a lot, but it's going to be occurring very frequently.) Currently, this table has approximately 50,000,000 rows in it, and performance is becoming noticeable.

My first alternative thought is to translate this to a stored-procedure, but that has it's own hurdles. (I have to write a `BINARY(64) + BINARY(64)` algorithm, as well as a slew of other things.) This would be painful, but not infeasible. I've also considered implementing the translation algorithm based on `ROW_NUMBER`, but I have a really bad gut feeling about this. (A `BIGINT` is not nearly big enough for these values.)

I'm up for other suggestions, as I really need this to be as quick as possible. For what it's worth the only column selected by the C# query is the `KeyCol`, the others are irrelevant for this portion.

Also, for what it's worth, the current query that fetches the appropriate record is along the lines of:

``````SELECT [KeyCol]
FROM [Table]
ORDER BY [KeyCol] ASC
OFFSET <VALUE> ROWS FETCH FIRST 1 ROWS ONLY
``````

Where `<VALUE>` is the index supplied by the algorithm. I also haven't had the `BIGINT` issue with `OFFSET` yet, but I will. (Only having 50,000,000 rows right now means that it never asks for an index above that value, but at some point it'll get above the `BIGINT` range.)

• From deletions, the `gap:sequential` ratio is about `1:20`;
• The last 35,000 rows in the table have values > `BIGINT`'s maximum;
• Looking for a bit more clarification ... 1) why do you need the 'smallest' available binary as opposed to any available binary? 2) going forward, any chance of putting a `delete` trigger on the table that would dump the now-available binary to a separate table (eg, `create table available_for_reuse(id binary64)`), especially in light of the requirement to do this lookup very frequently? Sep 5, 2017 at 20:52
• @markp The smallest available value has a "preference" to it, think of it as similar to a URL shortener, you don't want the next longer value, because someone can manually specify something like `mynameisebrown` which would mean you would get `mynameisebrowo`, which you wouldn't want if `abc` is available. Sep 5, 2017 at 20:54
• What does a query like `select t1.keycol+1 as aa from t as t1 where not exists (select 1 from t as t2 where t2.keycol = t1.keycol+1) order by keycol fetch first 1 rows only` give you? Sep 5, 2017 at 20:55
• @Lennart Not what I need. Had to use `SELECT TOP 1 ([T1].[KeyCol] + 1) AS [AA] FROM [SearchTestTableProper] AS [T1] WHERE NOT EXISTS (SELECT 1 FROM [SearchTestTableProper] AS [T2] WHERE [T2].[KeyCol] = [T1].[KeyCol] + 1) ORDER BY [KeyCol]`, which always returns `1`. Sep 5, 2017 at 21:02
• I wonder whether that is some kind of casting error, it should not return 1. What does select t1.keycol from ... return? Sep 5, 2017 at 21:07

Joe's already hit on most of the points I just spent an hour typing up, in summary:

• highly doubtful you'll every run out of `KeyCol` values < `bigint` max (9.2e18), so conversions (if necessary) to/from `bigint` should not be a problem as long as you limit searches to `KeyCol <= 0x00..007FFFFFFFFFFFFFFF`
• I can't think of a query that's going to 'efficiently' find a gap all the time; you may get lucky and find a gap near the beginning of your search, or you could pay dearly to find the gap quite a ways into your search
• while I briefly thought about how to parallelize the query, I quickly discarded that idea (as a DBA I would not want to find out that your process is routinely bogging down my dataserver with 100% cpu utilization ... especially if you could have multiple copies of this running at the same time); noooo ... parallelization is going to be out of the question

So, what to do?

Let's put the (repeated, cpu-intensive, brute force) search idea on hold for a minute and look at the bigger picture.

• on an average basis one instance of this search is going to need to scan millions of index keys (and require a good bit of cpu, thrashing of db cache, and a user watching a spinning hour glass) just to locate a single value
• multiply the cpu-usage/cache-thrashing/spinning-hour-glass by ... how many searches do you expect in a day?
• keep in mind that, generally speaking, each instance of this search is going to need to scan the same set of (millions of) index keys; that's a LOT of repeated activity for such minimal benefit

What I'd like to propose is some additions to the data model ...

• a new table that keeps track of a set of 'available to use' `KeyCol` values, eg: `available_for_use(KeyCol binary(64) not null primary key)`
• how many records you maintain in this table is up to you to decide, eg, perhaps enough for a month's worth of activity?
• the table can periodically (weekly?) be 'topped off' with a new batch of `KeyCol` values (perhaps create a 'top off' stored proc?) [eg, update Joe's `select/top/row_number()` query to do a `top 100000`]
• you could setup a monitoring process to keep track of the number of available entries in `available_for_use` just in case you ever start to run low on values
• a new (or modified) DELETE trigger on the >main_table< that places deleted `KeyCol` values into our new table `available_for_use` whenever a row is deleted from the main table
• if you allow updates of the `KeyCol` column then a new/modified UPDATE trigger on the >main_table< to also keep our new table `available_for_use` updated
• when it comes time to 'search' for a new `KeyCol` value you `select min(KeyCol) from available_for_use` (obviously there's a bit more to this since a) you'll need to code for concurrency issues - don't want 2 copies of your process grabbing the same `min(KeyCol)` and b) you'll need to delete `min(KeyCol)` from the table; this should be relatively easy to code, perhaps as a stored proc, and can be addressed in another Q&A if necessary)
• in a worst case scenario, if your `select min(KeyCol)` process finds no available rows, you could kick off your 'top off' proc to generate a new batch of rows

With these proposed changes to the data model:

• you eliminate a LOT of excessive cpu cycles [your DBA will thank you]
• you eliminate ALL of those repetitive index scans and cache thrashing [your DBA will thank you]
• your users no longer have to watch the spinning hour glass (though they may not like the loss of an excuse to step away from their desk)
• there are plenty of ways to monitor the size of the `available_for_use` table to make sure you never run out of new values

Yes, the proposed `available_for_use` table is just a table of pre-generated 'next key' values; and yes, there's a potential for some contention when grabbing the 'next' value, but any contention a) is easily addressed through proper table/index/query design and b) is going to be minor/short-lived compared to the overhead/delays with the current idea of repeated, brute force, index searches.

• This is actually similar to what I ended up thinking in chat, I'm thinking probably run every 15-20 minutes, since Joe's query runs relatively quickly (on the live server with contrived test-data worst-case was 4.5s, best was 0.25s), I can pull in a days' worth of keys, and no less than `n` keys (probably 10 or 20, to force it to search for what might be lower, more desirable values). Really appreciate the answer here though, you put the thoughts in writing! :) Sep 6, 2017 at 0:24
• ahhhh, if you've got an application/middleware server that can provide an intermediate cache of available `KeyCol` values ... yeah, that would work, too :-) and obviously eliminate the need for a data model change eh Sep 6, 2017 at 0:28
• Precisely, I'm thinking about building a static cache on the web-application itself even, the only problem is that it's distributed (so I need to sync the cache across servers), which means a SQL or middle-ware implementation would be much preferred. :) Sep 6, 2017 at 0:36
• hmmmm ... a distributed `KeyCol` manager, and the need to code for potential PK violations if 2 (or more) concurrent instances of the app try to use the same `KeyCol` value ... yuck ... definitely easier with a single middleware server or a db-centric solution Sep 6, 2017 at 0:44

There are a few challenges with this question. Indexes in SQL Server can do the following very efficiently with just a few logical read each:

• check that a row exists
• check that a row doesn't exist
• find the next row starting at some point
• find the previous row starting at some point

However, they cannot be used to find the Nth row in an index. Doing that requires you roll your own index stored as a table or to scan the first N rows in the index. Your C# code heavily relies on the fact that you can efficiently find the Nth element of the array, but you can't do that here. I think that algorithm isn't usable for T-SQL without a data model change.

The second challenge relates to the restrictions on the `BINARY` data types. As far as I can tell you cannot perform addition, subtraction, or division in the usual ways. You can convert your `BINARY(64)` to a `BIGINT` and it won't throw conversion errors, but the behavior is not defined:

Conversions between any data type and the binary data types are not guaranteed to be the same between versions of SQL Server.

In addition, the lack of conversion errors is somewhat of a problem here. You can convert anything larger than the biggest possible `BIGINT` value but it'll give you the wrong results.

It's true that you have values right now that are bigger than 9223372036854775807. However, if you're always starting at 1 and searching for the smallest minimum value then those large values cannot be relevant unless your table has more than 9223372036854775807 rows. This seems unlikely because your table at that point would be around 2000 exabytes, so for the purposes of answering your question I'm going to assume that the very large values do not need to be searched. I'm also going to do data type conversion because they seem to be unavoidable.

For the test data, I inserted the equivalent of 50 million sequential integers into a table along with 50 million more integers with a single value gap about every 20 values. I also inserted a single value that won't properly fit in a signed `BIGINT`:

``````CREATE TABLE dbo.BINARY_PROBLEMS (
KeyCol BINARY(64) NOT NULL
);

INSERT INTO dbo.BINARY_PROBLEMS WITH (TABLOCK)
SELECT CAST(SUM(OFFSET) OVER (ORDER BY (SELECT NULL) ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS BINARY(64))
FROM
(
SELECT 1 + CASE WHEN t.RN > 50000000 THEN
CASE WHEN ABS(CHECKSUM(NewId()) % 20)  = 10 THEN 1 ELSE 0 END
ELSE 0 END OFFSET
FROM
(
SELECT TOP (100000000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) RN
FROM master..spt_values t1
CROSS JOIN master..spt_values t2
CROSS JOIN master..spt_values t3
) t
) tt
OPTION (MAXDOP 1);

CREATE UNIQUE CLUSTERED INDEX CI_BINARY_PROBLEMS ON dbo.BINARY_PROBLEMS (KeyCol);

-- add a value too large for BIGINT
INSERT INTO dbo.BINARY_PROBLEMS
SELECT CAST(0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000008000000000000000 AS BINARY(64));
``````

That code took a few minutes to run on my machine. I made the first half of the table not have any gaps to represent a sort of worse case for performance. The code that I used to solve the problem scans the index in order so it will finish very quickly if the first gap is early on in the table. Before we get to that let's verify that the data is as it should be:

``````SELECT TOP (2) KeyColBigInt
FROM
(
SELECT KeyCol
, CAST(KeyCol AS BIGINT) KeyColBigInt
FROM dbo.BINARY_PROBLEMS
) t
ORDER By KeyCol DESC;
``````

The results suggest that the maximum value that we converts to `BIGINT` is 102500672:

``````╔══════════════════════╗
║     KeyColBigInt     ║
╠══════════════════════╣
║ -9223372036854775808 ║
║            102500672 ║
╚══════════════════════╝
``````

There are 100 million rows with values that fit into BIGINT as expected:

``````SELECT COUNT(*)
FROM dbo.BINARY_PROBLEMS
WHERE KeyCol < 0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000007FFFFFFFFFFFFFFF;
``````

One approach to this problem is to scan the index in order and to quit as soon as a row's value doesn't match the expected `ROW_NUMBER()` value. The entire table does not need to be scanned to get the first row: only the rows up until the first gap. Here's one way to write code that is likely to get that query plan:

``````SELECT TOP (1) KeyCol
FROM
(
SELECT KeyCol
, CAST(KeyCol AS BIGINT) KeyColBigInt
, ROW_NUMBER() OVER (ORDER BY KeyCol) RN
FROM dbo.BINARY_PROBLEMS
WHERE KeyCol < 0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000007FFFFFFFFFFFFFFF
) t
WHERE KeyColBigInt <> RN
ORDER BY KeyCol;
``````

For reasons that won't fit in this answer, this query will often be run serially by SQL Server and SQL Server will often underestimate the number of rows that need to be scanned before the first match is found. On my machine, SQL Server scans 50000022 rows from the index before finding the first match. The query takes 11 seconds to run. Note that this returns the first value past the gap. It's not clear which row you want exactly, but you should be able to change the query to fit your needs without a lot of trouble. Here's what the plan looks like:

My only other idea was to bully SQL Server into using parallelism for the query. I have four CPUs, so I'm going to split the data up into four ranges and do seeks on those ranges. Each CPU will be assigned a range. To calculate the ranges I just grabbed the max value and assumed that data was evenly distributed. If you want to be smarter about it you could look at a sampled stats histogram for the column values and build your ranges that way. The code below relies on a lot of undocumented tricks that aren't safe for production, including trace flag 8649:

``````SELECT TOP 1 ca.KeyCol
FROM (
SELECT 1 bucket_min_value, 25625168 bucket_max_value
UNION ALL
SELECT 25625169, 51250336
UNION ALL
SELECT 51250337, 76875504
UNION ALL
SELECT 76875505, 102500672
) buckets
CROSS APPLY (
SELECT TOP 1 t.KeyCol
FROM
(
SELECT KeyCol
, CAST(KeyCol AS BIGINT) KeyColBigInt
, buckets.bucket_min_value - 1 + ROW_NUMBER() OVER (ORDER BY KeyCol) RN
FROM dbo.BINARY_PROBLEMS
WHERE KeyCol >= CAST(buckets.bucket_min_value AS BINARY(64)) AND KeyCol <=  CAST(buckets.bucket_max_value AS BINARY(64))
) t
WHERE t.KeyColBigInt <> t.RN
ORDER BY t.KeyCol
) ca
ORDER BY ca.KeyCol
OPTION (QUERYTRACEON 8649);
``````

Here is what the parallel nested loop pattern looks like:

Overall, the query does more work than before since it'll scan more rows in the table. However, it now runs in 7 seconds on my desktop. It might parallelize better on a real server. Here's a link to the actual plan.

I really can't think of a good way to solve this problem. Doing the calculation outside of SQL or changing the data model may be your best bets.

• Even if the best answer is "this won't work well in SQL", at least it tells me where to move next. :) Sep 6, 2017 at 0:36

Here's an answer that's probably not gonna work for you, but I'll add it anyhow.

Even though BINARY(64) is enumerable there is poor support to determine the successor of an item. Since BIGINT appears to be too small for your domain you might consider using a DECIMAL(38,0), which seems to be the largest NUMBER type in SQL-server.

``````CREATE TABLE SearchTestTableProper
( keycol decimal(38,0) not null primary key );

INSERT INTO SearchTestTableProper (keycol)
VALUES (1),(2),(3),(12);
``````

Finding the first gap is easy since we can construct the number we are looking for:

``````select top 1 t1.keycol+1
from SearchTestTableProper t1
where not exists (
select 1
from SearchTestTableProper t2
where t2.keycol = t1.keycol + 1
)
order by t1.keycol;
``````

A nested loop join over the p.k. index should be sufficient to find first availible item.