Les covering index, de la théorie à la pratique avec MyISAM et InnoDB

20 novembre 2008 par arnaud

Pour faire suite au dernier schéma sur les structures comparées d’un index MyISAM et InnoDB, ce billet a pour but de détailler une optimisation nommée covering index.
On appelle ainsi un index lorsqu’il « couvre » l’intégralité des données recherchées et évite ainsi un parcours des enregistrements souvent basé sur des random I/O, spécialement couteux sur disque.

A propos des random I/O, voici un court extrait d’un billet précédent sur les SSD :

Sur un disque classique un “random read” entraîne (du plus couteux au moins couteux) :
- le déplacement de la tête de lecture/écriture sur la bonne piste (”seek time”)
- une fois la tête sur la bonne piste, il faut encore repérer sur celle-ci le bloc secteur demandé (”rotational latency”)
- la lecture et la transmission de la donnée vers le système.

Les quelques chiffres suivants permettent de mesurer les conséquences du paragraphe précédent et ainsi de mieux visualiser les enjeux soulevés par les covering index.

On se base ici sur la base d’un enregistrement de 100 bytes. Notez que ces valeurs sont des ordres de grandeur :

En mémoire :
Sequential read : 5 000 000 read/s (500 Mb /s)
Random read : 250 000 read/s (25 Mb /s)

=> En mémoire, un coefficient x20 existe entre les performances en sequentiel et en lecture aléatoire.

Sur disque :
Sequential read : 500 000 r/s (50 Mb /s)
Random read : 100 r/s (10 Kb /s)

=> Sur disque, un coefficient x5000 (!) existe entre les performances en sequentiel et en lecture aléatoire.

(Source : MySQL High Performance 2nd Edition)

On note qu’entre un parcours séquentiel sur disque (full scan table) et le même parcours en mémoire, il existe un facteur 10… A comparer avec un facteur 2500 pour du random I/O entre un parcours mémoire et son homologue sur disque.
Pas de chance, c’est le parcours basé sur des random I/O qui en général permet de retrouver un enregistrement à partir d’un index (la clé primaire « clustered » d’InnoDB mise à part : raccrochez-vous au schéma pour comprendre pourquoi).

Nous avons donc tout intérêt à tenter de minimiser ce type de parcours grâce aux covering index.

Les covering index : de la théorie…

Un covering index doit rassembler deux qualités :
- Etre l’index choisi par MySQL pour résoudre votre requête
- Contenir l’intégralité des champs recherchés (ceux du SELECT)

Si vous avez sous les yeux le fameux schéma, vous voyez que dans le cas de MyISAM par exemple, il existe en effet un « saut » à effectuer entre la valeur indexée (peu importe que l’index soit primaire ou secondaire) et l’enregistrement. Dans le cas d’un covering index il n’y a plus besoin d’effectuer ce saut puisque la donnée recherchée se trouve déjà intégralement dans l’index.

Nous allons le voir maintenant, c’est au développeur affuté de rechercher ce type d’optimisations. Pour cela une bonne connaissance des caractéristiques de chaque moteur de stockage utilisé est nécessaire.

Si vous maîtrisez le principe du leftmost prefixing et si en plus vous tirez parti d’une table InnoDB à la clé primaire ajoutée derrière chaque index secondaire, voilà qui devrait vous éviter de créer des index inutiles en profitant au maximum des forces en présence !

… à la pratique

Conçu autour de la base world, voici un exemple concret des différences entre MyISAM et InnoDB dont vous devez tenir compte pour vos stratégies d’indexation.

Nous partons d’une table MyISAM qui possède deux index, sa clé primaire (ID) et un index que j’ai crée sur le « countrycode » :

mysql> SHOW INDEX FROM city\G
***** 1. row ****
Key_name: PRIMARY
Seq_in_index: 1
Column_name: ID
Cardinality: 4321
[...]
**** 2. row ****
Key_name: idx_countrycode
Seq_in_index: 1
Column_name: CountryCode
Cardinality: 720
[...]

Testons un premier EXPLAIN :

mysql> EXPLAIN SELECT countrycode, id FROM city WHERE countrycode=’fra’ ORDER BY id ASC\G
***** 1. row ****
id: 1
select_type: SIMPLE
table: city
type: ref
possible_keys: idx_countrycode
key: idx_countrycode
key_len: 3
ref: const
rows: 39
Extra: Using where; Using filesort
1 row in set (0.00 sec)

Cette table sera parcourue selon son index « idx_countrycode », cependant vu que la colonne « id » est également nécessaire pour les résultats, il y’a un saut systématique à chaque entrée de l’index vers les enregistrements correspondants (c’est le « saut » entre le fichier .MYI et le .MYD représenté sur le schéma).

A noter que nous avons ici un filesort c’est à dire un tri supplémentaire effectué par le serveur MySQL pour classer nos résultats. Certes, l’index contient des données ordonnées mais il s’agit ici des valeurs de « countrycode », pas de celles concernant la colonne « id ».

Tentons maintenant une modification du moteur de stockage de la table suivie du même EXPLAIN :

mysql> ALTER TABLE city ENGINE=InnoDB;
Query OK, 4079 rows affected (0.45 sec)
Records: 4079  Duplicates: 0  Warnings: 0

mysql> EXPLAIN SELECT countrycode, id FROM city WHERE countrycode=’fra’ ORDER BY id ASC\G
***** 1. row ****
id: 1
select_type: SIMPLE
table: city
type: ref
possible_keys: idx_countrycode
key: idx_countrycode
key_len: 3
ref: const
rows: 40
Extra: Using where; Using index
1 row in set (0.02 sec)

Explain nous gratifie d’un « USING INDEX », cela signifie que nous sommes dans le cas d’un « covering index ». Ne pas confondre en effet le libellé « index » dans la colonne « type » de EXPLAIN, qui signifie que tout l’index est parcouru, avec le « Using index » de la colonne extra qui indique un covering index.

Pour en revenir au schéma, puisque c’est le support de ce billet, nous sommes passés du côté gauche du dessin (MyISAM), au côté droit (InnoDB). Remarquez comment est formé l’index secondaire sous InnoDB… Il contient la valeur de la clé primaire, c’est une caractéristique très importante puisque c’est comme si notre index placé simplement sur « countrycode » était en fait un index composé des champs (countrycode, id).

Nous sommes donc bien dans le cas d’un covering index puisque cette fois l’intégralité des données recherchées (le countrycode et « id ») sont contenues dans l’index, aucun « saut » supplémentaire vers les enregistrements n’est nécessaire, autant de random I/O de gagnés.

Nous aurions pu obtenir la même chose avec MyISAM mais en spécifiant cette fois un index composé, pour cela on repasse le moteur de stockage en MyISAM puis on crée l’index :

mysql> ALTER TABLE city ENGINE=myisam;
Query OK, 4079 rows affected (0.23 sec)
Records: 4079  Duplicates: 0  Warnings: 0

mysql> CREATE INDEX idx_countrycode_id ON city(countrycode,id);
Query OK, 4079 rows affected (0.25 sec)
Records: 4079  Duplicates: 0  Warnings: 0

mysql> EXPLAIN SELECT id,countrycode FROM city WHERE countrycode=’fra’ ORDER BY id ASC\G
***** 1. row ****
table: city
type: ref
possible_keys: idx_countrycode,idx_countrycode_id
key: idx_countrycode_id
key_len: 3
ref: const
rows: 40
Extra: Using where; Using index
1 row in set (0.00 sec)

Inutile en revanche de créer ce même index composé sous InnoDB puisqu’il existe en fait déjà… Nous ne rajouterions dans ce cas qu’une possibilité supplémentaire à étudier inutilement pour l’optimiseur MySQL sans parler du temps de perdu à mettre à jour un index redondant.

« Combien d’index inutiles ai-je donc dans ma base à l’heure actuelle ? » est peut-être la question que vous vous posez désormais ?

Le tips dbnewz : allez jeter un oeil du côté du « maatkit« , cet ensemble de scripts perl contient justement un outil, le « mk duplicate key checker » qui a justement pour but de vous aider à détecter les doublons.

Notez que dans certains cas particuliers, un index peut volontairement avoir été crée bien que redondant avec un autre index existant. En effet il est parfois préférable de ne pas « alourdir » un index déjà composé de plusieurs champs, exemple un covering index, ou bien encore un index numérique spécialement impliqué dans des jointures qui verrait d’un mauvais oeil ce VARCHAR que vous souhaitez lui ajouter… Cela pourrait engendrer un ralentissement sur les requêtes précedemment basées sur les index que vous souhaitez « enrichir ».

Le « mk duplicate key checker » vous apporte les candidats sur un plateau, à vous d’apporter la valeur ajoutée finale ;)

A retenir :

- Les covering index constituent une optimisation très intéressante pour éviter de couteux random I/O, notamment sur disque. Ayez à l’esprit qu’ils existent et profitez des caractéristiques propres à InnoDB dans ce domaine (présence de la clé primaire derrière chaque index secondaire) pour optimiser vos requêtes sans créer d’index redondants.

- Dans certains cas un covering index peut également vous aider à faire disparaître un disgracieux « Using filesort » dans la colonne « Extra » (la preuve dans notre exemple).

Mots-clefs : ,

11 commentaires sur “Les covering index, de la théorie à la pratique avec MyISAM et InnoDB”

  1. tsyr dit :

    Dommage qu’on ne puisse mixer les covering index avec les index requis par MySQL pour les foreign keys …
    En tout cas, encore merci pour cet article très intéressant.

  2. Arnaud dit :

    Salut tsyr,

    Je n’ai pas d’exemple sous les yeux mais je ne vois pas pourquoi on ne pourrait pas rentrer dans des cas de covering index également avec les clés étrangères ? Le fait qu’on puisse définir des clés étrangères composées facilite la tâche je pense non ? Je suis preneur si tu as un cas où tu penses que cela n’est pas possible, j’y jetterai un oeil.

  3. StephaneC dit :

    Un petit détail supplémentaire : il peut arriver dans certaines conditions qu’en triturant la requête pour qu’elle utilise un covering index, la requête réécrite (donc avec les covering index) soit moins efficace que la requête initiale.
    Le cas typique, c’est quand on utilise une sous-requête en vue de l’utilisation d’un covering index mais que cette sous-requête est lente.
    Evidemment, ce cas de figure est plutôt rare, mais c’est juste pour signaler que comme toute optimisation, les covering index ont aussi des contre-indications.

  4. Arnaud dit :

    Merci Stéphane pour cette précision.

    Ca promet pour ta session à Santa Clara ;) Avec un peu de chance Pascal et moi y serons, comme l’an passé !

  5. StephaneC dit :

    Eh oui, justement, je suis en train de chercher un exemple pour ma session, et c’est pas facile facile tout ça !!!
    Heureusement, il me reste 2 mois et demi pour qu’une idée lumineuse me vienne ;-)

  6. [...] sommes dans le cas d’un covering index mais celui-ci n’est pas hélas pas d’une grande utilité sur la machine perso [...]

  7. [...] avec notamment celle de Stéphane Combaudon, un lecteur de ce blog, qui nous parlera en détail des covering index. A ne pas rater Autres billets susceptibles de vous intéresser :dbnewz au salon [...]

  8. olive dit :

    bonjour,

    merci pour cette explication limpide, j’ai cepandant une question, que se passe t’il dans le cas d’un select à plusieurs WHERE ? du genre:

    SELECT genre, count(*) as c FROM `videos` WHERE videos.enable=1 AND videos.type=0 Group by genre

    si je place un index composé comme suit:
    alter table videos add index Idx_enable_type_genre(enable, type, genre)

    j’ai bien un using index mais mysql créé quand même une temporary table or dans cet exemple: http://dasini.net/blog/2009/02/18/optimisation-de-requetes-comprendre-loptimiseur-de-mysql/ on devrait pouvoir arriver à faire sans.

    Une petite idée ?

  9. Arnaud dit :

    Bonjour,

    Effectivement c’est interessant, a premiere vue j’aurais sans doute placé mes index comme tu l’as fait… Peux-tu poster ici un show create table from videos ainsi qu’un show index from videos ?

    Apres avoir relu l’exemple que tu cites sur le blog d’Olivier, je me rends compte que lui a finalement retenu un index où le group by (le responsable de ta table temp) est en premiere position, donc en toute « logique » je te conseillerais d’appliquer la meme idee histoire de voir ? Tente un index sur (genre, enable, type) par exemple.

    L’idee du show index est aussi de voir si vraiment tu as besoin d’un index sur les 3 colonnes… Si par exemple « enable » est tres peu selectif contrairement a « type », je pense que tu peux te permettre de n’en garder que deux, a voir.

    Par ailleurs un test que je ferai aussi histoire de voir c’est un alter table videos order by genre, afin d’avoir ma table deja toute ordonnee selon le genre (si tu es en myisam). Je ne sais pas si l’optimiseur s’en rendrait compte et eliminerait le tri que tu constates. (A ne tenter que si ta table n’est pas enorme, a des fins de test).

    Tiens nous au courant…

  10. Salut,
    effectivement Arnaud à raison, l’ordre de l’index est important. Son premier élément doit être le champ du group by.
    ++

    Olivier

  11. Baptiste Jouaneton dit :

    Bonjour,
    Je suis tout à fait d’accord, l’ordre de l’index est très important et joue d manière non négligeable sur les performances.
    En revanche, le premier champs de l’index ne devrait il pas être plutôt le champs le plus discriminant?

    Baptiste

Laisser une réponse