Le mois dernier, j'ai couvert un casse-tête consistant à faire correspondre chaque ligne d'une table avec la correspondance la plus proche d'une autre table. J'ai reçu ce casse-tête de Karen Ly, analyste junior des titres à revenu fixe chez RBC. J'ai couvert deux solutions relationnelles principales qui combinaient l'opérateur APPLY avec des sous-requêtes basées sur TOP. La solution 1 avait toujours une mise à l'échelle quadratique. La solution 2 a plutôt bien fonctionné lorsqu'elle était fournie avec de bons index de support, mais sans ces index, elle avait également une mise à l'échelle quadrique. Dans cet article, je couvre les solutions itératives qui, bien qu'elles soient généralement mal vues par les professionnels de SQL, offrent une bien meilleure mise à l'échelle dans notre cas, même sans indexation optimale.

Le défi

Pour rappel, notre défi concerne des tables appelées T1 et T2, que vous créez avec le code suivant :

 SET NOCOUNT ON ; IF DB_ID('testdb') IS NULL CREATE DATABASE testdb; ALLEZ UTILISER testdb ; SUPPRIMER TABLE SI EXISTE dbo.T1, dbo.T2 ; CREATE TABLE dbo.T1 ( keycol INT NOT NULL IDENTITY CONSTRAINT PK_T1 PRIMARY KEY, val INT NOT NULL, othercols BINARY(100) NOT NULL CONSTRAINT DFT_T1_col1 DEFAULT(0xAA) ); CREATE TABLE dbo.T2 ( keycol INT NOT NULL IDENTITY CONSTRAINT PK_T2 PRIMARY KEY, val INT NOT NULL, othercols BINARY(100) NOT NULL CONSTRAINT DFT_T2_col1 DEFAULT(0xBB) );

Vous utilisez ensuite le code suivant pour remplir les tableaux avec de petits ensembles d'exemples de données afin de vérifier l'exactitude de vos solutions :

 TRUNCATE TABLE dbo.T1 ; TRUNCATE TABLE dbo.T2 ; INSÉRER DANS dbo.T1 (val) VALEURS(1),(1),(3),(3),(5),(8),(13),(16),(18),(20),( 21); INSÉRER DANS dbo.T2 (val) VALEURS(2),(2),(7),(3),(3),(11),(11),(13),(17),(19); 

 Rappelez-vous que le défi consistait à faire correspondre à chaque ligne de T1 la ligne de T2 où la différence absolue entre T2.val et T1.val est la plus faible. En cas d'égalité, vous êtes censé utiliser l'ordre croissant val, keycol comme critère de départage. 
 

 Voici le résultat souhaité pour les exemples de données donnés :
 
 keycol1 val1 othercols1 keycol2 val2 othercols2 ----------- ----------- ---------- --------- -- ----------- ---------- 1 1 0xAA 1 2 0xBB 2 1 0xAA 1 2 0xBB 3 3 0xAA 4 3 0xBB 4 3 0xAA 4 3 0xBB 5 5 0xAA 4 3 0xBB 6 8 0xAA 3 7 0xBB 7 13 0xAA 8 13 0xBB 8 16 0xAA 9 17 0xBB 9 18 0xAA 9 17 0xBB 10 20 0xAA 10 19 0xBB 11 21 0xAA 10 19 0xBB
 

 Pour vérifier les performances de vos solutions, vous avez besoin d'ensembles plus importants d'échantillons de données. Vous créez d'abord la fonction d'assistance GetNums, qui génère une séquence d'entiers dans une plage demandée, en utilisant le code suivant :
 
 SUPPRIMER LA FONCTION SI EXISTE dbo.GetNums ; ALLER CRÉER OU MODIFIER LA FONCTION dbo.GetNums(@low AS BIGINT, @high AS BIGINT) RETURNS TABLE AS RETURN WITH L0 AS (SELECT c FROM (SELECT 1 UNION ALL SELECT 1) AS D(c)), L1 AS (SELECT 1 AS c FROM L0 AS A CROSS JOIN L0 AS B), L2 AS (SELECT 1 AS c FROM L1 AS A CROSS JOIN L1 AS B), L3 AS (SELECT 1 AS c FROM L2 AS A CROSS JOIN L2 AS B), L4 AS (SELECT 1 AS c FROM L3 AS A CROSS JOIN L3 AS B), L5 AS (SELECT 1 AS c FROM L4 AS A CROSS JOIN L4 AS B), Nums AS (SELECT ROW_NUMBER() OVER(ORDER BY (SELECT NULL)) ) AS rownum FROM L5) SELECT TOP(@high - @low + 1) @low + rownum - 1 AS n FROM Nums ORDER BY rownum ; ALLER
 

 Vous remplissez ensuite T1 et T2 à l'aide du code suivant, en ajustant les paramètres indiquant les nombres de lignes et les valeurs maximales en fonction de vos besoins :
 
 DECLARE @numrowsT1 AS INT =1000000, @maxvalT1 AS INT =10000000, @numrowsT2 AS INT =1000000, @maxvalT2 AS INT =10000000 ; TRUNCATE TABLE dbo.T1 ; TRUNCATE TABLE dbo.T2 ; INSERT INTO dbo.T1 WITH(TABLOCK) (val) SELECT ABS(CHECKSUM(NEWID())) % @maxvalT1 + 1 AS val FROM dbo.GetNums(1, @numrowsT1) AS Nums ; INSERT INTO dbo.T2 WITH(TABLOCK) (val) SELECT ABS(CHECKSUM(NEWID())) % @maxvalT2 + 1 AS val FROM dbo.GetNums(1, @numrowsT2) AS Nums ;
 

 Dans cet exemple, vous remplissez les tables avec 1 000 000 de lignes chacune, avec des valeurs comprises entre 1 et 10 000 000 dans la colonne val (faible densité).
 
Solution 3, en utilisant un curseur et une variable de table sur disque
 

 Une solution itérative efficace pour notre défi de correspondance la plus proche est basée sur un algorithme similaire à l'algorithme de jointure Merge. L'idée est d'appliquer une seule passe ordonnée contre chaque table à l'aide de curseurs, en évaluant les éléments de classement et de départage à chaque tour pour décider de quel côté avancer et en faisant correspondre les lignes en cours de route. 
 

 La passe ordonnée sur chaque table bénéficiera certainement de la prise en charge des index, mais l'implication de ne pas en avoir est qu'un tri explicite aura lieu. Cela signifie que la partie tri subira une mise à l'échelle n log n, mais c'est beaucoup moins sévère que la mise à l'échelle quadratique que vous obtenez de la solution 2 dans des circonstances similaires.
 

 De plus, les performances des solutions 1 et 2 ont été affectées par la densité de la colonne val. Avec une densité plus élevée, le plan appliquait moins de reliures. Inversement, étant donné que les solutions itératives n'effectuent qu'une seule passe sur chacune des entrées, la densité de la colonne val n'est pas un facteur affectant les performances.
 

 Utilisez le code suivant pour créer des index de support :
 
 CREATE INDEX idx_val_key ON dbo.T1(val, keycol) INCLUDE(othercols); CREATE INDEX idx_val_key ON dbo.T2(val, keycol) INCLUDE(othercols);
 

 Assurez-vous de tester les solutions avec et sans ces index.
 

 Voici le code complet de la solution 3 :
 
 SET NOCOUNT ON ; COMMENCER TRAN ; DÉCLARER @keycol1 AS INT, @val1 AS INT, @othercols1 AS BINARY(100), @keycol2 AS INT, @val2 AS INT, @othercols2 AS BINARY(100), @prevkeycol2 AS INT, @prevval2 AS INT, @prevothercols2 AS BINAIRE(100), @C1 COMME CURSEUR, @C2 COMME CURSEUR, @C1fetch_status COMME INT, @C2fetch_status COMME INT ; DECLARE @Result AS TABLE ( keycol1 INT NOT NULL PRIMARY KEY, val1 INT NOT NULL, othercols1 BINARY(100) NOT NULL, keycol2 INT NULL, val2 INT NULL, othercols2 BINARY(100) NULL ); SET @C1 =CURSOR FORWARD_ONLY STATIC READ_ONLY FOR SELECT keycol, val, othercols FROM dbo.T1 ORDER BY val, keycol; SET @C2 =CURSOR FORWARD_ONLY STATIC READ_ONLY FOR SELECT keycol, val, othercols FROM dbo.T2 ORDER BY val, keycol; OUVERT @C1 ; OUVERT @C2 ; FETCH NEXT FROM @C2 INTO @keycol2, @val2, @othercols2 ; SET @C2fetch_status =@@fetch_status ; SELECT @prevkeycol2 =@keycol2, @prevval2 =@val2, @prevothercols2 =@othercols2 ; FETCH NEXT FROM @C1 INTO @keycol1, @val1, @othercols1 ; SET @C1fetch_status =@@fetch_status ; TANT QUE @C1fetch_status =0 COMMENCEZ SI @val1 <=@val2 OU @C2fetch_status <> 0 COMMENCEZ SI ABS(@val1 - @val2)  @prevval2 SELECT @prevkeycol2 =@keycol2, @prevval2 =@val2, @prevothercols2 =@othercols2 ; FETCH NEXT FROM @C2 INTO @keycol2, @val2, @othercols2 ; SET @C2fetch_status =@@fetch_status ; FINIR; FINIR; SELECT keycol1, val1, SUBSTRING(othercols1, 1, 1) AS othercols1, keycol2, val2, SUBSTRING(othercols2, 1, 1) AS othercols2 FROM @Result ; COMMIT TRAN ;
 

 Le code utilise une variable de table appelée @Result pour stocker les correspondances et les renvoie éventuellement en interrogeant la variable de table. Notez que le code effectue le travail en une seule transaction pour réduire la journalisation. 
 

 Le code utilise des variables de curseur appelées @C1 et @C2 pour parcourir les lignes dans T1 et T2, respectivement, dans les deux cas classés par val, keycol. Les variables locales sont utilisées pour stocker les valeurs de ligne actuelles de chaque curseur (@keycol1, @val1 et @othercols1 pour @C1, et @keycol2, @val2 et @othercols2 pour @C2). Des variables locales supplémentaires stockent les valeurs de ligne précédentes de @C2 (@prevkeycol2, @prevval2 et @prevothercols2). Les variables @C1fetch_status et @C2fetch_status contiennent le statut de la dernière récupération à partir du curseur respectif.
 

 Après avoir déclaré et ouvert les deux curseurs, le code récupère une ligne de chaque curseur dans les variables locales respectives et stocke initialement les valeurs de ligne actuelles de @C2 également dans les variables de ligne précédentes. Le code entre ensuite dans une boucle qui continue de s'exécuter pendant que la dernière extraction de @C1 a réussi (@C1fetch_status =0). Le corps de la boucle applique le pseudo-code suivant à chaque tour :
 
 Si @val1 <=@val2 ou a atteint la fin de @C2 Begin Si la différence absolue entre @val1 et @val2 est inférieure à celle entre @val1 et @prevval2 Ajouter une ligne à @Result avec les valeurs de ligne actuelles de @C1 et de la ligne actuelle valeurs de @C2 Sinon Ajouter une ligne à @Result avec les valeurs de la ligne actuelle de @C1 et les valeurs de la ligne précédente de @C2 Extraire la ligne suivante de @C1 Fin Sinon si la dernière extraction de @C2 a réussi Commencer Si @val2> @prevval2 Définir les variables en attente Valeurs de la ligne précédente de @C2 en valeurs des variables de la ligne actuelle Extraire la ligne suivante de @C2 End
 

 Le code interroge ensuite simplement la variable de table @Result pour renvoyer toutes les correspondances.
 

 En utilisant les grands ensembles d'échantillons de données (1 000 000 de lignes dans chaque table), avec une indexation optimale en place, cette solution a pris 38 secondes pour se terminer sur mon système et a effectué 28 240 lectures logiques. Bien entendu, la mise à l'échelle de cette solution est alors linéaire. Sans indexation optimale, il a fallu 40 secondes pour terminer (seulement 2 secondes supplémentaires !) et effectué 29 519 lectures logiques. La partie tri de cette solution a une mise à l'échelle n log n.
 
Solution 4, en utilisant un curseur et une variable de table optimisée en mémoire
 

 Pour tenter d'améliorer les performances de l'approche itérative, vous pouvez essayer de remplacer l'utilisation de la variable de table basée sur le disque par une variable optimisée en mémoire. Étant donné que la solution consiste à écrire 1 000 000 de lignes dans la variable de table, cela pourrait entraîner une amélioration non négligeable. 
 

 Tout d'abord, vous devez activer l'OLTP en mémoire dans la base de données en créant un groupe de fichiers marqué comme CONTAINS MEMORY_OPTIMIZED_DATA, et à l'intérieur un conteneur qui pointe vers un dossier dans le système de fichiers. En supposant que vous ayez créé à l'avance un dossier parent appelé C:\IMOLTP\, utilisez le code suivant pour appliquer ces deux étapes :
 
 ALTER DATABASE testdb ADD FILEGROUP testdb_MO CONTAINS MEMORY_OPTIMIZED_DATA ; ALTER DATABASE testdb ADD FILE ( NAME =testdb_dir, FILENAME ='C:\IMOLTP\testdb_dir' ) TO FILEGROUP testdb_MO;
 

 L'étape suivante consiste à créer un type de table optimisé en mémoire comme modèle pour notre variable de table en exécutant le code suivant :
 
 DROP TYPE IF EXISTS dbo.TYPE_closestmatch; GO CREATE TYPE dbo.TYPE_closestmatch AS TABLE ( keycol1 INT NOT NULL PRIMARY KEY NONCLUSTERED, val1 INT NOT NULL, othercols1 BINARY(100) NOT NULL, keycol2 INT NULL, val2 INT NULL, othercols2 BINARY(100) NULL ) WITH (MEMORY_OPTIMIZED =ON );
 

 Ensuite, au lieu de la déclaration d'origine de la variable de table @Result, vous utiliseriez le code suivant :
 
 DÉCLARER @Result AS dbo.TYPE_closestmatch ;
 

 Voici le code complet de la solution :
 
 SET NOCOUNT ON ; UTILISER testdb ; COMMENCER TRAN ; DÉCLARER @keycol1 AS INT, @val1 AS INT, @othercols1 AS BINARY(100), @keycol2 AS INT, @val2 AS INT, @othercols2 AS BINARY(100), @prevkeycol2 AS INT, @prevval2 AS INT, @prevothercols2 AS BINAIRE(100), @C1 COMME CURSEUR, @C2 COMME CURSEUR, @C1fetch_status COMME INT, @C2fetch_status COMME INT ; DECLARE @Result AS dbo.TYPE_closestmatch ; SET @C1 =CURSOR FORWARD_ONLY STATIC READ_ONLY FOR SELECT keycol, val, othercols FROM dbo.T1 ORDER BY val, keycol; SET @C2 =CURSOR FORWARD_ONLY STATIC READ_ONLY FOR SELECT keycol, val, othercols FROM dbo.T2 ORDER BY val, keycol; OUVERT @C1 ; OUVERT @C2 ; FETCH NEXT FROM @C2 INTO @keycol2, @val2, @othercols2 ; SET @C2fetch_status =@@fetch_status ; SELECT @prevkeycol2 =@keycol2, @prevval2 =@val2, @prevothercols2 =@othercols2 ; FETCH NEXT FROM @C1 INTO @keycol1, @val1, @othercols1 ; SET @C1fetch_status =@@fetch_status ; TANT QUE @C1fetch_status =0 COMMENCEZ SI @val1 <=@val2 OU @C2fetch_status <> 0 COMMENCEZ SI ABS(@val1 - @val2)  @prevval2 SELECT @prevkeycol2 =@keycol2, @prevval2 =@val2, @prevothercols2 =@othercols2 ; FETCH NEXT FROM @C2 INTO @keycol2, @val2, @othercols2 ; SET @C2fetch_status =@@fetch_status ; FINIR; FINIR; SELECT keycol1, val1, SUBSTRING(othercols1, 1, 1) AS othercols1, keycol2, val2, SUBSTRING(othercols2, 1, 1) AS othercols2 FROM @Result ; COMMIT TRAN ;
 

 Avec l'indexation optimale en place, cette solution a pris 27 secondes pour se terminer sur ma machine (contre 38 secondes avec la variable de table basée sur le disque), et sans indexation optimale, il a fallu 29 secondes pour se terminer (contre 40 secondes). Cela représente une réduction de près de 30 % du temps d'exécution.
 
Solution 5, en utilisant SQL CLR
 

 Une autre façon d'améliorer encore les performances de l'approche itérative consiste à implémenter la solution à l'aide de SQL CLR, étant donné que la majeure partie de la surcharge de la solution T-SQL est due aux inefficacités de la récupération du curseur et des boucles dans T-SQL.
 

 Voici le code de solution complet implémentant le même algorithme que j'ai utilisé dans les solutions 3 et 4 avec C#, en utilisant des objets SqlDataReader au lieu de curseurs T-SQL :
 
 en utilisant le système ; en utilisant System.Data ; en utilisant System.Data.SqlClient ; en utilisant System.Data.SqlTypes ; en utilisant Microsoft.SqlServer.Server ; public partial class ClosestMatch { [SqlProcedure] public static void GetClosestMatches() { using (SqlConnection conn =new SqlConnection("data source=MyServer\\MyInstance;Database=testdb;Trusted_Connection=True;MultipleActiveResultSets=true;")) { SqlCommand comm1 =new SqlCommand(); SqlCommand comm2 =new SqlCommand(); comm1.Connexion =conn ; comm2.Connexion =conn ; comm1.CommandText ="SELECT keycol, val, othercols FROM dbo.T1 ORDER BY val, keycol;"; comm2.CommandText ="SELECT keycol, val, othercols FROM dbo.T2 ORDER BY val, keycol;"; SqlMetaData[] colonnes =nouveau SqlMetaData[6] ; colonnes[0] =new SqlMetaData("keycol1", SqlDbType.Int); colonnes[1] =new SqlMetaData("val1", SqlDbType.Int); colonnes[2] =new SqlMetaData("othercols1", SqlDbType.Binary, 100); colonnes[3] =new SqlMetaData("keycol2", SqlDbType.Int); colonnes[4] =new SqlMetaData("val2", SqlDbType.Int); colonnes[5] =new SqlMetaData("othercols2", SqlDbType.Binary, 100); Enregistrement SqlDataRecord =nouveau SqlDataRecord (colonnes); SqlContext.Pipe.SendResultsStart(enregistrement); conn.Open(); SqlDataReader lecteur1 =comm1.ExecuteReader(); SqlDataReader lecteur2 =comm2.ExecuteReader(); SqlInt32 keycol1 =SqlInt32.Null ; SqlInt32 val1 =SqlInt32.Null ; SqlBinary othercols1 =SqlBinary.Null ; SqlInt32 keycol2 =SqlInt32.Null ; SqlInt32 val2 =SqlInt32.Null ; SqlBinary othercols2 =SqlBinary.Null ; SqlInt32 prevkeycol2 =SqlInt32.Null ; SqlInt32 prevval2 =SqlInt32.Null ; SqlBinary prevothercols2 =SqlBinary.Null ; booléen reader2foundrow =reader2.Read(); si (reader2foundrow) { keycol2 =reader2.GetSqlInt32(0); val2 =lecteur2.GetSqlInt32(1); othercols2 =reader2.GetSqlBinary(2); prevkeycol2 =keycol2 ; prevval2 =val2 ; prevothercols2 =othercols2 ; } Boolean reader1foundrow =reader1.Read(); si (reader1foundrow) { keycol1 =reader1.GetSqlInt32(0); val1 =lecteur1.GetSqlInt32(1); othercols1 =lecteur1.GetSqlBinary(2); } while (reader1foundrow) { if (val1 <=val2 || !reader2foundrow) { if (Math.Abs((int)(val1 - val2))  prevval2) { prevkeycol2 =keycol2; prevval2 =val2 ; prevothercols2 =othercols2 ; } reader2foundrow =reader2.Read(); si (reader2foundrow) { keycol2 =reader2.GetSqlInt32(0); val2 =lecteur2.GetSqlInt32(1); othercols2 =reader2.GetSqlBinary(2); } } } SqlContext.Pipe.SendResultsEnd(); } } } 

 Pour vous connecter à la base de données, vous devez normalement utiliser l'option "context connection=true" au lieu d'une chaîne de connexion complète. Malheureusement, cette option n'est pas disponible lorsque vous devez travailler avec plusieurs ensembles de résultats actifs. Notre solution émulant le travail parallèle avec deux curseurs à l'aide de deux objets SqlDataReader, et donc vous avez besoin d'une chaîne de connexion complète, avec l'option MultipleActiveResultSets=true. Voici la chaîne de connexion complète :
 
 "data source=MyServer\\MyInstance;Database=testdb;Trusted_Connection=True;MultipleActiveResultSets=true ;"
 

 Bien sûr, dans votre cas, vous devrez remplacer MyServer\\MyInstance par les noms de votre serveur et de votre instance (le cas échéant).
 

 De plus, le fait que vous n'ayez pas utilisé "context connection=true" plutôt une chaîne de connexion explicite signifie que l'assembly doit accéder à une ressource externe et donc être approuvé. Normalement, vous y parviendrez en le signant avec un certificat ou une clé asymétrique qui a une connexion correspondante avec la bonne autorisation, ou en le mettant sur liste blanche à l'aide de la procédure sp_add_trusted_assembly. Par souci de simplicité, je vais définir l'option de base de données TRUSTWORTHY sur ON et spécifier le jeu d'autorisations EXTERNAL_ACCESS lors de la création de l'assembly. Le code suivant déploie la solution dans la base de données :
 
 EXEC sys.sp_configure 'avancé', 1; RECONFIGURER ; EXEC sys.sp_configure 'clr activé', 1; EXEC sys.sp_configure 'clr sécurité stricte', 0; RECONFIGURER ; EXEC sys.sp_configure 'avancé', 0; RECONFIGURER ; ALTER DATABASE testdb SET TRUSTWORTHY ON ; UTILISER testdb ; ANNULER LA PROCÉDURE SI EXISTE dbo.GetClosestMatches ; ABANDONNER L'ASSEMBLAGE SI EXISTE ClosestMatch ; CRÉER L'ASSEMBLAGE ClosestMatch À PARTIR DE 'C:\ClosestMatch\ClosestMatch\bin\Debug\ClosestMatch.dll' AVEC PERMISSION_SET =EXTERNAL_ACCESS ; ALLER CRÉER LA PROCÉDURE dbo.GetClosestMatches AS NOM EXTERNE ClosestMatch.ClosestMatch.GetClosestMatches ;
 

 Le code active CLR dans l'instance, désactive l'option de sécurité stricte CLR, définit l'option de base de données TRUSTWORTHY sur ON, crée l'assembly et crée la procédure GetClosestMatches.
 

 Utilisez le code suivant pour tester la procédure stockée :
 
 EXEC dbo.GetClosestMatches ;
 

 La solution CLR a pris 8 secondes pour se terminer sur mon système avec une indexation optimale et 9 secondes sans. C'est une amélioration des performances assez impressionnante par rapport à toutes les autres solutions, à la fois relationnelles et itératives.
 
Conclusion
 

 Les solutions itératives sont généralement mal vues dans la communauté SQL car elles ne suivent pas le modèle relationnel. La réalité est que parfois vous n'êtes pas en mesure de créer des solutions relationnelles performantes et la performance est une priorité. En utilisant une approche itérative, vous n'êtes pas limité aux algorithmes auxquels l'optimiseur SQL Server a accès, mais vous pouvez plutôt implémenter n'importe quel algorithme que vous aimez. Comme démontré dans cet article, en utilisant un algorithme de type fusion, vous avez pu accomplir la tâche avec une seule passe ordonnée sur chacune des entrées. En utilisant des curseurs T-SQL et une variable de table sur disque, vous avez obtenu des performances et une mise à l'échelle raisonnables. Vous avez pu améliorer les performances d'environ 30 % en passant à une variable de table optimisée en mémoire, et bien plus encore en utilisant SQL CLR.