par Guillaume Lelarge.

Tables organisées en index et index regroupés


Le parcours d'index seul exécute une requête SQL en utilisant seulement les données redondantes enregistrées dans l'index. Les données originales disponibles dans la table (heap) ne sont pas nécessaires. Si nous prenons ce concept au niveau supérieur et plaçons toutes les colonnes dans l'index, nous pourrions nous demander pourquoi nous avons besoin de la table.

De ce fait, certaines bases de données utilisent un index comme principal stockage de la table. La base de données Oracle appelle ce concept table organisée en index (IOT, pour « index-organized table »), d'autres bases de données utilisent le terme index regroupé (« clustered index » en anglais). Dans cette section, les deux termes sont utilisés pour mettre l'accent sur les caractéristiques de la table ou de l'index, suivant le besoin.

Ainsi, une table organisée en index est un index B-tree sans table (heap). Cela a deux avantages : on évite de perdre de l'espace disque et chaque accès à un index regroupé est automatiquement un parcours d'index seul. Ces deux avantages sont très prometteurs mais difficilement atteignables en pratique.

Les inconvénients des tables organisées en index deviennent apparents lors de la création d'un autre index sur la même table. De façon analogue à un index standard, un index secondaire fait référence aux données de la table originale, qui sont stockées dans l'index regroupé. Là, les données ne sont pas enregistrées statiquement comme dans une table mais peuvent être déplacées à tout moment pour maintenir l'ordre de l'index. Du coup, il n'est pas possible d'enregistrer l'emplacement physique des lignes dans la table organisée en index dans l'index secondaire. La base de données doit utiliser une clé logique à la place.

Le graphe suivant montre une recherche via un index pour trouver toutes les ventes du 23 mai 2012. En comparaison, nous allons tout d'abord regarder la Figure 5.2 qui montre le processus lors de l'utilisation d'une table standard. L'exécution implique deux étapes : l'opération INDEX RANGE SCAN et l'opération TABLE ACCESS BY INDEX ROWID.

Figure 5.2 Accès basé sur l'index à une table standard

Bien que l'accès à la table puisse devenir un goulet d'étranglement, cela reste limité à une opération de lecture par ligne car l'index dispose du ROWID comme pointeur direct vers la ligne de la table. La base de données peut immédiatement charger la ligne à partir de la table standard car l'index a sa position exacte. Néanmoins, le graphe change lors de l'utilisation de l'index secondaire sur une table organisée en index. Un index secondaire ne stocke pas de pointeurs physiques (ROWID) mais seulement les valeurs clés de l'index regroupé, fréquemment appelées clé de regroupement. Il s'agit souvent de la clé primaire de la table organisée en index.

Pourquoi les index secondaires n'ont pas de ROWID

Un pointeur direct à une ligne de la table serait préférable dans l'index secondaire. Cela est seulement possible si la ligne de la table reste à la même position de stockage. Malheureusement, ce n'est pas possible si la ligne est partie intégrante d'une structure d'index qui est conservée dans l'ordre. Garder l'index dans l'ordre rend parfois nécessaire de déplacer les lignes. Ceci est aussi vrai pour les opérations qui n'affectent pas directement la ligne elle-même. Par exemple, une requête insert pourrait diviser en deux un nœud feuille pour gagner de la place pour la nouvelle entrée. Cela signifie que certaines entrées sont déplacées dans un nouveau bloc de données.

D'un autre côté, une table standard ne conserve pas les lignes dans un certain ordre. La base de données enregistre les nouvelles entrées là où elle dispose de la place libre. Une fois écrite, la donnée n'est pas déplacée.

Accéder à un index secondaire ne ramène pas un ROWID mais une clé logique pour rechercher la ligne dans l'index regroupé. Néanmoins, un seul accès n'est pas suffisant pour rechercher dans l'index regroupé. Cela nécessite un parcours complet de l'arbre. Autrement dit, un accès à la table via un index secondaire fait une recherche dans deux index : tout d'abord dans l'index secondaire (INDEX RANGE SCAN), puis dans l'index regroupé pour chaque ligne trouvée dans l'index secondaire (INDEX UNIQUE SCAN).

Figure 5.3 Index secondaire sur un IOT

La Figure 5.3 rend évident le fait que le B-tree de l'index regroupé se tient entre l'index secondaire et les données de la table.

Accéder à une table organisée en index via un index secondaire est très inefficace, et cela peut être empêché de la même façon qu'on empêche un accès à la table sur une table standard : en utilisant un parcours d'index seul, qui est mieux décrit dans ce cas comme un « parcours d'index secon­daire seul ». L'avantage au niveau des performances d'un parcours d'index seul est encore plus important car il empêche non seulement un accès seul mais aussi une opération INDEX UNIQUE SCAN entière.

Important

Accéder à une table organisée en index via un index secondaire est très inefficace.

En utilisant cet exemple, nous pouvons aussi voir que les bases de données exploitent toutes les redondances qu'elles ont. Gardez en tête qu'un index secondaire enregistre la clé de regroupement pour chaque entrée d'index. En conséquence, nous pouvons demander la clé de regroupement à partir d'un index secondaire sans accéder à la table organisée en index :

SELECT id_vente
  FROM ventes_iot
 WHERE date_vente = ?;
--------------------------------------------------
| Id | Operation        | Name            | Cost |
--------------------------------------------------
|  0 | SELECT STATEMENT |                 |    4 |
|* 1 |  INDEX RANGE SCAN| VENTES_IOT_DATE |    4 |
--------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   1 - access("DATE_VENTE"=:DT)

La table VENTES_IOT est une table organisée en index qui utilise ID_VENTE comme clé de regroupement. Bien que l'index VENTE_IOT_DATE soit seulement sur la colonne DATE_VENTE, il a toujours une copie de la clé de regroupement ID_VENTE pour qu'il puisse répondre à la requête en utilisant seulement l'index secondaire.

Lors de la sélection des autres colonnes, la base de données doit exécuter une opération INDEX UNIQUE SCAN sur l'index regroupé pour chaque ligne :

SELECT valeur_eur
  FROM ventes_iot
 WHERE date_vente = ?;
----------------------------------------------------
| Id  | Operation         | Name            | Cost |
----------------------------------------------------
|   0 | SELECT STATEMENT  |                 |   13 |
|*  1 |  INDEX UNIQUE SCAN| VENTES_IOT_PK   |   13 |
|*  2 |   INDEX RANGE SCAN| VENTES_DATE_IOT |    4 |
----------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   1 - access("DATE_VENTE"=:DT)
   2 - access("DATE_VENTE"=:DT)

Les tables organisées en index et les index regroupés ne sont donc pas si utiles. Les améliorations de performance sur l'index regroupé sont facilement perdues lors de l'utilisation d'un index secondaire. La clé de regroupement est généralement plus longue qu'un ROWID, du coup les index secondaires sont plus gros qu'une table standard, ce qui élimine souvent le gain réalisé par l'omission de la table standard. La force des tables organisées en index et des index regroupés est souvent limitée aux tables qui n'ont pas besoin d'index secondaire. Les tables standard ont l'intérêt de fournir des données qui ne sont pas déplacées, ce qui facilite leur référencement.

Important

Les tables avec un seul index sont intéressantes pour la mise en place d'index regroupés ou de tables organisées en index.

Les tables ayant plus d'index peuvent généralement bénéficier du format standard. Vous pouvez toujours utiliser les parcours d'index seul pour éviter l'accès à la table. Cela vous donne les performances d'un select sur un index regroupé sans ralentir les autres index.

Le support des bases de données pour les tables organisées en index et pour les index regroupés est très différent. L'aperçu suivant explique les spécificités les plus importantes.

DB2

DB2 n'a pas de table organisée en index mais utilise le terme d'index regroupé pour une autre fonctionnalité. Elle utilise une table standard et essaie d'insérer les nouvelles lignes dans le même bloc que les lignes proches dans l'index.

MySQL

Le moteur MyISAM utilise seulement les tables standards alors que le moteur InnoDB utilise toujours les index regroupés. Autrement dit, vous n'avez pas le choix.

Oracle

La base de données Oracle utilise par défaut les tables standards. Les tables organisées en index peuvent être créées en utilisant la clause ORGANIZATION INDEX :

CREATE TABLE (
   id    NUMBER NOT NULL PRIMARY KEY,
   [...]
) ORGANIZATION INDEX;

La base de données Oracle utilise toujours la clé primaire comme clé de regroupement.

PostgreSQL

PostgreSQL utilise seulement les tables standards.

Néanmoins, vous pouvez utiliser la clause CLUSTER pour aligner le contenu de la table standard avec un index.

SQL Server

Par défaut, SQL Server utilise des index regroupés (tables organisées en index) en utilisant la clé primaire comme clé de regroupement. Néanmoins, vous pouvez utiliser des colonnes arbitraires pour la clé de regroupement, voire même des colonnes non uniques.

Pour créer une table standard, vous devez utiliser la clause NONCLUSTERED dans la définition de la clé primaire :

CREATE TABLE (
   id    NUMBER NOT NULL,
   [...]
   CONSTRAINT pk PRIMARY KEY NONCLUSTERED (id)
);

Supprimer un index regroupé transforme la table en table standard.

Le comportement par défaut de SQL Server cause souvent des problèmes de performances lors de l'utilisation d'index secondaires.

À 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