Quand et pourquoi les jointures de bases de données sont-elles coûteuses ?

Question

Je fais des recherches sur les bases de données et j'examine certaines limites des bases de données relationnelles.

J'ai compris que les jointures de grandes tables sont très coûteuses, mais je ne sais pas vraiment pourquoi. Que doit faire le SGBD pour exécuter une opération de jointure, où se trouve le goulot d'étranglement ?
Comment la dénormalisation peut-elle aider à surmonter cette dépense ? Comment les autres techniques d'optimisation (l'indexation, par exemple) peuvent-elles aider ?

Les expériences personnelles sont les bienvenues ! Si vous devez poster des liens vers des ressources, évitez s'il vous plaît Wikipedia. Je sais déjà où trouver cela.

À ce propos, je m'interroge sur les approches dénormalisées utilisées par les bases de données des services en nuage comme BigTable et SimpleDB. Voir cette question .

Answer 1

Dénormaliser pour améliorer les performances ? C'est convaincant, mais ça ne tient pas la route.

Chris Date, qui, en compagnie du Dr Ted Codd, a été le premier promoteur du modèle de données relationnel, a perdu patience avec les arguments mal informés contre la normalisation et les a systématiquement démolis en utilisant la méthode scientifique : il a obtenu de grandes bases de données et des données d'analyse de l'environnement. testé ces affirmations.

Je pense qu'il l'a écrit dans Écrits sur les bases de données relationnelles 1988-1991 mais ce livre a été repris plus tard dans l'édition six de Introduction aux systèmes de bases de données qui est le site Le texte définitif sur la théorie et la conception des bases de données, qui en est à sa huitième édition au moment où j'écris ces lignes et qui devrait rester imprimé pendant des décennies. Chris Date était un expert dans ce domaine lorsque la plupart d'entre nous couraient encore pieds nus.

Il a trouvé ça :

• Certaines d'entre elles sont valables pour des cas particuliers
• Tous ne sont pas rentables pour un usage général.
• Ils sont tous nettement plus mauvais pour d'autres cas particuliers

Tout revient à atténuer la taille de l'ensemble de travail. Les jointures impliquant des clés correctement sélectionnées avec des index correctement configurés sont bon marché, et non coûteuses, car elles permettent un élagage significatif du résultat. avant les rangs sont matérialisés.

La matérialisation du résultat implique des lectures de disque en masse qui sont l'aspect le plus coûteux de l'exercice par ordre de grandeur. L'exécution d'une jointure, en revanche, ne nécessite logiquement que la récupération de l'élément clés . En pratique, les valeurs des clés ne sont même pas récupérées : les valeurs de hachage des clés sont utilisées pour les comparaisons de jointures, ce qui atténue le coût des jointures multi-colonnes et réduit radicalement le coût des jointures impliquant des comparaisons de chaînes. Non seulement une quantité beaucoup plus importante de données peut être mise en cache, mais il y a aussi beaucoup moins de lecture sur disque à effectuer.

De plus, un bon optimiseur choisira la condition la plus restrictive et l'appliquera avant d'effectuer une jointure, ce qui permet d'exploiter très efficacement la grande sélectivité des jointures sur les index à cardinalité élevée.

Il est vrai que ce type d'optimisation peut également être appliqué à des bases de données dénormalisées, mais le type de personnes qui utilisent ces bases de données n'est pas le même. veulent pour dénormaliser un schéma ne pensent généralement pas à la cardinalité quand (si) ils mettent en place des index.

Il est important de comprendre que les balayages de table (examen de chaque ligne d'une table au cours de la production d'une jointure) sont rares en pratique. Un optimiseur de requêtes ne choisira un balayage de table que si une ou plusieurs des conditions suivantes sont remplies.

• Il y a moins de 200 lignes dans la relation (dans ce cas, un scan sera moins coûteux).
• Il n'y a pas d'index approprié sur les colonnes de jointure (si la jointure sur ces colonnes a un sens, pourquoi ne sont-elles pas indexées ? corrigez cela)
• Une coercition de type est nécessaire avant que les colonnes puissent être comparées (WTF ?! Fixez-le ou rentrez chez vous). VOIR LES NOTES DE FIN D'OUVRAGE POUR LE PROBLÈME ADO.NET
• L'un des arguments de la comparaison est une expression (sans index).

Effectuer une opération est plus coûteux que de ne pas l'effectuer. Toutefois, l'exécution de l'opération mauvais d'être obligé d'effectuer des entrées/sorties inutiles sur le disque, puis de rejeter les déchets avant d'effectuer la jointure dont vous avez réellement besoin, est beaucoup plus coûteux. Même lorsque la "mauvaise" opération est précalculée et que les index ont été judicieusement appliqués, la pénalité reste importante. Dénormaliser pour précalculer une jointure - nonobstant les anomalies de mise à jour qui en découlent - est un engagement envers une jointure particulière. Si vous avez besoin d'une différents rejoindre, cet engagement va vous coûter grand .

Si quelqu'un veut me rappeler que le monde évolue, je pense que vous trouverez que des ensembles de données plus importants sur du matériel plus difficile ne font qu'exagérer l'étendue des résultats de Date.

Pour tous ceux d'entre vous qui travaillent sur des systèmes de facturation ou des générateurs de courrier indésirable (honte à vous) et qui s'indignent en tapant sur leur clavier pour me dire qu'ils savent pertinemment que la dénormalisation est plus rapide, je suis désolé mais vous vivez dans l'un des cas particuliers - plus précisément, le cas où vous traitez les données suivantes tous des données, dans l'ordre. Ce n'est pas un cas général, et on peut sont justifiée dans votre stratégie.

Vous êtes pas justifié de le généraliser faussement. Voir la fin de la section des notes pour plus d'informations sur l'utilisation appropriée de la dénormalisation dans les scénarios d'entreposage de données.

J'aimerais également répondre à

Les joints sont juste des produits cartésiens avec un peu de brillant à lèvres.

Quel tas de conneries. Les restrictions sont appliquées le plus tôt possible, les plus restrictives en premier. Vous avez lu la théorie, mais vous ne l'avez pas comprise. Les jointures sont traité comme des "produits cartésiens auxquels s'appliquent des prédicats". uniquement par l'optimiseur de requêtes. Il s'agit d'une représentation symbolique (une normalisation, en fait) pour faciliter la décomposition symbolique afin que l'optimiseur puisse produire toutes les transformations équivalentes et les classer par coût et sélectivité afin de pouvoir sélectionner le meilleur plan de requête.

La seule façon pour l'optimiseur de produire un produit cartésien est de ne pas fournir de prédicat : SELECT * FROM A,B

---

Notes

---

David Aldridge fournit des informations complémentaires importantes.

Il existe en effet une variété de stratégies autres que les index et les balayages de table, et un optimiseur moderne les évaluera toutes avant de produire un plan d'exécution.

Un conseil pratique : s'il peut être utilisé comme clé étrangère, alors indexez-le, de sorte qu'une stratégie d'indexation est disponible sur à l'optimiseur.

J'avais l'habitude d'être plus intelligent que l'optimiseur MSSQL. Cela a changé il y a deux versions. Maintenant, il enseigne généralement moi . Il s'agit, dans un sens très réel, d'un système expert, codifiant toute la sagesse de nombreuses personnes très intelligentes dans un domaine suffisamment fermé pour qu'un système basé sur des règles soit efficace.

---

"Bollocks" a peut-être manqué de tact. On me demande d'être moins hautain et on me rappelle que les mathématiques ne mentent pas. C'est vrai, mais toutes les implications des modèles mathématiques ne doivent pas nécessairement être prises au pied de la lettre. Les racines carrées des nombres négatifs sont très pratiques si vous évitez soigneusement d'examiner leur absurdité (jeu de mots là) et si vous vous assurez de toutes les annuler avant d'essayer d'interpréter votre équation.

La raison pour laquelle j'ai répondu si violemment est que la déclaration telle qu'elle est formulée dit que

Rejoint sont produits cartésiens...

Ce n'est peut-être pas ce qui était prévu, mais c'est est ce qui a été écrit, et c'est catégoriquement faux. Un produit cartésien est une relation. Une jointure est une fonction. Plus précisément, une jointure est une fonction à valeur de relation. Avec un prédicat vide, elle produira un produit cartésien, et vérifier qu'elle le fait est un contrôle de correction pour un moteur d'interrogation de base de données, mais personne n'écrit de jointures sans contrainte dans la pratique parce qu'elles n'ont aucune valeur pratique en dehors d'une salle de classe.

Je l'ai signalé parce que je ne veux pas que les lecteurs tombent dans le vieux piège qui consiste à confondre le modèle et la chose modélisée. Un modèle est une approximation, délibérément simplifiée pour faciliter la manipulation.

---

Le seuil de sélection d'une stratégie de jointure par balayage de table peut varier selon les moteurs de base de données. Il est affecté par un certain nombre de décisions d'implémentation telles que le facteur de remplissage des nœuds d'arbre, la taille des valeurs clés et les subtilités de l'algorithme, mais d'une manière générale, l'indexation haute performance a un temps d'exécution de k journal n + c . Le terme C correspond à des frais généraux fixes, essentiellement constitués de temps de préparation, et la forme de la courbe signifie que vous n'obtenez pas de gain (par rapport à une recherche linéaire) avant la fin de l'année. n se compte en centaines.

---

Parfois, la dénormalisation est une bonne idée

La dénormalisation est un engagement envers une stratégie de jonction particulière. Comme mentionné précédemment, cela interfère avec autre stratégies de jointure. Mais si vous disposez d'une grande quantité d'espace disque, de schémas d'accès prévisibles et d'une tendance à traiter tout ou partie de cet espace, le calcul préalable d'une jointure peut s'avérer très utile.

Vous pouvez également déterminer les chemins d'accès que votre opération utilise généralement et précalculer toutes les jointures pour ces chemins d'accès. C'est le principe qui sous-tend les entrepôts de données, du moins lorsqu'ils sont construits par des personnes qui savent pourquoi elles font ce qu'elles font, et pas seulement pour des raisons de conformité aux mots à la mode.

Un entrepôt de données correctement conçu est produit périodiquement par une transformation en masse à partir d'un système de traitement des transactions normalisé. Cette séparation des bases de données d'opérations et de rapports a pour effet très souhaitable d'éliminer le conflit entre OLTP et OLAP (traitement des transactions en ligne, c'est-à-dire saisie des données, et traitement analytique en ligne, c'est-à-dire rapports).

Un point important ici est qu'en dehors des mises à jour périodiques, l'entrepôt de données est lecture seulement . Cela rend caduque la question des anomalies de mise à jour.

Ne faites pas l'erreur de dénormaliser votre base de données OLTP (la base de données sur laquelle se fait la saisie des données). Cela peut être plus rapide pour la facturation, mais si vous le faites, vous obtiendrez des anomalies de mise à jour. Avez-vous déjà essayé de faire en sorte que le Reader's Digest cesse de vous envoyer des articles ?

L'espace disque est bon marché de nos jours, alors faites-vous plaisir. Mais la dénormalisation n'est qu'une partie de l'histoire des entrepôts de données. Des gains de performance bien plus importants sont obtenus grâce à des valeurs cumulées précalculées : totaux mensuels, ce genre de choses. C'est toujours sur la réduction de l'ensemble de travail.

---

Problème d'inadéquation des types dans ADO.NET

Supposons que vous avez une table SQL Server contenant une colonne indexée de type varchar, et que vous utilisez AddWithValue pour passer un paramètre contraignant une requête sur cette colonne. Les chaînes de caractères C# sont Unicode, donc le type de paramètre déduit sera NVARCHAR, qui ne correspond pas à VARCHAR.

La conversion de VARCHAR en NVARCHAR est une conversion élargie qui se produit donc implicitement - mais dites adieu à l'indexation, et bonne chance pour trouver pourquoi.

---

"Count the disk hits" (Rick James)

Si tout est mis en cache dans la RAM, JOINs sont plutôt bon marché. C'est-à-dire que la normalisation n'a pas beaucoup pénalité de performance .

Si un schéma "normalisé" provoque JOINs de frapper le disque souvent, mais le schéma équivalent "dénormalisé" n'aurait pas à frapper le disque, alors la dénormalisation gagne une compétition de performance.

Commentaire de l'auteur original : Les moteurs de bases de données modernes sont très bons pour organiser le séquençage des accès afin de minimiser les pertes de cache pendant les opérations de jointure. Ce qui précède, bien que vrai, pourrait être interprété à tort comme impliquant que les jointures sont nécessairement coûteuses sur les grandes données. Cela pourrait conduire à une mauvaise prise de décision de la part de développeurs inexpérimentés.

Answer 2

Ce que la plupart des commentateurs ne remarquent pas, c'est le large éventail de méthodologies de jointure disponibles dans un SGBDR complexe, et les dénormalisateurs passent invariablement sous silence le coût plus élevé de la maintenance des données dénormalisées. Toutes les jointures ne sont pas basées sur des index, et les bases de données disposent d'un grand nombre d'algorithmes et de méthodologies de jointure optimisés, destinés à réduire les coûts de jointure.

Dans tous les cas, le coût d'une articulation dépend de son type et de quelques autres facteurs. Elle ne doit pas nécessairement être chère du tout - quelques exemples.

• Une jointure de hachage, dans laquelle les données en vrac sont jointes de manière égale, est en effet très bon marché, et le coût ne devient significatif que si la table de hachage ne peut pas être mise en cache en mémoire. Aucun index n'est nécessaire. L'équi-partitionnement entre les ensembles de données joints peut être d'une grande aide.
• Le coût d'une jointure tri-fusion est déterminé par le coût du tri plutôt que par celui de la fusion. Une méthode d'accès basée sur un index peut pratiquement éliminer le coût du tri.
• Le coût d'une jointure en boucle imbriquée sur un index dépend de la hauteur de l'index b-tree et de l'accès au bloc de table lui-même. C'est rapide, mais pas adapté aux jointures en masse.
• Une jointure en boucle imbriquée basée sur un cluster est beaucoup moins chère, avec moins d'entrées-sorties logiques requises par ligne de jointure. Si les tables jointes sont toutes deux dans le même cluster, la jointure devient très bon marché grâce à la colocation des lignes jointes.

Les bases de données sont conçues pour faire des jointures, et elles sont très flexibles dans la façon dont elles le font et généralement très performantes, à moins qu'elles ne se trompent dans le mécanisme de jointure.

Answer 3

Je pense que toute la question est basée sur une fausse prémisse. Les jointures sur les grandes tables sont pas nécessairement coûteux. En effet, Faire des jointures de manière efficace est l'une des principales raisons d'être des bases de données relationnelles. du tout. Joints sur grand fixe sont souvent coûteuses, mais il est très rare que vous souhaitiez joindre l'intégralité du contenu d'une grande table A à l'intégralité du contenu d'une grande table B. Au lieu de cela, vous écrivez la requête de telle sorte que seulement les lignes importantes de chaque table sont utilisés et l'ensemble réel conservé par la jointure reste plus petit.

En outre, vous bénéficiez des gains d'efficacité mentionnés par Peter Wone, à savoir que seules les parties importantes de chaque enregistrement doivent rester en mémoire jusqu'à ce que le jeu de résultats final soit matérialisé. De plus, dans les grandes requêtes avec de nombreuses jointures, il est préférable de commencer par les plus petits ensembles de tables et de progresser vers les plus grands, de sorte que l'ensemble conservé en mémoire reste aussi petit que possible aussi longtemps que possible.

Lorsqu'elles sont faites correctement, les jonctions sont généralement meilleur moyen pour comparer, combiner ou filtrer de grandes quantités de données.

Answer 4

Le goulot d'étranglement est à peu près toujours les entrées/sorties sur disque, et plus particulièrement les entrées/sorties aléatoires sur disque (en comparaison, les lectures séquentielles sont assez rapides et peuvent être mises en cache avec des stratégies de lecture anticipée).

Rejoint peut augmenter les recherches aléatoires - si vous sautez partout en lisant de petites parties d'une grande table. Mais les optimiseurs de requêtes tiennent compte de ce phénomène et, s'ils pensent que c'est mieux, ils le transformeront en un balayage séquentiel de la table (en éliminant les lignes inutiles).

Un tableau unique dénormalisé présente un problème similaire : les lignes sont grandes et ne tiennent pas sur une seule page de données. Si vous avez besoin de lignes éloignées les unes des autres (et que la taille importante des lignes les rend plus éloignées les unes des autres), vous aurez davantage d'E/S aléatoires. Là encore, un balayage de table peut être imposé pour éviter cela. Mais, cette fois, votre analyse de table doit lire plus de données en raison de la grande taille des lignes. Ajoutez à cela le fait que vous la copie des données d'un emplacement unique à plusieurs emplacements, et le SGBDR a beaucoup plus à lire (et à mettre en cache).

Avec deux tables, vous disposez également de deux index en cluster et vous pouvez généralement indexer davantage (en raison de la réduction de la surcharge d'insertion/mise à jour), ce qui peut vous permettre d'améliorer considérablement les performances (principalement, encore une fois, parce que les index sont (relativement) petits, rapides à lire sur le disque (ou bon marché à mettre en cache) et réduisent le nombre de lignes de la table que vous devez lire sur le disque).

La seule surcharge d'une jointure provient de la recherche des lignes correspondantes. Sql Server utilise 3 différents types de jointures, principalement basés sur la taille des ensembles de données, pour trouver les lignes correspondantes. Si l'optimiseur choisit le mauvais type de jointure (en raison de statistiques inexactes, d'index inadéquats ou simplement d'un bogue ou d'un cas limite de l'optimiseur), cela peut affecter considérablement les temps de requête.

• Une jointure en boucle est très bon marché pour (au moins un) petit ensemble de données.
• Une jointure de fusion nécessite d'abord un tri des deux ensembles de données. Cependant, si vous effectuez une jointure sur une colonne indexée, l'index est déjà trié et aucun travail supplémentaire n'est nécessaire. Dans le cas contraire, le tri entraîne une surcharge du processeur et de la mémoire.
• La jointure de hachage nécessite à la fois de la mémoire (pour stocker la table de hachage) et du CPU (pour construire le hachage). Là encore, cette opération est assez rapide par rapport aux E/S du disque. Cependant Si la RAM n'est pas suffisante pour stocker la table de hachage, Sql Server utilisera tempdb pour stocker des parties de la table de hachage et les lignes trouvées, puis ne traitera que des parties de la table de hachage à la fois. Comme pour tout ce qui concerne le disque, cette méthode est assez lente.

Dans le cas optimal, ils n'entraînent aucune entrée/sortie de disque et sont donc négligeables du point de vue des performances.

En somme, au pire, il devrait être plus rapide de lire la même quantité de logique Il est plus facile de lire les données de x tables jointes que celles d'une seule table dénormalisée, car les lectures sur disque sont plus petites. Pour lire la même quantité de physique les données, il pourrait y avoir une légère surcharge.

Étant donné que le temps de requête est généralement dominé par les coûts d'E/S et que la taille de vos données ne change pas (à l'exception d'un minuscule surcoût de ligne) avec la dénormalisation, il n'y a pas beaucoup d'avantages à fusionner les tables ensemble. Le type de dénormalisation qui tend à augmenter les performances, IME, est la mise en cache des valeurs calculées au lieu de lire les 10.000 lignes nécessaires pour les calculer.

Answer 5

L'ordre dans lequel vous joignez les tables est extrêmement important. Si vous avez deux ensembles de données, essayez de construire la requête de manière à ce que le plus petit soit utilisé en premier afin de réduire la quantité de données sur laquelle la requête doit travailler.

Pour certaines bases de données, cela n'a pas d'importance, par exemple MS SQL connaît l'ordre de jointure approprié la plupart du temps. Pour d'autres (comme IBM Informix), l'ordre fait toute la différence.