帶有子查詢的大表更新緩慢

由於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 中列出的不同片語的數量，這些片語是 the 中欄位的子字元串，Name然後SourceTable將該結果放入 field Bad_Count。

我想要一些關於如何讓這個查詢執行得更快的建議。

雖然我同意其他評論者的觀點，即這是一個計算成本很高的問題，但我認為通過調整您正在使用的 SQL 有很大的改進空間。為了說明，我創建了一個包含 15MM 名稱和 3K 片語的假數據集，執行舊方法並執行新方法。

生成假數據集並嘗試新方法的完整腳本

TL; 博士

在我的機器和這個假數據集上，原來的方法需要大約 4 個小時才能執行。提議的新方法大約需要 10 分鐘，這是一個相當大的改進。以下是所提議方法的簡短摘要：

• 對於每個名稱，從每個字元偏移量開始生成子字元串（並以最長的壞片語的長度為上限，作為優化）
• 在這些子字元串上創建聚集索引
• 對於每個錯誤的片語，對這些子字元串執行搜尋以辨識任何匹配項
• 對於每個原始字元串，計算與該字元串的一個或多個子字元串匹配的不同壞片語的數量

原始方法：算法分析

從原始UPDATE語句的計劃中，我們可以看到工作量與名稱的數量（15MM）和片語的數量（3K）都呈線性比例關係。因此，如果我們將名稱和片語的數量都乘以 10，則整體執行時間將慢約 100 倍。

查詢實際上也與長度成正比name；雖然這在查詢計劃中有點隱藏，但它通過“執行次數”來尋找表假離線。在實際計劃中，我們可以看到這不僅發生在每個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子字元串上的 對每個批次都是獨立的，並且很容易適應記憶體。您可以根據需要操縱批量大小，但在一批中嘗試所有 15MM 行是不明智的。
• 我使用的是 SQL 2014，而不是 SQL 2005，因為我無法訪問 SQL 2005 機器。我一直小心不要使用 SQL 2005 中不可用的任何語法，但我可能仍會從SQL 2012+ 中的tempdb 延遲寫入功能和 SQL 2014 中的並行 SELECT INTO功能中受益。
• 名稱和片語的長度對於新方法都相當重要。我假設不好的片語通常相當短，因為這可能與現實世界的案例相匹配。名稱比壞片語長很多，但假設不是數千個字元。我認為這是一個公平的假設，更長的名稱字元串也會減慢您原來的方法。
• 部分改進（但遠非全部）是由於新方法比舊方法（執行單執行緒）更有效地利用並行性這一事實。我在一台四核筆記型電腦上，所以很高興有可以使用這些核心的方法。

相關博文

Aaron Bertrand在他的部落格文章One way to get an index seek for aleading %wildcard中更詳細地探討了這種類型的解決方案。

讓我們暫時擱置Aaron Bertrand在評論中提出的明顯問題：

因此，您正在掃描表 3K 次，並可能將所有 15MM 行全部更新 3K 次，並且您希望它很快？

您的子查詢在兩邊都使用萬用字元這一事實極大地影響了 sargability。從該部落格文章中引用：

這意味著 SQL Server 必須從 Product 表中讀取每一行，檢查名稱中是否有“nut”，然後返回我們的結果。

將每個“壞詞”和“產品”換成“堅果”這個詞SourceTable，然後將其與 Aaron 的評論結合起來，您應該開始明白為什麼使用您目前的算法使其快速執行非常困難（閱讀不可能）。

我看到幾個選項：

1. 說服企業購買具有如此強大功能的怪物伺服器，它通過剪切蠻力克服了查詢。（這不會發生，所以其他選擇更好）
2. 使用您現有的算法，接受一次痛苦，然後將其分散。這將涉及計算插入時的壞詞，這將減慢插入速度，並且僅在輸入/發現新的壞詞時更新整個表。
3. 接受傑夫的回答。這是一個很棒的算法，比我想出的任何算法都要好得多。
4. 執行選項 2，但將您的算法替換為 Geoff 的算法。

根據您的要求，我會推薦選項 3 或 4。

引用自：https://dba.stackexchange.com/questions/115984