par Guillaume Lelarge.

Index lents, partie II


La section précédente a expliqué comment gagner en performance à partir d'un index existant en changeant l'ordre de ses colonnes mais l'exemple portait seulement sur deux requêtes. Néanmoins, changer un index pourrait affecter toutes les requêtes sur la table indexée. Cette section explique comment les bases de données choisissent un index et démontre les effets de bord possibles dû à un changement dans la définition d'un index.

L'index EMPLOYE_PK adopté améliore les performances de toutes les requêtes qui cherchent par société seulement. Il est aussi utilisable pour toutes les requêtes qui cherchent par ID_SUPPLEMENTAIRE et par tout autre critère de recherche supplémentaire. Cela signifie que l'index devient utilisable pour les requêtes qui utilisaient un autre index pour une autre partie de la clause where. Dans ce cas, si plusieurs chemins d'accès sont possibles, c'est à l'optimiseur de choisir le meilleur.

L'optimiseur de requêtes

L'optimiseur de requêtes, ou le planificateur de requêtes, est le composant de la base de données qui transforme une requête SQL en un plan d'exécution. Ce processus est aussi connu sous le nom de compilation ou analyse. Il existe deux types distincts d'optimiseurs.

Un optimiseur basé sur le coût (CBO) génère un grand nombre de plans d'exécution et calcule un coût pour chaque plan. Le calcul du coût est basé sur les opérations utilisées et les estimations de nombres de lignes. À la fin, la valeur du coût sert d'information de base pour choisir le « meilleur » plan d'exécution.

Un optimiseur basé sur des règles (RBO) génère le plan d'exécution utilisant un ensemble de règles codées en dur. Ce type d'optimiseur est moins flexible et très peu utilisé de nos jours.

Changer un index peut aussi avoir des effets de bord déplaisants. Dans notre exemple, l'application du répertoire téléphonique est devenue très lente depuis la fusion. La première analyse a identifié la requête suivante comme cause principale des lenteurs.

SELECT prenom, nom, id_supplementaire, numero_telephone
  FROM employes
 WHERE nom = 'WINAND'
   AND id_supplementaire = 30

Le plan d'exécution est le suivant :

Exemple 2.1 Plan d'exécution avec l'index de clé primaire revu

----------------------------------------------------------------
|Id |Operation                   | Name         | Rows | Cost |
---------------------------------------------------------------
| 0 |SELECT STATEMENT            |              |    1 |   30 |
|*1 | TABLE ACCESS BY INDEX ROWID| EMPLOYES     |    1 |   30 |
|*2 |  INDEX RANGE SCAN          | EMPLOYES_PK  |   40 |    2 |
---------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
  1 - filter("NOM"='WINAND')
  2 - access("ID_SUPPLEMENTAIRE"=30)

Le plan d'exécution utilise un index. Il a un coût global de 30. Pour l'instant, tout va bien. Néanmoins, il est étonnant de voir qu'il utilise l'index que nous venons de changer. C'est une raison suffisante pour suspecter que le changement d'index a causé le problème de performances, tout particulièrement si on se rappelle de l'ancienne définition de l'index. Elle commençait avec la colonne ID_EMPLOYE qui ne fait pas du tout partie de la clause where. La requête ne pouvait pas utiliser cet index avant.

Pour aller plus loin dans l'analyse, il serait bon de comparer le plan d'exécution avant et après changement. Pour obtenir le plan d'exécution original, nous pourrions remettre en place l'ancien index. Néanmoins, la plupart des bases de données offre un moyen simple pour empêcher l'utilisation d'un index pour une requête particulière. L'exemple suivant utilise un marqueur pour l'optimiseur Oracle (appelé « hint ») pour gérer ce cas.

SELECT /*+ NO_INDEX(EMPLOYES EMPLOYE_PK) */ 
       prenom, nom, id_supplementaire, numero_telephone
  FROM employes
 WHERE nom  = 'WINAND'
   AND id_supplementaire = 30

Le plan d'exécution qui était utilisé avant la modification de l'index n'utilisait pas d'index du tout :

----------------------------------------------------
| Id | Operation         | Name      | Rows | Cost |
----------------------------------------------------
|  0 | SELECT STATEMENT  |           |    1 |  477 |
|* 1 |  TABLE ACCESS FULL| EMPLOYES  |    1 |  477 |
----------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   1 - filter("NOM"='WINAND' AND "ID_SUPPLEMENTAIRE"=30)

Même si l'opération TABLE ACCESS FULL doit lire et traiter la table entière, elle semble plus rapide qu'utiliser l'index dans ce cas. Ceci est plutôt inhabituel car la requête ne récupère qu'une ligne. Utiliser un index pour trouver une seule ligne devrait être bien plus rapide qu'un parcours de table complet. Mais cela ne se passe pas ainsi ici. L'index semble être lent.

Dans ce cas, il est préférable de vérifier chaque étape du plan problé­matique. La première étape est l'opération INDEX RANGE SCAN sur l'index EMPLOYEE_PK. Cet index ne couvre pas la colonne NOM. INDEX RANGE SCAN peut seulement traiter le filtre sur ID_SUPPLEMENTAIRE ; la base de données Oracle affiche cette information sur le deuxième élément dans la partie « Predicate Information » du plan d'exécution. Vous pouvez donc voir les conditions appliquées à chaque opération.

Astuce

L'Annexe A, « Plans d'exécution » explique comment trouver la partie « Predicate Information » pour chaque base de données.

Le INDEX RANGE SCAN avec l'identifiant d'opération 2 (Exemple 2.1) applique seulement le filtre ID_SUPPLEMENTAIRE=30. Cela signifie qu'il parcourt l'arbre de l'index pour trouver le premier enregistrement pour lequel ID_SUPPLEMENTAIRE vaut 30. Ensuite, il suit la chaîne de nœuds feuilles pour trouver tous les enregistrements pour cette société. Le résultat de l'opération INDEX RANGE SCAN est une liste d'identifiants de lignes (généralement appelés ROWID) qui remplissent la condition ID_SUPPLEMENTAIRE : suivant la taille de la société, cela peut aller de quelques-uns à plusieurs centaines.

La prochaine étape est l'opération TABLE ACCESS BY INDEX ROWID. Elle uti­lise les ROWID trouvés à l'étape précédente pour récupérer les lignes, toutes colonnes comprises, de la table. Une fois que la colonne NOM est disponible, la base de données peut évaluer le reste de la clause where. Cela signifie que la base de données doit récupérer toutes les lignes de la table pour lesquelles la clause ID_SUPPLEMENTAIRE=30 est vraie avant d'appliquer le filtre NOM.

La durée d'exécution de la requête ne dépend pas du nombre de lignes du résultat mais du nombre d'employés dans la société visée. Si cette société a peu d'employés, l'opération INDEX RANGE SCAN donnera de meilleures performances. Néanmoins, un TABLE ACCESS FULL peut se révéler plus rapide sur une grosse société car il peut lire dans ce cas de larges parties de la table en une fois (voir « Parcours complet de table »).

La requête est lente parce que la recherche dans l'index renvoie de nombreux ROWID, un pour chaque employé de la société originale, et la base de données doit les récupérer un par un. C'est la combinaison parfaite des deux ingrédients qui rend l'index lent : la base de données lit un grand nombre d'éléments dans l'index et doit récupérer chaque ligne séparément.

Choisir le meilleur plan d'exécution dépend aussi de la distribution des données dans la table. Du coup, l'optimiseur utilise les statistiques sur le contenu de la base de données. Dans notre exemple, un histogramme contenant la distribution des employés par société est utilisé. Cela permet à l'optimiseur d'estimer le nombre de lignes renvoyées à partir de la recherche de l'index. Le résultat est utilisé pour le calcul du coût.

Statistiques

Un optimiseur basé sur les coûts utilise les statistiques sur les tables, colonnes et index. La plupart des statistiques sont récupérées au niveau des colonnes : le nombre de valeurs distinctes, la plus petite et la plus grande valeur (intervalle de données), le nombre de valeurs NULL et l'histogramme de la colonne (distribution des données). La valeur statistique la plus importante pour une table est sa volumétrie (en lignes et en blocs).

Les statistiques les plus importantes pour un index sont la profondeur de l'arbre, le nombre de nœuds feuilles, le nombre de clés distinctes et le facteur d'ordonnancement (voir le Chapitre 5, « Regrouper les données »).

L'optimiseur utilise ces valeurs pour estimer la sélectivité des prédicats de la clause where.

Si aucune statistique n'est disponible, par exemple parce qu'elles ont été supprimées, l'optimiseur utilise des valeurs par défaut. Les statistiques par défaut de la base de données Oracle font référence à un petit index avec une sélectivité moyenne. Elles amènent à supposer qu'un INDEX RANGE SCAN renverra 40 lignes. Le plan d'exécution affiche cette estimation dans la colonne « Rows » (encore une fois, voir l'Exemple 2.1). Évidemment, c'est très fortement sous-estimé car 1000 employés travaillent pour cette société.

Si nous fournissons des statistiques correctes, l'optimiseur fait un meilleur travail. Le plan d'exécution suivant montre la nouvelle estimation : 1000 lignes pour l'INDEX RANGE SCAN. En conséquence, il calcule un coût supérieur pour les accès suivant à la table.

---------------------------------------------------------------
|Id |Operation                   | Name         | Rows | Cost |
---------------------------------------------------------------
| 0 |SELECT STATEMENT            |              |    1 |  680 |
|*1 | TABLE ACCESS BY INDEX ROWID| EMPLOYES     |    1 |  680 |
|*2 |  INDEX RANGE SCAN          | EMPLOYES_PK  | 1000 |    4 |
---------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
  1 - filter("NOM"='WINAND')
  2 - access("ID_SUPPLEMENTAIRE"=30)

Un coût de 680 est même plus important que le coût pour le plan d'exécution utilisant l'opération FULL TABLE SCAN (477). Du coup, l'optimiseur préférera automatiquement l'opération FULL TABLE SCAN.

Cet exemple d'un index lent ne devrait pas cacher le fait qu'une bonne indexation est la meilleure solution. Bien sûr, chercher le nom est très bien supporté par un index sur NOM :

CREATE INDEX nom_emp ON employes (nom);

En utilisant le nouvel index, l'optimiseur calcule un coût de 3 :

Exemple 2.2 Plan d'exécution avec un index dédié

--------------------------------------------------------------
| Id | Operation                   | Name      | Rows | Cost |
--------------------------------------------------------------
|  0 | SELECT STATEMENT            |           |    1 |    3 |
|* 1 |  TABLE ACCESS BY INDEX ROWID| EMPLOYES  |    1 |    3 |
|* 2 |   INDEX RANGE SCAN          | NOM_EMP   |    1 |    1 |
--------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   1 - filter("ID_SUPPLEMENTAIRE"=30)
   2 - access("NOM"='WINAND')

L'accès à l'index ramène, suivant les estimations de l'optimiseur, une seule ligne. Du coup, la base de données doit récupérer uniquement cette ligne dans la table : ceci sera à coup sûr plus rapide qu'une opération FULL TABLE SCAN. Un index correctement défini est toujours meilleur qu'un parcours complet de table.

Les deux plans d'exécution provenant de l'Exemple 2.1 et de l'Exemple 2.2 sont pratiquement identiques. La base de données réalise les mêmes opérations et l'optimiseur calcule des coûts similaires. Néanmoins, le deuxième plan est bien plus performant. L'efficacité d'une opération INDEX RANGE SCAN peut varier dans un grand intervalle, tout spécialement s'il est suivi d'un accès à la table. Utiliser un index ne signifie pas automatiquement qu'une requête est exécutée de la meilleure façon qu'il soit.

À propos de l'auteur

Photo de Markus Winand

Markus Winand teaches efficient SQL—inhouse and online. He minimizes the development time using modern SQL and optimizes the runtime with smart indexing—for that he also published the book SQL Performance Explained.

“Use The Index, Luke!” by Markus Winand and translated by Guillaume Lelarge is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 Unported License.
Mentions légales | Contact | NO WARRANTY | Marque déposée | Privacy | CC-BY-NC-ND 3.0 license