Wyszukiwanie danych ciągu w celu znalezienia dowolnego dopasowania podciągu może być kosztowną operacją w programie SQL Server. Zapytania w postaci Column LIKE '%match%' nie może korzystać z możliwości wyszukiwania indeksu b-drzewa, więc procesor zapytań musi zastosować predykat do każdego wiersza indywidualnie. Ponadto każdy test musi poprawnie stosować pełny zestaw skomplikowanych reguł sortowania. Łącząc wszystkie te czynniki, nie jest niespodzianką, że tego typu wyszukiwania mogą być czasochłonne i wymagające dużej ilości zasobów.
Wyszukiwanie pełnotekstowe to potężne narzędzie do dopasowywania językowego, a nowsze statystyczne wyszukiwanie semantyczne doskonale nadaje się do znajdowania dokumentów o podobnym znaczeniu. Ale czasami naprawdę wystarczy znaleźć ciągi, które zawierają określony podciąg – podciąg, który może nawet nie być słowem, w dowolnym języku.
Jeśli wyszukiwane dane nie są duże lub wymagania dotyczące czasu odpowiedzi nie są krytyczne, użyj LIKE '%match%' równie dobrze może być odpowiednim rozwiązaniem. Ale w dziwnej sytuacji, gdy potrzeba superszybkiego wyszukiwania przewyższa wszystkie inne względy (w tym przestrzeń dyskową), możesz rozważyć niestandardowe rozwiązanie przy użyciu n-gramów. Konkretną odmianą omawianą w tym artykule jest trzyznakowy trygram.
Wyszukiwanie symboli wieloznacznych za pomocą trygramów
Podstawowa idea wyszukiwania trygramów jest dość prosta:
- Utrzymuj trzyznakowe podciągi (trygramy) danych docelowych.
- Podziel wyszukiwane hasła na trygramy.
- Dopasuj trygramy wyszukiwania do zapisanych trygramów (wyszukiwanie równości)
- Przetnij zakwalifikowane wiersze, aby znaleźć ciągi pasujące do wszystkich trygramów
- Zastosuj oryginalny filtr wyszukiwania do znacznie ograniczonego skrzyżowania
Przeanalizujemy przykład, aby zobaczyć dokładnie, jak to wszystko działa i jakie są kompromisy.
Przykładowa tabela i dane
Poniższy skrypt tworzy przykładową tabelę i wypełnia ją milionem wierszy danych łańcuchowych. Każdy ciąg ma długość 20 znaków, przy czym pierwsze 10 znaków to cyfry. Pozostałe 10 znaków to mieszanka cyfr i liter od A do F, wygenerowana za pomocą NEWID() . Nie ma nic strasznie specjalnego w tych przykładowych danych; technika trygramów jest dość ogólna.
-- 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); Zajmuje to około 3 sekundy do tworzenia i wypełniania danych na moim skromnym laptopie. Dane są pseudolosowe, ale jako wskazówka będzie wyglądać mniej więcej tak:
Próbka danych
Generowanie trygramów
Poniższa funkcja wbudowana generuje różne trygramy alfanumeryczne z podanego ciągu wejściowego:
--- 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]%'; Jako przykład jego użycia, następujące wywołanie:
SELECT
GT.trigram
FROM dbo.GenerateTrigrams('SQLperformance.com') AS GT; Tworzy następujące trygramy:
Trygramy SQLperformance.com
W tym przypadku plan wykonania jest dość bezpośrednim tłumaczeniem T-SQL:
- Generowanie wierszy (łączenie krzyżowe stałych skanów)
- Numerowanie wierszy (projekt segmentów i sekwencji)
- Ograniczanie potrzebnych liczb na podstawie długości ciągu (góra)
- Usuń trygramy ze znakami niealfanumerycznymi (filtr)
- Usuń duplikaty (sortowanie odrębne)
Plan generowania trygramów
Ładowanie trygramów
Następnym krokiem jest utrwalenie trygramów dla przykładowych danych. Trygramy będą przechowywane w nowej tabeli, wypełnionej za pomocą utworzonej właśnie funkcji wbudowanej:
-- 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; Zajmuje to około 20 sekund do wykonania na moim laptopie SQL Server 2016. Ten konkretny przebieg dał 17 937 972 wiersze trygramów dla 1 miliona wierszy 20-znakowych danych testowych. Plan wykonania zasadniczo pokazuje plan funkcji, który jest oceniany dla każdego wiersza tabeli Przykład:
Wypełnianie tabeli trygramów
Ponieważ ten test został przeprowadzony na SQL Server 2016 (ładowanie tabeli sterty, na poziomie zgodności bazy danych 130, z TABLOCK wskazówka), plan korzysta z równoległego wstawiania. Wiersze są rozdzielane między wątki przez równoległe skanowanie tabeli Przykład i pozostają w tym samym wątku później (bez wymiany na partycje).
Operator Sort może wyglądać nieco imponująco, ale liczby pokazują całkowitą liczbę posortowanych wierszy we wszystkich iteracjach sprzężenia w pętli zagnieżdżonej. W rzeczywistości istnieje milion oddzielnych rodzajów, każdy po 18 rzędów. Przy stopniu równoległości równym czterem (w moim przypadku dwa rdzenie hiperwątkowe) w dowolnym momencie występują maksymalnie cztery małe sortowania, a każda instancja sortowania może ponownie wykorzystać pamięć. To wyjaśnia, dlaczego maksymalne wykorzystanie pamięci w tym planie wykonania wynosi zaledwie 136 KB (chociaż przyznano 2152 KB).
Tabela trygramów zawiera jeden wiersz na każdy odrębny trygram w każdym wierszu tabeliźródłowej (identyfikowany przez id ):
Przykład tabeli trygramów
Teraz tworzymy klastrowany indeks b-drzewa do obsługi wyszukiwania dopasowań trygramów:
-- Trigram search index
CREATE UNIQUE CLUSTERED INDEX
[CUQ dbo.ExampleTrigrams (trigram, id)]
ON dbo.ExampleTrigrams (trigram, id)
WITH (DATA_COMPRESSION = ROW); Zajmuje to około 45 sekund , chociaż częściowo wynika to z rozsypywania się (moja instancja jest ograniczona do 4 GB pamięci). Instancja z większą dostępną pamięcią mogłaby prawdopodobnie ukończyć budowanie indeksu równoległego z minimalnym logowaniem znacznie szybciej.
Spis planu budowy
Zauważ, że indeks jest określony jako unikalny (przy użyciu obu kolumn w kluczu). Mogliśmy stworzyć nieunikalny indeks klastrowy na samym trygramie, ale SQL Server i tak dodałby 4-bajtowe ujednolicacze do prawie wszystkich wierszy. Gdy weźmiemy pod uwagę, że uniquifiers są przechowywane w części wiersza o zmiennej długości (z powiązanym obciążeniem), bardziej sensowne jest dołączenie id w kluczu i skończ z tym.
Kompresja wierszy jest określona, ponieważ zmniejsza rozmiar tabeli trygramów z 277 MB do 190 MB (dla porównania przykładowa tabela ma 32 MB). Jeśli nie używasz przynajmniej SQL Server 2016 SP1 (gdzie kompresja danych jest dostępna dla wszystkich edycji), możesz w razie potrzeby pominąć klauzulę kompresji.
Jako ostateczną optymalizację utworzymy również zindeksowany widok tabeli trygramów, aby szybko i łatwo znaleźć, które trygramy są najczęściej i najmniej powszechne w danych. Ten krok można pominąć, ale jest on zalecany ze względu na wydajność.
-- 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); 
Zindeksowany widok planu budynku
To zajmuje tylko kilka sekund. Rozmiar zmaterializowanego widoku jest niewielki, zaledwie 104 KB .
Wyszukiwanie trygramów
Podany ciąg wyszukiwania (np. '%find%this%' ), nasze podejście będzie polegać na:
- Wygeneruj pełny zestaw trygramów dla wyszukiwanego ciągu
- Użyj widoku indeksowanego, aby znaleźć trzy najbardziej selektywne trygramy
- Znajdź identyfikatory pasujące do wszystkich dostępnych trygramów
- Pobierz ciągi według identyfikatora
- Zastosuj pełny filtr do wierszy zakwalifikowanych do trygramu
Znajdowanie selektywnych trygramów
Pierwsze dwa kroki są dość proste. Mamy już funkcję do generowania trygramów dla dowolnego ciągu. Znalezienie najbardziej selektywnego z tych trygramów można osiągnąć, dołączając do zindeksowanego widoku. Poniższy kod otacza implementację naszej przykładowej tabeli w innej funkcji wbudowanej. Obraca trzy najbardziej selektywne trygramy w jednym rzędzie w celu ułatwienia późniejszego użycia:
-- 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; Jako przykład:
SELECT
EGBT.trigram1,
EGBT.trigram2,
EGBT.trigram3
FROM dbo.Example_GetBestTrigrams('%1234%5678%') AS EGBT; zwraca (dla moich przykładowych danych):
Wybrane trygramy
Plan wykonania to:
Plan wykonania GetBestTrigrams
Jest to znany wcześniej plan generowania trygramów, po którym następuje przeglądanie indeksowanego widoku dla każdego trygramu, sortowanie według liczby dopasowań, numerowanie wierszy (Projekt sekwencyjny), ograniczanie zestawu do trzech wierszy (Góra), a następnie obracanie wynik (Stream Aggregate).
Znajdowanie identyfikatorów pasujących do wszystkich trygramów
Następnym krokiem jest znalezienie identyfikatorów wierszy tabeli Przykład, które pasują do wszystkich trygramów innych niż null pobranych w poprzednim etapie. Zmarszczka polega na tym, że możemy mieć dostępne zero, jeden, dwa lub trzy trygramy. Poniższa implementacja otacza niezbędną logikę w funkcji wieloinstrukcji, zwracając kwalifikujące się identyfikatory w zmiennej tabeli:
-- 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; Szacowany plan wykonania dla tej funkcji przedstawia strategię:
Plan Trigram Match IDs
Jeśli dostępny jest jeden trygram, wykonywane jest pojedyncze wyszukiwanie w tablicy trygramów. W przeciwnym razie wykonywane są dwa lub trzy wyszukiwania i przecięcie identyfikatorów znalezione za pomocą wydajnego łączenia jeden-do-wielu. W tym planie nie ma operatorów zajmujących pamięć, więc nie ma szans na mieszanie lub sortowanie.
Kontynuując przykładowe wyszukiwanie, możemy znaleźć id pasujące do dostępnych trygramów, stosując nową funkcję:
SELECT EGTMID.id
FROM dbo.Example_GetBestTrigrams('%1234%5678%') AS EGBT
CROSS APPLY dbo.Example_GetTrigramMatchIDs
(EGBT.trigram1, EGBT.trigram2, EGBT.trigram3) AS EGTMID; Zwraca to zestaw podobny do następującego:
Pasujące identyfikatory
Rzeczywisty plan (po wykonaniu) nowej funkcji pokazuje kształt planu z użyciem trzech trygramów wejściowych:
Rzeczywisty plan dopasowania identyfikatora
To dość dobrze pokazuje moc dopasowania trygramów. Chociaż każdy z trzech trygramów identyfikuje około 11 000 wierszy w tabeli Przykład, pierwsze przecięcie zmniejsza ten zestaw do 1004 wierszy, a drugie przecięcie zmniejsza go do tylko 7 .
Pełna implementacja wyszukiwania trygramów
Teraz, gdy mamy identyfikatory pasujące do trygramów, możemy wyszukać pasujące wiersze w tabeli Przykład. Nadal musimy zastosować pierwotny warunek wyszukiwania jako ostatnią kontrolę, ponieważ trygramy mogą generować fałszywie pozytywne (ale nie fałszywie negatywne). Ostatnią kwestią do rozwiązania jest to, że poprzednie etapy mogły nie znaleźć żadnych trygramów. Może to być na przykład spowodowane tym, że wyszukiwany ciąg zawiera zbyt mało informacji. Ciąg wyszukiwania '%FF%' nie można użyć wyszukiwania trygramów, ponieważ dwa znaki nie wystarczą do wygenerowania nawet jednego trygramu. Aby sprawnie obsłużyć ten scenariusz, nasze wyszukiwanie wykryje ten stan i wróci do wyszukiwania bez trygramów.
Następująca końcowa funkcja inline implementuje wymaganą 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;
Kluczową cechą jest zewnętrzne odniesienie do GBT.trigram1 po obu stronach UNION ALL . Przekładają się one na filtry z wyrażeniami początkowymi w planie wykonania. Filtr startowy wykonuje swoje poddrzewo tylko wtedy, gdy jego warunek ma wartość prawda. Efekt netto jest taki, że tylko jedna część unii zostanie wykonana, w zależności od tego, czy znaleźliśmy trygram, czy nie. Odpowiednia część planu wykonania to:
Efekt filtra uruchamiania
Albo Example_GetTrigramMatchIDs zostanie wykonana funkcja (a wyniki zostaną wyszukane w przykładzie przy użyciu wyszukiwania według identyfikatora) lub skanowanie indeksu klastrowego przykładu z resztą LIKE predykat zostanie uruchomiony, ale nie jedno i drugie.
Wydajność
Poniższy kod testuje wydajność wyszukiwania trygramów względem równoważnego 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());
Oba generują te same wiersze wyników, ale LIKE zapytanie działa przez 2100ms , podczas gdy wyszukiwanie trygramów trwa 15 ms .
Możliwa jest jeszcze lepsza wydajność. Ogólnie rzecz biorąc, wydajność poprawia się, gdy trygramy stają się bardziej selektywne i mniej liczne (poniżej maksymalnej liczby trzech w tej implementacji). Na przykład:
SET STATISTICS XML OFF
DECLARE @S datetime2 = SYSUTCDATETIME();
SELECT ETS.string
FROM dbo.Example_TrigramSearch('%BEEF%') AS ETS;
SELECT ElapsedMS = DATEDIFF(MILLISECOND, @S, SYSUTCDATETIME());
To wyszukiwanie zwróciło 111 wierszy do siatki SSMS w 4 ms . LIKE odpowiednik trwał 1950ms .
Utrzymanie trygramów
Jeśli tabela docelowa jest statyczna, nie ma oczywiście problemu z synchronizacją tabeli podstawowej i powiązanej tabeli trygramów. Podobnie, jeśli wyniki wyszukiwania nie muszą być zawsze w pełni aktualne, zaplanowane odświeżanie tabeli trygramów może działać dobrze.
W przeciwnym razie możemy użyć dość prostych wyzwalaczy, aby zsynchronizować dane wyszukiwania trygramu z bazowymi ciągami. Ogólną ideą jest generowanie trygramów dla usuniętych i wstawionych wierszy, a następnie odpowiednio dodawanie lub usuwanie ich w tabeli trygramów. Poniższe wyzwalacze wstawiania, aktualizowania i usuwania pokazują ten pomysł w praktyce:
-- 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;
Wyzwalacze są dość wydajne i będą obsługiwać zarówno zmiany jedno-, jak i wielowierszowe (w tym wiele akcji dostępnych podczas korzystania z MERGE oświadczenie). Zindeksowany widok tabeli trygramów będzie automatycznie obsługiwany przez SQL Server bez konieczności pisania kodu wyzwalacza.
Operacja wyzwalania
Jako przykład uruchom instrukcję, aby usunąć dowolny wiersz z tabeli Przykład:
-- Single row delete DELETE TOP (1) dbo.Example;
Plan wykonania po wykonaniu (rzeczywisty) zawiera wpis dla wyzwalacza po usunięciu:
Usuń plan wykonania wyzwalacza
Żółta sekcja planu odczytuje wiersze z usuniętych pesudo-table, generuje trygramy dla każdego usuniętego przykładowego ciągu (używając znanego planu podświetlonego na zielono), a następnie lokalizuje i usuwa powiązane wpisy tablicy trygramów. Ostatnia sekcja planu, pokazana na czerwono, jest automatycznie dodawana przez SQL Server, aby zapewnić aktualność zindeksowanego widoku.
Plan wyzwalacza wstawiania jest bardzo podobny. Aktualizacje są obsługiwane przez wykonanie usunięcia, a następnie wstawienia. Uruchom następujący skrypt, aby zobaczyć te plany i potwierdzić, że nowe i zaktualizowane wiersze można zlokalizować za pomocą funkcji wyszukiwania trygramów:
-- 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; Przykład scalania
Następny skrypt pokazuje MERGE instrukcja używana do jednoczesnego wstawiania, usuwania i aktualizowania tabeli Przykład:
-- 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; Wynik pokaże coś takiego:
Wyjście akcji
Ostateczne przemyślenia
Być może istnieje pewien zakres, aby przyspieszyć duże operacje usuwania i aktualizacji poprzez bezpośrednie odwoływanie się do identyfikatorów zamiast generowania trygramów. Nie jest to tutaj zaimplementowane, ponieważ wymagałoby to nowego indeksu nieklastrowego w tabeli trygramów, podwajając zajętą (już znaczącą) przestrzeń dyskową. Tabela trygramów zawiera jedną liczbę całkowitą i char(3) na rząd; indeks nieklastrowany w kolumnie liczb całkowitych zyskałby char(3) kolumna na wszystkich poziomach (dzięki uprzejmości indeksu klastrowego i konieczności, aby klucze indeksu były unikalne na każdym poziomie). Należy również wziąć pod uwagę miejsce w pamięci, ponieważ wyszukiwanie trygramów działa najlepiej, gdy wszystkie odczyty pochodzą z pamięci podręcznej.
Dodatkowy indeks uczyniłby kaskadową integralność referencyjną opcją, ale często jest to więcej kłopotów, niż jest to warte.
Wyszukiwanie trygramów nie jest panaceum. Dodatkowe wymagania dotyczące pamięci masowej, złożoność implementacji i wpływ na wydajność aktualizacji mają na to duży wpływ. Technika ta jest również bezużyteczna w przypadku wyszukiwań, które nie generują żadnych trygramów (minimum 3 znaki). Chociaż pokazana tutaj podstawowa implementacja może obsługiwać wiele typów wyszukiwania (zaczyna się, zawiera, kończy się wieloma symbolami wieloznacznymi), nie obejmuje ona wszystkich możliwych wyrażeń wyszukiwania, które mogą działać z LIKE . Działa dobrze dla ciągów wyszukiwania, które generują trygramy typu AND; potrzeba więcej pracy, aby obsłużyć ciągi wyszukiwania, które wymagają obsługi typu OR, lub bardziej zaawansowanych opcji, takich jak wyrażenia regularne.
Wszystko to powiedziawszy, jeśli Twoja aplikacja naprawdę musi mieć szybkie wyszukiwanie ciągów znaków wieloznacznych, n-gramy są czymś, co należy poważnie rozważyć.
Powiązane treści:Jeden ze sposobów na uzyskanie indeksu wyszukiwania wiodącego %wildcard autorstwa Aarona Bertranda.
