Bonsoir,
Ce dont je souhaite vous entretenir a trait aux conséquences sur les performances des applications, résultant de certains choix d’organisation au niveau du MCD. En effet, les AGL répercutent ces choix au niveau du MLD, puis du MPD, ce dernier niveau se situant sous le capot, là où en réalité tout se joue en ce qui concerne la performance des requêtes. Je m’intéresse plus particulièrement ici à l’identification des entités-types, à savoir absolue ou relative, ainsi qu’à la façon d’ordonner les attributs dans les clés : ce dernier point peut paraître anodin, sans intérêt, mais cette façon d’ordonner peut en fait être très lourde de conséquences.
Évidemment, si le MCD comporte un nombre réduit d’entités-types et d’associations-types, on peut toujours modifier manuellement le MLD produit par l’AGL (le bon sens voulant que l’on agisse ainsi seulement si l’on ne peut pas faire autrement), mais quand le MCD comporte des centaines de ces objets-types, cela devient mission impossible.
Identification absolue vs identification relative
Partons de votre MLD et supposons que l’utilisateur de la base de données souhaite disposer de la liste complète des femelles, en se limitant aux informations suivantes :
NUM_OFFICIEL, DATE_NAISS, DATE_SOIN, DATE_RAPPEL_TRAIT.
Selon le Modèle Relationnel de Données (nom donné par son inventeur, Ted Codd, à la théorie relationnelle), le résultat est obtenu au moyen de la requête suivante :
1 2 3
|
(FEMELLE JOIN SOIN)
{NUM_OFFICIEL, DATE_NAISS, DATE_SOIN, DATE_RAPPEL_TRAIT} ; |
Ce qui se lit : Sur la base de leurs attributs portant le même nom (en l’occurrence ID_FEMELLE) et dont les valeurs égales, marier (JOIN) les tables FEMELLE et SOIN. Puis, du bébé issu de ce mariage, récupérer les valeurs, uniquement pour les attributs énumérés entre les accolades (opération de projection), à savoir NUM_OFFICIEL, DATE_NAISS, DATE_SOIN, DATE_RAPPEL_TRAIT.
Ou encore, dans le style du modèle SQL (avec des SGBD tels que SQL Server, DB2 for z/OS, etc.) :
1 2 3 4
|
SELECT NUM_OFFICIEL, DATE_NAISS, DATE_SOIN, DATE_RAPPEL_TRAIT
FROM FEMELLE INNER JOIN SOIN
ON FEMELLE.ID_FEMELLE = SOIN.ID_FEMELLE ; |
Vous aurez noté à cette occasion que seuls sont énumérés les attributs relatifs aux données qui intéressent l’utilisateur : si l’attribut ID_FEMELLE a joué un rôle clé dans cette opération, il n’en demeure pas moins qu’il est parfaitement inutile de le faire figurer dans le résultat, puisque les valeurs qu’il prend n’ont de signification que pour le SGBD. Pour imager, on pourrait dire qu’un attribut artificiel tel que ID FEMELLE, et ne concernant donc pas l’utilisateur, joue dans la production de ce résultat un rôle analogue à celui que joue le nombre imaginaire i dans la résolution d’une équation polynomiale.
Incidemment, observons que le bébé issu du mariage est de même nature que ses parents FEMELLE et SOIN, c'est-à-dire qu’il s’agit d’une table T (dans le cadre de la théorie relationnelle, il faudrait utiliser le terme relation, mais ne compliquons pas les choses). Cette propriété porte le nom de fermeture (closure), en vertu de quoi, le bébé T peut à son tour jouer le rôle d’opérande pour une autre opération relationnelle. Il est le fruit d’une opération de jointure (que j’ai appelée mariage), et subit ensuite une opération de projection, grâce à laquelle on limite le résultat aux seuls attributs mentionnés plus haut (NUM_OFFICIEL, DATE_NAISS, DATE_SOIN, DATE_RAPPEL_TRAIT). Toujours au nom de la propriété de fermeture, le résultat final est évidemment une table.
Ce que je viens de décrire relève de la théorie relationnelle. On se situe au niveau de l’algèbre (ou du calcul des prédicats) : à ce stade, le coût de l’opération (disons sa durée) n’entre pas en ligne de compte, l’utilisateur ayant déclenché la requête étant théoriquement infiniment patient et n’exigeant seulement que résultat qu’on lui présente soit valide.
Une première remarque
Je n’ai pas fait participer la table ATTRAP à l’opération, puisque cela n’apporterait rien de plus. La requête suivante est certes correcte, et c’est elle qui serait vraisemblablement codée par les progiciels et nombre de développeurs. En effet, intuitivement, ATTRAP est un point de passage naturel, quasi obligé, pour « aller » de FEMELLE à SOIN :
1 2 3
|
((FEMELLE JOIN ATTRAP) JOIN SOIN)
{NUM_OFFICIEL, DATE_NAISS, DATE_SOIN, DATE_RAPPEL_TRAIT} ; |
Ou dans le style du modèle SQL :
1 2 3 4 5 6
|
SELECT NUM_OFFICIEL, DATE_NAISS, DATE_SOIN, DATE_RAPPEL_TRAIT
FROM FEMELLE INNER JOIN ATTRAP
ON FEMELLE.ID_FEMELLE = ATTRAP.ID_FEMELLE
INNER JOIN SOIN
ON ATTRAP.ID_FEMELLE = SOIN.ID_FEMELLE ; |
Quoi qu’il en soit, cette requête mérite tout simplement de passer au rasoir d’Ockham. Ainsi, l’optimiseur de DB2 for z/OS ne s’en prive pas : il la simplifie en la réécrivant de telle sorte qu’elle devienne celle que j’ai fournie initialement. Pour les autres SGBD, je ne sais pas ce qu’il en est, sinon qu’avec SQL Server (version Express 2005), la simplification n’a pas lieu, en effet ce SGBD fait participer inutilement un index de la table ATTRAP (voir ci-dessous les quelques mots qui expliquent très succinctement ce qu’est un index et à quoi il sert).
Une deuxième remarque
Certains ignorent (ou veulent ignorer) ce qu’est un identifiant relatif. Supposons qu’au niveau du MCD, ATTRAP soit une entité-type, dotée d’un identifiant absolu ID_ATTRAP. Dans ces conditions, la clé étrangère qui dans SOIN permet de référencer ATTRAP n’est plus {ID_FEMELLE, ID_MALADIE, ID_DATE}, mais {ID_ATTRAP} : la table ATTRAP doit désormais participer à titre de moyen terme entre les tables FEMELLE et SOIN, parce que ID_FEMELLE n’est plus un attribut de la table SOIN, et la jointure de ma première requête n’est donc plus valide (en réalité elle dégénère en produit cartésien). C’est dommage.
Je rappelle que l’identification relative s’impose dans le cas des propriétés multivaluées. Par exemple, une facture est composée de une à plusieurs lignes de facture, autrement dit une ligne de facture est une propriété multivaluée d’une facture, et si l’on supprime une facture, ses lignes le sont aussi, de facto. Si l’on définit une entité-type LIGNE_FACTURE, celle-ci n’est qu’une entité-type faible et elle hérite de l’identifiant de l’entité-type FACTURE, auquel on ajoute un attribut artificiel, par exemple un numéroteur relatif, permettant de distinguer chaque ligne de la même facture.
Il en va ainsi pour l’entité-type ATTRAP, faible par rapport à FEMELLE : Si l’on supprime la femelle Rosa, il est évident que tout ce qui concerne celle-ci doit disparaître de ATTRAP. Il est intéressant d’observer qu’à l’opposé, si l’on supprime une maladie, cela est en fait impossible tant qu’une femelle est concernée (de même que l’on ne peut pas supprimer un produit auquel fait référence une facture). Autrement dit, pour se situer au plan sémantique, ATTRAP n’est pas a priori une propriété multivaluée de MALADIE (sauf à me démentir) : je dirais que ATTRAP fait référence à (désigne) MALADIE, c'est-à-dire que si Rosa a attrapé une bronchopneumonie, elle n’est pas pour autant la propriété de cette maladie. Maintenant, et comme c’est le cas dans votre MLD, rien n’empêche évidemment que l’attribut ID_MALADIE soit un des éléments de la clé de la table ATTRAP. Ce n’est qu’une réminiscence du fait d’avoir considéré ATTRAP comme entité-type associative.
Une question en passant : LACTATION et CTRL_LACTATION sont-elles des entités-types fortes ou faibles ? Si elles sont fortes, on ne touche pas au mode d’identification, sinon...
Des performances
Revenons-en à la première requête :
1 2 3
|
(FEMELLE JOIN SOIN)
{NUM_OFFICIEL, DATE_NAISS, DATE_SOIN, DATE_RAPPEL_TRAIT} ; |
Une fois celle-ci déclenchée, les yeux rivés sur son écran, l’utilisateur aimerait quand même bien que le résultat lui soit fourni dans un délai raisonnable, qu’il ne faille pas une heure pour afficher les informations impliquant mille vaches (sur un plateau, si je puis dire). En ce sens, équipés d’un fer à souder, nous devrons donc descendre dans la soute, pour vérifier que les turbos ad-hoc sont opérationnels et serrer au besoin quelques boulons. Nous nous situerons alors au niveau du modèle physique de données (MPD), dont la responsabilité incombe cette fois-ci au DBA (Database Administrator) et pour lequel le concepteur n’est pas (théoriquement) compétent.
En première approche, comment les choses se passent-elles ? Dans les tréfonds, l’image physique d’une table T est hébergée par un fichier sur le disque (ou plusieurs fichiers sur plusieurs disques au besoin). Le fichier est lui-même composé de blocs que l’on appelle encore pages. Une page P comporte un plusieurs enregistrements, chacun d’eux étant l’image physique d’une ligne de T. Une ligne cohabite donc dans P avec 0 à plusieurs autres lignes de T, selon la place disponible.
Après examen de la requête, le SGBD lit la première page P1 du fichier affecté à la table FEMELLE. Supposons que le 1er enregistrement de P1 corresponde à la vachette Zaza. Le SGBD récupère ce dont il a besoin : le numéro officiel et la date de naissance de Zaza. L’opération est rapide. Supposons maintenant que Zaza ait fait l’objet de dix soins. La rapidité de récupération des données correspondant aux dix soins de la Zaza dépendra de la proximité physique de ces données dans le fichier hébergeant la table SOIN : soit les enregistrements utilisés pour Zaza sont physiquement regroupés dans une même page, soit au contraire, ils sont éparpillés dans des pages distinctes (« façon puzzle », comme dirait Raoul Volfoni).
Si tous les soins concernant Zaza sont regroupés dans une même page, le SGBD peut les récupérer en un seul accès au disque. S’ils sont éparpillés dans dix pages distinctes et éloignées les unes des autres, le SGBD devra effectuer dix accès pour récupérer les informations. Le coût est alors dix fois supérieur à celui qui correspond au scénario précédent.
Si votre cas correspond au second scénario, cela risque de ne pas être dramatique, mais si l’on en vient à la récupération des mouvements en relation avec les comptes des dix millions de clients d’une banque, cela pourrait vraiment devenir un problème insurmontable. En effet, le coût d’un accès à une page sur disque se mesure en millisecondes et les temps de traitement pour retrouver tous les mouvements de tous les clients deviennent rédhibitoires (et c’est pour cela que l’on m’a encore sollicité il y a quelques mois pour résoudre en catastrophe un problème de cette nature). D’aucuns vous diront qu’en mettant en place des caches énormes, donc en remplaçant les accès au disque par des accès à la mémoire, ce genre de problème ne devrait plus se poser : mais les faits sont là, et vous comprendrez que, dans ce genre d’expérience, on me convaincra difficilement que les caches sont la panacée. Et puis, dans un établissement tel qu’une banque, deux ou trois mille utilisateurs opèrent en même temps et personne n’a l’exclusivité des ressources. Même, en y mettant le prix, on a très peu de chances que les choses s’arrangent, et il est peut-être bon d’appliquer quelques principes éprouvés, afin d'éviter d’en arriver à des solutions extrêmes, pour des résultats fort aléatoires.
Des index
Toujours dans la soute, venons-en aux turbos. Depuis qu’ils existent, quels que soient les SGBD, la bonne performance des requêtes est le plus généralement la conséquence du bon choix de ce que l’on appelle les index : ce sont des objets (disons des fichiers) que l’on ne connaît pas au niveau logique, mais qui relèvent du niveau physique et que l’on « branche » sur [les fichiers hébergeant] les tables. A l’image de l’index d’un livre, la finalité d’un index d’une table est de nous permettre de retrouver les données (par exemple celles d’une femelle dans la table FEMELLE), non pas en parcourant le contenu intégral de la table (comme on lirait laborieusement le livre mot par mot, de la première à la dernière page, pour y chercher tel mot), mais en accédant directement et rapidement à la bonne page. Comme pour une table, l’accès à un index est réalisé au moyen d’une clé, image d’une clé de la table (ou composée de tous autres attributs pour lesquels les recherches doivent être rapides).
J’ignore quel est votre niveau de connaissance en matière d’index, mais peu importe, je rappelle quelques principes généraux.
Les éléments pour travailler efficacement sont notamment les suivants, en remontant de la soute vers le pont :
Au niveau physique, la façon d’organiser les index.
Au niveau logique : l’ordre des attributs dans les clés, car cet ordre conditionnera celui des clés correspondantes dans les index.
Au niveau conceptuel : la façon d’identifier, soit de façon absolue (exemple : l’entité-type FEMELLE est identifiée de façon absolue, à l’aide de l’attribut ID_FEMELLE), soit de façon relative (dans la mesure où, en conséquence, on permet au niveau logique, la propagation des attributs de table en table : attribut ID_FEMELLE, propagé depuis la table FEMELLE jusqu’à la table SOIN, via la table ATTRAP). Je rappelle : quelles seraient les conséquences quant à la performance de la requête initiale si l’on avait identifié ATTRAP de façon absolue ?
Et bien sûr, tout cela est conditionné par la mise en évidence des traitements transactionnels (légers) ou traitements de type batch (lourds) qui reviennent le plus souvent.
Quelques mots ayant trait à l’organisation d’un index. Je rappelle brièvement qu’un index est en général organisé selon une structure d’arbre, avec :
— Tout en haut (niveau 1) la racine (une seule page), point d’entrée essentiel pour accéder à l’information recherchée, en fonction d’une valeur de clé. Exemple, si l’on définit un index, appelons-le FEMELLE_PK_X, dont la clé est construite sur l’attribut ID_FEMELLE, alors on pourra accéder directement aux données de la vachette Rosa pour laquelle tout le monde sait qu’elle répond au critère ID_FEMELLE=31415, Partant de la racine, le système entamera une descente dans les niveaux inférieurs, sur la base de cette valeur.
— Tout en bas (niveau N, avec N > 1) les feuilles de l’arbre, lesquelles contiennent les adresses des pages du fichier hébergeant la table. A noter à cette occasion que l’arbre est équilibré, c'est-à-dire que, contrairement à ce que nous observons dans la nature, les feuilles sont toutes à la même distance de la racine.
— Au milieu (niveaux intermédiaires), les nœuds permettant au système d’atteindre les feuilles à partir de la racine (jeux de pointeurs). Le nombre de niveaux intermédiaires est variable. Par exemple, avec DB2 for z/OS, pour les dix millions de clients de la banque, ce nombre sera égal à deux. Si votre table MALADIE décrivait dix mille maladies, aucun nœud intermédiaire ne serait nécessaire, l’index se résumerait à la racine plus une trentaine de feuilles directement en relation avec la racine.
Toujours avec DB2 for z/OS, si votre table SOIN comportait dix millions de lignes, vous devriez compter normalement sur deux index : un pour la clé primaire (appelons-le SOIN_XPK) et un pour la clé alternative (appelons-le SOIN_XAK), organisés ainsi :
Pour l’index « primaire » SOIN_XPK (clé : ID_SOIN), la racine comporterait une page ; au deuxième niveau, un nœud comporterait une centaine de pages et au troisième et dernier niveau, le nombre de pages (feuilles) serait de l’ordre de 3000. Ainsi, pour retrouver les données d’un soin via la clé primaire, on aurait droit au plus à trois accès physiques (un pour le deuxième niveau, un pour le niveau feuille et un pour la page contenant les données (il est d’usage de ne pas tenir compte du premier niveau, présent le plus souvent en mémoire). Via l’index primaire, à dix millisecondes l’accès, le SGBD récupèrera les données d’un soin en une trentaine de millisecondes.
Pour l’index « alternatif » SOIN_XAK (clé : ID_FEMELLE, ID_MALADIE, ID_DATE, ID_SOIN), la racine comporterait une page ; au deuxième niveau, on aurait trois pages, au troisième niveau environ 400 pages et enfin au dernier niveau, le nombre de feuilles serait de l’ordre de 64000. Ainsi, pour retrouver les données d’un soin via la clé alternative, on aurait droit à quatre accès physiques. Le SGBD récupèrerait les données d’un soin en une quarantaine de millisecondes.
Supposons maintenant que l’on ne gère pas dix millions de femelles, mais plutôt quelques milliers. Complétons la requête initiale, pour retrouver les informations concernant plus précisément la vachette Rosa, sur la base de son identité officielle (attribut NUM_OFFICIEL prenant la valeur 1234) :
1 2 3
|
((FEMELLE WHERE NUM_OFFICIEL = 1234) JOIN SOIN)
{NUM_OFFICIEL, DATE_NAISS, DATE_SOIN, DATE_RAPPEL_TRAIT} ; |
Je suppose qu’une requête de cette nature sera fort utilisée, dans la mesure où l’utilisateur propose le numéro officiel pour avoir accès aux données de l’animal. Il est souhaitable qu’en l’occurrence le SGBD n’ait pas à balayer mot à mot la table FEMELLE pour résoudre la partie "WHERE NUM_OFFICIEL = 1234" de la requête : un index ad-hoc s’impose (nommons-le FEMELLE_OFF_X), avec NUM_OFFICIEL comme clé d’accès. A peu de choses près, les choses se passeront alors ainsi dans la soute pour traiter la requête :
1) Le SGBD utilise l’index FEMELLE_OFF_X et consomme de l’ordre de vingt millisecondes pour retrouver toutes les données de l’animal, en particulier les valeurs des attributs ID_FEMELLE et DATE_NAISS. Supposons qu’il s’agisse donc de la vachette Rosa, pour laquelle ID_FEMELLE=31415.
2) Ayant pris connaissance de l’information ID_FEMELLE=31415, le SGBD traverse verticalement l’index SOIN_XAK et en une dizaine de millisecondes récupère au niveau feuille les pointeurs vers les données concernant Rosa dans la table SOIN. A méditer : quelles auraient les conséquences d’une permutation des attributs ID_FEMELLE et ID_MALADIE dans la clé alternative de la table SOIN ?
3) Supposons que Rosa ait fait l’objet de dix soins. Si les enregistrements correspondants sont regroupés dans une même page (situation idéale), en dix millisecondes les informations complémentaires sont récupérées (DATE_SOIN, DATE_RAPPEL_TRAIT), et le SGBD peut présenter à l’utilisateur le résultat voulu, pour un coût global de l’ordre d’une quarantaine de millisecondes. Si les enregistrements sont éparpillés dans le fichier hébergeant la table SOIN, le coût peut être de l’ordre de cent trente millisecondes. Dans le contexte des traitements bancaires, il est impératif de se ramener au cas précédent, dès lors que le nombre de transactions est élevé, et la production informatique ne manquera pas de nous brandir sous le nez ses statistiques et d’exiger que nous fassions le nécessaire.
Quelques observations.
1) J’ai considéré qu’un accès à un enregistrement du disque était de l’ordre de la dizaine de millisecondes : ceci est évidemment à titre indicatif. Selon que les accès sont sélectifs (à l’unité) ou se font en rafales, lire 64 pages peut dans un cas coûter 640 millisecondes et quatre fois moins dans l’autre cas. Selon le prix que l’on met, les disques sont plus ou moins performants. De même, la technologie rend les accès toujours plus rapides au fil des ans. Mais une chose est sûre, il n’y a aucune mesure en termes de coût entre un accès à l’information sur le disque et à cette même information quand elle est mémorisée dans les caches. Je le répète, il est prudent de partir du principe que l’information que l’on cherche n’est pas encore mémorisée.
2) Beaucoup plus important : l’ordre des attributs de la clé alternative de la table SOIN induit l’ordre des attributs composant la clé de l’index associé SOIN_XAK :
ID_FEMELLE, ID_MALADIE, ID_DATE, DATE_SOIN.
Cet ordre est primordial. En effet, s’il était par exemple le suivant :
ID_MALADIE, ID_FEMELLE, ID_DATE, DATE_SOIN,
alors le SGBD ne pourrait plus traverser verticalement l’index et balaierait horizontalement le niveau feuilles, d’où une dégradation radicale des performances si l’on ne branchait pas un index supplémentaire pour pallier. Quand on a une poignée de tables mal indexées, on peut s’en sortir, mais si l’on en a des centaines...
3) Comment faire pour éviter l’éparpillement des 10 soins sur le disque ? Un SGBD comme DB2 for z/OS (même chose pour SQL Server) permet, par paramétrage de l’index, d’imposer que le regroupement sur le disque des enregistrements correspondant aux lignes de la table, se fasse selon la séquence de la clé de l’index (lequel est alors qualifié de CLUSTER). Bien entendu, pour la table SOIN, seul l’index alternatif est pertinent pour être CLUSTER, puisque les soins de Rosa doivent se suivre selon la séquence ID_FEMELLE. Si vous désigniez l’index primaire comme CLUSTER, vous auriez tout faux.
Au fait, quel est intérêt de l’attribut ID_SOIN ? Que perdriez-vous à supprimer cet attribut et à rendre primaire la clé alternative de la table SOIN ? Au niveau MCD, un soin n’est-il pas d’un point de vue sémantique une propriété multivaluée de l’entité-type ATTRAP, et par contrecoup de l’entité-type FEMELLE ?
4) Supposons encore que l’on veuille savoir quelles femelles ont attrapé telle maladie.
La requête serait la suivante :
1 2
| (((MALADIE WHERE NOM_MALADIE = 'bronchopneumonie')
JOIN ATTRAP) JOIN FEMELLE) {NUM_OFFICIEL} ; |
Qui se lit : Sélectionner dans la table MALADIE la ligne pour laquelle NOM_MALADIE = 'bronchopneumonie'. Joindre le résultat avec la table ATTRAP (sur la base de l’attribut commun ID_MALADIE). Joindre le nouveau résultat avec la table FEMELLE (sur la base de l’attribut commun ID_FEMELLE). Fournir à l’utilisateur la liste des NUM_OFFICIEL.
Vous aurez compris qu’il n’est pas superflu de disposer pour la table ATTRAP d’un index supplémentaire, ordonné sur l’attribut ID_MALADIE pour que la jointure des tables MALADIE et ATTRAP soit performante. Quant à la jointure avec la table FEMELLE, la table ATTRAP étant dotée d’office d’un index pour la clé primaire de celle-ci (même si cela relève d’un diktat arbitraire de la part des SGBD, cet index est imposé), pas de problème de traversée verticale. Maintenant, le coût de la requête n’est pas optimal, dans la mesure où les femelles sont ordonnées dans le fichier qui les héberge selon une séquence cluster qui n’est pas celle des maladies. Pour vous ça sera relativement transparent. Mais transposé dans le monde bancaire...
Pour conclure
Quand on construit un MCD, il est évident que l’on n’est pas concerné par la performance des requêtes qui attaqueront la base de données. Néanmoins, il est bon d’avoir un minimum de connaissances à ce sujet, pour prendre conscience que certains choix sémantiques (propriétés multivaluées, identification relative, etc.) sont lourds de conséquence quant à l’organisation des données au niveau physique, dès lors que l’on passe par les services d’un AGL, lequel traduit mécaniquement le MCD en MLD puis celui-ci en MPD. Dans le même sens, on doit être attentif quant à l’ordre des attributs dans les clés, et ne pas oublier que la performance dépend largement (au moins pour des traitements lourds) du choix de l’index cluster d’une table. En tout état de cause, il faut avoir connaissance des requêtes qui seront les plus utilisées et qui pourront orienter nos choix, sachant que favoriser celles-ci pénalisera forcément les autres. Vieux problème, but that's another story...
Partager