par Guillaume Lelarge.

Index concaténés


Même si la base de données crée automatiquement l'index pour la clé primaire, il est toujours possible de réaliser des améliorations manuelles si la clé contient plusieurs colonnes. Dans ce cas, la base de données crée un index sur toutes les colonnes de la clé primaire, ce qu'on appelle un index concaténé (aussi connu sous le nom d'index multi-colonnes, composite ou combiné). Notez que l'ordre des colonnes d'un index concaténé a un grand impact sur ses capacités à être utilisé. Donc l'ordre des colonnes doit être choisi avec attention.

Pour les besoins de la démonstration, supposons qu'il y ait une fusion de sociétés. Les employés de l'autre société sont ajoutés à notre table EMPLOYES qui devient alors dix fois plus grosses. Il y a ici un problème : la colonne ID_EMPLOYE n'est pas unique entre les deux sociétés. Nous avons besoin d'étendre la clé primaire par un identifiant supplémentaire. Du coup, la nouvelle clé primaire a deux colonnes : la colonne ID_EMPLOYE comme auparavant et la colonne ID_SUPPLEMENTAIRE pour rétablir l'unicité.

L'index pour la nouvelle clé primaire est donc défini de la façon suivante :

CREATE UNIQUE INDEX employe_pk 
    ON employes (id_employe, id_supplementaire);

Une requête pour un employé en particulier doit prendre en compte la clé primaire complète. Autrement dit, la colonne ID_SUPPLEMENTAIRE doit aussi être utilisée :

SELECT prenom, nom
  FROM employes
 WHERE id_employe        = 123
   AND id_supplementaire = 30
MySQL

+----+----------+-------+---------+---------+------+-------+
| id | table    | type  | key     | key_len | rows | Extra |
+----+----------+-------+---------+---------+------+-------+
|  1 | employes | const | PRIMARY | 10      |    1 |       |
+----+----------+-------+---------+---------+------+-------+

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

Predicate Information (identified by operation id):
---------------------------------------------------
   2 - access("ID_EMPLOYE"=123 AND "ID_SUPPLEMENTAIRE"=30)
PostgreSQL

                QUERY PLAN
-------------------------------------------
 Index Scan using employes_pk on employes
   (cost=0.00..8.27 rows=1 width=14)
   Index Cond: (id_employe = 123::numeric
             and id_supplementaire = 30::numeric)

SQL Server

|--Nested Loops(Inner Join)
   |--Index Seek(OBJECT:employes_pk,
   |               SEEK:id_employe=@ AND id_supplementaire=@2
   |            ORDERED FORWARD)
   |--RID Lookup(OBJECT:employes,
                   SEEK:Bmk1000=Bmk1000
                 LOOKUP ORDERED FORWARD)

Quand une requête utilise la clé primaire complète, la base de données peut utiliser une opération INDEX UNIQUE SCAN, quel que soit le nombre de colonnes de l'index. Mais qu'arrive-t-il quand seulement une des colonnes clés, par exemple, est utilisée pour rechercher tous les employés d'une société ?

SELECT prenom, nom
  FROM employes
 WHERE id_supplementaire = 20
MySQL

+----+----------+------+------+-------+-------------+
| id | table    | type | key  | rows  | Extra       |
+----+----------+------+------+-------+-------------+
|  1 | employes | ALL  | NULL | 11000 | Using where |
+----+----------+------+------+-------+-------------+

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

Predicate Information (identified by operation id):
---------------------------------------------------
   1 - filter("ID_SUPPLEMENTAIRE"=20)
PostgreSQL

                QUERY PLAN
-------------------------------------------
 Seq Scan on employes
   (cost=0.00..1398.50 rows=1070 width=14)
   Filter: (id_supplementaire = 2::numeric)

SQL Server

|--Table Scan(OBJECT:employes,
               WHERE:id_supplementaire=30)

Le plan d'exécution révèle que la base de données ne doit pas utiliser l'index. À la place, il réalise un FULL TABLE SCAN. En résultat, la base de données lit la table entière et évalue chaque ligne par rapport à la clause where. La durée d'exécution grandit avec la taille de la table : si la table décuple, l'opération FULL TABLE SCAN prendra dix fois plus longtemps. Le danger de cette opération est qu'elle est souvent suffisamment rapide dans un petit environnement de développement, mais elle cause de sérieux problèmes de performance en production.

Parcours complet de table

L'opération TABLE ACCESS FULL, aussi connue sous le nom de parcours complet de table, peut être l'opération la plus efficace dans certains cas, en particulier quand il faut récupérer une large portion de la table.

Ceci est dû en partie à la surcharge pour une recherche dans l'index, ce qui n'arrive pas pour une opération TABLE ACCESS FULL. En fait, quand une recherche par index lit un bloc après l'autre, la base de données ne sait pas quel bloc sera lu après tant que le traitement du bloc courant n'est pas terminé. Un FULL TABLE SCAN doit lire la table complète de toute façon, donc la base de données peut lire de plus gros morceaux à la fois (lecture multi-blocs). Bien que la base de données lise plus de données, il pourrait être nécessaire d'exécuter moins d'opérations de lecture.

La base de données n'utilise pas l'index car elle ne peut pas utiliser une colonne à partir d'un index concaténé. C'est beaucoup plus clair en faisant plus attention à la structure de l'index.

Un index concaténé est un index B-tree comme n'importe quel autre, qui conserve les données indexées dans une liste triée. La base de données considère chaque colonne suivant sa position dans la définition de l'index pour trier les enregistrements. La première colonne est le critère principal de tri et la deuxième colonne détermine l'ordre seulement si deux enregis­trements ont la même valeur dans la première colonne. Et ainsi de suite.

Important

Un index concaténé est un index sur plusieurs colonnes.

L'ordre d'un index à deux colonnes ressemble à l'ordre d'un annuaire téléphonique : il est tout d'abord trié par le nom, puis par le prénom. Cela signifie qu'un index à deux colonnes ne permet pas une recherche sur la deuxième colonne seule. Cela reviendrait à rechercher dans un annuaire en ayant seulement le prénom.

Figure 2.1 Index concaténé

L'exemple d'index dans la Figure 2.1 montre que les enregistrements pour l'identifiant supplémentaire 20 ne sont pas stockés les uns à côté des autres. On remarque également qu'il n'y a pas d'enregistrements pour lesquels ID_SUPPLEMENTAIRE = 20 dans l'arbre, bien qu'ils existent dans les nœuds feuilles. Du coup, l'arbre est inutile pour cette requête.

Astuce

Visualiser un index aide à comprendre les requêtes supportées par cet index. Vous pouvez exécuter une requête sur la base de données pour retrouver tous les enregistrements dans l'ordre de l'index (syntaxe SQL:2008, voir la pour des solutions propriétaires utilisant LIMIT, TOP ou ROWNUM) :

SELECT <COLONNES LISTE D'INDEX> 
  FROM <TABLE>  
 ORDER BY <COLONNES LISTE D'INDEX>
 FETCH FIRST 100 ROWS ONLY;

Si vous placez la définition de l'index et le nom de la table dans la requête, vous obtiendrez un extrait de l'index. Demandez-vous si les lignes demandées sont groupées en un point central. Dans le cas contraire, l'arbre de l'index ne peut pas vous aider à trouver cette place.

Bien sûr, nous pouvons ajouter un autre index sur ID_SUPPLEMENTAIRE pour améliorer la rapidité de la requête. Néanmoins, il existe une meilleure solution, tout du moins si nous supposons que la recherche sur ID_EMPLOYE seul n'a pas de sens.

Nous pouvons profiter du fait que la première colonne de l'index est toujours utilisable pour la recherche. Encore une fois, cela fonctionne comme un annuaire téléphonique : vous n'avez pas besoin de connaître le prénom pour chercher le nom. L'astuce revient donc à inverser l'ordre des colonnes de l'index pour que ID_SUPPLEMENTAIRE soit en première position :

CREATE UNIQUE INDEX EMPLOYES_PK 
    ON EMPLOYES (ID_SUPPLEMENTAIRE, ID_EMPLOYE);

Les deux colonnes ensemble sont toujours uniques. Ainsi les requêtes sur la clé primaire complète peuvent toujours utiliser un INDEX UNIQUE SCAN mais la séquence des enregistrements d'index est complètement différente. La colonne ID_SUPPLEMENTAIRE est devenue le critère principal de tri. Cela signifie que tous les enregistrements pour une société sont consécutifs dans l'index, et la base de données peut utiliser l'index B-tree pour trouver leur emplacement.

Important

Le point le plus important à considérer lors de la définition d'un index concaténé est le choix de l'ordre des colonnes pour qu'il puisse supporter autant de requêtes SQL que possible.

Le plan d'exécution confirme que la base de données utilise l'index inversé. La colonne ID_SUPPLEMENTAIRE seule n'est plus unique, donc la base de données doit suivre les nœuds feuilles pour trouver tous les enregistrements correspondants : du coup, il utilise une opération INDEX RANGE SCAN.

MySQL

+----+----------+------+---------+---------+------+-------+
| id | table    | type | key     | key_len | rows | Extra |
+----+----------+------+---------+---------+------+-------+
|  1 | employes | ref  | PRIMARY | 5       |  123 |       |
+----+----------+------+---------+---------+------+-------+

Oracle

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

Predicate Information (identified by operation id):
---------------------------------------------------
   2 - access("ID_SUPPLEMENTAIRE"=20)

PostgreSQL

                 QUERY PLAN
----------------------------------------------
 Bitmap Heap Scan on employes
 (cost=24.63..1529.17 rows=1080 width=13)
   Recheck Cond: (id_supplementaire = 2::numeric)
   -> Bitmap Index Scan on employees_pk
      (cost=0.00..24.36 rows=1080 width=0)
      Index Cond: (id_supplementaire = 2::numeric)

SQL Server

|--Nested Loops(Inner Join)
   |--Index Seek(OBJECT:employes_pk,
   |               SEEK:id_supplementaire=20
   |            ORDERED FORWARD)
   |--RID Lookup(OBJECT:employes,
                   SEEK:Bmk1000=Bmk1000
                 LOOKUP ORDERED FORWARD)

En général, une base de données peut utiliser un index concaténé lors de la recherche des colonnes les plus à gauche. Un index à trois colonnes peut être utilisé pour une recherche sur la première colonne, pour une recherche sur les deux premières colonnes et pour une recherche sur toutes les colonnes.

Même si la solution à deux index délivre des performances très bonnes pour les SELECT, la solution à un seul index est préférable. Non seulement cela permet d'économiser de l'espace de stockage, mais aussi la surcharge due à la maintenance pour le deuxième index. Moins une table a d'index, meilleures sont les performances des commandes INSERT, DELETE et UPDATE.

Pour définir un index optimal, vous devez comprendre un peu plus que le simple fonctionnement des index. Vous devez également savoir comment l'application demande les données, c'est-à-dire connaître les combinaisons de colonnes qui apparaissent dans les clauses WHERE.

Du coup, définir un index optimal est très difficile pour des consultants externes car ils n'ont pas de vue globale des chemins d'accès de l'application. Les consultants peuvent généralement prendre en compte une seule requête. Ils n'exploitent pas les bénéfices supplémentaires qu'un index peut fournir pour les autres requêtes. Les administrateurs de bases de données sont dans une position similaire. Ils peuvent connaître le schéma de la base de données mais ils n'ont pas de connaissances étendues des chemins d'accès.

La seule personne qui doit avoir la connaissance technique de la base de données et la connaissance fonctionnelle du métier est le développeur. Les développeurs ont une idée des données et connaissent les chemins d'accès aux données. Ils peuvent indexer les données correctement de telle manière à obtenir les meilleures performances pour l'application complète sans trop d'efforts.

À 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