使用子查询对大表进行缓慢更新

Question

由于SourceTable具有 >15MM 记录和Bad_Phrase>3K 记录，以下查询需要将近 10 个小时才能在 SQL Server 2005 SP4 上运行。

UPDATE [SourceTable] 
SET 
    Bad_Count=
             (
               SELECT 
                  COUNT(*) 
               FROM Bad_Phrase 
               WHERE 
                  [SourceTable].Name like '%'+Bad_Phrase.PHRASE+'%'
             )

在英语中，这个查询计数Bad_Phrase列出不同的短语是一个子领域的数量Name在SourceTable，然后把该结果在现场Bad_Count。

我想要一些关于如何让这个查询运行得更快的建议。

Answer 1

虽然我同意其他评论者的意见，即这是一个计算成本高的问题，但我认为通过调整您正在使用的 SQL 有很大的改进空间。为了说明这一点，我创建了一个包含 15MM 名称和 3K 短语的假数据集，运行旧方法，然后运行新方法。

生成假数据集并尝试新方法的完整脚本

TL; 博士

在我的机器和这个假数据集上，原始方法大约需要 4 个小时才能运行。建议的新方法大约需要 10 分钟，这是一个相当大的改进。以下是所提议方法的简短摘要：

• 对于每个名称，生成从每个字符偏移开始的子字符串（并以最长的坏短语的长度为上限，作为优化）
• 在这些子字符串上创建聚集索引
• 对于每个坏短语，对这些子字符串执行查找以识别任何匹配项
• 对于每个原始字符串，计算与该字符串的一个或多个子字符串匹配的不同坏短语的数量

原始方法：算法分析

从原始UPDATE语句的计划中，我们可以看到工作量与名称数量（15MM）和短语数量（3K）成线性比例。因此，如果我们将名称和短语的数量都乘以 10，则整体运行时间将慢约 100 倍。

查询实际上也与长度成正比name；虽然这在查询计划中有点隐藏，但它通过查找表假脱机的“执行次数”来实现。在实际计划中，我们可以看到这不仅在 per 发生一次name，而且实际上在name. 所以这种方法的运行时复杂度是 O( # names* # phrases* name length) 。

新方法：代码

此代码也可在完整的pastebin 中找到，但为了方便起见，我已将其复制到此处。pastebin 还具有完整的过程定义，其中包括您在下面看到的用于定义当前批次边界的@minId和@maxId变量。

-- For each name, generate the string at each offset
DECLARE @maxBadPhraseLen INT = (SELECT MAX(LEN(phrase)) FROM Bad_Phrase)
SELECT s.id, sub.sub_name
INTO #SubNames
FROM (SELECT * FROM SourceTable WHERE id BETWEEN @minId AND @maxId) s
CROSS APPLY (
    -- Create a row for each substring of the name, starting at each character
    -- offset within that string.  For example, if the name is "abcd", this CROSS APPLY
    -- will generate 4 rows, with values ("abcd"), ("bcd"), ("cd"), and ("d"). In order
    -- for the name to be LIKE the bad phrase, the bad phrase must match the leading X
    -- characters (where X is the length of the bad phrase) of at least one of these
    -- substrings. This can be efficiently computed after indexing the substrings.
    -- As an optimization, we only store @maxBadPhraseLen characters rather than
    -- storing the full remainder of the name from each offset; all other characters are
    -- simply extra space that isn't needed to determine whether a bad phrase matches.
    SELECT TOP(LEN(s.name)) SUBSTRING(s.name, n.n, @maxBadPhraseLen) AS sub_name 
    FROM Numbers n
    ORDER BY n.n
) sub
-- Create an index so that bad phrases can be quickly compared for a match
CREATE CLUSTERED INDEX IX_SubNames ON #SubNames (sub_name)

-- For each name, compute the number of distinct bad phrases that match
-- By "match", we mean that the a substring starting from one or more 
-- character offsets of the overall name starts with the bad phrase
SELECT s.id, COUNT(DISTINCT b.phrase) AS bad_count
INTO #tempBadCounts
FROM dbo.Bad_Phrase b
JOIN #SubNames s
    ON s.sub_name LIKE b.phrase + '%'
GROUP BY s.id

-- Perform the actual update into a "bad_count_new" field
-- For validation, we'll compare bad_count_new with the originally computed bad_count
UPDATE s
SET s.bad_count_new = COALESCE(b.bad_count, 0)
FROM dbo.SourceTable s
LEFT JOIN #tempBadCounts b
    ON b.id = s.id
WHERE s.id BETWEEN @minId AND @maxId

新方法：查询计划

首先，我们生成从每个字符偏移量开始的子串

然后在这些子串上创建聚集索引

现在，对于每个不好的短语，我们都会搜索这些子字符串以识别任何匹配项。然后我们计算与该字符串的一个或多个子字符串匹配的不同坏短语的数量。这确实是关键的一步；由于我们索引子字符串的方式，我们不再需要检查错误短语和名称的完整交叉产品。这一步进行实际计算，只占实际运行时间的 10% 左右（其余部分是子串的预处理）。

最后，执行实际的更新语句，使用 aLEFT OUTER JOIN将 0 分配给我们没有发现任何错误短语的任何名称。

新方法：算法分析

新方法可以分为两个阶段，预处理和匹配。让我们定义以下变量：

• N = # 名称
• B = # 不好的词组
• L = 平均名称长度，以字符为单位

预处理阶段是O(N*L * LOG(N*L))为了创建N*L子串，然后对它们进行排序。

实际匹配是O(B * LOG(N*L))为了寻找每个坏短语的子串。

通过这种方式，我们创建了一种算法，它不会随着坏词的数量线性扩展，当我们扩展到 3K 词组及更多时，这是一个关键的性能解锁。换句话说，只要我们从 300 个坏短语变成 3K 个坏短语，原始实现大约需要 10 倍的时间。类似地，如果我们要从 3K 个坏词组变成 30K 个，则需要另外 10 倍的时间。然而，新的实现将次线性扩展，实际上当扩展到 30K 坏词组时，所用时间不到 3K 坏词组测量时间的 2 倍。

假设/警告

• 我将整体工作分成适度大小的批次。这对于任何一种方法都可能是一个好主意，但对于新方法尤其重要，这样SORT子串的on 对每个批次都是独立的，并且很容易适应内存。您可以根据需要操纵批次大小，但在一批中尝试所有 15MM 行是不明智的。
• 我使用的是 SQL 2014，而不是 SQL 2005，因为我无法访问 SQL 2005 机器。我一直很小心不使用 SQL 2005 中没有的任何语法，但我可能仍然从SQL 2012+ 中的tempdb 延迟写入功能和SQL 2014 中的并行 SELECT INTO功能中受益。
• 名称和短语的长度对新方法来说相当重要。我假设坏短语通常很短，因为这可能与现实世界的用例相匹配。名称比坏短语要长很多，但假定不是数千个字符。我认为这是一个合理的假设，更长的名称字符串也会减慢您的原始方法。
• 部分改进（但远非全部）是由于新方法可以比旧方法（运行单线程）更有效地利用并行性。我在一台四核笔记本电脑上，所以很高兴有可以使用这些内核的方法。

相关博文

Aaron Bertrand在他的博客文章中更详细地探讨了这种类型的解决方案：一种获得领先 %wildcard 的索引搜索的方法。

Answer 2

让我们暂时搁置Aaron Bertrand在评论中提出的明显问题：

因此，您正在扫描表 3K 次，并可能将所有 15MM 行更新 3K 次，并且您希望它很快？

您的子查询在双方都使用通配符这一事实极大地影响了 sargability。引用那篇博文：

这意味着 SQL Server 必须读取 Product 表中的每一行，检查名称中是否有“nut”，然后返回我们的结果。

为每个“坏词”和“产品”换出“坚果”一词SourceTable，然后将其与 Aaron 的评论结合起来，您应该开始明白为什么使用当前算法使其快速运行非常困难（读起来不可能）。

我看到几个选项：

1. 说服企业购买一个强大的服务器，它可以通过剪切蛮力克服查询。（这不会发生，所以交叉手指其他选项更好）
2. 使用您现有的算法，接受一次痛苦，然后将其分散开。这将涉及计算插入时会减慢插入速度的坏词，并且只有在输入/发现新的坏词时才更新整个表。
3. 拥抱杰夫的回答。这是一个很棒的算法，比我想出的任何算法都要好。
4. 执行选项 2，但将您的算法替换为 Geoff 的算法。

根据您的要求，我会推荐选项 3 或 4。