Karen Ly, analyste junior des titres à revenu fixe chez RBC, m'a lancé un défi T-SQL qui consiste à trouver la correspondance la plus proche, plutôt que de trouver une correspondance exacte. Dans cet article, je couvre une forme généralisée et simpliste du défi.

Le défi

Le défi consiste à faire correspondre les lignes de deux tables, T1 et T2. Utilisez le code suivant pour créer un exemple de base de données appelée testdb, et à l'intérieur de celle-ci les tables T1 et T2 :

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

Comme vous pouvez le voir, T1 et T2 ont une colonne numérique (de type INT dans cet exemple) appelée val. Le défi consiste à 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é (plusieurs lignes correspondantes dans T2), faites correspondre la ligne du haut en fonction de l'ordre croissant val, keycol. Autrement dit, la ligne avec la valeur la plus basse dans la colonne val, et si vous avez toujours des liens, la ligne avec la valeur keycol la plus basse. Le tie-break est utilisé pour garantir le déterminisme.

Utilisez le code suivant pour remplir T1 et T2 avec de petits ensembles d'échantillons de données afin de pouvoir 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); 

 Vérifiez le contenu de T1 :
 
 SELECT keycol, val, SUBSTRING(othercols, 1, 1) AS othercols FROM dbo.T1 ORDER BY val, keycol;
 

 Ce code génère la sortie suivante :
 
 keycol val othercols ----------- ----------- --------- 1 1 0xAA 2 1 0xAA 3 3 0xAA 4 3 0xAA 5 5 0xAA 6 8 0xAA 7 13 0xAA 8 16 0xAA 9 18 0xAA 10 20 0xAA 11 21 0xAA
 

 Vérifiez le contenu de T2 :
 
 SELECT keycol, val, SUBSTRING(othercols, 1, 1) AS othercols FROM dbo.T2 ORDER BY val, keycol;
 

 Ce code génère la sortie suivante :
 
 keycol val othercols ----------- ----------- --------- 1 2 0xBB 2 2 0xBB 4 3 0xBB 5 3 0xBB 3 7 0xBB 6 11 0xBB 7 11 0xBB 8 13 0xBB 9 17 0xBB 10 19 0xBB
 

 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
 

 Avant de commencer à travailler sur le défi, examinez le résultat souhaité et assurez-vous de comprendre la logique de correspondance, y compris la logique de départage. Par exemple, considérons la ligne dans T1 où keycol est 5 et val est 5. Cette ligne a plusieurs correspondances les plus proches dans T2 :
 
 keycol val othercols ----------- ----------- --------- 4 3 0xBB 5 3 0xBB 3 7 0xBB
 

 Dans toutes ces lignes, la différence absolue entre T2.val et T1.val (5) est de 2. En utilisant la logique de départage basée sur l'ordre val croissant, keycol ascendant la ligne la plus haute ici est celle où val est 3 et keycol est 4. 
 

 Vous utiliserez les petits ensembles d'exemples de données pour vérifier la validité de vos solutions. Pour vérifier les performances, vous avez besoin d'ensembles plus grands. Utilisez le code suivant pour créer une fonction d'assistance appelée GetNums, qui génère une séquence d'entiers dans une plage demandée :
 
 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
 

 Utilisez le code suivant pour remplir T1 et T2 avec de grands ensembles d'exemples de données :
 
 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 ;
 

 Les variables @numrowsT1 et @numrowsT2 contrôlent le nombre de lignes avec lesquelles vous souhaitez que les tables soient remplies. Les variables @maxvalT1 et @maxvalT2 contrôlent la plage de valeurs distinctes dans la colonne val et affectent donc la densité de la colonne. Le code ci-dessus remplit les tables avec 1 000 000 lignes chacune et utilise la plage de 1 à 10 000 000 pour la colonne val dans les deux tables. Il en résulte une faible densité dans la colonne (grand nombre de valeurs distinctes, avec un petit nombre de doublons). L'utilisation de valeurs maximales inférieures entraînera une densité plus élevée (plus petit nombre de valeurs distinctes, et donc plus de doublons).
 
Solution 1, en utilisant une sous-requête TOP
 

 La solution la plus simple et la plus évidente est probablement celle qui interroge T1, et l'utilisation de l'opérateur CROSS APPLY applique une requête avec un filtre TOP (1), en ordonnant les lignes par la différence absolue entre T1.val et T2.val, en utilisant T2.val , T2.keycol comme condition de départage. Voici le code de la solution :
 
 SELECT T1.keycol AS keycol1, T1.val AS val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1 ) AS othercols2 FROM dbo.T1 CROSS APPLY ( SELECT TOP (1) T2.* FROM dbo.T2 ORDER BY ABS(T2.val - T1.val), T2.val, T2.keycol ) AS A;
 

 N'oubliez pas qu'il y a 1 000 000 de lignes dans chacune des tables. Et la densité de la colonne val est faible dans les deux tableaux. Malheureusement, puisqu'il n'y a pas de prédicat de filtrage dans la requête appliquée et que le classement implique une expression qui manipule les colonnes, il n'y a aucun potentiel ici pour créer des index de support. Cette requête génère le plan de la figure 1. 
 

 Figure 1 :Planifier la solution 1 
 

 L'entrée externe de la boucle analyse 1 000 000 lignes à partir de T1. L'entrée interne de la boucle effectue une analyse complète de T2 et un tri TopN pour chaque valeur T1.val distincte. Dans notre plan, cela se produit 998 657 fois puisque nous avons une très faible densité. Il place les lignes dans un spool d'index, indexé par T1.val, afin de pouvoir les réutiliser pour les occurrences en double des valeurs T1.val, mais nous avons très peu de doublons. Ce plan a une complexité quadratique. Entre toutes les exécutions attendues de la branche interne de la boucle, on s'attend à ce qu'elle traite près d'un billion de lignes. Lorsque vous parlez d'un grand nombre de lignes à traiter par une requête, une fois que vous commencez à mentionner des milliards de lignes, les gens savent déjà que vous avez affaire à une requête coûteuse. Normalement, les gens ne prononcent pas des termes comme des billions, à moins qu'ils ne discutent de la dette nationale américaine ou des krachs boursiers. Vous ne traitez généralement pas ces nombres dans le contexte du traitement des requêtes. Mais les plans avec une complexité quadratique peuvent rapidement se retrouver avec de tels chiffres. L'exécution de la requête dans SSMS avec Inclure les statistiques de requête en direct activée a pris 39,6 secondes pour traiter seulement 100 lignes de T1 sur mon ordinateur portable. Cela signifie que cette requête devrait prendre environ 4,5 jours. La question est la suivante :êtes-vous vraiment attiré par les plans de requête en direct ? Cela pourrait être un record Guinness intéressant à essayer d'établir.
 
Solution 2, en utilisant deux sous-requêtes TOP
 

 En supposant que vous recherchiez une solution qui prend quelques secondes, et non des jours, voici une idée. Dans l'expression de table appliquée, unifiez deux requêtes internes TOP (1) :une filtrant une ligne où T2.val  =T1.val (ordonné par T2.val, T2.keycol). Il est facile de créer des index pour prendre en charge de telles requêtes en activant une recherche sur une seule ligne. Toujours dans l'expression de table appliquée, utilisez une requête TOP externe (1) sur le résultat à deux lignes, en fonction de l'ordre ABS(D.val – T1.val), D.val, D.keycol. Un tri TopN sera impliqué, mais il sera appliqué à deux lignes à la fois.
 

 Voici les index recommandés pour prendre en charge cette solution :
 
 CREATE INDEX idx_val_key ON dbo.T1(val, keycol) INCLUDE(othercols); CREATE INDEX idx_val_key ON dbo.T2(val, keycol) INCLUDE(othercols); CREATE INDEX idx_valD_key ON dbo.T2(val DESC, keycol) INCLUDE(othercols);
 

 Voici le code complet de la solution :
 
 SELECT T1.keycol AS keycol1, T1.val AS val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1 ) AS othercols2 FROM dbo.T1 CROSS APPLY ( SELECT TOP (1) D.* FROM ( SELECT TOP (1) * FROM dbo.T2 WHERE T2.val =T1.val ORDER BY T2.val, T2.keycol ) AS D ORDER BY ABS(D.val - T1.val), D.val, D. keycol ) AS A;
 

 N'oubliez pas que nous avons 1 000 000 de lignes dans chaque table, la colonne val ayant des valeurs comprises entre 1 et 10 000 000 (faible densité) et des index optimaux en place. 
 

 Le plan de cette requête est illustré à la figure 2.
 

 Figure 2 :Planifier la solution 2 
 

 Observez l'utilisation optimale des index sur T2, résultant en un plan avec une mise à l'échelle linéaire. Ce plan utilise un spool d'index de la même manière que le plan précédent, c'est-à-dire pour éviter de répéter le travail dans la branche interne de la boucle pour les valeurs T1.val en double. Voici les statistiques de performances que j'ai obtenues pour l'exécution de cette requête sur mon système :
 
Elapsed :27,7 secondes, CPU :27,6 secondes, lectures logiques :17 304 674
 
Solution 2, avec mise en file d'attente désactivée
 

 Vous ne pouvez pas vous empêcher de vous demander si la bobine d'index est vraiment bénéfique ici. Le but est d'éviter de répéter le travail pour les valeurs T1.val en double, mais dans une situation comme la nôtre où nous avons une très faible densité, il y a très peu de doublons. Cela signifie que le travail impliqué dans la mise en file d'attente est très probablement plus important que la simple répétition du travail pour les doublons. Il existe un moyen simple de vérifier cela :en utilisant l'indicateur de trace 8690, vous pouvez désactiver la mise en file d'attente dans le plan, comme suit :
 
 SELECT T1.keycol AS keycol1, T1.val AS val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1 ) AS othercols2 FROM dbo.T1 CROSS APPLY ( SELECT TOP (1) D.* FROM ( SELECT TOP (1) * FROM dbo.T2 WHERE T2.val =T1.val ORDER BY T2.val, T2.keycol ) AS D ORDER BY ABS(D.val - T1.val), D.val, D. keycol ) EN OPTION(QUERYTRACEON 8690);
 

 J'ai obtenu le plan illustré à la figure 3 pour cette exécution :
 

 Figure 3 :Plan pour la solution 2, avec mise en file d'attente désactivée 
 

 Observez que le spool d'index a disparu, et cette fois la branche interne de la boucle est exécutée 1 000 000 fois. Voici les statistiques de performances que j'ai obtenues pour cette exécution :
 
Elapsed :19,18 secondes, CPU :19,17 secondes, lectures logiques :6 042 148
 

 Cela représente une réduction de 44 % du temps d'exécution. 
 
Solution 2, avec plage de valeurs et indexation modifiées
 

 La désactivation de la mise en file d'attente a beaucoup de sens lorsque vous avez une faible densité dans les valeurs T1.val ; cependant, la mise en file d'attente peut être très bénéfique lorsque vous avez une densité élevée. Par exemple, exécutez le code suivant pour remplir à nouveau T1 et T2 avec un exemple de paramètre de données @maxvalT1 et @maxvalT2 sur 1 000 (1 000 valeurs distinctes maximales) :
 
 DECLARE @numrowsT1 AS INT =1000000, @maxvalT1 AS INT =1000, @numrowsT2 AS INT =1000000, @maxvalT2 AS INT =1000 ; 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 ;
 

 Réexécutez la solution 2, d'abord sans l'indicateur de trace :
 
 SELECT T1.keycol AS keycol1, T1.val AS val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1 ) AS othercols2 FROM dbo.T1 CROSS APPLY ( SELECT TOP (1) D.* FROM ( SELECT TOP (1) * FROM dbo.T2 WHERE T2.val =T1.val ORDER BY T2.val, T2.keycol ) AS D ORDER BY ABS(D.val - T1.val), D.val, D. keycol ) AS A;
 

 Le plan de cette exécution est illustré à la figure 4 :
 

 Figure 4 :Plan pour la solution 2, avec une plage de valeurs de 1 à 1 000 
 

 L'optimiseur a décidé d'utiliser un plan différent en raison de la forte densité dans T1.val. Observez que l'index sur T1 est scanné dans l'ordre des clés. Ainsi, pour chaque première occurrence d'une valeur T1.val distincte, la branche interne de la boucle est exécutée et le résultat est mis en file d'attente dans une file d'attente de table normale (rebind). Ensuite, pour chaque non-première occurrence de la valeur, un rembobinage est appliqué. Avec 1 000 valeurs distinctes, la branche interne n'est exécutée que 1 000 fois. Cela se traduit par d'excellentes statistiques de performances :
 
Elapsed :1,16 s, CPU :1,14 s, lectures logiques :23 278
 

 Essayez maintenant d'exécuter la solution avec la mise en file d'attente désactivée :
 
 SELECT T1.keycol AS keycol1, T1.val AS val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1 ) AS othercols2 FROM dbo.T1 CROSS APPLY ( SELECT TOP (1) D.* FROM ( SELECT TOP (1) * FROM dbo.T2 WHERE T2.val =T1.val ORDER BY T2.val, T2.keycol ) AS D ORDER BY ABS(D.val - T1.val), D.val, D. keycol ) EN OPTION(QUERYTRACEON 8690);
 

 J'ai obtenu le plan illustré à la figure 5.
 

 Figure 5 :Plan pour la solution 2, avec une plage de valeurs comprise entre 1 et 1 000 et la mise en file d'attente désactivée  
 

 Il s'agit essentiellement du même plan illustré précédemment à la figure 3. La branche interne de la boucle est exécutée 1 000 000 fois. Voici les statistiques de performances que j'ai obtenues pour cette exécution :
 
Elapsed :24,5 secondes, CPU :24,2 secondes, lectures logiques :8 012 548
 

 De toute évidence, vous voulez faire attention à ne pas désactiver la mise en file d'attente lorsque vous avez une densité élevée dans T1.val.
 

 La vie est belle lorsque votre situation est suffisamment simple pour que vous puissiez créer des index de support. La réalité est que dans certains cas, en pratique, il y a suffisamment de logique supplémentaire dans la requête, ce qui empêche la possibilité de créer des index de support optimaux. Dans de tels cas, la solution 2 ne fonctionnera pas bien.
 

 Pour démontrer les performances de la solution 2 sans prendre en charge les index, remplissez de nouveau T1 et T2 avec des exemples de paramètres de données @maxvalT1 et @maxvalT2 à 10000000 (plage de valeurs de 1 à 10 M), et supprimez également les index de prise en charge :
 
 SUPPRIMER L'INDEX SI EXISTE idx_val_key ON dbo.T1 ; SUPPRIMER L'INDEX SI EXISTE idx_val_key ON dbo.T2 ; SUPPRIMER L'INDEX SI EXISTE idx_valD_key ON dbo.T2 ; DÉCLARER @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 ;
 

 Réexécutez la solution 2, avec Inclure les statistiques de requête en direct activées dans SSMS :
 
 SELECT T1.keycol AS keycol1, T1.val AS val1, SUBSTRING(T1.othercols, 1, 1) AS othercols1, A.keycol AS keycol2, A.val AS val2, SUBSTRING(A.othercols, 1, 1 ) AS othercols2 FROM dbo.T1 CROSS APPLY ( SELECT TOP (1) D.* FROM ( SELECT TOP (1) * FROM dbo.T2 WHERE T2.val =T1.val ORDER BY T2.val, T2.keycol ) AS D ORDER BY ABS(D.val - T1.val), D.val, D. keycol ) AS A;
 

 J'ai obtenu le plan illustré à la figure 6 pour cette requête :
 

 Figure 6 :Plan pour la solution 2, sans indexation, avec une plage de valeurs comprise entre 1 et 1 000 000  
 

 Vous pouvez voir un schéma très similaire à celui illustré précédemment dans la figure 1, mais cette fois le plan analyse T2 deux fois par valeur T1.val distincte. Encore une fois, la complexité du plan devient quadratique. L'exécution de la requête dans SSMS avec Inclure les statistiques de requête en direct activée a pris 49,6 secondes pour traiter 100 lignes de T1 sur mon ordinateur portable, ce qui signifie que cette requête devrait prendre environ 5,7 jours. Cela pourrait bien sûr signifier de bonnes nouvelles si vous essayez de battre le record du monde Guinness pour la surveillance excessive d'un plan de requête en direct.
 
Conclusion
 

 J'aimerais remercier Karen Ly de RBC de m'avoir présenté ce beau défi de match le plus proche. J'ai été assez impressionné par son code pour le gérer, qui comprenait beaucoup de logique supplémentaire spécifique à son système. Dans cet article, j'ai montré des solutions raisonnablement performantes lorsque vous êtes en mesure de créer des index de support optimaux. Mais comme vous avez pu le voir, dans les cas où ce n'est pas une option, évidemment les temps d'exécution que vous obtenez sont abyssaux. Pouvez-vous penser à des solutions qui fonctionneront bien même sans index de support optimaux ? A suivre…