Principes des index MySQL et optimisation des requêtes

Introduction

Les systèmes d'application courants présentent un ratio lecture/écriture d'environ 10:1. Les opérations d'insertion et de mise à jour standard posent rarement des problèmes de performance. En production, ce sont les requêtes complexes qui sont les plus fréquentes et les plus susceptibles de causer des problèmes. L'optimisation des requêtes est donc primordiale. Pour accélérer les requêtes, il est essentiel de parler des index.

Pourquoi utiliser des index ?

Dans MySQL, les index, également appelés "clés", sont des structures de données utilisées par le moteur de stockage pour localiser rapidement les enregistrements. Les index sont cruciaux pour de bonnes performances, surtout à mesure que la quantité de données dans une table augmente. L'optimisation des index est souvent le moyen le plus efficace d'améliorer les performances des requêtes, pouvant multiplier celles-ci par plusieurs ordres de grandeur. Un index est comparable à l'index d'un dictionnaire ; sans lui, il faudrait parcourir des centaines de pages pour trouver un mot spécifique.

Principes des index

Principe fondamental

L'objectif des index MySQL est d'améliorer l'efficacité des requêtes. C'est le même principe que l'utilisation d'une table des matières pour un livre : on localise d'abord le chapitre, puis la section, puis la page. D'autres exemples incluent la recherche dans un dictionnaire, la recherche de numéros de train ou de vols.

Essentiellement, il s'agit de réduire continuellement la portée des données à rechercher pour isoler le résultat souhaité, transformant des opérations aléatoires en opérations séquentielles. Avec un mécanisme d'indexation, on peut toujours utiliser la même méthode de recherche pour localiser les données.

Les bases de données fonctionnent de manière similaire, mais de manière plus complexe, car elles doivent gérer non seulement les recherches d'égalité, mais aussi les recherches par intervalle (<, >, BETWEEN, IN), les recherches floues (LIKE) et les recherches par union (OR). Comment une base de données doit-elle gérer tous ces cas ? Reprenons l'exemple du dictionnaire : peut-on diviser les données en sections et effectuer des recherches par section ? Si une table contient 1000 enregistrements, on pourrait diviser les données de 1 à 100 en première section, de 101 à 200 en deuxième section, etc. Pour trouver le 250ème enregistrement, il suffirait de chercher dans la troisième section, éliminant ainsi 90% des données inutiles. Mais qu'en est-il de 10 millions d'enregistrements ? Combien de sections seraient idéales ? Les personnes ayant des notions d'algorithmique penseront aux arbres de recherche, dont la complexité moyenne est O(log N), offrant de bonnes performances de recherche. Cependant, un aspect crucial est négligé ici : la complexité est basée sur l'hypothèse d'un coût d'opération identique à chaque étape. L'implémentation d'une base de données est plus complexe ; d'une part, les données sont stockées sur disque, et d'autre part, pour améliorer les performances, des parties des données sont lues en mémoire. Le coût d'accès au disque est environ 100 000 fois supérieur à celui de l'accès à la mémoire, ce qui rend les arbres de recherche simples insuffisants pour des scénarios d'application complexes.

IO disque et prélecture

Compte tenu du coût élevé des opérations d'IO disque, les systèmes d'exploitation d'ordinateurs implémentent des optimisations : lors d'une opération d'IO, non seulement les données à l'adresse disque actuelle sont lues, mais aussi les données adjacentes sont chargées dans le buffer mémoire. Ceci est basé sur le principe de localité spatiale, qui stipule que lorsque l'ordinateur accède à des données à une certaine adresse, les données voisines seront probablement accédées bientôt. La quantité de données lue lors d'une seule opération d'IO est appelée "page". La taille d'une page dépend du système d'exploitation, généralement 4 Ko ou 8 Ko. Cela signifie qu'en lisant une page entière, une seule opération d'IO est réellement effectuée. Cette théorie est très utile pour la conception des structures de données d'index.

Structures de données d'index

Aucune structure de données n'apparaît par hasard ; elle a toujours un contexte et un cas d'utilisation. Résumons ce que nous attendons de cette structure de données : elle doit pouvoir limiter le nombre d'opérations d'IO disque à un très petit nombre à chaque recherche, idéalement dans l'ordre de grandeur d'une constante. Cela nous amène à considérer si un arbre de recherche multi-voies avec une hauteur contrôlable pourrait répondre à ces exigences. C'est ainsi qu'est né l'arbre B+.

L'image ci-dessus représente un arbre B+. Pour sa définition, référez-vous à l'arbre B+. Ici, nous nous concentrerons sur les points clés. Les blocs bleu clair sont appelés "blocs disque". Chaque bloc disque contient plusieurs éléments de données (en bleu foncé) et des pointeurs (en jaune). Par exemple, le bloc 1 contient les éléments de données 17 et 35, ainsi que les pointeurs P1, P2 et P3. P1 pointe vers un bloc disque contenant des valeurs inférieures à 17, P2 vers un bloc disque contenant des valeurs entre 17 et 35, et P3 vers un bloc disque contenant des valeurs supérieures à 35. Les données réelles se trouvent dans les nœuds feuilles : 3, 5, 9, 10, 13, 15, 28, 29, 36, 60, 75, 79, 90, 99. Les nœuds internes ne stockent pas de données réelles ; ils contiennent uniquement des éléments de données qui guident la recherche, comme 17 et 35 qui n'existent pas réellement dans la table.

Processus de recherche dans un arbre B+

Comme illustré, pour rechercher l'élément de données 29, le bloc disque 1 est d'abord chargé du disque vers la mémoire (première opération d'IO). Dans la mémoire, une recherche binaire détermine que 29 se situe entre 17 et 35, ce qui permet de sélectionner le pointeur P2 du bloc disque 1. Le temps passé en mémoire étant très court par rapport aux IO disque, il est négligeable. En utilisant l'adresse disque du pointeur P2 du bloc disque 1, le bloc disque 3 est chargé du disque vers la mémoire (deuxième opération d'IO). 29 se situe entre 26 et 30, sélectionnant le pointeur P2 du bloc disque 3. En suivant ce pointeur, le bloc disque 8 est chargé en mémoire (troisième opération d'IO). Une recherche binaire en mémoire trouve alors 29, et la requête se termine. Au total, trois IO ont été nécessaires. En réalité, un arbre B+ à 3 niveaux peut représenter des millions de données. Si la recherche de millions d'enregistrements ne nécessite que trois IO, l'amélioration des performances est énorme. Sans index, chaque élément de données nécessiterait une opération d'IO, totalisant des millions d'IO, ce qui est manifestement coûteux.

Propriétés de l'arbre B+

Les champs d'index doivent être aussi petits que possible : D'après l'analyse ci-dessus, le nombre d'IO dépend de la hauteur h de l'arbre B+. Si N est le nombre total d'enregistrements dans la table et m est le nombre d'éléments de données par bloc disque, alors h = logm+1N. Pour une quantité de données N fixe, plus m est grand, plus h est petit. Or, m = taille du bloc disque / taille de l'élément de données. La taille du bloc disque est la taille d'une page de données, qui est fixe. Si l'espace occupé par chaque élément de données est plus petit, le nombre d'éléments de données augmente, et la hauteur de l'arbre diminue. C'est pourquoi chaque élément de données, c'est-à-dire le champ d'index, doit être aussi petit que possible. Par exemple, un INT occupe 4 octets, la moitié d'un BIGINT qui en occupe 8. C'est aussi pourquoi l'arbre B+ exige que les données réelles soient stockées dans les nœuds feuilles plutôt que dans les nœuds internes. Si elles étaient stockées dans les nœuds internes, le nombre d'éléments de données par bloc disque diminuerait considérablement, entraînant une augmentation de la hauteur de l'arbre. Si le nombre d'éléments de données est de 1, l'arbre se dégrade en une liste linéaire.
La propriété de corrsepondance de préfixe le plus à gauche de l'index (correspondance de gauche à droite) : Lorsque les éléments de données dans un arbre B+ sont des structures composites, comme (nom, âge, sexe), l'arbre B+ construit l'arbre de recherche dans l'ordre de gauche à droite. Par exemple, pour rechercher des données comme (Jean, 20, F), l'arbre B+ comparera d'abord le nom pour déterminer la direction de recherche suivante. Si les noms sont identiques, il comparera ensuite l'âge, puis le sexe, pour finalement obtenir les données recherchées. Cependant, lorsque des données comme (20, F), sans le nom, sont utilisées pour la recherche, l'arbre B+ ne sait pas quel nœud consulter ensuite. Comme le nom est le premier facteur de comparaison lors de la construction de l'arbre de recherche, il faut d'abord rechercher par nom pour savoir où chercher ensuite. Par exemple, lors de la recherche de données comme (Jean, F), l'arbre B+ peut utiliser le nom pour spécifier la direction de recherche, mais comme le champ suivant, l'âge, est manquant, il ne peut que trouver toutes les données dont le nom est "Jean", puis filtrer celles dont le genre est "F". C'est une propriété très importante, à savoir la propriété de correspondance de préfixe le plus à gauche de l'index.

Gestion des index dans MySQL

I. Fonctionnalités


#1. La fonction d'un index est d'accélérer la recherche.
#2. Les clés primaires, les index uniques et les index composites dans MySQL sont également des index. Ces index accélèrent la recherche et ont une fonction de contrainte.

II. Classification des index MySQL


<strong>Classification des index
1. Index ordinaire (index) :</strong> Accélère la recherche.
<strong>2. Index unique</strong>
   - Clé primaire (primary key) : Accélère la recherche + contrainte (non nul et unique).
   - Index unique (unique) : Accélère la recherche + contrainte (unique).
<strong>3. Index composite</strong>
   - primary key(id, name) : Clé primaire composite.
   - unique(id, name) : Index unique composite.
   - index(id, name) : Index ordinaire composite.
<strong>4. Index de recherche plein texte (fulltext) :</strong> Idéal pour rechercher de longs articles.
<strong>5. Index spatial (spatial) :</strong> Connaissance générale, rarement utilisé.

III. Deux principaux types d'index : Hash et B-Tree


# Lors de la création des index ci-dessus, nous pouvons spécifier leur type. Il existe deux catégories :
# Index de type Hash : rapide pour la recherche d'une seule ligne, lent pour les recherches par intervalle.
# Index de type B-Tree : arbre B+, plus il y a de niveaux, plus la quantité de données augmente exponentiellement (nous l'utilisons car InnoDB le prend en charge par défaut).

# Les différents moteurs de stockage prennent en charge différents types d'index :
# InnoDB : prend en charge les transactions, le verrouillage au niveau des lignes, les index B-tree, Full-text, etc. Ne prend pas en charge les index Hash.
# MyISAM : ne prend pas en charge les transactions, le verrouillage au niveau des tables, les index B-tree, Full-text, etc. Ne prend pas en charge les index Hash.
# Memory : ne prend pas en charge les transactions, le verrouillage au niveau des tables, les index B-tree, Hash, etc. Ne prend pas en charge les index Full-text.
# NDB : prend en charge les transactions, le verrouillage au niveau des lignes, les index Hash. Ne prend pas en charge les index B-tree, Full-text.
# Archive : ne prend en charge pas les transactions, le verrouillage au niveau des tables, les index B-tree, Hash, Full-text.

IV. Syntaxe de création/suppression d'index


Utiliser la documentation d'aide :
help create
help create index
==================
1. Création d'index
   - Création lors de la création de la table (points à noter) :
   create table s1(
       id int, # Vous pouvez ajouter primary key ici
       # id int index # On ne peut pas ajouter d'index comme ça, car index n'a pas de contrainte. Contrairement à primary key ou unique, on ne peut pas ajouter l'index lors de la définition du champ.
       name char(20),
       age int,
       email varchar(30)
       # primary key(id) # On peut aussi l'ajouter ici
       index(id) # On peut l'ajouter comme ça
   );
   - Création après la création de la table :
       create index idx_name on s1(name); # Ajouter un index ordinaire
       create unique index idx_age on s1(age); # Ajouter un index unique
       alter table s1 add primary key(id); # Ajouter une clé primaire, c'est-à-dire ajouter une contrainte de clé primaire au champ id.
       create index idx_multi_name_age on s1(id, name); # Ajouter un index composite ordinaire.
2. Suppression d'index :
       drop index idx_id on s1;
       drop index idx_name on s1; # Supprimer un index ordinaire.
       drop index idx_age on s1; # Supprimer un index unique. Il est supprimé comme un index ordinaire, sans avoir besoin d'ajouter "unique" avant "index" pour le supprimer.
       alter table s1 drop primary key; # Supprimer la clé primaire. Comme elle a été ajoutée avec ALTER, on la supprime aussi avec ALTER.

Aide à la consultation. Test des index

Préparation


#1. Préparer la table
create table s1(
   id int,
   name varchar(20),
   gender char(6),
   email varchar(50)
);

#2. Créer une procédure stockée pour insérer un grand nombre d'enregistrements
delimiter $$ # Déclarer le délimiteur de fin de procédure stockée comme $$
create procedure auto_insert1()
BEGIN
   declare i int default 1;
   while(i<3000000)do
       insert into s1 values(i,concat('egon',i),'male',concat('egon',i,'@oldboy'));
       set i=i+1;
   end while;
END$$ # $$ pour terminer
delimiter ; # Rétablir le point-virgule comme délimiteur

#3. Afficher la procédure stockée
show create procedure auto_insert1\G

#4. Appeler la procédure stockée
call auto_insert1();

Test de la vitesse de requête sans index


# Sans index : Scan complet de la table, donc la vitesse de requête est très lente.
mysql> select * from s1 where id=333;
+------+---------+--------+----------------+
| id   | name    | gender | email          |
+------+---------+--------+----------------+
|  333 | egon333 | male   | 333@oldboy.com |
|  333 | egon333 | f      | alex333@oldboy |
|  333 | egon333 | f      | alex333@oldboy |
+------+---------+--------+----------------+
rows in set (0.32 sec)

mysql> select * from s1 where email='egon333@oldboy';
....
... rows in set (0.36 sec)

Ajout d'index


#1. Il faut impérativement créer un index sur le champ utilisé dans la condition WHERE, par exemple pour 'select * from t1 where age > 5;', il faut ajouter un index sur 'age'.

#2. Si la table contient déjà une grande quantité de données, la création d'index peut être lente, consommer de l'espace disque, et ralentir les insertions, suppressions et mises à jour. Seules les requêtes seront rapides.
Par exemple, 'create index idx on s1(id);' scannera toutes les données de la table, puis créera la structure d'index en utilisant 'id' comme élément de données, et la stockera dans la table sur disque.
Une fois l'index créé, les requêtes seront beaucoup plus rapides.

#3. Il est important de noter que les index des tables InnoDB sont stockés dans le fichier s1.ibd, tandis que les index des tables MyISAM ont un fichier d'index séparé, table1.MYI.

Utilisation correcte des index

I. Index couvrant


# Analyse
select * from s1 where id=123;
Cette requête utilise l'index, mais ne le couvre pas.
Elle utilise la valeur id=123 pour localiser la position de cet id dans la structure de l'index, ou plus précisément, sa position dans la table.
Cependant, nous sélectionnons le champ '*', ce qui signifie qu'en plus de l'id, d'autres champs sont nécessaires. Cela implique qu'après avoir trouvé l'id via la structure de l'index, il faut encore aller chercher les valeurs des autres champs pour cette ligne. Cela prend du temps. Clairement, si nous ne sélectionnons que l'id, nous éliminons ce temps d'attente, comme suit :
select id from s1 where id=123;
Cette requête est un index couvrant : elle utilise l'index et récupère directement l'id depuis la structure de l'index, ce qui est très rapide.

II. Index composite

III. Fusion d'index


# Fusion d'index : Utiliser plusieurs index sur colonnes uniques de manière combinée.

# Analyse :
Ce que les index composites peuvent faire, nous pouvons le réaliser avec la fusion d'index. Par exemple :
create index idx_name_email on s1(name,email); # Index composite
Nous pouvons tout à fait créer des index séparés pour "name" et "email".

Ce que l'index composite peut utiliser :
select * from s1 where name='egon' ;
select * from s1 where name='egon' and email='adf';

Ce que la fusion d'index peut utiliser :
select * from s1 where name='egon' ;
select * from s1 where email='adf';
select * from s1 where name='egon' and email='adf';

À première vue, la fusion d'index semble meilleure : elle peut satisfaire plus de cas. Cependant, cela dépend de la situation. Pour 'name='egon' and email='adf', l'index composite est plus efficace. Pour une recherche avec une seule condition, la fusion d'index est plus appropriée.

III. Pour que l'utilisation des index améliore les performances des requêtes comme prévu, nous devons respecter les principes suivants lors de l'ajout d'index :


#1. Principe de correspondance du préfixe le plus à gauche, principe très important.
create index ix_name_email_gender_id on s1(name,email,gender,id);
- Correspondance du préfixe le plus à gauche : Doit correspondre dans l'ordre de gauche à droite.
select * from s1 where name='egon'; # OK
select * from s1 where name='egon' and email='asdf'; # OK
select * from s1 where email='alex@oldboy.com'; # NON OK
MySQL continuera à faire correspondre vers la droite jusqu'à ce qu'il rencontre une requête par intervalle (>, <, BETWEEN, LIKE) et s'arrêtera.
Par exemple, pour 'a = 1 and b = 2 and c > 3 and d = 4', si un index dans l'ordre (a,b,c,d) est créé, 'd' n'utilisera pas l'index. Si un index dans l'ordre (a,b,d,c) est créé, tous les champs pourront utiliser l'index. L'ordre de a,b,d peut être ajusté.

#2. '=' et 'IN' peuvent être dans n'importe quel ordre. Par exemple, 'a = 1 and b = 2 and c = 3'. Un index (a,b,c) peut être utilisé dans n'importe quel ordre ; l'optimiseur de requêtes MySQL s'en chargera.

#3. Il est préférable de choisir des colonnes avec une haute cardinalité comme index. La formule de cardinalité est count(distinct col)/count(*), qui représente la proportion de champs non répétés. Plus cette proportion est élevée, moins nous scannons d'enregistrements. La cardinalité d'une clé unique est de 1, tandis que celle de champs comme le statut ou le genre peut être de 0 pour de grands volumes de données. Alors, certains se demanderont s'il existe une valeur expérimentale pour cette proportion. L'utilisation varie selon les scénarios, il est donc difficile de la déterminer. Généralement, pour les champs impliqués dans des JOIN, nous demandons une valeur supérieure à 0.1, ce qui signifie qu'en moyenne, une ligne scanne 10 enregistrements.

#4. Les colonnes d'index ne doivent pas participer à des calculs ; gardez les colonnes "propres". Par exemple, 'from_unixtime(create_time) = ’2014-05-29’' ne peut pas utiliser l'index. La raison est simple : l'arbre B+ stocke les valeurs des champs de la table, mais lors de la recherche, il faut appliquer une fonction à tous les éléments pour pouvoir les comparer, ce qui est évidemment trop coûteux. La requête devrait donc être écrite comme : 'create_time = unix_timestamp(’2014-05-29’);'

Démonstration du préfixe le plus à gauche. ```

mysql> select * from s1 where id>3 and name='egon' and email='alex333@oldboy.com' and gender='male'; Empty set (0.39 sec)

mysql> create index idx_no_left_prefix on s1(id,name,email,gender); # Ne suit pas le préfixe le plus à gauche Query OK, 0 rows affected (15.27 sec) Records: 0 Duplicates: 0 Warnings: 0

mysql> select * from s1 where id>3 and name='egon' and email='alex333@oldboy.com' and gender='male'; Empty set (0.43 sec)

mysql> drop index idx_no_left_prefix on s1; Query OK, 0 rows affected (0.16 sec) Records: 0 Duplicates: 0 Warnings: 0

mysql> create index idx_left_prefix on s1(name,email,gender,id); # Suit le préfixe le plus à gauche Query OK, 0 rows affected (15.97 sec) Records: 0 Duplicates: 0 Warnings: 0

mysql> select * from s1 where id>3 and name='egon' and email='alex333@oldboy.com' and gender='male'; Empty set (0.03 sec)


 Création d'index composite, correspondance du préfixe le plus à gauche. Cas où les index ne sont pas utilisés (à noter) :
-------------------------------------------------

like '%xx' select * from tb1 where email like '%cn';
Utilisation de fonctions select * from tb1 where reverse(email) = 'wupeiqi';
OR select * from tb1 where nid = 1 or name = 'seven@live.com';

Particularité : L'index est invalide si l'une des conditions OR ne contient pas de colonne indexée. Les requêtes suivantes utiliseront l'index : select * from tb1 where nid = 1 or name = 'seven'; select * from tb1 where nid = 1 or name = 'seven@live.com' and email = 'alex'
Types de données incohérents Si une colonne est de type chaîne, la condition doit être mise entre guillemets, sinon... select * from tb1 where email = 999;

Les opérateurs de non-égalité sur les index ordinaires ne permettent pas d'utiliser l'index :

!= select * from tb1 where email != 'alex'

Particularité : Si la colonne est une clé primaire, l'index sera utilisé : select * from tb1 where nid != 123
select * from tb1 where email > 'alex'

Particularité : Si la clé primaire ou l'index est de type entier, l'index sera utilisé : select * from tb1 where nid > 123 select * from tb1 where num > 123
La condition de tri est un index, mais les champs sélectionnés ne sont pas des champs d'index, sinon l'index ne sera pas utilisé.
order by select name from s1 order by email desc; Lors du tri par index, si les champs sélectionnés ne sont pas des champs d'index, l'index ne sera pas utilisé. select email from s1 order by email desc; Particularité : Si le tri s'effectue sur la clé primaire, l'index sera quand même utilisé : select * from tb1 order by nid desc;
Préfixe le plus à gauche de l'index composite Si l'index composite est : (name,email) name and email -- Utilise l'index name -- Utilise l'index email -- N'utilise pas l'index
count(1) ou count(colonne) au lieu de count(*) n'a plus de différence dans MySQL.
create index xxxx on tb(title(19)) # Pour les types TEXT, une longueur doit être spécifiée.

Éviter 'select *'
Utiliser count(1) ou count(colonne) au lieu de count(*)
Lors de la création de tables, préférer char à varchar autant que possible.
Les champs de longueur fixe doivent être placés en premier dans l'ordre des champs de la table.
Utiliser des index composites pour remplacer plusieurs index sur colonnes uniques (lors de requêtes avec plusieurs conditions fréquentes).
Essayer d'utiliser des index courts.
Utiliser des jointures (JOIN) pour remplacer les sous-requêtes.
Lors des jointures, s'assurer que les types des conditions sont cohérents.
Les champs avec une faible cardinalité (peu de répétitions) ne conviennent pas à la création d'index, par exemple, le genre n'est pas approprié.


Étapes de base pour l'optimisation des requêtes lentes
======================================================

Vérifier d'abord si la requête est réellement lente, en utilisant SQL_NO_CACHE si nécessaire.
Pour les requêtes sur une seule table avec des conditions WHERE, sélectionnez la table qui renvoie le minimum d'enregistrements. Cela signifie appliquer toutes les conditions WHERE aux tables et commencer par celle qui renvoie le moins d'enregistrements. Pour chaque champ de la table, effectuer une requête individuelle pour voir lequel a la plus haute cardinalité.
Utiliser EXPLAIN pour vérifier le plan d'exécution et s'assurer qu'il correspond à l'attente de l'étape 1 (en commençant par la table qui verrouille le moins d'enregistrements).
Pour les requêtes de type ORDER BY LIMIT, privilégier la table de tri en premier.
Comprendre le contexte d'utilisation métier.
Lors de l'ajout d'index, se référer aux principes fondamentaux de création d'index.
Observer les résultats, et si les attentes ne sont pas satisfaites, analyser à nouveau à partir de l'étape 0.

Étiquettes: MySQL index b+ tree SQL performance tuning

Publié le 14 juin à 16h03

L'Atelier Monstre