Bonsoir,
Envoyé par
CinePhil
Là j'ai plus de mal...
Je reprends donc le fil de mes tentatives d’explication et passe aux index. Dans ce qui suit, je me limiterai à la façon dont travaille DB2 for z/OS dans les versions précédant la V9, laquelle comporte des raffinements pouvant à l’occasion rendre incomplètes, voire caduques certaines de mes explications.
Un index DB2 est un arbre équilibré (balanced tree) ; comme je l’ai déjà dit, cela signifie que toutes les feuilles sont à la même distance de la racine, autrement dit, le temps d’accès est le même pour toutes les feuilles. Ceci est capital quand il s’agit de s’attaquer au réglage des performances, lesquelles seraient aléatoires si l’arbre n’était pas équilibré. Les index sont donc le plus souvent, des arbres B, et dans le cas de DB2 ce sont même des B+, je reviendrai un peu plus loin sur cette particularité.
N.B. J’ai écrit que le temps d’accès est le même pour toutes les feuilles : ceci est vrai quand l’index vient d’être créé ou réorganisé, mais au fil du temps il peut y avoir une dégradation perceptible des performances du fait de nombreuses mises à jour, et il est alors préférable de procéder à une réorganisation de l’index. DB2 met à notre disposition, dans son catalogue, toutes informations utiles à cet effet.
Observons maintenant comment DB2 (disons version 5) organise un index. Celui que je dépiaute (appelons-le MEMBRE_X1) est destiné à contenir les valeurs de la clé primaire de la table MEMBRE des membres de DVP : '0012' (valeur de la clé primaire du membre CinePhil), '4089' (valeur de la clé primaire du membre Fsmrel), etc.
Supposons que l’index vient d’être défini et vide. Lors du premier INSERT, par exemple du membre SQLpro dans la table MEMBRE, DB2 crée un enregistrement dans le table space d’accueil des images des lignes de la table. Appelons MEMBRE_TS ce table space.
La page P1 contient un certain nombre d’informations « système », dont une petite table appelée id map contenant l’adresse dans P1 de la ligne qui vient d’être insérée. Le rôle de l’id map est capital : les index branchés sur la table ne connaîtront jamais l’adresse exacte d’une ligne dans le table space, mais seulement l’adresse de la page P1 et le numéro du poste (invariable) de cette ligne dans l’id map (1 dans l’exemple). Ainsi, si les enregistrements bougent dans la page, ou sont carrément expulsés vers d’autres pages (« Ôte-toi de là, que je m’y mette ! » dit le gros enregistrement au petit), ces phénomènes n’auront aucun impact sur les valeurs connues par les index (dans l’exemple, la seule information connue est 'P1,1', à savoir l’adresse de la page et le numéro de poste dans l’id map).
Concernant l’index MEMBRE_X1, DB2 réalise les opérations suivantes à l’occasion de ce premier insert :
—Création de la page racine et d’une page feuille.
— DB2 note dans la page feuille les coordonnées de SQLpro dans MEMBRE_TS, à savoir un record identifier (RID), composé du numéro de la page hébergeant SQLpro, et du numéro qui lui est affecté dans l’id map : 'P1,1'.
— DB2 note dans la page racine la plus grande valeur de clé au niveau inférieur et l’adresse de celle-ci (symbolisée par '↑').
Effectuons un deuxième INSERT, par exemple du membre CinePhil. Il reste de la place dans la page P1 du table space MEMBRE_TS, et elle ressemblera à quelque chose comme ceci :
L’id map s’est enrichie d’un élément (poste), portant le numéro 2 et contenant l’adresse dans P1 du nouvel enregistrement.
L’index MEMBRE_X1 est mis à jour en conséquence :
La feuille est enrichie d’un élément permettant d’adresser dans MEMBRE_TS le membre dont la valeur de clé est égale à '0012'. Les éléments dans la feuille sont triés, ce qui fait que l’élément "3500 (RID = 'P1,1')" passe derrière le nouvel arrivant.
La racine ne change pas de contenu, par construction elle conserve toujours la plus grande valeur de clé de la feuille cible.
Les inserts se suivent et se ressemblent : Fsmrel (clé = '4089'), Antoun (clé = '0967'), etc.
Au fil de ces inserts, le table space contiendra de plus en plus de pages et l’index suivra. A un moment donné, il n’y aura plus assez de place dans la feuille F1 : DB2 créera une feuille supplémentaire F2 et en notera l’adresse dans la racine. Dans la figure ci-dessous, la racine contient donc deux entrées, une pour F1 et une pour F2. Chaque entrée contient la plus grande valeur de clé pour chaque feuille ainsi que l’adresse de celle-ci.
La séquence des clés doit être strictement respectée, aussi les feuilles seront-elles chaînées à cet effet : ceci favorise les traitements de masse (batch) pour lesquels les requêtes SQL SELECT comportent une clause ORDER BY (attention, au sein des pages de données, P1, etc., les lignes ne sont pas triées). Ce chaînage des feuilles fait que les index DB2 ne sont pas seulement des arbres B, mais B+.
Si l’on soumet l’instruction :
1 2 3 4
|
SELECT NOM
FROM MEMBRE
WHERE MembreId = '3500' |
Alors DB2 lira le contenu de la racine de l’index Membre_X1, et comme '3500' est supérieur à '0967' et inférieur à '4089', ce sera la feuille F2 qui sera lue à son tour. La lecture suivante sera celle de la page de données P1. La consultation de l’id map permettra de retrouver les données du membre '3500'.
Les inserts continuant, de nouvelles feuilles vont être crées et le nombre d’entrées dans la racine croîtra en conséquence. Arrivera un moment où à son tour elle sera pleine :
C’est alors que DB2 effectue un split de cette racine, en en répartissant l’ensemble des éléments dans deux pages, pour moitié entre chacune d'elles. Mais comme par définition la racine ne comporte qu’une page, ces deux pages deviennent des nœuds intermédiaires et une nouvelle racine est créée, n’adressant plus cette fois-ci les feuilles, mais ces nœuds intermédiaires. Je résume la situation dans le dessin ci-dessous, extrait d’un cours que j’ai monté il y a vingt ans (DB2 V2) et que j’ai retouché pour les besoins de la cause :
A chaque fois que la racine sera pleine, il y aura split et création d’un nouveau niveau intermédiaire.
Quelques estimations
Revenons-en aux bovins. L’attribut ID_FEMELLE composant la clé primaire est du type Integer. Je me sers à nouveau de DB2 Estimator pour tout savoir sur l’index FEMELLE_PK_X ayant pour clé ID_FEMELLE. Pour 67 000 000 de têtes, les chiffres sont les suivants :
La taille de la clé est de 4 octets.
La taille de chaque page est de 4 KB. Comme dans le cas du table space, j’ai prévu un free space de 20% par page et une page complètement libre après chaque paquet de 15 pages.
=>
Nombre de niveaux d’index : 4.
Racine : 1 page.
Niveau intermédiaire 1 : 3 pages.
Niveau intermédiaire 2 : 689 pages.
Niveau feuille : 228 669 pages.
Je fais observer à cette occasion que, vu le grand nombre de lignes de la table, il est souhaitable de partitionner le table space en sous-table spaces, correspondant chacun à une fourchette de clés. Le but est de pouvoir effectuer les tâches de service (sauvegardes, restaurations, réorganisations, chargements incrémentaux) non pas pour un table space gigantesque, mais pour des partitions de taille beaucoup plus réduite. De même, cela permet de paralléliser les traitements de masse. Tout ceci est évidemment transparent pour la table, autrement dit les applications ne sont pas affectées (sinon que leurs performances ne peuvent qu'être améliorées).
Incidemment, si l’on partitionne le table space utilisé pour la table FEMELLE et que le critère de partitionnement est l’attribut ID_FEMELLE, DB2 Estimator nous apprend que l’on gagne un niveau d’index :
Pour 10 partitions :
Nombre de niveaux d’index : 3.
Racine : 1 page.
Niveau intermédiaire : 76 pages.
Niveau feuille : 24 908 pages.
Pour 80 partitions :
Nombre de niveaux d’index : 3.
Racine : 1 page.
Niveau intermédiaire : 10 pages.
Niveau feuille : 3 114 pages.
Concernant l’index FEMELLE_NOM_X ayant pour clé l’attribut FEMELLE_NOM (de type VARCHAR(32)) :
Intuitivement, cet index est bien plus volumineux que le précédent (du moins dans sa version non partitionnée). En effet, DB2 (V8) considère que cette clé mesure exactement 32 octets. Paradoxalement, c’est le contraire qui aura toutes les chances de se produire...
Il faut en effet tenir compte d’un paramètre important, à savoir en moyenne combien de vaches portent le même nom. Supposons qu’un 'COUNT (DISTINCT FEMELLE_NOM)' nous apprenne qu’il y a 6 700 000 noms distincts. Ce ne sont pas 67 000 000 valeurs de clés qui seront stockées dans l’index, mais dix fois moins : chaque valeur ne figure qu’une fois, accompagnée des RID (4 octets chacun) de chaque homonyme. Dans ces conditions, DB2 Estimator annonce :
Nombre de niveaux d’index : 4.
Racine : 1 page.
Niveau intermédiaire 1 : 28 pages.
Niveau intermédiaire 2 : 2 346 pages.
Niveau feuille : 199 405 pages, contre 228 669 pages ci-dessus.
Si le nombre de noms distincts est de 500 000, soit en moyenne 130 bêtes portant le même nom, les chiffres sont les suivants :
Racine : 1 page.
Niveau intermédiaire 1 : 19 pages.
Niveau intermédiaire 2 : 1 534 pages.
Niveau feuille : 130 351 pages.
Mais le nombre de niveaux d’index reste égal à 4.
A noter que DB2 for z/OS V9 autorise la compression des clés dans les index, mais malheureusement DB2 Estimator ne va pas au-delà de la V8, ce qui pour l’observation est gênant, mais bon...
Partager