Powolna aktualizacja na dużym stole z podzapytaniem

Dzięki SourceTableposiadaniu> 15 MM rekordów i Bad_Phrase> 3K rekordów uruchomienie następującego zapytania w programie SQL Server 2005 SP4 zajmuje prawie 10 godzin.

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

W języku angielskim to zapytanie liczy liczbę odrębnych fraz wymienionych w Bad_Phrase, które są podciągiem pola Namew polu, SourceTablea następnie umieszcza ten wynik w polu Bad_Count.

Chciałbym uzyskać kilka sugestii, w jaki sposób uruchomić to zapytanie znacznie szybciej.

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 nazwisk
• B = liczba złych fraz
• L = ś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 .

Odłóżmy na chwilę oczywistą kwestię poruszoną przez Aarona Bertranda w komentarzach na sekundę:

Czyli skanujesz tabelę 3k razy i potencjalnie aktualizujesz wszystkie wiersze 15MM wszystkie 3k razy i oczekujesz, że będzie szybki?

Fakt, że twoje podzapytanie używa symboli wieloznacznych po obu stronach, ma ogromny wpływ na możliwości sprzedaży . Aby zacytować ten post na blogu:

Oznacza to, że SQL Server musi czytać każdy wiersz z tabeli Produkt, sprawdzać, czy ma gdzieś w nazwie „nutę”, a następnie zwracać nasze wyniki.

Zamień słowo „nakrętka” dla każdego „złego słowa” i „Produkt” dla SourceTable, a następnie połącz to z komentarzem Aarona i powinieneś zacząć rozumieć, dlaczego tak trudno (czytać niemożliwe) sprawić, by działał szybko przy użyciu twojego obecnego algorytmu.

Widzę kilka opcji:

1. Przekonaj biznes, aby kupił serwer potworów, który ma tyle mocy, że pokonuje zapytanie brutalną siłą ścinającą. (To się nie stanie, więc trzymajcie kciuki, inne opcje są lepsze)
2. Korzystając z istniejącego algorytmu, zaakceptuj ból raz, a następnie rozłóż go. Wymagałoby to obliczenia złych słów na wstawce, co spowolni wstawianie, i zaktualizuje całą tabelę tylko po wprowadzeniu / wykryciu nowego złego słowa.
3. Odpowiedź Embrace'a Geoffa . To świetny algorytm i znacznie lepszy niż cokolwiek, co bym wymyślił.
4. Wykonaj opcję 2, ale zamień swój algorytm na Geoffa.

W zależności od wymagań poleciłbym opcję 3 lub 4.

po pierwsze to dziwna aktualizacja

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

Jak „%” + [Bad_Phrase]. [PHRASE] cię zabija,
który nie może korzystać z indeksu

Projektowanie danych nie jest optymalne pod względem szybkości
Czy potrafisz podzielić [Bad_Phrase]. [PHRASE] na pojedyncze frazy / słowa?
Jeśli ta sama fraza / słowo pojawia się więcej niż jedno, możesz wpisać je więcej niż jeden raz, jeśli chcesz, aby miał większą liczbę,
więc liczba wierszy w złej fazie wzrośnie.
Jeśli możesz, to będzie to znacznie szybsze

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]

Nie jestem pewien, czy 2005 obsługuje to, ale Indeks pełnotekstowy i użycie Zawiera