Sqlserver
 sql >> Base de données >  >> RDS >> Sqlserver

Recherche de chaînes génériques Trigram dans SQL Server

La recherche de données de chaîne pour une correspondance de sous-chaîne arbitraire peut être une opération coûteuse dans SQL Server. Requêtes de la forme Column LIKE '%match%' ne peut pas utiliser les capacités de recherche d'un index b-tree, le processeur de requêtes doit donc appliquer le prédicat à chaque ligne individuellement. De plus, chaque test doit appliquer correctement l'ensemble complet des règles de classement compliquées. En combinant tous ces facteurs, il n'est pas surprenant que ces types de recherches puissent être lentes et gourmandes en ressources.

La recherche en texte intégral est un outil puissant pour la correspondance linguistique, et la nouvelle recherche sémantique statistique est idéale pour trouver des documents ayant des significations similaires. Mais parfois, vous avez vraiment besoin de trouver des chaînes qui contiennent une sous-chaîne particulière - une sous-chaîne qui peut même ne pas être un mot, dans n'importe quelle langue.

Si les données recherchées ne sont pas volumineuses ou si les exigences de temps de réponse ne sont pas critiques, utilisez LIKE '%match%' pourrait bien être une solution appropriée. Mais, dans les rares occasions où le besoin d'une recherche ultra-rapide l'emporte sur toutes les autres considérations (y compris l'espace de stockage), vous pouvez envisager une solution personnalisée utilisant des n-grammes. La variation spécifique explorée dans cet article est un trigramme à trois caractères.

Recherche générique à l'aide de trigrammes

L'idée de base d'une recherche par trigramme est assez simple :

  1. Persistez à des sous-chaînes de trois caractères (trigrammes) des données cibles.
  2. Divisez le(s) terme(s) de recherche en trigrammes
  3. Mettre en correspondance les trigrammes de recherche avec les trigrammes stockés (recherche d'égalité)
  4. Intersecter les lignes qualifiées pour trouver les chaînes qui correspondent à tous les trigrammes
  5. Appliquez le filtre de recherche d'origine à l'intersection très réduite

Nous allons travailler sur un exemple pour voir exactement comment tout cela fonctionne et quels sont les compromis.

Exemple de tableau et de données

Le script ci-dessous crée un exemple de table et le remplit avec un million de lignes de données de chaîne. Chaque chaîne comporte 20 caractères, les 10 premiers caractères étant numériques. Les 10 caractères restants sont un mélange de chiffres et de lettres de A à F, générés à l'aide de NEWID() . Il n'y a rien de vraiment spécial dans cet exemple de données ; la technique du trigramme est assez générale.

-- Le test tableCREATE 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 rowsINSERT dbo.Example WITH (TABLOCKX) (string)SELECT TOP (1 * 1000 * 1000) -- 10 caractères numériques REPLACE(STR(RAND(CHECKSUM(NEWID())) * 1e10, 10), SPACE(1), ' 0') + -- plus 10 caractères mixtes numériques + [A-F] RIGHT(NEWID(), 10)FROM master.dbo.spt_values ​​AS SV1CROSS JOIN master.dbo.spt_values ​​AS SV2OPTION (MAXDOP 1);

Cela prend environ 3 secondes pour créer et remplir les données sur mon modeste ordinateur portable. Les données sont pseudo-aléatoires, mais à titre indicatif, elles ressembleront à ceci :

Exemple de données

Générer des trigrammes

La fonction en ligne suivante génère des trigrammes alphanumériques distincts à partir d'une chaîne d'entrée donnée :

--- Générer des trigrammes à partir d'une chaîneCREATE FUNCTION dbo.GenerateTrigrams (@string varchar(255))RETURNS tableWITH SCHEMABINDINGAS 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)), -- Tableau des nombres (256) Nums AS ( SELECT n =ROW_NUMBER() OVER (ORDER BY A.v) FROM N16 AS A CROSS JOIN N16 AS B ), Trigrammes AS ( -- Chaque sous-chaîne de 3 caractères 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 ) -- Supprimez les doublons et assurez-vous que tous trois caractères sont alphanumériques SELECT DISTINCT T.trigram FROM Trigrams AS T WHERE -- Comparaison de classement binaire so r les anges fonctionnent comme prévu T.trigram COLLATE Latin1_General_BIN2 NOT LIKE '%[^A-Z0-9a-z]%';

Comme exemple de son utilisation, l'appel suivant :

SELECT GT.trigramFROM dbo.GenerateTrigrams('SQLperformance.com') AS GT ;

Produit les trigrammes suivants :

Trigrammes SQLperformance.com

Le plan d'exécution est une traduction assez directe du T-SQL dans ce cas :

  • Génération de lignes (cross join of Constant Scans)
  • Numérotation des lignes (Segment et Projet de séquence)
  • Limiter les nombres nécessaires en fonction de la longueur de la chaîne (Top)
  • Supprimer les trigrammes contenant des caractères non alphanumériques (Filtre)
  • Supprimer les doublons (tri distinct)

Plan de génération des trigrammes

Charger les trigrammes

L'étape suivante consiste à conserver les trigrammes pour les exemples de données. Les trigrammes seront conservés dans un nouveau tableau, rempli à l'aide de la fonction en ligne que nous venons de créer :

-- Trigrams for Example tableCREATE TABLE dbo.ExampleTrigrams( id integer NOT NULL, trigram char(3) NOT NULL);GO-- Generate trigramsINSERT dbo.ExampleTrigrams WITH (TABLOCKX) (id, trigram)SELECT E.id, GT.trigramFROM dbo.Example AS ECROSS APPLY dbo.GenerateTrigrams(E.string) AS GT ;

Cela prend environ 20 secondes à exécuter sur mon instance d'ordinateur portable SQL Server 2016. Cette exécution particulière a produit 17 937 972 lignes de trigrammes pour les 1 millions de lignes de données de test de 20 caractères. Le plan d'exécution montre essentiellement le plan de fonction en cours d'évaluation pour chaque ligne du tableau Exemple :

Remplir la table des trigrammes

Puisque ce test a été réalisé sur SQL Server 2016 (chargement d'une table de tas, sous le niveau de compatibilité de la base de données 130, et avec un TABLOCK indice), le plan bénéficie d'insertion parallèle. Les lignes sont réparties entre les threads par le parcours parallèle de la table Exemple, et restent ensuite sur le même thread (pas d'échanges de repartitionnement).

L'opérateur de tri peut sembler un peu imposant, mais les nombres indiquent le nombre total de lignes triées, sur toutes les itérations de la jointure de boucle imbriquée. En fait, il existe un million de sortes distinctes, de 18 rangées chacune. À un degré de parallélisme de quatre (deux cœurs hyperthreadés dans mon cas), il y a un maximum de quatre petits tris en cours à tout moment, et chaque instance de tri peut réutiliser la mémoire. Cela explique pourquoi l'utilisation maximale de la mémoire de ce plan d'exécution n'est que de 136 Ko (bien que 2 152 Ko aient été accordés).

La table des trigrammes contient une ligne pour chaque trigramme distinct dans chaque ligne de la table source (identifiée par id ):

Exemple de tableau des trigrammes

Nous créons maintenant un index clusterisé b-tree pour prendre en charge la recherche de correspondances de trigramme :

-- Trigram search indexCREATE UNIQUE CLUSTERED INDEX [CUQ dbo.ExampleTrigrams (trigram, id)]ON dbo.ExampleTrigrams (trigram, id)WITH (DATA_COMPRESSION =ROW);

Cela prend environ 45 secondes , bien qu'une partie de cela soit due au débordement du tri (mon instance est limitée à 4 Go de mémoire). Une instance avec plus de mémoire disponible pourrait probablement terminer cette construction d'index parallèle avec une journalisation minimale un peu plus rapidement.

Plan de construction d'index

Notez que l'index est spécifié comme unique (en utilisant les deux colonnes de la clé). Nous aurions pu créer un index clusterisé non unique sur le trigramme seul, mais SQL Server aurait de toute façon ajouté des unificateurs de 4 octets à presque toutes les lignes. Une fois que nous avons pris en compte le fait que les uniquificateurs sont stockés dans la partie de longueur variable de la ligne (avec la surcharge associée), il est simplement plus logique d'inclure id dans la clé et finissons-en.

La compression des lignes est spécifiée car elle réduit utilement la taille de la table des trigrammes de 277 Mo à 190 Mo (à titre de comparaison, la table d'exemple est de 32 Mo). Si vous n'utilisez pas au moins SQL Server 2016 SP1 (où la compression des données est devenue disponible pour toutes les éditions), vous pouvez omettre la clause de compression si nécessaire.

En guise d'optimisation finale, nous allons également créer une vue indexée sur la table des trigrammes pour faciliter et accélérer la recherche des trigrammes les plus et les moins courants dans les données. Cette étape peut être omise, mais elle est recommandée pour les performances.

-- Sélectivité de chaque trigramme (optimisation des performances)CREATE VIEW dbo.ExampleTrigramCountsWITH SCHEMABINDINGASSELECT ET.trigram, cnt =COUNT_BIG(*)FROM dbo.ExampleTrigrams AS ETGROUP BY ET.trigram;GO-- Matérialiser la vueCREATE UNIQUE CLUSTERED INDEX [ CUQ dbo.ExampleTrigramCounts (trigramme)]ON dbo.ExampleTrigramCounts (trigramme);

Plan de construction en vue indexée

Cela ne prend que quelques secondes. La taille de la vue matérialisée est minuscule, juste 104 Ko .

Recherche trigramme

Étant donné une chaîne de recherche (par exemple, '%find%this%' ), notre approche consistera à :

  1. Générer le jeu complet de trigrammes pour la chaîne de recherche
  2. Utilisez la vue indexée pour trouver les trois trigrammes les plus sélectifs
  3. Trouvez les identifiants correspondant à tous les trigrammes disponibles
  4. Récupérer les chaînes par identifiant
  5. Appliquer le filtre complet aux lignes qualifiées de trigramme

Trouver des trigrammes sélectifs

Les deux premières étapes sont assez simples. Nous avons déjà une fonction pour générer des trigrammes pour une chaîne arbitraire. Trouver le plus sélectif de ces trigrammes peut être réalisé en se joignant à la vue indexée. Le code suivant encapsule l'implémentation de notre exemple de table dans une autre fonction en ligne. Il fait pivoter les trois trigrammes les plus sélectifs sur une seule ligne pour faciliter leur utilisation ultérieure :

-- Les trigrammes les plus sélectifs pour une chaîne de recherche-- Renvoie toujours une ligne (NULL si aucun trigramme n'est trouvé)CREATE FUNCTION dbo.Example_GetBestTrigrams (@string varchar(255))RETURNS tableWITH SCHEMABINDING ASRETURN 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 ( -- Générer des trigrammes pour la chaîne de recherche -- et choisir les trois plus sélectifs 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 AVEC (NOEXPAND) ON ETC.trigram =GT.trigram ORDER BY ETC.cnt ASC ) AS BT ;

Par exemple :

SELECT EGBT.trigram1, EGBT.trigram2, EGBT.trigram3 FROM dbo.Example_GetBestTrigrams('%1234%5678%') AS EGBT ;

renvoie (pour mes exemples de données) :

Trigrammes sélectionnés

Le plan d'exécution est :

Plan d'exécution GetBestTrigrams

Il s'agit du plan de génération de trigrammes familier du précédent, suivi d'une recherche dans la vue indexée pour chaque trigramme, en triant par le nombre de correspondances, en numérotant les lignes (Sequence Project), en limitant l'ensemble à trois lignes (Top), puis en pivotant le résultat (Stream Aggregate).

Trouver des identifiants correspondant à tous les trigrammes

L'étape suivante consiste à rechercher les ID de ligne de table d'exemple qui correspondent à tous les trigrammes non nuls récupérés par l'étape précédente. Le problème ici est que nous pouvons avoir zéro, un, deux ou trois trigrammes disponibles. L'implémentation suivante encapsule la logique nécessaire dans une fonction multi-instructions, renvoyant les identifiants qualifiants dans une variable de table :

-- Renvoie des exemples d'identifiants correspondant à tous les trigrammes (non nuls) fournisCREATE FUNCTION dbo.Example_GetTrigramMatchIDs( @Trigram1 char(3), @Trigram2 char(3), @Trigram3 char(3))RETURNS @IDs table (id integer PRIMARY KEY)WITH SCHEMABINDING ASBEGIN IF @Trigram1 IS NOT NULL BEGIN IF @Trigram2 IS NOT NULL BEGIN IF @Trigram3 IS NOT NULL BEGIN -- 3 trigrammes disponibles 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); FINIR; ELSE BEGIN -- 2 trigrammes disponibles 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 ( FUSION JOINTURE ); FINIR; FINIR; ELSE BEGIN -- 1 trigramme disponible INSERT @IDs (id) SELECT ET1.id FROM dbo.ExampleTrigrams AS ET1 WHERE ET1.trigram =@Trigram1; FINIR; FINIR; RETOUR;FIN;

Le plan d'exécution estimé pour cette fonction montre la stratégie :

Plan d'identifiants de correspondance de trigrammes

S'il y a un trigramme disponible, une seule recherche dans la table des trigrammes est effectuée. Sinon, deux ou trois recherches sont effectuées et l'intersection des identifiants est trouvée à l'aide d'une ou plusieurs fusions efficaces un-à-plusieurs. Il n'y a pas d'opérateurs consommant de la mémoire dans ce plan, donc aucune chance de débordement de hachage ou de tri.

En continuant l'exemple de recherche, nous pouvons trouver des identifiants correspondant aux trigrammes disponibles en appliquant la nouvelle fonction :

SELECT EGTMID.id FROM dbo.Example_GetBestTrigrams('%1234%5678%') AS EGBTCROSS APPLY dbo.Example_GetTrigramMatchIDs (EGBT.trigram1, EGBT.trigram2, EGBT.trigram3) AS EGTMID ;

Cela renvoie un ensemble comme celui-ci :

Identifiants correspondants

Le plan réel (post-exécution) de la nouvelle fonction montre la forme du plan avec trois entrées de trigramme utilisées :

Plan de correspondance d'identité réel

Cela montre assez bien la puissance de la correspondance des trigrammes. Bien que les trois trigrammes identifient chacun environ 11 000 lignes dans le tableau Exemple, la première intersection réduit cet ensemble à 1 004 lignes, et la seconde intersection le réduit à seulement 7 .

Mise en œuvre complète de la recherche de trigrammes

Maintenant que nous avons les identifiants correspondant aux trigrammes, nous pouvons rechercher les lignes correspondantes dans le tableau Exemple. Nous devons encore appliquer la condition de recherche d'origine comme vérification finale, car les trigrammes peuvent générer des faux positifs (mais pas des faux négatifs). Le dernier problème à résoudre est que les étapes précédentes n'ont peut-être trouvé aucun trigramme. Cela peut être dû, par exemple, au fait que la chaîne de recherche contient trop peu d'informations. Une chaîne de recherche de '%FF%' ne peut pas utiliser la recherche de trigramme car deux caractères ne suffisent pas pour générer même un seul trigramme. Pour gérer ce scénario avec élégance, notre recherche détectera cette condition et reviendra à une recherche sans trigramme.

La fonction en ligne finale suivante implémente la logique requise :

-- Implémentation de la rechercheCREATE FUNCTION dbo.Example_TrigramSearch( @Search varchar(255))RETURNS tableWITH SCHEMABINDINGASRETURN SELECT Result.string FROM dbo.Example_GetBestTrigrams(@Search) AS GBT CROSS APPLY ( -- Trigram search SELECT E.id, E. chaîne FROM dbo.Example_GetTrigramMatchIDs (GBT.trigram1, GBT.trigram2, GBT.trigram3) AS MID JOIN dbo.Example AS E ON E.id =MID.id WHERE -- Au moins un trigramme trouvé GBT.trigram1 IS NOT NULL AND E .string LIKE @Search UNION ALL -- Recherche sans trigramme SELECT E.id, E.string FROM dbo.Example AS E WHERE -- Aucun trigramme trouvé GBT.trigram1 IS NULL AND E.string LIKE @Search ) AS Result; 

 La caractéristique clé est la référence externe à GBT.trigram1 de part et d'autre de l'UNION ALL . Ceux-ci se traduisent par des filtres avec des expressions de démarrage dans le plan d'exécution. Un filtre de démarrage n'exécute son sous-arbre que si sa condition est vraie. L'effet net est qu'une seule partie de l'union sera exécutée, selon que nous avons trouvé un trigramme ou non. La partie pertinente du plan d'exécution est :
  

 Effet de filtre de démarrage 
 

 Soit le Example_GetTrigramMatchIDs la fonction sera exécutée (et les résultats recherchés dans l'exemple à l'aide d'une recherche sur l'identifiant), ou le balayage d'index clusterisé de l'exemple avec un LIKE résiduel le prédicat s'exécutera, mais pas les deux.
 
Performances
 

 Le code suivant teste les performances de la recherche de trigrammes par rapport à l'équivalent LIKE :
 
SET STATISTICS XML OFFDECLARE @S datetime2 =SYSUTCDATETIME(); SELECT F2.stringFROM dbo.Example AS F2WHERE F2.string LIKE '%1234%5678%'OPTION (MAXDOP 1); SELECT ElapsedMS =DATEDIFF(MILLISECOND, @S, SYSUTCDATETIME());GOSET STATISTICS XML OFFDECLARE @S datetime2 =SYSUTCDATETIME(); SELECT ETS.stringFROM dbo.Example_TrigramSearch('%1234%5678%') AS ETS ; SELECT ElapsedMS =DATEDIFF(MILLISECOND, @S, SYSUTCDATETIME());
 

 Ceux-ci produisent tous les deux la ou les mêmes lignes de résultat mais le LIKE la requête s'exécute pendant 2 100 ms , alors que la recherche de trigrammes prend 15 ms .
 

 Des performances encore meilleures sont possibles. Généralement, les performances s'améliorent à mesure que les trigrammes deviennent plus sélectifs et moins nombreux (en dessous du maximum de trois dans cette implémentation). Par exemple :
 
SET STATISTICS XML OFFDECLARE @S datetime2 =SYSUTCDATETIME(); SELECT ETS.stringFROM dbo.Example_TrigramSearch('%BEEF%') AS ETS ; SELECT ElapsedMS =DATEDIFF(MILLISECOND, @S, SYSUTCDATETIME());
 

 Cette recherche a renvoyé 111 lignes dans la grille SSMS en 4 ms . Le LIKE l'équivalent a duré 1950 ms .
 
Maintenir les trigrammes
 

 Si la table cible est statique, il n'y a évidemment aucun problème à maintenir la table de base et la table de trigrammes associée synchronisée. De même, s'il n'est pas nécessaire que les résultats de la recherche soient complètement à jour à tout moment, une actualisation planifiée de la ou des tables de trigrammes peut bien fonctionner.
 

 Sinon, nous pouvons utiliser des déclencheurs assez simples pour synchroniser les données de recherche de trigrammes avec les chaînes sous-jacentes. L'idée générale est de générer des trigrammes pour les lignes supprimées et insérées, puis de les ajouter ou de les supprimer dans la table des trigrammes selon le cas. Les déclencheurs d'insertion, de mise à jour et de suppression ci-dessous illustrent cette idée en pratique :
 
-- Maintenir les trigrammes après Example insertsCREATE TRIGGER MaintainTrigrams_AION dbo.ExampleAFTER INSERTASBEGIN IF @@ROWCOUNT =0 RETURN; SI TRIGGER_NESTLEVEL(@@PROCID, 'APRÈS', 'DML')> 1 RETOUR ; SET NOCOUNT ON ; DÉFINIR LE COMPTE DE LIGNES 0 ; -- Insérer les trigrammes associés INSERT dbo.ExampleTrigrams (id, trigram) SELECT INS.id, GT.trigram FROM Inséré AS INS CROSS APPLY dbo.GenerateTrigrams(INS.string) AS GT;END;
 
-- Maintenir les trigrammes après Exemple deletesCREATE TRIGGER MaintainTrigrams_ADON dbo.ExampleAFTER DELETEASBEGIN IF @@ROWCOUNT =0 RETURN; SI TRIGGER_NESTLEVEL(@@PROCID, 'APRÈS', 'DML')> 1 RETOUR ; SET NOCOUNT ON ; DÉFINIR LE COMPTE DE LIGNES 0 ; -- Trigrammes associés supprimés DELETE ET WITH (SERIALIZABLE) FROM Supprimé 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; FIN ;
 
-- Maintenir les trigrammes après Exemple updatesCREATE TRIGGER MaintainTrigrams_AUON dbo.ExampleAFTER UPDATEASBEGIN IF @@ROWCOUNT =0 RETURN; SI TRIGGER_NESTLEVEL(@@PROCID, 'APRÈS', 'DML')> 1 RETOUR ; SET NOCOUNT ON ; DÉFINIR LE COMPTE DE LIGNES 0 ; -- Trigrammes associés supprimés DELETE ET WITH (SERIALIZABLE) FROM Supprimé 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; -- Insérer les trigrammes associés INSERT dbo.ExampleTrigrams (id, trigram) SELECT INS.id, GT.trigram FROM Inséré AS INS CROSS APPLY dbo.GenerateTrigrams(INS.string) AS GT;END;
 

 Les déclencheurs sont assez efficaces et gèrent à la fois les modifications à une ou plusieurs lignes (y compris les multiples actions disponibles lors de l'utilisation d'un MERGE déclaration). La vue indexée sur la table des trigrammes sera automatiquement maintenue par SQL Server sans que nous ayons besoin d'écrire de code de déclenchement.
 
Opération de déclenchement
 

 Par exemple, exécutez une instruction pour supprimer une ligne arbitraire de la table Exemple :
 
-- Single row deleteDELETE TOP (1) dbo.Example;
 

 Le plan d'exécution post-exécution (réel) inclut une entrée pour le déclencheur après suppression :
  

 Supprimer le plan d'exécution du déclencheur 
 

 La section jaune du plan lit les lignes du supprimé pesudo-table, génère des trigrammes pour chaque chaîne d'exemple supprimée (en utilisant le plan familier surligné en vert), puis localise et supprime les entrées de table de trigrammes associées. La dernière section du plan, affichée en rouge, est automatiquement ajoutée par SQL Server pour maintenir à jour la vue indexée.
 

 Le plan du déclencheur d'insertion est extrêmement similaire. Les mises à jour sont gérées en effectuant une suppression suivie d'une insertion. Exécutez le script suivant pour afficher ces plans et confirmer que les lignes nouvelles et mises à jour peuvent être localisées à l'aide de la fonction de recherche de trigramme :
 
-- Single row insertINSERT dbo.Example (string) VALUES ('SQLPerformance.com'); -- Trouvez la nouvelle ligneSELECT ETS.stringFROM dbo.Example_TrigramSearch('%perf%') AS ETS; -- Mise à jour à une seule ligneUPDATE TOP (1) dbo.Example SET string ='12345678901234567890'; -- Insertion multi-lignesINSERT 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 ; -- Mise à jour multi-lignesUPDATE TOP (1000) dbo.Example SET string ='12345678901234567890'; -- Rechercher les lignes mises à jourSELECT ETS.string FROM dbo.Example_TrigramSearch('12345678901234567890') AS ETS;
 
Exemple de fusion
 

 Le script suivant montre un MERGE instruction utilisée pour insérer, supprimer et mettre à jour l'Exemple de table en une seule fois :
 
-- MERGE demoDECLARE @MergeData table ( id entier UNIQUE CLUSTERED NULL, opération 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'); -- Mettre à jour la table DECLARE @Actions ( action$ nvarchar(10) NOT NULL, old_id entier NULL, old_string char(20) NULL, new_id entier NULL, new_string char(20) NULL); MERGE dbo.Example AS EUSING @MergeData AS MD ON MD.id =E.idWHEN MATCHED AND MD.operation ='DEL' THEN DELETEWHEN MATCHED AND MD.operation ='UPD' THEN UPDATE SET E.string =MD.stringWHEN NOT MATCHED AND MD.operation ='INS' THEN INSERT (string) VALUES (MD.string)OUTPUT $action, Deleted.id, Deleted.string, Inserted.id, Inserted.stringINTO @Actions (action$, old_id, old_string, new_id, nouvelle_chaîne); SELECT * FROM @Actions COMME A ;
 

 La sortie affichera quelque chose comme :
  

 Sortie de l'action 
 
Réflexions finales
 

 Il est peut-être possible d'accélérer les opérations de suppression et de mise à jour importantes en référençant directement les identifiants au lieu de générer des trigrammes. Ceci n'est pas implémenté ici car cela nécessiterait un nouvel index non clusterisé sur la table des trigrammes, doublant l'espace de stockage (déjà significatif) utilisé. La table des trigrammes contient un seul entier et un char(3) Par rangée; un index non clusterisé sur la colonne entière gagnerait le char(3) colonne à tous les niveaux (grâce à l'index clusterisé et à la nécessité pour les clés d'index d'être uniques à chaque niveau). Il faut également tenir compte de l'espace mémoire, car les recherches par trigramme fonctionnent mieux lorsque toutes les lectures proviennent du cache.
 

 L'index supplémentaire ferait de l'intégrité référentielle en cascade une option, mais cela pose souvent plus de problèmes qu'il n'en vaut la peine.
 

 La recherche de trigrammes n'est pas une panacée. Les exigences de stockage supplémentaires, la complexité de la mise en œuvre et l'impact sur les performances de mise à jour pèsent lourdement sur elle. La technique est également inutile pour les recherches qui ne génèrent aucun trigramme (3 caractères minimum). Bien que l'implémentation de base présentée ici puisse gérer de nombreux types de recherche (commence par, contient, se termine par, plusieurs caractères génériques), elle ne couvre pas toutes les expressions de recherche possibles qui peuvent fonctionner avec LIKE . Cela fonctionne bien pour les chaînes de recherche qui génèrent des trigrammes de type AND ; plus de travail est nécessaire pour gérer les chaînes de recherche qui nécessitent une gestion de type OR, ou des options plus avancées comme les expressions régulières.
 

 Cela dit, si votre application doit vraiment ont des recherches rapides de chaînes génériques, les n-grammes sont quelque chose à considérer sérieusement.
 

 Contenu connexe :Une façon d'obtenir une recherche d'index pour un %wildcard de début par Aaron Bertrand.