Le site des utilisateurs francophones de FluxBB.
Les index sont un sujet vraiment paradoxal. Ils sont absents de la théorie relationnelle et de la norme SQL. Invisibles à l'utilisateur, ils sont pourtant omniprésents dans toute base de donnée relationnelle.
Nota, j'ai pris des exemples à partir mes propres bases de données et tables :
Tests et valeurs obtenues sous Windows Xp Home SP3 - Apache 2.2.16 - MySQL 5.1.49 - PHP 5.3.3
Les chiffres obtenus peuvent être très différents en fonction du processeur, de la quantité mémoire et de la vitesse de transfert des disques durs.
Les lignes d'une table sont stockées sans aucun ordre logique ; si l'on demande ainsi à MySQL de rechercher le ou les livres titrés « L'Illustration », il doit parcourir toutes les lignes de la table et tester chaque titre. Si les livres sont triés par ordre alphabétique de titre, MySQL peut sauter directement à la lettre L et s'arrêter de chercher quand il a atteint la lettre M.
Les index sont des sortes de répertoires qui permettent cette accélération de la recherche. Supposez par exemple que l'on pose trois index sur la table Livres, sur les colonnes Titre, Compendium et IDlivre. La table n'est pas ordonnée, mais chacun des index l'est, selon son ordre propre. À chaque fois qu'on ajoute ou qu'on supprime un livre, ou bien que l'on modifie son titre ou son Compendium, les index sont mis à jour. La création d'un index a donc pour effet d'augmenter la taille de la base de données, de ralentir légèrement toutes les modifications de données, mais d'accélérer énormément les recherches sur la colonne indexée. Il est donc recommandé de poser des index sur les colonnes fréquemment utilisées en recherche, et seulement sur celles-ci.
Les colonnes les plus utiles à indexer sont évidemment les clés ; MySQL tend d'ailleurs à confondre les deux notions d'index et de clé. On peut le voir à travers les types d'index proposés par MySQL :
On sait comment définir, à la création de la table, une colonne comme clé primaire (PRIMARY KEY). Voici comment on peut ajouter les deux index manquants, par exemple à la table Livres :
ALTER TABLE Livres ADD INDEX (Titre), ADD INDEX (Compendium) ;
Avec de petites tables, il n'y a guère de problème de vitesse et de taux d'occupation du serveur MySQL. Donc, pour étudier les questions de performance, j'ai créé une table de test comprenant plus de sept millions de lignes à partir d'une copie de 202 lignes d'une de mes tables, de mes tables d'essais Octet (255) et Chiffres (10)
CREATE TABLE Test_Perf SELECT A.a_nom, A.a_prenom FROM avia_vilg_apprentis AS A CROSS JOIN test_octet AS O CROSS JOIN test_chiffres AS C ORDER BY RAND(); -- Tri aléatoire Query OK, 7439360 rows affected (53.03 sec)
Cherchons maintenant combien il y a d'apprentis prénommés Michel :
SELECT COUNT(*) FROM Test_Perf WHERE a_prenom = 'Michel' ; Réponse de MySQL +----------+ | COUNT(*) | +----------+ | 317440 | +----------+ 1 row IN SET (3.36 sec)
Si on relance la même requête, on constate que nous obtenons cette fois-ci une réponse quasi immédiate (0,01 ou même 0,00 seconde). MySQL utilise en effet un cache de requêtes (query cache). Si une requête est relancée à l'identique (au caractère près) et si la table source n'a pas été modifiée depuis, il se souvient du résultat. Afin d'éliminer cet artefact, nous utiliserons à l'avenir le mot-clé Sql_No_Cache pour demander à MySQL de ne pas utiliser le cache de requêtes.
Dans quelle mesure un index peut-il accélérer cette recherche ? Pour pouvoir comparer, nous allons dupliquer la colonne Prenom, et poser un index sur le duplicata :
ALTER TABLE Test_Perf ADD COLUMN PrenomIndexe VARCHAR(45) ; Query OK, 7439360 rows affected (4.80 sec) UPDATE Test_Perf SET PrenomIndexe = a_prenom ; Query OK, 7439360 rows affected (1 min 42.55 sec) mysql> CREATE INDEX i ON Test_Perf(PrenomIndexe) ; Query OK, 7439360 rows affected (10 min 51.39 sec)
On peut déjà voir que la création de l'index prend plus de 10 min ; il faut quand-même voir qu'il y a plus de 7 millions de lignes.
Combien de temps prend la recherche des Michel dans la colonne indexée ?
SELECT SQL_NO_CACHE COUNT(*) FROM Test_Perf WHERE PrenomIndexe = 'Michel' ; +----------+ | COUNT(*) | +----------+ | 317440 | +----------+ 1 row IN SET (0.24 sec)
L'effet de l'index est spectaculaire ! Afin d'aller plus loin dans sa mesure, voici les résultats d'une série de tests (que vous êtes invité à reproduire).
Toutes les requêtes commencent par : Select Sql_No_Cache Count(*) From Test_Perf Where. La colonne indexée est spectaculairement plus rapide, sauf dans un cas
Condition | Avec a_prenom | Avec PrenonIndexe |
---|---|---|
= 'Michel' | 2,36 | 0,24 |
LIKE 'Michel%' | 2,66 | 0,22 |
LIKE '%Michel%' | 5,22 | 5,39 |
IS NULL | 0,00 | 0,00 |
IS NOT NULL | 2.56 | 0.58 |
IN ('Michel','Jean') | 2,83 | 0,48 |
Avec la colonne sans index, la durée de la requête est toujours à peu près la même : c'est le temps nécessaire à MySQL pour effectuer un balayage complet de la table (table scan).
Avec l'index, le temps est beaucoup plus court, sauf pour le test “contient (LIKE)”. En effet, l'index se présente comme un répertoire des prénoms par ordre alphabétique, avec l'adresse des lignes correspondantes. Sur un tel répertoire, il est facile de trouver Michel, et tout aussi facile de trouver Jean. Par contre, si vous souhaitez trouver Jean-Michel, Jean-Marie, et tous les autres composés, vous êtes obligé de parcourir tout le répertoire. L'index trié ne vous apporte donc aucun avantage par rapport à la table, où les lignes sont en vrac.
Que donne l'index avec les opérateurs < et > ?
Condition | Avec a_prenom | Avec PrenomIndexe |
---|---|---|
< 'Alex' | 7,89 | 0,38 |
< 'Jean' | 7,64 | 4,00 |
< 'Yves' | 7,52 | 8,39 |
> 'Alex' | 7,56 | 7,98 |
> 'Jean' | 7,53 | 4,20 |
> 'Yves' | 7,66 | 0,16 |
Avec la condition inférieur, l'index est très efficace en début d'ordre alphabétique, et perd de son efficacité au fur et à mesure qu'on avance vers la fin. Avec supérieur, c'est le contraire. L'efficacité d'un index dépend de sa spécificité. En effet, peu de prénoms se trouvent avant Alex. L'index permet donc d'économiser l'essentiel du nombre de lignes. À l'inverse, presque tous les prénoms sont avant Yves. MySQL doit donc parcourir soit la table en entier, soit l'index dans sa quasi-intégralité. Comme celui-ci est destiné à une recherche précise et non à une recherche intégrale, il est alors moins efficace que la table.
À chaque requête, l'optimiseur de MySQL choisit ou non d'utiliser l'index. L'essentiel du travail d'optimisation consiste à s'assurer qu'il fait les bons choix. Les chiffres présentés ici (et qu'on retrouve plus ou moins en répétant plusieurs fois les tests) montrent que la contribution globale de l'index est très positive, même si elle peut être légèrement pénalisante dans les cas marginaux. Pour connaître la décision de l'optimiseur, mettons la commande EXPLAIN en tête de requête. Elle révèlera le plan d'exécution de la requête :
Affichage du plan d'exécution de deux requêtes
EXPLAIN SELECT COUNT(*) FROM Test_Perf WHERE a_prenom > 'Yves'; EXPLAIN SELECT COUNT(*) FROM Test_Perf WHERE Prenomlndexe > 'Yves';
Quelques colonnes de l'Explain des deux requêtes
Table | Type | Possible_key | Key | Key_len | Rows | Extra |
---|---|---|---|---|---|---|
Test_Perf | ALL | NULL | NULL | NULL | 7469360 | Using where |
Test_Perf | range | i | i | 138 | 10109 | Using where |
Using index |
Lire un plan d'exécution ne s'apprend pas en quelques lignes. Soulignons juste trois points :
Sources : Documentation MySQL - Livre MySQL5 Le guide complet, Antoine Dinimant