Tout sur l’index ! (partie 1/2)

Qu’est ce qu’un index ? A quoi ça sert ? Quel gain sont obtenus avec des index ? Comment est structuré un index ? Pourquoi mon index n’est pas utilisé ? Pourquoi les index se fragmentent-ils ?… Voici quelque unes des questions qu’aborde cet article !

1 – Qu’est ce qu’un index ?

Définition « mathématique » de l’index (bases de données) : un index est une structure de données redondante organisée de manière à accélérer certaines recherches.

Par sa nature un index est une information redondante qui n’est en aucun cas nécessaire à la logique relationnelle (c’est d’ailleurs pourquoi les index n’existent pas dans le langage SQL).

Dans le principe, la technique de l’indexation consiste à découper la surface de stockage de l’information en plus petites parties ordonnées et ce de manière récursive. Ainsi retrouver une information indexée consiste à naviguer de branche en branche dans l’index en éliminant à chaque étape un grand nombre de cas. Ce parcours peut être fait notamment par dichotomie ou parcours d’arbre. Nous verrons quelques uns des algorithmes en seconde partie du présent article.

=> 1.1 – exemples :

Par exemple, si vous devez donner rendez vous à une personne qui ne vous connais pas encore, vous pouvez vous contenter de donner le nom de la ville ou vous habitez pour qu’il vous retrouve. Sans précision de rue cette personne devra chercher longtemps votre habitation, car il devra visiter un à un l’ensemble des logements de la ville. Si vous lui donnez le nom de la rue (dont les nomenclatures ont commencés au moyen âge) cette recherche sera déjà moins longue. Avec le numéro dans la rue (notion datant de la révolution) ce sera quasi immédiat.
Voici donc un index que vous utilisez tous les jours sans le savoir.
Même chose pour le téléphone. Au début de son invention, les demoiselles (du téléphone) connectais les quelques abonnées par référence à leur nom dans une ville. C’est ainsi que pour obtenir le marquis de Carabat à Pampelune depuis Paris, quartier du Maris, l’opératrice du centrale Archive appelais l’opératrice de Siant Tropez et les deux opératrices opéraient un câblage physique entre les deux points de la ligne.
Puis vint une première numérotation par ville. On le voit ici avec la transformation du central de Mâcon.
A cette même époque Fernand Raynaud avait du mal à obtenir le 22 à Asnières !
Finalement les transformations du téléphone, à partir des années 70 et jusqu’à nos jours, permettent aujourd’hui d’accéder à quiconque sur la planète à partir d’un simple numéro, reléguant ainsi les opératrices au rangs d’assistantes pour la recherche dans les annuaires !

En fait nous sommes environnés d’un grand nombre d’index sans le savoir, une immatriculation de véhicule, un numéro de compte en banque votre n° se sécurité sociale, un code postal sont autant d’index que vous utilisez tous les jours !

=> 1.2 – Intérêt de l’index

L’accès aux lignes des tables se fait séquentiellement, c’est à dire que pour trouver une information précise, il faut parcourir une à une et l’une après l’autre les lignes de la table. Il faudra aussi parcourir toute la table. Par exemple pour chercher un Marcel Dupont dans une table d’individus, il faut lire toutes les lignes, car il peut y en avoir plusieurs et par malchance l’un d’entre eux peut figurer en dernière position dans la table.

Un index permet d’accélérer certaines recherches (les plus classiques) par le fait que la structure sous-jacente à l’index est spécialement conçue pour accélérer certaines recherches, notamment par le tri des données indexées.
Ainsi pour rechercher un Marcel Dupont dans un index sur Nom + Prénom, on peut agir par dichotomie et donc éliminer un nombre important de cas, d’autant plus important que le nombre de données est important (échelle exponentielle).
L’efficacité d’une telle recherche est en O(log2(n)) (notation landau), c’est à dire que le nombre de cas scrutés et le gain entre lecture séquentielle des lignes et lecture dichotomique est le suivant :


Nombre de ligne            Nombre d'itération Gain en %
-------------------------- ------------------ -----------  
         5                 3                  40  
        10                 4                  60
        50                 6                  88
       100                 7                  93
       500                 9                  98,2
     1 000                 10                 99
     5 000                 13                 99,74
    10 000                 14                 99,86
    50 000                 16                 99,968
   100 000                 17                 99,983
   500 000                 19                 99,9962
 1 000 000                 20                 99,998  
 5 000 000                 23                 99,99954
10 000 000                 24                 99,99976

Le gain devient très important à mesure que le nombre de ligne croit. Pour une petite table un index n’a donc pas un gain très intéressant. Nous explorerons plus loin ce point.

On constate donc qu’un index n’est pas nécessaire à l’information, mais permet une efficacité de recherche optimale (ce pourquoi il est créé d’ailleurs). Mais attention, pour les recherches pour lequel il est prévu… Par pour toutes les recherches !

Seul inconvénient, il constitue une sorte de redondance dans le sens ou il oblige à stocker plus de données que l’information de base. Il augmente dons le volume globale de la base, mais nous verrons que, paradoxalement, il permet aussi de réduire grandement le volume utile de la base !

=> 1.3 – index créés automatiquement

Les SGBDR créée systématiquement un index chaque fois que l’on pose une clef primaire (PRIMARY KEY) ou une contrainte d’unicité (UNIQUE) sur une table. En revanche, il n’y a pas d’index créé automatiquement par le SGBDR derrière une FOREIGN KEY (clef étrangère).

Certains SGBD (en principe non relationnels) créé des index systématiquement sur toutes les colonnes. C’est le cas de Sybase IQ récemment racheté par SAP.

=> 1.4 – composition d’un index (clef d’index et vecteur)

Un index peut être composé de plusieurs colonnes et cet ensemble est appelé clef d’index. Par exemple, sur une table comportant les colonnes A, B, C, D, E, F et G, poser un index sur les colonnes A, C et G font que l’ensemble A, C, G est la clef de l’index.
L’ordre des colonnes de la clef (que l’on appelle vecteur) revêt une importance particulière. En effet un index composé des colonnes A, B, C est totalement différent d’un index créé sur les colonnes B, C et A. Les effets de chacun de ces deux index sont différent parce que la composition interne des données en vue de l’accélération des recherches n’est pas orientés dans le même sens parce que, dans la structure des index on trouve une organisation ordonnées… En fait dans un index le contenu des colonnes est concaténé avant le tri.

Voici par exemple le contenu d’un index composé des colonnes NOM, PRENOM et DATE_NAISSANCE d’une table contenant des individus :


NOM             PRENOM        DATE_NAISSANCE
--------------- ------------- --------------
ABELARD         Alain         26/04/1895
ABELARD         Alain         16/08/1969
...
ABELARD         Marcel        12/11/1950
...
ABELARD         Zoé           17/02/1987
ABELARD         Zoé           11/06/1992
 
...
 
MARTIN          Alain         16/11/1899
MARTIN          Alain         25/06/1964
...
MARTIN          Marcel        16/08/1969
...
MARTIN          Zoé           11/06/1992
 
...
 
 
ZWEIG           Alain         21/06/1896
...
ZWEIG           Marcel        11/04/1963
...
ZWEIG           Zoé           05/08/1974
ZWEIG           Zoé           02/01/1989

On observe que le tri de ces 3 colonnes fait que le prénom est trié relativement au nom, c’est à dire qu’il est possible de trouver toute la plage de tous les prénoms de A à Z pour un même nom comme MARTIN. De même pour la date de naissance qui est triée relativement au tri des colonnes précédente.
On comprend bien que dans un tel ordre relatif l’efficacité de la recherche sera différente en fonction des cas pratique. Voici un tableau résumant l’efficacité des recherches au regard de la combinaisons de tous les cas de recherches directes :


Recherche                          Efficacité
---------------------------------- ------------------
NOM + PRENOM + DATE_NAISSANCE      Maximale
NOM + PRENOM                       Très importante
NOM seul                           Importante
NOM + DATE_NAISSANCE               Bonne
PRENOM + DATE_NAISSANCE            Médiocre
PRENOM seul                        Très médiocre
DATE_NAISSANCE seule               Très médiocre

On peut s’étonner de voir que l’index peut être utilisé même lorsque l’on recherche des informations « interne » au vecteur comme le prénom ou la date de naissance. Mais il est souvent moins couteux de chercher dans un index, même séquentiellement, plutôt que globalement dans la table, car la table possède souvent plus de colonnes. Donc, dans la plupart des cas, on lirait des données inutiles qui induisent un traitement plus long. Certes la différence n’est pas très importante, mais dans un SGBDR, chaque milliseconde gagnée peut se transformer en minute ou en heure en fonction du nombre d’utilisateurs et donc du nombre de fois ou une requête similaire est envoyée au serveur !

=> 1.5 – limitation des index

Plus les données d’un, index sont petites, plus l’index est efficace. Plus ces mêmes données sont longues ou composées d’un grand nombre de colonnes et moins l’index est efficace. C’est pourquoi tous les SGBDR limitent la composition des index.

Voici un tableau résumant les limites de l’indexation


                           | Oracle  | SQL Server | PostGreSQL | MySQL (INNOdb) |
---------------------------|---------|----------- |------------|----------------|
Nombre maximal de          | 30 à 32 | 16         | 32         | inconnue       |
colonnes dans un index     | (1)     |            |            |                |              
---------------------------|---------|----------- |------------|----------------|
Longueur maximal de        | (2)     | 900        | (3)        | 767            |
la clef d'index (octets)   |         |            |            |                |
---------------------------|---------|----------- |------------|----------------|
Nombre maximal d'index     | infini  | 1000       | infini     | 16             |
par table                  |         |            |            |                |

(1) suivant le type de structure de l’index.
(2) 75% de la taille de la page moins quelques octets techniques
(3) 33% de la taille de la page moins quelques octets techniques
NOTA : les données des tables et index sont stockées dans des pages de longueur fixe pour une même base et dont la longueur peut être spécifiée à la création de la base.

Attention : pour les données littérales, les règles de calcul de longueur sont généralement les suivantes :


Type          Longueur
------------ -------------------------------------
CHAR(n)     : n
VARCHAR(n)  : de 2 (données vides) à n + 3 octets
NCHAR(n)    : 2 x n
NVARCHAR(n) : de 2 (données vides) à 2 x n + 3

De plus, certains encodage peu intéressant pour les bases de données, expandent encore la taille en octets des littéraux stockées. Par exemple l’utilisation d’UF8 dans MySQL nécessite 3 octets par caractères ce qui fait que l’on ne peut pas indexer des données de plus de 256 caractères UTF8.

Les données de types Large Objet Binaire (LOB) comme les CLOB (texte ASCII), NCLOB (texte UNICODE) ou les BLOB (Binary) ne sont généralement pas indexable, sauf à travers des services particuliers, comme la recherche plain texte pour les LOB contenant des phrases composées de mots…

=> 1.6 – types de données indexées

En principe les données purement relationnelles (donc atomique) sont toutes indexables dans les limites ci avant évoquées. Cependant certains SGBDR proposent d’indexer aussi des données non atomique pour des objets structurés dont la structure est connue du serveur, voire, pour les SGBD relationnel objet, lorsque l’objet a été spécialement conçu pour être indexé.
Pour la recherche textuelle il s’agit de créer un index particulier sur des colonnes atomiques littérale ou CLOB/NCLOB.

Voici un tableau résumant l’indexation des principaux objets non atomiques pour les 4 SGBDR les plus courants :


            Oracle        SQL Server       PostGreSQL        MySQL (InnoDB)
FULLTEXT    OUI           OUI              OUI (1)           NON
XML         OUI           OUI              NON               NON
GEOMETRY    OUI           OUI              OUI               NON
GEOGRAPHY   NON (2)       OUI              OUI               NON

(1) mais ne fonctionne pas suivant la norme SQL
(2) mais le type GEOMETRY d’Oracle permet de stocker un SRID, ce qui revient à utiliser un GEOGRAPHY !

=> 1.7 – création d’un index

Pour créer un index sur une table, la plupart des éditeurs proposent un pseudo ordre SQL (pseudo car il n’existe pas dans le langage SQL…) CREATE INDEX dont la syntaxe générale est :

CREATE INDEX <nom_index>
ON <nom_table> ( <liste_colonne> )

Suivi d’une éventuelle liste d’option spécifique à chaque éditeur.


<liste_colonne> ::
     <colonne1> [ { ASC | DESC } ]  
  [, <colonne2> [ { ASC | DESC } ]  
  [, <colonneN> [ { ASC | DESC } ]  
  ... ] ]

Cette liste spécifie les colonnes et le sens du tri qui a défaut est ASC pour ascendant. Il y a peu d’intérêt d’utiliser le sens DESC (descendant) sauf dans le cas d’un index composé de plusieurs colonnes, et ce pour une colonne vis à vis des autres. C’est souvent le cas des colonnes temporelles, car on est fréquemment intéressé de retrouver l’élément le plus récent plutôt que l’élément le plus ancien en règle général (les clients dont la date de naissance remonte à 1889 étant souvent peu en état de continuer à acheter !).

En sus de cette syntaxes primaire, il existe des options relationnelles sur l’indexation, que nous allons maintenant détailler…

–> 1.7.1 – Indexer une colonne calculée ou une expression

Certains SGBDR permettent d’indexer des colonnes calculées ou des expressions dérivées des colonnes de la table. Ceci est extrêmement intéressant dans certains cas pour des requêtes particulières.
Soit, par exemple, une table de contact avec des numéros de téléphone. Nous savons tous que la partie significative d’un numéro de téléphone n’est pas son début, mais sa fin. En effet, le début peut être exprimé de différentes manière, comme ceci 06 21 12 52 47 ou encore 00 33 6 21 12 52 47… Alors comment faire dans une telle table pour retrouver un numéro de téléphone particulier ? Il faut faire une requête avec un LIKE comme ceci :
WHERE TEL_NUMERO LIKE '%6 21 12 52 47'
Compte tenu du sens du tri dans un index, une telle requête ne pourra jamais utiliser de manière efficace l’index, sauf si nous inversons la chaine de caractères composant le numéro et que nous recherchons « à l’envers »…. C’est tout l’intérêt des index sur colonnes calculées ou sur expression.

Exemple de création d’un index sur expression dans Oracle :
CREATE INDEX X_PERSONNE_NOM ON T_PERSONNE (UPPER(PRS_NOM));

–> 1.7.2 – Index filtrés (ou index partiels)

Un index peut être volumineux, et certaines données d’un groupe particulier peu requêtées. C’est souvent le cas des données anciennes. Par exemple il est courant de manipuler les factures, commandes, bon de livraisons datant de moins d’un mois, un peu moins pour ceux datant de un à trois moins, encore moins pour ceux datant de quatre à douze mois, quand çà ceux de plus d’un ans, c’est exceptionnel ! Dans un tel cas on aura donc tout intérêt à limiter l’indexation à 3 mois voir plus. C’est la notion d’index filtré qui accueille une clause WHERE.

Exemple de création d’un index filtré avec MS SQL Server :
CREATE INDEX X_CLIENT ON T_CLIENT (CLI_NOM, CLI_PRENOM) WHERE (CLI_DATE_NAISSANCE > '1900-01-01');

–> 1.7.3 – Index couvrants

Nous avons dit qu’un index était une copie partielle des informations de la table. Pour certaines requête, la seule lecture de l’index suffit à répondre à la requête. Dans ce cas on parle d’index couvrant, car il couvre la totalité des besoins de l’information de la requête par sa simple lecture. Point n’est besoin d’aller rechercher des informations complémentaires dans la table pour répondre à la requête. Lorsque l’index n’est pas couvrant, cela oblige à un double parcours : parcourir l’index pour trouver la valeur recherché, puis une fois les lignes trouvées dans l’index, revenir sur la table afin de compléter les informations pour les colonnes qui ne sont pas présentes dans l’index…

Voici une même requête, partant de la même table, une première fois exécutée avec un index traditionnel et la seconde fois avec un index couvrant, et les différences qu’il en résulte :

La table en question, qui contient 300 000 lignes :


CREATE TABLE T_PERSONNE_PRS
(PRS_ID           INT NOT NULL PRIMARY KEY,
 PRS_NOM          CHAR(32) NOT NULL,
 PRS_PRENOM       VARCHAR(25),
 PRS_PROFESSION   VARCHAR(32));

La requête en question :


SELECT PRS_NOM, PRS_PRENOM
FROM   T_PERSONNE_PRS
WHERE  PRS_PROFESSION = 'Informaticien';

L’index non couvrant :
CREATE INDEX X ON T_PERSONNE_PRS (PRS_PROFESSION);

Le plan de requête généré :

Plan index non couvrant

et son coût : Table ‘T_PERSONNE_PRS’. Nombre d’analyses 1, lectures logiques 7

Et maintenant la version avec l’index couvrant :
CREATE INDEX X ON T_PERSONNE_PRS (PRS_PROFESSION) INCLUDE (PRS_NOM, PRS_PRENOM);
Le plan de requête généré :

Plan requête index couvrant

Et son coût : Table ‘T_PERSONNE_PRS’. Nombre d’analyses 1, lectures logiques 4

Bref, on a encore gagné près de 50%…

NOTA : cet exemple est donné pour MS SQL Server.

C’est la clause INCLUDE, qui permet de rajouter des colonnes non indexées, mais redondante dont les données seront reprises afin de couvrir la totalité de la requête et éviter ainis une double lecture.

Quand on sait la propension non négligeable d’informaticiens adorant faire des tables avec un nombre délirant de colonnes (plutôt que de gérer un vrai modèle relationnel), ce genre de technique permet de se sauver d’un mauvais modèle à bon compte !

–> 1.7.4 – Index de vues

En principe une vue ne contient pas de données. Mais le but d’une vue indexée (ou matérialisée, terme employé sous Oracle) est de stocker les résultats de la vue dans un index. Cela est particulièrement intéressant dans le cas ou l’on désire requêter sur des données très distantes (traversant un grand nombre de tables par des jointures) ou bien encore plus, pour des données agrégées (SUM, COUNT en particulier).
L’idée est de stocker dans un index les résultats de la requête qui construit la vue. J’ai donné dans cet exemple la puissance gigantesque qui peut se dégager d’un tel outil : on fait passer d’un coût de 30 000 à 2 une requête calculant un COUNT !

=> Tableau résumant les techniques relationnelles d’indexation


                    | Oracle      | SQL Server   | PostGreSQL | MySQL
--------------------|-------------|--------------|------------|--------------
index calculé       | OUI         | OUI colonne  | NON        | NON
ou sur expression   | expression  | calculée     |            |
--------------------|-------------|--------------|------------|--------------
index filtre        | OUI         | OUI          | OUI        | NON
(clause WHERE)      |             |              |            |
--------------------|-------------|--------------|------------|--------------
index couvrant      | NON         | OUI          | NON        | NON
(clause INCLUDE)    |             |              |            |
--------------------|-------------|--------------|------------|--------------
index de vue        | Asynchrone  | Synchrone    | NON        | NON

–> 1.7.5 – Index sur LOB

Il existe trois sortes d’index sur LOB classiquement implémentés dans les SGBD relationnels objet. Les index textuels prévus par la norme SQL dans son option FULL TEXT, les index XML et les index sur les données géométriques ou géographiques (SIG).

Les index textuels permettent des recherches textuelles avec différentes combinaisons dont des recherches par forme fléchies, proximités, synonymes… À lire : http://blog.developpez.com/sqlpro/p9344/langage-sql-norme/indexation-textuelle-full-text-search-no/
Les index sur XML permettent d’accélérer certains traitements (recherche de nœuds, de valeurs, de chemin…). À lire (exemple d’implémentation d’index XML dans SQL Server) : http://rdonfack.developpez.com/tutoriels/sqlserver/prise-charge-xml-dans-sql-server/
Les index sur objets géométriques ou géographique permettent d’accélérer les traitements des requêtes géomatiques. À lire : http://blog.developpez.com/sqlpro/p9414/langage-sql-norme/sql-et-systeme-d-information-geographiqu/

Tous ces index possèdent des structures particulières, plus ou moins complexes, mais le principe est le même : organiser l’information pour la rendre plus rapidement accessible.

=> Tableau résumant les techniques relationnelles des index sur LOBs


                    | Oracle      | SQL Server   | PostGreSQL  | MySQL
--------------------|-------------|--------------|-------------|--------------
indexation          | spécifique  | norme +      | spécifique  | spécifique
textuelle           |             | spécifique   | (ts_vector) | et ISAM (1)
--------------------|-------------|--------------|-------------|--------------
XML                 | OUI         | OUI          | NON         | NON
(clause WHERE)      |             |              |             |
--------------------|-------------|--------------|-------------|--------------
SIG                 | OUI         | OUI          | OUI         | ISAM seulement
(clause INCLUDE)    |             |              |             | limitée (2)
--------------------|-------------|--------------|-------------|--------------

(1) L’indexation textuelle version MySQL possède très peu de fonctionnalité. Lire : http://blog.developpez.com/sqlpro/p9344/langage-sql-norme/indexation-textuelle-full-text-search-no/
(2) Les index spatiaux MySQL sont assez « rustiques » (pas de bounding box ni de niveaux de tesselation) et par conséquent peuvent s’avérer peu performant

–> 1.7.6 – Options physiques d’indexation

En sus des options relationnelles, il existe des options physiques de création des index qui sont utiles soit pour l’optimisation de l’index lui même, soit pour la maintenance des index. Nous en parlerons au chapitre suivant !

*   *   *

Dans la suite (à paraître) de cet article, nous aborderons les sujets suivants :
2 – type de structure d’index
3 – fragmentation et maintenance des index
4 – gain réel obtenu par un index en fonction des types de requêtes


--------
Frédéric Brouard, SQLpro - ARCHITECTE DE DONNÉES, http://sqlpro.developpez.com/
Expert bases de données relationnelles et langage SQL. MVP Microsoft SQL Server
www.sqlspot.com : modélisation, conseil, audit, optimisation, tuning, formation
* * * * *  Enseignant CNAM PACA - ISEN Toulon - CESI Aix en Provence  * * * * *

MVP Microsoft SQL Server

4 réflexions au sujet de « Tout sur l’index ! (partie 1/2) »

  1. Avatar de sqlprosqlpro Auteur de l’article

    En terme de volumétrie le gain est peu important entre l’index complet (PRS_PROFESSION, PRS_NOM, PRS_PRENOM) et l’index couvrant (PRS_PROFESSION) INCLUDE (PRS_NOM, PRS_PRENOM). En revanche en terme d’utilisation c’est beaucoup plus intéressant, car on ne stocke pas les données incluses au niveau des pages intermédiaire ce qui simplifie l’aiguillage sur les pages de navigation.

  2. Avatar de zinzinetizinzineti

    Encore un excellent article qui lève le voile sur les index. J’apprécie particulièrement la mise en perspective qui est faite avec les principaux SGBDR du marché : ORACLE, SQL SERVER, PostGreSQL,…

    J’aurais bien souhaité voir le plan de requête et le coût d’un index qui n’utilise pas la clause INCLUDE. c’est à dire un index du genre
    CREATE INDEX X ON T_PERSONNE_PRS (PRS_PROFESSION,PRS_NOM,PRS_PRENOM);
    afin de déduire l’effet de la clause INCLUDE

Laisser un commentaire