Nous avons vu dans un précédent billet que les index gérés sous SQL Server étaient des arbres B-Tree. Nous verrons aujourd’hui comment SQL Server parcourt ces arbres en interne pour retrouver les informations recherchés lors des requêtes et ceci pour chaque type d’index.

1- Index cluster

Commençons par créer une table dbo.employee et une clé primaire sur la colonne emp_id avec un jeu de données.

 

Nous pouvons visualiser la structure physique de l’index grâce à la DMF sys.dm_db_index_physical_stats :

L’index cluster de la table dbo.employee possède trois niveaux. Le premier niveau (index_level = 2) correspond à la racine de l’index cluster. Le deuxième niveau (index_level = 1) correspond au niveau intermédiaire de l’index et enfin le troisième niveau correspond au niveau feuille de l’index dans lequel nous retrouvons les 199999 lignes de données précédemment. SQL Server a réservé 1014 pages à cet effet.

Faisons un rapide calcul : 1014 x 8096 soit environ 8016 Ko pour héberger 199999 x 40 = 7812 Ko. Toutes les pages de données ne sont pas pleines du fait de la variation de la longueur des noms er prénoms insérés au fur et à mesure dans table. Les colonnes min_record_size_ind_bytes et max_record_size_in_bytes permettent de connaître respectivement les tailles minimum et maximum d’une ligne de données ou d’index dans la table dbo.employee. Je reparlerais du calcul de la taille d’un index dans un prochain billet.

Attardons nous à voir comment s’effectue le parcours de cette structure de données en interne par SQL Server. Pour cela nous prendrons un exemple simple : nous rechercherons le nom et le prénom d’un employé ayant le matricule 60000 ce qui correspond à la requête suivante :

Tout d’abord il faut commencer par trouver la page représentant la racine de l’index à l’aide de la commande DBCC IND :

C’est la page 1255 qui est la la racine de l’index. Le type de page indique que nous avons à faire à une page d’index (PageType = 2). Cette page se trouve au niveau le plus haut de l’index (indexLevel = 2). Nous avons vu précédemment que cet index possédait 3 niveaux (de 0 à 2). Remarquez également que cette page ne possède aucun lien avec d’autres pages (colonnes NextPageFID, NextPagePID, PrevPageFID et PrevPagePID à 0).

Regardons le contenu de cette page à l’aide de la commande DBCC PAGE :

Chaque ligne de l’index contient une clé (emp_id key) et une page enfant correspondante (ChilPageId). Nous pouvons en déduire facilement que pour trouver la clé d’index dont la valeur est égale à 60000 nous devons nous rendre à la page 1256 car la valeur de clé d’index la plus basse gérée par cette page est inférieure à la clé recherché (54907 inférieur à 60000.

En suivant le même le raisonnement on en déduit que notre ligne de données se trouve à la page 927. Notez au passage que nous nous retrouvons à présent au niveau intermédiaire de l’index (Level = 1).

Nous avons donc bien retrouvé notre ligne de données qui correspondait à notre recherche (emp_id = 60000). Pour arriver à ce résultat SQL Server a lu 3 pages. Vérifions le à l’aide de l’instruction SET STATISTICS IO :

Effectivement il y a eu 3 lectures de pages pour arriver à ce résultat. Les pages étant déjà dans le cache des données, c’est la raison pour laquelle on ne voit que des lectures logiques.

Représentation graphique du parcours de l’index :

 

2- Index non cluster

Avant de commencer à étudier le parcours d’un index non cluster nous devons apporter tout d’abord quelques précisions quant à la structure interne d’un tel index. Premièrement à l’inverse d’un index cluster, le niveau feuille ne contient pas les données de la table mais des lignes d’index faisant référence à l’aide de signets aux données de la table. Ensuite, selon si la table hôte contient ou pas un index cluster déterminera la structure interne des lignes d’index non cluster. Nous le verrons par la suite.

Note : Il existe plusieurs autres facteurs qui déterminent la structure interne d’une ligne d’index non cluster mais ne nous le verrons pas dans ce billet. Nous insisterons simplement sur la différence qu’il existe au niveau des signets lorsqu’il existe un index cluster ou pas.

–> Cas d’un index non cluster dépendant d’un index cluster

Commençons par créer un index non cluster sur la table dbo.employee utilisée précédemment et possédant un index cluster.

L’index a bien été créé avec un id qui est égale à 2

La racine de l’index non cluster correspond à la page 175.

Le parcours se fait de la même manière que pour un index cluster. Nous recherchons un employée dont le nom est ‘nom_60000′. La requête SQL est la suivante :

. avec le plan d’exécution suivant :

Le plan d’exécution indique qu’une opération de recherche de clé sur l’index non cluster (Index Seek) est effectuée pour retrouver la ligne d’index correspondante à notre recherche. Cependant comme l’index ne satisfait pas entièrement notre demande car il ne possède pas l’ensemble des informations à retourner, SQL Server doit parcourir ensuite l’index cluster extraire le reste des informations nécessaires. C’est pour cela qu’une opération supplémentaire est présente (Key Lookup). Cette opération prend en paramètre la clé d’index cluster de la ligne d’index non cluster.

Voyons maintenant ce qui se produit en interne. Nous adopterons la même méthode utilisée pour un index cluster.

Nous remarquons tout d’abord que l’index non cluster est constitué de sa clé d’index (lastname) mais aussi de la clé d’index cluster comme signet. Ensuite la clé d’index que nous recherchons est à l’évidence gérée par la page 296.

On continue . la clé d’index recherchée est gérée par la page d’index 1651.

Nous retrouvons finalement la clé d’index non cluster correspondante ainsi que la valeur du signet vers notre index cluster (emp_id key = 60000). Ce signet est ensuite utilisé pour la seconde opération de recherche sur l’index cluster (opérateur Key Lookup). Le processus de recherche est exactement le même que les précédents. Je vous laisse le constater si le cour vous en dit :-). Vous pourrez également vérifier que SQL Server doit lire 6 pages de données pour trouver les données nécessaires à la requête.

Représentation graphique du parcours de l’index :

–> Cas d’un index non cluster dépendant d’une table HEAP (sans index cluster)

Regardons maintenant les différentes existantes avec un index non cluster sur une table HEAP. Le script suivant copie la structure et les données de la table dbo.employee vers une table que nous appelerons dbo.employee_no_cluster en utilisant la commande SELECT .. INTO . . Cette table ne possédera pas d’index cluster.

Créons ensuite un index non cluster sur la colonne lastname de la table dbo.employee_no_cluster :

Récupérons le détail de la page racine de cet nouvel index. La commande DBCC IND nous indique que la page concernée porte l’ID 3026.

Le signet de l’index non cluster est cette fois ce que l’on appelle un RID (ou Row Identifier). Ce RID est composé des numéros de fichier, de page et de slot qui permettent de retrouver précisément la ligne de donnée recherche. En interne cette valeur est stockée en hexadécimale comme nous pouvons le constater. La fonction suivante permet de convertir cette valeur dans un format FileID:PageID:Slotnumber :

Reprenons le même exemple que tout à l’heure. (Je ne ferais pas à nouveau la démonstration dans son entier. Le but ici est de voir la différences existantes avec une table HEAP). La requête correspondante et le plan d’exécution sont les suivants :

 

L’opérateur utilisé de ce cas est une recherche par RID. (opérateur RID Lookup). Une fois que l’index non cluster a été parcouru, une deuxième recherche est lancée en se basant cette fois ci sur le RID trouvé dans la page d’index non cluster afin de retrouver la ligne de données recherchée dans les pages de la table HEAP.

La page d’index au niveau feuille correspondant à la recherche est la page no 3319.

La valeur du RID de la ligne d’index est 0x3608000001002B00 en hexadécimale. A ce stade SQL Server convertit cette valeur pour connaître la position exacte des données recherchées. Si l’on exécute notre fonction de conversion nous obtenons :

. La ligne de données se situe donc dans le fichier no 1, la page 2102 au slot 43. C’est ici que la deuxième opération de recherche (RID Lookup) s’effectue pour extraire les données de la page 2102 au slot 43 :

. nous retrouvons bien notre ligne de données avec les informations nécessaires manquantes. Vérifions, comme tout à l’heure, à l’aide de la commande SET STATISTICS IO le nombre de pages nécessaires pour retrouver les données nécessaires à la recherche :

Cette fois, il y a eu 4 lectures logiques et une opération de balayage pour retrouver les données. Comme nous l’avons vu un peu plus haut, il faut simplement trois pages pour arriver à la ligne d’index correspondante au prédicat de la requête. Cette page nous a fournit le RID de la ligne de données dont il faut extraire les informations. Il faut savoir que les pages d’une table HEAP ne sont pas reliées entre elles comme pour un index cluster. Par conséquent le seul moyen que possède SQL Server pour localiser la page qui héberge notre ligne de données est de faire une recherche d’affectation dans le plan d’index de la table. Il s’agit de lire ici la page IAM gérant la table dbo.employee_no_cluster avec le RID fourni par l’index non cluster et de retrouver la page de données correspondante de la table. Ceci explique pourquoi nous avons une lecture logique et une opération de balayage supplémentaire.

Représentation graphique du parcours de l’index :

Voilà en ce qui concerne le parcours des index avec SQL Server pour les index cluster et non cluster. Il peut être nécessaire de connaître comment SQL Server parcourt ces structures d’index pour pouvoir les créer judicieusement d’une part et pour la conception de certaines requêtes par rapport aux opérateurs utilisés d’autre part !!!

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