par Guillaume Lelarge.

Index lents, partie I


Malgré l'efficacité du parcours de l'arbre, il existe des cas où une recherche via l'index ne sera pas aussi rapide que souhaité. Cette contradiction est la raison d'être du mythe de l'index dégénéré. Le mythe affirme qu'une reconstruction d'index est la solution miracle. L'Annexe B« Myth Directory » couvre ce mythe et d'autres en détails. Pour l'instant, sachez que la reconstruction d'un index n'améliore pas les performances au final. La vraie raison pour laquelle des requêtes basiques peuvent être lentes, même en utilisant un index, peut se trouver sur les bases des sections précédentes.

Le premier ingrédient rendant une recherche lente via l'index est la chaîne de nœuds feuilles. Considérez de nouveau la recherche de la valeur 57 dans la Figure 1.3. Il existe deux entrées correspondantes dans l'index. Au moins deux entrées sont identiques, pour être plus précis : le nœud feuille suivant pourrait contenir de nouvelles entrées 57. La base de données doit lire le prochain nœud feuille pour savoir s'il existe des entrées correspondantes. Cela signifie qu'une recherche d'index doit non seulement faire le parcours de l'arbre, mais il doit aussi suivre la chaîne des nœuds feuilles.

Le deuxième ingrédient pour une recherche d'index lente est d'avoir à accéder à la table. Même un nœud feuille simple peut contenir plusieurs fois la valeur recherchée, parfois même des centaines de fois. Les données correspondantes de la table sont généralement réparties sur un grand nombre de blocs (voir la Figure 1.1« Nœuds feuilles de l'index et données de la table »). Cela signifie qu'il y a un accès supplémentaire à la table pour chaque valeur trouvée dans l'index.

Une recherche dans un index suit trois étapes : (1) le parcours de l'arbre ; (2) la suite de la chaîne de nœuds feuilles ; (3) la récupération des données de la table. Le parcours de l'arbre est la seule étape qui accède à un nombre limité de blocs, qui correspond à la profondeur de l'index. Les deux autres étapes doivent avoir accès à de nombreux blocs. Elles sont la cause des lenteurs lors d'une recherche par index.

L'origine du mythe des index lents est la croyance erronée qu'une recherche d'index ne fait que parcourir l'arbre, et donc l'idée qu'un index lent est causé par un arbre « cassé » ou « non équilibré ». En fait, vous pouvez demander à la plupart des bases de données comment elles utilisent un index. La base de données Oracle est assez verbeuse sur cet aspect. Elle a trois opérations distinctes qui décrivent une recherche basique par index :

INDEX UNIQUE SCAN

Un INDEX UNIQUE SCAN réalise seulement le parcours de l'arbre. La base de données Oracle utilise cette opération sur une contrainte unique qui assure que le critère de recherche correspondra à une seule entrée.

INDEX RANGE SCAN

Un INDEX RANGE SCAN fait le parcours de l'arbre et suit la chaîne de nœuds feuilles pour trouver toutes les entrées correspondantes. C'est l'opération la plus sûre si le critère peut se révéler vrai pour plusieurs entrées.

TABLE ACCESS BY INDEX ROWID

Une opération TABLE ACCESS BY INDEX ROWID récupère la ligne de la table. Cette opération est (souvent) réalisée pour chaque enregistrement récupéré à partir d'un précédent parcours d'index.

Le point important est qu'un INDEX RANGE SCAN peut potentiellement lire une large part d'un index. S'il existe plus d'un accès de table pour chaque ligne, la requête peut devenir lente même en utilisant un index.

À 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