Sep
05
2008
Cardinalité, sélectivité et distributivité d’un index MySQL : quel impact sur le plan d’exécution ?
Posted by DBNewz on Fri 05 Sep 2008 00:37 UTC
Tags:

Nouveau volet de notre série consacrée aux index, la notion de sélectivité d’un index est ici à l’honneur.
Souvenez-vous du billet précédent : notre table de test contient 1 million de lignes et un champ “flag” à la cardinalité très faible : 2.

Cardinalité ? Sélectivité ? Avant d’aller plus loin, deux définitions s’imposent. Tout d’abord la cardinalité d’un index : c’est le nombre de valeurs uniques qu’il contient.

La sélectivité d’un index se calcule elle de la façon suivante :

Selectivité = Cardinalité(Idx) / Nombre total d’enregistrements dans la table
Résultat des courses notre index à une sélectivité de 2 /1 000 000 = 2e-6, qui a dit “peu sélectif” ?

A l’opposé d’une si faible sélectivité on trouve celle d’une clé primaire puisque celle-ci a une selectivité de 1. Exprimé autrement : à une “entrée” de la clé primaire ne correspond qu’un seul enregistrement dans la table.

D’où la règle générale suivante : plus un index est sélectif, plus il est efficace, c’est à dire capable d’identifier rapidement la ou les données recherchées.

L’optimiseur MySQL est chargé de transformer votre requête en un plan d’exécution le plus efficace possible, suit-il à la lettre cette règle générale ?

Vous vous doutez bien que non…

Rentrée oblige : le cas d’école

Débutons par le cas “standard”, celui qui effectivement illustre qu’un index sélectif est efficace. Un tel index a donc toutes les chances d’être choisi par l’optimiseur MySQL lors de la conception du plan d’exécution de la requête (s’il est pertinent pour celle-ci bien sûr).

On utilise ici la base de test sakila afin d’afficher la liste des films de l’acteur dont le nom est ‘CRUZ’ :

mysql> EXPLAIN SELECT f.title
FROM film f, actor a, film_actor fa
WHERE a.actor_id = fa.actor_id
AND fa.film_id = f.film_id
AND a.last_name = ‘CRUZ’\G

*************************** 1. row
id: 1
select_type: SIMPLE
table: a
type: ref
possible_keys: PRIMARY,idx_actor_last_name
key: idx_actor_last_name
key_len: 137
ref: const
rows: 1
Extra: Using where; Using index
*************************** 2. row
id: 1
select_type: SIMPLE
table: fa
type: ref
possible_keys: PRIMARY,idx_fk_film_id
key: PRIMARY
key_len: 2
ref: sakila.a.actor_id
rows: 13
Extra: Using index
*************************** 3. row
id: 1
select_type: SIMPLE
table: f
type: eq_ref
possible_keys: PRIMARY
key: PRIMARY
key_len: 2
ref: sakila.fa.film_id
rows: 1
Extra:
3 rows in set (0.00 sec)

La commande EXPLAIN indique le plan d’exécution de la requête : quelles informations en tirer du point de vue des index utilisés ?

L’optimiseur a tout d’abord décidé de restreindre notre recherche grâce au critère “nom de l’acteur”, pour cela il utilise l’index “idx_actor_last_name” de la table “actor”.
“Using index” indique que nous sommes ici dans le cas d’un “covering index“, c’est à dire qu’il est inutile pour MySQL d’aller lire les enregistrements puisque toute l’information recherchée (le nom de l’acteur) est présente dans l’index. Dans le cas d’une table MyISAM cela signifie que seul le fichier .MYI (index) est lu, inutile d’aller lire le .MYD (data).

Jetons un oeil aux index présents sur cette table afin d’en savoir un peu plus sur l’index utilisé  (idx_actor_last_name) :

mysql> SHOW INDEX FROM ACTOR\G
*************************** 1. row
Table: ACTOR
Non_unique: 0
Key_name: PRIMARY
Seq_in_index: 1
Column_name: actor_id
Collation: A
Cardinality: 200
Sub_part: NULL
Packed: NULL
Null:
Index_type: BTREE
Comment:
*************************** 2. row
Table: ACTOR
Non_unique: 1
Key_name: idx_actor_last_name
Seq_in_index: 1
Column_name: last_name
Collation: A
Cardinality: 200
Sub_part: NULL
Packed: NULL
Null:
Index_type: BTREE
Comment:
2 rows in set (0.02 sec)

A priori notre index a une cardinalité de 200… C’est à dire que d’après MySQL, celui-ci contient approximativement (dixit la doc) 200 valeurs uniques. Une estimation à prendre en effet avec des pincettes puisque le champ indexé n’en contient lui-même que 121 :

mysql> SELECT COUNT(DISTINCT(last_name)) FROM actor;
+—————————-+
| COUNT(DISTINCT(last_name)) |
+—————————-+
|                        121 |
+—————————-+
1 row in set (0.06 sec)

Calculons plutôt la sélectivité de l’index à partir des chiffres suivants :
S = 121 / 200 (nb d’enregistrements dans la table)
S = 0,605

C’est moins bon qu’une sélectivité de 1 bien sûr, mais cela dit cet index permet de mettre la main relativement rapidement sur le nom recherché. La distributivité des données est en effet plutôt “homogène”. Entendre par là qu’un seul acteur ne représente pas 95% de la table, ce qui fausserait l’idée que l’on se fait sur la sélectivité de l’index… En effet celle-ci ne prend pas en compte (en tout cas dans la formule) la distributivité des données.

Concernant les approximations relevées ci-dessus sur les cardinalités de nos index, cet article est entièrement tourné vers ce phénomène. A lire !

Voici un aperçu de la distributivité de la colonne “last_name” :

mysql> SELECT last_name, COUNT(last_name) as nb
FROM actor
GROUP BY last_name
ORDER BY nb
DESC LIMIT 5;

+———–+—-+
| last_name | nb |
+———–+—-+
| KILMER    |  5 |
| NOLTE     |  4 |
| TEMPLE    |  4 |
| PECK      |  3 |
| ALLEN     |  3 |
+———–+—-+
5 rows in set (0.00 sec)

Le nom d’acteur le plus représenté parmi les 121 noms de la table “actor” apparaît “seulement” 5 fois, on peut donc dire qu’au pire l’index posé sur “last_name” correspond à 5 enregistrements de la table. Par ailleurs, la moitié environ des noms d’acteur présents dans la table sont uniques.

Pour revenir à notre plan d’exécution, MySQL a donc utilisé pour cette première étape de “sélection” un index plutôt sélectif.

Etape suivante : la jointure entre la table “actor” et “film_actor”.

L’attribut “ref” affiché par la commande EXPLAIN indique que la table “film_actor” sera parcourue pour chaque valeur correspondante de l’index “idx_actor_last_name”. Cet index n’étant pas unique, il existe en effet des cas où à une valeur de l’index, mettons “KILMER”, vont correspondre 5 enregistrements dans la table “film_actor”. Ce parcours n’est ici pas pénalisant puisque nous avons encore une fois affaire à un “covering index”, les enregistrements de la table ne sont pas accédés puisque tout ce que nous recherchons est déjà dans l’index, une telle optimisation est la bienvenue !

Nous reparlerons des covering index dans un billet ultérieur, mais vous connaissez maintenant le principe.

Dernière étape : la jointure avec la table “film”. “eq_ref” signifie qu’un seul enregistrement de la table “film” est lu pour chaque enregistrement correspondant de la table “film_actor”. Rien d’étonnant à cela puisque nous passons pour la table “film” par une clé primaire qui fait donc la jointure avec la clé primaire de “film_actor”, on tombe donc directement sur un seul film identifié par sa clé primaire.

Bilan de cet EXPLAIN ?

L’estimation du nombres d’enregistrements à parcourir pour aboutir au résultat d’après l’optimiseur est de : 1 x 13 x 1 = 13 enregistrements. En parcourant rapidement cet EXPLAIN comme nous venons de le faire, on constate que 13 enregistrements environ sont à parcourir via deux covering index et une clé primaire : la requête a l’air convenable.

Les “Index hints” ou comment “orienter” les choix de l’optimiseur

Quel plan d’exécution l’optimiseur aurait-il choisi si nous n’avions pas eu d’index ? Quelles conséquences sur le nombre estimé d’enregistrements à parcourir ?

Pour le savoir, les barbares suppriment leurs index à grands coups de DROP INDEX ou d’ALTER TABLE plus ou moins heureux, les autres peuvent utiliser ce qu’on appelle les “index hints” et “suggérer” à l’optimiseur (pour ne pas dire forcer) d’effectuer certaines actions et pas d’autres.

Exemple : forcer l’utilisation d’un index ou au contraire l’ignorer ou encore joindre deux tables dans un ordre particulier…

Pour forcer le trait (”cas d’école” rappelez-vous), on supprime ici toute possibilité pour l’optimiseur d’utiliser un index “intéressant” pour lui :

mysql> EXPLAIN SELECT f.title
FROM film f IGNORE INDEX (PRIMARY, idx_title),
actor a IGNORE INDEX (PRIMARY, idx_actor_last_name), film_actor
fa IGNORE INDEX (PRIMARY, idx_fk_film_id)
WHERE a.actor_id = fa.actor_id
AND fa.film_id = f.film_id
AND a.last_name = ‘CRUZ’\G

*************************** 1. row
id: 1
select_type: SIMPLE
table: a
type: ALL
possible_keys: NULL
key: NULL
key_len: NULL
ref: NULL
rows: 200
Extra: Using where
*************************** 2. row
id: 1
select_type: SIMPLE
table: fa
type: ALL
possible_keys: NULL
key: NULL
key_len: NULL
ref: NULL
rows: 5920
Extra: Using where; Using join buffer
*************************** 3. row
id: 1
select_type: SIMPLE
table: f
type: ALL
possible_keys: NULL
key: NULL
key_len: NULL
ref: NULL
rows: 952
Extra: Using where; Using join buffer
3 rows in set (0.00 sec)

Les résultats sont identiques en 5.1.26 et en 5.0.67, seule la mention du “Using join buffer” fait son apparition en 5.1
Le nombre approximatif d’enregistrements à parcourir est ici de : 200 x 5920 x 952 = 1 127 168 000, un résultat logique puisque l’intégralité des trois tables sont parcourues…

Bien que “dramatique” ce plan d’exécution a ici des conséquences très limitées puisque d’aussi petites tables sont aisément logées en mémoire. Les index sont stockés dans le key_buffer_size et le cache de l’OS s’occupe des données puisque nous sommes en MyISAM (à comparer avec l’innodb_buffer_pool qui stocke index ET données).

Résumons ce “cas d’école” : l’optimiseur a effectivement choisi des clés primaires (index le plus sélectif possible) ainsi qu’un index efficace, tout est logique.

Voyons maintenant un cas… “particulier” qui va nous apprendre à garder un oeil critique sur les plans d’exécution proposés par MySQL.

La légende des 30 %

Il était une fois un optimiseur MySQL qui décidait de ne jamais utiliser un index si celui-ci osait sélectionner plus de 30% des enregistrements d’une table. Pour schématiser, les développeurs de l’optimiseur considèreraient d’après leur expérience qu’en effet une fois cette limite dépassée, un parcours séquentiel de la table serait plus rapide que davantage d’accès aléatoires aux données (cas d’un index MyISAM par exemple). La réalité est évidemment beaucoup plus complexe et bien que le code source ne contienne pas en “dur” un tel seuil, cette valeur de 30% circule ici et là sur le net, davantage pour illustrer l’idée de sélectivité que pour réellement indiquer qu’il existe une telle valeur au sein de l’optimiseur qui guiderait ses choix si grossièrement.

L’idée à retenir est qu’un index sélectif est un bon candidat pour l’optimiseur et a donc toutes ses chances d’être retenu dans le plan d’exécution final.

Il existe cependant quelques exceptions, et il est parfois difficile de comprendre les choix de l’optimiseur…

Nous reprenons notre table de test conçue dans le billet précédent.
Rappel : 1 million d’enregistrements, 3 colonnes : une clé primaire, un TIMESTAMP et un champ “flag” (0 ou 1) équitablement réparti (environ 500 000 “0″ pour autant de “1″).

L’index “flag” ne possède que 2 entrées à comparer avec le million de rangées de la table t. Autrement dit, à un index correspond en moyenne 500 000 rangées possibles, bref absolument rien de sélectif, c’est tout le contraire.

Quel accueil l’optimiseur MySQL va t’il réserver à notre index “flag” sur une requête du type SELECT count(date) from t WHERE flag = 1 ?

Les tests effectués ci-dessous sont valables pour les versions 5.0.67 et la 5.1.26.
Rappel de la structure de la table t et de ses index :

mysql> show create table t;
CREATE TABLE `t` (
`id` mediumint(8) unsigned NOT NULL auto_increment,
`date` timestamp NOT NULL default CURRENT_TIMESTAMP on update CURRENT_TIMESTAMP,
`flag` tinyint(4) NOT NULL default ‘0′,
PRIMARY KEY  (`id`),
KEY `flag` (`flag`)
) ENGINE=MyISAM AUTO_INCREMENT=1000001 DEFAULT CHARSET=latin1

Concernant les index nous avons une clé primaire “id” et “flag”, de type “index” :

mysql> show index from t\G
*************************** 1. row
Table: t
Non_unique: 0
Key_name: PRIMARY
Seq_in_index: 1
Column_name: id
Collation: A
Cardinality: 1000000
Sub_part: NULL
Packed: NULL
Null:
Index_type: BTREE
Comment:
*************************** 2. row
Table: t
Non_unique: 1
Key_name: flag
Seq_in_index: 1
Column_name: flag
Collation: A
Cardinality: 2
Sub_part: NULL
Packed: NULL
Null:
Index_type: BTREE
Comment:
2 rows in set (0.01 sec)

Pour un rappel sur les différents types d'index disponibles, ce billet précédent est tout indiqué.

Appliquons notre requête à notre jeu d’essai :

mysql> SELECT SQL_NO_CACHE COUNT(date)
FROM t WHERE flag = 1;
+————-+
| count(date) |
+————-+
|      499959 |
+————-+
1 row in set (1.70 sec)

Un score sensiblement identique est obtenu pour l’autre valeur de “flag” :

mysql> SELECT SQL_NO_CACHE COUNT(date)
FROM t WHERE flag = 0;
+————-+
| count(date) |
+————-+
|      500041 |
+————-+
1 row in set (1.69 sec)

Voyons maintenant ce qui se passe avec EXPLAIN :

mysql> EXPLAIN SELECT SQL_NO_CACHE COUNT(date)
FROM t WHERE flag = 1\G
*************************** 1. row
id: 1
select_type: SIMPLE
table: t
type: ref
possible_keys: flag
key: flag
key_len: 1
ref: const
rows: 512463
Extra:
1 row in set (0.00 sec)

Surprise ! MySQL utilise notre index alors que la requête retourne environ la moitié de nos enregistrements… Nous sommes donc loin des “30%”, et pourtant les index ont été préférés au parcours complet de la table. On note ici le type “ref” qui signifie que chaque ligne de la table t correspondant à la valeur de “flag” est lue, c’est à dire environ 500 000 random I/O.

Retenons que sans la clause EXPLAIN, cette requête s’exécute en 1.7 secondes quel que soit la valeur de flag.

Un index de trop ?

Voyons ce que cette même requête donnerait sans l’index appliqué au champ “flag” :

mysql> EXPLAIN SELECT SQL_NO_CACHE count(date)
FROM t IGNORE INDEX(flag)
WHERE flag = 1\G
*************************** 1. row
id: 1
select_type: SIMPLE
table: t
type: ALL
possible_keys: NULL
key: NULL
key_len: NULL
ref: NULL
rows: 1000000
Extra: Using where
1 row in set (0.00 sec)

Changement de décor, MySQL ne peut plus utiliser l’index “flag” et effectue un scan complet de la table, un million de lignes sont parcourues (deux fois plus qu’avec l’utilisation de l’index “flag”) mais séquentiellement cette fois.

Quel est le temps d’exécution de ce scan complet ?

mysql> SELECT SQL_NO_CACHE COUNT(date)
FROM t IGNORE INDEX(flag) WHERE flag = 1\G
*************************** 1. row
count(date): 499959
1 row in set (0.23 sec)

23 centièmes de seconde seulement, le scan complet de la table est donc ici 7 fois plus rapide que l’accès aux données par les index.

Pourquoi l’optimiseur a t’il décidé de partir sur un plan d’exécution basé sur l’utilisation de l’index “flag” si peu sélectif ? Peut-être considère t-il que 50% des données retournées est un seuil trop bas pour “désactiver” les index par rapport au scan complet de la table ?

Modifions maintenant la distributivité du champ flag. Nous avions quasiment autant de 0 que de 1 dans la colonne “flag”, voyons ce que donnerait 95% de “1″ et 5% de “0″.

Pour cela on modifie la procédure stockée utilisée précedemment pour le remplissage de la table “t” et en deux étapes on charge d’abord les 950 000 lignes de “1″ puis les 50 000 lignes de “0″, reste alors à mélanger le tout :

mysql> CREATE TABLE t2 LIKE t;
Query OK, 0 rows affected (0.03 sec)

mysql> INSERT INTO t2 SELECT * FROM t ORDER BY RAND();
Query OK, 1000000 rows affected (12.59 sec)
Records: 1000000  Duplicates: 0  Warnings: 0

t2 est désormais équivalente à la table t à ceci près qu’elle contient 95% de “0″, le reste en “1″, le tout aléatoirement réparti.

mysql> EXPLAIN SELECT COUNT(date)
FROM t2 WHERE flag = 1\G
*************************** 1. row
id: 1
select_type: SIMPLE
table: t2
type: ref
possible_keys: flag
key: flag
key_len: 1
ref: const
rows: 950277
Extra:
1 row in set (0.01 sec)

Même résultat que précédemment, quelque soit la valeur de flag, “1″ ou “0″ : MySQL passe toujours par l’index s’il est disponible :

mysql> select COUNT(date) FROM t2
WHERE flag = 0;
+————-+
| count(date) |
+————-+
|       50000 |
+————-+
1 row in set (0.23 sec)

mysql> select COUNT(date) FROM t2 IGNORE INDEX(flag) WHERE flag = 0;
+————-+
| count(date) |
+————-+
|       50000 |
+————-+
1 row in set (0.17 sec)

mysql> select COUNT(date) FROM t2
WHERE flag = 1;
+————-+
| count(date) |
+————-+
|      950000 |
+————-+
1 row in set (3.17 sec)

mysql> select COUNT(date) FROM t2 IGNORE INDEX(flag)
WHERE flag = 1;
+————-+
| count(date) |
+————-+
|      950000 |
+————-+
1 row in set (0.20 sec)

… On constate que les résultats sont quasiment équivalents pour le cas où flag = 0, c’est effectivement la valeur pour laquelle l’index est le plus sélectif, en revanche l’écart se creuse encore davantage entre le scan complet de la table et l’accès aux données via l’index : le parcours complet de la table est 16 fois plus rapide.

La sélectivité de notre index est la même dans la table t2 que dans la table t1, seule la distributivité des données de la colonne flag a été modifiée pour en faire un index vraiment peu sélectif dans le cas où “flag” = 1 puisque dans cette configuration ce sont 95% des données de la table qui sont sélectionnées, la légende prend un coup de vieux…

Conclusion

Il est parfois difficile de comprendre les choix de l’optimiseur, il existe des règles générales et des exceptions troublantes. L’optimiseur est un logiciel complexe, très efficace la plupart du temps mais pas parfait. L’architecture même de MySQL, basé sur des moteurs “externes” (”pluggable storage engine”), complique sa tâche : il lui est difficile, selon les cas, de déterminer où seront stockées les données. Cette information est pourtant cruciale pour prendre des décisions lourdes de conséquences. De plus chaque moteur gère les index à sa façon…
Sommes-nous en présence de MyISAM (index en mémoire, données cachées par l’OS), sur du InnoDB ? (index clustered, données triées selon la clé primaire “accolées” à l’index), ou bien encore sur du MEMORY (les lectures aléatoires ou random I/O sont beaucoup moins coûteuses en mémoire que sur disque), les différents système de cache sont-ils activés ? Les données sont-elles toutes en mémoire ou en partie sur disque ? On peut également parier sur le fait que l’apparition des disques SSD devrait par exemple impacter les choix de l’optimiseur à l’avenir…

Bref, à moins d’avoir écrit soi-même le code source de l’optimiseur, il est difficile de tout maîtriser de A à Z en ce qui le concerne, le conseil est alors le suivant : il faut appliquer régulièrement EXPLAIN sur les requêtes importantes de vos applications. Savoir lire un plan d’exécution et ainsi comprendre ce que MySQL a decidé pour votre requête permet de détecter avec un peu d’expérience si le plan d’exécution est efficace.
Utilisez le cas échéant les “index hints” pour modifier si besoin le parcours proposé : IGNORE INDEX, FORCE INDEX, ou encore STRAIGHT JOIN si vous souhaitez modifier l’ordre de jointures de vos tables…

Sans se focaliser sur les fameux 30%, un index sélectif est un bon candidat. Nous avons rencontré un cas où un parcours total de la table aurait été plus efficace, cependant c’est parfois l’inverse qui se produit, un index même peu sélectif peut s’avérer payant, il faut donc tester si le plan d’exécution proposé vous semble perfectible.

Derniers détails d’importance : on ne peut pas comparer uniquement deux plans d’exécution uniquement sur l’estimation du nombre d’enregistrements à parcourir… La preuve dans notre exemple, le parcours total et séquentiel de la table (1 million d’enregistrement) s’avère plus rapide que les 500 000 accès aléatoires issus de l’index. On retiendra également de notre exemple qu’un index n’est pas systématiquement synonyme de meilleures performances… (Même si c’est le cas en général).

L’exemple étudié ici est un cas particulier au sens où c’est plutôt le parcours complet de la table (full scan) que l’on cherche d’habitude à éviter. Sachez qu’il existe une variable serveur, max_seeks_for_key (on en parle aussi ici et là) sur laquelle il est possible de jouer pour orienter les choix de l’optimiseur.

Enfin, puisqu’il est difficile d’aborder toutes les problématiques possibles autour de la sélectivité d’un index dans un seul billet, voici quelques autres articles sur la même thématique afin d’aller encore plus loin :

  • L’article qui m’a incité à effectuer mes propres tests.

N’oubliez pas de lire également les commentaires associés à ces articles…