par Guillaume Lelarge.

Parcours d'index seul : éviter l'accès à la table


Le parcours d'index seul est une des optimisations les plus puissantes. Non seulement cela évite d'accéder à la table pour évaluer la clause where mais cela évite aussi complètement d'accéder à la table si la base de données peut trouver les colonnes sélectionnées dans l'index.

Pour couvrir une requête entière, un index doit contenir toutes les colonnes de la requête SQL, en particulier celles de la clause select comme indiqué dans l'exemple suivant :

CREATE INDEX ventes_sous_eur
    ON ventes
     ( id_supplementaire, valeur_eur );

SELECT SUM(valeur_eur)
  FROM ventes
 WHERE id_supplementaire = ?;

Bien sûr, indexer la clause where est prioritaire par rapport aux autres clauses. La colonne ID_SUPPLEMENTAIRE est du coup en première position pour que l'index soit utilisable en tant que prédicat d'accès.

Le plan d'exécution montre que l'index est parcouru sans faire appel à un parcours de table (pas d'opération TABLE ACCESS BY INDEX ROWID).

------------------------------------------------------------
| Id  | Operation         | Name            |  Rows | Cost |
------------------------------------------------------------
|   0 | SELECT STATEMENT  |                 |     1 |  104 |
|   1 |  SORT AGGREGATE   |                 |     1 |      |
|*  2 |   INDEX RANGE SCAN| VENTES_SOUS_EUR | 40388 |  104 |
------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   2 - access("SUBSIDIARY_ID"=TO_NUMBER(:A))

L'index couvre la requête complète, donc il est aussi appelé index couvrant.

Remarque

Si un index empêche un accès à la table, il est aussi appelé un index couvrant.

Néanmoins, le terme est ambigu car il pourrait passer pour une propriété de l'index. L'expression « parcours d'index seul » suggère à raison qu'il s'agit d'une opération dans un plan d'exécution.

L'index a une copie de la colonne VALEUR_EUR, donc la base de données peut utiliser la valeur stockée dans l'index. Accéder à la table n'est pas requis car l'index a toutes les informations pour satisfaire la requête.

Un parcours d'index seul peut améliorer très fortement les performances. Regardez l'estimation du nombre de lignes dans le plan d'exécution : l'optimiseur s'attend à agréger plus de 40 000 lignes. Cela signifie que le parcours d'index seul a empêché la lecture de 40 000 blocs de table, si chaque ligne se trouve dans un bloc différent de la table. Si l'index a un bon facteur de regroupement, autrement dit si les lignes respectives sont bien regroupées dans un petit nombre de blocs de la table, l'avantage du parcours d'index seul sera moindre.

En dehors du facteur de regroupement, le nombre de lignes sélectionnées limite le gain potentiel de performances d'un parcours d'index seul. Si vous sélectionnez une seule ligne par exemple, vous pouvez seulement économiser un accès à la table. Comme le parcours d'arbre a besoin de récupérer quelques blocs, l'accès sauvé à la table peut devenir négligeable.

Important

L'avantage en termes de performance d'un parcours d'index seul dépend du nombre de lignes accédées et du facteur de regroupement de l'index.

Le parcours d'index seul est une stratégie d'indexation agressive. Il ne faut pas concevoir un index pour un parcours d'index seul sur de simples suppositions car il utilise plus de mémoire et augmente l'effort de maintenance lors des requêtes update. Voir le Chapitre 8, « Modifier les données ». En pratique, vous devez tout d'abord indexer sans considérer la clause select et étendre l'index seulement si cela se révèle nécessaire.

Les parcours d'index seul peuvent aussi causer de mauvaises surprises, par exemple si nous limitons la requête aux ventes récentes :

SELECT SUM(valeur_eur)
  FROM ventes
 WHERE id_supplementaire = ?
   AND date_vente > ?;

Sans regarder le plan d'exécution, on pourrait s'attendre à ce que la requête soit rapide car elle sélectionne peu de lignes. Néanmoins, la clause where fait référence à une colonne qui ne se trouve pas dans l'index pour que la base de données accède à la table pour charger cette colonne.

---------------------------------------------------------------
|Id | Operation                    | Name       | Rows  |Cost |
---------------------------------------------------------------
| 0 | SELECT STATEMENT             |            |     1 | 371 |
| 1 |  SORT AGGREGATE              |            |     1 |     |
|*2 |   TABLE ACCESS BY INDEX ROWID| VENTES     |  2019 | 371 |
|*3 |    INDEX RANGE SCAN          | DATE_VENTE | 10541 |  30 |
---------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   2 - filter("ID_SUPPLEMENTAIRE"=TO_NUMBER(:A))
   3 - access("DATE_VENTE">:B)

L'accès à la table augmente le temps de réponse bien que la requête sélectionne moins de lignes. Le facteur adéquat n'est pas le nombre de lignes que la requête ramène mais le nombre de lignes que la requête doit inspecter pour trouver les bonnes lignes.

Attention

Étendre la clause where peut causer un comportement illogique au niveau des performances. Vérifiez le plan d'exécution avant d'étendre les requêtes.

Si un index ne peut plus être utilisé pour un parcours d'index seul, l'optimiseur choisira le prochain meilleur plan d'exécution. Autrement dit, il pourrait choisir un plan d'exécution complètement différent ou, comme ci-dessus, un plan similaire avec un autre index. Dans notre cas, il utilise un index sur DATE_VENTE, qui date du chapitre précédent.

Du point de vue de l'optimiseur, cet index a deux avantages sur VENTES_SOUS_EUR. L'optimiseur pense que le filtre sur DATE_VENTE est plus sélectif que celui sur ID_SUPPLEMENTAIRE. Vous pouvez vous en rendre compte en regardant la colonne « Rows » des deux derniers plans d'exécutions (environ 10 000 pour l'un et 40 000 pour l'autre). Néanmoins, ces estimations sont plutôt arbitraires car la requête utilise les paramètres liés. La condition DATE_VENTE pourrait sélectionner la table entière si un utilisateur fournit la date de la première vente.

Le deuxième avantage de l'index sur DATE_VENTE est son meilleur facteur de regroupement. Cette raison est valide car la table VENTES grossit seulement chronologiquement. Les nouvelles lignes sont toujours ajoutées à la fin de la table, tant qu'aucune ligne n'a été supprimée. L'ordre de la table correspond donc à l'ordre de l'index car les deux sont grossièrement triées chronologiquement. L'index a un bon facteur de regroupement.

Lors de l'utilisation d'un index doté d'un bon facteur de regroupement, les lignes sélectionnées sont stockées proches les unes des autres pour que la base de données n'ait besoin de lire que quelques blocs de la table pour obtenir toutes les lignes. En utilisant cet index, la requête pourrait être assez rapide sans même utiliser un parcours d'index seul. Dans ce cas, nous devons supprimer les colonnes inutiles de l'autre index.

Remarque

Certains index ont automatiquement un bon facteur de regroupe­ment. L'avantage des parcours d'index seul est minimal pour eux.

Dans cet exemple particulier, c'était une coïncidence heureuse. Le nouveau filtre sur DATE_VENTE a non seulement empêché un parcours d'index seul mais a aussi ouvert un nouveau chemin d'accès en même temps. Du coup, l'optimiseur était capable de limiter l'impact sur les performances de ce changement. Néanmoins, il est aussi possible d'empêcher un parcours d'index seul en ajoutant des colonnes sur d'autres clauses. Ajouter une colonne à la clause select ne peut jamais ouvrir un nouveau chemin d'accès, ce qui limiterait l'impact de la perte du parcours d'index seul.

Astuce

Maintenez vos parcours d'index seul.

Ajoutez des commentaires pour vous rappeler le parcours d'index seul et faites références à cette page pour que tout le monde puisse en prendre connaissance.

Les index fonctionnels peuvent aussi causer de mauvaises suprises relatives aux parcours d'index seul. Un index sur UPPER(nom) ne peut pas être utilisé pour un parcours d'index seul lors de la sélection de la colonne NOM. Dans la section précédente, nous aurions dû indexer la colonne NOM elle-même pour supporter le filtre LIKE et lui permettre d'être utilisé pour un parcours d'index seul lors de la sélection de la colonne NOM.

Astuce

Avoir toujours comme but d'indexer la donnée originale car elle est souvent l'information la plus utile à placer dans un index.

Évitez les index fonctionnels pour les expressions qui ne peuvent pas être utilisées comme prédicats d'accès.

Agréger des requêtes comme celle ci-dessus est excellent pour les parcours d'index seul. Elles récupèrent plusieurs lignes mais peu de colonnes, rendant un petit index suffisant pour supporter un parcours d'index seul. Plus vous demandez de colonnes, plus vous devez ajouter de colonnes à l'index qui servira au parcours d'index seul. En tant que développeur, vous devez du coup seulement sélectionner les colonnes dont vous avez réellement besoin.

Astuce

Évitez select * et récupérez seulement les colonnes dont vous avez besoin.

Sans compter qu'indexer un grand nombre de lignes demande beaucoup d'espace disque, vous pouvez aussi atteindre les limites de votre base de données. La plupart des bases de données impose des limites assez rigides sur le nombre de colonnes par index et sur la taille totale d'une entrée d'un index. Cela signifie que vous ne pouvez pas indexer un nombre arbitraire de colonnes, pas plus que des colonnes arbitrairement longues. L'aperçu suivant liste les limitations les plus importantes. Néanmoins, il existe des index qui couvrent la table entière comme nous le voyons dans la prochaine section.

DB2

DB2 V8 limite un index à 64 colonnes, avec une longueur maximale de la clé à 2000 octets, réduits par la surcharge qui dépend du nombre et du type des colonnes.

MySQL

MySQL avec InnoDB limite la longueur totale des clés (toutes les colonnes) à 3072 octets. De plus, la longueur de chaque colonne est limitée à 767 octets si l'option innodb_large_prefix n'est pas activée ou si les formats ligne autre que DYNAMIC ou COMPRESSED sont utilisés. C'était la valeur par défaut jusqu'à la version 5.6 de MySQL. Les index MyISAM sont limités à 16 colonnes et une longueur maximale de clés de 1000 octets.

MySQL dispose d'une fonctionnalité unique appelée « indexation de préfixe » (quelque fois aussi appelé « indexation partielle »). Cette fonctionnalité permet de n'indexer que les quelques premiers caractères d'une colonne, donc cela n'a rien à voir avec les index partiels décrits dans Chapitre 2. Si vous indexez une colonne qui dépasse la longueur maximale autorisée (767, 1000 ou 3072 octets comme décrit ci-dessus), MySQL pourrait, suivant le mode SQL et le format ligne, tronquer la colonne. Dans ce cas, l'instruction create index réussit avec le message d'avertissement “Specified key was too long; max key length is … bytes” (en français, « La clé spécifiée était trop longue ; la longueur maximale d'une clé est de … octets »). Ceci signifie que l'index n'a plus une copie complète de la colonne. Sélectionner la colonne empêche un parcours uniquement de l'index (similaire aux index fonctionnels).

Vous pouvez utiliser l'indexation du préfixe de MySQL explicitement pour empêcher le dépassement de la limite de la longueur de la clé si vous obtenez le message d'erreur « Specified key was too long; max key length is … bytes. » (en français, « La clé spécifiée était trop longue ; la longueur maximale d'une clé est de … octets »). L'exemple suivant crée un index sur les dix premiers caractères de la colonne NOM.

CREATE INDEX .. ON employes (nom(10));
Oracle

La longueur maximale d'une clé d'index dépend de la taille du bloc et des paramètres de stockage de l'index (75% de la taille d'un bloc de la base moins l'en-tête). Un index B-tree est limité à 32 colonnes.

Lors de l'utilisation d'Oracle 11g avec toutes les valeurs par défaut (donc des blocs de 8 Ko), la longueur maximale de la clé d'un index est de 6398 octets. Dépasser cette limite renvoie le message d'erreur « ORA-01450: maximum key length (6398) exceeded. »

PostgreSQL

La base de données PostgreSQL supporte les parcours d'index seul depuis la version 9.2.

La longueur d'une clé dans un index B-tree est limitée à 2713 octets (codé en dur, approximativement BLCKSZ/3). Le message d'erreur respectif « index row size ... exceeds btree maximum, 2713 » apparaît seulement lors de l'exécution d'un insert ou d'un update qui dépasse la limite. Les index B-tree peuvent contenir jusqu'à 32 colonnes.

SQL Server

SQL Server limite la longueur de la clé à 900 octets et à 16 colonnes. Néanmoins, SQL Server dispose d'une fonctionnalité qui vous permet d'ajouter arbitrairement des colonnes longues à un index dans le seul but de supporter les parcours d'index seul. Pour cela, SQL Server fait la distinction entre colonnes clés et colonnes autres.

Les colonnes clés sont des colonnes d'index comme discuté auparavant. Les autres colonnes sont des colonnes supplémentaires qui sont simplement stockées dans les nœuds feuilles d'un index. Ces autres colonnes peuvent avoir toutes tailles mais ne peuvent pas être utilisées comme prédicats d'accès (prédicats de recherche).

Ces autres colonnes sont définies avec le mot-clé include de la commande create index :

 CREATE INDEX empsousnommaj
     ON employes
       (id_supplementaire, nom)
INCLUDE(numero_telephone, prenom);

Astuce

Les requêtes qui ne sélectionnent aucune colonne de table sont souvent exécutées avec des parcours d'index seul.

Pouvez-vous trouver un exemple intéressant ?

À 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.

Livre de Markus

Couverture du livre « SQL : Au cœur des performances »

L'essence de SQL tuning dans 200 pages.

Acheter de Markus
(Livre de poche et PDF)

Achetez chez Amazon
(Seulement en poche)

“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