Quand et pourquoi les jointures de base de données coûtent-elles cher?

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

J'obtiens que les jointures de grandes tables coûtent très cher, mais je ne sais pas vraiment pourquoi. Que doit faire le SGBD pour exécuter une opération de jointure, où est le goulot d'étranglement?
Comment la dénormalisation peut-elle aider à surmonter ces dépenses? Comment les autres techniques d'optimisation (indexation, par exemple) aident-elles?

Les expériences personnelles sont les bienvenues! Si vous souhaitez publier des liens vers des ressources, veuillez éviter Wikipédia. Je sais déjà où trouver ça.

Par rapport à cela, je m'interroge sur les approches dénormalisées utilisées par les bases de données de services cloud comme BigTable et SimpleDB. Voir cette question .

Dénormaliser pour améliorer les performances? Cela semble convaincant, mais il ne tient pas la route.

Chris Date, qui en compagnie du Dr Ted Codd était le promoteur initial du modèle de données relationnelles, a manqué de patience avec des arguments mal informés contre la normalisation et les a systématiquement démolis en utilisant une méthode scientifique: il a obtenu de grandes bases de données et testé ces assertions.

Je pense qu'il l'a écrit dans Relational Database Writings 1988-1991, mais ce livre a ensuite été intégré à la sixième édition d' Introduction to Database Systems , qui est le texte définitif sur la théorie et la conception des bases de données, dans sa huitième édition au moment où j'écris et qui restera probablement en version imprimée pour les décennies à venir. Chris Date était un expert dans ce domaine lorsque la plupart d'entre nous couraient encore pieds nus.

Il a constaté que:

• Certains d'entre eux tiennent pour des cas spéciaux
• Tous ne sont pas rentables pour une utilisation générale
• Tous sont nettement pires pour d'autres cas spéciaux

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é, pas chers, car elles permettent un élagage significatif du résultat avant la matérialisation des lignes.

La matérialisation du résultat implique des lectures de disques en vrac qui sont l'aspect le plus coûteux de l'exercice par ordre de grandeur. La réalisation d'une jointure, en revanche, nécessite logiquement la récupération des seules clés . En pratique, même les valeurs de clé ne sont pas récupérées: les valeurs de hachage de clé sont utilisées pour les comparaisons de jointures, ce qui réduit le coût des jointures à plusieurs colonnes et réduit radicalement le coût des jointures impliquant des comparaisons de chaînes. Non seulement sa place dans le cache sera beaucoup plus importante, mais il y aura beaucoup moins de lecture de disque à faire.

De plus, un bon optimiseur choisira la condition la plus restrictive et l'appliquera avant d'effectuer une jointure, en tirant très efficacement parti de la haute sélectivité des jointures sur les index à cardinalité élevée.

Certes, ce type d'optimisation peut également être appliqué aux bases de données dénormalisées, mais le type de personnes qui souhaitent dénormaliser un schéma ne pense généralement pas à la cardinalité quand (si) elles configurent des index.

Il est important de comprendre que les analyses de table (examen de chaque ligne d'une table au cours de la production d'une jointure) sont rares dans la pratique. Un optimiseur de requête choisira une analyse de table uniquement lorsqu'un ou plusieurs des éléments suivants sont conservés.

• Il y a moins de 200 lignes dans la relation (dans ce cas, un scan sera moins cher)
• Il n'y a pas d'index appropriés sur les colonnes de jointure (s'il est utile de se joindre à ces colonnes, alors pourquoi ne sont-elles pas indexées? Corrigez-le)
• Une contrainte de type est requise avant que les colonnes puissent être comparées (WTF?! Corrigez-le ou rentrez chez vous) VOIR LES NOTES FINALES POUR LE NUMÉRO ADO.NET
• L'un des arguments de la comparaison est une expression (pas d'index)

L'exécution d'une opération est plus coûteuse que son absence. Cependant, effectuer la mauvaise opération, être forcé dans des E / S disque inutiles, puis éliminer les scories avant d'effectuer la jointure dont vous avez vraiment 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, il reste une pénalité importante. Dénormaliser pour précalculer une jointure - nonobstant les anomalies de mise à jour impliquées - est un engagement envers une jointure particulière. Si vous avez besoin d' une autre jointure, cet engagement va vous coûter gros .

Si quelqu'un veut me rappeler que le monde est en mutation, je pense que vous constaterez que des ensembles de données plus volumineux sur un matériel plus grognon exagèrent simplement la propagation des résultats de Date.

Pour tous ceux qui travaillent sur des systèmes de facturation ou des générateurs de courrier indésirable (honte à vous) et mettent la main au clavier avec indignation pour me dire que vous savez pertinemment que la dénormalisation est plus rapide, désolé mais vous vivez dans l'un des spéciaux cas - en particulier, le cas où vous traitez toutes les données, dans l'ordre. Ce n'est pas un cas général, et vous êtes justifié dans votre stratégie.

Vous n'êtes pas justifié de le généraliser à tort. 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.

Je voudrais également répondre à

Les joints sont juste des produits cartésiens avec du brillant à lèvres

Quelle charge de conneries. Les restrictions sont appliquées le plus tôt possible, la plus restrictive en premier. Vous avez lu la théorie, mais vous ne l'avez pas comprise. Les jointures sont traitées comme des "produits cartésiens auxquels s'appliquent les 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 d'obtenir l'optimiseur pour produire un produit cartésien est de ne pas fournir un prédicat: SELECT * FROM A,B

Remarques

David Aldridge fournit quelques informations supplémentaires importantes.

Il existe en effet une variété d'autres stratégies en plus des index et des analyses de table, et un optimiseur moderne les coûtera toutes avant de produire un plan d'exécution.

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

J'étais plus intelligent que l'optimiseur MSSQL. Cela a changé il y a deux versions. Maintenant, cela m'apprend généralement . 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 fondé sur des règles soit efficace.

"Bollocks" peut avoir été sans tact. On me demande d'être moins hautain et de me rappeler 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 à 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à-bas) et assurez-vous de les annuler toutes avant d'essayer d'interpréter votre équation.

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

Les jointures sont des produits cartésiens ...

Cela peut ne pas être ce que voulait dire , mais il est ce qui a été écrit, et il est absolument faux. Un produit cartésien est une relation. Une jointure est une fonction. Plus précisément, une jointure est une fonction à valeur relationnelle. Avec un prédicat vide, il produira un produit cartésien et vérifier qu'il le fait est une vérification d'exactitude pour un moteur de requête de base de données, mais personne n'écrit des jointures sans contrainte dans la pratique parce qu'elles n'ont aucune valeur pratique en dehors d'une salle de classe.

J'ai appelé cela parce que je ne veux pas que les lecteurs tombent dans le piège ancien de confondre le modèle avec la chose modélisée. Un modèle est une approximation, délibérément simplifiée pour une manipulation pratique.

La coupure pour la sélection d'une stratégie de jointure de table-scan peut varier selon les moteurs de base de données. Elle est affectée par un certain nombre de décisions d'implémentation telles que le facteur de remplissage du nœud d'arbre, la taille de la valeur-clé et les subtilités de l'algorithme, mais d'une manière générale, l'indexation hautes performances a un temps d'exécution de k log n + c . Le terme C est une surcharge fixe principalement constituée de temps de configuration, et la forme de la courbe signifie que vous n'obtenez pas de gain (par rapport à une recherche linéaire) tant que n n'est pas dans les centaines.

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

La dénormalisation est un engagement envers une stratégie de jointure particulière. Comme mentionné précédemment, cela interfère avec d' autres stratégies de jointure. Mais si vous avez des compartiments d'espace disque, des modèles d'accès prévisibles et une tendance à en traiter une grande partie ou la totalité, le précalcul d'une jointure peut être 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 la prémisse derrière les entrepôts de données, ou du moins c'est quand ils sont construits par des gens qui savent pourquoi ils font ce qu'ils font, et pas seulement pour la 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 des opérations et des 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 en lecture seule . Cela rend sans objet la question des anomalies de mise à jour.

Ne commettez pas l'erreur de dénormaliser votre base de données OLTP (la base de données sur laquelle s'effectue la saisie des données). Cela peut être plus rapide pour les cycles de facturation, mais si vous le faites, vous obtiendrez des anomalies de mise à jour. Avez-vous déjà essayé d'obtenir que Reader's Digest arrête de vous envoyer des trucs?

L'espace disque est bon marché de nos jours, alors assommez-vous. Mais la dénormalisation n'est qu'une partie de l'histoire des entrepôts de données. Des gains de performances beaucoup plus importants sont dérivés des valeurs cumulées précalculées: les totaux mensuels, ce genre de choses. Il s'agit toujours de réduire l'ensemble de travail.

Problème ADO.NET avec des incompatibilités de types

Supposons que vous ayez 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 C # sont Unicode, donc le type de paramètre déduit sera NVARCHAR, qui ne correspond pas à VARCHAR.

VARCHAR vers NVARCHAR est une conversion qui s'élargit donc cela se produit implicitement - mais dites adieu à l'indexation et bonne chance pour comprendre pourquoi.

"Comptez les hits du disque" (Rick James)

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

Si un schéma "normalisé" fait JOINsbeaucoup frapper le disque, mais que le schéma équivalent "dénormalisé" n'aurait pas à frapper le disque, la dénormalisation remporte un concours de performances.

Commentaire de l'auteur original: Les moteurs de base de données modernes sont très bons pour organiser le séquencement des accès afin de minimiser les erreurs de cache pendant les opérations de jointure. Ce qui précède, bien que vrai, pourrait être mal interprété comme impliquant que les jointures sont nécessairement problématiques sur des données volumineuses. Cela entraînerait une mauvaise prise de décision de la part des développeurs inexpérimentés.

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 ignorent invariablement 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 ont de nombreux algorithmes et méthodologies de jointure optimisés qui visent à réduire les coûts de jointure.

Dans tous les cas, le coût d'une jointure dépend de son type et de quelques autres facteurs. Cela n'a pas besoin d'être cher du tout - quelques exemples.

• Une jointure de hachage, dans laquelle des données en vrac sont jointes, 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 requis. L'équi-partitionnement entre les ensembles de données joints peut être d'une grande aide.
• Le coût d'une jointure de fusion-tri est déterminé par le coût du tri plutôt que par 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 de boucle imbriquée sur un index est déterminé par la hauteur de l'index b-tree et l'accès au bloc de table lui-même. C'est rapide, mais ne convient pas aux jointures en masse.
• Une jointure en boucle imbriquée basée sur un cluster est beaucoup moins chère, avec moins d'E / S logiques requises par ligne de jointure - si les tables jointes sont toutes les 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 se joindre, 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 sur le mécanisme de jointure.

Je pense que toute la question est basée sur une fausse prémisse. Les jointures sur de grandes tables ne sont pas nécessairement chères. En fait, effectuer des jointures efficacement est l'une des principales raisons pour lesquelles les bases de données relationnelles existent . Les jointures sur de grands ensembles sont souvent coûteuses, mais très rarement, vous voulez joindre le contenu entier de la grande table A avec le contenu entier de la grande table B. Au lieu de cela, vous écrivez la requête de telle sorte que seules les lignes importantes de chaque table soient utilisées et l'ensemble réel conservé par la jointure reste plus petit.

De plus, vous avez les efficacités mentionnées par Peter Wone, de sorte que seules les parties importantes de chaque enregistrement doivent être en mémoire jusqu'à ce que le jeu de résultats final soit matérialisé. En outre, dans les requêtes volumineuses avec de nombreuses jointures, vous souhaitez généralement commencer par les ensembles de tables plus petits et progresser jusqu'aux plus grands, afin que l'ensemble conservé en mémoire reste aussi petit que possible aussi longtemps que possible.

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

Le goulot d'étranglement est à peu près toujours les E / S de disque, et encore plus spécifiquement - les E / S de disque aléatoires (en comparaison, les lectures séquentielles sont assez rapides et peuvent être mises en cache avec des stratégies de lecture anticipée).

Les jointures peuvent augmenter les recherches aléatoires - si vous sautez en lisant de petites parties d'une grande table. Mais, les optimiseurs de requête recherchent cela et le transformeront en une analyse séquentielle de table (en supprimant les lignes inutiles) s'il pense que ce serait mieux.

Une seule table dénormalisée a un problème similaire - les lignes sont grandes et donc moins adaptées à une seule page de données. Si vous avez besoin de lignes éloignées les unes des autres (et la grande taille des lignes les rend plus éloignées), vous aurez plus d'E / S aléatoires. Encore une fois, une analyse de table peut être forcée 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 copiez des données d'un emplacement unique à plusieurs emplacements, et le SGBDR a bien plus à lire (et à mettre en cache).

Avec 2 tables, vous obtenez également 2 index clusterisés - et vous pouvez généralement indexer plus (en raison de moins de surcharge d'insertion / mise à jour), ce qui peut vous permettre d'augmenter considérablement les performances (principalement, encore une fois, car les index sont (relativement) petits, rapides à lire sur le disque (ou pas cher à mettre en cache), et réduisez la quantité de lignes de table que vous devez lire sur le disque).

Le seul surcoût avec une jointure provient de la détermination des lignes correspondantes. Sql Server utilise 3 types de jointures différents, 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 d'optimiseur ou d'un cas de bord), il peut considérablement affecter les temps de requête.

• Une jointure en boucle est de loin bon marché pour (au moins 1) petit ensemble de données.
• Une jointure de fusion nécessite d'abord une sorte des deux jeux de données. Si vous vous joignez à une colonne indexée, cependant, l'index est déjà trié et aucun autre travail n'a besoin d'être effectué. Sinon, il y a une surcharge de CPU et de mémoire dans le tri.
• La jointure de hachage nécessite à la fois de la mémoire (pour stocker la table de hachage) et du CPU (pour créer le hachage). Encore une fois, c'est assez rapide par rapport aux E / S disque. Cependant , s'il n'y a pas suffisamment de RAM 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 traitera uniquement des parties de la table de hachage à la fois. Comme pour tout ce qui concerne le disque, c'est assez lent.

Dans le cas optimal, ceux-ci n'entraînent aucune E / S disque - et sont donc négligeables du point de vue des performances.

Dans l'ensemble, au pire - il devrait en fait être plus rapide de lire la même quantité de données logiques à partir de tables jointes x, comme c'est le cas d'une table dénormalisée unique en raison des lectures de disque plus petites. Pour lire la même quantité de données physiques , 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 (moins des frais généraux de ligne très minuscules) avec la dénormalisation, il n'y a pas énormément d'avantages à tirer simplement de la fusion des tables. Le type de dénormalisation qui tend à augmenter les performances, IME, consiste à mettre en cache les valeurs calculées au lieu de lire les 10 000 lignes requises pour les calculer.

L'ordre dans lequel vous rejoignez les tables est extrêmement important. Si vous disposez de deux ensembles de données, essayez de créer la requête de manière à ce que le plus petit soit utilisé en premier pour 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 la plupart du temps l'ordre de jointure approprié. Pour certains (comme IBM Informix), la commande fait toute la différence.

Décider de dénormaliser ou de normaliser est un processus assez simple lorsque vous considérez la classe de complexité de la jointure. Par exemple, j'ai tendance à concevoir mes bases de données avec une normalisation lorsque les requêtes sont O (k log n) où k est relatif à la magnitude de sortie souhaitée.

Un moyen simple de dénormaliser et d'optimiser les performances consiste à réfléchir à la façon dont les modifications apportées à votre structure de normalisation affectent votre structure dénormalisée. Cela peut être problématique car il peut nécessiter une logique transactionnelle pour fonctionner sur une structure dénormalisée.

Le débat sur la normalisation et la dénormalisation ne va pas se terminer car les problèmes sont vastes. Il existe de nombreux problèmes où la solution naturelle nécessite les deux approches.

En règle générale, j'ai toujours stocké une structure normalisée et des caches dénormalisés pouvant être reconstruits. Finalement, ces caches me sauvent le cul pour résoudre les futurs problèmes de normalisation.

Élaborer ce que les autres ont dit,

Les joints sont juste des produits cartésiens avec du brillant à lèvres. {1,2,3,4} X {1,2,3} nous donnerait 12 combinaisons (nXn = n ^ 2). Cet ensemble calculé agit comme une référence sur laquelle les conditions sont appliquées. Le SGBD applique les conditions (comme lorsque gauche et droite sont égales à 2 ou 3) pour nous donner la ou les conditions correspondantes. En fait, il est plus optimisé mais le problème est le même. Les changements de taille des ensembles augmenteraient la taille du résultat de façon exponentielle. La quantité de mémoire et les cycles de CPU consommés sont tous effectués en termes exponentiels.

Lorsque nous dénormalisons, nous évitons complètement ce calcul, pensez à avoir un collant coloré, attaché à chaque page de votre livre. Vous pouvez déduire les informations sans utiliser de référence. La pénalité que nous payons est que nous compromettons l'essence du SGBD (organisation optimale des données)