Langsames Update für große Tabelle mit Unterabfrage

Bei SourceTablemehr als 15 Millionen Einträgen und Bad_Phrasemehr als 3.000 Einträgen dauert die Ausführung der folgenden Abfrage unter SQL Server 2005 SP4 fast 10 Stunden.

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

In Englisch zählt diese Abfrage die Anzahl der in Bad_Phrase aufgelisteten unterschiedlichen Phrasen, die eine Teilzeichenfolge des Felds Namein sind, SourceTableund platziert dieses Ergebnis dann in das Feld Bad_Count.

Ich hätte gerne einige Vorschläge, wie diese Abfrage erheblich schneller ausgeführt werden kann.

Obwohl ich mit anderen Kommentatoren übereinstimme, dass dies ein rechenintensives Problem ist, denke ich, dass es viel Raum für Verbesserungen gibt, wenn Sie die von Ihnen verwendete SQL optimieren. Zur Veranschaulichung erstelle ich einen gefälschten Datensatz mit 15-MM-Namen und 3-KB-Ausdrücken, führe den alten Ansatz aus und führe einen neuen Ansatz aus.

Vollständiges Skript zum Generieren eines gefälschten Datensatzes und Testen des neuen Ansatzes

TL; DR

Auf meinem Computer und diesem gefälschten Datensatz dauert der ursprüngliche Ansatz ca. 4 Stunden . Der vorgeschlagene neue Ansatz dauert ungefähr 10 Minuten , was eine erhebliche Verbesserung darstellt. Hier ist eine kurze Zusammenfassung des vorgeschlagenen Ansatzes:

• Generieren Sie für jeden Namen die Teilzeichenfolge, beginnend mit jedem Zeichenversatz (und als Optimierung begrenzt auf die Länge der längsten fehlerhaften Phrase).
• Erstellen Sie einen Clustered-Index für diese Teilzeichenfolgen
• Führen Sie für jede fehlerhafte Phrase eine Suche in diesen Teilzeichenfolgen durch, um Übereinstimmungen zu identifizieren
• Berechnen Sie für jede ursprüngliche Zeichenfolge die Anzahl der eindeutigen fehlerhaften Phrasen, die einer oder mehreren Teilzeichenfolgen dieser Zeichenfolge entsprechen

Ursprünglicher Ansatz: algorithmische Analyse

Aus dem Plan der ursprünglichen UPDATEAussage können wir ersehen, dass der Arbeitsaufwand sowohl zur Anzahl der Namen (15MM) als auch zur Anzahl der Phrasen (3K) linear proportional ist. Wenn wir also sowohl die Anzahl der Namen als auch die der Phrasen mit 10 multiplizieren, wird die Gesamtlaufzeit ~ 100-mal langsamer sein.

Die Abfrage ist tatsächlich proportional zur Länge der name; Dies ist zwar im Abfrageplan etwas versteckt, kommt aber in der "Anzahl der Ausführungen" zum Suchen in der Tabellenspule durch. Im aktuellen Plan können wir sehen, dass dies nicht nur einmal pro name, sondern tatsächlich einmal pro Zeichen im Offset auftritt name. Dieser Ansatz hat also eine Laufzeitkomplexität von 0 ( # names* # phrases* name length).

Neuer Ansatz: Code

Dieser Code ist auch im vollständigen Pastebin verfügbar , ich habe ihn jedoch aus Gründen der Benutzerfreundlichkeit hierher kopiert. Der Pastebin verfügt auch über die vollständige Prozedurdefinition, die die unten angezeigten Variablen @minIdund enthält @maxId, um die Grenzen des aktuellen Stapels zu definieren.

-- 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

Neuer Ansatz: Abfragepläne

Zuerst generieren wir die Teilzeichenfolge beginnend mit jedem Zeichenversatz

Erstellen Sie dann einen Clustered-Index für diese Teilzeichenfolgen

Nun suchen wir für jede fehlerhafte Phrase in diesen Teilzeichenfolgen nach Übereinstimmungen. Wir berechnen dann die Anzahl der eindeutigen fehlerhaften Phrasen, die mit einem oder mehreren Teilstrings dieser Zeichenfolge übereinstimmen. Dies ist wirklich der Schlüsselschritt; Aufgrund der Art und Weise, wie wir die Teilzeichenfolgen indiziert haben, müssen wir nicht länger ein vollständiges Kreuzprodukt aus fehlerhaften Phrasen und Namen prüfen. Dieser Schritt, der die eigentliche Berechnung durchführt, macht nur etwa 10% der tatsächlichen Laufzeit aus (der Rest ist die Vorverarbeitung von Teilzeichenfolgen).

Zuletzt führen Sie die eigentliche Update-Anweisung aus, indem Sie a verwenden LEFT OUTER JOIN, um allen Namen, für die wir keine fehlerhaften Phrasen gefunden haben, eine Anzahl von 0 zuzuweisen.

Neuer Ansatz: Algorithmische Analyse

Der neue Ansatz kann in zwei Phasen unterteilt werden: Vorverarbeitung und Matching. Definieren wir die folgenden Variablen:

• N = Anzahl der Namen
• B = Anzahl der schlechten Phrasen
• L = durchschnittliche Länge des Namens in Zeichen

Die Vorverarbeitung Phase O(N*L * LOG(N*L))zu schaffen , um N*LTeilstrings und dann sortieren.

Die tatsächliche Übereinstimmung dient O(B * LOG(N*L))dazu, nach jeder fehlerhaften Phrase in den Teilzeichenfolgen zu suchen.

Auf diese Weise haben wir einen Algorithmus erstellt, der nicht linear mit der Anzahl der fehlerhaften Phrasen skaliert. Dies ist eine wichtige Voraussetzung für die Leistungssteigerung, wenn wir auf 3K-Phrasen und mehr skalieren. Anders gesagt, die ursprüngliche Implementierung dauert ungefähr das 10-fache, solange wir von 300 schlechten Phrasen zu 3K schlechten Phrasen übergehen. In ähnlicher Weise würde es weitere 10x so lange dauern, wenn wir von 3K schlechten Phrasen auf 30K wechseln würden. Die neue Implementierung wird jedoch sublinear skaliert und benötigt weniger als das Zweifache der Zeit, die bei 3K-fehlerhaften Phrasen gemessen wird, wenn sie auf 30K-fehlerhafte Phrasen skaliert wird.

Annahmen / Vorbehalte

• Ich teile die Gesamtarbeit in bescheidene Losgrößen auf. Dies ist wahrscheinlich für beide Ansätze eine gute Idee, ist jedoch für den neuen Ansatz besonders wichtig, damit SORTdie Zeichenfolgen auf den Teilzeichenfolgen für jeden Stapel unabhängig sind und problemlos in den Speicher passen. Sie können die Stapelgröße nach Bedarf ändern, es ist jedoch nicht ratsam, alle 15-MM-Zeilen in einem Stapel zu testen.
• Ich bin in SQL 2014 und nicht in SQL 2005, da ich keinen Zugriff auf einen SQL 2005-Computer habe. Ich habe sorgfältig darauf geachtet, keine Syntax zu verwenden, die in SQL 2005 nicht verfügbar ist, aber ich kann trotzdem von der tempdb Lazy Write- Funktion in SQL 2012+ und der parallelen SELECT INTO- Funktion in SQL 2014 profitieren .
• Die Länge sowohl der Namen als auch der Phrasen ist für den neuen Ansatz ziemlich wichtig. Ich gehe davon aus, dass die schlechten Phrasen in der Regel ziemlich kurz sind, da dies wahrscheinlich mit realen Anwendungsfällen übereinstimmt. Die Namen sind viel länger als die schlechten Ausdrücke, es wird jedoch davon ausgegangen, dass sie nicht Tausende von Zeichen enthalten. Ich halte dies für eine faire Annahme, und längere Namensketten würden Ihren ursprünglichen Ansatz ebenfalls verlangsamen.
• Ein Teil der Verbesserung (aber bei weitem nicht alles) ist auf die Tatsache zurückzuführen, dass der neue Ansatz die Parallelität effektiver nutzen kann als der alte Ansatz (der Single-Threaded-Verfahren ausführt). Ich arbeite auf einem Quad-Core-Laptop, daher ist es schön, einen Ansatz zu haben, mit dem diese Kerne genutzt werden können.

Verwandte Blog-Post

Aaron Bertrand untersucht diese Art von Lösung ausführlicher in seinem Blogbeitrag. Eine Möglichkeit, einen Index nach einem führenden Platzhalter zu durchsuchen .

Lassen Sie uns das offensichtliche Problem, das Aaron Bertrand in den Kommentaren angesprochen hat, für eine Sekunde beiseite legen :

Sie scannen die Tabelle also dreimal und aktualisieren möglicherweise alle 15-Millimeter-Zeilen dreimal. Und Sie erwarten, dass sie schnell ist?

Die Tatsache, dass Ihre Unterabfrage die Platzhalter auf beiden Seiten verwendet, wirkt sich dramatisch auf die Sargabilität aus . So nehmen Sie ein Zitat aus diesem Blogeintrag entgegen:

Das bedeutet, dass SQL Server jede Zeile aus der Product-Tabelle lesen muss, prüfen muss, ob sie irgendwo im Namen "nut" enthält, und dann unsere Ergebnisse zurückgeben muss.

Tauschen Sie das Wort "nut" für jedes "bad word" und "Product" für aus SourceTableund kombinieren Sie dies mit Aarons Kommentar. Sie sollten verstehen, warum es extrem schwierig ist (unmöglich zu lesen), es mit Ihrem aktuellen Algorithmus schnell laufen zu lassen.

Ich sehe ein paar Möglichkeiten:

1. Überzeugen Sie das Unternehmen, einen Monsterserver zu kaufen, der so viel Leistung bietet, dass er die Anfrage mit aller Gewalt überwindet. (Das wird nicht passieren, drücken Sie die Daumen, die anderen Optionen sind besser)
2. Akzeptieren Sie den Schmerz mit Ihrem vorhandenen Algorithmus einmal und verteilen Sie ihn dann. Dies würde die Berechnung der fehlerhaften Wörter beim Einfügen umfassen, wodurch das Einfügen verlangsamt wird, und nur dann die gesamte Tabelle aktualisieren, wenn ein neues fehlerhaftes Wort eingegeben / entdeckt wird.
3. Umarme Geoffs Antwort . Dies ist ein großartiger Algorithmus und viel besser als alles, was ich mir ausgedacht hätte.
4. Tun Sie Option 2, aber ersetzen Sie Ihren Algorithmus durch Geoffs.

Abhängig von Ihren Anforderungen würde ich entweder Option 3 oder 4 empfehlen.

das ist erstmal nur ein seltsames update

Update [SourceTable]  
   Set [SourceTable].[Bad_Count] = [fix].[count]
  from [SourceTable] 
  join ( Select count(*) 
           from [Bad_Phrase]  
          where [SourceTable].Name like '%' + [Bad_Phrase].[PHRASE] + '%')

Wie '%' + [Bad_Phrase]. [PHRASE] bringt Sie um
Das kann keinen Index verwenden

Das
Datendesign ist nicht optimal für die Geschwindigkeit. Können Sie die [Bad_Phrase]. [PHRASE] in einzelne Phrasen / Wörter aufteilen?
Wenn die gleiche Phrase / Wort mehr als eine erscheint , kann man es mehr geben als einmal , wenn Sie es wollen , eine höhere Zählung haben
also die Anzahl der Zeilen in einem schlechten pharase gehen würde ,
wenn Sie können , dann wird dies viel viel schneller

Update [SourceTable]  
   Set [SourceTable].[Bad_Count] = [fix].[count]
  from [SourceTable] 
  join ( select [PHRASE], count(*) as count 
           from [Bad_Phrase] 
          group by [PHRASE] 
       ) as [fix]
    on [fix].[PHRASE] = [SourceTable].[name]  
 where [SourceTable].[Bad_Count] <> [fix].[count]

Nicht sicher, ob 2005 es unterstützt, aber Volltextindex und Verwendung enthält