par Guillaume Lelarge.

Fusion d'index


C'est une des questions les plus fréquentes sur l'indexation : est-il préférable de créer un index pour chaque colonne ou un index seul pour toutes les colonnes d'une clause where ? La réponse est très simple dans la plupart des cas : un index avec plusieurs colonnes est mieux qu'un index concaténé ou composite. « Index concaténés » les explique en détail.

Néanmoins, pour certaines requêtes, un index seul ne peut pas faire un travail parfait, quelle que soit la définition de l'index. Par exemple, les requêtes avec au moins deux conditions différentes d'intervalle comme dans l'exemple suivant :

SELECT prenom, nom, date_de_naissance
  FROM employes
 WHERE UPPER(nom)        < ? 
   AND date_de_naissance < ?

Il est impossible de définir un index B-tree supportant cette requête sans passer par des prédicats filtres. L'explication est simple : souvenez-vous qu'un index est une liste chaînée.

Si vous définissez l'index comme UPPER(NOM), DATE_DE_NAISSANCE (dans cet ordre), la liste commence avec A et se termine avec Z. La date de naissance n'est considérée que si deux employés ont le même nom. Si vous définissez l'index dans l'ordre inverse, il commencera avec les employés les plus âgés et finira avec les plus jeunes. Dans ce cas, les noms auront un impact moindre sur l'ordre de tri.

Peu importe comment vous personnalisez la définition de l'index, les enregistrements sont toujours rangés dans une chaîne. À un bout, vous avez les plus petits enregistrements et à l'autre les plus gros. Du coup, un index peut seulement supporter une condition d'intervalle comme prédicat d'accès. Supporter deux conditions d'intervalles indépendantes nécessiterait un deuxième axe, comme par exemple un échiquier. Mais un index n'est pas comme un échiquier. Il s'agit d'une liste chaînée.

Vous pouvez bien sûr accepter le prédicat filtre et néanmoins utiliser un index multi-colonnes. C'est la meilleure solution dans de nombreux cas de toute façon. La définition de l'index doit alors mentionner en premier la colonne la plus sélective pour qu'il soit utilisable avec un prédicat accès. Cela pourrait être à l'origine du mythe « la plus sélective d'abord » mais cette règle n'est vraie que si vous pouvez éviter un prédicat filtre.

L'autre option est d'utiliser deux index séparés, un pour chaque colonne. La base de données doit parcourir les deux index, puis combiner leur résultat. La recherche d'index dupliqué demande déjà plus d'efforts car la base de données doit parcourir deux arbres d'index. De plus, la base de données a besoin de beaucoup de mémoire et de temps processeur pour combiner les résultats intermédiaires.

Remarque

Parcourir un index est plus rapide qu'en parcourir deux.

Les bases de données utilisent deux méthodes pour combiner les index. Tout d'abord, il y a la jointure d'index. Le Chapitre 4« Opération de jointure » explique les algorithmes en question en détail. La deuxième approche revient à utiliser des fonctionnalités du monde des entrepôts de données.

Les logiciels d'entrepôt de données sont le berceau de toutes les requêtes personnalisées. Il suffit de quelques clics pour combiner des conditions arbitraires dans la requête de votre choix. Il est impossible de prédire les combinaisons de colonnes qui pourraient apparaître dans la clause where et cela rend l'indexation, tel qu'expliqué jusqu'ici, pratiquement impossible.

Les entrepôts de données ont un type d'index particulier pour résoudre ce problème : les index bitmap. L'avantage des index bitmap est qu'ils peuvent être combinés plutôt facilement. Cela signifie que vous obtenez des performances décentes lors de l'indexation individuelle de chaque colonne. Si vous connaissez la requête à l'avance, vous pouvez créer un index B-tree multi-colonnes très spécialisé, il sera toujours plus rapide que de combiner plusieurs index bitmap.

La plus grande faiblesse des index bitmap est la scalabilité ridicule face aux insert, update et delete. Les opérations d'écritures concurrentes sont virtuellement impossibles. Ce n'est pas un problème dans un entrepôt car les processus de chargement sont planifiés les uns après les autres. Dans les applications en ligne, les index bitmap sont pratiquement inutiles.

Important

Les index bitmap sont pratiquement inutilisables pour les traite­ments en ligne (OLTP).

Beaucoup de bases de données proposent une solution hybride entre les index B-tree et les index bitmap. En l'absence d'un meilleur chemin d'accès, ils convertissent les résultats du parcours de plusieurs index B-tree en des structures bitmap en mémoire. Elles peuvent être combinées efficacement. Les structures bitmap sont temporaires car annulées dès l'exécution de la requête terminée. Cela permet d'éviter le problème de la scalabilité. L’inconvénient est que cela utilise beaucoup de mémoire et de temps processeur. En fait, cette méthode est un acte désespéré de l'optimiseur pour obtenir de meilleures performances.

À 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