Das Durchsuchen von Zeichenfolgendaten nach einer beliebigen Teilzeichenfolgenübereinstimmung kann in SQL Server ein kostspieliger Vorgang sein. Abfragen der Form Column LIKE '%match%' kann die Suchfähigkeiten eines B-Tree-Index nicht verwenden, daher muss der Abfrageprozessor das Prädikat auf jede Zeile einzeln anwenden. Darüber hinaus muss jeder Test den vollständigen Satz komplizierter Vergleichsregeln korrekt anwenden. Wenn man all diese Faktoren kombiniert, ist es nicht verwunderlich, dass diese Suchtypen ressourcenintensiv und langsam sein können.
Die Volltextsuche ist ein leistungsstarkes Tool für den sprachlichen Abgleich, und die neuere statistische semantische Suche eignet sich hervorragend zum Auffinden von Dokumenten mit ähnlichen Bedeutungen. Aber manchmal müssen Sie wirklich nur Zeichenfolgen finden, die eine bestimmte Teilzeichenfolge enthalten – eine Teilzeichenfolge, die in keiner Sprache möglicherweise nicht einmal ein Wort ist.
Wenn die durchsuchten Daten nicht groß sind oder die Anforderungen an die Antwortzeit nicht kritisch sind, verwenden Sie LIKE '%match%' könnte durchaus eine passende Lösung sein. Aber in den seltenen Fällen, in denen die Notwendigkeit einer superschnellen Suche alle anderen Überlegungen (einschließlich Speicherplatz) übertrifft, könnten Sie eine benutzerdefinierte Lösung mit N-Gramm in Betracht ziehen. Die spezifische Variante, die in diesem Artikel untersucht wird, ist ein dreistelliges Trigramm.
Platzhaltersuche mit Trigrammen
Die Grundidee einer Trigrammsuche ist ganz einfach:
- Dreistellige Teilzeichenfolgen (Trigramme) der Zieldaten beibehalten.
- Teilen Sie den/die Suchbegriff(e) in Trigramme auf.
- Suchtrigramme mit den gespeicherten Trigrammen abgleichen (Gleichheitssuche)
- Schneiden Sie die qualifizierten Zeilen, um Zeichenfolgen zu finden, die mit allen Trigrammen übereinstimmen
- Wenden Sie den ursprünglichen Suchfilter auf die stark reduzierte Kreuzung an
Wir werden ein Beispiel durcharbeiten, um genau zu sehen, wie das alles funktioniert und welche Kompromisse es gibt.
Beispieltabelle und Daten
Das folgende Skript erstellt eine Beispieltabelle und füllt sie mit einer Million Zeilen von Zeichenfolgendaten. Jede Zeichenfolge ist 20 Zeichen lang, wobei die ersten 10 Zeichen numerisch sind. Die restlichen 10 Zeichen sind eine Mischung aus Zahlen und Buchstaben von A bis F, generiert mit NEWID() . An diesen Beispieldaten ist nichts besonders Besonderes; Die Trigramm-Technik ist ziemlich allgemein.
-- The test table
CREATE TABLE dbo.Example
(
id integer IDENTITY NOT NULL,
string char(20) NOT NULL,
CONSTRAINT [PK dbo.Example (id)]
PRIMARY KEY CLUSTERED (id)
);
GO
-- 1 million rows
INSERT dbo.Example WITH (TABLOCKX)
(string)
SELECT TOP (1 * 1000 * 1000)
-- 10 numeric characters
REPLACE(STR(RAND(CHECKSUM(NEWID())) * 1e10, 10), SPACE(1), '0') +
-- plus 10 mixed numeric + [A-F] characters
RIGHT(NEWID(), 10)
FROM master.dbo.spt_values AS SV1
CROSS JOIN master.dbo.spt_values AS SV2
OPTION (MAXDOP 1); Es dauert ungefähr 3 Sekunden um die Daten auf meinem bescheidenen Laptop zu erstellen und zu füllen. Die Daten sind pseudozufällig, sehen aber ungefähr so aus:
Datenbeispiel
Trigramme generieren
Die folgende Inline-Funktion generiert unterschiedliche alphanumerische Trigramme aus einer gegebenen Eingabezeichenfolge:
--- Generate trigrams from a string
CREATE FUNCTION dbo.GenerateTrigrams (@string varchar(255))
RETURNS table
WITH SCHEMABINDING
AS RETURN
WITH
N16 AS
(
SELECT V.v
FROM
(
VALUES
(0),(0),(0),(0),(0),(0),(0),(0),
(0),(0),(0),(0),(0),(0),(0),(0)
) AS V (v)),
-- Numbers table (256)
Nums AS
(
SELECT n = ROW_NUMBER() OVER (ORDER BY A.v)
FROM N16 AS A
CROSS JOIN N16 AS B
),
Trigrams AS
(
-- Every 3-character substring
SELECT TOP (CASE WHEN LEN(@string) > 2 THEN LEN(@string) - 2 ELSE 0 END)
trigram = SUBSTRING(@string, N.n, 3)
FROM Nums AS N
ORDER BY N.n
)
-- Remove duplicates and ensure all three characters are alphanumeric
SELECT DISTINCT
T.trigram
FROM Trigrams AS T
WHERE
-- Binary collation comparison so ranges work as expected
T.trigram COLLATE Latin1_General_BIN2 NOT LIKE '%[^A-Z0-9a-z]%'; Als Beispiel für seine Verwendung der folgende Aufruf:
SELECT
GT.trigram
FROM dbo.GenerateTrigrams('SQLperformance.com') AS GT; Erzeugt die folgenden Trigramme:
SQLperformance.com-Trigramme
Der Ausführungsplan ist in diesem Fall eine ziemlich direkte Übersetzung des T-SQL:
- Zeilen generieren (Cross Join von Constant Scans)
- Zeilennummerierung (Segment- und Sequenzprojekt)
- Einschränkung der benötigten Anzahl basierend auf der Länge der Zeichenfolge (Top)
- Trigramme mit nicht alphanumerischen Zeichen entfernen (Filter)
- Duplikate entfernen (eindeutige Sortierung)
Planen Sie das Generieren von Trigrammen
Laden der Trigramme
Der nächste Schritt besteht darin, Trigramme für die Beispieldaten beizubehalten. Die Trigramme werden in einer neuen Tabelle gespeichert, die mit der gerade erstellten Inline-Funktion gefüllt wird:
-- Trigrams for Example table
CREATE TABLE dbo.ExampleTrigrams
(
id integer NOT NULL,
trigram char(3) NOT NULL
);
GO
-- Generate trigrams
INSERT dbo.ExampleTrigrams WITH (TABLOCKX)
(id, trigram)
SELECT
E.id,
GT.trigram
FROM dbo.Example AS E
CROSS APPLY dbo.GenerateTrigrams(E.string) AS GT; Das dauert etwa 20 Sekunden auf meiner SQL Server 2016-Laptop-Instanz auszuführen. Dieser spezielle Durchlauf produzierte 17.937.972 Zeilen von Trigrammen für die 1 Million Zeilen mit 20-Zeichen-Testdaten. Der Ausführungsplan zeigt im Wesentlichen den Funktionsplan, der für jede Zeile der Beispieltabelle ausgewertet wird:
Befüllen der Trigrammtabelle
Da dieser Test auf SQL Server 2016 durchgeführt wurde (Laden einer Heap-Tabelle, unter Datenbank-Kompatibilitätsgrad 130 und mit einem TABLOCK Hinweis), profitiert der Plan von der parallelen Einfügung. Die Zeilen werden durch den parallelen Scan der Beispieltabelle zwischen den Threads verteilt und verbleiben danach im selben Thread (keine Neupartitionierungsaustausche).
Der Sort-Operator sieht vielleicht etwas imposant aus, aber die Zahlen zeigen die Gesamtzahl der sortierten Zeilen über alle Iterationen des Nested-Loop-Join. Tatsächlich gibt es eine Million separate Sorten mit jeweils 18 Reihen. Bei einem Parallelitätsgrad von vier (in meinem Fall zwei Kerne mit Hyperthreading) laufen maximal vier winzige Sortiervorgänge gleichzeitig ab, und jede Sortierinstanz kann Speicher wiederverwenden. Dies erklärt, warum die maximale Speichernutzung dieses Ausführungsplans lediglich 136 KB beträgt (obwohl 2.152 KB gewährt wurden).
Die Trigrammtabelle enthält eine Zeile für jedes unterschiedliche Trigramm in jeder Quelltabellenzeile (identifiziert durch id ):
Trigramm-Tabellenbeispiel
Wir erstellen jetzt einen geclusterten B-Tree-Index, um die Suche nach Trigramm-Übereinstimmungen zu unterstützen:
-- Trigram search index
CREATE UNIQUE CLUSTERED INDEX
[CUQ dbo.ExampleTrigrams (trigram, id)]
ON dbo.ExampleTrigrams (trigram, id)
WITH (DATA_COMPRESSION = ROW); Dies dauert etwa 45 Sekunden , obwohl ein Teil davon auf die Art des Verschüttens zurückzuführen ist (meine Instanz ist auf 4 GB Speicher begrenzt). Eine Instanz mit mehr verfügbarem Arbeitsspeicher könnte diese minimal protokollierte parallele Indexerstellung wahrscheinlich etwas schneller abschließen.
Indexaufbauplan
Beachten Sie, dass der Index als eindeutig angegeben ist (unter Verwendung beider Spalten im Schlüssel). Wir hätten einen nicht eindeutigen gruppierten Index nur für das Trigramm erstellen können, aber SQL Server hätte sowieso fast allen Zeilen 4-Byte-Uniquifier hinzugefügt. Sobald wir berücksichtigen, dass Uniquifier im Teil der Zeile mit variabler Länge gespeichert werden (mit dem zugehörigen Overhead), ist es einfach sinnvoller, id einzufügen in den Schlüssel und fertig.
Die Zeilenkomprimierung wird angegeben, weil sie die Größe der Trigrammtabelle sinnvollerweise von 277 MB auf 190 MB reduziert (zum Vergleich, die Beispieltabelle ist 32 MB groß). Wenn Sie nicht mindestens SQL Server 2016 SP1 verwenden (wo die Datenkomprimierung für alle Editionen verfügbar wurde), können Sie die Komprimierungsklausel bei Bedarf weglassen.
Als letzte Optimierung werden wir auch eine indizierte Ansicht über die Trigrammtabelle erstellen, damit Sie schnell und einfach finden können, welche Trigramme in den Daten am häufigsten und am wenigsten verbreitet sind. Dieser Schritt kann weggelassen werden, wird aber aus Leistungsgründen empfohlen.
-- Selectivity of each trigram (performance optimization)
CREATE VIEW dbo.ExampleTrigramCounts
WITH SCHEMABINDING
AS
SELECT ET.trigram, cnt = COUNT_BIG(*)
FROM dbo.ExampleTrigrams AS ET
GROUP BY ET.trigram;
GO
-- Materialize the view
CREATE UNIQUE CLUSTERED INDEX
[CUQ dbo.ExampleTrigramCounts (trigram)]
ON dbo.ExampleTrigramCounts (trigram); 
Bauplan für indizierte Ansicht
Dies dauert nur ein paar Sekunden. Die Größe der materialisierten Ansicht ist winzig, nur 104 KB .
Trigrammsuche
Bei gegebenem Suchstring (z. B. '%find%this%' ), ist unser Ansatz:
- Generieren Sie den vollständigen Satz von Trigrammen für die Suchzeichenfolge
- Verwenden Sie die indizierte Ansicht, um die drei selektivsten Trigramme zu finden
- Finde die IDs, die allen verfügbaren Trigrammen entsprechen
- Strings nach ID abrufen
- Wenden Sie den vollständigen Filter auf die Trigramm-qualifizierten Zeilen an
Selektive Trigramme finden
Die ersten beiden Schritte sind ziemlich einfach. Wir haben bereits eine Funktion zum Generieren von Trigrammen für eine beliebige Zeichenfolge. Das Finden der selektivsten dieser Trigramme kann durch Verbinden mit der indizierten Ansicht erreicht werden. Der folgende Code umschließt die Implementierung für unsere Beispieltabelle in einer anderen Inline-Funktion. Es schwenkt die drei selektivsten Trigramme in einer einzigen Zeile, um die spätere Verwendung zu erleichtern:
-- Most selective trigrams for a search string
-- Always returns a row (NULLs if no trigrams found)
CREATE FUNCTION dbo.Example_GetBestTrigrams (@string varchar(255))
RETURNS table
WITH SCHEMABINDING AS
RETURN
SELECT
-- Pivot
trigram1 = MAX(CASE WHEN BT.rn = 1 THEN BT.trigram END),
trigram2 = MAX(CASE WHEN BT.rn = 2 THEN BT.trigram END),
trigram3 = MAX(CASE WHEN BT.rn = 3 THEN BT.trigram END)
FROM
(
-- Generate trigrams for the search string
-- and choose the most selective three
SELECT TOP (3)
rn = ROW_NUMBER() OVER (
ORDER BY ETC.cnt ASC),
GT.trigram
FROM dbo.GenerateTrigrams(@string) AS GT
JOIN dbo.ExampleTrigramCounts AS ETC
WITH (NOEXPAND)
ON ETC.trigram = GT.trigram
ORDER BY
ETC.cnt ASC
) AS BT; Als Beispiel:
SELECT
EGBT.trigram1,
EGBT.trigram2,
EGBT.trigram3
FROM dbo.Example_GetBestTrigrams('%1234%5678%') AS EGBT; gibt zurück (für meine Beispieldaten):
Ausgewählte Trigramme
Der Ausführungsplan ist:
GetBestTrigrams-Ausführungsplan
Dies ist der bekannte Trigramm-Erzeugungsplan von früher, gefolgt von einem Nachschlagen in der indizierten Ansicht für jedes Trigramm, Sortieren nach der Anzahl der Übereinstimmungen, Nummerieren der Zeilen (Sequence Project), Begrenzen des Satzes auf drei Zeilen (Top) und dann Pivotieren das Ergebnis (Stream Aggregate).
IDs finden, die mit allen Trigrammen übereinstimmen
Der nächste Schritt besteht darin, Beispieltabellen-Zeilen-IDs zu finden, die mit allen Nicht-Null-Trigrammen übereinstimmen, die in der vorherigen Phase abgerufen wurden. Der Haken hier ist, dass wir vielleicht null, eins, zwei oder drei Trigramme zur Verfügung haben. Die folgende Implementierung umschließt die erforderliche Logik in einer Funktion mit mehreren Anweisungen und gibt die qualifizierenden IDs in einer Tabellenvariablen zurück:
-- Returns Example ids matching all provided (non-null) trigrams
CREATE FUNCTION dbo.Example_GetTrigramMatchIDs
(
@Trigram1 char(3),
@Trigram2 char(3),
@Trigram3 char(3)
)
RETURNS @IDs table (id integer PRIMARY KEY)
WITH SCHEMABINDING AS
BEGIN
IF @Trigram1 IS NOT NULL
BEGIN
IF @Trigram2 IS NOT NULL
BEGIN
IF @Trigram3 IS NOT NULL
BEGIN
-- 3 trigrams available
INSERT @IDs (id)
SELECT ET1.id
FROM dbo.ExampleTrigrams AS ET1
WHERE ET1.trigram = @Trigram1
INTERSECT
SELECT ET2.id
FROM dbo.ExampleTrigrams AS ET2
WHERE ET2.trigram = @Trigram2
INTERSECT
SELECT ET3.id
FROM dbo.ExampleTrigrams AS ET3
WHERE ET3.trigram = @Trigram3
OPTION (MERGE JOIN);
END;
ELSE
BEGIN
-- 2 trigrams available
INSERT @IDs (id)
SELECT ET1.id
FROM dbo.ExampleTrigrams AS ET1
WHERE ET1.trigram = @Trigram1
INTERSECT
SELECT ET2.id
FROM dbo.ExampleTrigrams AS ET2
WHERE ET2.trigram = @Trigram2
OPTION (MERGE JOIN);
END;
END;
ELSE
BEGIN
-- 1 trigram available
INSERT @IDs (id)
SELECT ET1.id
FROM dbo.ExampleTrigrams AS ET1
WHERE ET1.trigram = @Trigram1;
END;
END;
RETURN;
END; Der geschätzte Ausführungsplan für diese Funktion zeigt die Strategie:
Trigram-Match-IDs-Plan
Wenn ein Trigramm verfügbar ist, wird eine einzelne Suche in der Trigrammtabelle durchgeführt. Andernfalls werden zwei oder drei Suchvorgänge durchgeführt und die Schnittmenge von IDs unter Verwendung einer effizienten Eins-zu-Viele-Zusammenführung(en) gefunden. Es gibt keine speicherintensiven Operatoren in diesem Plan, also keine Chance auf Hash- oder Sort-Spill.
Wenn wir die Beispielsuche fortsetzen, können wir IDs finden, die mit den verfügbaren Trigrammen übereinstimmen, indem wir die neue Funktion anwenden:
SELECT EGTMID.id
FROM dbo.Example_GetBestTrigrams('%1234%5678%') AS EGBT
CROSS APPLY dbo.Example_GetTrigramMatchIDs
(EGBT.trigram1, EGBT.trigram2, EGBT.trigram3) AS EGTMID; Dies gibt einen Satz wie den folgenden zurück:
Übereinstimmende IDs
Der tatsächliche Plan (nach der Ausführung) für die neue Funktion zeigt die Planform mit drei verwendeten Trigrammeingaben:
Tatsächlicher ID-Abgleichsplan
Dies zeigt die Leistungsfähigkeit des Trigram-Matching recht gut. Obwohl alle drei Trigramme jeweils etwa 11.000 Zeilen in der Beispieltabelle identifizieren, reduziert die erste Schnittmenge diese Menge auf 1.004 Zeilen und die zweite Schnittmenge auf nur 7 .
Vollständige Implementierung der Trigrammsuche
Nachdem wir nun die IDs haben, die mit den Trigrammen übereinstimmen, können wir die übereinstimmenden Zeilen in der Beispieltabelle nachschlagen. Wir müssen noch die ursprüngliche Suchbedingung als abschließende Prüfung anwenden, da Trigramme falsch positive Ergebnisse (aber keine falsch negativen) erzeugen können. Das letzte Problem, das angesprochen werden muss, ist, dass die vorherigen Phasen möglicherweise keine Trigramme gefunden haben. Dies kann beispielsweise daran liegen, dass der Suchstring zu wenig Informationen enthält. Eine Suchzeichenfolge von '%FF%' kann die Trigrammsuche nicht verwenden, da zwei Zeichen nicht ausreichen, um auch nur ein einzelnes Trigramm zu generieren. Um dieses Szenario angemessen zu handhaben, erkennt unsere Suche diese Bedingung und greift auf eine Nicht-Trigramm-Suche zurück.
Die folgende abschließende Inline-Funktion implementiert die erforderliche Logik:
-- Search implementation
CREATE FUNCTION dbo.Example_TrigramSearch
(
@Search varchar(255)
)
RETURNS table
WITH SCHEMABINDING
AS
RETURN
SELECT
Result.string
FROM dbo.Example_GetBestTrigrams(@Search) AS GBT
CROSS APPLY
(
-- Trigram search
SELECT
E.id,
E.string
FROM dbo.Example_GetTrigramMatchIDs
(GBT.trigram1, GBT.trigram2, GBT.trigram3) AS MID
JOIN dbo.Example AS E
ON E.id = MID.id
WHERE
-- At least one trigram found
GBT.trigram1 IS NOT NULL
AND E.string LIKE @Search
UNION ALL
-- Non-trigram search
SELECT
E.id,
E.string
FROM dbo.Example AS E
WHERE
-- No trigram found
GBT.trigram1 IS NULL
AND E.string LIKE @Search
) AS Result;
Das Schlüsselmerkmal ist der äußere Verweis auf GBT.trigram1 auf beiden Seiten von UNION ALL . Diese werden in Filter mit Startausdrücken im Ausführungsplan übersetzt. Ein Startfilter führt seinen Teilbaum nur aus, wenn seine Bedingung wahr ist. Der Nettoeffekt ist, dass nur ein Teil der Vereinigung ausgeführt wird, je nachdem, ob wir ein Trigramm gefunden haben oder nicht. Der relevante Teil des Ausführungsplans ist:
Startfiltereffekt
Entweder die Example_GetTrigramMatchIDs Funktion ausgeführt wird (und die Ergebnisse in Beispiel mit einer Suche nach ID gesucht werden), oder der Clustered Index Scan von Beispiel mit einem Rest LIKE Prädikat wird ausgeführt, aber nicht beides.
Leistung
Der folgende Code testet die Leistung der Trigrammsuche anhand des entsprechenden LIKE :
SET STATISTICS XML OFF
DECLARE @S datetime2 = SYSUTCDATETIME();
SELECT F2.string
FROM dbo.Example AS F2
WHERE
F2.string LIKE '%1234%5678%'
OPTION (MAXDOP 1);
SELECT ElapsedMS = DATEDIFF(MILLISECOND, @S, SYSUTCDATETIME());
GO
SET STATISTICS XML OFF
DECLARE @S datetime2 = SYSUTCDATETIME();
SELECT ETS.string
FROM dbo.Example_TrigramSearch('%1234%5678%') AS ETS;
SELECT ElapsedMS = DATEDIFF(MILLISECOND, @S, SYSUTCDATETIME());
Beide erzeugen die gleiche(n) Ergebniszeile(n), aber den LIKE Abfrage wird 2100 ms ausgeführt , während die Suche nach Trigrammen 15 ms dauert .
Eine noch bessere Leistung ist möglich. Im Allgemeinen verbessert sich die Leistung, wenn die Trigramme selektiver und weniger zahlreich werden (unter dem Maximum von drei in dieser Implementierung). Zum Beispiel:
SET STATISTICS XML OFF
DECLARE @S datetime2 = SYSUTCDATETIME();
SELECT ETS.string
FROM dbo.Example_TrigramSearch('%BEEF%') AS ETS;
SELECT ElapsedMS = DATEDIFF(MILLISECOND, @S, SYSUTCDATETIME());
Diese Suche lieferte in 4 ms 111 Zeilen an das SSMS-Raster zurück . Das LIKE Äquivalent lief für 1950ms .
Pflege der Trigramme
Wenn die Zieltabelle statisch ist, gibt es offensichtlich kein Problem, die Basistabelle und die zugehörige Trigrammtabelle synchron zu halten. Ebenso kann eine planmäßige Aktualisierung der Trigrammtabelle(n) gut funktionieren, wenn die Suchergebnisse nicht immer auf dem neuesten Stand sein müssen.
Andernfalls können wir einige ziemlich einfache Trigger verwenden, um die Trigramm-Suchdaten mit den zugrunde liegenden Zeichenfolgen zu synchronisieren. Die allgemeine Idee besteht darin, Trigramme für gelöschte und eingefügte Zeilen zu generieren und sie dann entsprechend in der Trigrammtabelle hinzuzufügen oder zu löschen. Die folgenden Trigger zum Einfügen, Aktualisieren und Löschen zeigen diese Idee in der Praxis:
-- Maintain trigrams after Example inserts
CREATE TRIGGER MaintainTrigrams_AI
ON dbo.Example
AFTER INSERT
AS
BEGIN
IF @@ROWCOUNT = 0 RETURN;
IF TRIGGER_NESTLEVEL(@@PROCID, 'AFTER', 'DML') > 1 RETURN;
SET NOCOUNT ON;
SET ROWCOUNT 0;
-- Insert related trigrams
INSERT dbo.ExampleTrigrams
(id, trigram)
SELECT
INS.id, GT.trigram
FROM Inserted AS INS
CROSS APPLY dbo.GenerateTrigrams(INS.string) AS GT;
END; -- Maintain trigrams after Example deletes
CREATE TRIGGER MaintainTrigrams_AD
ON dbo.Example
AFTER DELETE
AS
BEGIN
IF @@ROWCOUNT = 0 RETURN;
IF TRIGGER_NESTLEVEL(@@PROCID, 'AFTER', 'DML') > 1 RETURN;
SET NOCOUNT ON;
SET ROWCOUNT 0;
-- Deleted related trigrams
DELETE ET
WITH (SERIALIZABLE)
FROM Deleted AS DEL
CROSS APPLY dbo.GenerateTrigrams(DEL.string) AS GT
JOIN dbo.ExampleTrigrams AS ET
ON ET.trigram = GT.trigram
AND ET.id = DEL.id;
END; -- Maintain trigrams after Example updates
CREATE TRIGGER MaintainTrigrams_AU
ON dbo.Example
AFTER UPDATE
AS
BEGIN
IF @@ROWCOUNT = 0 RETURN;
IF TRIGGER_NESTLEVEL(@@PROCID, 'AFTER', 'DML') > 1 RETURN;
SET NOCOUNT ON;
SET ROWCOUNT 0;
-- Deleted related trigrams
DELETE ET
WITH (SERIALIZABLE)
FROM Deleted AS DEL
CROSS APPLY dbo.GenerateTrigrams(DEL.string) AS GT
JOIN dbo.ExampleTrigrams AS ET
ON ET.trigram = GT.trigram
AND ET.id = DEL.id;
-- Insert related trigrams
INSERT dbo.ExampleTrigrams
(id, trigram)
SELECT
INS.id, GT.trigram
FROM Inserted AS INS
CROSS APPLY dbo.GenerateTrigrams(INS.string) AS GT;
END;
Die Trigger sind ziemlich effizient und verarbeiten sowohl ein- als auch mehrzeilige Änderungen (einschließlich der mehreren verfügbaren Aktionen, wenn ein MERGE verwendet wird Erklärung). Die indizierte Ansicht über die Trigrams-Tabelle wird automatisch von SQL Server verwaltet, ohne dass wir Triggercode schreiben müssen.
Vorgang auslösen
Führen Sie als Beispiel eine Anweisung aus, um eine beliebige Zeile aus der Beispieltabelle zu löschen:
-- Single row delete DELETE TOP (1) dbo.Example;
Der (tatsächliche) Ausführungsplan nach der Ausführung enthält einen Eintrag für den Auslöser nach dem Löschen:
Trigger-Ausführungsplan löschen
Der gelbe Abschnitt des Plans liest Zeilen von gelöscht pesudo-table, generiert Trigramme für jede gelöschte Beispielzeichenfolge (unter Verwendung des vertrauten, grün hervorgehobenen Plans), sucht und löscht dann die zugehörigen Einträge in der Trigrammtabelle. Der letzte Abschnitt des Plans, rot dargestellt, wird automatisch von SQL Server hinzugefügt, um die indizierte Ansicht auf dem neuesten Stand zu halten.
Der Plan für den Insert-Trigger ist sehr ähnlich. Aktualisierungen werden durch Ausführen eines Löschens gefolgt von einem Einfügen behandelt. Führen Sie das folgende Skript aus, um diese Pläne anzuzeigen und zu bestätigen, dass neue und aktualisierte Zeilen mithilfe der Trigramm-Suchfunktion gefunden werden können:
-- Single row insert
INSERT dbo.Example (string)
VALUES ('SQLPerformance.com');
-- Find the new row
SELECT ETS.string
FROM dbo.Example_TrigramSearch('%perf%') AS ETS;
-- Single row update
UPDATE TOP (1) dbo.Example
SET string = '12345678901234567890';
-- Multi-row insert
INSERT dbo.Example WITH (TABLOCKX)
(string)
SELECT TOP (1000)
REPLACE(STR(RAND(CHECKSUM(NEWID())) * 1e10, 10), SPACE(1), '0') +
RIGHT(NEWID(), 10)
FROM master.dbo.spt_values AS SV1;
-- Multi-row update
UPDATE TOP (1000) dbo.Example
SET string = '12345678901234567890';
-- Search for the updated rows
SELECT ETS.string
FROM dbo.Example_TrigramSearch('12345678901234567890') AS ETS; Zusammenführungsbeispiel
Das nächste Skript zeigt ein MERGE -Anweisung zum gleichzeitigen Einfügen, Löschen und Aktualisieren der Beispieltabelle verwendet wird:
-- MERGE demo
DECLARE @MergeData table
(
id integer UNIQUE CLUSTERED NULL,
operation char(3) NOT NULL,
string char(20) NULL
);
INSERT @MergeData
(id, operation, string)
VALUES
(NULL, 'INS', '11223344556677889900'), -- Insert
(1001, 'DEL', NULL), -- Delete
(2002, 'UPD', '00000000000000000000'); -- Update
DECLARE @Actions table
(
action$ nvarchar(10) NOT NULL,
old_id integer NULL,
old_string char(20) NULL,
new_id integer NULL,
new_string char(20) NULL
);
MERGE dbo.Example AS E
USING @MergeData AS MD
ON MD.id = E.id
WHEN MATCHED AND MD.operation = 'DEL'
THEN DELETE
WHEN MATCHED AND MD.operation = 'UPD'
THEN UPDATE SET E.string = MD.string
WHEN NOT MATCHED AND MD.operation = 'INS'
THEN INSERT (string) VALUES (MD.string)
OUTPUT $action, Deleted.id, Deleted.string, Inserted.id, Inserted.string
INTO @Actions (action$, old_id, old_string, new_id, new_string);
SELECT * FROM @Actions AS A; Die Ausgabe zeigt etwas wie:
Aktionsausgabe
Abschließende Gedanken
Es gibt möglicherweise einen gewissen Spielraum, um große Lösch- und Aktualisierungsvorgänge zu beschleunigen, indem direkt auf IDs verwiesen wird, anstatt Trigramme zu generieren. Dies wird hier nicht implementiert, da dies einen neuen Nonclustered-Index für die Trigrams-Tabelle erfordern würde, wodurch der (bereits beträchtliche) verwendete Speicherplatz verdoppelt würde. Die Trigrammtabelle enthält eine einzelne Ganzzahl und ein char(3) pro Zeile; ein Nonclustered-Index für die Integer-Spalte würde den char(3) erhalten -Spalte auf allen Ebenen (mit freundlicher Genehmigung des gruppierten Indexes und der Notwendigkeit, dass Indexschlüssel auf jeder Ebene eindeutig sind). Es ist auch Speicherplatz zu berücksichtigen, da Trigrammsuchen am besten funktionieren, wenn alle Lesevorgänge aus dem Cache stammen.
Der zusätzliche Index würde die kaskadierende referentielle Integrität zu einer Option machen, aber das ist oft mehr Mühe als es wert ist.
Die Trigrammsuche ist kein Allheilmittel. Die zusätzlichen Speicheranforderungen, die Implementierungskomplexität und die Auswirkungen auf die Aktualisierungsleistung wiegen stark dagegen. Die Technik ist auch nutzlos für Suchen, die keine Trigramme (mindestens 3 Zeichen) erzeugen. Obwohl die hier gezeigte grundlegende Implementierung viele Suchtypen handhaben kann (beginnt mit, enthält, endet mit, mehrere Platzhalter), deckt sie nicht jeden möglichen Suchausdruck ab, der mit LIKE funktionieren kann . Es funktioniert gut für Suchstrings, die Trigramme vom Typ AND erzeugen; Es ist mehr Arbeit erforderlich, um Suchzeichenfolgen zu verarbeiten, die eine Verarbeitung vom Typ OR erfordern, oder erweiterte Optionen wie reguläre Ausdrücke.
All das gesagt, wenn Ihre Bewerbung wirklich muss schnelle Platzhalter-String-Suchen haben, N-Gramme sollten ernsthaft in Betracht gezogen werden.
Zugehöriger Inhalt:Eine Möglichkeit, eine Indexsuche nach einem führenden %Wildcard von Aaron Bertrand zu erhalten.
