Mise à jour lente sur une grande table avec sous-requête

Avec SourceTable> 15MM d'enregistrements et Bad_Phraseayant> 3K enregistrements, la requête suivante prend près de 10 heures pour s'exécuter sur SQL Server 2005 SP4.

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

En anglais, cette requête compte le nombre d'expressions distinctes répertoriées dans Bad_Phrase qui sont une sous-chaîne du champ Namedans le SourceTablepuis en plaçant ce résultat dans le champ Bad_Count.

Je voudrais quelques suggestions sur la façon d'exécuter cette requête beaucoup plus rapidement.

Bien que je convienne avec d'autres commentateurs qu'il s'agit d'un problème de calcul coûteux, je pense qu'il y a beaucoup de place à l'amélioration en peaufinant le SQL que vous utilisez. Pour illustrer, je crée un faux ensemble de données avec des noms 15MM et des phrases 3K, j'ai exécuté l'ancienne approche et j'ai exécuté une nouvelle approche.

Script complet pour générer un faux ensemble de données et essayer la nouvelle approche

TL; DR

Sur ma machine et ce faux ensemble de données, l' approche originale prend environ 4 heures pour s'exécuter. La nouvelle approche proposée prend environ 10 minutes , une amélioration considérable. Voici un bref résumé de l'approche proposée:

• Pour chaque nom, générez la sous-chaîne à partir de chaque décalage de caractère (et plafonné à la longueur de la plus mauvaise phrase incorrecte, comme optimisation)
• Créer un index cluster sur ces sous-chaînes
• Pour chaque mauvaise phrase, effectuez une recherche dans ces sous-chaînes pour identifier les correspondances
• Pour chaque chaîne d'origine, calculez le nombre de mauvaises phrases distinctes qui correspondent à une ou plusieurs sous-chaînes de cette chaîne

Approche originale: analyse algorithmique

D'après le plan de l'original UPDATE déclaration d' , nous pouvons voir que la quantité de travail est linéairement proportionnelle à la fois au nombre de noms (15MM) et au nombre de phrases (3K). Donc, si nous multiplions le nombre de noms et de phrases par 10, le temps d'exécution global sera ~ 100 fois plus lent.

La requête est en fait proportionnelle à la longueur de la nameaussi; bien que cela soit un peu caché dans le plan de requête, il apparaît dans le "nombre d'exécutions" pour rechercher dans le spouleur de table. Dans le plan réel, nous pouvons voir que cela se produit non seulement une fois par name, mais en fait une fois par caractère décalé dans le name. Cette approche est donc O ( # names* # phrases* name length) en complexité d'exécution.

Nouvelle approche: code

Ce code est également disponible dans le casier complet mais je l'ai copié ici pour plus de commodité. Le pastebin a également la définition de procédure complète, qui comprend les variables @minIdet @maxIdque vous voyez ci-dessous pour définir les limites du lot en cours.

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

Nouvelle approche: plans de requête

Tout d'abord, nous générons la sous-chaîne à partir de chaque décalage de caractère

Créez ensuite un index cluster sur ces sous-chaînes

Maintenant, pour chaque mauvaise phrase, nous recherchons dans ces sous-chaînes pour identifier les correspondances. Nous calculons ensuite le nombre de mauvaises phrases distinctes qui correspondent à une ou plusieurs sous-chaînes de cette chaîne. C'est vraiment l'étape clé; en raison de la façon dont nous avons indexé les sous-chaînes, nous n'avons plus à vérifier un produit croisé complet de mauvaises phrases et de mauvais noms. Cette étape, qui effectue le calcul réel, ne représente qu'environ 10% du temps d'exécution réel (le reste est le prétraitement des sous-chaînes).

Enfin, effectuez l'instruction de mise à jour réelle, en utilisant a LEFT OUTER JOINpour attribuer un nombre de 0 à tous les noms pour lesquels nous n'avons trouvé aucune mauvaise phrase.

Nouvelle approche: analyse algorithmique

La nouvelle approche peut être divisée en deux phases, le prétraitement et l'appariement. Définissons les variables suivantes:

• N = nombre de noms
• B = nombre de mauvaises phrases
• L = longueur moyenne du nom, en caractères

La phase de prétraitement consiste O(N*L * LOG(N*L))à créer des N*Lsous-chaînes puis à les trier.

La correspondance réelle vise O(B * LOG(N*L))à rechercher dans les sous-chaînes pour chaque mauvaise phrase.

De cette façon, nous avons créé un algorithme qui n'évolue pas linéairement avec le nombre de phrases erronées, un déverrouillage des performances clés lorsque nous évoluons vers des expressions 3K et au-delà. Autrement dit, l'implémentation d'origine prend environ 10 fois aussi longtemps que nous passons de 300 phrases mauvaises à 3K phrases mauvaises. De même, cela prendrait 10 fois plus de temps si nous passions de 3K mauvaises phrases à 30K. La nouvelle implémentation, cependant, évoluera de manière sous-linéaire et prend en fait moins de 2x le temps mesuré sur les 3K mauvaises phrases lorsqu'elle est mise à l'échelle jusqu'à 30K de mauvaises phrases.

Hypothèses / mises en garde

• Je divise le travail global en lots de taille modeste. C'est probablement une bonne idée pour l'une ou l'autre approche, mais elle est particulièrement importante pour la nouvelle approche afin que SORTles sous-chaînes soient indépendantes pour chaque lot et tiennent facilement en mémoire. Vous pouvez manipuler la taille du lot selon vos besoins, mais il ne serait pas judicieux d'essayer toutes les lignes de 15 mm en un seul lot.
• Je suis sur SQL 2014, pas SQL 2005, car je n'ai pas accès à une machine SQL 2005. J'ai pris soin de ne pas utiliser de syntaxe qui n'est pas disponible dans SQL 2005, mais je peux toujours bénéficier de la fonctionnalité d' écriture différée tempdb dans SQL 2012+ et de la fonctionnalité SELECT INTO parallèle dans SQL 2014.
• La longueur des noms et des phrases est assez importante pour la nouvelle approche. Je suppose que les mauvaises phrases sont généralement assez courtes, car cela correspond probablement à des cas d'utilisation réels. Les noms sont un peu plus longs que les mauvaises phrases, mais sont supposés ne pas être des milliers de caractères. Je pense que c'est une hypothèse juste, et des chaînes de noms plus longues ralentiraient également votre approche d'origine.
• Une partie de l'amélioration (mais loin d'être la totalité) est due au fait que la nouvelle approche peut tirer parti du parallélisme plus efficacement que l'ancienne approche (qui fonctionne sur un seul thread). Je suis sur un ordinateur portable quad core, il est donc agréable d'avoir une approche qui peut mettre ces cœurs à utiliser.

Article de blog connexe

Aaron Bertrand explore ce type de solution plus en détail dans son article de blog One way pour obtenir une recherche d'index pour un% générique de premier plan .

Laissons de côté le problème évident soulevé par Aaron Bertrand dans les commentaires pendant une seconde:

Vous analysez donc la table 3K fois, et mettez potentiellement à jour toutes les lignes de 15MM toutes les 3K fois, et vous vous attendez à ce que ce soit rapide?

Le fait que votre sous-requête utilise les caractères génériques des deux côtés affecte considérablement la sargabilité . Pour prendre une citation de ce billet de blog:

Cela signifie que SQL Server doit lire chaque ligne de la table Product, vérifier si elle est «écrou» n'importe où dans le nom, puis renvoyer nos résultats.

Échangez le mot «écrou» pour chaque «mauvais mot» et «produit» pour SourceTable, puis combinez cela avec le commentaire d'Aaron et vous devriez commencer à voir pourquoi il est extrêmement difficile (lire impossible) de le faire fonctionner rapidement en utilisant votre algorithme actuel.

Je vois quelques options:

1. Convaincre les entreprises d'acheter un serveur monstre qui a tellement de puissance qu'il surmonte la requête par force brute de cisaillement. (Cela ne va pas se produire, alors croisez les doigts, les autres options sont meilleures)
2. En utilisant votre algorithme existant, acceptez la douleur une fois, puis étalez-la. Cela impliquerait de calculer les mauvais mots sur l'insertion, ce qui ralentirait les insertions et ne mettrait à jour la table entière que lorsqu'un nouveau mauvais mot est entré / découvert.
3. Embrassez la réponse de Geoff . C'est un excellent algorithme, et bien meilleur que tout ce que j'aurais imaginé.
4. Faites l'option 2 mais remplacez votre algorithme par celui de Geoff.

Selon vos besoins, je recommanderais l'option 3 ou 4.

c'est juste une étrange mise à jour

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

Comme '%' + [Bad_Phrase]. [PHRASE] vous tue
Qui ne peut pas utiliser d'index

La conception des données n'est pas optimale pour la vitesse
Pouvez-vous diviser la [Bad_Phrase]. [PHRASE] en une seule phrase (s) / mot?
Si la même phrase / mot apparaît plus que vous pouvez entrer plus d'une fois si vous voulez avoir un nombre plus élevé
Ainsi , le nombre de lignes en mauvais pharase grimperait
Si vous pouvez alors ce sera beaucoup plus rapide

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]

Je ne sais pas si 2005 le prend en charge, mais l'index de texte intégral et l'utilisation contiennent