Ceci fait partie d'une série d'opérateurs problématiques internes de SQL Server. Pour lire le premier message, cliquez ici.
SQL Server existe depuis plus de 30 ans, et je travaille avec SQL Server depuis presque aussi longtemps. J'ai vu beaucoup de changements au fil des années (et des décennies !) et des versions de cet incroyable produit. Dans ces articles, je vais partager avec vous comment j'examine certaines des fonctionnalités ou certains aspects de SQL Server, parfois avec un peu de perspective historique.
La dernière fois, j'ai parlé d'une opération d'analyse dans un plan de requête SQL Server en tant qu'opérateur potentiellement problématique dans les diagnostics SQL Server. Bien que les analyses soient fréquemment utilisées uniquement parce qu'il n'y a pas d'index utile, il y a des moments où l'analyse est en fait un meilleur choix qu'une opération de recherche d'index.
Dans cet article, je vais vous parler d'une autre famille d'opérateurs parfois considérée comme problématique :le hachage. Le hachage est un algorithme de traitement de données très connu qui existe depuis de nombreuses décennies. Je l'ai étudié dans mes cours sur les structures de données lorsque j'étudiais pour la première fois l'informatique à l'université. Si vous souhaitez des informations générales sur le hachage et les fonctions de hachage, vous pouvez consulter cet article sur Wikipedia. Cependant, SQL Server n'a pas ajouté le hachage à son répertoire d'options de traitement des requêtes avant SQL Server 7. (En passant, je mentionnerai que SQL Server a utilisé le hachage dans certains de ses propres algorithmes de recherche internes. Comme le mentionne l'article de Wikipedia , le hachage utilise une fonction spéciale pour mapper des données de taille arbitraire à des données de taille fixe. SQL a utilisé le hachage comme technique de recherche pour mapper chaque page d'une base de données de taille arbitraire à un tampon en mémoire, qui est de taille fixe. En fait , il y avait une option pour sp_configure appelés "seaux de hachage", qui vous permettaient de contrôler le nombre de compartiments utilisés pour le hachage des pages de la base de données dans les mémoires tampons.)
Qu'est-ce que le hachage ?
Le hachage est une technique de recherche qui ne nécessite pas que les données soient ordonnées. SQL Server peut l'utiliser pour les opérations JOIN, les opérations d'agrégation (DISTINCT ou GROUP BY) ou les opérations UNION. Ce que ces trois opérations ont en commun, c'est que lors de l'exécution, le moteur de requête recherche des valeurs correspondantes. Dans une jointure, nous voulons trouver des lignes dans une table (ou un ensemble de lignes) qui ont des valeurs correspondantes avec des lignes dans une autre. (Et oui, je suis au courant des jointures qui ne comparent pas les lignes en fonction de l'égalité, mais ces non-équijointures ne sont pas pertinentes pour cette discussion.) Pour GROUP BY, nous trouvons des valeurs correspondantes à inclure dans le même groupe, et pour UNION et DISTINCT, nous recherchons les valeurs correspondantes afin de les exclure. (Oui, je sais que UNION ALL est une exception.)
Avant SQL Server 7, le seul moyen pour ces opérations de trouver facilement des valeurs correspondantes était de trier les données. Ainsi, s'il n'y avait pas d'index existant qui maintenait les données dans un ordre trié, le plan de requête ajouterait une opération SORT au plan. Le hachage organise vos données pour une recherche efficace en plaçant toutes les lignes qui ont le même résultat de la fonction de hachage interne dans le même "seau de hachage".
Pour une explication plus détaillée de l'opération JOIN de hachage de SQL Server, y compris des diagrammes, consultez ce billet de blog de SQL Shack.
Une fois que le hachage est devenu une option, SQL Server n'a pas complètement ignoré la possibilité de trier les données avant de les joindre ou de les agréger, mais c'est simplement devenu une possibilité que l'optimiseur doit envisager. En général, cependant, si vous essayez de joindre, d'agréger ou d'effectuer UNION sur des données non triées, l'optimiseur choisira généralement une opération de hachage. Tant de gens supposent qu'un HASH JOIN (ou une autre opération HASH) dans un plan signifie que vous n'avez pas les index appropriés et que vous devez créer des index appropriés pour éviter l'opération de hachage.
Prenons un exemple. Je vais d'abord créer deux tables non indexées.
USE AdventureWorks2016 GO DROP TABLE IF EXISTS Details;
GO
SELECT * INTO Details FROM Sales.SalesOrderDetail;
GO
DROP TABLE IF EXISTS Headers;
GO
SELECT * INTO Headers FROM Sales.SalesOrderHeader;
GO
Now, I’ll join these two tables together and filter the rows in the Details table:
SELECT *
FROM Details d JOIN Headers h
ON d.SalesOrderID = h.SalesOrderID
WHERE SalesOrderDetailID < 100;
Quest Spotlight Tuning Pack ne semble pas indiquer que la jointure de hachage est un problème. Il ne met en évidence que les deux balayages de table.
Les suggestions recommandent de créer un index sur chaque table qui inclut chaque colonne non clé en tant que colonne INCLUDED. Je prends rarement ces recommandations (comme je l'ai mentionné dans mon post précédent). Je vais construire juste l'index sur les Détails table, sur la colonne de jointure, et n'avoir aucune colonne incluse.
CREATE INDEX Header_index on Headers(SalesOrderID);
Une fois cet index construit, HASH JOIN disparaît. L'index trie les données dans les En-têtes table et permet à SQL Server de rechercher les lignes correspondantes dans la table interne à l'aide de la séquence de tri de l'index. Maintenant, la partie la plus chère du plan est le scan sur la table extérieure (Détails ) qui pourrait être réduit en créant un index sur le SalesOrderID colonne de ce tableau. Je vais laisser cela comme un exercice pour le lecteur.
Cependant, un plan avec un HASH JOIN n'est pas toujours une mauvaise chose. L'opérateur alternatif (sauf dans des cas particuliers) est un NESTED LOOPS JOIN, et c'est généralement le choix lorsque de bons index sont présents. Cependant, une opération de boucles NESTED nécessite plusieurs recherches dans la table interne. Le pseudocode suivant montre l'algorithme de jointure de boucles imbriquées :
for each row R1 in the outer table
for each row R2 in the inner table
if R1 joins with R2
return (R1, R2)
Comme son nom l'indique, un NESTED LOOP JOIN est exécuté comme une boucle imbriquée. La recherche de la table interne sera généralement effectuée plusieurs fois, une fois pour chaque ligne de qualification dans la table externe. Même s'il n'y a que quelques pour cent des lignes éligibles, si le tableau est très volumineux (peut-être des centaines de millions, ou des milliards, ou des lignes), il y aura beaucoup de lignes à lire. Dans un système lié aux E/S, ces millions ou milliards de lectures peuvent constituer un véritable goulot d'étranglement.
Un HASH JOIN, d'autre part, ne fait pas plusieurs lectures de l'une ou l'autre table. Il lit la table externe une fois pour créer les seaux de hachage, puis lit la table interne une fois, vérifiant les seaux de hachage pour voir s'il existe une ligne correspondante. Nous avons une limite supérieure d'un seul passage à travers chaque table. Oui, des ressources CPU sont nécessaires pour calculer la fonction de hachage et gérer le contenu des compartiments. Des ressources mémoire sont nécessaires pour stocker les informations hachées. Mais, si vous avez un système lié aux E/S, vous pouvez avoir des ressources de mémoire et de processeur à revendre. HASH JOIN peut être un choix raisonnable pour l'optimiseur dans ces situations où vos ressources d'E/S sont limitées et où vous joignez de très grandes tables.
Voici le pseudocode de l'algorithme de jointure par hachage :
for each row R1 in the build table
begin
calculate hash value on R1 join key(s)
insert R1 into the appropriate hash bucket
end
for each row R2 in the probe table
begin
calculate hash value on R2 join key(s)
for each row R1 in the corresponding hash bucket
if R1 joins with R2
output (R1, R2)
end
Comme mentionné précédemment, le hachage peut également être utilisé pour les opérations d'agrégation (ainsi que d'UNION). Encore une fois, s'il existe un index utile dont les données sont déjà triées, le regroupement des données peut être effectué de manière très efficace. Cependant, il existe également de nombreuses situations où le hachage n'est pas du tout un mauvais opérateur. Considérez une requête comme la suivante, qui regroupe les données dans les Détails table (créée ci-dessus) par le ProductID colonne. Il y a 121 317 lignes dans le tableau et seulement 266 ProductID différents valeurs.
SELECT ProductID, count(*)
FROM Details
GROUP BY ProductID;
GO
Utilisation des opérations de hachage
Pour utiliser le hachage, SQL Server n'a qu'à créer et maintenir 266 compartiments, ce qui n'est pas beaucoup. En fait, Quest Spotlight Tuning Pack n'indique aucun problème avec cette requête. 
Oui, il doit faire une analyse de table, mais c'est parce que nous devons examiner chaque ligne de la table, et nous savons que les analyses ne sont pas toujours une mauvaise chose. Un index n'aiderait qu'au tri préalable des données, mais l'utilisation de l'agrégation de hachage pour un si petit nombre de groupes donnera toujours des performances raisonnables même sans index utile disponible.
Comme les analyses de table, les opérations de hachage sont souvent considérées comme un « mauvais » opérateur à avoir dans un plan. Il existe des cas où vous pouvez grandement améliorer les performances en ajoutant des index utiles pour supprimer les opérations de hachage, mais ce n'est pas toujours vrai. Et si vous essayez de limiter le nombre d'index sur des tables fortement mises à jour, vous devez savoir que les opérations de hachage ne doivent pas toujours être "fixées", donc laisser la requête utiliser un hachage peut être une chose raisonnable faire. De plus, pour certaines requêtes sur de grandes tables exécutées sur des systèmes liés aux E/S, le hachage peut en fait donner de meilleures performances que les algorithmes alternatifs en raison du nombre limité de lectures qui doivent être effectuées. Le seul moyen d'en être sûr, c'est de tester différentes possibilités sur votre système, avec vos requêtes et vos données.
Dans l'article suivant de cette série, je vous parlerai d'autres opérateurs problématiques qui pourraient apparaître dans vos plans de requête, alors revenez bientôt !
