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 &lt;VALUE&gt; ROWS FETCH FIRST 1 ROWS ONLY


Where &lt;VALUE&gt; 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.)

Some additional data:


From deletions, the gap:sequential ratio is about 1:20;
The last 35,000 rows in the table have values > BIGINT's maximum;
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 &gt; 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 &lt; 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 &lt; 0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000007FFFFFFFFFFFFFFF
) t
WHERE KeyColBigInt &lt;&gt; 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 &gt;= CAST(buckets.bucket_min_value AS BINARY(64)) AND KeyCol &lt;=  CAST(buckets.bucket_max_value AS BINARY(64))
    ) t
    WHERE t.KeyColBigInt &lt;&gt; 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.