[SQL Server] Un peu de théorie sur les indexes…

Ce billet traite de l’importance d’un index dans l’univers de SQL Server, et notamment des différents concepts théoriques qui lui sont associés (architecture, fonctionnement,…). Nous allons également aborder la fragmentation d’indexes.

Notions d’index et de B-Tree

Un index est une structure de données organisée de la même manière qu’un arbre équilibré (Balanced tree ou B-Tree)[1]. Il permet, à SQL Server (et aux systèmes de gestion de bases de données, en général) de retrouver rapidement des enregistrements spécifiques, à l’instar de l’index d’un livre permettant, au lecteur, de retrouver facilement la page ou le mot-clé recherché.

Les indexes sont créés sur des colonnes de tables ou de vues. Et le stockage peut être effectué par lignes tout comme il peut être effectué par colonnes (depuis SQL Server 2012, via l’index de type ColumnStore).

Voici ci-dessous un exemple (très simplifié) de B-Tree d’un index contenant 20 enregistrements :


Supposons que l’index en question pointe vers une colonne appelée Product_ID et contenant 20 enregistrements. Et supposons que l’on veuille retrouver tous les enregistrements (ou lignes) dont le numéro de produit est égal à 3. Voici donc comment SQL Server travaille avec une B-Tree :

  1. Durant la recherche des lignes de données répondant au critère « Produits d’identifiant 5 », SQL Server commence toujours par le niveau racine, ce qui signifie que le scan se fait d’abord sur toutes les lignes à la racine. Dans notre exemple, la racine indique qu’il y a entre 1 et 20 lignes qui pointent vers différentes pages dans le niveau intermédiaire.
  2. Comme le numéro de ligne que nous recherchons n’est pas présent au niveau racine, et comme l’index est dans un ordre numérique croissant, SQL Server sait que la valeur recherchée se situe après 1 mais avant 20. Donc, pour retrouver les lignes ayant une valeur égale à 3, SQL Server va dans le niveau intermédiaire, dans la page dont le numéro de ligne de départ est 1.
  3. La page d’index en question pointant vers les enregistrements 1 à 10 du niveau feuille, et SQL Server sachant que la valeur de la ligne recherchée est supérieure à 1 mais inférieure à 10, il va alors descendre vers le niveau feuille afin de tenter de la retrouver dans la page dont le numéro de ligne de départ est 1 et de fin 5, puisqu’il sait que la valeur recherchée est comprise entre ces deux valeurs (l’autre page ne renvoyant que des valeurs comprises entre 6 et 10).
  4. Selon le type d’index traité (cluster ou non-cluster), SQL Server récupèrera le pointeur RID si la B-Tree est celle d’un index non-cluster, la ligne de données entière s’il s’agit d’un index en cluster. Voir plus loin.
Remarquons qu’une B-Tree peut avoir plusieurs niveaux intermédiaires. Dans notre exemple, un seul niveau intermédiaire a été choisi pour des raisons de simplification.

Comme on peut le constater dans notre exemple ci-dessus, un index fournit une manière rapide de rechercher des données basée sur les valeurs au sein de ces colonnes. Par exemple, si un index est créé sur une colonne de clé primaire, et qu’ensuite une recherche d’une ligne de données basée sur une des valeurs de clé primaire d’une table est demandée, SQL Server trouve d’abord la valeur dans l’index, puis utilise celui-ci pour rapidement localiser l’intégralité de la ligne de données. Sans la présence d’un index de ce type, SQL Server effectue un scan de table (i.e., balayage de toute la table) afin de localiser la ligne ce qui pourrait impacter les performances.

En conclusion : l’importance d’un index est telle que ce dernier a une influence significative sur les performances d’une requête. En effet, une requête utilisant des tables peu, pas ou mal (ou trop) indexées a de grandes chances de rencontrer des problèmes de performances, tandis qu’une requête utilisant des tables bien indexées peut voir ses performances s’améliorer de façon optimale.

Index en cluster et index non-cluster

Il existe de nombreux types d’indexes[2], dont les plus connus et utilisés sont l’index en cluster (ou clustered index) et l’index non-cluster (non-clustered index). Et la différence entre les 2 est la suivante :

  • L’index en cluster (ou ordonné) est un index au sein duquel les enregistrements sont physiquement triés, et ses pages de données (aussi appelées pages d’indexes) au niveau feuille et les numéros d’enregistrements au niveau intermédiaire. C’est ainsi qu’une table ne peut avoir qu’un index en cluster à la fois dans la mesure où les lignes ne peuvent être triées qu’en un seul ordre physique. Par défaut, à chaque création d’une clé primaire sur une table, SQL Server crée automatiquement un index en cluster.
  • L’index non-cluster (ou non-ordonné) est un index au sein duquel le tri logique des enregistrements (i.e., tri des pages d’indexes) ne correspond pas au tri physique des enregistrements (sur le disque). De plus, au niveau structurel, seuls les numéros d’enregistrements sont placés au niveau feuille, ce qui permet donc, à une table, de pouvoir disposer de plusieurs indexes non-clusters. Par contre, il ne peut y avoir qu’un maximum de 249 indexes non-clusters par table.
De manière générale, du point de vue des performances :

  • Un index en cluster est utile :
    • Sur les colonnes contenant un très grand nombre de valeurs différentes (souvent le cas des primary keys).
    • Sur les tables régulièrement accédées séquentiellement en lecture.
    • Sur les colonnes concernées par la spécification d’un intervalle de valeurs au sein d’une requête (via BETWEEN ou les opérateurs de comparaison).
    • Sur les colonnes concernées par des requêtes retournant un très grand nombre de résultats.
    • Sur les colonnes concernées par des jointures (typiquement souvent le cas des foreign keys).
    • Sur les colonnes spécifiées dans des ORDER BY ou GROUP BY, ce qui élimine la nécessité, pour l’optimiseur SQL, de trier les lignes d’enregistrements, l’index en cluster le faisant déjà.
  • Un index non-cluster est utile :
    • Sur les colonnes régulièrement mises-à-jour.
    • Sur les colonnes concernées par une clause WHERE de sélectivité.
    • Sur les colonnes retournant peu de résultats.

Notons que dans le cas d’un index couvrant (include) qui inclut des colonnes supplémentaires, les valeurs des colonnes incluses seront placées dans le niveau feuille. De cette façon, SQL Server pourra non seulement traiter la ou les colonnes indexées, mais également celles incluses (ce qui réduit les risques de key ou RID lookups coûteux).

Par ailleurs, concernant les clés naturelles (c’est-à-dire, non-numériques), l’index en cluster effectue ses tris par ordre alphabétique.

Outre l’index en cluster et l’index non-cluster, citons notamment l’index couvrant (ou de type include, qui inclut des colonnes), l’index composite (qui indexe plusieurs colonnes), l’index de type unique, l’index de type XML, l’index de type filtered (à partir de SQL Server 2008, pour les colonnes à filtrer), l’index de type column-store (à partir de SQL Server 2012, pour le stockage de données par colonne et non plus par ligne afin de réduire le nombre de pages à parcourir, et donc la charge I/O). Nous n’allons pas détailler leurs cas en détail dans ce billet.

Pour créer un index en cluster ou non-cluster, cela est très simple en T-SQL :

  • Index en cluster sur une colonne MaTable_ID d’une table appelée MaTable :
CREATE CLUSTERED INDEX IDX_MaTable_ID ON dbo.MaTable(MaTable_ID)
GO
  • Index non-cluster sur une colonne Nom d’une table appelée MaTable :
CREATE NONCLUSTERED INDEX IDX_Nom ON dbo.MaTable(Nom)
GO
  • Index sur une colonne Nom d’une table appelée MaTable et couvrant (ou incluant) une colonne Description :
CREATE NONCLUSTERED INDEX IDX_Nom ON dbo.MaTable(Nom) INCLUDE(Description)
GO
Notons que quand un index est créé sans précision de son type (CLUSTERED, NONCLUSTERED,…), SQL Server va automatiquement choisir de le créer en tant qu’index non-cluster.En outre, s’il n’est pas précisé, le fill factor utilisé sera celui par défaut de l’instance.

Facteur de remplissage (fill factor)

Le fill factor indique le pourcentage de remplissage d’une page d’index. Plus de détails ici.

Relation entre les pages d’indexes non-cluster et les pages d’index en cluster ou les pages de données (heap)

Cette section explique brièvement comment les indexes non-clusters peuvent retrouver des lignes de données spécifiques au sein d’une table heap ou avec un index en cluster.

Chaque ligne d’index non-cluster stocke (au niveau feuille), en plus d’une clé de valeur non-cluster, un pointeur vers soit une ligne de données quand il s’agit d’une table heap, soit une ligne d’index en cluster quand il s’agit d’une table indexée en cluster.

Ainsi :

  • Dans le cas d’une table avec index en cluster, le pointeur est la clé d’index en cluster pour la ligne. De ce fait, chaque fois qu’un index non-cluster fait référence à une ligne d’index en cluster par clé, SQL Server retrouve ladite ligne dans l’index en cluster en utilisant la clé d’index en cluster stockée dans la ligne correspondante de l’index non-cluster au niveau feuille. Ce type de recherche est appelé Key lookup.
  • Dans le cas d’une table heap, ce pointeur est appelé RID (ou Row ID ou identifiant de ligne) et inclut des informations sur l’identifiant du fichier (File ID), l’identifiant de la page (Page ID) et le numéro de ligne au sein de la page de données. Ainsi, chaque fois qu’un index non-cluster fait référence à une ligne de données par RID, cela signifie qu’il va demander un numéro de ligne à une page spécifique d’un fichier de données spécifique. Puis ensuite, SQL Server, munit du RID, va consulter la table de décalage de lignes (offsets) de la page de données spécifique pour retrouver (la position de) la ligne désirée en utilisant sa valeur d’offset. Ce type de recherche est appelé RID Lookup.

On rappelle qu’au sein d’une page de données, grâce à la table de décalage de lignes, une ligne peut changer de position sans changer de RID. Cela assure aux entrées d’indexes de ces lignes la possibilité de ne pas avoir à systématiquement être mises à jour à chaque changement.

Remarquons que concernant la relation entre une page d’index en cluster et une page de données (table heap), il faut savoir que ces 2 éléments sont communs, l’index en cluster prenant la place de la table concernée.

Remarques sur la fragmentation d’indexes

Tout index peut être fragmenté, que ce soit faiblement, moyennement ou fortement. En effet, plus il est utilisé, plus son taux de fragmentation logique augmente.

Il existe 2 types de fragmentation :

  • La fragmentation externe (ou logique) : intervient quand, au sein d’un index, une page au niveau feuille n’est pas dans un ordre logique. En d’autres termes : la fragmentation externe se manifeste quand l’ordre logique d’un index (i.e., tri des pages) ne correspond pas à son ordre physique (sur le disque). Cela pousse SQL Server a multiplier les opérations I/O pour retourner un résultat ordonné. De manière générale, ce type de fragmentation n’est pas un problème pour les requêtes qui tournent peu de résultats, et ne nécessitant pas un résultat ordonné. C’est pour cette raison que les index en cluster sont plus efficaces que ceux non-clusters pour retourner un très grand nombre de résultats.
  • La fragmentation interne : intervient quand il y a trop d’espace disponible au sein des pages d’un index. Bien que cela puisse être un avantage pour les requêtes DML (Data Modification Language), cela prolongerait la durée d’exécution des requêtes de lecture (étant donné les lectures supplémentaires que doit réaliser SQL Server pour retrouver un ensemble de données correspondant au résultat recherché), sans parler du fait qu’il y a risque potentiel d’augmentation… de la volumétrie de l’index. Par contre, s’il n’y a pas assez d’espace (ou plus du tout), les requêtes DML causeront des splits de pages ce qui monopoliserait également des ressources systèmes additionnelles. C’est pour cette raison que le fill factor joue un rôle important pour tout index.

Afin de maintenir un index à un bon niveau de santé, outre l’importance de son fill factor (notamment en ce qui concerne la fragmentation interne), il est crucial de s’assurer que la (ou les) requête(s) qui l’utilise(nt) sont correctement codées ou utiles (le traitement d’un trop grand nombre de résultats peut avoir un impact certain sur la santé d’un index utilisé), que les types d’indexes sont savamment choisis et, surtout, que des jobs de maintenance d’indexes sont régulièrement utilisés et planifiés.

Il existe 2 types de réindexation :

  • La réorganisation d’indexes, qui consiste à défragmenter à chaud les pages d’un index (au niveau feuille) en les réorganisant physiquement afin qu’elles puissent correspondre à l’ordre logique des nœuds feuilles, de gauche à droite. Cela compacte également les pages d’indexes en se basant sur la valeur du fill factor.
  • La reconstruction d’indexes, qui consiste à recréer l’index traité.

La réorganisation d’indexes, moins consommatrice en ressources, est plus adaptée dans le cas d’un index faiblement (5%) ou moyennement (=<30-40%) fragmenté tandis que la reconstruction d’indexes, plus consommatrice en ressources, est plus adaptée dans le cas d’un index fortement fragmenté (>30-40%).

Du point de vue des bonnes pratiques, lancer une opération de défragmentation n’est pertinent que si, en plus de tenir compte des recommandations du paragraphe précédent, il y a au moins 1000 pages fragmentées par index traité. En fait, la fragmentation des petits indexes peut, souvent, ne pas être corrigées. En effet, les pages des petites indexes sont stockées sur des extents mixtes pouvant être partagés par, jusqu’à, 8 objets différents. C’est également pour cette raison qu’il est plus pertinent de se concentrer sur les indexes avec au moins 1000 pages[3].

Soulignons que :

  • En cas de réorganisation d’index, il est important d’effectuer une mise-à-jour des statistiques des indexes concernés. En effet, une telle opération (contrairement à la reconstruction d’indexes) rend obsolète les informations des statistiques associées aux indexes traités. Et par ailleurs, la reconstruction d’indexes est une opération offline dans la mesure où elle pose un verrou exclusif sur toutes les pages d’indexes traitées[4].
  • La réorganisation d’indexes implique que l’option ALLOW_PAGE_LOCKS des indexes à traiter soit activée[5] afin de permettre à SQL Server de verrouiller chaque page à ordonner durant le traitement.
  • Les indexes de plus de 128 extents sont reconstruits en 2 phases :
    • Phase logique : les unités d’allocation des indexes traités sont marquées « libres » et les lignes de données associées sont copiées, triées et déplacées vers de nouvelles unités d’allocation crées pour la reconstruction de l’index concerné.
    • Phase physique : les unités d’allocation précédemment « libérées » sont physiquement supprimées via de petites transactions lancées en arrière-plan, et ne nécessitant pas trop de verrous.
  • Il n’est pas nécessaire de défragmenter des indexes dont le taux de fragmentation est inférieur à 5%. En effet, le gain post-réindexation, dans ces cas-là, est faible (voire inexistant), sachant que toute opération de réindexation (que ce soit la réorganisation ou la reconstruction d’indexes) nécessite un minimum de ressources systèmes.
  • Pour déterminer le niveau de santé d’un index :
    • Utilisez la DMV sys.dm_db_index_physical_stats pour les versions supérieures ou égales à SQL Server 2005[6].
    • Utilisez DBCC SHOWCONTIG pour les versions inférieures à SQL Server 2005, et surveillez notamment[7]:
      • Avg. Pages per Extent (rapport entre le nombre de pages scannées et le nombre d’extents scannés) qui doit être égal à 8.
      • Scan Density qui doit être suffisamment proche de 100%.
      • Logical Scan Fragmentation qui doit être suffisamment bas (entre 0 et 10%).
      • Extent Scan Fragmentation qui doit être proche de 0%.
      • Avg. Page Density qui doit être suffisamment élevé.

En résumé…

Dans ce billet, nous avons pu aborder différents concepts propres à l’architecture d’un index et discuter des différences fondamentales entre un index en cluster et un index non-cluster. Dans le futur, nous traitons de cas pratiques de l’utilisation d’un index et de diverses méthodes de gestion d’indexes (i.e., détection d’indexes malades, réindexations,…).



[1] Un arbre équilibré est une structure informatique, constituée de feuilles et de nœuds (contenant une ou plusieurs lignes d’enregistrements), mise en œuvre sous une forme triée et permettant une exécution rapide des opérations de recherche, d’insertion et de suppression.[2]Outre l’index en cluster et l’index non-cluster, citons notamment l’index couvrant (ou de type include, qui inclut des colonnes), l’index composite (qui indexe plusieurs colonnes), l’index de type unique, l’index de type XML, l’index de type filtered (à partir de SQL Server 2008, pour les colonnes à filtrer), l’index de type column-store (à partir de SQL Server 2012, pour le stockage de données par colonne et non plus par ligne afin de réduire le nombre de pages à parcourir, et donc la charge I/O). Nous n’allons pas détailler leurs cas en détail dans ce billet.

[3]Pour vous en convaincre : http://sqlblog.com/blogs/kalen_delaney/archive/2008/02/28/fragmentation-revisited.aspx.

[4]Néanmoins, depuis SQL Server 2008, une reconstruction d’indexes online est possible, mais au prix d’une surconsommation des ressources CPU et I/O, notamment.

[5]Référez-vous au BOL pour plus de détails : http://msdn.microsoft.com/en-us/library/ms189076.aspx.

[6]Plus de détails ici : http://msdn.microsoft.com/en-us/library/ms188917.aspx.

[7]Vous pouvez étudier en détail le lien suivant : http://www.sql-server-performance.com/2004/index-fragmentation/2.

Publicités

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s