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 | 32 | 32 | inconnue |
colonnes dans un index | (1) | | | |
---------------------------|---------|----------- |------------|----------------|
Longueur maximal de | (2) | 1600 | (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 :
ON ( )
Suivi d’une éventuelle liste d’option spécifique à chaque éditeur.
::
[ { ASC | DESC } ]
[, [ { ASC | DESC } ]
[, [ { 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é :
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é :
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 * * * * *
Bonjour,
Excellent article.
Par ailleurs, ma question est de savoir quelle serait la conséquence de l’indexation de plusieurs champs sur une table donnée ?
Merci d’avance.
Salut sqlpro
A quand la suite (2/2)? si ce n’est pas trop vous exiger.
PS: puis-je dire Frédéric à la place de sqlpro?
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.
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