Vous trouverez en ligne les différentes versions complètes de ce document. Les solutions de TP ne figurent pas forcément dans la version imprimée, mais sont dans les versions numériques (PDF ou HTML).

Vous n’avez pas le droit d’utiliser cette création à des fins commerciales.

Si vous modifiez, transformez ou adaptez cette création, vous n’avez le droit de distribuer la création qui en résulte que sous un contrat identique à celui-ci.

Vous devez citer le nom de l’auteur original de la manière indiquée par l’auteur de l’œuvre ou le titulaire des droits qui vous confère cette autorisation (mais pas d’une manière qui suggérerait qu’ils vous soutiennent ou approuvent votre utilisation de l’œuvre). À chaque réutilisation ou distribution de cette création, vous devez faire apparaître clairement au public les conditions contractuelles de sa mise à disposition. La meilleure manière de les indiquer est un lien vers cette page web. Chacune de ces conditions peut être levée si vous obtenez l’autorisation du titulaire des droits sur cette œuvre. Rien dans ce contrat ne diminue ou ne restreint le droit moral de l’auteur ou des auteurs.

Le texte complet de la licence est disponible sur http://creativecommons.org/licenses/by-nc-sa/2.0/fr/legalcode

Cela inclut les diapositives, les manuels eux-mêmes et les travaux pratiques. Cette formation peut également contenir quelques images et schémas dont la redistribution est soumise à des licences différentes qui sont alors précisées.

Sur les versions précédentes susceptibles d’être encore rencontrées en production, seuls quelques points très importants sont évoqués, en plus éventuellement de quelques éléments historiques.

Sauf précision contraire, le système d’exploitation utilisé est Linux.

Photo de Maksym Kaharlytskyi, Unsplash licence

Les index ne sont pas des objets qui font partie de la théorie relationnelle. Ils sont des objets physiques qui permettent d’accélérer l’accès aux données. Et comme ils ne sont que des moyens d’optimisation des accès, les index ne font pas non plus partie de la norme SQL. C’est d’ailleurs pour cette raison que la syntaxe de création d’index est si différente d’une base de données à une autre.

La création des index est à la charge du développeur ou du DBA, leur création n’est pas automatique, sauf exception.

Pour Markus Winand, c’est d’abord au développeur de poser les index, car c’est lui qui sait comment ses données sont utilisées. Un DBA d’exploitation n’a pas cette connaissance, mais il connaît généralement mieux les différents types d’index et leurs subtilités, et voit comment les requêtes réagissent en production. Développeur et DBA sont complémentaires dans l’analyse d’un problème de performance.

Le site de Markus Winand, Use the index, Luke, propose une version en ligne de son livre SQL Performance Explained, centré sur les index B-tree (les plus courants). Une version française est par ailleurs disponible sous le titre SQL : au cœur des performances.

Les index ne changent pas le résultat d’une requête, mais l’accélèrent. L’index permet de pointer l’endroit de la table où se trouve une donnée, pour y accéder directement. Parfois c’est toute une plage de l’index, voire sa totalité, qui sera lue, ce qui est généralement plus rapide que lire toute la table.

Le cas le plus favorable est l’Index Only Scan : toutes les données nécessaires sont contenues dans l’index, lui seul sera lu et PostgreSQL ne lira pas la table elle-même.

PostgreSQL propose différentes formes d’index :

• index classique sur une seule colonne d’une table ;
• index composite sur plusieurs colonnes d’une table ;
• index partiel, en restreignant les données indexées avec une clause WHERE ;
• index fonctionnel, en indexant le résultat d’une fonction appliquée à une ou plusieurs colonnes d’une table ;
• index couvrants, contenant plus de champs que nécessaire au filtrage, pour ne pas avoir besoin de lire la table, et obtenir un Index Only Scan.

La création des index est à la charge du développeur. Seules exceptions : ceux créés automatiquement quand on déclare des contraintes de clé primaire ou d’unicité. La création est alors automatique.

Les contraintes de clé étrangère imposent qu’il existe déjà une clé primaire sur la table pointée, mais ne crée pas d’index sur la table portant la clé.

L’index est une structure de données qui permet d’accéder rapidement à l’information recherchée. À l’image de l’index d’un livre, pour retrouver un thème rapidement, on préférera utiliser l’index du livre plutôt que lire l’intégralité du livre jusqu’à trouver le passage qui nous intéresse. Dans une base de données, l’index a un rôle équivalent. Plutôt que de lire une table dans son intégralité, la base de données utilisera l’index pour ne lire qu’une faible portion de la table pour retrouver les données recherchées.

Pour la requête d’exemple (avec une table de 20 millions de lignes), on remarque que l’optimiseur n’utilise pas le même chemin selon que l’index soit présent ou non. Sans index, PostgreSQL réalise un parcours séquentiel de la table :

EXPLAIN SELECT * FROM test WHERE id = 10000;

                              QUERY PLAN
----------------------------------------------------------------------
 Gather  (cost=1000.00..193661.66 rows=1 width=4)
   Workers Planned: 2
   ->  Parallel Seq Scan on test  (cost=0.00..192661.56 rows=1 width=4)
         Filter: (id = 10000)

Lorsqu’il est présent, PostgreSQL l’utilise car l’optimiseur estime que son parcours ne récupérera qu’une seule ligne sur les 20 millions que compte la table :

EXPLAIN SELECT * FROM test WHERE id = 10000;

                               QUERY PLAN
----------------------------------------------------------------------------
 Index Only Scan using idx_test_id on test  (cost=0.44..8.46 rows=1 width=4)
   Index Cond: (id = 10000)

Mais l’index n’accélère pas seulement la simple lecture de données, il permet également d’accélérer les tris et les agrégations, comme le montre l’exemple suivant sur un tri :

EXPLAIN SELECT id FROM test
        WHERE id BETWEEN 1000 AND 1200 ORDER BY id DESC;

                               QUERY PLAN
--------------------------------------------------------------------------------
 Index Only Scan Backward using idx_test_id on test
                                             (cost=0.44..12.26 rows=191 width=4)
   Index Cond: ((id >= 1000) AND (id <= 1200))

La présence d’un index ralentit les écritures sur une table. En effet, il faut non seulement ajouter ou modifier les données dans la table, mais il faut également maintenir le ou les index de cette table.

Les index dégradent surtout les temps de réponse des insertions. Les mises à jour et les suppressions (UPDATE et DELETE) tirent en général parti des index pour retrouver les lignes concernées par les modifications. Le coût de maintenance de l’index est secondaire par rapport au coût de l’accès aux données.

Soit une table test2 telle que :

CREATE TABLE test2 (
    id INTEGER GENERATED BY DEFAULT AS IDENTITY PRIMARY KEY,
    valeur INTEGER,
    commentaire TEXT
);

La table est chargée avec pour seul index présent celui sur la clé primaire :

INSERT INTO test2 (valeur, commentaire)
SELECT i, 'commentaire ' || i FROM generate_series(1, 10000000) i;

INSERT 0 10000000
Durée : 35253,228 ms (00:35,253)

Un index supplémentaire est créé sur une colonne de type entier :

CREATE INDEX idx_test2_valeur ON test2 (valeur);
INSERT INTO test2 (valeur, commentaire)
SELECT i, 'commentaire ' || i FROM generate_series(1, 10000000) i;

INSERT 0 10000000
Durée : 44410,775 ms (00:44,411)

Un index supplémentaire est encore créé, mais cette fois sur une colonne de type texte :

CREATE INDEX idx_test2_commentaire ON test2 (commentaire);
INSERT INTO test2 (valeur, commentaire)
SELECT i, 'commentaire ' || i FROM generate_series(1, 10000000) i;

INSERT 0 10000000
Durée : 207075,335 ms (03:27,075)

On peut comparer ces temps à l’insertion dans une table similaire dépourvue d’index :

CREATE TABLE test3 AS SELECT * FROM test2;
INSERT INTO test3 (valeur, commentaire)
SELECT i, 'commentaire ' || i FROM generate_series(1, 10000000) i;

INSERT 0 10000000
Durée : 14758,503 ms (00:14,759)

La table test2 a été vidée préalablement pour chaque test.

Enfin, la place disque utilisée par ces index n’est pas négligeable :

\di+ *test2*
                                 Liste des relations
 Schéma |          Nom          | Type  | Propriétaire | Table | Taille |  …
--------+-----------------------+-------+--------------+-------+--------+-
 public | idx_test2_commentaire | index | postgres     | test2 | 387 MB |
 public | idx_test2_valeur      | index | postgres     | test2 | 214 MB |
 public | test2_pkey            | index | postgres     | test2 | 214 MB |

SELECT pg_size_pretty(pg_relation_size('test2')),
       pg_size_pretty(pg_indexes_size('test2')) ;

 pg_size_pretty | pg_size_pretty
----------------+----------------
 574 MB         | 816 MB

Pour ces raisons, on ne posera pas des index systématiquement avant de se demander s’ils seront utilisés. L’idéal est d’étudier les plans de ses requêtes et de chercher à optimiser.

Création d’un index :

Bien sûr, la durée de création de l’index dépend fortement de la taille de la table. PostgreSQL va lire toutes les lignes et trier les valeurs rencontrées. Ce peut être lourd et impliquer la création de fichiers temporaires.

Si l’on utilise la syntaxe classique, toutes les écritures sur la table sont bloquées (mises en attente) pendant la durée de la création de l’index (verrou ShareLock). Les lectures restent possibles, mais cette contrainte est parfois rédhibitoire pour les grosses tables.

Clause CONCURRENTLY :

Ajouter le mot clé CONCURRENTLY permet de rendre la table accessible en écriture. Malheureusement, cela nécessite au minimum deux parcours de la table, et donc alourdit et ralentit la construction de l’index. Dans quelques cas défavorables (entre autres l’interruption de la création de l’index), la création échoue et l’index existe mais est invalide :

pgbench=# \d pgbench_accounts
                  Table « public.pgbench_accounts »
 Colonne  |     Type      | Collationnement | NULL-able | Par défaut 
----------+---------------+-----------------+-----------+------------
 aid      | integer       |                 | not null  | 
 bid      | integer       |                 |           | 
 abalance | integer       |                 |           | 
 filler   | character(84) |                 |           | 
Index :
    "pgbench_accounts_pkey" PRIMARY KEY, btree (aid)
    "pgbench_accounts_bid_idx" btree (bid) INVALID

L’index est inutilisable et doit être supprimé et recréé, ou bien réindexé. Pour les détails, voir la documentation officielle.

Une supervision peut détecter des index invalides avec cette requête, qui ne doit jamais rien ramener :

SELECT indexrelid::regclass AS index, indrelid::regclass AS table
FROM pg_index
WHERE indisvalid = false ;

Réindexation :

Comme les tables, les index sont soumis à la fragmentation. Celle-ci peut cependant monter assez haut sans grande conséquence pour les performances. De plus, le nettoyage des index est une des étapes des opérations de VACUUM.

Une reconstruction de l’index est automatique lors d’un VACUUM FULL de la table.

Certaines charges provoquent une fragmentation assez élevée, typiquement les tables gérant des files d’attente. Une réindexation reconstruit totalement l’index. Voici quelques variantes de l’ordre :

REINDEX INDEX pgbench_accounts_bid_idx ;  -- un seul index
REINDEX TABLE pgbench_accounts ;          -- tous les index de la table
REINDEX (VERBOSE) DATABASE pgbench ;      -- tous ceux de la base, avec détails

Il existe là aussi une clause CONCURRENTLY :

REINDEX (VERBOSE) INDEX CONCURRENTLY pgbench_accounts_bid_idx ;

(En cas d’échec, on trouvera là aussi des index invalides, suffixés avec _ccnew, à côté des index préexistants toujours fonctionnels et que PostgreSQL n’a pas détruits.)

Paramètres :

La rapidité de création d’un index dépend essentiellement de la mémoire accordée, définie dans maintenance_work_mem. Si elle ne suffit pas, le tri se fera dans des fichiers temporaires plus lents. Sur les serveurs modernes, le défaut de 64 Mo est ridicule, et on peut monter aisément à :

SET maintenance_work_mem = '2GB' ;

Attention de ne pas saturer la mémoire en cas de création simultanée de nombreux gros index (lors d’une restauration avec pg_restore notamment).

Si le serveur est bien doté en CPU, la parallélisation de la création d’index peut apporter un gain en temps appréciable. La valeur par défaut est :

SET max_parallel_maintenance_workers = 2 ;

et devrait même être baissée sur les plus petites configurations.

Par défaut un CREATE INDEX créera un index de type B-tree, de loin le plus courant. Il est stocké sous forme d’arbre équilibré, avec de nombreux avantages :

• les performances se dégradent peu avec la taille de l’arbre (les temps de recherche sont en O(log(n)), donc fonction du logarithme du nombre d’enregistrements dans l’index) ;
• l’accès concurrent est excellent, avec très peu de contention entre processus qui insèrent simultanément.

Toutefois les B-tree ne permettent de répondre qu’à des questions très simples, portant sur la colonne indexée, et uniquement sur des opérateurs courants (égalité, comparaison). Cela couvre tout de même la majorité des cas.

Contrainte d’unicité et index :

Un index peut être déclaré UNIQUE pour provoquer une erreur en cas d’insertion de doublons. Mais on préférera généralement déclarer une contrainte d’unicité (notion fonctionnelle), qui techniquement, entraînera la création d’un index.

Par exemple, sur cette table personne :

$ CREATE TABLE personne (id int, nom text);

$ \d personne
                 Table « public.personne »
 Colonne |  Type   | Collationnement | NULL-able | Par défaut
---------+---------+-----------------+-----------+------------
 id      | integer |                 |           |
 nom     | text    |                 |           |

on peut créer un index unique :

$ CREATE UNIQUE INDEX ON personne (id);

$ \d personne
                  Table « public.personne »
 Colonne |  Type   | Collationnement | NULL-able | Par défaut
---------+---------+-----------------+-----------+------------
 id      | integer |                 |           |
 nom     | text    |                 |           |
Index :
    "personne_id_idx" UNIQUE, btree (id)

La contrainte d’unicité est alors implicite. La suppression de l’index se fait sans bruit :

DROP INDEX personne_id_idx;

Définissons une contrainte d’unicité sur la colonne plutôt qu’un index :

ALTER TABLE personne ADD CONSTRAINT unique_id UNIQUE (id);

$ \d personne
                  Table « public.personne »
 Colonne |  Type   | Collationnement | NULL-able | Par défaut
---------+---------+-----------------+-----------+------------
 id      | integer |                 |           |
 nom     | text    |                 |           |
Index :
    "unique_id" UNIQUE CONSTRAINT, btree (id)

Un index est également créé. La contrainte empêche sa suppression :

DROP INDEX unique_id ;

ERREUR:  n'a pas pu supprimer index unique_id car il est requis par contrainte
 unique_id sur table personne
ASTUCE : Vous pouvez supprimer contrainte unique_id sur table personne à la
 place.

Le principe est le même pour les clés primaires.

Indexation avancée :

Il faut aussi savoir que PostgreSQL permet de créer des index B-tree :

• sur plusieurs colonnes ;
• sur des résultats de fonction ;
• sur une partie des valeurs indexées ;
• intégrant des champs non indexés mais souvent récupérés avec les champs indexés (index couvrants).

D’autres types d’index que B-tree existent, destinés à certains types de données ou certains cas d’optimisation précis.

Les fiches en carton des anciennes bibliothèques sont un bon équivalent du type d’index le plus courant utilisé par les bases de données en général et PostgreSQL en particulier : le B-tree.

Lorsque l’on recherche des ouvrages dans la bibliothèque, il est possible de parcourir l’intégralité du bâtiment pour chercher les livres qui nous intéressent. Ceci prend énormément de temps. La bibliothèque peut être triée, mais ce tri ne permet pas forcément de trouver facilement le livre. Ce type de recherche trouve son analogie sous la forme du parcours complet d’une table (Seq Scan).

Une deuxième méthode pour localiser l’ouvrage consiste à utiliser un index. Sur fiche carton ou sous forme informatique, cet index associe par exemple le nom d’auteur à un ensemble de références (emplacements dans les rayonnages) où celui-ci est présent. Ainsi, pour trouver les œuvres de Proust avec l’index en carton, il suffit de parcourir les fiches, dont l’intégralité tient devant l’utilisateur. La fiche indique des références dans plusieurs rayons et il faudra aller se déplacer pour trouver les œuvres, en allant directement aux bons rayons.

Dans une base de données, le fonctionnement d’un index est très similaire. En effet, comme dans une bibliothèque, l’index est une structure de données à part, qui n’est pas strictement nécessaire à l’exploitation des informations, et qui est principalement utilisée pour la recherche dans l’ensemble de données. Cette structure de données possède un coût de maintenance, dans les deux cas : toute modification des données entraîne des modifications de l’index afin de le maintenir à jour. Et un index qui n’est pas à jour peut provoquer de gros problèmes. Dans le doute, on peut jeter l’index et le recréer de zéro sans problème d’intégrité des données originales.

Il peut y avoir plusieurs index suivant les besoins. L’index trié par auteur ne permet pas de trouver un livre dont on ne connaît que le titre (sauf à lire toutes les fiches). Il faut alors un autre index classé par titre.

Pour filer l’analogie : un index peut être multicolonne (les fiches en carton triées par auteur le sont car elles contiennent le titre, et pas que la référence dans les rayons). L’index peut répondre à une demande à lui seul : il suffit pour compter le nombre de livres de Marcel Proust (c’est le principe des Index Only Scans). Une fiche d’un index peut contenir des informations supplémentaires (dates de publication, éditeur…) pour faciliter d’autres recherches sans aller dans les rayons (index « couvrant »).

Dans la réalité comme dans une base de données, il y a un dilemme quand il faut récupérer de très nombreuses données : soit aller chercher de nombreux livres un par un dans les rayons, soit balayer tous les livres systématiquement dans l’ordre où ils viennent pour éviter trop d’allers-retours.

Autres types d’index non informatiques similaires au B-tree :

• les tables décennales de l’État civil, qui pointent vers un endroit précis des registres des actes de naissance, mariage ou décès d’une commune ;
• l’index d’un catalogue papier.

L’index d’un livre technique ou d’un livre de recettes cible des parties des données et non les données elles-mêmes (comme le titre). Il s’approche plus d’un autre type d’index, le GIN, qui existe aussi dans PostgreSQL.

Un annuaire téléphonique papier présente les données sous un mode strictement ordonné. Cette intégration entre table et index n’a pas d’équivalent sous PostgreSQL mais existe dans d’autres moteurs de bases de données.

Bien souvent, la création d’index est vue comme le remède à tous les maux de performance subis par une application. Il ne faut pas perdre de vue que les facteurs principaux affectant les performances vont être liés à la conception du schéma de données, et à l’écriture des requêtes SQL.

Pour prendre un exemple caricatural, un schéma EAV (Entity-Attribute-Value, ou entité-clé-valeur) ne pourra jamais être performant, de part sa conception. Bien sûr, dans certains cas, une méthodologie pertinente d’indexation permettra d’améliorer un peu les performances, mais le problème réside là dans la conception même du schéma. Il est donc important dans cette phase de considérer la manière dont le modèle va influer sur les méthodes d’accès aux données, et les implications sur les performances.

De même, l’écriture des requêtes elles-mêmes conditionnera en grande partie les performances observées sur l’application. Par exemple, la mauvaise pratique (souvent mise en œuvre accidentellement via un ORM) dite du « N+1 » ne pourra être corrigée par une indexation correcte : celle-ci consiste à récupérer une collection d’enregistrement (une requête) puis d’effectuer une requête pour chaque enregistrement afin de récupérer les enregistrements liés (N requêtes). Dans ce type de cas, une jointure est bien plus performante. Ce type de comportement doit encore une fois être connu de l’équipe de développement, car il est plutôt difficile à détecter par une équipe d’exploitation.

De manière générale, avant d’envisager la création d’index supplémentaires, il convient de s’interroger sur les possibilités de réécriture des requêtes, voire du schéma.

L’index B-tree est le plus simple conceptuellement parlant. Sans entrer dans les détails, un index B-tree est par définition équilibré : ainsi, quelle que soit la valeur recherchée, le coût est le même lors du parcours d’index. Ceci ne veut pas dire que toute requête impliquant l’index mettra le même temps ! En effet, si chaque clé n’est présente qu’une fois dans l’index, celle-ci peut être associée à une multitude de valeurs, qui devront alors être cherchées dans la table.

L’algorithme utilisé par PostgreSQL pour ce type d’index suppose que chaque page peut contenir au moins trois valeurs. Par conséquent, chaque valeur ne peut excéder un peu moins d’⅓ de bloc, soit environ 2,6 ko. La valeur en question correspond donc à la totalité des données de toutes les colonnes de l’index pour une seule ligne. Si l’on tente de créer ou maintenir un index sur une table ne satisfaisant pas ces prérequis, une erreur sera renvoyée, et la création de l’index (ou l’insertion/mise à jour de la ligne) échouera. Ces champs sont souvent des longs textes ou des champs composés dont on cherchera plutôt des parties, et un index B-tree n’est de toute façon pas adapté. Si un index de type B-tree est tout de même nécessaire sur les colonnes en question, pour des recherches sur l’intégralité de la ligne, les index de type hash sont plus adaptés (mais ils ne supportent que l’opérateur =).