根据特定公式找到最小的缺失元素

Question

我需要能够从具有数千万行的表中找到缺失的元素，并且有一个BINARY(64)列的主键（这是要计算的输入值）。这些值大多按顺序插入，但有时我想重用已删除的先前值。用IsDeleted列修改已删除的记录是不可行的，因为有时插入的行比当前存在的行高数百万个值。这意味着示例数据将类似于：

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

因此在0x000000000002和之间插入所有缺失值0xFFFFFFFFFFFF是不可行的，使用的时间和空间量将是不可取的。本质上，当我运行算法时，我希望它返回0x000000000003，这是第一个开口。

我在 C# 中提出了一个二进制搜索算法，它将查询数据库中位置的每个值i，并测试该值是否是预期的。对于上下文，我可怕的算法：https : //codereview.stackexchange.com/questions/174498/binary-search-for-a-missing-or-default-value-by-a-given-formula

例如，该算法将在具有 100,000,000 个项目的表上运行 26-27 个 SQL 查询。（这看起来并不多，但它会非常频繁地发生。）目前，该表中大约有 50,000,000 行，性能变得很明显。

我的第一个替代想法是将其转换为存储过程，但这有其自身的障碍。（我必须编写一个BINARY(64) + BINARY(64)算法，以及大量其他东西。）这会很痛苦，但并非不可行。我也考虑过实现基于的翻译算法ROW_NUMBER，但我对此有一种非常糟糕的直觉。（BIGINT对于这些值，A几乎不够大。）

我愿意接受其他建议，因为我真的需要尽快解决这个问题。值得一提的是，C# 查询选择的唯一列是KeyCol，其他列与此部分无关。

---

此外，对于它的价值，获取适当记录的当前查询是这样的：

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

<VALUE>算法提供的索引在哪里。我也没有遇到过这个BIGINT问题OFFSET，但我会的。（现在只有 50,000,000 行意味着它从不要求高于该值的索引，但在某些时候它会超出BIGINT范围。）

一些额外的数据：

• 从删除来看，该gap:sequential比例约为1:20;
• 表中最后 35,000 行的值 >BIGINT的最大值；

Answer 1

这个问题有一些挑战。SQL Server 中的索引可以非常有效地执行以下操作，每个索引只需几个逻辑读取：

• 检查一行是否存在
• 检查一行不存在
• 找到从某个点开始的下一行
• 找到从某个点开始的前一行

但是，它们不能用于查找索引中的第 N 行。这样做需要您滚动存储为表的自己的索引或扫描索引中的前 N ​​行。您的 C# 代码在很大程度上依赖于您可以有效地找到数组的第 N 个元素这一事实，但在这里您不能这样做。我认为该算法在没有数据模型更改的情况下不适用于 T-SQL。

第二个挑战与BINARY数据类型的限制有关。据我所知，您不能以通常的方式执行加法、减法或除法。您可以将您的转换BINARY(64)为 aBIGINT并且它不会抛出转换错误，但未定义行为：

不保证任何数据类型和二进制数据类型之间的转换在 SQL Server 版本之间是相同的。

此外，这里缺少转换错误也是一个问题。你可以转换任何大于最大可能BIGINT值的东西，但它会给你错误的结果。

确实，您现在有大于 9223372036854775807 的值。但是，如果您总是从 1 开始并搜索最小的最小值，那么除非您的表有超过 9223372036854775807 行，否则这些大值将不相关。这似乎不太可能，因为那时您的表大约为 2000 艾字节，因此为了回答您的问题，我将假设不需要搜索非常大的值。我还要做数据类型转换，因为它们似乎是不可避免的。

对于测试数据，我将相当于 5000 万个连续整数以及另外 5000 万个整数插入到表中，并且每 20 个值有一个值差距。我还插入了一个无法正确放入已签名的值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));

该代码需要几分钟才能在我的机器上运行。我让表格的前半部分没有任何间隙来代表性能更差的情况。我用来解决问题的代码按顺序扫描索引，因此如果第一个间隙在表中较早出现，它将很快完成。在我们开始之前，让我们验证数据是否应该是这样：

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

结果表明，我们转换为的最大值BIGINT是 102500672：

????????????????????????
?     KeyColBigInt     ?
????????????????????????
? -9223372036854775808 ?
?            102500672 ?
????????????????????????

有 1 亿行的值符合预期的 BIGINT：

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

解决此问题的一种方法是按顺序扫描索引并在行的值与预期ROW_NUMBER()值不匹配时立即退出。不需要扫描整个表来获取第一行：只有直到第一个间隙为止的行。这是编写可能获得该查询计划的代码的一种方法：

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;

由于不适合此答案的原因，此查询通常由 SQL Server 串行运行，并且 SQL Server 通常会低估在找到第一个匹配项之前需要扫描的行数。在我的机器上，SQL Server 在找到第一个匹配项之前从索引中扫描 50000022 行。查询运行需要 11 秒。请注意，这将返回经过间隙的第一个值。不清楚您到底想要哪一行，但您应该能够更改查询以满足您的需求，而不会遇到很多麻烦。这是计划的样子：

我唯一的其他想法是强迫 SQL Server 使用并行性进行查询。我有四个 CPU，所以我要将数据分成四个范围并在这些范围内进行搜索。每个 CPU 都会被分配一个范围。为了计算范围，我只是获取了最大值并假设数据是均匀分布的。如果您想更聪明一点，您可以查看列值的采样统计直方图并以此方式构建范围。下面的代码依赖于许多对生产不安全的未记录的技巧，包括跟踪标志 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);

这是并行嵌套循环模式的样子：

总的来说，查询比以前做的工作更多，因为它将扫描表中的更多行。但是，它现在在我的桌面上运行 7 秒。它可能会在真实服务器上更好地并行化。这是实际计划的链接。

实在想不出解决这个问题的好办法。在 SQL 之外进行计算或更改数据模型可能是您最好的选择。

Answer 2

乔已经找到了我花了一个小时打字的大部分要点，总结如下：

• 非常怀疑你会用完KeyCol值 < bigintmax (9.2e18)，所以bigint只要你将搜索限制为KeyCol <= 0x00..007FFFFFFFFFFFFFFF
• 我想不出一个查询可以一直“有效”地找到差距；您可能会很幸运并在搜索开始时找到一个差距，或者您可能会付出高昂的代价在搜索中找到差距
• 虽然我简要地考虑了如何并行化查询，但我很快就放弃了这个想法（作为一名 DBA，我不想发现您的进程经常以 100% 的 CPU 利用率使我的数据服务器陷入困境……尤其是如果您可以有多个同时运行的副本）；noooo ...并行化将是不可能的

那么该怎么办？

让我们暂时搁置（重复的、cpu 密集型、蛮力的）搜索想法，看看更大的图景。

• 平均而言，此搜索的一个实例将需要扫描数百万个索引键（并且需要大量的 CPU、数据库缓存的颠簸和用户观看旋转的沙漏）只是为了找到一个值
• 将 CPU 使用率/高速缓存颠簸/旋转沙漏乘以...您预计一天中的搜索次数是多少？
• 请记住，一般来说，此搜索的每个实例都需要扫描同一组（数百万个）索引键；为了这种最小的好处，这是很多重复的活动

我想建议的是对数据模型进行一些补充......

• 一个记录一组“可用”KeyCol值的新表，例如：available_for_use(KeyCol binary(64) not null primary key)
• 您在此表中保留多少条记录由您决定，例如，可能足以用于一个月的活动？
• 该表可以定期（每周？）用一批新KeyCol值“加满” （也许创建一个“加满”存储过程？）[例如，更新 Joe 的select/top/row_number()查询来做一个top 100000]
• 您可以设置一个监控过程来跟踪可用条目的数量，available_for_use 以防万一您开始运行低值
• >main_table< 上的一个新的（或修改过的）DELETE 触发器，每当从主表中删除一行时，它就会将删除的KeyCol值放入我们的新表available_for_use中
• 如果您允许更新该KeyCol列，那么在 >main_table< 上的一个新的/修改的 UPDATE 触发器也可以使我们的新表保持available_for_use更新
• 当需要“搜索”一个新KeyCol值时，您select min(KeyCol) from available_for_use（显然还有更多内容，因为 a）您需要为并发问题编写代码 - 不希望您的进程的 2 个副本占用相同的内容min(KeyCol)和 b）您'需要min(KeyCol)从表中删除；这应该相对容易编码，也许作为一个存储过程，如有必要，可以在另一个问答中解决）
• 在最坏的情况下，如果您的select min(KeyCol)流程没有找到可用的行，您可以启动“顶部关闭”过程以生成新的一批行

通过对数据模型的这些提议更改：

• 你消除了很多过多的 CPU 周期 [你的 DBA 会感谢你]
• 您消除了所有那些重复的索引扫描和缓存抖动 [您的 DBA 会感谢您]
• 您的用户不再需要观看旋转的沙漏（尽管他们可能不喜欢失去离开办公桌的借口）
• 有很多方法可以监控available_for_use表的大小，以确保您永远不会用完新值

是的，建议的available_for_use表只是一个预先生成的“下一个键”值的表；是的，在获取“下一个”值时可能会出现一些争用，但是任何争用 a) 都可以通过适当的表/索引/查询设计轻松解决，并且 b) 与开销相比将是次要的/短暂的/与当前重复、蛮力、索引搜索的想法延迟。