Chociaż zgadzam się z innymi komentatorami, że jest to problem kosztowny obliczeniowo, myślę, że jest wiele miejsca na ulepszenia poprzez ulepszenie używanego SQL. Aby to zilustrować, tworzę fałszywy zestaw danych z nazwami 15MM i zwrotami 3K, zastosowałem stare podejście i uruchomiłem nowe podejście.
Pełny skrypt do wygenerowania fałszywego zestawu danych i wypróbowania nowego podejścia
TL; DR
Na moim komputerze i tym fałszywym zestawie danych uruchomienie oryginalnego podejścia zajmuje około 4 godzin . Proponowane nowe podejście zajmuje około 10 minut , co stanowi znaczną poprawę. Oto krótkie podsumowanie proponowanego podejścia:
- Dla każdej nazwy wygeneruj podciąg, zaczynając od każdego przesunięcia znaku (i zakończony długością najdłuższego niepoprawnego wyrażenia, jako optymalizacja)
- Utwórz indeks klastrowy na tych podciągach
- Dla każdego złego wyrażenia wykonaj wyszukiwanie w tych podciągach, aby zidentyfikować dowolne dopasowania
- Dla każdego oryginalnego łańcucha oblicz liczbę różnych niepoprawnych fraz pasujących do jednego lub więcej podciągów tego łańcucha
Oryginalne podejście: analiza algorytmiczna
Z planu pierwotnego UPDATEstwierdzenia wynika, że ilość pracy jest liniowo proporcjonalna zarówno do liczby nazw (15 MM), jak i do liczby fraz (3K). Jeśli więc pomnożymy zarówno liczbę nazwisk, jak i wyrażeń przez 10, całkowity czas działania będzie ~ 100 razy wolniejszy.
Zapytanie jest również proporcjonalne do długości name; choć jest to nieco ukryte w planie zapytań, pojawia się w „liczbie wykonań” wyszukiwania w buforze tabeli. W obecnym planie widzimy, że dzieje się to nie tylko raz na name, ale faktycznie raz na znak przesunięcia w obrębie name. Tak więc podejście to O ( # names* # phrases* name length) w złożoności w czasie wykonywania.
Nowe podejście: kod
Ten kod jest również dostępny w pełnej wersji pastebin, ale skopiowałem go tutaj dla wygody. Pastebin ma również pełną definicję procedury, która zawiera zmienne @minIdi @maxId, które widzisz poniżej, aby zdefiniować granice bieżącej partii.
-- 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
Nowe podejście: plany zapytań
Najpierw generujemy podciąg, zaczynając od każdego przesunięcia znaku
Następnie utwórz indeks klastrowy na tych podciągach
Teraz dla każdego złego wyrażenia szukamy tych podciągów, aby zidentyfikować dowolne dopasowania. Następnie obliczamy liczbę różnych złych fraz, które pasują do jednego lub więcej podciągów tego ciągu. To naprawdę kluczowy krok; z powodu sposobu, w jaki zaindeksowaliśmy podciągi, nie musimy już sprawdzać pełnego iloczynu złych fraz i nazw. Ten krok, który dokonuje rzeczywistego obliczenia, stanowi jedynie około 10% rzeczywistego czasu wykonywania (reszta to wstępne przetwarzanie podciągów).
Na koniec wykonaj rzeczywistą instrukcję aktualizacji, używając a, LEFT OUTER JOINaby przypisać liczbę 0 do dowolnych nazw, dla których nie znaleźliśmy złych fraz.
Nowe podejście: analiza algorytmiczna
Nowe podejście można podzielić na dwie fazy, wstępne przetwarzanie i dopasowanie. Zdefiniujmy następujące zmienne:
N = liczba nazwiskB = liczba złych frazL = średnia długość imienia, w znakach
Faza wstępnego przetwarzania ma O(N*L * LOG(N*L))na celu utworzenie N*Lpodciągów, a następnie ich posortowanie.
Rzeczywiste dopasowanie ma O(B * LOG(N*L))na celu wyszukanie podłańcuchów dla każdej złej frazy.
W ten sposób stworzyliśmy algorytm, który nie skaluje się liniowo z liczbą złych fraz, kluczowym odblokowaniem wydajności, gdy skalujemy do 3K fraz i więcej. Innymi słowy, oryginalna implementacja zajmuje około 10 razy tyle, ile przechodzimy od 300 złych fraz do 3 tys. Złych fraz. Podobnie zajęłoby to kolejne 10 razy więcej, gdybyśmy przeszli z 3 000 złych fraz do 30 000. Nowa implementacja będzie jednak skalować się sublinearnie i w rzeczywistości zajmuje mniej niż dwukrotność czasu mierzonego dla 3 000 niepoprawnych fraz przy skalowaniu do 30 000 niepoprawnych fraz.
Założenia / zastrzeżenia
- Dzielę całą pracę na skromne partie. Jest to prawdopodobnie dobry pomysł
SORTna każde z tych podejść, ale jest to szczególnie ważne w przypadku nowego podejścia, aby podciągi były niezależne dla każdej partii i łatwo mieściły się w pamięci. W razie potrzeby możesz manipulować rozmiarem partii, ale nie byłoby rozsądnie wypróbować wszystkich wierszy 15 MM w jednej partii.
- Korzystam z SQL 2014, a nie SQL 2005, ponieważ nie mam dostępu do maszyny SQL 2005. Starałem się nie używać żadnej składni, która nie jest dostępna w SQL 2005, ale nadal mogę czerpać korzyści z funkcji leniwego zapisu tempdb w SQL 2012+ i równoległej funkcji SELECT INTO w SQL 2014.
- Długości zarówno imion, jak i fraz są dość ważne w nowym podejściu. Zakładam, że złe frazy są zazwyczaj dość krótkie, ponieważ mogą one pasować do rzeczywistych przypadków użycia. Nazwy są nieco dłuższe niż złe frazy, ale zakłada się, że nie są to tysiące znaków. Myślę, że jest to uczciwe założenie, a dłuższe ciągi nazw spowolniłyby również twoje oryginalne podejście.
- Część ulepszeń (ale nigdzie w pobliżu) wynika z faktu, że nowe podejście może efektywniej wykorzystywać równoległość niż stare (działające jednowątkowo). Jestem na czterordzeniowym laptopie, więc miło jest mieć podejście, które może wykorzystać te rdzenie.
Powiązany post na blogu
Aaron Bertrand bada bardziej szczegółowo tego rodzaju rozwiązanie w swoim blogu Jeden ze sposobów na uzyskanie indeksu dla wiodącej% wieloznacznej .