Histoire d’index : Importance du choix d’un index cluster avec SQL Server

Le choix d’un index cluster est important pour une table de données. Des bonnes pratiques existent et permettent d’orienter ce choix. Dans ce billet je tenterais d’en expliquer la raison tout en expliquant le fonctionnement interne de ces index et les conséquences d’une mauvaise stratégie de ce type d’indexation. Je ne prétends pas donner la liste exhaustive des bonnes pratiques sur ce point mais d’en donner une première analyse :-)

Pour commencer, faisons un bref rappel de ce qu’est un index : C’est une structure de données organisée sous la forme d’un B-Tree (Balanced Tree). Cet arbre équilibré possède une racine, un voir plusieurs niveaux intermédiaires et un niveau feuille. Ceci est valable aussi bien pour les index clusters que non cluster. La différence majeure est qu’un index cluster est une représentation physique ordonnée d’une table (c’est la table elle même) alors qu’un index non cluster n’en est qu’une structure dupliquée et ordonnée de certaines de ses données. Maintenant que ce rappel est fait nous verrons les principales bonnes pratiques à appliquer sur les index cluster et ce que cela implique.

–> Il est préférable de créer un index cluster avec une contrainte d’unicité.

Attardons nous sur la structure interne d’un index cluster. Lorsque celui-ci n’est pas déclaré unique lors de sa création, SQL Server doit quand même préserver l’unicité des lignes d’index pour une simple et bonne raison : celles-ci peuvent être référencées par des index non clusters en tant que signet utilisées lors des recherches de type Bookmark Lookup par exemple. Par conséquent chaque signet doit être unique pour que chaque recherche puisse se faire. Pour cela SQL Server ajoute un UNIQUIFIER mais  seulement pour les lignes d’index en doublon. Cet UNIQUIFIER est en réalité un entier de 4 octets ajouté à la clé d’index.

Prenons le script suivant :

index_cluster_1

index_cluster_1_1

index_cluster_1_2

Nous avons ici une table comportant des employées. On décide de poser un index cluster non unique sur la colonne nom car nous estimons que celui-ci satisfera la plupart des requêtes qui porteront sur ce critère. Le jeu de données de cette table indique que plusieurs personnes portent le même nom (ce qui est souvent le cas dans les grandes entreprises). Dans ce cas SQL Server est obligé de rajouter une information supplémentaire (UNIQUIFIER) pour transformer les lignes d’index en doublon en ligne d’index unique.

Nous utiliserons la table système sysindexes qui nous permet de faire un premier constat (Cette table système est dépréciée mais celle-ci possède une information non présente avec les nouvelles vues de gestion notamment la colonne keycnt) :

index_cluster_2

La colonne keycnt indique le nombre de clés composant l’index cluster. Ce nombre est égale à 2 dans notre cas alors que nous n’avons défini qu’une seule colonne pour ce même index. Cela signifie que SQL Server a ajouté une information supplémentaire en automatique car l’index cluster n’a pas été défini unique d’une part et qu’il existe également des doublons dans la colonne nom de la table dbo. employee d’autre part.

Récupérons à présent le contenu de la page d’index qui gère la table dbo.employee. Pour cela nous utiliserons conjointement les commandes DBCC IND et DBCC PAGE.

Dans un 1er temps nous devons récupérer le PID de la page d’index (pageType = 2) de la table dbo.employee :

index_cluster_3

 

Maintenant regardons le détail de cette page à l’aide de la commande DBCC PAGE :

index_cluster_4

SQL Server a donc bien ajouté un l’UNIQUIFIER pour les noms en doublon dans la table dbo.employee soit 4 octets par UNIQUIFIER ajouté. Sur des tables volumineuses possédant un grand nombre de lignes de données l’impact peut être important en terme de stockage et en terme de gestion des UNIQUIFIERS par SQL Server.

 

–> Une clé d’index cluster doit être la plus courte possible.

Attardons nous maintenant sur le principe de dépendance des index non cluster avec les index cluster. Reprenons pour cela notre table dbo.employee. Nous décidons maintenant d’ordonner la table par nom et par prénom. Par conséquent nous changeons la définition de l’index cluster de la manière suivante :

index_cluster_5

 

Le nombre de clés composant l’index devrait avoir évolué puisque nous avons changé la définition de l’index (une colonne supplémentaire) :

index_cluster_6

Effectivement ce nombre est maintenant égale à 3 (Les deux colonnes nom et prenom suivies d’un UNIQUIFIER car la table contient encore quelques clés d’index en doublon par rapport aux données de la table dbo.employee).

Ajoutons maintenant un index non cluster et unique sur la colonne emp_id qui est, à priori, une clé candidate pour être clé primaire de notre table.

index_cluster_7

Le résultat de la table système sysindexes est le suivant :

index_cluster_8

Le nombre de clés du nouvel index non cluster est égale à 4. Ce nombre correspond à l’addition des colonnes emp_id composant la clé non cluster suivie des colonnes nom et prenom et de l’UNIQUIFIER de l’index cluster.

Pour s’en assurer nous pouvons regarder le détail de la page d’index de notre index non cluster :

index_cluster_9

Ce que nous avons dit se vérifie donc bien.

Maintenant que nous avons vu en interne la notion de dépendance des index non cluster vis à vis d’un index cluster nous pouvons facilement expliquer pourquoi il est préférable de minimiser au maximum la taille d’un index cluster. Cette taille induit automatiquement une partie de celui d’un index non cluster. En imaginant (et c’est souvent le cas) qu’il existe plusieurs index non cluster pour une table, la clé constituant l’index cluster sera automatiquement reportée autant de fois qu’il existe d’index non cluster. Ceci peut avoir un impact important en terme de stockage sur des bases de données volumineuses et une influence majeure sur le temps et les ressources monopolisés par les opérations de maintenance des index.

 

–> Une clé séquentielle est préférable pour index cluster

Que se passe t’il pour l’index cluster lorsqu’une une nouvelle ligne de données est insérée mais aléatoirement dans la table ? Cette nouvelle ligne sera insérée dans l’index cluster en fonction de la position de sa clé. Pour cela il doit exister assez de place pour cette nouvelle ligne de données dans la page concernée. Si ceci est vérifié notre ligne de données est simplement ajoutée et la page de donnée est mise à jour en conséquence (notamment les numéros de slots car pour rappel un index cluster garantit l’ordre des données). Mais que se passe t’il s’il n’existe plus assez de place pour héberger les données de la nouvelle ligne ? Pour le comprendre, reprenons l’exemple de notre table dbo.employee et insérons un nouveau jeu de données (nous forcerons cette fois-ci les valeurs de la colonne emp_id en utilisant la commande IDENTITY_INSERT) :

index_cluster_10

Récupérons ensuite le contenu de la page hébergeant les lignes de données de la table dbo.employee (Remarquez que dans notre cas il n’existe pour le moment qu’une seule page de données pour cette table. Il n’existe donc pas pour le moment de liens vers d’autres pages de données (valeurs de colonnes NextPageFID, NextPagePID . à 0).

index_cluster_11

Regardons les offsets de cette page :

 index_cluster_12

Nous retrouvons les 15 lignes de données que nous avons inséré. Le slot 14 et l’offset ayant la valeur hexadécimale (0xefa) correspondent au tuple (‘9′, ‘PRENOM_9′, ‘NOM_9′, ‘CCC..’).

index_cluster_13

Note :  L’index cluster étant composé de 2 colonnes de type caractère et que la collation de la base de données étant fixée à French_CI_AS il est par conséquent logique de trouver un tel classement des données de la table avec le tuple (‘9′, ‘PRENOM_9′, ‘NOM_9′, ‘CCC.’) positionné après le tuple (’16’, ‘PRENOM_16′, ‘NOM_16′, ‘CCC.’).

Que se passe t’il maintenant si nous ajoutons une ligne de données supplémentaire en début de table (Clé d’index égale à 3) ?

index_cluster_14

 

index_cluster_15

Un premier constat évident est qu’une page supplémentaire a été ajoutée. En effet comme il ne restait plus assez de place dans la page 79 SQL Server a dû en ajouter pour y accueillir la ligne de données supplémentaire.

Regardons maintenant les lignes de données hébergées par les pages 79 et 595 :

index_cluster_16

Tout à l’heure nous avions 15 lignes de données dans une seule page alors que maintenant il n’en reste plus que la moitié pour la page 79. Le slot 6 et l’offset ayant la valeur hexadécimale (0x1b88) représentants la dernière ligne de données classée de la page correspondent au tuple (’15’, ‘PRENOM_15′, ‘NOM_15′, ‘CCC.’) de la table dbo.employee.

index_cluster_17

Notez également que les données de l’entête de la page 79 a été mis à jour avec le paramètre m_next_page :

index_cluster_18

La page qui suit la page 79 est bien celle ayant l’ID 595.

Regardons à présent la page 595 :

index_cluster_19

Les 8 autres lignes de données manquantes dans la page 79 sont en fait maintenant hébergées par cette page. Le slot 8 correspond au tuple (‘9′, ‘PRENOM_9′, ‘NOM_9′, ‘CCC.’).

index_cluster_20

Cela donne droit à une explication : l’insertion d’une ligne de données dans ce cas a provoqué ce que l’on appelle un SPLIT de pages car comme nous l’avons vu il n’existait plus de place disponible dans la page 79. Au niveau feuille d’un index cluster, cette opération est très coûteuse car cela oblige SQL Server a créé une nouvelle page, à diviser ensuite en 2 le jeu des lignes de données de la page pleine et d’en insérer la moitié dans la nouvelle page. De plus, il faut tenir à jour les liens de la page pleine (paramètres d’entête) ainsi que les pages d’index parentes de l’index pour prendre en compte la nouvelle page. Bien entendu toutes ces opérations sont  également enregistrées dans le journal des transactions. Ce même phénomène existe pour les ordres SQL exécutés à l’aide de la commande UPDATE. En effet, pendant une opération de mise à jour il se peut qu’une ligne de données change de pages de données de part sa nouvelle position dans l’index. Dans ce cas SQL Server transforme l’instruction UPDATE en deux instructions distinctes DELETE ET INSERT. Si la page cible qui doit héberger la ligne de données à déplacer est pleine, il se produira un SPLIT de page avec toutes les conséquences que cela induit.

Comment éviter ce problème ? Il existe plusieurs solutions :

- On peut jouer avec le paramètre FILLFACTOR de l’index cluster. Cet paramètre permet de garder de l’espace supplémentaire dans l’index au niveau feuille pour supporter les futures insertions aléatoires de lignes de données. L’inconvénient de cette méthode est que la taille de l’index s’en retrouve affectée de part l’espace supplémentaire alloué et il n’attenue le phénomène de SPLIT que temporairement. En effet, une fois que la page de données remplie, un éventuel SPLIT devient alors possible.

- Une autre solution consiste à choisir une colonne dont les valeurs sont incrémentales (et unique) pour que les insertions se fassent toujours à la fin de la table. Le processus de SPLIT de pages est alors évité.

–> Un index cluster doit de préférence être durable dans le temps

Nous avons vu un peu plus haut qu’il existait un lien de dépendance des index non cluster vis à vis des index cluster. La clé de l’index cluster se retrouve automatiquement dan un index non cluster. Que se passe t’il si la clé d’un index cluster est appelé à changer ? Bien évidement ce changement doit être automatiquement reporté dans l’index non cluster, ce qui ajoute une charge supplémentaire de travail à SQL Server. Selon le nombre d’index non cluster dépendants et le taux de changement d’une clé d’index cluster, cela peut très vite s’avérer coûteux. Je vous laisse le soin de regarder en interne la mise à jour des pages des index concernés.

Enfin dernière chose que je voulais aborder dans ce billet est que Microsoft nous dit également qu’un index cluster est idéal pour les requêtes qui ramènent un ensemble de données consécutifs (à l’aide de l’instruction BETWEEN par exemple). Pourquoi ? Les pages d’index sont liées par une double liste chaînée. Nous avons vu que SQL Server tenait à jour ces liens par le biais de paramètres dans l’entête de chaque page. Un index cluster garantie également que les lignes de données de l’index soient toujours classés selon sa définition (Nous l’avons vu dans cet article et je vous renvoie à ce billet pour plus de détail). Il suffit dans ce cas de trouver la première ligne de données en parcourant l’index depuis la racine et ensuite de parcourir une à une les pages de données adjacentes sans avoir besoin de remonter à un quelconque niveau de l’arbre de l’index puisque les données recherchées sont par nature adjacentes dans un intervalle donné. Ceci n’est pas le cas pour un index non cluster qui ne garantit pas que le niveau feuille de l’index soit correctement trié.

index_cluster_21

Dans la plupart des cas, ce choix peut paraître évident car il s’agit en principe de la clé primaire d’une table mais comme toute règle il existe certaines exceptions. C’est à ce moment là qu’il faut bien comprendre les conséquences que peuvent engendrer la création d’un index cluster tant sur le côté positif que négatif. Bon indexage !!

David BARBARIN (Mikedavem)
Elève ingénieur CNAM Lyon

Laisser un commentaire