Déjà trois semaines d’écoulées depuis que certains d’entre vous, les “héros”, ont posé leurs questions (oui il est possible de devenir un héros rien qu’en lisant dbnewz ! Les véritables héros sont d’ailleurs abonnés au tout nouveau flux feedburner )
Trois semaines d’attente, cela mérite un billet digne de ce nom, c’est parti.
Indexer, pourquoi ?
L’indexation peut avoir plusieurs buts :
- Accéder à ses données plus rapidement, les index sont en effet
l’outil le plus puissant pour accélérer les temps
d’exécution de vos requêtes jusqu’à parfois plusieurs
centaines de % !
- Définir le degré d’unicité d’une colonne donnée : chaque champ
doit-il être unique ? les doublons sont-ils autorisés ?
Principe de fonctionnement
Lorsque vous envoyez une requête à votre serveur MySQL, celle-ci
est d’abord confiée au “parseur” SQL qui a pour but de vérifier
si la syntaxe de votre demande est correcte. Cette étape
franchie, la requête passe par “l’optimiseur”. Il s’agit ici de
déterminer le plan d’exécution de la requête
afin que celle-ci s’exécute le plus rapidement possible.
L’optimiseur détecte si d’éventuels index sont disponibles, si c’est le cas il décidera de s’en servir… ou pas : il est parfois plus rapide de ne pas se servir d’un index ! Nous verrons pourquoi au cours de cette série d’articles.
Une fois le plan d’exécution achevé, c’est le moteur de stockage qui prend le relais, celui-ci peut être vu comme un “module” de MySQL :
Pour schématiser, et dans un monde idéal, lorsqu’un index est disponible et “compatible” avec votre requête, l’optimiseur MySQL peut décider de l’utiliser afin d’éviter de parcourir l’ensemble des données des tables concernées.
Un exemple couramment employé pour illustrer ce propos consiste à
imaginer la difficultée que nous aurions à retrouver quelqu’un
dans l’annuaire si nous connaissions son nom mais pas l’alphabet
(qui est notre index)… Transposé au monde informatique cela donne
un serveur MySQL qui compare une à une les entrées du botin pour
trouver toutes celles qui correspondent au nom recherché. Si au
contraire ce nom est indexé, et si celui-ci commence par exemple
par ‘T’, le serveur sait directement qu’il doit démarrer sa
recherche à partir du ‘T’. Imaginez l’impact en terme de gain de
temps lorsque plusieurs jointures sont concernées : deux tables
de 10 000 lignes chacune forment un produit cartésien de 100 000
lignes environ à étudier…
Les index n’ont hélas pas que des avantages :
- Les opérations de mises à jour (INSERT, UPDATE, DELETE) sont en
effet ralenties puisqu’en plus des données, les index doivent eux
aussi être mis à jour lors de ces opérations, c’est le prix à
payer… Ce prix peut néamoins se “négocier”, nous verrons cela
plus tard.
Notre terrain de jeu, la base “world”
MySQL propose au téléchargement plusieurs bases d’exemple dont “world” et “sakila”. Elles épargnent le soin aux utilisateurs de MySQL souhaitant tester quelques requêtes de se constituer eux-mêmes une base de test, celles-ci sont prêtes à l’emploi.
Nous utiliserons pour nos tests la base “world”. Très simple
puisque constituée uniquement de trois petites tables MyISAM
(Country, CountryLanguage et City), elle permet de se concentrer
uniquement sur les index sans perdre de temps à assimiler un
schéma plus complexe.
Si vous souhaitez transformer le script de création SQL de la
base “world” en une version graphique “presque” MCD (les
relations entre les tables ne sont pas générées automatiquement
pour cette base), le billet précédent est fait pour vous,
les étapes d’installation et de génération du MCD
par “reverse engineering” avec DBDesigner 4 y sont
décrites.
Voici ce qu’on peut obtenir pour cette base à partir de
DBDesigner :
Quel type d’index choisir : PRIMARY KEY, UNIQUE, ou INDEX
?
Choisissez le type de vos index avec soin :
- Une clé primaire (PRIMARY KEY) est strictement
unique, les NULL ne sont pas autorisés.
- Un index de type UNIQUE est comparable à une
clé primaire, mis à part pour les valeurs NULL puisque celles-ci
sont autorisées (et potentiellement en plusieurs
occurences).
- Un index de type INDEX ou KEY
(c’est un alias) signifie simplement que l’on souhaite indexer
une colonne susceptible de contenir des doublons.
Les index de type FULLTEXT et
SPATIAL sont particuliers et méritent un épisode
à eux seuls, ils seront donc évoqués ultérieurement.
Passons rapidement sur l’étape de déclaration d’un index, celle-ci s’effectue soit
au moment de la création de la table, soit plus tard comme ici
:
mysql> CREATE INDEX idx_district ON City
(District);
Query OK, 4079 rows affected (0.04 sec)
Records: 4079 Duplicates: 0 Warnings: 0
Nous venons de créer un index de type INDEX (autorise les
doublons) sur la colonne District de la table City.
Attention, si nous avions tenté la même chose avec un index de
type UNIQUE…
mysql> CREATE UNIQUE INDEX idx_district ON City
(District);
ERROR 1062 (23000): Duplicate entry ‘Zuid-Holland’ for key
2
… MySQL nous signale qu’il y’a déjà des doublons dans la colonne
District, impossible donc de créer un index de type UNIQUE sur
celle-ci.
Pour supprimer cet index :
mysql> DROP INDEX idx_district ON City;
Ou :
mysql> ALTER TABLE City DROP INDEX
idx_district;
Pour visualiser les index d’une table :
mysql> SHOW INDEX FROM Country;
Attention aux doublons !
Inutile de rajouter un index de type “INDEX” ou encore “UNIQUE”
sur un champ qui est déjà clé primaire par exemple… Vous
dupliqueriez inutilement les index avec à la clé un gaspillage
d’espace disque/mémoire, des ralentissements inutiles lors des
mises à jour, davantage de travail pour l’optimiseur…
Quels types de champ indexer ?
INT, VARCHAR, BLOB… ? Quels sont les meilleurs candidats à
l’indexation ?
Plus l’index est court, mieux c’est : un index
est en permanence comparé à d’autres valeurs (celles
recherchées), ces comparaisons sont plus rapides si la zone à
comparer est plus courte. Des index concis occupent également
moins de place sur disque, génèrent moins d’I/O (activité disque
s’ils ne sont pas en mémoire) et peuvent ainsi être stockés en
plus grand nombre dans une même quantité de RAM (pensez au
key_buffer_size de MyISAM par exemple).
Bref, si vous désirez stocker une liste de noms de villes sous
forme de chaînes de caractères, sachez qu’il est inutile de
réserver un champ de type CHAR(255) : rares sont celles qui
atteindront cette longueur, pensez plutôt au VARCHAR qui
s’adaptera à la longueur de vos valeurs.
Plus malin encore, lors de la conception de votre base de
données, intéressez-vous aux différentes formes de normalisation
: 1NF, 2NF, 3NF, ces méthodes permettent d’obtenir un schéma qui
permet de partir sur de bonnes bases.
En gardant cet exemple des villes, si vous stockez dans une table
“inscrits” toutes les infos contextuelles à un utilisateur, dont
sa ville, envisagez de stocker dans une table “ville”, toutes les
infos qui s’y rapportent : nom, population, etc. Reliez ensuite
votre table “inscrits” à la table “ville” par la valeur de la clé
primaire de ville et vous supprimerez ainsi tous ces libellés de
villes identiques au profit d’un ID bien plus rapide et
économique.
Soyez radins !
Vos index seront d’autant plus efficaces s’ils sont apposés sur
des champs bien adaptés à vos données. Ne gaspillez pas
le capital “performance” de vos index en utilisant un
INT pour stocker par exemple la vitesse légale sur autoroute en
France (par temps sec) : 130 km/h… Un TINY INT UNSIGNED
suffira (permet de stocker les valeurs de 0 à 255). Un INT permet
lui de stocker des valeurs comprises entre
-2.147.483.648 2.147.483.647, et en rajoutant
l'attribut UNSIGNED, on obtient un rayon d’action de 0 à
plus de 4 milliards ! A quoi bon utiliser un INT dans cet exemple
? Quand on sait de plus qu’un INT occupe quatre fois plus de
place qu’un TINY INT, l’impact sur les performances et la perte
d’espace avec une table de plusieurs millions d’enregistrements
est évident…
Prenez connaissance des caractéristiques des types de données que vous
utilisez. Visualisez également la taille requise, c’est un élement qui peut
s’avérer dissuasif.
Pour résumer, n’indexez pas une colonne en fonction de son type,
mais prenez soin dans un premier temps de définir celles-ci avec
le type de données qui leur convient le mieux, le plus
économique. Prévoyez une marge néanmoins : n’utilisez pas un TINY
INT même UNSIGNED pour un identifiant de clé primaire
AUTO_INCREMENT concernant une newsletter d’un grand service
commercial : si tout se passe bien vous devriez rapidement
dépasser le seuil des 255 inscrits… Le type de données juste
“au-dessus”, SMALLINT UNSIGNED, qui permet d’aller jusqu’à 65535,
est sans doute plus confortable.
Le tips dbnewz : utilisez la commande
PROCEDURE ANALYSE()
Cette commande analyse pour vous vos tables et vous propose le
type idéal pour vos données… si vous en avez bien sûr, ça ne peut
pas vous aider lors d’une création de table. En revanche, elle
permet “d’auditer” vos enregistrements actuels, d’en tirer
quelques statistiques et propose le type le plus adapté :
mysql> SELECT Name FROM Country PROCEDURE
ANALYSE(10,256)\G
Field_name: world.Country.Name
Min_value: Afghanistan
Max_value: Zimbabwe
Min_length: 4
Max_length: 44
Empties_or_zeros: 0
Nulls: 0
Avg_value_or_avg_length: 10.0962
Std: NULL
Optimal_fieldtype: VARCHAR(44) NOT NULL
1 row in set (0.00 sec)
Vous pouvez bien sûr effectuer cette requête sur l’intégralité
des champs de l’une de vos tables (SELECT *…)
Les paramètres fournis à PROCEDURE ANALYSE () sont à modifier en
fonction de vos souhaits. Par défaut cette fonction a tendance à
vouloir transformer toutes vos chaînes de caractères en champs
ENUM (stockés sous forme numérique en interne), à
vous de définir combien de champs ENUM vous êtes prêts à
utiliser. Réservez-les pour les cas où le champ représente une
courte liste “fermée”, ex “M” ou “F”, les jours de la semaine par
exemple, etc.
Où placer ses index : quels sont les champs à indexer
?
Les champs concernés par une clause WHERE, ORDER BY,
GROUP BY, MIN(), MAX(), ainsi que les champs qui
permettent de relier des tables entre elles,
sont de bons candidats à l’indexation, exemple :
SELECT ci.Name, ci.Population
FROM City ci INNER JOIN Country co ON ci.CountryCode =
co.Code
WHERE ci.Population > 5000000
ORDER BY ci.District ASC LIMIT 3
- Le champ CountryCode de la table City ainsi que le champ Code
de la table Country sont tous les deux à indexer. C’est
d’ailleurs le cas ici puisque ces deux champs sont respectivement
clés primaires de la table City et Country.
- Le champ Population est intéressant à indexer, il permet à
MySQL de parcourir très rapidement les villes par leur population
triée et évite de comparer l’intégralité des populations de
chaque ville, une à une.
- Le champ District est également un candidat à l’indexation, il
peut aider MySQL à trier les données plus rapidement.
A retenir : on indexe en priorité les champs impliqués dans les
clauses évoqués ci-dessus (en gras), pas forcément ceux présents
dans le SELECT.
Les index composés (ou multiples) et la règle du leftmost
prefixing
“Faut-il préférer un index unique ou composé” était l’une des questions posées par l’un d’entre
vous il y’a quelques semaines…
Un index composé doit se construire en fonction des requêtes que
vous effectuez sur la table concernée.
Prenons pour exemple la table City et ses cinq champs (ID, Name,
CountryCode, District, Population).
Si les seules requêtes que vous avez sur City sont du type :
SELECT ... FROM City WHERE Name = "..."
… Indexez Name et tout ira bien.
Si en revanche il vous arrive de trier non seulement sur “Name” mais également sur le code du pays :
SELECT ... FROM City WHERE Name = "..." AND CountryCode =
"..."
Dans ce cas, plutôt que de laisser MySQL comparer tous les
CountryCode de la table avec votre recherche (ex : “FRA”),
indexez la colonne CountryCode… Oui mais pas toute seule !
Considérez en effet pour l’instant que MySQL n’utilise qu’un
index par table, l’optimiseur MySQL choisit donc le plus
restrictif afin que votre requête s’exécute le plus rapidement
possible (nous verrons plus tard les cas particuliers où MySQL
peut tirer parti de plusieurs index).
Conséquence, il vous faut trouver un index qui soit utilisable
pour vos deux critères de recherche : “Name” et “CountryCode”. La
solution : créez un index multiple sur ces deux champs.
Dès lors que vous utilisez un index multiple, la
règle du leftmost prefixing rentre en
jeu. Trop souvent méconnue, elle permet pourtant de créer ses
index de façon efficace et d’éviter les doublons.
Afin d’illustrer cette règle, ajoutons cette fois à la table City
un index multiple sur les champs Name, CountryCode, District et
Population :
mysql> CREATE INDEX name_cc_dis_pop ON City (Name,
CountryCode, District, Population);
Voici ce que l’on obtient avec le SHOW INDEX correspondant (la clé primaire existait déjà à la création de la table, ci-dessous une vue partielle des résultats réels) :
mysql> SHOW INDEX FROM City;
| Key_name | Seq_in_index
| Column_name
+——-+————+—————–+
|name_cc_dis_pop |
1 | Name
|name_cc_dis_pop
| 2 |
CountryCode
|name_cc_dis_pop
| 3 |
District
|name_cc_dis_pop |
4 | Population |
+——-+————+—————–+
On remarque par rapport au SHOW INDEX précédent que cette fois-ci nous avons la colonne “Seq_in_index” qui s’incrémente pour chaque colonne qui compose notre index multiple. La position de chaque index dans cette séquence a une importance, c’est ce que nous allons voir maintenant.
Tel quel, cet index multiple sera potentiellement utilisé pour les requêtes de ce type :
SELECT ... FROM City WHERE Name = ... AND CountryCode = ...
AND District = ... AND Population = ...
SELECT … FROM City WHERE Name = … AND CountryCode = … AND
District = …
SELECT … FROM City WHERE Name = … AND CountryCode = …
SELECT … FROM City WHERE Name = …
Une fois cette “logique” acquise, on comprend qu’il est inutile
de rajouter un index sur Name par exemple puisque cette colonne
est déjà indexée grâce à cet index multiple. Idem pour notre
exemple précédent d’index multiple concernant les champs
Name et CountryCode, là encore inutile de recréer un index sur
ces deux champs puisque ces derniers sont déjà représentés dans
notre dernier exemple.
En revanche, si l’ordre de vos champs ne respecte pas l’ordre de
séquence de votre index, comme ici :
SELECT ... FROM City WHERE Name = ... AND Population =
..
Cette requête ne bénéficiera pas complètement de l’index multiple
précedemment crée, cela dit l’optimiseur tirera sûrement parti de
cet index pour la colonne Name, mais pas pour le second critère
de recherche.
De même si votre requête est du type :
SELECT ... FROM City WHERE CountryCode = ...
SELECT … FROM City WHERE District = …
SELECT … FROM City WHERE Population = …
SELECT … FROM City WHERE CountryCode = … AND District = … AND
Population = …
… et autres variations qui ne débutent pas avec “Name” et ne
respectent pas ensuite l’ordre de séquence de l’index (Name,
CountryCode, District, et Population), l’index ne sera pas
utilisé.
En conséquence, il est donc tout à fait légitime d’indexer par
ailleurs la colonne Population seule si vous avez des requêtes du
type :
SELECT ... FROM City WHERE Population > ...
Mesurez l’efficacité des index avec
EXPLAIN
Impossible d’évoquer les index sans parler de la commande
EXPLAIN. Absolument
fondamentale, elle affiche le plan d’exécution
décidé par l’optimiseur MySQL et vous permet de mesurer si oui ou
non vos index sont réellement utilisés.
Reprenons une des premières requêtes de ce billet et
rajoutons-lui le mot clé EXPLAIN :
(on considère ici que la table City ne contient que sa clé
primaire, pas les index rajoutés précedemment)
mysql> EXPLAIN SELECT ci.Name,
ci.Population
FROM City ci INNER JOIN Country co ON ci.CountryCode =
co.Code
WHERE ci.Population > 5000000
ORDER BY ci.District ASC LIMIT 3\G
*************************** 1. row *************
id: 1
select_type: SIMPLE
table: ci
type: ALL
possible_keys: NULL
key: NULL
key_len: NULL
ref: NULL
rows: 4079
Extra: Using where; Using filesort
*************************** 2. row *************
id: 1
select_type: SIMPLE
table: co
type: eq_ref
possible_keys: PRIMARY
key: PRIMARY
key_len: 3
ref: world.ci.CountryCode
rows: 1
Extra: Using index
2 rows in set (0.00 sec)
La commande EXPLAIN sera étudiée plus précisemment dans un autre épisode, pour le moment contentons-nous de prêter attention aux champs en gras :
- Sur la première ligne le type ALL signale que MySQL doit effectuer un “full table scan” c’est à dire parcourir entièrement la table City qui compte 4079 enregistrements, ceci afin de repérer quelles sont les villes qui ont une population supérieure à 5M d’habitants. Aucun index/key n’a pu être utilisé (possible_keys : NULL) pour résoudre cette partie de la requête. La colonne “rows” indique le nombre approximatif d’enregistrements que MySQL pense devoir analyser pour mener à bien l’opération.
- La seconde ligne nous indique que cette fois MySQL a un
candidat pour l’indexation, il s’agit de la clé primaire de la
table Country, la jointure s’effectuant avec le champ
“CountryCode” de la table City, qui est également une clé
primaire. Résultat : MySQL effectue la correspondance très
rapidement (rows : 1 et extra : Using index).
Ceci répond à une des questions posées précedemment par un
lecteur : “Quand préférer le FULL TABLE SCAN à l’index ?” C’est
en fait le travail de l’optimiseur, il doit déterminer si oui ou
non un index vous fera gagner du temps. Il se peut qu’il se
trompe (rarement), nous verrons comment orienter ses choix si
besoin.
Rajoutons maintenant un index de type “INDEX” sur la colonne
Population :
mysql> CREATE INDEX idx_pop ON City
(Population);
Puis appliquons à nouveau la même commande EXPLAIN, on obtient
cette fois :
*************************** 1. row ************
id: 1
select_type: SIMPLE
table: ci
type: range
possible_keys: idx_pop
key: idx_pop
key_len: 4
ref: NULL
rows: 25
Extra: Using where; Using filesort
*************************** 2. row ************
id: 1
select_type: SIMPLE
table: co
type: eq_ref
possible_keys: PRIMARY
key: PRIMARY
key_len: 3
ref: world.ci.CountryCode
rows: 1
Extra: Using index
2 rows in set (0.02 sec)
Notre index a permis à MySQL de lire 160 fois moins de
lignes cette fois-ci par rapport à l’exemple précédent…
Seules 25 lignes de la table City sont lues désormais (au lieu
des 4079 lignes précedemment parcourues). C’est un gain très
intéressant en termes de ressources serveur ! Amateurs de
chiffres, des benchmarks sont prévus dans la suite de cette
série.
Afin de patienter jusqu’aux prochains épisodes justement, vous
pouvez commencer par appliquer les quelques conseils de ce billet
tout en relisant pourquoi pas l’article concernant l’implémentation des index (BTREE ou HASH)
selon le type de votre moteur de stockage (MyISAM, InnoDB ou
MEMORY).
Il reste certaines de vos questions en suspens, elles ne sont pas
oubliées et seront débattues ici très prochainement.
Si vous avez des questions ou des remarques concernant cette première étape, n’hésitez pas.