UPDATE [SourceTable]
SET
Bad_Count=
(
SELECT
COUNT(*)
FROM Bad_Phrase
WHERE
[SourceTable].Name like '%'+Bad_Phrase.PHRASE+'%'
)
在英语中,此查询计算Bad_Phrase中列出的不同短语的数量,这些短语是SourceTable中字段Name的子字符串,然后将该结果放在字段Bad_Count中.
我想知道如何让这个查询运行得更快.
解决方法
Full script to generate a fake data set and try out the new approach
TL; DR
在我的机器和这个假数据集上,原始方法需要大约4个小时才能运行.拟议的新方法大约需要10分钟,这是一项相当大的改进.以下是拟议方法的简短摘要：
>对于每个名称,从每个字符偏移量开始生成子字符串(并且以最长的错误短语的长度为上限,作为优化)
>在这些子字符串上创建聚簇索引
>对于每个坏词,执行搜索这些子串以识别任何匹配
>对于每个原始字符串,计算与该字符串的一个或多个子字符串匹配的不同坏短语的数量
原始方法：算法分析
从原始UPDATE语句的计划中,我们可以看到工作量与名称数量(15MM)和短语数量(3K)成线性比例.因此,如果我们将名称和短语的数量乘以10,则整体运行时间将慢约100倍.
查询实际上也与名称的长度成正比;虽然这在查询计划中有点隐藏,但它通过“执行次数”来寻找表盘.在实际计划中,我们可以看到每个名称不仅发生一次,而且名称中每个字符偏移实际上发生一次.因此,这种方法在运行时复杂性方面是O(#names * #words * 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％(其余为子串的预处理).
最后,执行实际更新语句,使用LEFT 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对于每个批次都是独立的,并且很容易适合内存.您可以根据需要操作批量大小,但在一个批次中尝试所有15MM行是不明智的.
>我在sql 2014上,而不是sql 2005,因为我无法访问sql 2005计算机.我一直小心不要使用sql 2005中没有的任何语法,但我仍然可以从sql 2012中的tempdb lazy write功能和sql 2014中的parallel SELECT INTO功能中获益.
>名称和短语的长度对新方法非常重要.我假设坏短语通常很短,因为这可能与现实世界的用例相匹配.名字比坏词长得多,但假设不是数千个字符.我认为这是一个公平的假设,较长的名称字符串也会减慢您的原始方法.
>改进的某些部分(但无处接近全部)是由于新方法可以比旧方法(运行单线程)更有效地利用并行性.我使用的是四核笔记本电脑,因此有一种可以使用这些内核的方法很不错.
相关博文
Aaron Bertrand在他的博客文章One way to get an index seek for a leading %wildcard中更详细地探讨了这种类型的解决方案.
