Vous trouverez en ligne les différentes versions complètes de ce document.

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 =).

Ce schéma présente une vue très simplifiée d’une table (en blanc, avec ses champs id et name) et d’un index B-tree sur id (en bleu), tel que le créerait :

CREATE INDEX mon_index ON ma_table (id) ;

Un index B-tree peut contenir trois types de nœuds :

• la racine : elle est unique c’est la base de l’arbre ;
• des nœuds internes : il peut y en avoir plusieurs niveaux ;
• des feuilles : elles contiennent :
  • les valeurs indexées (triées !) ;
  • les valeurs incluses (si applicable) ;
  • les positions physiques (ctid), ici entre parenthèses et sous forme abrégée, car la forme réelle est (numéro de bloc, position de la ligne dans le bloc) ;
  • l’adresse de la feuille précédente et de la feuille suivante.

La racine et les nœuds internes contiennent des enregistrements qui décrivent la valeur minimale de chaque bloc du niveau inférieur et leur adresse (ctid).

Lors de la création de l’index, il ne contient qu’une feuille. Lorsque cette feuille se remplit, elle se divise en deux et un nœud racine est créé au-dessus. Les feuilles se remplissent ensuite progressivement et se séparent en deux quand elles sont pleines. Ce processus remplit progressivement la racine. Lorsque la racine est pleine, elle se divise en deux nœuds internes, et une nouvelle racine est crée au-dessus. Ce processus permet de garder un arbre équilibré.

Recherchons le résultat de :

SELECT name FROM ma_table WHERE id = 22

en passant par l’index.

• En parcourant la racine, on cherche un enregistrement dont la valeur est strictement supérieure à la valeur que l’on recherche. Ici, 22 est plus petit que 24 : on explore donc le nœud de gauche.
• Ce nœud référence trois nœuds inférieurs (ici des feuilles). On compare de nouveau la valeur recherchée aux différentes valeurs (triées) du nœud : pour chaque intervalle de valeur, il existe un pointeur vers un autre nœud de l’arbre. Ici, 22 est plus grand que 12, on explore donc le nœud de droite au niveau inférieur.
• Un arbre B-tree peut bien évidemment avoir une profondeur plus grande, auquel cas l’étape précédente est répétée.
• Une fois arrivé sur une feuille, il suffit de la parcourir pour récupérer l’ensemble des positions physiques des lignes correspondants au critère. Ici, la feuille nous indique qu’à la valeur 22 correspondent deux lignes aux positions 2 et 17. Lorsque la valeur recherchée est supérieure ou égale à la plus grande valeur du bloc, PostgreSQL va également lire le bloc suivant. Ce cas de figure peut se produire si PostgreSQL a divisé une feuille en deux avant ou même pendant la recherche que nous exécutons. Ce serait par exemple le cas si on cherchait la valeur 30.
• Pour trouver les valeurs de name, il faut aller chercher dans la table même les lignes aux positions trouvées dans l’index. D’autre part, les informations de visibilité des lignes doivent aussi être trouvées dans la table. (Il existe des cas où la recherche peut éviter cette dernière étape : ce sont les Index Only Scan.)

Même en parcourant les deux structures de données, si la valeur recherchée représente une assez petite fraction des lignes totales, le nombre d’accès disques sera donc fortement réduit. En revanche, au lieu d’effectuer des accès séquentiels (pour lesquels les disques durs classiques sont relativement performants), il faudra effectuer des accès aléatoires, en sautant d’une position sur le disque à une autre. Le choix est fait par l’optimiseur.

Supposons désormais que nous souhaitions exécuter une requête sans filtre, mais exigeant un tri, du type :

SELECT id FROM ma_table ORDER BY id ;

L’index peut nous aider à répondre à cette requête. En effet, toutes les feuilles sont liées entre elles, et permettent ainsi un parcours ordonné. Il nous suffit donc de localiser la première feuille (la plus à gauche), et pour chaque clé, récupérer les lignes correspondantes. Une fois les clés de la feuille traitées, il suffit de suivre le pointeur vers la feuille suivante et de recommencer.

L’alternative consisterait à parcourir l’ensemble de la table, et trier toutes les lignes afin de les obtenir dans le bon ordre. Un tel tri peut être très coûteux, en mémoire comme en temps CPU. D’ailleurs, de tels tris débordent très souvent sur disque (via des fichiers temporaires) afin de ne pas garder l’intégralité des données en mémoire.

Pour les requêtes utilisant des opérateurs d’inégalité, on voit bien comment l’index peut là aussi être utilisé. Par exemple, pour la requête suivante :

SELECT * FROM ma_table WHERE id <= 10 AND id >= 4 ;

Il suffit d’utiliser la propriété de tri de l’index pour parcourir les feuilles, en partant de la borne inférieure, jusqu’à la borne supérieure.

Dernière remarque : ce schéma ne montre qu’une entrée d’index pour 22, bien qu’il pointe vers deux lignes. En fait, il y avait bien deux entrées pour 22 avant PostgreSQL 13. Depuis cette version, PostgreSQL sait dédupliquer les entrées pour économiser de la place.

Il est possible de créer un index sur plusieurs colonnes. Il faut néanmoins être conscient des requêtes supportées par un tel index. Admettons que l’on crée une table d’un million de lignes avec un index sur trois champs :

CREATE TABLE t1 (c1 int, c2 int, c3 int, c4 text);

INSERT INTO t1 (c1, c2, c3, c4)
SELECT i*10,j*5,k*20, 'text'||i||j||k
FROM generate_series (1,100) i
CROSS JOIN generate_series(1,100) j
CROSS JOIN generate_series(1,100) k ;

CREATE INDEX ON t1 (c1, c2, c3) ;

VACUUM ANALYZE t1 ;

-- Figer des paramètres pour l'exemple
SET max_parallel_workers_per_gather to 0;
SET seq_page_cost TO 1 ;
SET random_page_cost TO 4 ;

L’index est optimal pour répondre aux requêtes portant sur les premières colonnes de l’index :

EXPLAIN SELECT * FROM t1 WHERE c1 = 1000 and c2=500 and c3=2000 ;

                                QUERY PLAN
---------------------------------------------------------------------------
 Index Scan using t1_c1_c2_c3_idx on t1  (cost=0.42..8.45 rows=1 width=22)
   Index Cond: ((c1 = 1000) AND (c2 = 500) AND (c3 = 2000))

Et encore plus quand l’index permet de répondre intégralement au contenu de la requête :

EXPLAIN SELECT c1,c2,c3 FROM t1 WHERE c1 = 1000 and c2=500 ;

                                   QUERY PLAN
---------------------------------------------------------------------------------
 Index Only Scan using t1_c1_c2_c3_idx on t1  (cost=0.42..6.33 rows=95 width=12)
   Index Cond: ((c1 = 1000) AND (c2 = 500))

Mais si les premières colonnes de l’index ne sont pas spécifiées, alors l’index devra être parcouru en grande partie.

Cela reste plus intéressant que parcourir toute la table, surtout si l’index est petit et contient toutes les données du SELECT. Mais le comportement dépend alors de nombreux paramètres, comme les statistiques, les estimations du nombre de lignes ramenées et les valeurs relatives de seq_page_cost et random_page_cost :

SET random_page_cost TO 0.1 ; SET seq_page_cost TO 0.1 ;  -- SSD

EXPLAIN (ANALYZE,BUFFERS) SELECT * FROM t1 WHERE c3 = 2000 ;

                                   QUERY PLAN
---------------------------------------------------------------------------------
 Index Scan using t1_c1_c2_c3_idx on t1  (...) (...)
   Index Cond: (c3 = 2000)
   Buffers: shared hit=3899
 Planning:
   Buffers: shared hit=15
 Planning Time: 0.218 ms
 Execution Time: 67.081 ms

Noter que tout l’index a été lu.

Mais pour limiter les aller-retours entre index et table, PostgreSQL peut aussi décider d’ignorer l’index et de parcourir directement la table :

SET random_page_cost TO 4 ; SET seq_page_cost TO 1 ;  -- défaut (disque mécanique)

EXPLAIN (ANALYZE,BUFFERS) SELECT * FROM t1 WHERE c3 = 2000 ;

                                   QUERY PLAN
---------------------------------------------------------------------------------
Seq Scan on t1  (cost=0.00..18871.00 rows=9600 width=22) (...)
   Filter: (c3 = 2000)
   Rows Removed by Filter: 990000
   Buffers: shared hit=6371
 Planning Time: 0.178 ms
 Execution Time: 114.572 ms

Concernant les range scans (requêtes impliquant des opérateurs d’inégalité, tels que <, <=, >=, >), celles-ci pourront être satisfaites par l’index de manière quasi optimale si les opérateurs d’inégalité sont appliqués sur la dernière colonne requêtée, et de manière sub-optimale s’ils portent sur les premières colonnes.

Cet index pourra être utilisé pour répondre aux requêtes suivantes de manière optimale :

SELECT * FROM t1 WHERE c1 = 20 ;
SELECT * FROM t1 WHERE c1 = 20 AND c2 = 50 AND c3 = 400 ;
SELECT * FROM t1 WHERE c1 = 10 AND c2 <= 4 ;

Il pourra aussi être utilisé, mais de manière bien moins efficace, pour les requêtes suivantes, qui bénéficieraient d’un index sur un ordre alternatif des colonnes :

SELECT * FROM t1 WHERE c1 = 100 AND c2 >= 80 AND c3 = 40 ;
SELECT * FROM t1 WHERE c1 < 100 AND c2 = 100 ;

Le plan de cette dernière requête est :

 Bitmap Heap Scan on t1  (cost=2275.98..4777.17 rows=919 width=22) (...)
   Recheck Cond: ((c1 < 100) AND (c2 = 100))
   Heap Blocks: exact=609
   Buffers: shared hit=956
   ->  Bitmap Index Scan on t1_c1_c2_c3_idx  (cost=0.00..2275.76 rows=919 width=0) (...)
         Index Cond: ((c1 < 100) AND (c2 = 100))
         Buffers: shared hit=347
 Planning Time: 0.227 ms
 Execution Time: 15.596 ms

Les index multicolonnes peuvent aussi être utilisés pour le tri comme dans les exemples suivants. Il n’y a pas besoin de trier (ce peut être très coûteux) puisque les données de l’index sont triées. Ici le cas est optimal puisque l’index contient toutes les données nécessaires :

SELECT * FROM t1 ORDER BY c1 ;
SELECT * FROM t1 ORDER BY c1, c2 ;
SELECT * FROM t1 ORDER BY c1, c2, c3 ;

Le plan de cette dernière requête est :

 Index Scan using t1_c1_c2_c3_idx on t1  (cost=0.42..55893.66 rows=1000000 width=22) (...)
   Buffers: shared hit=1003834
 Planning Time: 0.282 ms
 Execution Time: 425.520 ms

Il est donc nécessaire d’avoir une bonne connaissance de l’application (ou de passer du temps à observer les requêtes consommatrices) pour déterminer comment créer des index multicolonnes pertinents pour un nombre maximum de requêtes.

L’optimiseur a le choix entre plusieurs parcours pour utiliser un index, principalement suivant la quantité d’enregistrements à récupérer :

Index Scan

Un Index Scan est optimal quand il y a peu d’enregistrements à récupérer. Noter qu’il comprend l’accès à l’index et celui à la table ensuite.

Bitmap Scan

Le Bitmap Scan est utile quand il y a plus de lignes, ou quand on veut lire plusieurs index d’une même table pour satisfaire plusieurs conditions de filtre.

Il se décompose en deux nœuds : un Bitmap Index Scan qui récupère des blocs d’index, et un Bitmap Heap Scan qui va chercher les blocs dans la table.

Typiquement, ce nœud servira pour des recherches de plages de valeurs ou de grandes quantités de lignes.

Index Only Scan

L’Index Only Scan est utile quand les champs de la requête correspondent aux colonnes de l’index. Ce nœud permet d’éviter la lecture de tout ou partie de la table et est donc très performant.

Autre intérêt de l’Index Only Scan : les enregistrements cherchés sont contigus dans l’index (puisqu’il est trié), et le nombre d’accès disque est bien plus faible. Il est tout à fait possible d’obtenir dans des cas extrêmes des gains de l’ordre d’un facteur 10 000.

Si peu de champs de la table sont impliqués dans la requête, il faut penser à viser un Index Only Scan.

Parallélisation

Chacun de ses nœuds a une version parallélisable si l’index est assez grand et que l’optimiseur pense que paralléliser est utile. Il apparaît alors un nœud Gather pour rassembler les résultats des différents workers.

La première chose à garder en tête est que l’on indexe pas le schéma de données, c’est-à-dire les tables, mais en fonction de la charge de travail supportée par la base, c’est-à-dire les requêtes. En effet, comme nous l’avons vu précédemment, tout index superflu a un coût global pour la base de données, notamment pour les opérations DML.

La méthodologie elle-même est assez simple. Selon le principe qu’un index sert à une (ou des) requête(s), la première chose à faire consiste à identifier celle(s)-ci. L’équipe de développement est dans une position idéale pour réaliser ce travail : elle seule peut connaître le fonctionnement global de l’application, et donc les colonnes qui vont être utilisées, ensemble ou non, comme cible de filtres ou de tris. Au delà de la connaissance de l’application, il est possible d’utiliser des outils tels que pgBadger, pg_stat_statements et PoWA pour identifier les requêtes particulièrement consommatrices, et qui pourraient donc potentiellement nécessiter un index. Ces outils seront présentés plus loin dans cette formation.

Une fois les requêtes identifiées, il est nécessaire de trouver les index permettant d’améliorer celles-ci. Ils peuvent être utilisés pour les opérations de filtrage (clause WHERE), de tri (clauses ORDER BY, GROUP BY) ou de jointures. Idéalement, l’étude portera sur l’ensemble des requêtes, afin notamment de pouvoir décider d’index multicolonnes pertinents pour le plus grand nombre de requêtes, et éviter ainsi de créer des index redondants.

De manière générale, l’ensemble des colonnes étant la source d’une clé étrangère devraient être indexées, et ce pour deux raisons.

La première concerne les jointures. Généralement, lorsque deux tables sont liées par des clés étrangères, il existe au moins certaines requêtes dans l’application joignant ces tables. La colonne « cible » de la clé étrangère est nécessairement indexée, c’est un prérequis dû à la contrainte unique nécessaire à celle-ci. Il est donc possible de la parcourir de manière triée.

La colonne source devrait être indexée elle aussi : en effet, il est alors possible de la parcourir de manière ordonnée, et donc de réaliser la jointure selon l’algorithme Merge Join (comme vu lors du module sur les plans d’exécution), et donc d’être beaucoup plus rapide. Un tel index accélérera de la même manière les Nested Loop, en permettant de parcourir l’index une fois par ligne de la relation externe au lieu de parcourir l’intégralité de la table.

De la même manière, pour les DML sur la table cible, cet index sera d’une grande aide : pour chaque ligne modifiée ou supprimée, il convient de vérifier, soit pour interdire soit pour « cascader » la modification, la présence de lignes faisant référence à celle touchée.

S’il n’y a qu’une règle à suivre aveuglément ou presque, c’est bien celle-ci : les colonnes faisant partie d’une clé étrangère doivent être indexées !

Deux exceptions : les champs ayant une cardinalité très faible et homogène (par exemple, un champ homme/femme dans une population équilibrée) ; et ceux dont on constate l’inutilité après un certain temps, par des valeurs à zéro dans pg_stat_user_indexes.

C’est l’optimiseur SQL qui choisit si un index doit ou non être utilisé. Il est tout à fait possible que PostgreSQL décide qu’utiliser un index donné n’en vaut pas la peine par rapport à d’autres chemins. Il faut aussi savoir identifier les cas où l’index ne peut pas être utilisé.

L’optimiseur possède forcément quelques limitations. Certaines sont un compromis par rapport au temps que prendrait la recherche systématique de toutes les optimisations imaginables. Il y aussi le problème des estimations de volumétries, qui sont d’autant plus difficiles que la requête est complexe.

Quant à un vrai bug, si le cas peut être reproduit, il doit être remonté aux développeurs de PostgreSQL. D’expérience, c’est rarissime.

Il existe plusieurs raisons pour que PostgreSQL néglige un index.

Sélectivité trop faible, trop de lignes :

Comme vu précédemment, le parcours d’un index implique à la fois des lectures sur l’index, et des lectures sur la table. Au contraire d’une lecture séquentielle de la table (Seq Scan), l’accès aux données via l’index nécessite des lectures aléatoires. Ainsi, si l’optimiseur estime que la requête nécessitera de parcourir une grande partie de la table, il peut décider de ne pas utiliser l’index : l’utilisation de celui-ci serait alors trop coûteux.

Autrement dit, l’index n’est pas assez discriminant pour que ce soit la peine de faire des allers-retours entre lui et la table. Le seuil dépend entre autres des volumétries de la table et de l’index et du rapport entre les paramètres random_page_cost et seq_page_cost (respectivement 4 et 1 pour un disque dur classique peu rapide, et souvent 1 et 1 pour du SSD, voire moins).

Il y a un meilleur chemin :

Un index sur un champ n’est qu’un chemin parmi d’autres, en aucun cas une obligation, et une requête contient souvent plusieurs critères sur des tables différentes. Par exemple, un index sur un filtre peut être ignoré si un autre index permet d’éviter un tri coûteux, ou si l’optimiseur juge que faire une jointure avant de filtrer le résultat est plus performant.

Index redondant :

Il existe un autre index doublant la fonctionnalité de celui considéré. PostgreSQL favorise naturellement un index plus petit, plus rapide à parcourir. À l’inverse, un index plus complet peut favoriser plusieurs filtres, des tris, devenir couvrant…

VACUUM trop ancien :

Dans le cas précis des Index Only Scan, si la table n’a pas été récemment nettoyée, il y aura trop d’allers-retours avec la table pour vérifier les informations de visibilité (heap fetches). Un VACUUM permet de mettre à jour la Visibility Map pour éviter cela.

Statistiques périmées :

Il peut arriver que l’optimiseur se trompe quand il ignore un index. Des statistiques périmées sont une cause fréquente. Pour les rafraîchir :

ANALYZE (VERBOSE) nom_table;

Si cela résout le problème, ce peut être un indice que l’autovacuum ne passe pas assez souvent (voir pg_stat_user_tables.last_autoanalyze). Il faudra peut-être ajuster les paramètres autovacuum_analyze_scale_factor ou autovacuum_analyze_threshold sur les tables.

Statistiques pas assez fines :

Les statistiques sur les données peuvent être trop imprécises. Le défaut est un histogramme de 100 valeurs, basé sur 300 fois plus de lignes. Pour les grosses tables, augmenter l’échantillonnage sur les champs aux valeurs peu homogènes est possible :

ALTER TABLE ma_table ALTER ma_colonne SET STATISTICS 500 ;

La valeur 500 n’est qu’un exemple. Monter beaucoup plus haut peut pénaliser les temps de planification. Ce sera d’autant plus vrai si on applique cette nouvelle valeur globalement, donc à tous les champs de toutes les tables (ce qui est certes le plus facile).

Estimations de volumétries trompeuses :

Par exemple, une clause WHERE sur deux colonnes corrélées (ville et code postal par exemple), mène à une sous-estimation de la volumétrie résultante par l’optimiseur, car celui-ci ignore le lien entre les deux champs. Vous pouvez demander à PostgreSQL de calculer cette corrélation avec l’ordre CREATE STATISTICS (voir le module de formation J2 ou la documentation officielle).

Compatibilité :

Il faut toujours s’assurer que la requête est écrite correctement et permet l’utilisation de l’index.

Un index peut être inutilisable à cause d’une fonction plus ou moins explicite, ou encore d’un mauvais typage. Il arrive que le critère de filtrage ne peut remonter sur la table indexée à cause d’un CTE matérialisé (explicitement ou non), d’un DISTINCT, ou d’une vue complexe.

Nous allons voir quelques problèmes classiques.

Voici quelques exemples d’index incompatible avec la clause WHERE :

Mauvais type :

Cela peut paraître contre-intuitif, mais certains transtypages ne permettent pas de garantir que les résultats d’un opérateur (par exemple l’égalité) seront les mêmes si les arguments sont convertis dans un type ou dans l’autre. Cela dépend des types et du sens de conversion. Dans les exemples suivants, le champ client_id est de type bigint. PostgreSQL réussit souvent à convertir, mais ce n’est pas toujours parfait.

EXPLAIN (COSTS OFF) SELECT * FROM clients WHERE client_id = 3 ;

                         QUERY PLAN
-------------------------------------------------------------
 Index Scan using clients_pkey on clients
   Index Cond: (client_id = 3)

EXPLAIN (COSTS OFF) SELECT * FROM clients WHERE client_id = 3::numeric;

                         QUERY PLAN
-------------------------------------------------------------
 Seq Scan on clients
   Filter: ((client_id)::numeric = '3'::numeric)

EXPLAIN (COSTS OFF) SELECT * FROM clients WHERE client_id = 3::int;

                         QUERY PLAN
-------------------------------------------------------------
 Index Scan using clients_pkey on clients
   Index Cond: (client_id = 3)

EXPLAIN (COSTS OFF) SELECT * FROM clients WHERE client_id = '003';

                         QUERY PLAN
-------------------------------------------------------------
 Index Scan using clients_pkey on clients
   Index Cond: (client_id = '3'::bigint)

De même, les conversions entre date et timestamp/timestamptz se passent généralement bien.

Autres exemples :

• Dans une jointure, si les deux champs joints n’ont pas le même type, il est possible que de simples index ne soient pas utilisables, ou un seul d’entre eux. Il faudra corriger l’incohérence, ou créer des index fonctionnels incluant le transtypage.
• Un index B-tree sur un tableau ou un JSON ne peut servir pour une recherche sur un de ses éléments. Il faudra s’orienter vers un index plus spécialisé, par exemple GIN ou GiST.

Utilisation de fonction :

Si une fonction est appliquée sur la colonne à indexer, comme dans cet exemple classique :

SELECT * FROM ma_table WHERE to_char(ma_date, 'YYYY')='2014' ;

alors PostgreSQL n’utilisera pas l’index sur ma_date. Il faut réécrire la requête ainsi :

SELECT * FROM ma_table WHERE ma_date >='2014-01-01' AND ma_date<'2015-01-01' ;

Dans l’exemple suivant, on cherche les commandes dont la date tronquée au mois correspond au 1^er janvier, c’est-à-dire aux commandes dont la date est entre le 1^er et le 31 janvier. Pour un humain, la logique est évidente, mais l’optimiseur n’en a pas connaissance.

EXPLAIN ANALYZE
SELECT * FROM commandes
WHERE date_trunc('month', date_commande) = '2015-01-01';

                              QUERY PLAN
------------------------------------------------------------------------
Gather  (cost=1000.00..8160.96 rows=5000 width=51)
        (actual time=17.282..192.131 rows=4882 loops=1)
 Workers Planned: 3
 Workers Launched: 3
 ->  Parallel Seq Scan on commandes (cost=0.00..6660.96 rows=1613 width=51)
                           (actual time=17.338..177.896 rows=1220 loops=4)
     Filter: (date_trunc('month'::text,
                                    (date_commande)::timestamp with time zone)
                         = '2015-01-01 00:00:00+01'::timestamp with time zone)
     Rows Removed by Filter: 248780
 Planning time: 0.215 ms
 Execution time: 196.930 ms

Il faut plutôt écrire :

EXPLAIN ANALYZE
SELECT * FROM commandes
WHERE date_commande BETWEEN '2015-01-01' AND '2015-01-31' ;

                           QUERY PLAN
----------------------------------------------------------
 Index Scan using commandes_date_commande_idx on commandes
                                      (cost=0.42..118.82 rows=5554 width=51)
                               (actual time=0.019..0.915 rows=4882 loops=1)
   Index Cond: ((date_commande >= '2015-01-01'::date)
            AND (date_commande <= '2015-01-31'::date))
 Planning time: 0.074 ms
 Execution time: 1.098 ms

Dans certains cas, la réécriture est impossible (fonction complexe, code non modifiable…). Nous verrons qu’un index fonctionnel peut parfois être la solution.

Ces exemples semblent évidents, mais il peut être plus compliqué de trouver dans l’urgence la cause du problème dans une grande requête d’un schéma mal connu.

Si vous avez un index « normal » sur une chaîne texte, certaines recherches de type LIKE n’utiliseront pas l’index. En effet, il faut bien garder à l’esprit qu’un index est basé sur un opérateur précis. Ceci est généralement indiqué correctement dans la documentation, mais pas forcément très intuitif.

Si un opérateur non supporté pour le critère de tri est utilisé, l’index ne servira à rien :

CREATE INDEX ON fournisseurs (commentaire);
EXPLAIN ANALYZE SELECT * FROM fournisseurs WHERE commentaire LIKE 'ipsum%';

                            QUERY PLAN
---------------------------------------------------------------------
 Seq Scan on fournisseurs  (cost=0.00..225.00 rows=1 width=45)
                           (actual time=0.045..1.477 rows=47 loops=1)
   Filter: (commentaire ~~ 'ipsum%'::text)
   Rows Removed by Filter: 9953
 Planning time: 0.085 ms
 Execution time: 1.509 ms

Nous verrons qu’il existe d’autre classes d’opérateurs, permettant d’indexer correctement la requête précédente, et que varchar_pattern_ops est l’opérateur permettant d’indexer la requête précédente.

Dans le cas où un index a été construit avec la clause CONCURRENTLY, nous avons vu qu’il peut arriver que l’opération échoue et l’index existe mais reste invalide, et donc inutilisable. Le problème ne se pose pas pour un échec de REINDEX … CONCURRENTLY, car l’ancienne version de l’index est toujours là et utilisable.

Un index partiel est un index ne couvrant qu’une partie des enregistrements. Ainsi, l’index est beaucoup plus petit. En contrepartie, il ne pourra être utilisé que si sa condition est définie dans la requête.

Pour prendre un exemple simple, imaginons un système de « queue », dans lequel des événements sont entrés, et qui disposent d’une colonne traite indiquant si oui ou non l’événement a été traité. Dans le fonctionnement normal de l’application, la plupart des requêtes ne s’intéressent qu’aux événements non traités :

CREATE TABLE evenements (
    id int primary key,
    traite bool NOT NULL,
    type text NOT NULL,
    payload text
);

-- 10 000 événements traités
INSERT INTO evenements (id, traite, type) (
    SELECT i,
        true,
        CASE WHEN i % 3 = 0 THEN 'FACTURATION'
             WHEN i % 3 = 1 THEN 'EXPEDITION'
             ELSE 'COMMANDE'
        END
    FROM generate_series(1, 10000) as i);

-- et 10  non encore traités
INSERT INTO evenements (id, traite, type) (
    SELECT i,
        false,
        CASE WHEN i % 3 = 0 THEN 'FACTURATION'
             WHEN i % 3 = 1 THEN 'EXPEDITION'
             ELSE 'COMMANDE'
        END
    FROM generate_series(10001, 10010) as i);

\d evenements

                 Table « public.evenements »
 Colonne |  Type   | Collationnement | NULL-able | Par défaut
---------+---------+-----------------+-----------+------------
 id      | integer |                 | not null  |
 traite  | boolean |                 | not null  |
 type    | text    |                 | not null  |
 payload | text    |                 |           |
Index :
    "evenements_pkey" PRIMARY KEY, btree (id)

Typiquement, différents applicatifs vont être intéressés par des événements d’un certain type, mais les événements déjà traités ne sont quasiment jamais accédés, du moins via leur état (une requête portant sur traite IS true sera exceptionnelle et ramènera l’essentiel de la table : un index est inutile).

Ainsi, on peut souhaiter indexer le type d’événement, mais uniquement pour les événements non traités :

CREATE INDEX index_partiel on evenements (type) WHERE NOT traite ;

Si on recherche les événements dont le type est « FACTURATION », sans plus de précision, l’index ne peut évidemment pas être utilisé :

EXPLAIN SELECT * FROM evenements WHERE type = 'FACTURATION' ;

                            QUERY PLAN
----------------------------------------------------------------
 Seq Scan on evenements  (cost=0.00..183.12 rows=50 width=69)
   Filter: (type = 'FACTURATION'::text)

En revanche, si la condition sur l’état de l’événement est précisée, l’index sera utilisé :

EXPLAIN SELECT * FROM evenements WHERE type = 'FACTURATION' AND NOT traite ;

                                 QUERY PLAN
----------------------------------------------------------------------------
 Bitmap Heap Scan on evenements  (cost=8.22..54.62 rows=25 width=69)
   Recheck Cond: ((type = 'FACTURATION'::text) AND (NOT traite))
   ->  Bitmap Index Scan on index_partiel  (cost=0.00..8.21 rows=25 width=0)
         Index Cond: (type = 'FACTURATION'::text)

Sur ce jeu de données, on peut comparer la taille de deux index, partiels ou non :

CREATE INDEX index_complet ON evenements (type);

SELECT idxname, pg_size_pretty(pg_total_relation_size(idxname::text))
FROM (VALUES ('index_complet'), ('index_partiel')) as a(idxname);

    idxname    | pg_size_pretty
---------------+----------------
 index_complet | 88 kB
 index_partiel | 16 kB

Un index composé sur (is_traite,type) serait efficace, mais inutilement gros.

Clauses de requête et clause d’index :

Par exemple, dans les requêtes précédentes, un critère traite IS FALSE à la place de NOT traite n’utilise pas l’index (en effet, il ne s’agit pas du même critère à cause de NULL : NULL = false renvoie NULL, mais NULL IS false renvoie false).

Par contre, des conditions mathématiquement plus restreintes que l’index permettent son utilisation :

CREATE INDEX commandes_recentes_idx
ON commandes (client_id) WHERE date_commande > '2015-01-01' ;

EXPLAIN (COSTS OFF) SELECT * FROM commandes
WHERE date_commande > '2016-01-01' AND client_id = 17 ;

                      QUERY PLAN                      
------------------------------------------------------
 Index Scan using commandes_recentes_idx on commandes
   Index Cond: (client_id = 17)
   Filter: (date_commande > '2016-01-01'::date)

Mais cet index partiel ne sera pas utilisé pour un critère précédant 2015.

De la même manière, si un index partiel contient une liste de valeurs, IN ()ou NOT IN (), il est en principe utilisable :

CREATE INDEX commandes_1_3 ON commandes (numero_commande)
WHERE  mode_expedition IN (1,3);

EXPLAIN (COSTS OFF) SELECT * FROM commandes WHERE mode_expedition = 1 ;

                 QUERY PLAN                  
---------------------------------------------
 Index Scan using commandes_1_3 on commandes
   Filter: (mode_expedition = 1)

DROP INDEX commandes_1_3 ;

CREATE INDEX commandes_not34 ON commandes (numero_commande)
WHERE  mode_expedition NOT IN (3,4);

EXPLAIN (COSTS OFF) SELECT * FROM commandes WHERE mode_expedition = 1 ;

                  QUERY PLAN                   
-----------------------------------------------
 Index Scan using commandes_not34 on commandes
   Filter: (mode_expedition = 1)

DROP INDEX commandes_not34 ;

Le cas typique d’utilisation d’un index partiel est celui de l’exemple précédent : une application avec des données chaudes, fréquemment accédées et traitées, et des données froides, qui sont plus destinées à de l’historisation ou de l’archivage. Par exemple, un système de vente en ligne aura probablement intérêt à disposer d’index sur les commandes dont l’état est différent de clôturé : en effet, un tel système effectuera probablement des requêtes fréquemment sur les commandes qui sont en cours de traitement, en attente d’expédition, en cours de livraison mais très peu sur des commandes déjà livrées, qui ne serviront alors plus qu’à de l’analyse statistique.

De manière générale, tout système est susceptible de bénéficier des index partiels s’il doit gérer des données à état dont seul un sous-ensemble de ces états est activement exploité par les requêtes à optimiser. Par exemple, toujours sur cette même table, des requêtes visant à faire des statistiques sur les expéditions pourraient tirer parti de cet index :

CREATE INDEX index_partiel_expes ON evenements (id) WHERE type = 'EXPEDITION' ;

EXPLAIN SELECT count(id) FROM evenements WHERE type = 'EXPEDITION' ;

                                 QUERY PLAN                                              
----------------------------------------------------------------------------------
 Aggregate  (cost=106.68..106.69 rows=1 width=8)
   ->  Index Only Scan using index_partiel_expes on evenements  (cost=0.28..98.34 rows=3337 width=4)

Nous avons mentionné précédemment qu’un index est destiné à satisfaire une requête ou un ensemble de requêtes. Donc, si une requête présente fréquemment des critères de ce type :

WHERE une_colonne = un_parametre_variable
  AND une_autre_colonne = une_valeur_fixe

alors il peut être intéressant de créer un index partiel pour les lignes satisfaisant le critère :

WHERE une_autre_colonne = une_valeur_fixe

Ces critères sont généralement très liés au fonctionnel de l’application : du point de vue de l’exploitation, il est souvent difficile d’identifier des requêtes dont une valeur est toujours fixe. Encore une fois, l’appropriation des techniques d’indexation par l’équipe de développement permet d’améliorer grandement les performances de l’application.

En général, un index partiel doit indexer une colonne différente de celle qui est filtrée (et donc connue). Ainsi, dans l’exemple précédent, la colonne indexée (type) n’est pas celle de la clause WHERE. On pose un critère, mais on s’intéresse aux types d’événements ramenés. Un autre index partiel pourrait porter sur id WHERE NOT traite pour simplement récupérer une liste des identifiants non traités de tous types.

L’intérêt est d’obtenir un index très ciblé et compact, et aussi d’économiser la place disque et la charge CPU de maintenance. Il faut tout de même que les index partiels soient notablement plus petits que les index « génériques » (au moins de moitié). Avec des index partiels spécialisés, il est possible de « précalculer » certaines requêtes critiques en intégrant leurs critères de recherche exacts.

À partir du moment où une clause WHERE applique une fonction sur une colonne, un index sur la colonne ne permet plus un accès à l’enregistrement.

C’est comme demander à un dictionnaire Anglais vers Français : « Quels sont les mots dont la traduction en français est ‘fenêtre’ ? ». Le tri du dictionnaire ne correspond pas à la question posée. Il nous faudrait un index non plus sur les mots anglais, mais sur leur traduction en français.

C’est exactement ce que font les index fonctionnels : ils indexent le résultat d’une fonction appliquée à l’enregistrement.

L’exemple classique est l’indexation insensible à la casse : on crée un index sur UPPER (ou LOWER) de la chaîne à indexer, et on recherche les mots convertis à la casse souhaitée.

Il est facile de créer involontairement des critères comportant des fonctions, notamment avec des conversions de type ou des manipulations de dates. Il a été vu plus haut qu’il vaut mieux placer la transformation du côté de la constante. Par exemple, la requête suivante retourne toutes les commandes de l’année 2011, mais la fonction extract est appliquée à la colonne date_commande (type date) et l’index est inutilisable.

L’optimiseur ne peut donc pas utiliser un index :

CREATE INDEX ON commandes (date_commande) ;

EXPLAIN (COSTS OFF) SELECT * FROM commandes
WHERE extract('year' from date_commande) = 2011;

                              QUERY PLAN
--------------------------------------------------------------------------
 Gather
   Workers Planned: 2
   ->  Parallel Seq Scan on commandes
         Filter: (EXTRACT(year FROM date_commande) = '2011'::numeric)

En réécrivant le prédicat, l’index est bien utilisé :

EXPLAIN (COSTS OFF) SELECT * FROM commandes
WHERE date_commande BETWEEN '2011-01-01'::date AND '2011-12-31'::date;

                              QUERY PLAN
--------------------------------------------------------------------------
 Index Scan using commandes_date_commande_idx on commandes
   Index Cond: ((date_commande >= '2011-01-01'::date) AND (date_commande <= '2011-12-31'::date))

C’est la solution la plus propre.

Mais dans d’autres cas, une telle réécriture de la requête sera impossible ou très délicate. On peut alors créer un index fonctionnel, dont la définition doit être strictement celle du WHERE :

CREATE INDEX annee_commandes_idx ON commandes( extract('year' from date_commande) ) ;

EXPLAIN (COSTS OFF) SELECT * FROM commandes
WHERE extract('year' from date_commande) = 2011;

                              QUERY PLAN
--------------------------------------------------------------------------
 Bitmap Heap Scan on commandes
   Recheck Cond: (EXTRACT(year FROM date_commande) = '2011'::numeric)
   ->  Bitmap Index Scan on annee_commandes_idx
         Index Cond: (EXTRACT(year FROM date_commande) = '2011'::numeric)

Ceci fonctionne si date_commande est de type date ou timestamp without timezone.

Fonction immutable :

Cependant, n’importe quelle fonction d’indexation n’est pas utilisable, ou pas pour tous les types. La fonction d’indexation doit être notée IMMUTABLE : cette propriété indique à PostgreSQL que la fonction retournera toujours le même résultat quand elle est appelée avec les mêmes arguments.

En d’autres termes : le résultat de la fonction ne doit dépendre :

• ni du contenu de la base (pas de SELECT donc) ;
• ni de la configuration, ni de l’environnement (variables d’environnement, paramètres de session, fuseau horaire, formatage…) ;
• ni du temps (now() ou clock_timestamp() sont interdits, et indirectement les calculs d’âge) ;
• ni d’une autre fonction non-déterministe (comme random()) ou plus généralement non immutable.

Sans ces restrictions, l’endroit dans lequel la donnée est insérée dans l’index serait potentiellement différent à chaque exécution, ce qui est évidemment incompatible avec la notion d’indexation.

Pour revenir à l’exemple précédent : pour calculer l’année, on peut aussi imaginer un index avec la fonction to_char, une autre fonction hélas fréquemment utilisée pour les conversions de date. Au moment de la création d’un tel index, PostgreSQL renvoie l’erreur suivante :

CREATE INDEX annee_commandes_idx2
ON commandes ((to_char(date_commande,'YYYY')::int));

ERROR:  functions in index expression must be marked IMMUTABLE

En effet, to_char() n’est pas immutable, juste « stable » et cela dans toutes ses variantes :

magasin=# \df+ to_char
                                    Liste des fonctions
…  Nom   |…résultat|  Type de données des paramètres  |…|Volatibilité|…
+--------+---------+----------------------------------+-+------------+-
…to_char | text    | bigint, text                     | | stable     |…
…to_char | text    | double precision, text           | | stable     |…
…to_char | text    | integer, text                    | | stable     |…
…to_char | text    | interval, text                   | | stable     |…
…to_char | text    | numeric, text                    | | stable     |…
…to_char | text    | real, text                       | | stable     |…
…to_char | text    | timestamp without time zone, text| | stable     |…
…to_char | text    | timestamp with time zone, text   | | stable     |…
(8 lignes)

La raison est que to_date accepte des paramètres de formatage qui dépendent de la session (nom du mois, virgule ou point décimal…). Ce n’est pas une très bonne fonction pour convertir une date ou heure en nombre.

La fonction extract, elle, est bien immutable quand il s’agit de convertir commande.date_commande de date vers une année, comme dans l’exemple plus haut.

 \sf extract (text, date)
CREATE OR REPLACE FUNCTION pg_catalog."extract"(text, date)
 RETURNS numeric
 LANGUAGE internal
 IMMUTABLE PARALLEL SAFE STRICT
AS $function$extract_date$function$

De même, extract est immutable avec une entrée de type timestamp without time zone.

Les choses se compliquent si l’on manipule des heures avec fuseau horaire. En effet, il est conseillé de toujours privilégier la variante timestamp with time zone. Cette fois, l’index fonctionnel basé avec extract va poser problème :

DROP INDEX annee_commandes_idx ;
-- Nouvelle table d'exemple avec date_commande comme timestamp with time zone
-- La conversion introduit implicitement le fuseau horaire de la session
CREATE TABLE commandes2 (LIKE commandes INCLUDING ALL);
ALTER TABLE  commandes2 ALTER COLUMN date_commande TYPE timestamp with time zone ;
INSERT INTO  commandes2 SELECT * FROM commandes ;
-- Reprise de l'index fonctionnel précédent
CREATE INDEX annee_commandes2_idx
ON commandes2(extract('year' from date_commande) ) ;

ERROR:  functions in index expression must be marked IMMUTABLE

En effet la fonction extract n’est pas immutable pour le type timestamp with time zone :

magasin=# \sf extract (text, timestamp with time zone)
CREATE OR REPLACE FUNCTION pg_catalog."extract"(text, timestamp with time zone)
 RETURNS numeric
 LANGUAGE internal
 STABLE PARALLEL SAFE STRICT
AS $function$extract_timestamptz$function$

Pour certains timestamps autour du Nouvel An, l’année retournée dépend du fuseau horaire. Le problème se poserait bien sûr aussi si l’on extrayait les jours ou les mois.

Il est possible de « tricher » en figeant le fuseau horaire dans une fonction pour obtenir un type intermédiaire timestamp without time zone, qui ne posera pas de problème :

CREATE INDEX annee_commandes2_idx
ON commandes2(extract('year' from (
  date_commande AT TIME ZONE 'Europe/Paris' )::timestamp
  )) ;

Ce contournement impose de modifier le critère de la requête. Tant qu’on y est, il peut être plus clair d’enrober l’appel dans une fonction que l’on définira immutable.

CREATE OR REPLACE FUNCTION annee_paris (t timestamptz)
RETURNS int
AS $$
    SELECT extract ('year' FROM (t AT TIME ZONE 'Europe/Paris')::timestamp) ;
$$ LANGUAGE sql 
IMMUTABLE ;

CREATE INDEX annee_commandes2_paris_idx ON commandes2 (annee_paris (date_commande));
VACUUM ANALYZE commandes2 ;

EXPLAIN (COSTS OFF)
SELECT * FROM commandes2
WHERE annee_paris (date_commande) = 2021 ;

                              QUERY PLAN
--------------------------------------------------------------------------
 Index Scan using annee_commandes2_paris_idx on commandes2
   Index Cond: ((EXTRACT(year FROM (date_commande AT TIME ZONE 'Europe/Paris'::text)))::integer = 2021)

Le nom de la fonction est aussi une indication pour les utilisateurs dans d’autres fuseaux.

Certes, on a ici modifié le code de la requête, mais il est parfois possible de contourner ce problème en passant par des vues qui masquent la fonction.

Signalons enfin la fonction date_part : c’est une alternative possible à extract, avec les mêmes soucis et contournement.

À partir de PostgreSQL 16, une autre possibilité existe avec date_trunc car la variante avec timestamp without time zoneest devenue immutable :

CREATE INDEX annee_commandes2_paris_idx3
ON commandes2 ( (date_trunc ( 'year', date_commande, 'Europe/Paris')) );
ANALYZE commandes2 ;

EXPLAIN (COSTS OFF)
SELECT * FROM commandes2
WHERE date_trunc('year', date_commande, 'Europe/Paris') = '2021-01-01'::timestamptz;

                              QUERY PLAN
--------------------------------------------------------------------------
 Index Scan using annee_commandes2_paris_idx3 on commandes2
   Index Cond: (date_trunc('year'::text, date_commande, 'Europe/Paris'::text) = '2021-01-01 00:00:00+01'::timestamp with time zone)

Index Only Scan :

Obtenir un Index Only Scan est une optimisation importante pour les requêtes critiques avec peu de champs sur la table. Hélas, en raison d’une limitation du planificateur, les index fonctionnels ne donnent pas lieu à un Index Only Scan :

EXPLAIN (COSTS OFF)
SELECT annee_paris (date_commande) FROM commandes2
WHERE annee_paris (date_commande) > 2021 ;

                              QUERY PLAN
--------------------------------------------------------------------------
 Index Scan using annee_commandes2_paris_idx on commandes2
   Index Cond: ((EXTRACT(year FROM (date_commande AT TIME ZONE 'Europe/Paris'::text)))::integer > 2021)

Plus insidieusement, le planificateur peut choisir un Index Only Scan… sur la colonne sur laquelle porte la fonction !

EXPLAIN SELECT count( annee_paris(date_commande) ) FROM commandes2 ;

                              QUERY PLAN
--------------------------------------------------------------------------
  Aggregate  (cost=28520.40..28520.41 rows=1 width=8)
   ->  Index Only Scan using commandes2_date_commande_idx on commandes2  (cost=0.42..18520.41 rows=999999 width=8)

Ce qui entraîne au moins un gaspillage de CPU pour réexécuter les fonctions sur chaque ligne.

Sacrifier un peu d’espace disque pour une colonne générée et son index (non fonctionnel) peut s’avérer une solution :

-- Attention, cette commande réécrit la table
ALTER TABLE commandes2 ADD COLUMN annee_paris smallint
  GENERATED ALWAYS  AS ( annee_paris (date_commande) ) STORED ;
CREATE INDEX commandes2_annee_paris_idx ON commandes2 (annee_paris) ;
-- Prise en compte des statistiques et des lignes mortes sur la table réécrite
VACUUM ANALYZE commandes2;

EXPLAIN SELECT count( annee_paris ) FROM commandes2 ;

                              QUERY PLAN
--------------------------------------------------------------------------
 Finalize Aggregate  (cost=14609.10..14609.11 rows=1 width=8)
   ->  Gather  (cost=14608.88..14609.09 rows=2 width=8)
         Workers Planned: 2
         ->  Partial Aggregate  (cost=13608.88..13608.89 rows=1 width=8)
               ->  Parallel Index Only Scan using commandes2_annee_paris_idx on commandes2  (cost=0.42..12567.20 rows=416672 width=2)

Statistiques :

Après la création de l’index fonctionnel, un ANALYZE nom_table est conseillé : en effet, l’optimiseur ne peut utiliser les statistiques déjà connues pour le résultat d’une fonction. Par contre, PostgreSQL peut créer des statistiques sur le résultat de la fonction pour chaque ligne. Ces statistiques seront visibles dans la vue système pg_stats (tablename contient le nom de l’index, et non celui de la table !).

Ces statistiques à jour sont d’ailleurs un des intêrêts de l’index fonctionnel, même si l’index lui-même est superflu. Dans ce cas, à partir de PostgreSQL 14, on pourra utiliser CREATE STATISTICS sur l’expression pour ne pas avoir à créer et maintenir un index entier.

Avertissements :

Principe des index couvrants

Un index couvrant (covering index) cherche à favoriser le nœud d’accès le plus rapide, l’Index Only Scan : il contient non seulement les champs servant de critères de recherche, mais aussi tous les champs résultats. Ainsi, il n’y a plus besoin d’interroger la table.

Les index couvrants peuvent être explicitement déclarés avec la clause INCLUDE :

CREATE TABLE t (id int NOT NULL, valeur int) ;

INSERT INTO t SELECT i, i*50 FROM generate_series(1,1000000) i;

CREATE UNIQUE INDEX t_pk ON t (id) INCLUDE (valeur) ;

VACUUM t ;

EXPLAIN ANALYZE SELECT valeur FROM t WHERE id = 555555 ;

                               QUERY PLAN
--------------------------------------------------------------------------------
 Index Only Scan using t_pk on t  (cost=0.42..1.44 rows=1 width=4)
                                  (actual time=0.034..0.035 rows=1 loops=1)
   Index Cond: (id = 555555)
   Heap Fetches: 0
 Planning Time: 0.084 ms
 Execution Time: 0.065 ms

Dans cet exemple, il n’y a pas eu d’accès à la table. L’index est unique mais contient aussi la colonne valeur.

Par abus de langage, on peut dire d’un index multicolonne sans clause INCLUDE qu’il est « couvrant » s’il répond complètement à la requête.

Dans les versions antérieures à la 11, on émulait cette fonctionnalité en incluant les colonnes dans des index multicolonne :

CREATE INDEX t_idx ON t (id, valeur) ;

Cette technique reste tout à fait valable dans les versions suivantes, car l’index multicolonne (complètement trié) peut servir de manière optimale à d’autres requêtes. Il peut même être plus petit que celui utilisant INCLUDE.

Un intérêt de la clause INCLUDE est de se greffer sur des index uniques ou de clés et d’économiser un nouvel index et un peu de place. Accessoirement, il évite le tri des champs dans la clause INCLUDE.

Inconvénients & limitation des index couvrants

Il faut garder à l’esprit que l’ajout de colonnes à un index (couvrant ou multicolonne) augmente sa taille. Cela peut avoir un impact sur les performances des requêtes qui n’utilisent pas les colonnes supplémentaires. Il faut également être vigilant à ce que la taille des enregistrements avec les colonnes incluses ne dépassent pas 2,6 ko. Au-delà de cette valeur, les insertions ou mises à jour échouent.

Enfin, la déduplication (apparue en version 13) n’est pas active sur les index couvrants, ce qui a un impact supplémentaire sur la taille de l’index sur le disque et en cache. Ça n’a pas trop d’importance si l’index principal contient surtout des valeurs différentes, mais s’il y en a beaucoup moins que de lignes, il serait dommage de perdre l’intérêt de la déduplication. Là encore, le planificateur peut ignorer l’index s’il est trop gros. Il faut tester avec les données réelles, et comparer avec un index multicolonne (dédupliqué).

Les méthodes d’accès aux index doivent inclure le support de cette fonctionnalité. C’est le cas pour le B-tree ou le GiST, et pour le SP-GiST en version 14.

Un opérateur sert à indiquer à PostgreSQL comment il doit manipuler un certain type de données. Il y a beaucoup d’opérateurs par défaut, mais il est parfois possible d’en prendre un autre.

Pour l’indexation, il est notamment possible d’utiliser un jeu « alternatif » d’opérateurs de comparaison.

Le cas d’utilisation le plus fréquent dans PostgreSQL est la comparaison de chaîne LIKE 'chaine%'. L’indexation texte « classique » utilise la collation par défaut de la base (en France, généralement fr_FR.UTF-8 ou en_US.UTF-8) ou la collation de la colonne de la table si elle diffère. Cette collation contient des notions de tri. Les règles sont différentes pour chaque collation. Et ces règles sont complexes.

Par exemple, le ß allemand se place entre ss et t (et ce, même en français). En danois, le tri est très particulier car le å et le aa apparaissent après le z.

-- Cette collation doit exister sur le système
CREATE COLLATION IF NOT EXISTS "da_DK" (locale='da_DK.utf8');

WITH ls(x) AS (VALUES ('aa'),('å'),('t'),('s'),('ss'),('ß'), ('zz') )
SELECT * FROM ls ORDER BY x COLLATE "da_DK";

 x
----
 s
 ss
 ß
 t
 zz
 å
 aa

Il faut être conscient que cela a une influence sur le résultat d’un filtrage :

WITH ls(x) AS (VALUES ('aa'),('å'),('t'),('s'),('ss'),('ß'), ('zz') )
SELECT * FROM ls
WHERE x > 'z' COLLATE "da_DK" ;

 x
----
 aa
 å
 zz

Il serait donc très complexe de réécrire le LIKE en un BETWEEN, comme le font habituellement tous les SGBD : col_texte LIKE 'toto%' peut être réécrit comme coltexte >= 'toto' and coltexte < 'totp' en ASCII, mais la réécriture est bien plus complexe en tri linguistique sur Unicode par exemple. Même si l’index est dans la bonne collation, il n’est pas facilement utilisable :

CREATE INDEX ON textes (livre) ;
EXPLAIN SELECT * FROM textes WHERE livre LIKE 'Les misérables%';

                                   QUERY PLAN
--------------------------------------------------------------------------------
 Gather  (cost=1000.00..525328.76 rows=75173 width=123)
   Workers Planned: 2
   ->  Parallel Seq Scan on textes  (cost=0.00..516811.46 rows=31322 width=123)
         Filter: (livre ~~ 'Les misérables%'::text)

La classe d’opérateurs varchar_pattern_ops sert à changer ce comportement :

CREATE INDEX ON ma_table (col_varchar varchar_pattern_ops) ;

Ce nouvel index est alors construit sur la comparaison brute des valeurs octales de tous les caractères qu’elle contient. Il devient alors trivial pour l’optimiseur de faire la réécriture :

EXPLAIN SELECT * FROM textes WHERE livre LIKE 'Les misérables%';

                               QUERY PLAN
-------------------------------------------------------------------------------
 Index Scan using textes_livre_idx1 on textes  (cost=0.69..70406.87 rows=75173 width=123)
   Index Cond: ((livre ~>=~ 'Les misérables'::text) AND (livre ~<~ 'Les misérablet'::text))
   Filter: (livre ~~ 'Les misérables%'::text)

Cela convient pour un LIKE 'critère%', car le début est fixe, et l’ordre de tri n’influe pas sur le résultat. (Par contre cela ne permet toujours pas d’indexer LIKE %critère%.) Noter la clause Filter qui filtre en deuxième intention ce qui a pu être trouvé dans l’index.

Il existe quelques autres cas d’utilisation d’opclass alternatives, notamment pour utiliser d’autres types d’index que B-tree. Deux exemples :

• indexation d’un JSON (type jsonb) par un index GIN :

CREATE INDEX ON stock_jsonb USING gin (document_jsonb jsonb_path_ops);

• indexation de trigrammes de textes avec le module pg_trgm et des index GiST :

CREATE INDEX ON livres USING gist (text_data gist_trgm_ops);

Pour plus de détails à ce sujet, se référer à la section correspondant aux classes d’opérateurs.

L’indexation d’une base de données est souvent un sujet qui est traité trop tard dans le cycle de l’application. Lorsque celle-ci est gérée à l’étape du développement, il est possible de bénéficier de l’expérience et de la connaissance des développeurs. La maîtrise de cette compétence est donc idéalement transverse entre le développement et l’exploitation.

Le fonctionnement d’un index B-tree est somme toute assez simple, mais il est important de bien l’appréhender pour comprendre les enjeux d’une bonne stratégie d’indexation.

PostgreSQL fournit aussi d’autres types d’index moins utilisés, mais très précieux dans certaines situations : BRIN, GIN, GiST, etc.

La version en ligne des solutions de ces TP est disponible sur https://dali.bo/j4_solutions.

Tous les TP se basent sur la configuration par défaut de PostgreSQL, sauf précision contraire.

Cette série de question utilise la base magasin. La base magasin (dump de 96 Mo, pour 667 Mo sur le disque au final) peut être téléchargée et restaurée comme suit dans une nouvelle base magasin :

createdb magasin
curl -kL https://dali.bo/tp_magasin -o /tmp/magasin.dump
pg_restore -d magasin  /tmp/magasin.dump
# le message sur public préexistant est normal
rm -- /tmp/magasin.dump

Les données sont dans deux schémas, magasin et facturation. Penser au search_path.

Pour ce TP, figer les paramètres suivants :

SET max_parallel_workers_per_gather to 0;
SET seq_page_cost TO 1 ;
SET random_page_cost TO 4 ;

Considérons le cas d’usage d’une recherche de commandes par date. Le besoin fonctionnel est le suivant : renvoyer l’intégralité des commandes passées au mois de janvier 2014.

Créer la requête affichant l’intégralité des commandes passées au mois de janvier 2014.

Afficher le plan de la requête , en utilisant EXPLAIN (ANALYZE, BUFFERS). Que constate-t-on ?

Nous souhaitons désormais afficher les résultats à l’utilisateur par ordre de date croissante.

Réécrire la requête par ordre de date croissante. Afficher de nouveau son plan. Que constate-t-on ?

Maintenant, nous allons essayer d’optimiser ces deux requêtes.

Créer un index permettant de répondre à ces requêtes.

Afficher de nouveau le plan des deux requêtes. Que constate-t-on ?

Maintenant, étudions l’impact des index pour une opération de jointure. Le besoin fonctionnel est désormais de lister toutes les commandes associées à un client (admettons, dont le client_id vaut 3), avec les informations du client lui-même.

Écrire la requête affichant commandes.nummero_commande et clients.type_client pour client_id = 3. Afficher son plan. Que constate-t-on ?

Créer un index pour accélérer cette requête.

Afficher de nouveau son plan. Que constate-t-on ?

Écrire une requête renvoyant l’intégralité des clients qui sont du type entreprise (‘E’), une autre pour l’intégralité des clients qui sont du type particulier (‘P’).

Ajouter un index sur la colonne type_client, et rejouer les requêtes précédentes.

Afficher leurs plans d’exécution. Que se passe-t-il ? Pourquoi ?

Sur la base fournie pour les TPs, les lots non livrés sont constamment requêtés. Notamment, un système d’alerte est mis en place afin d’assurer un suivi qualité sur les lots expédié depuis plus de 3 jours (selon la date d’expédition), mais non réceptionné (date de réception à NULL).

Écrire la requête correspondant à ce besoin fonctionnel (il est normal qu’elle ne retourne rien).

Afficher le plan d’exécution.

Quel index partiel peut-on créer pour optimiser ?

Afficher le nouveau plan d’exécution et vérifier l’utilisation du nouvel index.

Pour répondre aux exigences de stockage, l’application a besoin de pouvoir trouver rapidement les produits dont le volume est compris entre certaines bornes (nous négligeons ici le facteur de forme, qui est problématique dans le cadre d’un véritable stockage en entrepôt !).

Écrire une requête permettant de renvoyer l’ensemble des produits (table magasin.produits) dont le volume ne dépasse pas 1 litre (les unités de longueur sont en mm, 1 litre = 1 000 000 mm³).

Quel index permet d’optimiser cette requête ? (Utiliser une fonction est possible, mais pas obligatoire.)

Un développeur cherche à récupérer les commandes dont le numéro d’expédition est 190774 avec cette requête :

SELECT * FROM lignes_commandes WHERE numero_lot_expedition = '190774'::numeric ;

Afficher le plan de la requête.

Créer un index pour améliorer son exécution.

L’index est-il utilisé ? Quel est le problème ?

Écrire une requête pour obtenir les commandes dont la quantité est comprise entre 1 et 8 produits.

Créer un index pour améliorer l’exécution de cette requête.

Pourquoi celui-ci n’est-il pas utilisé ? (Conseil : regarder la vue pg_stats)

Faire le test avec les commandes dont la quantité est comprise entre 1 et 4 produits.

Tout d’abord, nous positionnons le search_path pour chercher les objets des schémas magasin et facturation :

SET search_path = magasin,facturation;

Index « simples »

Considérons le cas d’usage d’une recherche de commandes par date. Le besoin fonctionnel est le suivant : renvoyer l’intégralité des commandes passées au mois de janvier 2014.

Créer la requête affichant l’intégralité des commandes passées au mois de janvier 2014.

Pour renvoyer l’ensemble de ces produits, la requête est très simple :

SELECT * FROM commandes date_commande
WHERE date_commande >= '2014-01-01'
AND date_commande < '2014-02-01';

Afficher le plan de la requête , en utilisant EXPLAIN (ANALYZE, BUFFERS). Que constate-t-on ?

Le plan de celle-ci est le suivant :

EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM commandes
WHERE date_commande >= '2014-01-01' AND date_commande < '2014-02-01';

                                 QUERY PLAN
-----------------------------------------------------------------------
 Seq Scan on commandes  (cost=0.00..25158.00 rows=19674 width=50)
                        (actual time=2.436..102.300 rows=19204 loops=1)
   Filter: ((date_commande >= '2014-01-01'::date)
            AND (date_commande < '2014-02-01'::date))
   Rows Removed by Filter: 980796
   Buffers: shared hit=10158
 Planning time: 0.057 ms
 Execution time: 102.929 ms

Réécrire la requête par ordre de date croissante. Afficher de nouveau son plan. Que constate-t-on ?

Ajoutons la clause ORDER BY :

EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM commandes
WHERE date_commande >= '2014-01-01' AND date_commande < '2014-02-01'
ORDER BY date_commande;

                              QUERY PLAN
-----------------------------------------------------------------------------
 Sort  (cost=26561.15..26610.33 rows=19674 width=50)
       (actual time=103.895..104.726 rows=19204 loops=1)
   Sort Key: date_commande
   Sort Method: quicksort  Memory: 2961kB
   Buffers: shared hit=10158
   ->  Seq Scan on commandes  (cost=0.00..25158.00 rows=19674 width=50)
                              (actual time=2.801..102.181
                               rows=19204 loops=1)
         Filter: ((date_commande >= '2014-01-01'::date)
                  AND (date_commande < '2014-02-01'::date))
         Rows Removed by Filter: 980796
         Buffers: shared hit=10158
 Planning time: 0.096 ms
 Execution time: 105.410 ms

On constate ici que lors du parcours séquentiel, 980 796 lignes ont été lues, puis écartées car ne correspondant pas au prédicat, nous laissant ainsi avec un total de 19 204 lignes. Les valeurs précises peuvent changer, les données étant générées aléatoirement. De plus, le tri a été réalisé en mémoire. On constate de plus que 10 158 blocs ont été parcourus, ici depuis le cache, mais ils auraient pu l’être depuis le disque.

Créer un index permettant de répondre à ces requêtes.

Création de l’index :

CREATE INDEX idx_commandes_date_commande ON commandes(date_commande);

Afficher de nouveau le plan des deux requêtes. Que constate-t-on ?

EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM commandes
WHERE date_commande >= '2014-01-01' AND date_commande < '2014-02-01';

                        QUERY PLAN
----------------------------------------------------------
 Index Scan using idx_commandes_date_commande on commandes
        (cost=0.42..822.60 rows=19674 width=50)
        (actual time=0.015..3.311 rows=19204
   Index Cond: ((date_commande >= '2014-01-01'::date)
                AND (date_commande < '2014-02-01'::date))
   Buffers: shared hit=254
 Planning time: 0.074 ms
 Execution time: 4.133 ms

Le temps d’exécution a été réduit considérablement : la requête est 25 fois plus rapide. On constate notamment que seuls 254 blocs ont été parcourus.

Pour la requête avec la clause ORDER BY, nous obtenons le plan d’exécution suivant :

                        QUERY PLAN
----------------------------------------------------------
 Index Scan using idx_commandes_date_commande on commandes
        (cost=0.42..822.60 rows=19674 width=50)
        (actual time=0.032..3.378 rows=19204
   Index Cond: ((date_commande >= '2014-01-01'::date)
                AND (date_commande < '2014-02-01'::date))
   Buffers: shared hit=254
 Planning time: 0.516 ms
 Execution time: 4.049 ms

Celui-ci est identique ! En effet, l’index permettant un parcours trié, l’opération de tri est ici « gratuite ».

Écrire la requête affichant commandes.nummero_commande et clients.type_client pour client_id = 3. Afficher son plan. Que constate-t-on ?

EXPLAIN (ANALYZE, BUFFERS) SELECT numero_commande, type_client FROM commandes
      INNER JOIN clients ON commandes.client_id = clients.client_id
    WHERE clients.client_id = 3;

                                  QUERY PLAN
--------------------------------------------------------------------------
 Nested Loop  (cost=0.29..22666.42 rows=11 width=101)
              (actual time=8.799..80.771 rows=14 loops=1)
   Buffers: shared hit=10161
   ->  Index Scan using clients_pkey on clients
            (cost=0.29..8.31 rows=1 width=51)
            (actual time=0.017..0.018 rows=1 loops=1)
         Index Cond: (client_id = 3)
         Buffers: shared hit=3
   ->  Seq Scan on commandes  (cost=0.00..22658.00 rows=11 width=50)
                              (actual time=8.777..80.734 rows=14 loops=1)
         Filter: (client_id = 3)
         Rows Removed by Filter: 999986
         Buffers: shared hit=10158
 Planning time: 0.281 ms
 Execution time: 80.853 ms

Créer un index pour accélérer cette requête.

CREATE INDEX ON commandes (client_id) ;

Afficher de nouveau son plan. Que constate-t-on ?

EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM commandes
      INNER JOIN clients on commandes.client_id = clients.client_id
      WHERE clients.client_id = 3;

                               QUERY PLAN
--------------------------------------------------------------------------------
 Nested Loop  (cost=4.80..55.98 rows=11 width=101)
              (actual time=0.064..0.189 rows=14 loops=1)
   Buffers: shared hit=23
   ->  Index Scan using clients_pkey on clients
            (cost=0.29..8.31 rows=1 width=51)
            (actual time=0.032..0.032 rows=1 loops=1)
         Index Cond: (client_id = 3)
         Buffers: shared hit=6
   ->  Bitmap Heap Scan on commandes  (cost=4.51..47.56 rows=11 width=50)
                                      (actual time=0.029..0.147
                                       rows=14 loops=1)
         Recheck Cond: (client_id = 3)
         Heap Blocks: exact=14
         Buffers: shared hit=17
         ->  Bitmap Index Scan on commandes_client_id_idx
                    (cost=0.00..4.51 rows=11 width=0)
                    (actual time=0.013..0.013 rows=14 loops=1)
               Index Cond: (client_id = 3)
               Buffers: shared hit=3
 Planning time: 0.486 ms
 Execution time: 0.264 ms

On constate ici un temps d’exécution divisé par 160 : en effet, on ne lit plus que 17 blocs pour la commande (3 pour l’index, 14 pour les données) au lieu de 10 158.

Sélectivité

Écrire une requête renvoyant l’intégralité des clients qui sont du type entreprise (‘E’), une autre pour l’intégralité des clients qui sont du type particulier (‘P’).

Les requêtes :

SELECT * FROM clients WHERE type_client = 'P';
SELECT * FROM clients WHERE type_client = 'E';

Ajouter un index sur la colonne type_client, et rejouer les requêtes précédentes.

Pour créer l’index :

CREATE INDEX ON clients (type_client);

Afficher leurs plans d’exécution. Que se passe-t-il ? Pourquoi ?

Les plans d’éxécution :

EXPLAIN ANALYZE SELECT * FROM clients WHERE type_client = 'P';

                               QUERY PLAN
--------------------------------------------------------------------
 Seq Scan on clients  (cost=0.00..2276.00 rows=89803 width=51)
                      (actual time=0.006..12.877 rows=89800 loops=1)
   Filter: (type_client = 'P'::bpchar)
   Rows Removed by Filter: 10200
 Planning time: 0.374 ms
 Execution time: 16.063 ms

EXPLAIN ANALYZE SELECT * FROM clients WHERE type_client = 'E';

                                  QUERY PLAN
--------------------------------------------------------------------------
 Bitmap Heap Scan on clients  (cost=154.50..1280.84 rows=8027 width=51)
                              (actual time=2.094..4.287 rows=8111 loops=1)
   Recheck Cond: (type_client = 'E'::bpchar)
   Heap Blocks: exact=1026
   ->  Bitmap Index Scan on clients_type_client_idx
            (cost=0.00..152.49 rows=8027 width=0)
            (actual time=1.986..1.986 rows=8111 loops=1)
         Index Cond: (type_client = 'E'::bpchar)
 Planning time: 0.152 ms
 Execution time: 4.654 ms

L’optimiseur sait estimer, à partir des statistiques (consultables via la vue pg_stats), qu’il y a approximativement 89 000 clients particuliers, contre 8 000 clients entreprise.

Dans le premier cas, la majorité de la table sera parcourue, et renvoyée : il n’y a aucun intérêt à utiliser l’index.

Dans l’autre, le nombre de lignes étant plus faible, l’index est bel et bien utilisé (via un Bitmap Scan, ici).

Index partiels

Sur la base fournie pour les TPs, les lots non livrés sont constamment requêtés. Notamment, un système d’alerte est mis en place afin d’assurer un suivi qualité sur les lots expédié depuis plus de 3 jours (selon la date d’expédition), mais non réceptionné (date de réception à NULL).

Écrire la requête correspondant à ce besoin fonctionnel (il est normal qu’elle ne retourne rien).

La requête est la suivante :

SELECT * FROM lots
    WHERE date_reception IS NULL
    AND   date_expedition < now() - '3d'::interval;

Afficher le plan d’exécution.

Le plans (ci-dessous avec ANALYZE) opère un Seq Scan parallélisé, lit et rejette toutes les lignes, ce qui est évidemment lourd :

                         QUERY PLAN
---------------------------------------------------------------
 Gather  (cost=1000.00..17764.65 rows=1 width=43) (actual time=28.522..30.993 rows=0 loops=1)
   Workers Planned: 2
   Workers Launched: 2
   ->  Parallel Seq Scan on lots  (cost=0.00..16764.55 rows=1 width=43) (actual time=24.887..24.888 rows=0 loops=3)
         Filter: ((date_reception IS NULL) AND (date_expedition < (now() - '3 days'::interval)))
         Rows Removed by Filter: 335568
 Planning Time: 0.421 ms
 Execution Time: 31.012 ms

Quel index partiel peut-on créer pour optimiser ?

On peut optimiser ces requêtes sur les critères de recherche à l’aide des index partiels suivants :

CREATE INDEX ON lots (date_expedition) WHERE date_reception  IS NULL;

Afficher le nouveau plan d’exécution et vérifier l’utilisation du nouvel index.

EXPLAIN (ANALYZE)
SELECT * FROM lots
    WHERE date_reception IS NULL
    AND   date_expedition < now() - '3d'::interval;

                         QUERY PLAN
---------------------------------------------------------------
 Index Scan using lots_date_expedition_idx on lots  (cost=0.13..4.15 rows=1 width=43) (actual time=0.008..0.009 rows=0 loops=1)
   Index Cond: (date_expedition < (now() - '3 days'::interval))
 Planning Time: 0.243 ms
 Execution Time: 0.030 ms

Il est intéressant de noter que seul le test sur la condition indexée (date_expedition) est présent dans le plan : la condition date_reception IS NULL est implicitement validée par l’index partiel.

Attention, il peut être tentant d’utiliser une formulation de la sorte pour ces requêtes :

SELECT * FROM lots
WHERE date_reception IS NULL
AND   now() - date_expedition > '3d'::interval;

D’un point de vue logique, c’est la même chose, mais l’optimiseur n’est pas capable de réécrire cette requête correctement. Ici, le nouvel index sera tout de même utilisé, le volume de lignes satisfaisant au critère étant très faible, mais il ne sera pas utilisé pour filtrer sur la date :

EXPLAIN (ANALYZE) SELECT * FROM lots
      WHERE date_reception IS NULL
      AND   now() - date_expedition > '3d'::interval;

                              QUERY PLAN
-------------------------------------------------------------------
 Index Scan using lots_date_expedition_idx on lots
        (cost=0.12..4.15 rows=1 width=43)
        (actual time=0.007..0.007 rows=0 loops=1)
   Filter: ((now() - (date_expedition)::timestamp with time zone) >
            '3 days'::interval)
 Planning time: 0.204 ms
 Execution time: 0.132 ms

La ligne importante et différente ici concerne le Filter en lieu et place du Index Cond du plan précédent. Ici tout l’index partiel (certes tout petit) est lu intégralement et les lignes testées une à une.

C’est une autre illustration des points vus précédemment sur les index non utilisés.

Index fonctionnel

Ce TP utilise la base magasin.

Écrire une requête permettant de renvoyer l’ensemble des produits (table magasin.produits) dont le volume ne dépasse pas 1 litre (les unités de longueur sont en mm, 1 litre = 1 000 000 mm³).

Concernant le volume des produits, la requête est assez simple :

SELECT * FROM produits WHERE longueur * hauteur * largeur < 1000000 ;

Quel index permet d’optimiser cette requête ? (Utiliser une fonction est possible, mais pas obligatoire.)

L’option la plus simple est de créer l’index de cette façon, sans avoir besoin d’une fonction :

CREATE INDEX ON produits((longueur * hauteur * largeur));

En général, il est plus propre de créer une fonction. On peut passer la ligne entière en paramètre pour éviter de fournir 3 paramètres. Il faut que cette fonction soit IMMUTABLE pour être indexable :

CREATE OR REPLACE function volume (p produits)
RETURNS numeric
AS $$
 SELECT p.longueur * p.hauteur * p.largeur;
$$ language SQL
PARALLEL SAFE
IMMUTABLE ;

(Elle est même PARALLEL SAFE pour la même raison qu’elle est IMMUTABLE : elle dépend uniquement des données de la table.)

On peut ensuite indexer le résultat de cette fonction :

CREATE INDEX ON produits (volume(produits)) ;

Il est ensuite possible d’écrire la requête de plusieurs manières, la fonction étant ici écrite en SQL et non en PL/pgSQL ou autre langage procédural :

SELECT * FROM produits WHERE longueur * hauteur * largeur < 1000000 ;
SELECT * FROM produits WHERE volume(produits) < 1000000 ;

En effet, l’optimiseur est capable de « regarder » à l’intérieur de la fonction SQL pour déterminer que les clauses sont les mêmes, ce qui n’est pas vrai pour les autres langages.

En revanche, la requête suivante, où la multiplication est faite dans un ordre différent, n’utilise pas l’index :

SELECT * FROM produits WHERE largeur * longueur * hauteur < 1000000 ;

et c’est notamment pour cette raison qu’il est plus propre d’utiliser la fonction.

De part l’origine « relationnel-objet » de PostgreSQL, on peut même écrire la requête de la manière suivante :

SELECT * FROM produits WHERE produits.volume < 1000000;

Cas d’index non utilisés

Afficher le plan de la requête.

SELECT * FROM lignes_commandes WHERE numero_lot_expedition = '190774'::numeric;

EXPLAIN (ANALYZE,BUFFERS) SELECT * FROM lignes_commandes
                            WHERE numero_lot_expedition = '190774'::numeric;

                    QUERY PLAN
-------------------------------------------------------------------------
 Seq Scan on lignes_commandes
                        (cost=0.00..89331.51 rows=15710 width=74)
                        (actual time=0.024..1395.705 rows=6 loops=1)
   Filter: ((numero_lot_expedition)::numeric = '190774'::numeric)
   Rows Removed by Filter: 3141961
   Buffers: shared hit=97 read=42105
 Planning time: 0.109 ms
 Execution time: 1395.741 ms

Le moteur fait un parcours séquentiel et retire la plupart des enregistrements pour n’en conserver que 6.

Créer un index pour améliorer son exécution.

CREATE INDEX ON lignes_commandes (numero_lot_expedition);

L’index est-il utilisé ? Quel est le problème ?

L’index n’est pas utilisé à cause de la conversion bigint vers numeric. Il est important d’utiliser les bons types :

EXPLAIN (ANALYZE,BUFFERS)
SELECT * FROM lignes_commandes
WHERE numero_lot_expedition = '190774' ;

                         QUERY PLAN
--------------------------------------------------------------------------
 Index Scan using lignes_commandes_numero_lot_expedition_idx
    on lignes_commandes
        (cost=0.43..8.52 rows=5 width=74)
        (actual time=0.054..0.071 rows=6 loops=1)
   Index Cond: (numero_lot_expedition = '190774'::bigint)
   Buffers: shared hit=1 read=4
 Planning time: 0.325 ms
 Execution time: 0.100 ms

Sans conversion la requête est bien plus rapide. Faites également le test sans index, le Seq Scan sera également plus rapide, le moteur n’ayant pas à convertir toutes les lignes parcourues.

Écrire une requête pour obtenir les commandes dont la quantité est comprise entre 1 et 8 produits.

EXPLAIN (ANALYZE,BUFFERS) SELECT * FROM lignes_commandes
                                    WHERE quantite BETWEEN 1 AND 8;

                           QUERY PLAN
---------------------------------------------------------------------------
 Seq Scan on lignes_commandes
        (cost=0.00..89331.51 rows=2504357 width=74)
        (actual time=0.108..873.666 rows=2512740 loops=1)
   Filter: ((quantite >= 1) AND (quantite <= 8))
   Rows Removed by Filter: 629227
   Buffers: shared hit=16315 read=25887
 Planning time: 0.369 ms
 Execution time: 1009.537 ms

Créer un index pour améliorer l’exécution de cette requête.

CREATE INDEX ON lignes_commandes(quantite);

Pourquoi celui-ci n’est-il pas utilisé ? (Conseil : regarder la vue pg_stats)

La table pg_stats nous donne des informations de statistiques. Par exemple, pour la répartition des valeurs pour la colonne quantite:

SELECT * FROM pg_stats
WHERE tablename='lignes_commandes' AND attname='quantite'
\gx

…
n_distinct             | 10
most_common_vals       | {0,6,1,8,2,4,7,9,5,3}
most_common_freqs      | {0.1037,0.1018,0.101067,0.0999333,0.0999,0.0997,
                                    0.0995,0.0992333,0.0978333,0.0973333}
…

Ces quelques lignes nous indiquent qu’il y a 10 valeurs distinctes et qu’il y a environ 10 % d’enregistrements correspondant à chaque valeur.

Avec le prédicat quantite BETWEEN 1 and 8, le moteur estime récupérer environ 80 % de la table. Il est donc bien plus coûteux de lire l’index et la table pour récupérer 80 % de la table. C’est pourquoi le moteur fait un Seq Scan qui moins coûteux.

Faire le test avec les commandes dont la quantité est comprise entre 1 et 4 produits.

EXPLAIN (ANALYZE,BUFFERS) SELECT * FROM lignes_commandes
                                    WHERE quantite BETWEEN 1 AND 4;

                           QUERY PLAN
------------------------------------------------------------------------
 Bitmap Heap Scan on lignes_commandes
            (cost=26538.09..87497.63 rows=1250503 width=74)
            (actual time=206.705..580.854 rows=1254886 loops=1)
   Recheck Cond: ((quantite >= 1) AND (quantite <= 4))
   Heap Blocks: exact=42202
   Buffers: shared read=45633
   ->  Bitmap Index Scan on lignes_commandes_quantite_idx
            (cost=0.00..26225.46 rows=1250503 width=0)
            (actual time=194.250..194.250 rows=1254886 loops=1)
         Index Cond: ((quantite >= 1) AND (quantite <= 4))
         Buffers: shared read=3431
 Planning time: 0.271 ms
 Execution time: 648.414 ms
(9 rows)

Cette fois, la sélectivité est différente et le nombre d’enregistrements moins élevé. Le moteur passe donc par un parcours d’index.

Cet exemple montre qu’on indexe selon une requête et non selon une table.