Traduction rapide de l’article http://coding-geek.com/how-databases-work/
Quand il s’agit de bases de données relationnelles, je ne peux m’empêcher de penser qu’il manque quelque chose. Ils sont utilisés partout. Il existe de nombreuses bases de données différentes: de la petite et utile SQLite au puissant Teradata. Mais, il n’y a que quelques articles qui expliquent comment fonctionne une base de données. Vous pouvez googler par vous-même « comment fonctionne une base de données relationnelle » pour voir combien il y a peu de résultats. De plus, ces articles sont courts. Maintenant, si vous recherchez les dernières technologies à la mode (Big Data, NoSQL ou JavaScript), vous trouverez des articles plus détaillés expliquant leur fonctionnement.
Les bases de données relationnelles sont-elles trop anciennes et trop ennuyeuses pour être expliquées en dehors des cours universitaires, des documents de recherche et des livres?
En tant que développeur, je déteste utiliser quelque chose que je ne comprends pas. Et, si les bases de données sont utilisées depuis 40 ans, il doit y avoir une raison. Au fil des ans, j’ai passé des centaines d’heures à vraiment comprendre ces étranges boîtes noires que j’utilise tous les jours. Les bases de données relationnelles sont très intéressantes car elles sont basées sur des concepts utiles et réutilisables. Si la compréhension d’une base de données vous intéresse mais que vous n’avez jamais eu le temps ou la volonté de creuser ce vaste sujet, vous devriez aimer cet article.
Bien que le titre de cet article soit explicite, le but de cet article n’est PAS de comprendre comment utiliser une base de données. Par conséquent, vous devez déjà savoir comment écrire une requête de jointure simple et des requêtes CRUD de base; Sinon, vous risquez de ne pas comprendre cet article. C’est la seule chose que vous devez savoir, je vais vous expliquer tout le reste.
Je vais commencer par quelques trucs informatiques comme la complexité temporelle. Je sais que certains d’entre vous détestent ce concept mais, sans lui, vous ne pouvez pas comprendre l’intelligence d’une base de données. Comme il s’agit d’un sujet énorme, je vais me concentrer sur ce qui me semble essentiel : la façon dont une base de données gère une requête SQL. Je ne présenterai que les concepts de base derrière une base de données afin qu’à la fin de l’article, vous ayez une bonne idée de ce qui se passe sous le capot.
Comme il s’agit d’un article long et technique qui implique de nombreux algorithmes et structures de données, prenez votre temps pour le lire. Certains concepts sont plus difficiles à comprendre; Vous pouvez les ignorer et toujours avoir l’idée globale.
Pour les plus avertis d’entre vous, cet article est plus ou moins divisé en 3 parties :
- Vue d’ensemble des composants de base de données de bas niveau et de haut niveau
- Vue d’ensemble du processus d’optimisation des requêtes
- Vue d’ensemble de la gestion des transactions et du pool de tampons
Retour aux sources
Il y a longtemps (dans une galaxie lointaine, très lointaine...), les développeurs devaient connaître exactement le nombre d’opérations qu’ils codaient. Ils connaissaient par cœur leurs algorithmes et leurs structures de données parce qu’ils ne pouvaient pas se permettre de gaspiller le processeur et la mémoire de leurs ordinateurs lents.
Dans cette partie, je vais vous rappeler certains de ces concepts car ils sont essentiels pour comprendre une base de données. J’introduirai également la notion d’index de base de données.
O(1) contre O(n2)
De nos jours, de nombreux développeurs ne se soucient pas de la complexité du temps ... Et ils ont raison !
Mais lorsque vous traitez une grande quantité de données (je ne parle pas de milliers) ou si vous vous battez pendant des millisecondes, il devient essentiel de comprendre ce concept. Et devinez quoi, les bases de données doivent faire face aux deux situations! Je ne vais pas vous ennuyer longtemps, juste le temps d’avoir l’idée. Cela nous aidera plus tard à comprendre le concept d’optimisation basée sur les coûts.
Le concept
La complexité temporelle est utilisée pour voir combien de temps un algorithme prendra pour une quantité donnée de données. Pour décrire cette complexité, les informaticiens utilisent la notation mathématique grand O. Cette notation est utilisée avec une fonction qui décrit le nombre d’opérations dont un algorithme a besoin pour une quantité donnée de données d’entrée.
Par exemple, quand je dis « cet algorithme est en O( some_function () ) », cela signifie que pour une certaine quantité de données, l’algorithme a besoin d’opérations some_function(a_certain_amount_of_data) pour faire son travail.
Ce qui est important, ce n’est pas la quantité de données, mais la façon dont le nombre d’opérations augmente lorsque la quantité de données augmente. La complexité temporelle ne donne pas le nombre exact d’opérations mais une bonne idée.
Dans cette figure, vous pouvez voir l’évolution de différents types de complexités. J’ai utilisé une échelle logarithmique pour le tracer. En d’autres termes, le nombre de données augmente rapidement de 1 à 1 milliard. Nous pouvons voir que :
- Le O(1) ou complexité constante reste constant (sinon on ne l’appellerait pas complexité constante).
- Le O(log(n)) reste faible même avec des milliards de données.
- La pire complexité est l’O(n2) où le nombre d’opérations explose rapidement.
- Les deux autrescomplexities augmentent rapidement.
Exemples
Avec une faible quantité de données, la différence entre O(1) et O(n2) est négligeable. Par exemple, disons que vous avez un algorithme qui doit traiter 2000 éléments.
- Un algorithme O(1) vous coûtera 1 opération
- Un algorithme O(log(n)) vous coûtera 7 opérations
- Un algorithme O(n) vous coûtera 2 000 opérations
- Un algorithme O(n*log(n)) vous coûtera 14 000 opérations
- Un algorithme O(n2) vous coûtera 4 000 000 d’opérations
La différence entre O(1) et O(n 2) semble beaucoup (4 millions) mais vous perdrez au maximum2 ms, juste le temps de cligner des yeux. En effet, les processeurs actuels peuvent gérer des centaines de millions d’opérations par seconde. C’est pourquoi la performance et l’optimisation ne sont pas un problème dans de nombreux projets informatiques.
Comme je l’ai dit, il est toujours important de connaître ce concept face à un grand nombre de données. Si cette fois l’algorithme doit traiter 1 000 000 d’éléments (ce qui n’est pas si gros pour une base de données):
- Un algorithme O(1) vous coûtera 1 opération
- Un algorithme O(log(n)) vous coûtera 14 opérations
- Un algorithme O(n) vous coûtera 1 000 000 d’opérations
- Un algorithme O(n*log(n)) vous coûtera 14 000 000 d’opérations
- Un algorithme O(n2) vous coûtera 1 000 000 000 000 d’opérations
Je n’ai pas fait le calcul mais je dirais qu’avec l’algorithme O(n2) vous avez le temps de prendre un café (même un deuxième!). Si vous mettez un autre 0 sur la quantité de données, vous aurez le temps de faire une longue sieste.
Aller plus loin
Pour vous donner une idée :
- Une recherche dans une bonne table de hachage donne un élément dans O(1)
- Une recherche dans un arbre bien équilibré donne un résultat en O(log(n))
- Une recherche dans un tableau donne un résultat en O(n)
- Les meilleurs algorithmes de tri ont une complexité O(n*log(n)).
- Un mauvais algorithme de tri a une complexité O(n2)
Remarque: Dans les parties suivantes, nous verrons ces algorithmes et structures de données.
Il existe plusieurs types de complexité temporelle :
- le scénario moyen
- Le meilleur scénario
- et le pire scénario
La complexité temporelle est souvent le pire des scénarios.
Je n’ai parlé que de la complexité temporelle, mais la complexité fonctionne aussi pour:
- la consommation de mémoire d’un algorithme
- la consommation d’E/S disque d’un algorithme
Bien sûr, il y a des complexités pires que n2, comme:
- n4 : C’est nul ! Certains des algorithmes que je mentionnerai ont cette complexité.
- 3n : ça craint encore plus ! L’un des algorithmes que nous allons voir au milieu de cet article a cette complexité (et il est vraiment utilisé dans de nombreuses bases de données).
- Factorielle N : Vous n’obtiendrez jamais vos résultats, même avec une faible quantité de données.
- nn : si vous vous retrouvez avec cette complexité, vous devriez vous demander si l’informatique est vraiment votre domaine...
Note: Je ne vous ai pas donné la vraie définition de la notation grand O mais juste l’idée. Vous pouvez lire cet article sur Wikipedia pour la définition réelle (asymptotique).
Tri de fusion
Que faites-vous lorsque vous devez trier une collection ? Quoi? Vous appelez la fonction sort() ... Ok, bonne réponse... Mais pour une base de données, vous devez comprendre comment fonctionne cette fonction sort().
Il existe plusieurs bons algorithmes de tri, je vais donc me concentrer sur le plus important : le tri de fusion. Vous ne comprenez peut-être pas pour le moment pourquoi le tri des données est utile, mais vous devriez le faire après la partie sur l’optimisation des requêtes. De plus, la compréhension du tri de fusion nous aidera plus tard à comprendre une opération de jointure de base de données commune appelée jointure de fusion.
Fusionner
Comme beaucoup d’algorithmes utiles, le tri par fusion est basé sur une astuce : fusionner 2 tableaux triés de taille N/2 en un tableau trié à N éléments ne coûte que N opérations. Cette opération est appelée fusion.
Voyons ce que cela signifie avec un exemple simple:
Vous pouvez voir sur cette figure que pour construire le tableau trié final de 8 éléments, vous n’avez besoin d’itérer qu’une seule fois dans les 2 tableaux à 4 éléments. Étant donné que les deux tableaux à 4 éléments sont déjà triés :
- 1) vous comparez les deux éléments actuels dans les 2 tableaux (current=first pour la première fois)
- 2) puis prenez le plus bas pour le mettre dans le tableau à 8 éléments
- 3) et passez à l’élément suivant dans le tableau où vous avez pris l’élément le plus bas
- et répétez 1,2,3 jusqu’à ce que vous atteigniez le dernier élément de l’un des tableaux.
- Ensuite, vous prenez le reste des éléments de l’autre tableau pour les placer dans le tableau à 8 éléments.
Cela fonctionne parce que les deux tableaux à 4 éléments sont triés et que vous n’avez donc pas besoin de « revenir en arrière » dans ces tableaux.
Maintenant que nous avons compris cette astuce, voici mon pseudo-code du type fusion.
array mergeSort(array a)
if(length(a)==1)
return a[0];
end if
//recursive calls
[left_array right_array] := split_into_2_equally_sized_arrays(a);
array new_left_array := mergeSort(left_array);
array new_right_array := mergeSort(right_array);
//merging the 2 small ordered arrays into a big one
array result := merge(new_left_array,new_right_array);
return result;
Le tri de fusion décompose le problème en problèmes plus petits, puis trouve les résultats des problèmes plus petits pour obtenir le résultat du problème initial (note: ce type d’algorithmes est appelé diviser pour régner). Si vous ne comprenez pas cet algorithme, ne vous inquiétez pas; Je ne l’ai pas compris la première fois que je l’ai vu. Si cela peut vous aider, je vois cet algorithme comme un algorithme à deux phases:
- La phase de division où la matrice est divisée en baies plus petites
- Phase de tri au cours de laquelle les petits tableaux sont assemblés (à l’aide de la fusion) pour former un tableau plus grand.
Phase de division
Pendant la phase de division, le tableau est divisé en tableaux unitaires en 3 étapes. Le nombre formel d’étapes est log(N) (puisque N=8, log(N) = 3).
Comment puis-je le savoir?
Je suis un génie ! En un mot : mathématiques. L’idée est que chaque étape divise la taille du tableau initial par 2. Le nombre d’étapes est le nombre de fois que vous pouvez diviser le tableau initial par deux. C’est la définition exacte du logarithme (en base 2).
Phase de tri
Dans la phase de tri, vous commencez par les tableaux unitaires. Au cours de chaque étape, vous appliquez plusieurs fusions et le coût global est N=8 opérations :
- Dans la première étape, vous avez 4 fusions qui coûtent 2 opérations chacune
- Dans la deuxième étape, vous avez 2 fusions qui coûtent 4 opérations chacune
- Dans la troisième étape, vous avez 1 fusion qui coûte 8 opérations
Puisqu’il y a des étapes log(N), le coût global N * log(N) opérations.
La puissance du tri de fusion
Pourquoi cet algorithme est-il si puissant ?
Parce que:
- Vous pouvez le modifier afin de réduire l’empreinte mémoire, de manière à ne pas créer de nouveaux tableaux, mais à modifier directement le tableau d’entrée.
Remarque: ce type d’algorithmes est appelé in-place.
- Vous pouvez le modifier afin d’utiliser l’espace disque et une petite quantité de mémoire en même temps sans une énorme pénalité d’E/S disque. L’idée est de charger en mémoire uniquement les parties qui sont actuellement traitées. Ceci est important lorsque vous devez trier une table de plusieurs gigaoctets avec seulement une mémoire tampon de 100 mégaoctets.
Remarque : ce type d’algorithmes est appelé tri externe.
- Vous pouvez le modifier pour l’exécuter sur plusieurs processus/threads/serveurs.
Par exemple, le tri de fusion distribué est l’un des composants clés de Hadoop (qui est LE framework du Big Data).
- Cet algorithme peut transformer le plomb en or (fait vrai!).
Cet algorithme de tri est utilisé dans la plupart (sinon toutes) les bases de données, mais ce n’est pas le seul. Si vous voulez en savoir plus, vous pouvez lire ce document de recherche qui traite des avantages et des inconvénients des algorithmes de tri courants dans une base de données.
Tableau, arborescence et table de hachage
Maintenant que nous comprenons l’idée derrière la complexité temporelle et le tri, je dois vous parler de 3 structures de données. C’est important parce qu’ils sont l’épine dorsale des bases de données modernes. J’introduirai également la notion d’index de base de données.
Tableau
Le tableau bidimensionnel est la structure de données la plus simple. Une table peut être vue comme un tableau. Par exemple:
Ce tableau à 2 dimensions est un tableau avec des lignes et des colonnes :
- Chaque ligne représente un sujet
- Les colonnes les caractéristiques qui décrivent les sujets.
- Chaque colonne stocke un certain type de données (entier, chaîne, date...).
Bien qu’il soit formidable de stocker et de visualiser des données, lorsque vous devez rechercher une valeur spécifique, c’est nul.
Par exemple, si vous voulez trouver tous les gars qui travaillent au Royaume-Uni, vous devrez regarder chaque ligne pour savoir si la ligne appartient au Royaume-Uni. Cela vous coûtera N opérations (N étant le nombre de lignes), ce qui n’est pas mal mais pourrait-il y avoir un moyen plus rapide? C’est là que les arbres entrent en jeu.
Remarque : La plupart des bases de données modernes fournissent des tableaux avancés pour stocker efficacement les tables, telles que les tables organisées en tas ou les tables organisées par index. Mais cela ne change pas le problème de la recherche rapide d’une condition spécifique sur un groupe de colonnes.
Index de l’arborescence et de la base de données
Un arbre de recherche binaire est un arbre binaire avec une propriété spéciale, la clé dans chaque nœud doit être:
- supérieure à toutes les clés stockées dans la sous-arborescence de gauche
- plus petite que toutes les clés stockées dans la sous-arborescence de droite
Voyons ce que cela signifie visuellement
L’idée
Cet arbre a N=15 éléments. Disons que je cherche 208:
- Je commence par la racine dont la clé est 136. Depuis 136<208, je regarde le sous-arbre de droite du nœud 136.
- 398>208 donc, je regarde le sous-arbre gauche du nœud 398
- 250>208 donc, je regarde le sous-arbre gauche du nœud 250
- 200<208 donc, je regarde le sous-arbre droit du nœud 200. Mais 200 n’a pas de sous-arbre droit, la valeur n’existe pas (parce que si elle existait, elle serait dans le bon sous-arbre de 200)
Maintenant, disons que je cherche 40
- Je commence par la racine dont la clé est 136. Depuis 136>40, je regarde le sous-arbre gauche du nœud 136.
- 80>40 donc, je regarde le sous-arbre gauche du nœud 80
- 40= 40, le nœud existe. J’extrait l’id de la ligne à l’intérieur du nœud (ce n’est pas dans la figure) et regarde la table pour l’ID de ligne donné.
- Connaître l’ID de ligne me permet de savoir où se trouvent précisément les données sur la table et donc je peux les obtenir instantanément.
En fin de compte, les deux recherches m’ont coûté le nombre de niveaux à l’intérieur de l’arbre. Si vous lisez attentivement la partie sur le tri de fusion, vous devriez voir qu’il y a des niveaux log(N). Donc le coût de la recherche est log(N), pas mal !
Retour à notre problème
Mais ce truc est très abstrait, alors revenons à notre problème. Au lieu d’un entier stupide, imaginez la chaîne qui représente le pays de quelqu’un dans la table précédente. Supposons que vous ayez une arborescence qui contient la colonne « pays » de la table :
- Si vous voulez savoir qui travaille au Royaume-Uni
- vous regardez l’arbre pour obtenir le nœud qui représente le Royaume-Uni
- à l’intérieur du « nœud Royaume-Uni », vous trouverez les emplacements des rangées des travailleurs britanniques.
Cette recherche ne vous coûte que les opérations log(N) au lieu de N opérations si vous utilisez directement le tableau. Ce que vous venez d’imaginer était un index de base de données.
Vous pouvez construire un index arborescent pour n’importe quel groupe de colonnes (une chaîne, un entier, 2 chaînes, un entier et une chaîne, une date...) tant que vous avez une fonction pour comparer les clés (c’est-à-dire le groupe de colonnes) afin que vous puissiez établir un ordre entre les clés (ce qui est le cas pour tous les types de base dans une base de données).
Index B+Arborescence
Bien que cet arbre fonctionne bien pour obtenir une valeur spécifique, il y a un GROS problème lorsque vous devez obtenir plusieurs éléments entre deux valeurs. Cela coûtera O(N) car vous devrez regarder chaque nœud de l’arbre et vérifier s’il se trouve entre ces 2 valeurs (par exemple, avec une traversée dans l’ordre de l’arbre). De plus, cette opération n’est pas conviviale pour les E/S du disque car vous devrez lire l’arborescence complète. Nous devons trouver un moyen d’effectuer efficacement une requête de plage. Pour résoudre ce problème, les bases de données modernes utilisent une version modifiée de l’arborescence précédente appelée B+Tree. Dans un arbre B+ :
- seuls les nœuds les plus bas (les feuilles) stockent des informations (l’emplacement des lignes dans la table associée)
- Les autres nœuds sont juste là pour acheminer vers le bon nœud pendant la recherche.
Comme vous pouvez le voir, il y a plus de nœuds (deux fois plus). En effet, vous avez des nœuds supplémentaires, les « nœuds de décision » qui vous aideront à trouver le bon nœud (qui stocke l’emplacement des lignes dans la table associée). Mais la complexité de la recherche est toujours dans O(log(N)) (il n’y a qu’un niveau de plus). La grande différence est que les nœuds les plus bas sont liés à leurs successeurs.
Avec cet arbre B+, si vous recherchez des valeurs comprises entre 40 et 100 :
- Il vous suffit de chercher 40 (ou la valeur la plus proche après 40 si 40 n’existe pas) comme vous l’avez fait avec l’arbre précédent.
- Rassemblez ensuite les successeurs de 40 en utilisant les liens directs vers les successeurs jusqu’à ce que vous atteigniez 100.
Disons que vous avez trouvé M successeurs et que l’arbre a N nœuds. La recherche d’un nœud spécifique coûte log(N) comme l’arborescence précédente. Mais, une fois que vous avez ce nœud, vous obtenez les successeurs M dans les opérations M avec les liens vers leurs successeurs. Cette recherche ne coûte que les opérations M + log(N) par rapport aux opérations N avec l’arbre précédent. De plus, vous n’avez pas besoin de lire l’arborescence complète (juste les nœuds M + log(N)), ce qui signifie moins d’utilisation du disque. Si M est faible (comme 200 lignes) et N grand (1 000 000 lignes), cela fait une GRANDE différence.
Mais il y a de nouveaux problèmes (encore !). Si vous ajoutez ou supprimez une ligne dans une base de données (et donc dans l’index B+Tree associé) :
- vous devez garder l’ordre entre les nœuds à l’intérieur de l’arbre B + sinon vous ne pourrez pas trouver de nœuds à l’intérieur du désordre.
- vous devez garder le plus petit nombre possible de niveaux dans l’arbre B+ sinon la complexité temporelle dans O(log(N)) deviendra O(N).
En d’autres termes, l’arbre B + doit être auto-ordonné et auto-équilibré. Heureusement, cela est possible avec des opérations intelligentes de suppression et d’insertion. Mais cela a un coût : l’insertion et la suppression dans un arbre B+ sont dans O(log(N)). C’est pourquoi certains d’entre vous ont entendu dire que l’utilisation d’un trop grand nombre d’index n’est pas une bonne idée. En effet, vous ralentissez l’insertion/mise à jour/suppression rapide d’une ligne dans une table puisque la base de données doit mettre à jour les index de la table avec une opération coûteuse O(log(N)) par index. De plus, l’ajout d’index signifie plus de charge de travail pour le gestionnaire de transactions (nous verrons ce gestionnaire à la fin de l’article).
Pour plus de détails, vous pouvez consulter l’article de Wikipedia sur B+Tree. Si vous voulez un exemple d’implémentation B+Tree dans une base de données, consultez cet article et cet article d’un développeur principal de MySQL. Ils se concentrent tous deux sur la façon dont innoDB (le moteur de MySQL) gère les index.
Note: Un lecteur m’a dit que, en raison des optimisations de bas niveau, l’arbre B + doit être entièrement équilibré.
Table de hachage
Notre dernière structure de données importante est la table de hachage. C’est très utile lorsque vous souhaitez rechercher rapidement des valeurs. De plus, la compréhension de la table de hachage nous aidera plus tard à comprendre une opération de jointure de base de données commune appelée jointure par hachage. Cette structure de données est également utilisée par une base de données pour stocker des éléments internes (comme la table de verrouillage ou le pool de tampons, nous verrons les deux concepts plus tard)
La table de hachage est une structure de données qui trouve rapidement un élément avec sa clé. Pour créer une table de hachage, vous devez définir :
- Une clé pour vos éléments
- une fonction de hachage pour les clés. Les hachages calculés des clés donnent les emplacements des éléments (appelés compartiments).
- une fonction pour comparer les touches. Une fois que vous avez trouvé le bon compartiment, vous devez trouver l’élément que vous recherchez à l’intérieur du compartiment en utilisant cette comparaison.
Un exemple simple
Prenons un exemple visuel :
Cette table de hachage comporte 10 compartiments. Comme je suis paresseux je n’ai dessiné que 5 seaux mais je sais que vous êtes intelligent alors je vous laisse imaginer les 5 autres. La fonction Hash que j’ai utilisée est le modulo 10 de la clé. En d’autres termes je ne garde que le dernier chiffre de la clé d’un élément pour trouver son compartiment :
- si le dernier chiffre est 0, l’élément se retrouve dans le compartiment 0,
- si le dernier chiffre est 1, l’élément se retrouve dans le compartiment 1,
- si le dernier chiffre est 2, l’élément se retrouve dans le compartiment 2,
- ...
La fonction de comparaison que j’ai utilisée est simplement l’égalité entre 2 entiers.
Disons que vous voulez obtenir l’élément 78:
- La table de hachage calcule le code de hachage pour 78 qui est 8.
- Il regarde dans le seau 8, et le premier élément qu’il trouve est 78.
- Il vous redonne l’élément 78
- La recherche ne coûte que 2 opérations (1 pour calculer la valeur de hachage et l’autre pour trouver l’élément à l’intérieur du compartiment).
Maintenant, disons que vous voulez obtenir l’élément 59:
- La table de hachage calcule le code de hachage pour 59 qui est 9.
- Il regarde dans le seau 9, et le premier élément qu’il trouve est 99. Puisque 99!=59, l’élément 99 n’est pas le bon élément.
- En utilisant la même logique, il examine le deuxième élément (9), le troisième (79), ... et le dernier (29).
- L’élément n’existe pas.
- La recherche coûte 7 opérations.
Une bonne fonction de hachage
Comme vous pouvez le constater, selon la valeur que vous recherchez, le coût n’est pas le même!
Si je change maintenant la fonction de hachage avec le modulo 1 000 000 de la clé (c’est-à-dire en prenant les 6 derniers chiffres), la deuxième recherche ne coûte que 1 opération car il n’y a pas d’éléments dans le compartiment 000059. Le vrai défi est de trouver une bonne fonction de hachage qui créera des compartiments contenant une très petite quantité d’éléments.
Dans mon exemple, trouver une bonne fonction de hachage est facile. Mais ceci est un exemple simple, trouver une bonne fonction de hachage est plus difficile lorsque la clé est:
- une chaîne (par exemple, le nom de famille d’une personne)
- 2 chaînes (par exemple le nom et le prénom d’une personne)
- 2 chaînes et une date (par exemple le nom, le prénom et la date de naissance d’une personne)
- ...
Avec une bonne fonction de hachage, la recherche dans une table de hachage est en O(1).
Tableau vs table de hachage
Pourquoi ne pas utiliser un tableau ?
Hum, vous posez une bonne question.
- Une table de hachage peut être à moitié chargée en mémoire et les autres compartiments peuvent rester sur le disque.
- Avec un tableau, vous devez utiliser un espace contigu en mémoire. Si vous chargez une grande table, il est très difficile d’avoir suffisamment d’espace contigu.
- Avec une table de hachage, vous pouvez choisir la clé que vous voulez (par exemple le pays ET le nom de famille d’une personne).
Pour plus d’informations, vous pouvez lire mon article sur la Java HashMap qui est une implémentation efficace de table de hachage; vous n’avez pas besoin de comprendre Java pour comprendre les concepts de cet article.
Vue d’ensemble globale
Nous venons de voir les composants de base à l’intérieur d’une base de données. Nous devons maintenant prendre du recul pour avoir une vue d’ensemble.
Une base de données est un ensemble d’informations facilement accessibles et modifiables. Mais un simple tas de fichiers pourrait faire la même chose. En fait, les bases de données les plus simples comme SQLite ne sont rien de plus qu’un tas de fichiers. Mais SQLite est un tas de fichiers bien conçu car il vous permet de:
- Utiliser des transactions qui garantissent la sécurité et la cohérence des données
- Traitez rapidement les données, même lorsque vous traitez des millions de données
Plus généralement, une base de données peut être vue comme la figure suivante :
Avant d’écrire cette partie, j’ai lu plusieurs livres / articles et chaque source était sur le point de représenter une base de données. Donc, ne vous concentrez pas trop sur la façon dont j’ai organisé cette base de données ou comment j’ai nommé les processus parce que j’ai fait quelques choix pour correspondre au plan de cet article. Ce qui compte, ce sont les différentes composantes; L’idée générale est qu’une base de données est divisée en plusieurs composants qui interagissent les uns avec les autres.
Les composants de base :
- Le gestionnaire de processus : De nombreuses bases de données ont un pool de processus/threads qui doivent être gérés. De plus, afin de gagner des nanosecondes, certaines bases de données modernes utilisent leurs propres threads au lieu des threads du système d’exploitation.
- Le gestionnaire de réseau : Les E/S réseau sont un gros problème, en particulier pour les bases de données distribuées. C’est pourquoi certaines bases de données ont leur propre gestionnaire.
- Gestionnaire de système de fichiers : les E/S disque constituent le premier goulot d’étranglement d’une base de données. Avoir un gestionnaire qui gérera parfaitement le système de fichiers du système d’exploitation ou même le remplacera est important.
- Le gestionnaire de mémoire : Pour éviter la pénalité d’E/S disque, une grande quantité de RAM est nécessaire. Mais si vous gérez une grande quantité de mémoire, vous avez besoin d’un gestionnaire de mémoire efficace. Surtout lorsque vous avez de nombreuses requêtes utilisant la mémoire en même temps.
- Security Manager : pour gérer l’authentification et les autorisations des utilisateurs
- Gestionnaire de clients : pour gérer les connexions client
- ...
Les outils :
- Gestionnaire de sauvegarde : pour enregistrer et restaurer une base de données.
- Gestionnaire de récupération : pour redémarrer la base de données dans un état cohérent après un crash
- Gestionnaire de moniteurs: pour enregistrer l’activité de la base de données et fournir des outils pour surveiller une base de données
- Responsable de l’administration : pour stocker les métadonnées (comme les noms et les structures des tables) et fournir des outils pour gérer les bases de données, schémas, tablespaces, ...
- ...
Le gestionnaire de requêtes :
- Analyseur de requêtes : pour vérifier si une requête est valide
- Réscripteur de requête : pour pré-optimiser une requête
- Optimiseur de requête : pour optimiser une requête
- Exécuteur de requête : pour compiler et exécuter une requête
Le gestionnaire de données :
- Gestionnaire de transactions : pour gérer les transactions
- Gestionnaire de cache: pour mettre les données en mémoire avant de les utiliser et mettre les données en mémoire avant de les écrire sur le disque
- Gestionnaire d’accès aux données : pour accéder aux données sur disque
Pour le reste de cet article, je vais me concentrer sur la façon dont une base de données gère une requête SQL via les processus suivants :
- Le gestionnaire de clientèle
- Le gestionnaire de requêtes
- le gestionnaire de données (j’inclurai également le gestionnaire de récupération dans cette partie)
Gestionnaire de clientèle
Le gestionnaire de clientèle est la partie qui gère les communications avec le client. Le client peut être un serveur (web) ou un utilisateur final/application finale. Le gestionnaire de clients fournit différentes façons d’accéder à la base de données via un ensemble d’API bien connues: JDBC, ODBC, OLE-DB ...
Il peut également fournir des API d’accès à la base de données propriétaires.
Lorsque vous vous connectez à une base de données :
- Le gestionnaire vérifie d’abord votre authentification (votre identifiant et votre mot de passe), puis vérifie si vous disposez des autorisations pour utiliser la base de données. Ces droits d’accès sont définis par votre administrateur de base de données.
- Ensuite, il vérifie s’il existe un processus (ou un thread) disponible pour gérer votre requête.
- Il vérifie également si la base de données n’est pas soumise à une charge importante.
- Il peut attendre un moment pour obtenir les ressources requises. Si cette attente atteint un délai d’attente, elle ferme la connexion et affiche un message d’erreur lisible.
- Ensuite, il envoie votre requête au gestionnaire de requêtes et votre requête est traitée
- Étant donné que le traitement des requêtes n’est pas une chose « tout ou rien », dès qu’il obtient des données du gestionnaire de requêtes, il stocke les résultats partiels dans un tampon et commence à vous les envoyer.
- En cas de problème, il arrête la connexion, vous donne une explication lisible et libère les ressources.
Gestionnaire de requêtes
C’est dans cette partie que réside la puissance d’une base de données. Au cours de cette partie, une requête mal écrite est transformée en un code exécutable rapide. Le code est ensuite exécuté et les résultats sont renvoyés au gestionnaire de clients. Il s’agit d’une opération en plusieurs étapes :
- La requête est d’abord analysée pour voir si elle est valide
- Il est ensuite réécrit pour supprimer les opérations inutiles et ajouter quelques pré-optimisations
- Il est ensuite optimisé pour améliorer les performances et transformé en un plan d’exécution et d’accès aux données.
- Ensuite, le plan est compilé
- Enfin, il est exécuté
Dans cette partie, je ne parlerai pas beaucoup des 2 derniers points car ils sont moins importants.
Après avoir lu cette partie, si vous voulez une meilleure compréhension, je vous recommande de lire:
- Le document de recherche initial (1979) sur l’optimisation basée sur les coûts: Sélection du chemin d’accès dans un système de gestion de base de données relationnelle. Cet article ne fait que 12 pages et est compréhensible avec un niveau moyen en informatique.
- Une très bonne présentation détaillée sur la façon dont DB2 9.X optimise les requêtes ici
- Une très bonne présentation sur la façon dont PostgreSQL optimise les requêtes ici. C’est le document le plus accessible car il s’agit plus d’une présentation sur « voyons quels plans de requête PostgreSQL donne dans ces situations » qu’un « voyons les algorithmes utilisés par PostgreSQL ».
- La documentation officielle SQLite sur l’optimisation. Il est « facile » à lire car SQLite utilise des règles simples. De plus, c’est la seule documentation officielle qui explique vraiment comment cela fonctionne.
- Une bonne présentation sur la façon dont SQL Server 2005 optimise les requêtes ici
- Un livre blanc sur l’optimisation dans Oracle 12c ici
- 2 cours théoriques sur l’optimisation des requêtes des auteurs du livre « DATABASE SYSTEM CONCEPTS » ici et tici. Une bonne lecture qui se concentre sur le coût des E/S du disque, mais un bon niveau en CS est requis.
- Un autre cours théorique que je trouve plus accessible mais qui ne se concentre que sur les opérateurs de jointure et les E/S disque.
Analyseur de requêtes
Chaque instruction SQL est envoyée à l’analyseur où sa syntaxe est vérifiée. Si vous avez fait une erreur dans votre requête, l’analyseur rejettera la requête. Par exemple, si vous avez écrit « SLECT ... » au lieu de « SELECT ... », l’histoire se termine ici.
Mais cela va plus loin. Il vérifie également que les mots-clés sont utilisés dans le bon ordre. Par exemple, un WHERE avant un SELECT sera rejeté.
Ensuite, les tables et les champs à l’intérieur de la requête sont analysés. L’analyseur utilise les métadonnées de la base de données pour vérifier :
- Si les tables existent
- Si les champs des tables existent
- Si les opérations pour les types de champs sont possibles (par exemple, vous ne pouvez pas comparer un entier avec une chaîne, vous ne pouvez pas utiliser une fonction substring() sur un entier)
Ensuite, il vérifie si vous avez les autorisations pour lire (ou écrire) les tables dans la requête. Là encore, ces droits d’accès sur les tables sont définis par votre administrateur de base de données.
Au cours de cette analyse, la requête SQL est transformée en une représentation interne (souvent une arborescence)
Si tout va bien, la représentation interne est envoyée au réscripteur de requête.
Réscripteur de requêtes
À cette étape, nous avons une représentation interne d’une requête. L’objectif du réscripteur est :
- Pour pré-optimiser la requête
- pour éviter les opérations inutiles
- pour aider l’optimiseur à trouver la meilleure solution possible
Le rédacteur exécute une liste de règles connues sur la requête. Si la requête correspond à un modèle d’une règle, la règle est appliquée et la requête est réécrite. Voici une liste non exhaustive de règles (facultatives) :
- Fusion de vues : Si vous utilisez une vue dans votre requête, la vue est transformée avec le code SQL de la vue.
- Aplatissement des sous-requêtes : Il est très difficile d’optimiser les sous-requêtes, de sorte que le réscripteur essaiera de modifier une requête avec une sous-requête pour supprimer la sous-requête.
Par exemple
SELECT PERSON.*
FROM PERSON
WHERE PERSON.person_key IN
(SELECT MAILS.person_key
FROM MAILS
WHERE MAILS.mail LIKE 'christophe%');
Sera remplacé par
SELECT PERSON.*
FROM PERSON, MAILS
WHERE PERSON.person_key = MAILS.person_key
and MAILS.mail LIKE 'christophe%';
- Suppression des opérateurs inutiles : Par exemple, si vous utilisez une contrainte DISTINCT alors que vous avez une contrainte UNIQUE qui empêche les données d’être non uniques, le mot-clé DISTINCT est supprimé.
- Élimination des jointures redondantes : Si vous avez deux fois la même condition de jointure parce qu’une condition de jointure est masquée dans une vue ou si, par transitivité, il y a une jointure inutile, elle est supprimée.
- Évaluation arithmétique constante: Si vous écrivez quelque chose qui nécessite un calcul, il est calculé une fois pendant la réécriture. Par exemple, WHERE AGE > 10+2 est transformé en WHERE AGE > 12 et TODATE(« une date ») est transformé en date au format datetime
- (Avancé) Élagage de partition: Si vous utilisez une table partitionnée, le réscripteur est en mesure de trouver les partitions à utiliser.
- (Avancé) Réécriture de vue matérialisée : si vous disposez d’une vue matérialisée qui correspond à un sous-ensemble des prédicats de votre requête, le réscripteur vérifie si la vue est à jour et modifie la requête pour utiliser la vue matérialisée au lieu des tables brutes.
- Règles personnalisées (avancées) : Si vous avez des règles personnalisées pour modifier une requête (comme les stratégies Oracle), le réscripteur exécute ces règles
- Transformations Olap (avancées) : fonctions analytiques/fenêtrage, jointures en étoile, rollup... sont également transformés (mais je ne sais pas si c’est fait par le réscripteur ou l’optimiseur, puisque les deux processus sont très proches, cela doit dépendre de la base de données).
Cette requête réécrite est ensuite envoyée à l’optimiseur de requête où le plaisir commence!
Statistiques
Avant de voir comment une base de données optimise une requête, nous devons parler de statistiques car sans elles, une base de données est stupide. Si vous ne dites pas à la base de données d’analyser ses propres données, elle ne le fera pas et elle fera de (très) mauvaises hypothèses.
Mais de quel type d’informations une base de données a-t-elle besoin ?
Je dois (brièvement) parler de la façon dont les bases de données et les systèmes d’exploitation stockent les données. Ils utilisent une unité minimale appelée page ou bloc (4 ou 8 kilo-octets par défaut). Cela signifie que si vous n’avez besoin que de 1 Ko, cela vous coûtera de toute façon une page. Si la page prend 8 Ko, vous gaspillerez 7 Ko.
Retour aux statistiques! Lorsque vous demandez à une base de données de collecter des statistiques, elle calcule des valeurs telles que :
- Le nombre de lignes/pages d’un tableau
- Pour chaque colonne d’une table :
- Valeurs de données distinctes
- la longueur des valeurs de données (min, max, moyenne)
- Informations sur la plage de données (min, max, moyenne)
- Informations sur les index de la table.
Ces statistiques aideront l’optimiseur à estimer les utilisations des E/S disque, du processeur et de la mémoire de la requête.
Les statistiques de chaque colonne sont très importantes. Par exemple, si une table PERSON doit être jointe sur 2 colonnes : LAST_NAME, FIRST_NAME. Avec les statistiques, la base de données sait qu’il n’y a que 1 000 valeurs différentes sur FIRST_NAME et 1 000 000 de valeurs différentes sur LAST_NAME. Par conséquent, la base de données joindra les données sur LAST_NAME, FIRST_NAME au lieu de FIRST_NAME,LAST_NAME car elle produit beaucoup moins de comparaisons puisque les LAST_NAME sont peu susceptibles d’être les mêmes, donc la plupart du temps une comparaison sur les 2 (ou 3) premiers caractères de la LAST_NAME suffit.
Mais ce sont des statistiques de base. Vous pouvez demander à une base de données de calculer des statistiques avancées appelées histogrammes. Les histogrammes sont des statistiques qui informent sur la distribution des valeurs à l’intérieur des colonnes. Par exemple
- Les valeurs les plus fréquentes
- Les quantiles
- ...
Ces statistiques supplémentaires aideront la base de données à trouver un plan de requête encore meilleur. Surtout pour les prédicats d’égalité (ex : WHERE AGE = 18 ) ou les prédicats de plage (ex : WHERE AGE > 10 et AGE <40 ) car la base de données aura une meilleure idée des lignes numériques concernées par ces prédicats (note : le mot technique pour ce concept est sélectivité).
Les statistiques sont stockées dans les métadonnées de la base de données. Par exemple, vous pouvez voir les statistiques des tables (non partitionnées) :
- dans USER/ALL/DBA_TABLES et USER/ALL/DBA_TAB_COLUMNS pour Oracle
- dans SYSCAT. TABLES et SYSCAT. COLONNES pour DB2.
Les statistiques doivent être à jour. Il n’y a rien de pire qu’une base de données qui pense qu’une table n’a que 500 lignes alors qu’elle en a 1 000 000. Le seul inconvénient des statistiques est qu’il faut du temps pour les calculer. C’est pourquoi ils ne sont pas calculés automatiquement par défaut dans la plupart des bases de données. Il devient difficile avec des millions de données de les calculer. Dans ce cas, vous pouvez choisir de calculer uniquement les statistiques de base ou de calculer les statistiques sur un échantillon de la base de données.
Par exemple, lorsque je travaillais sur un projet traitant de centaines de millions de lignes dans chaque table, j’ai choisi de calculer les statistiques sur seulement 10%, ce qui a entraîné un gain de temps énorme. Pour l’histoire, cela s’est avéré être une mauvaise décision car parfois les 10% choisis par Oracle 10G pour une colonne spécifique d’une table spécifique étaient très différents des 100% globaux (ce qui est très peu probable pour une table avec 100 millions de lignes). Cette statistique erronée a conduit à une requête prenant parfois 8 heures au lieu de 30 secondes; Un cauchemar pour trouver la cause profonde. Cet exemple montre à quel point les statistiques sont importantes.
Note : Bien sûr, il existe des statistiques plus avancées spécifiques à chaque base de données. Si vous voulez en savoir plus, lisez les documentations des bases de données. Cela étant dit, j’ai essayé de comprendre comment les statistiques sont utilisées et la meilleure documentation officielle que j’ai trouvée était celle de PostgreSQL.
Optimiseur de requêtes
Toutes les bases de données modernes utilisent une optimisation basée sur les coûts (ou CBO) pour optimiser les requêtes. L’idée est de mettre un coût à chaque opération et de trouver le meilleur moyen de réduire le coût de la requête en utilisant la chaîne d’opérations la moins chère pour obtenir le résultat.
Pour comprendre comment fonctionne un optimiseur de coûts, je pense qu’il est bon d’avoir un exemple pour « sentir » la complexité derrière cette tâche. Dans cette partie je vais vous présenter les 3 façons courantes de joindre 2 tables et nous verrons rapidement que même une simple requête de jointure est un cauchemar à optimiser. Après cela, nous verrons comment les vrais optimiseurs font ce travail.
Pour ces jointures, je me concentrerai sur leur complexité temporelle, mais un optimiseur de base de données calcule leur coût CPU, leur coût d’E/S disque et leurs besoins en mémoire. La différence entre la complexité du temps et le coût du processeur est que le coût du temps est très approximatif (c’est pour les paresseux comme moi). Pour le coût CPU, je devrais compter chaque opération comme un ajout, un « if statement », une multiplication, une itération ... En outre:
- Chaque opération de code de haut niveau a un nombre spécifique d’opérations CPU de bas niveau.
- Le coût d’une opération CPU n’est pas le même (en termes de cycles CPU) que vous utilisiez un Intel Core i7, un Intel Pentium 4, un AMD Opteron.... En d’autres termes, cela dépend de l’architecture du processeur.
Utiliser la complexité temporelle est plus facile (du moins pour moi) et avec elle, nous pouvons toujours obtenir le concept de CBO. Je parlerai parfois d’E/S disque car c’est un concept important. Gardez à l’esprit que le goulot d’étranglement est la plupart du temps l’E/S du disque et non l’utilisation du processeur.
Index
Nous avons parlé d’index lorsque nous avons vu les B+Trees. N’oubliez pas que ces index sont déjà triés.
Pour info, il existe d’autres types d’index comme les index bitmap. Ils n’offrent pas le même coût en termes de CPU, d’E/S disque et de mémoire que les index B+Tree.
En outre, de nombreuses bases de données modernes peuvent créer dynamiquement des index temporaires uniquement pour la requête en cours si cela peut améliorer le coût du plan d’exécution.
Chemin d’accès
Avant d’appliquer vos opérateurs de jointure, vous devez d’abord obtenir vos données. Voici comment vous pouvez obtenir vos données.
Remarque: Puisque le vrai problème avec tous les chemins d’accès est les E/S du disque, je ne parlerai pas beaucoup de la complexité temporelle.
Analyse complète
Si vous avez déjà lu un plan d’exécution, vous devez avoir vu le mot analyse complète (ou simplement numériser). Une analyse complète est simplement la base de données lisant une table ou un index entièrement. En termes d’E/S disque, une analyse complète de table est évidemment plus coûteuse qu’une analyse complète d’index.
Analyse de plage
Il existe d’autres types d’analyse comme l’analyse de la plage d’index. Il est utilisé par exemple lorsque vous utilisez un prédicat comme « WHERE AGE > 20 AND AGE <40 ».
Bien sûr, vous devez avoir un index sur le champ AGE pour utiliser ce balayage de plage d’index.
Nous avons déjà vu dans la première partie que le coût en temps d’une requête de plage est quelque chose comme log(N) + M, où N est le nombre de données dans cet index et M une estimation du nombre de lignes à l’intérieur de cette plage. Les valeurs N et M sont connues grâce aux statistiques (Note: M est la sélectivité pour le prédicat AGE >20 ET AGE<40). De plus, pour une analyse de plage, vous n’avez pas besoin de lire l’index complet, ce qui est moins coûteux en termes d’E/S disque qu’une analyse complète.
Analyse unique
Si vous n’avez besoin que d’une seule valeur d’un index, vous pouvez utiliser l’analyse unique.
Accès par ID de ligne
La plupart du temps, si la base de données utilise un index, elle devra rechercher les lignes associées à l’index. Pour ce faire, il utilisera un accès par ID de ligne.
Par exemple, si vous faites quelque chose comme
SELECT LASTNAME, FIRSTNAME from PERSON WHERE AGE = 28
Si vous avez un index pour la personne sur l’âge de la colonne, l’optimiseur utilisera l’index pour trouver toutes les personnes qui ont 28 ans, puis il demandera les lignes associées dans la table car l’index ne contient que des informations sur l’âge et vous voulez connaître le nom et le prénom.
Mais, si maintenant vous faites quelque chose comme
SELECT TYPE_PERSON.CATEGORY from PERSON ,TYPE_PERSON
WHERE PERSON.AGE = TYPE_PERSON.AGE
L’index sur PERSON sera utilisé pour joindre TYPE_PERSON mais la table PERSON ne sera pas accessible par ID de ligne car vous ne demandez pas d’informations sur cette table.
Bien que cela fonctionne très bien pour quelques accès, le vrai problème avec cette opération est les E/S disque. Si vous avez besoin d’un trop grand nombre d’accès par ID de ligne, la base de données peut choisir une analyse complète.
Autres chemins
Je n’ai pas présenté tous les chemins d’accès. Si vous voulez en savoir plus, vous pouvez lire la documentation Oracle. Les noms peuvent ne pas être les mêmes pour les autres bases de données, mais les concepts sous-jacents sont les mêmes.
Rejoindre les opérateurs
Alors, nous savons comment obtenir nos données, rejoignons-les!
Je vais présenter les 3 opérateurs de jointure courants: Merge Join, Hash Join et Nested Loop Join. Mais avant cela, je dois introduire un nouveau vocabulaire : relation intérieure et relation extérieure. Une relation peut être:
- une table
- un indice
- un résultat intermédiaire d’une opération précédente (par exemple le résultat d’une jointure précédente)
Lorsque vous joignez deux relations, les algorithmes de jointure gèrent les deux relations différemment. Dans le reste de l’article, je supposerai que:
- La relation externe est l’ensemble de données gauche
- La relation interne est le bon ensemble de données
Par exemple, A JOIN B est la jointure entre A et B où A est la relation externe et B la relation interne.
La plupart du temps, le coût de A JOIN B n’est pas le même que le coût de B JOIN A.
Dans cette partie, je supposerai également que la relation extérieure a N éléments et la relation interne M éléments. Gardez à l’esprit qu’un véritable optimiseur connaît les valeurs de N et M avec les statistiques.
Note: N et M sont les cardinalités des relations.
Jointure en boucle imbriquée
La jointure par boucle imbriquée est la plus simple.
Voici l’idée :
- pour chaque ligne de la relation externe
- Vous examinez toutes les lignes de la relation interne pour voir s’il y a des lignes qui correspondent
Voici un pseudo code :
nested_loop_join(array outer, array inner)
for each row a in outer
for each row b in inner
if (match_join_condition(a,b))
write_result_in_output(a,b)
end if
end for
end for
Comme il s’agit d’une double itération, la complexité temporelle est O(N*M)
En termes d’E/S disque, pour chacune des N lignes de la relation externe, la boucle interne doit lire M lignes de la relation interne. Cet algorithme doit lire les lignes N + N * M du disque. Mais, si la relation interne est suffisamment petite, vous pouvez mettre la relation en mémoire et simplement avoir M + N lit. Avec cette modification, la relation interne doit être la plus petite car elle a plus de chance de tenir dans la mémoire.
En termes de complexité temporelle, cela ne fait aucune différence, mais en termes d’E/S disque, il est préférable de ne lire qu’une seule fois les deux relations.
Bien sûr, la relation interne peut être remplacée par un index, ce sera mieux pour les E/S disque.
Puisque cet algorithme est très simple, voici une autre version qui est plus conviviale pour les E/S disque si la relation interne est trop grande pour tenir en mémoire. Voici l’idée :
- au lieu de lire les deux relations ligne par ligne,
- vous les lisez bouquet par groupe et gardez 2 paquets de lignes (de chaque relation) en mémoire,
- vous comparez les lignes à l’intérieur des deux grappes et conservez les lignes qui correspondent,
- Ensuite, vous chargez de nouveaux paquets à partir du disque et les comparez
- et ainsi de suite jusqu’à ce qu’il n’y ait plus de grappes à charger.
Voici un algorithme possible :
// improved version to reduce the disk I/O.
nested_loop_join_v2(file outer, file inner)
for each bunch ba in outer
// ba is now in memory
for each bunch bb in inner
// bb is now in memory
for each row a in ba
for each row b in bb
if (match_join_condition(a,b))
write_result_in_output(a,b)
end if
end for
end for
end for
end for
Avec cette version, la complexité temporelle reste la même, mais le nombre d’accès au disque diminue :
- Avec la version précédente, l’algorithme a besoin d’accès N + N * M (chaque accès obtient une ligne).
- Avec cette nouvelle version, le nombre d’accès disque devient number_of_bunches_for(externe)+ number_of_ bunches_for(externe)* number_of_ bunches_for(interne).
- Si vous augmentez la taille du groupe, vous réduisez le nombre d’accès au disque.
Remarque: Chaque accès au disque collecte plus de données que l’algorithme précédent, mais cela n’a pas d’importance puisqu’il s’agit d’accès séquentiels (le vrai problème avec les disques mécaniques est le temps nécessaire pour obtenir les premières données).
Jointure par hachage
La jointure par hachage est plus compliquée mais donne un meilleur coût qu’une jointure par boucle imbriquée dans de nombreuses situations.
L’idée de la jointure par hachage est de :
- 1) Obtenir tous les éléments de la relation interne
- 2) Créer une table de hachage en mémoire
- 3) Obtenez tous les éléments de la relation extérieure un par un
- 4) Calculer le hachage de chaque élément (avec la fonction de hachage de la table de hachage) pour trouver le compartiment associé de la relation interne
- 5) Déterminez s’il y a une correspondance entre les éléments du compartiment et l’élément de la table extérieure
En termes de complexité temporelle, je dois faire quelques hypothèses pour simplifier le problème:
- La relation interne est divisée en X compartiments
- La fonction de hachage distribue les valeurs de hachage presque uniformément pour les deux relations. En d’autres termes, les seaux sont de taille égale.
- La correspondance entre un élément de la relation externe et tous les éléments à l’intérieur d’un compartiment coûte le nombre d’éléments à l’intérieur des compartiments.
La complexité temporelle est (M/X) * N + cost_to_create_hash_table(M) + cost_of_hash_function*N
Si la fonction de hachage crée suffisamment de compartiments de petite taille, la complexité temporelle est O(M+N)
Voici une autre version de la jointure par hachage qui est plus conviviale pour la mémoire mais moins conviviale pour les E/S disque. Cette heure:
- 1) Vous calculez les tables de hachage pour les relations internes et externes
- 2) Ensuite, vous les mettez sur disque
- 3) Ensuite, vous comparez les 2 relations compartiment par compartiment (avec l’un chargé en mémoire et l’autre lu ligne par ligne)
Fusionner la jointure
La jointure de fusion est la seule jointure qui produit un résultat trié.
Remarque : Dans cette jointure de fusion simplifiée, il n’y a pas de tables internes ou externes ; Ils jouent tous les deux le même rôle. Mais les implémentations réelles font la différence, par exemple, lorsqu’il s’agit de doublons.
La jointure de fusion peut être divisée en deux étapes :
- (Facultatif) Trier les opérations de jointure : les deux entrées sont triées sur la ou les clés de jointure.
- Opération de jointure de fusion : les entrées triées sont fusionnées.
Trier
Nous avons déjà parlé du tri de fusion, dans ce cas un tri de fusion dans un bon algorithme (mais pas le meilleur si la mémoire n’est pas un problème).
Mais parfois, les ensembles de données sont déjà triés, par exemple :
- Si la table est classée en mode natif, par exemple une table organisée par index sur la condition de jointure
- Si la relation est un index sur la condition de jointure
- Si cette jointure est appliquée sur un résultat intermédiaire déjà trié au cours du processus de la requête
Fusionner la jointure
Cette partie est très similaire à l’opération de fusion du tri de fusion que nous avons vu. Mais cette fois, au lieu de choisir chaque élément des deux relations, nous ne choisissons que les éléments des deux relations qui sont égaux. Voici l’idée :
- 1) vous comparez les deux éléments actuels dans les 2 relations (current=first pour la première fois)
- 2) S’ils sont égaux, alors vous mettez les deux éléments dans le résultat et vous passez à l’élément suivant pour les deux relations
- 3) Sinon, vous passez à l’élément suivant pour la relation avec l’élément le plus bas (car l’élément suivant peut correspondre)
- 4) et répétez 1,2,3 jusqu’à ce que vous atteigniez le dernier élément de l’une des relations.
Cela fonctionne parce que les deux relations sont triées et que vous n’avez donc pas besoin de « revenir en arrière » dans ces relations.
Cet algorithme est une version simplifiée car il ne gère pas le cas où les mêmes données apparaissent plusieurs fois dans les deux tableaux (en d’autres termes, plusieurs correspondances). La version réelle est plus compliquée « juste » pour ce cas; c’est pourquoi j’ai choisi une version simplifiée.
Si les deux relations sont déjà triées, la complexité temporelle est O(N+M)
Si les deux relations doivent être triées, alors la complexité temporelle est le coût pour trier les deux relations : O(N*Log(N) + M*Log(M))
Pour les geeks CS, voici un algorithme possible qui gère les multiples correspondances (note: je ne suis pas sûr à 100% de mon algorithme):
mergeJoin(relation a, relation b)
relation output
integer a_key:=0;
integer b_key:=0;
while (a[a_key]!=null or b[b_key]!=null)
if (a[a_key] < b[b_key])
a_key++;
else if (a[a_key] > b[b_key])
b_key++;
else //Join predicate satisfied
//i.e. a[a_key] == b[b_key]
//count the number of duplicates in relation a
integer nb_dup_in_a = 1:
while (a[a_key]==a[a_key+nb_dup_in_a])
nb_dup_in_a++;
//count the number of duplicates in relation b
integer dup_in_b = 1:
while (b[b_key]==b[b_key+nb_dup_in_b])
nb_dup_in_b++;
//write the duplicates in output
for (int i = 0 ; i< nb_dup_in_a ; i++)
for (int j = 0 ; i< nb_dup_in_b ; i++)
write_result_in_output(a[a_key+i],b[b_key+j])
a_key=a_key + nb_dup_in_a-1;
b_key=b_key + nb_dup_in_b-1;
end if
end while
Lequel est le meilleur?
S’il y avait un meilleur type de jointures, il n’y aurait pas plusieurs types. Cette question est très difficile car de nombreux facteurs entrent en jeu comme:
- La quantité de mémoire libre : sans assez de mémoire, vous pouvez dire adieu à la puissante jointure par hachage (au moins la jointure de hachage en mémoire complète)
- Taille des 2 ensembles de données. Par exemple, si vous avez une grande table avec une très petite, une jointure par boucle imbriquée sera plus rapide qu’une jointure par hachage car la jointure par hachage a une création coûteuse de hachages. Si vous avez 2 très grandes tables, la jointure par boucle imbriquée sera très coûteuse en CPU.
- La présence d’index. Avec 2 index B+Tree, le choix intelligent semble être la jointure de fusion
- Si le résultat doit être trié : même si vous travaillez avec des ensembles de données non triés, vous pouvez utiliser une jointure de fusion coûteuse (avec les tris) car à la fin, le résultat sera trié et vous pourrez enchaîner le résultat avec une autre jointure de fusion (ou peut-être parce que la requête demande implicitement/explicitement un résultat trié avec une opération ORDER BY/GROUP BY/DISTINCT)
- Si les relations sont déjà triées : Dans ce cas, la jointure de fusion est le meilleur candidat
- Le type de jointures que vous effectuez : s’agit-il d’une équijonction (c’est-à-dire : tableA.col1 = tableB.col2) ? S’agit-il d’une jointure interne, d’une jointure externe, d’un produit cartésien ou d’une auto-jointure ? Certaines jointures ne peuvent pas fonctionner dans certaines situations.
- La distribution des données. Si les données de la condition de jointure sont biaisées (par exemple, vous rejoignez des personnes sur leur nom de famille, mais de nombreuses personnes ont le même), l’utilisation d’une jointure par hachage sera un désastre car la fonction de hachage créera des compartiments mal distribués.
- Si vous souhaitez que la jointure soit exécutée par plusieurs threads/processus
Pour plus d’informations, vous pouvez lire les documentations DB2, ORACLE ou SQL Server.
Exemple simplifié
Nous venons de voir 3 types d’opérations de jointure.
Maintenant, disons que nous devons rejoindre 5 tables pour avoir une vue complète d’une personne. Une PERSONNE peut avoir:
- plusieurs MOBILES
- MAILS multiples
- ADRESSES MULTIPLES
- BANK_ACCOUNTS multiples
En d’autres termes, nous avons besoin d’une réponse rapide pour la requête suivante:
SELECT * from PERSON, MOBILES, MAILS,ADRESSES, BANK_ACCOUNTS
WHERE
PERSON.PERSON_ID = MOBILES.PERSON_ID
AND PERSON.PERSON_ID = MAILS.PERSON_ID
AND PERSON.PERSON_ID = ADRESSES.PERSON_ID
AND PERSON.PERSON_ID = BANK_ACCOUNTS.PERSON_ID
En tant qu’optimiseur de requêtes, je dois trouver la meilleure façon de traiter les données. Mais il y a 2 problèmes :
- Quel type de jointure dois-je utiliser pour chaque jointure ?
J’ai 3 jointures possibles (Hash Join, Merge Join, Nested Join) avec la possibilité d’utiliser 0,1 ou 2 index (sans oublier qu’il existe différents types d’index).
- Quel ordre dois-je choisir pour calculer la jointure ?
Par exemple, la figure suivante montre différents plans possibles pour seulement 3 jointures sur 4 tables
Voici donc mes possibilités:
- 1) J’utilise une approche de force brute
En utilisant les statistiques de la base de données, je calcule le coût de chaque plan possible et je garde le meilleur. Mais il y a beaucoup de possibilités. Pour un ordre donné de jointures, chaque jointure a 3 possibilités : HashJoin, MergeJoin, NestedJoin. Ainsi, pour un ordre donné de jointures, il y a 34 possibilités. L’ordre de jointure est un problème de permutation sur un arbre binaire et il y a (2*4)!/(4+1)! commandes possibles. Pour ce problème très simplifié, je me retrouve avec 3 4*(2*4)!/(4+1)! Possibilités.
En termes non-geek, cela signifie 27 216 plans possibles. Si j’ajoute maintenant la possibilité pour la jointure de fusion de prendre 0,1 ou 2 index B+Tree, le nombre de plans possibles devient 210 000. Ai-je oublié de mentionner que cette requête est TRÈS SIMPLE?
- 2) Je pleure et j’abandonne cet emploi
C’est très tentant, mais vous n’obtiendrez pas votre résultat et j’ai besoin d’argent pour payer les factures.
- 3) Je n’essaie que quelques plans et je prends celui qui coûte le plus cher.
Comme je ne suis pas Superman, je ne peux pas calculer le coût de chaque plan. Au lieu de cela, je peux choisir arbitrairement un sous-ensemble de tous les plans possibles, calculer leurs coûts et vous donner le meilleur plan de ce sous-ensemble.
- 4) J’applique des règles intelligentes pour réduire le nombre de plans possibles.
Il existe 2 types de règles :
Je peux utiliser des règles « logiques » qui élimineront les possibilités inutiles, mais elles ne filtreront pas beaucoup de plans possibles. Par exemple : « la relation interne de la jointure par boucle imbriquée doit être le plus petit ensemble de données »
J’accepte de ne pas trouver la meilleure solution et d’appliquer des règles plus agressives pour réduire beaucoup le nombre de possibilités. Par exemple « Si une relation est petite, utilisez une jointure par boucle imbriquée et n’utilisez jamais une jointure par fusion ou une jointure par hachage »
Dans cet exemple simple, je me retrouve avec de nombreuses possibilités. Mais une requête réelle peut avoir d’autres opérateurs relationnels comme OUTER JOIN, CROSS JOIN, GROUP BY, ORDER BY, PROJECTION, UNION, INTERSECT, DISTINCT ... ce qui signifie encore plus de possibilités.
Alors, comment une base de données fait-elle?
Programmation dynamique, algorithme gourmand et heuristique
Une base de données relationnelle essaie les multiples approches que je viens de dire. Le vrai travail d’un optimiseur est de trouver une bonne solution sur un temps limité.
La plupart du temps, un optimiseur ne trouve pas la meilleure solution mais une « bonne ».
Pour les petites requêtes, il est possible de faire une approche par force brute. Mais il existe un moyen d’éviter les calculs inutiles afin que même les requêtes moyennes puissent utiliser l’approche de la force brute. C’est ce qu’on appelle la programmation dynamique.
Programmation dynamique
L’idée derrière ces 2 mots est que de nombreux plans d’exécution sont très similaires. Si vous regardez les plans suivants:
Ils partagent le même sous-arbre (A JOIN B). Ainsi, au lieu de calculer le coût de ce sous-arbre dans chaque plan, nous pouvons le calculer une fois, enregistrer le coût calculé et le réutiliser lorsque nous voyons à nouveau ce sous-arbre. Plus formellement, nous sommes confrontés à un problème de chevauchement. Pour éviter le calcul supplémentaire des résultats partiels, nous utilisons la mémorisation.
En utilisant cette technique, au lieu d’avoir un (2*N)!/(N+1)! complexité temporelle, nous avons « juste » 3N. Dans notre exemple précédent avec 4 jointures, cela signifie passer de 336 commandes à 81. Si vous prenez une requête plus importante avec 8 jointures (ce qui n’est pas gros), cela signifie passer de 57 657 600 à 6561.
Pour les geeks CS, voici un algorithme que j’ai trouvé sur le cours formel que je vous ai déjà donné. Je ne vais pas expliquer cet algorithme alors lisez-le seulement si vous connaissez déjà la programmation dynamique ou si vous êtes bon avec les algorithmes (vous êtes prévenus!) :
procedure findbestplan(S)
if (bestplan[S].cost infinite)
return bestplan[S]
// else bestplan[S] has not been computed earlier, compute it now
if (S contains only 1 relation)
set bestplan[S].plan and bestplan[S].cost based on the best way
of accessing S /* Using selections on S and indices on S */
else for each non-empty subset S1 of S such that S1 != S
P1= findbestplan(S1)
P2= findbestplan(S - S1)
A = best algorithm for joining results of P1 and P2
cost = P1.cost + P2.cost + cost of A
if cost < bestplan[S].cost
bestplan[S].cost = cost
bestplan[S].plan = “execute P1.plan; execute P2.plan;
join results of P1 and P2 using A”
return bestplan[S]
Pour les requêtes plus importantes, vous pouvez toujours adopter une approche de programmation dynamique, mais avec des règles supplémentaires (ou heuristiques) pour supprimer les possibilités :
- Si nous analysons seulement un certain type de plan (par exemple: les arbres de profondeur gauche), nous nous retrouvons avec n * 2 n au lieu de 3n
- Si nous ajoutons des règles logiques pour éviter les plans pour certains modèles (comme « si une table est un index pour le prédicat donné, n’essayez pas une jointure de fusion sur la table mais uniquement sur l’index »), cela réduira le nombre de possibilités sans nuire à la meilleure solution possible.
- Si nous ajoutons des règles sur le flux (comme « effectuer les opérations de jointure AVANT toutes les autres opérations relationnelles »), cela réduit également beaucoup de possibilités.
- ...
Des algorithmes gourmands
Mais pour une requête très grosse ou pour avoir une réponse très rapide (mais pas une requête très rapide), un autre type d’algorithmes est utilisé, les algorithmes gourmands.
L’idée est de suivre une règle (ou heuristique) pour construire un plan de requête de manière incrémentielle. Avec cette règle, un algorithme gourmand trouve la meilleure solution à un problème une étape à la fois. L’algorithme démarre le plan de requête avec une jointure. Ensuite, à chaque étape, l’algorithme ajoute une nouvelle jointure au plan de requête à l’aide de la même règle.
Prenons un exemple simple. Disons que nous avons une requête avec 4 jointures sur 5 tables (A, B, C, D et E). Pour simplifier le problème, nous prenons simplement la jointure imbriquée comme une jointure possible. Utilisons la règle « utiliser la jointure avec le coût le plus bas »
- nous commençons arbitrairement sur l’une des 5 tables (choisissons A)
- nous calculons le coût de chaque jointure avec A (A étant la relation interne ou externe).
- nous constatons que A JOIN B donne le coût le plus bas.
- Nous calculons ensuite le coût de chaque jointure avec le résultat de A JOINT B (A JOINT B étant la relation interne ou externe).
- nous trouvons que (A JOIN B) JOIN C donne le meilleur coût.
- Nous calculons ensuite le coût de chaque jointure avec le résultat de la jointure (A B) JOINT C ...
- ....
- À la fin, nous trouvons le plan (((A JOINDRE B) JOINDRE C) JOINDRE D) JOINDRE E)
Puisque nous avons arbitrairement commencé avec A, nous pouvons appliquer le même algorithme pour B, puis C puis D puis E. Nous conservons ensuite le plan au coût le plus bas.
Au fait, cet algorithme a un nom: il s’appelle l’algorithme du plus proche voisin.
Je n’entrerai pas dans les détails, mais avec une bonne modélisation et un tri dans N*log(N) ce problème peut facilement être résolu. Le coût de cet algorithme est en O(N*log(N)) vs O(3N) pour la version de programmation dynamique complète. Si vous avez une grosse requête avec 20 jointures, cela signifie 26 vs 3 486 784 401, une GRANDE différence!
Le problème avec cet algorithme est que nous supposons que trouver la meilleure jointure entre 2 tables nous donnera le meilleur coût si nous conservons cette jointure et ajoutons une nouvelle jointure. Mais:
- même si A JOIN B donne le meilleur coût entre A, B et C
- (A JOINDRE C) JOIN B pourrait donner un meilleur résultat que (A JOIN B) JOIN C.
Pour améliorer le résultat, vous pouvez exécuter plusieurs algorithmes gourmands en utilisant différentes règles et garder le meilleur plan.
Autres algorithmes
[Si vous en avez déjà marre des algorithmes, passez à la partie suivante, ce que je vais dire n’est pas important pour le reste de l’article]
Le problème de trouver le meilleur plan possible est un sujet de recherche actif pour de nombreux chercheurs en informatique. Ils essaient souvent de trouver de meilleures solutions pour des problèmes / modèles plus précis. Par exemple
- Si la requête est une jointure en étoile (il s’agit d’un certain type de requête à jointures multiples), certaines bases de données utiliseront un algorithme spécifique.
- Si la requête est une requête parallèle, certaines bases de données utiliseront un algorithme spécifique
- ...
D’autres algorithmes sont également étudiés pour remplacer la programmation dynamique pour les requêtes volumineuses. Les algorithmes gourmands appartiennent à une famille plus large appelée algorithmes heuristiques. Un algorithme gourmand suit une règle (ou heuristique), conserve la solution qu’il a trouvée à l’étape précédente et l'« ajoute » pour trouver la solution pour l’étape en cours. Certains algorithmes suivent une règle et l’appliquent étape par étape, mais ne gardent pas toujours la meilleure solution trouvée à l’étape précédente. Ils sont appelés algorithmes heuristiques.
Par exemple, les algorithmes génétiques suivent une règle mais la meilleure solution de la dernière étape n’est pas souvent retenue :
- Une solution représente un plan de requête complet possible
- Au lieu d’une solution (c’est-à-dire un plan), il y a des solutions P (c’est-à-dire des plans) conservées à chaque étape.
- 0) Les plans de requête P sont créés de manière aléatoire
- 1) Seuls les plans avec les meilleurs coûts sont conservés
- 2) Ces meilleurs plans sont mélangés pour produire des plans de nouvelles P
- 3) Certains des nouveaux plans P sont modifiés aléatoirement
- 4) Les étapes 1,2,3 sont répétées T fois
- 5) Ensuite, vous gardez le meilleur plan des plans P de la dernière boucle.
Plus vous faites de boucles, meilleur sera le plan.
Est-ce magique ? Non, ce sont les lois de la nature : seuls les plus aptes survivent !
Pour info, les algorithmes génétiques sont implémentés dans PostgreSQL mais je n’ai pas pu trouver s’ils sont utilisés par défaut.
Il existe d’autres algorithmes heuristiques utilisés dans les bases de données comme le recuit simulé, l’amélioration itérative, l’optimisation en deux phases... Mais je ne sais pas s’ils sont actuellement utilisés dans les bases de données d’entreprise ou s’ils ne sont utilisés que dans les bases de données de recherche.
Pour plus d’informations, vous pouvez lire l’article de recherche suivant qui présente plus d’algorithmes possibles : Examen des algorithmes pour le problème d’ordre de jointure dans l’optimisation des requêtes de base de données
De vrais optimiseurs
[Vous pouvez passer à la partie suivante, ce que je vais dire n’est pas important]
Mais, tout ce blabla est très théorique. Comme je suis développeur et non chercheur, j’aime les exemples concrets.
Voyons comment fonctionne l’optimiseur SQLite. C’est une base de données légère donc elle utilise une optimisation simple basée sur un algorithme gourmand avec des règles supplémentaires pour limiter le nombre de possibilités :
- SQLite choisit de ne jamais réorganiser les tables dans un opérateur CROSS JOIN
- Les jointures sont implémentées en tant que jointures imbriquées
- Les jointures externes sont toujours évaluées dans l’ordre dans lequel elles se produisent
- ...
- Avant la version 3.8.0, SQLite utilisait l’algorithme gourmand « Nearest Neighbor » lors de la recherche du meilleur plan de requête
Attends un peu... Nous avons déjà vu cet algorithme ! Quelle coïncidence!
- Depuis la version 3.8.0 (sortie en 2015), SQLite utilise l’algorithme gourmand « N Nearest Neighbors » lors de la recherche du meilleur plan de requête
Voyons comment un autre optimiseur fait son travail. IBM DB2 est comme toutes les bases de données d’entreprise, mais je vais me concentrer sur celle-ci car c’est la dernière que j’ai vraiment utilisée avant de passer au Big Data.
Si nous regardons la documentation officielle, nous apprenons que l’optimiseur DB2 vous permet d’utiliser 7 niveaux d’optimisation différents:
- Utilisez des algorithmes gourmands pour les jointures
- 0 – optimisation minimale, utilisez l’analyse d’index et la jointure en boucle imbriquée et évitez la réécriture des requêtes
- 1 – Faible optimisation
- 2 – Optimisation complète
- Utiliser la programmation dynamique pour les jointures
- 3 – Optimisation modérée et approximation approximative
- 5 – optimisation complète, utilise toutes les techniques avec heuristique
- 7 – Optimisation complète similaire à 5, sans heuristique
- 9 – Optimisation maximale Épargner Aucun effort / dépense ne tient compte de toutes les commandes de jointure possibles, y compris les produits cartésiens
On voit que DB2 utilise des algorithmes gourmands et une programmation dynamique. Bien sûr, ils ne partagent pas les heuristiques qu’ils utilisent puisque l’optimiseur de requêtes est la principale puissance d’une base de données.
Pour info, le niveau par défaut est 5. Par défaut, l’optimiseur utilise les caractéristiques suivantes :
- Toutes les statistiques disponibles, y compris les statistiques à valeurs fréquentes et les statistiques quantiles, sont utilisées.
- Toutes les règles de réécriture des requêtes (y compris le routage des tables de requêtes matérialisées) sont appliquées, à l’exception des règles de calcul intensif qui ne sont applicables que dans de très rares cas.
- L’énumération de jointure de programmation dynamique est utilisée, avec :
- Utilisation limitée de la relation interne composite
- Utilisation limitée des produits cartésiens pour les schémas en étoile impliquant des tables de correspondance
- Un large éventail de méthodes d’accès est considéré, y compris la prélecture de liste (note: verra ce que cela signifie), l’indexation ANDing (note: une opération spéciale avec des index) et le routage de table de requête matérialisée.
Par défaut, DB2 utilise une programmation dynamique limitée par des heuristiques pour l’ordre des jointures.
Les autres conditions (GROUP BY, DISTINCT...) sont gérées par des règles simples.
Cache de plan de requête
Étant donné que la création d’un plan prend du temps, la plupart des bases de données stockent le plan dans un cache de plan de requête pour éviter les recalculs inutiles du même plan de requête. C’est un sujet assez important car la base de données doit savoir quand mettre à jour les plans obsolètes. L’idée est de mettre un seuil et si les statistiques d’une table ont changé au-dessus de ce seuil, le plan de requête impliquant cette table est purgé du cache.
Exécuteur de requête
À ce stade, nous avons un plan d’exécution optimisé. Ce plan est compilé pour devenir un code exécutable. Ensuite, s’il y a suffisamment de ressources (mémoire, CPU), il est exécuté par l’exécuteur de requête. Les opérateurs du plan (JOIN, SORT BY...) peuvent être exécutés de manière séquentielle ou parallèle ; C’est à l’exécuteur testamentaire. Pour obtenir et écrire ses données, l’exécuteur de requête interagit avec le gestionnaire de données, qui est la partie suivante de l’article.
Gestionnaire de données
À cette étape, le gestionnaire de requêtes exécute la requête et a besoin des données des tables et des index. Il demande au gestionnaire de données d’obtenir les données, mais il y a 2 problèmes:
- Les bases de données relationnelles utilisent un modèle transactionnel. Ainsi, vous ne pouvez obtenir aucune donnée à tout moment car quelqu’un d’autre pourrait utiliser / modifier les données en même temps.
- La récupération de données est l’opération la plus lente dans une base de données, par conséquent, le gestionnaire de données doit être assez intelligent pour obtenir et conserver les données dans des tampons de mémoire.
Dans cette partie, nous verrons comment les bases de données relationnelles gèrent ces 2 problèmes. Je ne parlerai pas de la façon dont le gestionnaire de données obtient ses données car ce n’est pas le plus important (et cet article est assez long!).
Gestionnaire de cache
Comme je l’ai déjà dit, le principal goulot d’étranglement des bases de données est l’E/S disque. Pour améliorer les performances, les bases de données modernes utilisent un gestionnaire de cache.
Au lieu d’obtenir directement les données du système de fichiers, l’exécuteur de requête demande les données au gestionnaire de cache. Le gestionnaire de cache dispose d’un cache en mémoire appelé pool de mémoires tampons. L’obtention de données à partir de la mémoire accélère considérablement une base de données. Il est difficile de donner un ordre de grandeur car cela dépend de l’opération que vous devez faire :
- accès séquentiel (ex: analyse complète) vs accès aléatoire (ex: accès par ID de ligne),
- Lire vs écrire
et le type de disques utilisés par la base de données :
- Disque dur 7.2k / 10k / 15k rpm
- Ssd
- RAID 1/5/...
mais je dirais que la mémoire est 100 à 100k fois plus rapide que le disque.
Mais, cela conduit à un autre problème (comme toujours avec les bases de données...). Le gestionnaire de cache doit obtenir les données en mémoire AVANT que l’exécuteur de requête ne les utilise ; Sinon, le gestionnaire de requêtes doit attendre les données des disques lents.
Prérécupération
Ce problème est appelé prérécupération. Un exécuteur de requête connaît les données dont il aura besoin car il connaît le flux complet de la requête et a connaissance des données sur le disque avec les statistiques. Voici l’idée :
- Lorsque l’exécuteur de requête traite son premier groupe de données
- Il demande au gestionnaire de cache de précharger le deuxième groupe de données
- Quand il commence à traiter le deuxième groupe de données
- Il demande au CM de précharger le troisième groupe et informe le CM que le premier groupe peut être purgé du cache.
- ...
Le CM stocke toutes ces données dans son pool de tampons. Afin de savoir si une donnée est toujours nécessaire, le gestionnaire de cache ajoute une information supplémentaire sur les données mises en cache (appelée verrou).
Parfois, l’exécuteur de requête ne sait pas de quelles données il aura besoin et certaines bases de données ne fournissent pas cette fonctionnalité. Au lieu de cela, ils utilisent une prélecture spéculative (par exemple: si l’exécuteur de requête a demandé des données 1,3,5, il demandera probablement 7,9,11 dans un proche avenir) ou une prélecture séquentielle (dans ce cas, le CM charge simplement à partir des disques les données contiguës suivantes après celles demandées).
Pour surveiller le fonctionnement de la prélecture, les bases de données modernes fournissent une métrique appelée ratio tampon/cache d’accès. Le taux d’accès indique combien de fois une donnée demandée a été trouvée dans le cache tampon sans nécessiter d’accès au disque.
Remarque : un faible taux d’accès au cache ne signifie pas toujours que le cache fonctionne mal. Pour plus d’informations, vous pouvez lire la documentation Oracle.
Mais, une mémoire tampon est une quantité limitée de mémoire. Par conséquent, il doit supprimer certaines données pour pouvoir en charger de nouvelles. Le chargement et la purge du cache ont un coût en termes d’E/S disque et réseau. Si vous avez une requête qui est souvent exécutée, il ne serait pas efficace de toujours charger puis purger les données utilisées par cette requête. Pour résoudre ce problème, les bases de données modernes utilisent une stratégie de remplacement de la mémoire tampon.
Stratégies de remplacement de la mémoire tampon
La plupart des bases de données modernes (au moins SQL Server, MySQL, Oracle et DB2) utilisent un algorithme RU.
LRU
LRU signifie Least Recently Used. L’idée derrière cet algorithme est de conserver dans le cache les données qui ont été récemment utilisées et, par conséquent, sont plus susceptibles d’être utilisées à nouveau.
Voici un exemple visuel :
Par souci de compréhension, je supposerai que les données dans le tampon ne sont pas verrouillées par des loquets (et peuvent donc être supprimées). Dans cet exemple simple, le buffer peut stocker 3 éléments :
- 1 : le gestionnaire de cache utilise les données 1 et les place dans le tampon vide
- 2 : le CM utilise les données 4 et les met dans le tampon semi-chargé
- 3 : le CM utilise les données 3 et les met dans le tampon semi-chargé
- 4 : le CM utilise les données 9. La mémoire tampon est pleine, donc les données 1 sont supprimées puisqu’il s’agit des dernières données récemment utilisées. Les données 9 sont ajoutées au tampon
- 5 : le CM utilise les données 4. La donnée 4 est déjà dans la mémoire tampon, elle redevient donc la première donnée récemment utilisée.
- 6 : le CM utilise les données 1. La mémoire tampon est pleine, donc la donnée 9 est supprimée car il s’agit des dernières données récemment utilisées. Les données 1 sont ajoutées dans la mémoire tampon
- ...
Cet algorithme fonctionne bien mais il y a quelques limites. Que se passe-t-il s’il y a un scan complet sur une grande table? En d’autres termes, que se passe-t-il lorsque la taille de la table/de l’index est supérieure à la taille de la mémoire tampon ? L’utilisation de cet algorithme supprimera toutes les valeurs précédentes dans le cache alors que les données de l’analyse complète sont susceptibles d’être utilisées une seule fois.
Améliorations
Pour éviter cela, certaines bases de données ajoutent des règles spécifiques. Par exemple, selon la documentation Oracle :
« Pour les tables très volumineuses, la base de données utilise généralement une lecture directe du chemin, qui charge les blocs directement [...], pour éviter de remplir le cache tampon. Pour les tables de taille moyenne, la base de données peut utiliser une lecture directe ou une lecture cache. Si elle décide d’utiliser une lecture de cache, la base de données place les blocs à la fin de la liste LRU pour empêcher l’analyse de nettoyer efficacement le cache tampon.
Il existe d’autres possibilités comme l’utilisation d’une version avancée de LRU appelée LRU-K. Par exemple, SQL Server utilise LRU-K pour K = 2.
Cette idée derrière cet algorithme est de prendre en compte plus d’histoire. Avec le LRU simple (qui est également LRU-K pour K=1), l’algorithme ne prend en compte que la dernière fois que les données ont été utilisées. Avec le LRU-K :
- Il prend en compte les K dernières fois que les données ont été utilisées.
- Un poids est mis sur le nombre de fois que les données ont été utilisées
- Si un tas de nouvelles données est chargé dans le cache, les données anciennes mais souvent utilisées ne sont pas supprimées (car leur poids est plus élevé).
- Mais l’algorithme ne peut pas conserver les anciennes données dans le cache si elles ne sont plus utilisées.
- Ainsi, les poids diminuent avec le temps si les données ne sont pas utilisées.
Le calcul du poids est coûteux et c’est pourquoi SQL Server n’utilise que K=2. Cette valeur fonctionne bien pour une surcharge acceptable.
Pour une connaissance plus approfondie de LRU-K, vous pouvez lire le document de recherche original (1993): The LRU-K page replacement algorithm for database disk buffering.
Autres algorithmes
Bien sûr, il existe d’autres algorithmes pour gérer le cache comme
- 2Q (un algorithme de type LRU-K)
- CLOCK (un algorithme de type LRU-K)
- MRU (le plus récemment utilisé, utilise la même logique que LRU mais avec une autre règle)
- LRFU (le moins récent et fréquemment utilisé)
- ...
Certaines bases de données permettent d’utiliser un autre algorithme que celui par défaut.
Mémoire tampon d’écriture
J’ai seulement parlé des tampons de lecture qui chargent les données avant de les utiliser. Mais dans une base de données, vous avez également des tampons d’écriture qui stockent les données et les vident sur le disque par paquets au lieu d’écrire les données une par une et de produire de nombreux accès au disque unique.
Gardez à l’esprit que les tampons stockent les pages (la plus petite unité de données) et non les lignes (ce qui est une façon logique / humaine de voir les données). Une page dans un pool de mémoires tampons est modifiée si la page a été modifiée et non écrite sur le disque. Il existe plusieurs algorithmes pour décider du meilleur moment pour écrire les pages sales sur le disque, mais c’est fortement lié à la notion de transaction, qui est la partie suivante de l’article.
Gestionnaire de transactions
Enfin et surtout, cette partie concerne le gestionnaire de transactions. Nous verrons comment ce processus garantit que chaque requête est exécutée dans sa propre transaction. Mais avant cela, nous devons comprendre le concept de transactions ACID.
Je suis sous acide
Une transaction ACID est une unité de travail qui assure 4 choses :
- Atomicité : la transaction est « tout ou rien », même si elle dure 10 heures. Si la transaction se bloque, l’état revient à avant la transaction (la transaction est annulée).
- Isolation : si 2 transactions A et B s’exécutent en même temps, le résultat des transactions A et B doit être le même, que A se termine avant/après/pendant la transaction B.
- Durabilité : une fois la transaction validée (c’est-à-dire terminée avec succès), les données restent dans la base de données quoi qu’il arrive (crash ou erreur).
- Cohérence : seules les données valides (en termes de contraintes relationnelles et fonctionnelles) sont écrites dans la base de données. La cohérence est liée à l’atomicité et à l’isolement.
Au cours de la même transaction, vous pouvez exécuter plusieurs requêtes SQL pour lire, créer, mettre à jour et supprimer des données. Le désordre commence lorsque deux transactions utilisent les mêmes données. L’exemple classique est un transfert d’argent d’un compte A vers un compte B. Imaginez que vous avez 2 transactions:
- Transaction 1 qui prend 100$ du compte A et les donne au compte B
- Transaction 2 qui prend 50$ du compte A et les donne au compte B
Si nous revenons aux propriétés ACID:
- L’atomicité garantit que peu importe ce qui se passe pendant T1 (une panne de serveur, une panne de réseau...), vous ne pouvez pas vous retrouver dans une situation où les 100$ sont retirés de A et non donnés à B (ce cas est un état incohérent).
- Lasolation assure que si T1 et T2 se produisent en même temps, à la fin A sera pris 150$ et B donné 150$ et non, par exemple, A pris 150$ et B donné seulement 50$ parce que T2 a partiellement effacé les actions de T1 (ce cas est également un état incohérent).
- La durabilité garantit que T1 ne disparaîtra pas dans les airs si la base de données se bloque juste après la validation de T1.
- La cohérence garantit qu’aucun argent n’est créé ou détruit dans le système.
[Vous pouvez passer à la partie suivante si vous voulez, ce que je vais dire n’est pas important pour le reste de l’article]
De nombreuses bases de données modernes n’utilisent pas une isolation pure comme comportement par défaut, car elle s’accompagne d’une énorme surcharge de performances. La norme SQL définit 4 niveaux d’isolement :
- Serializable (comportement par défaut dans SQLite) : le niveau d’isolation le plus élevé. Deux transactions qui se produisent en même temps sont isolées à 100%. Chaque transaction a son propre « monde ».
- Lecture répétable (comportement par défaut dans MySQL) : Chaque transaction a son propre « monde », sauf dans une situation. Si une transaction aboutit avec succès et ajoute de nouvelles données, ces données seront visibles dans l’autre et les transactions seront toujours en cours d’exécution. Mais si A modifie une donnée et finit avec succès, la modification ne sera pas visible dans les transactions encore en cours d’exécution. Ainsi, cette rupture de l’isolement entre les transactions ne concerne que les nouvelles données, pas les données existantes.
Par exemple, si une transaction A effectue un « SELECT count(1) from TABLE_X », puis qu’une nouvelle donnée est ajoutée et validée dans TABLE_X par la transaction B, si la transaction A effectue à nouveau un count(1), la valeur ne sera pas la même.
C’est ce qu’on appelle une lecture fantôme.
- Lecture validée (comportement par défaut dans Oracle, PostgreSQL et SQL Server) : C’est une lecture répétable + une nouvelle rupture d’isolement. Si une transaction A lit une donnée D et que ces données sont modifiées (ou supprimées) et validées par une transaction B, si A lit à nouveau les données D, elle verra la modification (ou la suppression) effectuée par B sur les données.
C’est ce qu’on appelle une lecture non répétable.
- Lire non validé : le niveau d’isolement le plus bas. C’est une lecture engagée + une nouvelle rupture d’isolement. Si une transaction A lit une donnée D et que cette donnée D est modifiée par une transaction B (qui n’est pas validée et toujours en cours d’exécution), si A lit à nouveau les données D, il verra la valeur modifiée. Si la transaction B est annulée, alors les données D lues par A la deuxième fois n’ont aucun sens puisqu’elles ont été modifiées par une transaction B qui ne s’est jamais produite (depuis qu’elles ont été annulées).
C’est ce qu’on appelle une lecture sale.
La plupart des bases de données ajoutent leurs propres niveaux d’isolation personnalisés (comme l’isolation de snapshot utilisée par PostgreSQL, Oracle et SQL Server). De plus, la plupart des bases de données n’implémentent pas tous les niveaux de la norme SQL (en particulier le niveau de lecture non validée).
Le niveau d’isolation par défaut peut être remplacé par l’utilisateur/développeur au début de la connexion (c’est une ligne de code très simple à ajouter).
Contrôle de la simultanéité
Le vrai problème pour assurer l’isolement, la cohérence et l’atomicité est les opérations d’écriture sur les mêmes données (ajout, mise à jour et suppression) :
- Si toutes les transactions ne font que lire des données, elles peuvent fonctionner en même temps sans modifier le comportement d’une autre transaction.
- Si (au moins) l’une des transactions modifie une donnée lue par d’autres transactions, la base de données doit trouver un moyen de masquer cette modification aux autres transactions. De plus, il doit également s’assurer que cette modification ne sera pas effacée par une autre transaction qui n’a pas vu les données modifiées.
Ce problème est appelé contrôle d’accès concurrentiel.
Le moyen le plus simple de résoudre ce problème est d’exécuter chaque transaction une par une (c’est-à-dire séquentiellement). Mais ce n’est pas du tout évolutif et un seul cœur fonctionne sur le serveur multiprocesseur/cœur, pas très efficace...
La façon idéale de résoudre ce problème est, chaque fois qu’une transaction est créée ou annulée:
- surveiller toutes les opérations de toutes les transactions
- pour vérifier si les parties de 2 transactions (ou plus) sont en conflit parce qu’elles lisent/modifient les mêmes données.
- Pour réorganiser les opérations à l’intérieur des transactions en conflit afin de réduire la taille des parties en conflit
- pour exécuter les parties en conflit dans un certain ordre (alors que les transactions non conflictuelles sont toujours exécutées simultanément).
- pour tenir compte du fait qu’une transaction peut être annulée.
Plus formellement, c’est un problème de planification avec des horaires conflictuels. Plus concrètement, c’est un problème d’optimisation très difficile et coûteux en CPU. Les bases de données d’entreprise ne peuvent pas se permettre d’attendre des heures pour trouver le meilleur calendrier pour chaque nouvel événement transactionnel. Par conséquent, ils utilisent des approches moins idéales qui entraînent plus de perte de temps entre des transactions conflictuelles.
Gestionnaire de verrouillage
Pour résoudre ce problème, la plupart des bases de données utilisent des verrous et/ou le contrôle de version des données. Comme il s’agit d’un grand sujet, je vais me concentrer sur la partie verrouillage, puis je parlerai un peu du versioning des données.
Verrouillage pessimiste
L’idée derrière le verrouillage est:
- si une transaction nécessite une donnée,
- Il verrouille les données
- si une autre transaction a également besoin de ces données,
- Il devra attendre que la première transaction libère les données.
C’est ce qu’on appelle un verrou exclusif.
Mais l’utilisation d’un verrou exclusif pour une transaction qui ne nécessite que la lecture d’une donnée est très coûteuse car elle oblige d’autres transactions qui ne veulent lire que les mêmes données à attendre. C’est pourquoi il existe un autre type de serrure, le verrou partagé.
Avec le verrou partagé :
- si une transaction n’a besoin que de lire une donnée A,
- Il « verrouille » les données et lit les données
- si une deuxième transaction ne nécessite également que la lecture des données A,
- Il « verrouille » les données et lit les données
- si une troisième transaction doit modifier les données A,
- il « verrouille » les données mais il doit attendre que les 2 autres transactions libèrent leurs verrous partagés pour appliquer son verrou exclusif sur les données A.
Néanmoins, si une donnée est un verrou exclusif, une transaction qui a juste besoin de lire les données devra attendre la fin du verrou exclusif pour mettre un verrou partagé sur les données.
Le gestionnaire de verrous est le processus qui donne et libère les verrous. En interne, il stocke les verrous dans une table de hachage (où la clé est la donnée à verrouiller) et connaît pour chaque donnée :
- quelles transactions verrouillent les données
- quelles transactions attendent les données
Impasse
Mais l’utilisation de verrous peut conduire à une situation où 2 transactions attendent éternellement une donnée:
Dans cette figure :
- La transaction A a un verrou exclusif sur les données1 et attend d’obtenir les données2
- la transaction B a un verrou exclusif sur les données2 et attend d’obtenir les données1
C’est ce qu’on appelle une impasse.
Lors d’un interblocage, le gestionnaire de verrouillage choisit la transaction à annuler (restauration) afin de supprimer l’interblocage. Cette décision n’est pas facile :
- Vaut-il mieux tuer la transaction qui a modifié le moins de données (et donc qui produira le rollback le moins coûteux) ?
- Est-il préférable de tuer la transaction la moins ancienne parce que l’utilisateur de l’autre transaction a attendu plus longtemps?
- Vaut-il mieux tuer la transaction qui prendra moins de temps à terminer (et éviter une éventuelle famine)?
- En cas de restauration, combien de transactions seront impactées par cette restauration ?
Mais avant de faire ce choix, il doit vérifier s’il y a des impasses.
La table de hachage peut être vue comme un graphique (comme dans les figures précédentes). Il y a un blocage s’il y a un cycle dans le graphique. Comme il est coûteux de vérifier les cycles (car le graphique avec tous les verrous est assez grand), une approche plus simple est souvent utilisée: utiliser un délai d’attente. Si aucun verrou n’est donné dans ce délai, la transaction entre dans un état de blocage.
Le gestionnaire de verrouillage peut également vérifier avant de donner un verrou si ce verrou crée un blocage. Mais encore une fois, il est coûteux de le faire parfaitement. Par conséquent, ces contrôles préalables sont souvent un ensemble de règles de base.
Verrouillage en deux phases
Le moyen le plus simple d’assurer une isolation pure est si un verrou est acquis au début de la transaction et libéré à la fin de la transaction. Cela signifie qu’une transaction doit attendre tous ses verrous avant de démarrer et que les verrous détenus par une transaction sont libérés à la fin de la transaction. Cela fonctionne mais cela produit beaucoup de temps perdu à attendre toutes les serrures.
Un moyen plus rapide est le protocole de verrouillage à deux phases (utilisé par DB2 et SQL Server) où une transaction est divisée en 2 phases:
- Phase de croissance au cours de laquelle une transaction peut obtenir des verrous, mais ne peut libérer aucun verrou.
- Phase de réduction où une transaction peut libérer des verrous (sur les données qu’elle a déjà traitées et ne traitera plus), mais ne peut pas obtenir de nouveaux verrous.
L’idée derrière ces 2 règles simples est :
- pour libérer les verrous qui ne sont plus utilisés afin de réduire le temps d’attente des autres transactions en attente de ces verrous
- Pour éviter les cas où une transaction obtient des données modifiées après le début de la transaction et ne sont donc pas cohérentes avec les premières données que la transaction a acquises.
Ce protocole fonctionne bien, sauf si une transaction qui a modifié une donnée et libéré le verrou associé est annulée (annulée). Vous pourriez vous retrouver dans un cas où une autre transaction lit la valeur modifiée alors que cette valeur va être annulée. Pour éviter ce problème, tous les verrous exclusifs doivent être libérés à la fin de la transaction.
Quelques mots
Bien sûr, une base de données réelle utilise un système plus sophistiqué impliquant plus de types de verrous (comme les verrous d’intention) et plus de granularités (verrous sur une ligne, sur une page, sur une partition, sur une table, sur un tablespace) mais l’idée reste la même.
Je n’ai présenté que l’approche purement basée sur le verrouillage. Le contrôle de version des données est un autre moyen de résoudre ce problème.
L’idée derrière le versioning est la suivante :
- Chaque transaction peut modifier les mêmes données en même temps
- Chaque transaction a sa propre copie (ou version) des données
- Si 2 transactions modifient les mêmes données, une seule modification sera acceptée, l’autre sera refusée et la transaction associée sera annulée (et peut-être réexécutée).
Il augmente les performances puisque :
- Les transactions du lecteur ne bloquent pas les transactions du writer
- Les transactions de l’enregistreur ne bloquent pas les transactions du lecteur
- Il n’y a pas de frais généraux du gestionnaire de serrures « gras et lent »
Tout est mieux que des verrous sauf lorsque 2 transactions écrivent les mêmes données. De plus, vous pouvez rapidement vous retrouver avec une énorme surcharge d’espace disque.
Le versioning des données et le verrouillage sont deux visions différentes : le verrouillage optimiste et le verrouillage pessimiste. Ils ont tous les deux des avantages et des inconvénients; Cela dépend vraiment du cas d’utilisation (plus de lectures vs plus d’écritures). Pour une présentation sur le contrôle de version des données, je recommande cette très bonne présentation sur la façon dont PostgreSQL implémente le contrôle de concurrence multiversion.
Certaines bases de données comme DB2 (jusqu’à DB2 9.7) et SQL Server (à l’exception de l’isolement de snapshot) utilisent uniquement des verrous. D’autres comme PostgreSQL, MySQL et Oracle utilisent une approche mixte impliquant des verrous et la gestion des versions des données. Je ne connais pas de base de données utilisant uniquement le versioning des données (si vous connaissez une base de données basée sur un versioning de données pur, n’hésitez pas à me le dire).
[MISE À JOUR 20/08/2015] Un lecteur m’a dit que :
Firebird et Interbase utilisent le contrôle de version sans verrouillage des enregistrements.
Le versioning a un effet intéressant sur les index : parfois un index unique contient des doublons, l’index peut avoir plus d’entrées que la table n’a de lignes, etc.
Si vous lisez la partie sur les différents niveaux d’isolement, lorsque vous augmentez le niveau d’isolement vous augmentez le nombre de verrous et donc le temps perdu par les transactions à attendre leurs verrous. C’est pourquoi la plupart des bases de données n’utilisent pas le niveau d’isolement le plus élevé (Serializable) par défaut.
Comme toujours, vous pouvez vérifier par vous-même dans la documentation des principales bases de données (par exemple MySQL, PostgreSQL ou Oracle).
Gestionnaire de journaux
Nous avons déjà vu que pour augmenter ses performances, une base de données stocke des données dans des tampons mémoire. Mais si le serveur tombe en panne lors de la validation de la transaction, vous perdrez les données encore en mémoire pendant le blocage, ce qui rompt la durabilité d’une transaction.
Vous pouvez tout écrire sur le disque, mais si le serveur tombe en panne, vous vous retrouverez avec les données à moitié écrites sur le disque, ce qui casse l’atomicité d’une transaction.
Toute modification écrite par une transaction doit être annulée ou terminée.
Pour faire face à ce problème, il y a 2 façons :
- Clichés instantanés/pages : Chaque transaction crée sa propre copie de la base de données (ou seulement une partie de la base de données) et travaille sur cette copie. En cas d’erreur, la copie est supprimée. En cas de succès, la base de données bascule instantanément les données de la copie avec une astuce de système de fichiers puis supprime les « anciennes » données.
- Journal des transactions : un journal de transactions est un espace de stockage. Avant chaque écriture sur le disque, la base de données écrit une information dans le journal de transactions afin qu’en cas de plantage/annulation d’une transaction, la base de données sache comment supprimer (ou terminer) la transaction inachevée.
Wal
Les clichés instantanés / pages créent une énorme surcharge de disque lorsqu’ils sont utilisés sur de grandes bases de données impliquant de nombreuses transactions. C’est pourquoi les bases de données modernes utilisent un journal de transactions. Le journal de transactions doit être stocké sur un stockage stable. Je n’irai pas plus loin sur les technologies de stockage, mais l’utilisation (au moins) de disques RAID est obligatoire pour éviter une panne de disque.
La plupart des bases de données (au moins Oracle, SQL Server, DB2, PostgreSQL, MySQL et SQLite) traitent le journal des transactions à l’aide du protocole WAL. Le protocole WAL est un ensemble de 3 règles :
- 1) Chaque modification apportée à la base de données produit un enregistrement de journal, et l’enregistrement de journal doit être écrit dans le journal de transactions avant que les données ne soient écrites sur le disque.
- 2) Les registres doivent être rédigés dans l’ordre; un enregistrement de journal A qui se produit avant un enregistrement de journal B doit mais écrit avant B
- 3) Lorsqu’une transaction est validée, l’ordre de validation doit être écrit dans le journal de transactions avant que la transaction ne se termine avec succès.
Ce travail est effectué par un gestionnaire de journaux. Un moyen facile de le voir est qu’entre le gestionnaire de cache et le gestionnaire d’accès aux données (qui écrit les données sur le disque), le gestionnaire de journaux écrit chaque mise à jour/suppression/création/validation/restauration sur le journal de transactions avant qu’elles ne soient écrites sur le disque. Facile, non?
MAUVAISE RÉPONSE! Après tout ce que nous avons traversé, vous devez savoir que tout ce qui concerne une base de données est maudit par « l’effet de base de données ». Plus sérieusement, le problème est de trouver un moyen d’écrire des logs tout en gardant de bonnes performances. Si les écritures dans le journal de transactions sont trop lentes, elles ralentiront tout.
BÉLIER
En 1992, les chercheurs d’IBM ont « inventé » une version améliorée de WAL appelée ARIES. ARIES est plus ou moins utilisé par la plupart des bases de données modernes. La logique n’est peut-être pas la même, mais les concepts derrière le Bélier sont utilisés partout. J’ai mis les citations sur inventé parce que, selon ce cours du MIT, les chercheurs d’IBM n’ont « rien fait de plus que d’écrire les bonnes pratiques de récupération de transaction ». Depuis que j’avais 5 ans lorsque l’article ARIES a été publié, je ne me soucie pas de ces vieux potins de chercheurs amers. En fait, je ne mets cette info que pour vous donner une pause avant de commencer cette dernière partie technique. J’ai lu une grande partie du document de recherche sur le Bélier et je le trouve très intéressant! Dans cette partie, je ne vous donnerai qu’un aperçu du Bélier, mais je vous recommande fortement de lire l’article si vous voulez une vraie connaissance.
ARIES signifie Algorithmes pour Récovery et Isolation Exploiting Sémantique.
L’objectif de cette technique est double :
- 1) Avoir de bonnes performances lors de l’écriture de journaux
- 2) Avoir une récupération rapide et fiable
Il existe plusieurs raisons pour lesquelles une base de données doit annuler une transaction :
- Parce que l’utilisateur l’a annulé
- En raison de pannes de serveur ou de réseau
- Parce que la transaction a rompu l’intégrité de la base de données (par exemple, vous avez une contrainte UNIQUE sur une colonne et la transaction ajoute un doublon)
- En raison des impasses
Parfois, (par exemple, en cas de défaillance du réseau), la base de données peut récupérer la transaction.
Comment est-ce possible? Pour répondre à cette question, nous devons comprendre les informations stockées dans un enregistrement de journal.
Les journaux
Chaque opération (ajout/suppression/modification) au cours d’une transaction produit un journal. Cet enregistrement de journal est composé des éléments suivants :
- LSN : Une équence unique Log S Number. Ce LSN est donné dans un ordre chronologique*. Cela signifie que si une opération A s’est produite avant une opération B, le LSN du log A sera inférieur au LSN du log B.
- TransID : ID de la transaction qui a produit l’opération.
- PageID : emplacement sur le disque des données modifiées. La quantité minimale de données sur le disque est une page, de sorte que l’emplacement des données est l’emplacement de la page qui contient les données.
- PrécédentLSN : Lien vers l’enregistrement de journal précédent généré par la même transaction.
- UNDO : un moyen de supprimer l’effet de l’opération
Par exemple, si l’opération est une mise à jour, UNDO stockera soit la valeur/l’état de l’élément mis à jour avant la mise à jour (UNDO physique), soit l’opération inverse pour revenir à l’état précédent (UNDO logique)**.
- REDO : une façon de rejouer l’opération
De même, il y a 2 façons de le faire. Soit vous stockez la valeur/l’état de l’élément après l’opération, soit l’opération elle-même pour le rejouer.
- ...: (Pour info, un journal ARIES comporte 2 autres champs : UndoNxtLSN et Type).
De plus, chaque page sur le disque (qui stocke les données, pas le journal) a l’id de l’enregistrement de journal (LSN) de la dernière opération qui a modifié les données.
*La façon dont le LSN est donné est plus compliquée car elle est liée à la façon dont les journaux sont stockés. Mais l’idée reste la même.
**ARIES n’utilise que l’ANNULATION logique car c’est un véritable gâchis de gérer l’ANNULATION physique.
Note: D’après mes petites connaissances, seul PostgreSQL n’utilise pas UNDO. Il utilise à la place un démon garbage collector qui supprime les anciennes versions des données. Ceci est lié à l’implémentation du versioning des données dans PostgreSQL.
Pour vous donner une meilleure idée, voici un exemple visuel et simplifié des enregistrements de journaux produits par la requête « MISE À JOUR DE L’ÂGE DÉFINI PAR LA PERSONNE = 18; ». Disons que cette requête est exécutée dans la transaction 18.
Chaque journal possède un LSN unique. Les journaux liés appartiennent à la même transaction. Les journaux sont liés dans un ordre chronologique (le dernier journal de la liste liée est le journal de la dernière opération).
Tampon de journal
Pour éviter que l’écriture du journal ne devienne un goulot d’étranglement majeur, un tampon logarithmique est utilisé.
Lorsque l’exécuteur de la requête demande une modification :
- 1) Le gestionnaire de cache stocke la modification dans son buffer.
- 2) Le gestionnaire de journaux stocke le journal associé dans sa mémoire tampon.
- 3) A cette étape, l’exécuteur de requête considère que l’opération est terminée (et peut donc demander d’autres modifications)
- 4) Ensuite, (plus tard), le gestionnaire de journaux écrit le journal dans le journal de transactions. La décision d’écrire le journal est prise par un algorithme.
- 5) Puis (plus tard) le gestionnaire de cache écrit la modification sur le disque. La décision d’écrire des données sur le disque est prise par un algorithme.
Lorsqu’une transaction est validée, cela signifie que pour chaque opération de la transaction, les étapes 1, 2, 3,4,5 sont effectuées. L’écriture dans le journal de transactions est rapide car il s’agit simplement « d’ajouter un journal quelque part dans le journal de transactions » alors que l’écriture de données sur disque est plus compliquée car c’est « écrire les données de manière à ce qu’il soit rapide de les lire ».
Politiques STEAL et FORCE
Pour des raisons de performances, l’étape 5 peut être effectuée après la validation, car en cas de plantage, il est toujours possible de récupérer la transaction avec les journaux REDO. C’est ce qu’on appelle une politique NO-FORCE.
Une base de données peut choisir une stratégie FORCE (c’est-à-dire que l’étape 5 doit être effectuée avant la validation) pour réduire la charge de travail pendant la restauration.
Un autre problème consiste à choisir si les données sont écrites étape par étape sur le disque (stratégie STEAL) ou si le gestionnaire de tampon doit attendre l’ordre de validation pour tout écrire en même temps (NO-STEAL). Le choix entre STEAL et NO-STEAL dépend de ce que vous voulez : écriture rapide avec une longue récupération à l’aide des journaux UNDO ou récupération rapide ?
Voici un résumé de l’impact de ces politiques sur le rétablissement :
- STEAL/NO-FORCE a besoin d’UNDO et REDO: performances maximales mais donne des journaux et des processus de récupération plus complexes (comme ARIES). C’est le choix fait par la plupart des bases de données. Note: J’ai lu ce fait sur plusieurs documents de recherche et cours, mais je ne l’ai pas trouvé (explicitement) sur les documentations officielles.
- STEAL/ FORCE n’a besoin que d’ANNULER.
- NO-STEAL/NO-FORCE n’a besoin que de refaire.
- NO-STEAL/FORCE n’a besoin de rien : les pires performances et une énorme quantité de RAM sont nécessaires.
La partie récupération
Ok, alors nous avons de belles bûches, utilisons-les!
Disons que le nouveau stagiaire a planté la base de données (règle n°1 : c’est toujours la faute du stagiaire). Vous redémarrez la base de données et le processus de récupération commence.
ARIES se remet d’un accident en trois passages:
- 1) La réussite de l’analyse : Le processus de récupération lit le journal des transactions complet* pour recréer la chronologie de ce qui s’est passé pendant le crash. Il détermine les transactions à restaurer (toutes les transactions sans ordre de validation sont annulées) et les données qui devaient être écrites sur le disque au moment du blocage.
- 2) La passe de rétablissement : Cette passe commence à partir d’un enregistrement de journal déterminé lors de l’analyse et utilise l’opération de rétablissement pour mettre à jour la base de données à l’état où elle se trouvait avant le crash.
Pendant la phase de rétablissement, les journaux REDO sont traités dans un ordre chronologique (à l’aide du LSN).
Pour chaque journal, le processus de récupération lit le LSN de la page sur disque contenant les données à modifier.
Si LSN(page_on_disk)>=LSN(log_record), cela signifie que les données ont déjà été écrites sur le disque avant le crash (mais la valeur a été écrasée par une opération qui s’est produite après le journal et avant le crash) donc rien n’est fait.
Si LSN(page_on_disk)<LSN(log_record), la page sur le disque est mise à jour.
Le rétablissement est effectué même pour les transactions qui vont être annulées car il simplifie le processus de récupération (mais je suis sûr que les bases de données modernes ne le font pas).
- 3) La passe d’annulation : Cette passe annule toutes les transactions qui étaient incomplètes au moment du crash. La restauration commence par les derniers journaux de chaque transaction et traite les journaux UNDO dans un ordre anti-chronologique (en utilisant le PrevLSN des enregistrements de journal).
Pendant la restauration, le journal de transactions doit être averti des actions effectuées par le processus de récupération afin que les données écrites sur le disque soient synchronisées avec ce qui est écrit dans le journal de transactions. Une solution pourrait être de supprimer les enregistrements de journal des transactions qui sont annulées, mais c’est très difficile. Au lieu de cela, ARIES écrit des journaux de compensation dans le journal de transactions qui suppriment logiquement les enregistrements de journal des transactions supprimées.
Lorsqu’une transaction est annulée « manuellement » ou par le gestionnaire de verrouillage (pour arrêter un blocage) ou simplement en raison d’une défaillance du réseau, la passe d’analyse n’est pas nécessaire. En effet, les informations sur ce qu’il faut REFAIRE et ANNULER sont disponibles dans 2 tables en mémoire :
- une table de transactions (stocke l’état de toutes les transactions en cours)
- une table de pages modifiées (stocke les données qui doivent être écrites sur le disque).
Ces tables sont mises à jour par le gestionnaire de cache et le gestionnaire de transactions pour chaque nouvel événement de transaction. Comme ils sont en mémoire, ils sont détruits lorsque la base de données se bloque.
Le travail de la phase d’analyse consiste à recréer les deux tables après un crash à l’aide des informations contenues dans le journal de transactions. *Pour accélérer la passe d’analyse, ARIES fournit la notion de point de contrôle. L’idée est d’écrire sur disque de temps en temps le contenu de la table de transaction et de la table des pages modifiées et du dernier LSN au moment de cette écriture afin que lors de la passe d’analyse, seuls les logs après ce LSN soient analysés.
Pour conclure
Avant d’écrire cet article, je savais à quel point le sujet était vaste et je savais qu’il faudrait du temps pour écrire un article approfondi à ce sujet. Il s’est avéré que j’étais très optimiste et que j’ai passé deux fois plus de temps que prévu, mais j’ai beaucoup appris.
Si vous voulez un bon aperçu des bases de données, je vous recommande de lire le document de recherche « Architecture d’un système de base de données ». C’est une bonne introduction sur les bases de données (110 pages) et pour une fois elle est lisible par des non-CS. Cet article m’a beaucoup aidé à trouver un plan pour cet article et il n’est pas axé sur les structures de données et les algorithmes comme mon article, mais plus sur les concepts d’architecture.
Si vous lisez attentivement cet article, vous devriez maintenant comprendre à quel point une base de données est puissante. Comme il s’agissait d’un très long article, permettez-moi de vous rappeler ce que nous avons vu:
- une vue d’ensemble des index B+Tree
- Vue d’ensemble globale d’une base de données
- Une vue d’ensemble de l’optimisation basée sur les coûts avec un fort accent sur les opérateurs de jointure
- Vue d’ensemble de la gestion du pool de tampons
- Vue d’ensemble de la gestion des transactions
Mais une base de données contient encore plus d’intelligence. Par exemple, je n’ai pas parlé de certains problèmes délicats comme:
- Comment gérer les bases de données en cluster et les transactions globales
- Comment prendre un instantané lorsque la base de données est toujours en cours d’exécution
- Comment stocker (et compresser) efficacement les données
- Comment gérer la mémoire
Alors, réfléchissez à deux fois lorsque vous devez choisir entre une base de données NoSQL boguée et une base de données relationnelle solide comme le roc. Ne vous méprenez pas, certaines bases de données NoSQL sont excellentes. Mais ils sont encore jeunes et répondent à des problèmes spécifiques qui concernent quelques applications.
