Vous trouverez en ligne les différentes versions complètes de ce document. La version imprimée ne contient pas les travaux pratiques. Ils sont présents dans la version numérique (PDF ou HTML).

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

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

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

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

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

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

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

Photo de Maksym Kaharlytskyi, Unsplash licence

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

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

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

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

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

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

PostgreSQL propose différentes formes d’index :

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

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

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

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

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

EXPLAIN SELECT * FROM test WHERE id = 10000;

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

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

EXPLAIN SELECT * FROM test WHERE id = 10000;

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

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

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

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

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

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

Soit une table test2 telle que :

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Création d’un index :

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

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

Clause CONCURRENTLY :

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

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

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

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

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

Réindexation :

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

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

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

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

Il existe là aussi une clause CONCURRENTLY :

REINDEX (VERBOSE) INDEX CONCURRENTLY pgbench_accounts_bid_idx ;

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

Paramètres :

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

SET maintenance_work_mem = '2GB' ;

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

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

SET max_parallel_maintenance_workers = 2 ;

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

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

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

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

Contrainte d’unicité et index :

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

Par exemple, sur cette table personne :

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

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

on peut créer un index unique :

$ CREATE UNIQUE INDEX ON personne (id);

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

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

DROP INDEX personne_id_idx;

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

ALTER TABLE personne ADD CONSTRAINT unique_id UNIQUE (id);

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

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

DROP INDEX unique_id ;

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

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

Indexation avancée :

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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. Il est favorisé par une bonne corrélation des données avec leur emplacement physique.

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 '01-01-2011'::date AND '31-12-2011'::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.

L’installation est détaillée ici pour Rocky Linux 8 et 9 (similaire à Red Hat et à d’autres variantes comem Oracle Linux et Fedora), et Debian/Ubuntu.

Elle ne dure que quelques minutes.

Sur Rocky Linux 8 ou 9

Installation du dépôt communautaire  :

Les dépôts de la communauté sont sur https://yum.postgresql.org/. Les commandes qui suivent sont inspirées de celles générées par l’assistant sur https://www.postgresql.org/download/linux/redhat/, en précisant :

• la version majeure de PostgreSQL (ici la 16) ;
• la distribution (ici Rocky Linux 8) ;
• l’architecture (ici x86_64, la plus courante).

Les commandes sont à lancer sous root :

# dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms\
/EL-8-x86_64/pgdg-redhat-repo-latest.noarch.rpm

# dnf -qy module disable postgresql

Installation de PostgreSQL 16 (client, serveur, librairies, extensions) : 

# dnf install -y postgresql16-server postgresql16-contrib

Les outils clients et les librairies nécessaires seront automatiquement installés.

Une fonctionnalité avancée optionnelle, le JIT (Just In Time compilation), nécessite un paquet séparé.

# dnf install postgresql16-llvmjit

Création d’une première instance :

Il est conseillé de déclarer PG_SETUP_INITDB_OPTIONS, notamment pour mettre en place les sommes de contrôle et forcer les traces en anglais :

# export PGSETUP_INITDB_OPTIONS='--data-checksums --lc-messages=C'
# /usr/pgsql-16/bin/postgresql-16-setup initdb
# cat /var/lib/pgsql/16/initdb.log

Ce dernier fichier permet de vérifier que tout s’est bien passé et doit finir par :

Success. You can now start the database server using:

    /usr/pgsql-16/bin/pg_ctl -D /var/lib/pgsql/16/data/ -l logfile start

Chemins :

Configuration :

Modifier postgresql.conf est facultatif pour un premier lancement.

Commandes d’administration habituelles :

Démarrage, arrêt, statut, rechargement à chaud de la configuration, redémarrage :

# systemctl start postgresql-16
# systemctl stop postgresql-16
# systemctl status postgresql-16
# systemctl reload postgresql-16
# systemctl restart postgresql-16

Test rapide de bon fonctionnement et connexion à psql :

# systemctl --all |grep postgres
# sudo -iu postgres psql

Démarrage de l’instance au lancement du système d’exploitation :

# systemctl enable postgresql-16

Ouverture du firewall pour le port 5432 :

Voir si le firewall est actif :

# systemctl status firewalld

Si c’est le cas, autoriser un accès extérieur :

# firewall-cmd --zone=public --add-port=5432/tcp --permanent
# firewall-cmd --reload
# firewall-cmd --list-all

(Rappelons que listen_addresses doit être également modifié dans postgresql.conf.)

Création d’autres instances :

Si des instances de versions majeures différentes doivent être installées, il faut d’abord installer les binaires pour chacune (adapter le numéro dans dnf install …) et appeler le script d’installation de chaque version. l’instance par défaut de chaque version vivra dans un sous-répertoire numéroté de /var/lib/pgsql automatiquement créé à l’installation. Il faudra juste modifier les ports dans les postgresql.conf pour que les instances puissent tourner simultanément.

Si plusieurs instances d’une même version majeure (forcément de la même version mineure) doivent cohabiter sur le même serveur, il faut les installer dans des PGDATA différents.

• Ne pas utiliser de tiret dans le nom d’une instance (problèmes potentiels avec systemd).
• Respecter les normes et conventions de l’OS : placer les instances dans un nouveau sous-répertoire de /var/lib/pgsqsl/16/ (ou l’équivalent pour d’autres versions majeures).

Pour créer une seconde instance, nommée par exemple infocentre :

• Création du fichier service de la deuxième instance :

# cp /lib/systemd/system/postgresql-16.service \
        /etc/systemd/system/postgresql-16-infocentre.service

• Modification de ce dernier fichier avec le nouveau chemin :

Environment=PGDATA=/var/lib/pgsql/16/infocentre

• Option 1 : création d’une nouvelle instance vierge :

# export PGSETUP_INITDB_OPTIONS='--data-checksums --lc-messages=C'
# /usr/pgsql-16/bin/postgresql-16-setup initdb postgresql-16-infocentre

• Option 2 : restauration d’une sauvegarde : la procédure dépend de votre outil.

• Adaptation de /var/lib/pgsql/16/infocentre/postgresql.conf (port surtout).

• Commandes de maintenance de cette instance :

# systemctl [start|stop|reload|status] postgresql-16-infocentre
# systemctl [enable|disable] postgresql-16-infocentre

• Ouvrir le nouveau port dans le firewall au besoin.

Sur Debian / Ubuntu

Sauf précision, tout est à effectuer en tant qu’utilisateur root.

Référence : https://apt.postgresql.org/

Installation du dépôt communautaire :

L’installation des dépôts du PGDG est prévue dans le paquet Debian :

# apt update
# apt install -y  gnupg2  postgresql-common 
# /usr/share/postgresql-common/pgdg/apt.postgresql.org.sh

Ce dernier ordre créera le fichier du dépôt /etc/apt/sources.list.d/pgdg.list adapté à la distribution en place.

Installation de PostgreSQL 16 :

La méthode la plus propre consiste à modifier la configuration par défaut avant l’installation :

Dans /etc/postgresql-common/createcluster.conf, paramétrer au moins les sommes de contrôle et les traces en anglais :

initdb_options = '--data-checksums --lc-messages=C'

Puis installer les paquets serveur et clients et leurs dépendances :

# apt install postgresql-16 postgresql-client-16

La première instance est automatiquement créée, démarrée et déclarée comme service à lancer au démarrage du système. Elle porte un nom (par défaut main).

Elle est immédiatement accessible par l’utilisateur système postgres.

Chemins :

Configuration

Modifier postgresql.conf est facultatif pour un premier essai.

Démarrage/arrêt de l’instance, rechargement de configuration :

Debian fournit ses propres outils, qui demandent en paramètre la version et le nom de l’instance :

# pg_ctlcluster 16 main [start|stop|reload|status|restart]

Démarrage de l’instance avec le serveur :

C’est en place par défaut, et modifiable dans /etc/postgresql/16/main/start.conf.

Ouverture du firewall :

Debian et Ubuntu n’installent pas de firewall par défaut.

Statut des instances du serveur :

# pg_lsclusters

Test rapide de bon fonctionnement et connexion à psql :

# systemctl --all |grep postgres
# sudo -iu postgres psql

Destruction d’une instance :

# pg_dropcluster 16 main

Création d’autres instances :

Ce qui suit est valable pour remplacer l’instance par défaut par une autre, par exemple pour mettre les checksums en place :

• optionnellement, /etc/postgresql-common/createcluster.conf permet de mettre en place tout d’entrée les checksums, les messages en anglais, le format des traces ou un emplacement séparé pour les journaux :

initdb_options = '--data-checksums --lc-messages=C'
log_line_prefix = '%t [%p]: [%l-1] user=%u,db=%d,app=%a,client=%h '
waldir = '/var/lib/postgresql/wal/%v/%c/pg_wal'

• créer une instance :

# pg_createcluster 16 infocentre

Il est également possible de préciser certains paramètres du fichier postgresql.conf, voire les chemins des fichiers (il est conseillé de conserver les chemins par défaut) :

# pg_createcluster 16 infocentre \
  --port=12345 \
  --datadir=/PGDATA/16/infocentre \
  --pgoption shared_buffers='8GB' --pgoption work_mem='50MB' \
  --  --data-checksums --waldir=/ssd/postgresql/16/infocentre/journaux

• adapter au besoin /etc/postgresql/16/infocentre/postgresql.conf ;

• démarrage :

# pg_ctlcluster 16 infocentre start

Accès à l’instance depuis le serveur même (toutes distributions)

Par défaut, l’instance n’est accessible que par l’utilisateur système postgres, qui n’a pas de mot de passe. Un détour par sudo est nécessaire :

$ sudo -iu postgres psql
psql (16.0)
Type "help" for help.
postgres=#

Ce qui suit permet la connexion directement depuis un utilisateur du système :

Pour des tests (pas en production !), il suffit de passer à trust le type de la connexion en local dans le pg_hba.conf :

local   all             postgres                               trust

La connexion en tant qu’utilisateur postgres (ou tout autre) n’est alors plus sécurisée :

dalibo:~$ psql -U postgres
psql (16.0)
Type "help" for help.
postgres=#

Une authentification par mot de passe est plus sécurisée :

• dans pg_hba.conf, paramétrer une authentification par mot de passe pour les accès depuis localhost (déjà en place sous Debian) :

# IPv4 local connections:
host    all             all             127.0.0.1/32            scram-sha-256
# IPv6 local connections:
host    all             all             ::1/128                 scram-sha-256

(Ne pas oublier de recharger la configuration en cas de modification.)

• ajouter un mot de passe à l’utilisateur postgres de l’instance :

dalibo:~$ sudo -iu postgres psql
psql (16.0)
Type "help" for help.
postgres=# \password
Enter new password for user "postgres":
Enter it again:
postgres=# quit

dalibo:~$ psql -h localhost -U postgres
Password for user postgres:
psql (16.0)
Type "help" for help.
postgres=#

• Pour se connecter sans taper le mot de passe à une instance, un fichier .pgpass dans le répertoire personnel doit contenir les informations sur cette connexion :

localhost:5432:*:postgres:motdepassetrèslong

Ce fichier doit être protégé des autres utilisateurs :

$ chmod 600 ~/.pgpass

• Pour n’avoir à taper que psql, on peut définir ces variables d’environnement dans la session voire dans ~/.bashrc :

export PGUSER=postgres
export PGDATABASE=postgres
export PGHOST=localhost

Rappels :

• en cas de problème, consulter les traces (dans /var/lib/pgsql/16/data/log ou /var/log/postgresql/) ;
• toute modification de pg_hba.conf ou postgresql.conf impliquant de recharger la configuration peut être réalisée par une de ces trois méthodes en fonction du système :

root:~# systemctl reload postgresql-16

root:~# pg_ctlcluster 16 main reload

postgres:~$ psql -c 'SELECT pg_reload_conf()'

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

Toutes les données sont dans deux schémas nommés magasin et facturation.

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 du schéma magasin :

SET search_path = magasin;

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

Toutes les données sont dans deux schémas nommés magasin et facturation.

É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.

PostgreSQL fournit de nombreux types d’index, afin de répondre à des problématiques de recherches complexes.

Rappelons que l’index classique est créé comme ceci :

CREATE INDEX mon_index ON ma_table(ma_colonne) ;

B-tree (en arbre équilibré) est le type d’index le plus fréquemment utilisé.

Toutes les fonctionnalités vues précédemment peuvent être utilisées simultanément. Il est parfois tentant de créer des index très spécialisés grâce à toutes ces fonctionnalités, comme dans l’exemple ci-dessus. Mais il ne faut surtout pas perdre de vue qu’un index est une structure lourde à mettre à jour, comparativement à une table. Une table avec un seul index est environ 3 fois plus lente qu’une table nue, et chaque index ajoute le même surcoût. Il est donc souvent plus judicieux d’avoir des index pouvant répondre à plusieurs requêtes différentes, et de ne pas trop les spécialiser. Il faut trouver un juste compromis entre le gain à la lecture et le surcoût à la mise à jour.

Les index B-tree sont les plus utilisés, mais PostgreSQL propose d’autres types d’index. Le type GIN est l’un des plus connus.

Un index inversé est une structure classique, utilisée le plus souvent dans l’indexation Full Text. Le principe est de décomposer un document en sous-structures, et ce sont ces éléments qui seront indexées. Par exemple, un document sera décomposé en la liste de ses mots, et chaque mot sera une clé de l’index. Cette clé fournira la liste des documents contenant ce mot. C’est l’inverse d’un index B-tree classique, qui va lister chacune des occurrences d’une valeur et y associer sa localisation.

Par analogie : dans un livre de cuisine, un index classique permettrait de chercher « Crêpes au caramel à l’armagnac » et « Sauce caramel et beurre salé », alors qu’un index GIN contiendrait « caramel », « crêpes », « armagnac », « sauce », « beurre »…

Pour plus de détails sur la structure elle-même, cet article Wikipédia est une lecture conseillée.

Dans l’implémentation de PostgreSQL, un index GIN est construit autour d’un index B-tree des éléments indexés, et à chacun est associé soit une simple liste de pointeurs vers la table (posting list) pour les petites listes, soit un pointeur vers un arbre B-tree contenant ces pointeurs (posting tree). La pending list est une optimisation des écritures (voir plus bas).

Les index GIN de PostgreSQL sont « généralisés », car ils sont capables d’indexer n’importe quel type de données, à partir du moment où on leur fournit les différentes fonctions d’API permettant le découpage et le stockage des différents items composant la donnée à indexer. En pratique, ce sont les opérateurs indiqués à la création de l’index, parfois implicites, qui contiendront la logique nécessaire.

Les index GIN sont des structures lentes à la mise à jour. Par contre, elles sont extrêmement efficaces pour les interrogations multicritères, ce qui les rend très appropriées pour l’indexation Full Text, des champs jsonb…

GIN et champ structuré :

Comme premier exemple d’indexation d’un champ structuré, prenons une table listant des voitures, dont un champ caracteristiques contient une liste d’attributs séparés par des virgules. Ceci ne respecte bien entendu pas la première forme normale.

Cette liste peut être transformée facilement en tableau avec regexp_split_to_array. Des opérateurs de manipulation peuvent alors être utilisés, comme : @> (contient), <@ (contenu par), && (a des éléments en communs). Par exemple, pour chercher les voitures possédant deux caractéristiques données, la requête est :

SELECT * FROM voitures
WHERE regexp_split_to_array(caracteristiques,',')
       @> '{"toit ouvrant","climatisation"}'    ;

 immatriculation | modele |                      caracteristiques
-----------------+--------+-------------------------------------------------------
 XB-025-PH       | clio   | toit ouvrant,climatisation
 RC-561-BI       | megane | regulateur de vitesse,boite automatique,
                 |        | toit ouvrant,climatisation,…
 LU-190-KO       | megane | toit ouvrant,climatisation,4 roues motrices
 SV-193-YR       | megane | climatisation,abs,toit ouvrant
 FG-432-FZ       | kangoo | climatisation,jantes aluminium,regulateur de vitesse,
                 |        | toit ouvrant
 …

avec ce plan :

                               QUERY PLAN
-------------------------------------------------------------------------------
Seq Scan on voitures  (cost=0.00..1406.20 rows=1 width=96)
  Filter: (regexp_split_to_array(caracteristiques, ','::text) @> '{"toit ouvrant",climatisation}'::text[])

Pour accélérer la recherche, le tableau de textes peut être directement indexé avec un index GIN, ici un index fonctionnel :

CREATE INDEX idx_attributs_array ON voitures
USING gin (regexp_split_to_array(caracteristiques,',')) ;

On ne précise pas d’opérateur, celui par défaut pour les tableaux convient.

Le plan devient :

 Bitmap Heap Scan on voitures  (cost=40.02..47.73 rows=2 width=96)
   Recheck Cond: (regexp_split_to_array(caracteristiques, ','::text) @> '{"toit ouvrant",climatisation}'::text[])
   ->  Bitmap Index Scan on idx_attributs_array  (cost=0.00..40.02 rows=2 width=0)
         Index Cond: (regexp_split_to_array(caracteristiques, ','::text) @> '{"toit ouvrant",climatisation}'::text[])

GIN et tableau :

GIN supporte nativement les tableaux des types scalaires (int, float, text, date…) :

CREATE TABLE tablo (i int, a int[]) ;
INSERT INTO tablo SELECT i, ARRAY[i, i+1] FROM generate_series(1,100000) i ;

Un index B-tree classique permet de rechercher un tableau identique à un autre, mais pas de chercher un tableau qui contient une valeur scalaire à l’intérieur du tableau :

EXPLAIN (COSTS OFF) SELECT * FROM tablo WHERE a = ARRAY[42,43] ;

                   QUERY PLAN
-------------------------------------------------
 Bitmap Heap Scan on tablo
   Recheck Cond: (a = '{42,43}'::integer[])
   ->  Bitmap Index Scan on tablo_a_idx
         Index Cond: (a = '{42,43}'::integer[])

SELECT * FROM tablo WHERE a @> ARRAY[42] ;

 i  |    a
----+---------
 41 | {41,42}
 42 | {42,43}

EXPLAIN (ANALYZE, BUFFERS, COSTS OFF) SELECT * FROM tablo WHERE a @> ARRAY[42] ;

                          QUERY PLAN
--------------------------------------------------------------
 Seq Scan on tablo (actual time=0.023..19.322 rows=2 loops=1)
   Filter: (a @> '{42}'::integer[])
   Rows Removed by Filter: 99998
   Buffers: shared hit=834
 Planning:
   Buffers: shared hit=6 dirtied=1
 Planning Time: 0.107 ms
 Execution Time: 19.337 ms

L’indexation GIN permet de chercher des valeurs figurant à l’intérieur des champs indexés :

CREATE INDEX ON tablo USING gin (a);

pour un résultat beaucoup plus efficace :

 Bitmap Heap Scan on tablo (actual time=0.010..0.010 rows=2 loops=1)
   Recheck Cond: (a @> '{42}'::integer[])
   Heap Blocks: exact=1
   Buffers: shared hit=5
   ->  Bitmap Index Scan on tablo_a_idx1 (actual time=0.007..0.007 rows=2 loops=1)
         Index Cond: (a @> '{42}'::integer[])
         Buffers: shared hit=4
 Planning:
   Buffers: shared hit=23
 Planning Time: 0.121 ms
 Execution Time: 0.023 ms

Le principe est le même pour des JSON, s’ils sont bien stockés dans un champ de type jsonb. Les recherches de l’existence d’une clé à la racine du document ou tableau JSON sont réalisées avec les opérateurs ?, ?| et ?&.

SELECT x, x ? 'b' AS "b existe", x ? 'c' AS "c existe"
FROM (VALUES ('{ "b" : { "c" : "ccc" }}'::jsonb)) AS F(x) ;

          x          | b existe | c existe
---------------------+----------+----------
 {"b": {"c": "ccc"}} | t        | f

Les recherches sur la présence d’une valeur dans un document JSON avec les opérateurs @>, @? ou @@ peuvent être réalisées avec la classe d’opérateur par défaut (json_ops), mais aussi la classe d’opérateur jsonb_path_ops, donc au choix :

CREATE INDEX idx_prs ON personnes USING gin (proprietes jsonb_ops) ;

CREATE INDEX idx_prs ON personnes USING gin (proprietes jsonb_path_ops) ;

La classe jsonb_path_ops est plus performante pour ce genre de recherche et génère des index plus compacts lorsque les clés apparaissent fréquemment dans les données. Par contre, elle ne permet pas d’effectuer efficacement des recherches de structure JSON vide du type : { "a" : {} }. Dans ce dernier cas, PostgreSQL devra faire, au mieux, un parcours de l’index complet, au pire un parcours séquentiel de la table. Le choix de la meilleure classe pour l’index dépend fortement de la typologie des données.

La documentation officielle entre plus dans le détail.

L’extension pg_trgm utilise aussi les index GIN, pour permettre des recherches de type :

SELECT * FROM ma_table
WHERE ma_col_texte LIKE '%ma_chaine1%ma_chaine2%' ;

L’extension fournit un opérateur dédié pour l’indexation (voir plus loin).

La recherche Full Text est généralement couplée à un index GIN pour indexer les tsvector (voir le module T1).

Grâce à l’extension btree_gin, fournie avec PostgreSQL, l’indexation GIN peut aussi s’appliquer aux scalaires. Il est ainsi possible d’indexer un ensemble de colonnes, par exemple d’entiers ou de textes (voir exemple plus loin). Cela peut servir dans les cas où une requête multicritères peut porter sur de nombreux champs différents, dont aucun n’est obligatoire. Un index B-tree est là moins adapté, voire inutilisable.

Un autre cas d’utilisation traditionnel est celui des index dits bitmap. Les index bitmap sont très compacts, mais ne permettent d’indexer que peu de valeurs différentes. Un index bitmap est une structure utilisant 1 bit par enregistrement pour chaque valeur indexable. Par exemple, on peut définir un index bitmap sur le sexe : deux valeurs seulement (voire quatre si on autorise NULL ou non-binaire) sont possibles. Indexer un enregistrement nécessitera donc un ou deux bits. Le défaut des index bitmap est que l’ajout de nouvelles valeurs est très peu performant car l’index nécessite d’importantes réécritures à chaque ajout. De plus, l’ajout de données provoque une dégradation des performances puisque la taille par enregistrement devient bien plus grosse.

Les index GIN permettent un fonctionnement sensiblement équivalent au bitmap : chaque valeur indexable contient la liste des enregistrements répondant au critère, et cette liste a l’intérêt d’être compressée. Par exemple, sur une base créée avec pgbench, de taille 100, avec les options par défaut :

CREATE EXTENSION btree_gin ;

CREATE INDEX pgbench_accounts_gin_idx on pgbench_accounts USING gin (bid);

EXPLAIN (ANALYZE,BUFFERS,COSTS OFF) SELECT * FROM pgbench_accounts WHERE bid=5 ;

                               QUERY PLAN
-------------------------------------------------------------------------------
 Bitmap Heap Scan on pgbench_accounts (actual time=7.505..19.931 rows=100000 loops=1)
   Recheck Cond: (bid = 5)
   Heap Blocks: exact=1640
   Buffers: shared hit=1657
   ->  Bitmap Index Scan on pgbench_accounts_gin_idx (actual time=7.245..7.245 rows=100000 loops=1)
         Index Cond: (bid = 5)
         Buffers: shared hit=17
 Planning:
   Buffers: shared hit=2
 Planning Time: 0.080 ms
 Execution Time: 24.090 ms

Dans ce cas précis qui renvoie de nombreuses lignes, l’utilisation du GIN est même aussi efficace que le B-tree ci-dessous, car l’index GIN est mieux compressé et a besoin de lire moins de blocs :

CREATE INDEX pgbench_accounts_btree_idx ON pgbench_accounts (bid);

EXPLAIN (ANALYZE,BUFFERS,COSTS OFF) SELECT * FROM pgbench_accounts WHERE bid=5 ;

                               QUERY PLAN
-------------------------------------------------------------------------------
 Index Scan using pgbench_accounts_btree_idx on pgbench_accounts (actual time=0.008..19.138 rows=100000 loops=1)
   Index Cond: (bid = 5)
   Buffers: shared hit=1728
 Planning:
   Buffers: shared hit=18
 Planning Time: 0.117 ms
 Execution Time: 23.369 ms

L’index GIN est en effet environ 5 fois plus compact que le B-tree dans cet exemple simple, avec 100 valeurs distinctes de bid :

pgbench_300=# \di+ pgbench_accounts_*
                   Liste des relations
 Schéma |            Nom             | … | Méthode d'accès | Taille | Description
--------+----------------------------+---+-----------------+--------+-------------
 public | pgbench_accounts_bid_idx   | … | btree           | 66 MB  | 
 public | pgbench_accounts_gin_idx   | … | gin             | 12 MB  |

Ce ne serait pas le cas avec des valeurs toutes différentes. (Avant la version 13, la différence de taille est encore plus importante car les index B-tree ne disposent pas encore de la déduplication des clés.)

Avant de déployer un index GIN, il faut vérifier l’impact du GIN sur les performances en insertions et mises à jour et l’impact sur les requêtes.

Les index GIN sont lourds à créer et à mettre à jour. Une valeur élevée de maintenance_work_mem est conseillée.

L’option fastupdate permet une mise à jour bien plus rapide. Elle est activée par défaut. PostgreSQL stocke alors les mises à jour de l’index dans une pending list qui est intégrée en bloc, notamment lors d’un VACUUM. Sa taille peut être modifiée par le paramètre gin_pending_list_limit, par défaut à 4 Mo, et au besoin surchargeable sur chaque index.

L’inconvénient de cette technique est que le temps de réponse de l’index devient instable : certaines recherches peuvent être très rapides et d’autres très lentes. Le seul moyen d’accélérer ces recherches est de désactiver fastupdate. Cela permet en plus d’éviter la double écriture dans les journaux de transactions. Mais il y a un impact : les mises à jour de l’index sont bien plus lentes.

Il faut donc faire un choix. Si l’on conserve l’option fastupdate, il faut surveiller la fréquence de passage de l’autovacuum. L’appel manuel à la fonction gin_clean_pending_list() est une autre option.

Pour les détails, voir la documentation.

Initialement, les index GiST sont un produit de la recherche de l’université de Berkeley. L’idée fondamentale est de pouvoir indexer non plus les valeurs dans l’arbre B-tree, mais plutôt la véracité d’un prédicat : « ce prédicat est vrai sur telle sous-branche ». On dispose donc d’une API permettant au type de données d’informer le moteur GiST d’informations comme : « quel est le résultat de la fusion de tel et tel prédicat » (pour pouvoir déterminer le prédicat du nœud parent), quel est le surcoût d’ajout de tel prédicat dans telle ou telle partie de l’arbre, comment réaliser un split (découpage) d’une page d’index, déterminer la distance entre deux prédicats, etc.

Tout ceci est très virtuel, et rarement re-développé par les utilisateurs. Par contre, certaines extensions et outils intégrés utilisent ce mécanisme.

Il faut retenir qu’un index GiST est moins performant qu’un B-tree si ce dernier est possible.

L’utilisation se recoupant en partie avec les index GIN, il faut noter que  :

• les index GiST ont moins tendance à se fragmenter que les GIN, même si cela dépend énormément du type de mises à jour ;
• les index GiST sont moins lourds à maintenir ;
• mais généralement moins performants.

Un index GiST permet d’indexer n’importe quoi, quelle que soit la dimension, le type, tant qu’on peut utiliser des prédicats sur ce type.

Il est disponible pour les types natifs suivants :

• géométriques (box, circle, point, poly) : le projet PostGIS utilise les index GiST massivement, pour répondre efficacement à des questions complexes telles que « quelles sont les routes qui coupent le Rhône ? », « quelles sont les villes adjacentes à Toulouse ? », « quels sont les restaurants situés à moins de 3 km de la Nationale 12 ? » ;
• range (d’int, de timestamp…) ;
• adresses IP/CIDR.
• Full Text Search.

Une partie des cas d’utilisation des index GiST recouvre ceux des index GIN. Nous verrons que les index GiST sont notamment utilisés par :

• les contraintes d’exclusion ;
• les recherches multicolonnes ;
• l’extension pg_trgm (dans ce cas, GiST est moins efficace que GIN pour la recherche exacte, mais permet de rapidement trouver les N enregistrements les plus proches d’une chaîne donnée, sans tri, et est plus compact).

Les index GiST supportent les requêtes de type K-plus proche voisins, et permettent donc de répondre extrêmement rapidement à des requêtes telles que :

• quels sont les dix restaurants les plus proches d’un point particulier ?
• quels sont les 5 mots ressemblant le plus à « éphélant » ? afin de proposer des corrections à un utilisateur ayant commis une faute de frappe (par exemple).

Une convention veut que l’opérateur distance soit généralement nommé « <-> », mais rien n’impose ce choix.

On peut prendre l’exemple d’indexation ci-dessus, avec le type natif point :

CREATE TABLE mes_points (p point);

INSERT INTO mes_points (SELECT point(i, j)
FROM generate_series(1, 100) i, generate_series(1,100) j WHERE random() > 0.8);

CREATE INDEX ON mes_points USING gist (p);

Pour trouver les 4 points les plus proches du point ayant pour coordonnées (18,36), on peut utiliser la requête suivante :

SELECT p,
       p <-> point(18,36)
FROM   mes_points
ORDER BY p <-> point(18, 36)
LIMIT 4;

    p    |     ?column?
---------+------------------
 (18,37) |                1
 (18,35) |                1
 (16,36) |                2
 (16,35) | 2.23606797749979

Cette requête utilise bien l’index GiST créé plus haut :

                         QUERY PLAN
------------------------------------------------------
 Limit  (cost=0.14..0.49 rows=4 width=16)
        (actual time=0.049..0.052 rows=4 loops=1)
   ->  Index Scan using mes_points_p_idx on mes_points
            (cost=0.14..176.72 rows=2029 width=16)
            (actual time=0.047..0.049 rows=4 loops=1)
         Order By: (p <-> '(18,36)'::point)
 Planning time: 0.050 ms
 Execution time: 0.075 ms

Les index SP-GiST sont compatibles avec ce type de recherche depuis la version 12.

Premiers exemples :

Les contraintes d’unicité sont une forme simple de contraintes d’exclusion. Si on prend l’exemple :

CREATE TABLE foo (
    id int,
    nom text,
    EXCLUDE (id WITH =)
);

cette déclaration est équivalente à une contrainte UNIQUE sur foo.id, mais avec le mécanisme des contraintes d’exclusion. Ici, la contrainte s’appuie toujours sur un index B-tree. Les NULL sont toujours permis, exactement comme avec une contrainte UNIQUE.

On peut également poser une contrainte unique sur plusieurs colonnes :

CREATE TABLE foo (
    nom text,
    naissance date,
    EXCLUDE (nom WITH =, naissance WITH =)
);

Intérêt :

L’intérêt des contraintes d’exclusion est qu’on peut utiliser des index d’un autre type que les B-tree, comme les GiST ou les hash, et surtout des opérateurs autres que l’égalité, ce qui permet de couvrir des cas que les contraintes habituelles ne savent pas traiter.

Par exemple, une contrainte UNIQUE ne permet pas d’interdire que deux enregistrements de type intervalle aient des bornes qui se chevauchent. Cependant, il est possible de le faire avec une contrainte d’exclusion.

Exemples :

L’exemple suivante implémente la contrainte que deux objets de type circle (cercle) ne se chevauchent pas. Or ce type ne s’indexe qu’avec du GiST :

CREATE TABLE circles (
    c circle,
    EXCLUDE USING gist (c WITH &&)
);
INSERT INTO circles(c) VALUES ('10, 4, 10');
INSERT INTO circles(c) VALUES ('8, 3, 8');

ERROR:  conflicting key value violates exclusion constraint "circles_c_excl"
DETAIL : Key (c)=(<(8,3),8>) conflicts with existing key (c)=(<(10,4),10>).

Un autre exemple très fréquemment proposé est celui de la réservation de salles de cours sur des plages horaires qui ne doivent pas se chevaucher :

CREATE TABLE reservation
(
  salle      TEXT,
  professeur TEXT,
  durant    tstzrange);

CREATE EXTENSION btree_gist ;

ALTER TABLE reservation ADD CONSTRAINT test_exclude EXCLUDE
USING gist (salle WITH =,durant WITH &&);

INSERT INTO reservation (professeur,salle,durant) VALUES
( 'marc', 'salle techno', '[2010-06-16 09:00:00, 2010-06-16 10:00:00)');
INSERT INTO reservation (professeur,salle,durant) VALUES
( 'jean', 'salle techno', '[2010-06-16 10:00:00, 2010-06-16 11:00:00)');
INSERT INTO reservation (professeur,salle,durant) VALUES
( 'jean', 'salle informatique', '[2010-06-16 10:00:00, 2010-06-16 11:00:00)');

INSERT INTO reservation (professeur,salle,durant) VALUES
( 'michel', 'salle techno', '[2010-06-16 10:30:00, 2010-06-16 11:00:00)');

ERROR:  conflicting key value violates exclusion constraint "test_exclude"
DETAIL : Key (salle, durant)=(salle techno,
              ["2010-06-16 10:30:00+02","2010-06-16 11:00:00+02"))
         conflicts with existing key
         (salle, durant)=(salle techno,
                          ["2010-06-16 10:00:00+02","2010-06-16 11:00:00+02")).

On notera que, là encore, l’extension btree_gist permet d’utiliser l’opérateur = avec un index GiST, ce qui nous permet d’utiliser = dans une contrainte d’exclusion.

Cet exemple illustre la puissance du mécanisme. Il est quasiment impossible de réaliser la même opération sans contrainte d’exclusion, à part en verrouillant intégralement la table, ou en utilisant le mode d’isolation serializable, qui a de nombreuses implications plus profondes sur le fonctionnement de l’application.

Autres fonctionnalités :

Enfin, précisons que les contraintes d’exclusion supportent toutes les fonctionnalités avancées que l’on est en droit d’attendre d’un système comme PostgreSQL : mode différé (deferred), application de la contrainte à un sous-ensemble de la table (permet une clause WHERE), ou utilisation de fonctions/expressions en place de références de colonnes.

Ce module permet de décomposer en trigramme les chaînes qui lui sont proposées :

 SELECT show_trgm('hello');

             show_trgm
 ---------------------------------
  {"  h"," he",ell,hel,llo,"lo "}

Une fois les trigrammes indexés, on peut réaliser de la recherche floue, ou utiliser des clauses LIKE malgré la présence de jokers (%) n’importe où dans la chaîne. À l’inverse, les indexations simples, de type B-tree, ne permettent des recherches efficaces que dans un cas particulier : si le seul joker de la chaîne est à la fin de celle ci (LIKE 'hello%' par exemple). Contrairement à la Full Text Search, la recherche par trigrammes ne réclame aucune modification des requêtes.

CREATE EXTENSION pg_trgm;

CREATE TABLE test_trgm (text_data text);

INSERT INTO test_trgm(text_data)
VALUES ('hello'), ('hello everybody'),
('helo young man'),('hallo!'),('HELLO !');
INSERT INTO test_trgm SELECT 'hola' FROM generate_series(1,1000);

CREATE INDEX test_trgm_idx ON test_trgm
  USING gist (text_data gist_trgm_ops);

SELECT text_data FROM test_trgm
 WHERE text_data like '%hello%';

    text_data
-----------------
 hello
 hello everybody

Cette dernière requête passe par l’index test_trgm_idx, malgré le % initial :

EXPLAIN (ANALYZE)
SELECT text_data FROM test_trgm
WHERE  text_data like '%hello%' ;

                                 QUERY PLAN
----------------------------------------------------------------------------
Index Scan using test_trgm_gist_idx on test_trgm
   (cost=0.41..0.63 rows=1 width=8) (actual time=0.174..0.204 rows=2 loops=1)
   Index Cond: (text_data ~~ '%hello%'::text)
   Rows Removed by Index Recheck: 1
 Planning time: 0.202 ms
 Execution time: 0.250 ms

On peut aussi utiliser un index GIN (comme pour le Full Text Search). Les index GIN ont l’avantage d’être plus efficaces pour les recherches exhaustives. Mais l’indexation pour la recherche des k éléments les plus proches (on parle de recherche k-NN) n’est disponible qu’avec les index GiST .

SELECT text_data, text_data <-> 'hello'
 FROM test_trgm
 ORDER BY text_data <-> 'hello'
 LIMIT 4;

nous retourne par exemple les deux enregistrements les plus proches de « hello » dans la table test_trgm.

GiST comme GIN sont intéressants si on a besoin d’indexer plusieurs colonnes, sans trop savoir quelles colonnes seront interrogées.

Pour indexer des scalaires, il faut utiliser les extensions btree_gist ou btree_gin.

CREATE EXTENSION IF NOT EXISTS btree_gist ;
CREATE EXTENSION IF NOT EXISTS btree_gin ;

Ce premier jeu de données utilisera des données qui se répètent beaucoup (de basse cardinalité) et les requêtes ramèneront de nombreuses lignes :

CREATE TABLE demo_gist (n int, i int, j int, k int, l int,
                        filler char(50) default ' ') ;
CREATE TABLE demo_gin  (n int, i int, j int, k int, l int,
                        filler char(50) default ' ') ;
CREATE INDEX demo_gist_idx ON demo_gist USING gist (i,j,k,l) ;
CREATE INDEX demo_gin_idx ON demo_gin USING gin (i,j,k,l) ;

INSERT INTO demo_gist
SELECT n, mod(n,37) AS i, mod(n,53) AS j, mod (n, 97) AS k, mod(n,229) AS l
FROM generate_series (1,1000000) n ;

INSERT INTO demo_gin
SELECT n, mod(n,37) AS i, mod(n,53) AS j, mod (n, 97) AS k, mod(n,229) AS l
FROM generate_series (1,1000000) n ;

Même en ne fournissant pas la première colonne des index, les index GIN et GiST sont utilisables :

EXPLAIN (ANALYZE, BUFFERS, COSTS OFF)
SELECT * FROM demo_gist WHERE j=17 AND l=17  ;

                               QUERY PLAN
-------------------------------------------------------------------------------
 Bitmap Heap Scan on demo_gist (actual time=1.615..1.662 rows=83 loops=1)
   Recheck Cond: ((j = 17) AND (l = 17))
   Heap Blocks: exact=83
   Buffers: shared hit=434
   ->  Bitmap Index Scan on demo_gist_i_j_k_l_idx (actual time=1.607..1.607 rows=83 loops=1)
         Index Cond: ((j = 17) AND (l = 17))
         Buffers: shared hit=351
 Planning Time: 0.026 ms
 Execution Time: 1.673 ms

EXPLAIN (ANALYZE, BUFFERS, COSTS OFF)
SELECT * FROM demo_gin WHERE j=17 AND l=17  ;

Bitmap Heap Scan on demo_gin (actual time=0.436..0.491 rows=83 loops=1)
   Recheck Cond: ((j = 17) AND (l = 17))
   Heap Blocks: exact=83
   Buffers: shared hit=100
   ->  Bitmap Index Scan on demo_gin_i_j_k_l_idx (actual time=0.427..0.427 rows=83 loops=1)
         Index Cond: ((j = 17) AND (l = 17))
         Buffers: shared hit=17
 Planning:
   Buffers: shared hit=1
 Planning Time: 0.031 ms
 Execution Time: 0.503 ms

Le GIN est ici plus efficace car le nombre de blocs d’index balayés est plus bas. En effet, avec une basse cardinalité, la compression du GIN joue à plein. (Pour ces tables identiques de 97 Mo sous PostgreSQL 16, l’index GiST fait 62 Mo, et le GIN 19 Mo seulement.)

Si la première colonne i était systématiquement fournie à la requête, on pourrait se contenter d’un index B-tree (30 Mo ici) ; mais il serait peu efficace pour les autres requêtes : la requête précédente donnerait souvent lieu à un Seq Scan parallélisé, bien que parfois un Bitmap Scan puisse apparaître avec des performances satisfaisantes.

Toujours dans ce cas précis, le temps de création de l’index GIN est aussi meilleur que le GiST d’un facteur deux au moins (et équivalent au B-tree), mais ce temps est très sensible à la valeur de maintenance_work_mem.

À l’inverse, le GiST est bien plus performant que le GIN dans d’autres types de requêtes commme celle-ci avec BETWEEN :

EXPLAIN (ANALYZE, BUFFERS, COSTS OFF)
SELECT * FROM demo_gist
WHERE j BETWEEN 17 AND 21 AND l BETWEEN 17 AND 21  ;

                               QUERY PLAN
-------------------------------------------------------------------------------
 Bitmap Heap Scan on demo_gist (actual time=8.419..8.895 rows=2059 loops=1)
   Recheck Cond: ((j >= 17) AND (j <= 21) AND (l >= 17) AND (l <= 21))
   Heap Blocks: exact=757
   Buffers: shared hit=1744
   ->  Bitmap Index Scan on demo_gist_i_j_k_l_idx (actual time=8.355..8.355 rows=2059 loops=1)
         Index Cond: ((j >= 17) AND (j <= 21) AND (l >= 17) AND (l <= 21))
         Buffers: shared hit=987
 Planning Time: 0.030 ms
 Execution Time: 8.958 ms

EXPLAIN (ANALYZE, BUFFERS, COSTS OFF)
SELECT * FROM demo_gin
WHERE j BETWEEN 17 AND 21 AND l BETWEEN 17 AND 21  ;

                               QUERY PLAN
-------------------------------------------------------------------------------
 Bitmap Heap Scan on demo_gin (actual time=68.281..69.313 rows=2059 loops=1)
   Recheck Cond: ((j >= 17) AND (j <= 21) AND (l >= 17) AND (l <= 21))
   Heap Blocks: exact=757
   Buffers: shared hit=1760
   ->  Bitmap Index Scan on demo_gin_i_j_k_l_idx (actual time=68.174..68.174 rows=2059 loops=1)
         Index Cond: ((j >= 17) AND (j <= 21) AND (l >= 17) AND (l <= 21))
         Buffers: shared hit=1003
 Planning:
   Buffers: shared hit=1
 Planning Time: 0.056 ms
 Execution Time: 69.435 ms

Un index GiST permet aussi l’Index Scan et parfois l’Index Only Scan, au contraire d’un index GIN, qui se limitera toujours à un Bitmap Scan. L’intérêt varie selon les requêtes :

EXPLAIN (ANALYZE, BUFFERS, COSTS OFF)
SELECT j,l FROM demo_gist WHERE j=17 AND l=17 ;

                               QUERY PLAN
-------------------------------------------------------------------------------
 Index Only Scan using demo_gist_i_j_k_l_idx on demo_gist (actual time=0.043..1.563 rows=83 loops=1)
   Index Cond: ((j = 17) AND (l = 17))
   Heap Fetches: 0
   Buffers: shared hit=352
 Planning Time: 0.024 ms
 Execution Time: 1.572 ms

EXPLAIN (ANALYZE, BUFFERS, COSTS OFF)
SELECT j,l FROM demo_gin WHERE j=17 AND l=17 ;

                               QUERY PLAN
-------------------------------------------------------------------------------
 Bitmap Heap Scan on demo_gin (actual time=0.699..0.796 rows=83 loops=1)
   Recheck Cond: ((j = 17) AND (l = 17))
   Heap Blocks: exact=83
   Buffers: shared hit=100
   ->  Bitmap Index Scan on demo_gin_i_j_k_l_idx (actual time=0.683..0.683 rows=83 loops=1)
         Index Cond: ((j = 17) AND (l = 17))
         Buffers: shared hit=17
 Planning:
   Buffers: shared hit=1
 Planning Time: 0.069 ms
 Execution Time: 0.819 ms

Si la cardinalité est élevée (les données sont toutes différentes), l’index GIN perd son avantage en taille. En effet, si l’on remplace les données précédentes par un jeu de données toutes différentes :

TRUNCATE TABLE demo_gin ;
TRUNCATE TABLE demo_gist ;
INSERT INTO demo_gin
SELECT n, n AS i, 100e6+n AS j, 200e6+n AS k, 300e6+n AS l
FROM generate_series (1,1000000) n ;
INSERT INTO demo_gist
SELECT n, n AS i, 100e6+n AS j, 200e6+n AS k, 300e6+n AS l
FROM generate_series (1,1000000) n ;

la taille de l’index GIN passe à 218 Mo (plus que la table), alors que l’index GiST ne monte qu’à 85 Mo (et un index B-tree resterait à 30 Mo). Cela ne rend pas forcément l’index GIN moins efficace dans l’absolu, mais a un effet défavorable sur le cache.

Index bloom :

Il existe encore un type d’index, rarement utilisé : l’index Bloom, qui réclame l’installation de l’extension bloom (livrée avec PostgreSQL). Cet index est basé sur les filtres bloom, de nature probabiliste. Les lignes retournées par l’index doivent être revérifiées dans la table, ce qui impose un Recheck systématique. L’index est rapide à générer, et encore plus petit que les index ci-dessus (15 Mo ici), mais cet index doit être complètement parcouru. Les performances sont donc moins bonnes qu’avec GiST ou GIN. Il est aussi limité aux entiers et chaînes de caractères, et à une recherche sur l’égalité (donc il est inadapaté aux critères BETWEEN et LIKE). Si ses performances suffisent, un index bloom peut être utile dans le cas où de nombreuses colonnes sont susceptibles d’être interrogées, car il évite de créer d’autres index B-tree ou GIN coûteux en place. Sur une table identique à celles ci-dessus, le plan est :

EXPLAIN (ANALYZE, BUFFERS, COSTS OFF)
SELECT * FROM demo_bloom WHERE j=100000017 AND l=300000017  ;

                               QUERY PLAN
-------------------------------------------------------------------------------
 Bitmap Heap Scan on demo_bloom (actual time=3.732..3.753 rows=1 loops=1)
   Recheck Cond: ((j = 100000017) AND (l = 300000017))
   Rows Removed by Index Recheck: 27
   Heap Blocks: exact=28
   Buffers: shared hit=1961 read=28
   ->  Bitmap Index Scan on demo_bloom_i_j_k_l_idx (actual time=3.721..3.722 rows=28 loops=1)
         Index Cond: ((j = 100000017) AND (l = 300000017))
         Buffers: shared hit=1933 read=28
 Planning Time: 0.042 ms
 Execution Time: 3.767 ms

Choix du type d’index pour une indexation multicolonne :

Les exemples ci-dessus viennent d’une instance avec la configuration par défaut de PostgreSQL. Rappelons que les paramètres effective_io_concurrency, seq_page_cost et random_page_cost (liés aux disques) et effective_cache_size (lié à la mémoire), influent fortement sur le choix d’un parcours Index Scan, Bitmap Scan ou Seq Scan quand la requête balaie beaucoup de lignes. La répartition physique des données joue aussi (sur l’efficacité du cache comme sur celle des Index Scan et Bitmap Scan.) Le type de données à indexer, leur longueur, l’opérateur… a aussi une importance.

Au final, pour une indexation multicolonne d’une table, il faudra tester les types d’index disponibles avec la charge, le paramétrage et les requêtes réelles, des données réelles, et arbitrer en tenant compte des tailles des index (donc de l’impact sur le cache), des durées de génération, des performances pures et des performances en pratique acceptables…

Un index BRIN ne stocke pas les valeurs de la table, mais quelles plages de valeurs se rencontrent dans un ensemble de blocs. Cela réduit la taille de l’index et permet d’exclure un ensemble de blocs lors d’une recherche.

Exemple

Soit une table brin_demo de 2 millions de personnes, triée par âge :

CREATE TABLE brin_demo (id int, age int);
SET work_mem TO '300MB' ;
INSERT INTO brin_demo
SELECT id, trunc(random() * 90 + 1)  AS age
FROM   generate_series(1,2e6) id
ORDER  BY age ;

=# \dt+ brin_demo
                              List of relations
 Schema |   Name    | Type  |  Owner   | Persistence |  Size   | Description
--------+-----------+-------+----------+-------------+---------+-------------
 public | brin_demo | table | postgres | permanent   |   69 MB |

Un index BRIN va contenir une plage des valeurs pour chaque bloc. Dans notre exemple, l’index contiendra la valeur minimale et maximale de plusieurs blocs. La conséquence est que ce type d’index prend très peu de place et il peut facilement tenir en RAM (réduction des opérations des disques). Il est aussi plus rapide à construire et maintenir.

CREATE INDEX brin_demo_btree_idx ON brin_demo USING btree (age);
CREATE INDEX brin_demo_brin_idx  ON brin_demo USING brin (age);

=# \di+ brin_demo*
                        List of relations
 Schema |         Name         | Type  | … |    Table     | Persistence | Size  | …
--------+----------------------+-------+---+--------------+-------------+-------+---
 public | brin_demo_brin_idx   | index |   | brin_demo    | permanent   | 48 kB |
 public | brin_demo_btree_idx  | index |   | brin_demo    | permanent   | 13 MB |

On peut consulter le contenu de cet index, et constater que chacune de ses entrées liste les valeurs de age par paquet de 128 blocs (cette valeur peut se changer) :

CREATE EXTENSION IF NOT EXISTS pageinspect ;
SELECT *
FROM brin_page_items(get_raw_page('brin_demo_brin_idx', 2),'brin_demo_brin_idx');

 itemoffset | blknum | attnum | allnulls | hasnulls | placeholder |   value
------------+--------+--------+----------+----------+-------------+------------
          1 |      0 |      1 | f        | f        | f           | {1 .. 2}
          2 |    128 |      1 | f        | f        | f           | {2 .. 3}
          3 |    256 |      1 | f        | f        | f           | {3 .. 4}
          4 |    384 |      1 | f        | f        | f           | {4 .. 6}
          5 |    512 |      1 | f        | f        | f           | {6 .. 7}
          6 |    640 |      1 | f        | f        | f           | {7 .. 8}
          7 |    768 |      1 | f        | f        | f           | {8 .. 10}
          8 |    896 |      1 | f        | f        | f           | {10 .. 11}
          9 |   1024 |      1 | f        | f        | f           | {11 .. 12}
…
         66 |   8320 |      1 | f        | f        | f           | {85 .. 86}
         67 |   8448 |      1 | f        | f        | f           | {86 .. 88}
         68 |   8576 |      1 | f        | f        | f           | {88 .. 89}
         69 |   8704 |      1 | f        | f        | f           | {89 .. 90}
         70 |   8832 |      1 | f        | f        | f           | {90 .. 90}

La colonne blknum indique le début de la tranche de blocs, et value la plage de valeurs rencontrées. Les personnes de 87 ans sont donc présentes uniquement entre les blocs 8448 à 8575, ce qui se vérifie :

SELECT min (ctid), max (ctid) FROM brin_demo WHERE age = 87 ;

    min     |    max
------------+-----------
 (8457,170) | (8556,98)

Testons une requête avec uniquement ce petit index BRIN :

DROP INDEX brin_demo_btree_idx ;

EXPLAIN (ANALYZE,BUFFERS,COSTS OFF) SELECT count(*) FROM brin_demo WHERE age = 87 ;

                               QUERY PLAN
-------------------------------------------------------------------------------
 Aggregate (actual time=4.838..4.839 rows=1 loops=1)
   Buffers: shared hit=130
   ->  Bitmap Heap Scan on brin_demo (actual time=0.241..3.530 rows=22212 loops=1)
         Recheck Cond: (age = 87)
         Rows Removed by Index Recheck: 6716
         Heap Blocks: lossy=128
         Buffers: shared hit=130
         ->  Bitmap Index Scan on brin_demo_brin_idx (actual time=0.024..0.024 rows=1280 loops=1)
               Index Cond: (age = 87)
               Buffers: shared hit=2
 Planning:
   Buffers: shared hit=5
 Planning Time: 0.084 ms
 Execution Time: 4.873 ms

On constate que l’index n’est consulté que sur 2 blocs. Le nœud Bitmap Index Scan renvoie les 128 blocs contenant des valeurs entre 86 et 88, et ces blocs sont récupérés dans la table (heap). 6716 lignes sont ignorées, et 22 212 conservées. Le temps de 4,8 ms est bon.

Certes, un index B-tree, bien plus gros, aurait fait encore mieux dans ce cas précis, qui est modeste. Mais plus la table est énorme, plus une requête en ramène une proportion importante, plus les aller-retours entre index et table sont pénalisants, et plus l’index BRIN devient compétitif, en plus de rester très petit.

Par contre, si la table se fragmente, même un peu, les lignes d’un même age se retrouvent réparties dans toute la table, et l’index BRIN devient bien moins efficace :

UPDATE brin_demo
SET    age=age+0
WHERE  random()>0.99 ;  -- environ 20000 lignes
VACUUM brin_demo ;
UPDATE brin_demo
SET    age=age+0
WHERE  age > 80 AND random()>0.90 ;  -- environ 22175 lignes

VACUUM ANALYZE brin_demo ;

SELECT *
FROM brin_page_items(get_raw_page('brin_demo_brin_idx', 2),'brin_demo_brin_idx');

 itemoffset | blknum | attnum | allnulls | hasnulls | placeholder |   value
------------+--------+--------+----------+----------+-------------+------------
          1 |      0 |      1 | f        | f        | f           | {1 .. 81}
          2 |    128 |      1 | f        | f        | f           | {2 .. 81}
          3 |    256 |      1 | f        | f        | f           | {3 .. 81}
          4 |    384 |      1 | f        | f        | f           | {4 .. 81}
…
         45 |   5632 |      1 | f        | f        | f           | {58 .. 87}
         46 |   5760 |      1 | f        | f        | f           | {59 .. 87}
         47 |   5888 |      1 | f        | f        | f           | {60 .. 87}
…
         56 |   7040 |      1 | f        | f        | f           | {72 .. 89}
         57 |   7168 |      1 | f        | f        | f           | {73 .. 89}
         58 |   7296 |      1 | f        | f        | f           | {75 .. 89}
…
         67 |   8448 |      1 | f        | f        | f           | {86 .. 88}
         68 |   8576 |      1 | f        | f        | f           | {88 .. 89}
         69 |   8704 |      1 | f        | f        | f           | {89 .. 90}
         70 |   8832 |      1 | f        | f        | f           | {1 .. 90}

EXPLAIN (ANALYZE,BUFFERS,COSTS OFF) SELECT count(*) FROM brin_demo WHERE age = 87 ;

                               QUERY PLAN
-------------------------------------------------------------------------------
 Aggregate (actual time=71.053..71.055 rows=1 loops=1)
   Buffers: shared hit=3062
   ->  Bitmap Heap Scan on brin_demo (actual time=2.451..69.851 rows=22303 loops=1)
         Recheck Cond: (age = 87)
         Rows Removed by Index Recheck: 664141
         Heap Blocks: lossy=3060
         Buffers: shared hit=3062
         ->  Bitmap Index Scan on brin_demo_brin_idx (actual time=0.084..0.084 rows=30600 loops=1)
               Index Cond: (age = 87)
               Buffers: shared hit=2
 Planning:
   Buffers: shared hit=1
 Planning Time: 0.069 ms
 Execution Time: 71.102 ms

3060 blocs et 686 444 lignes, la plupart inutiles, ont été lus dans la table (en gros, un tiers de celles-ci). Cela ne devient plus très intéressant par rapport à un parcours complet de la table.

Pour rendre son intérêt à l’index, il faut reconstruire la table avec les données dans le bon ordre avec la commande CLUSTER. Hélas, c’est une opération au moins aussi lourde et bloquante qu’un VACUUM FULL. De plus, le tri de la table ne peut se faire par l’index BRIN, et il faut recréer un index B-tree au moins le temps de l’opération.

CREATE INDEX brin_demo_btree_idx ON brin_demo USING btree (age);
CLUSTER brin_demo USING brin_demo_btree_idx;
SELECT *
FROM brin_page_items(get_raw_page('brin_demo_brin_idx', 2),'brin_demo_brin_idx') ;

 itemoffset | blknum | attnum | allnulls | hasnulls | placeholder |   value
------------+--------+--------+----------+----------+-------------+------------
          1 |      0 |      1 | f        | f        | f           | {1 .. 2}
          2 |    128 |      1 | f        | f        | f           | {2 .. 3}
…
         68 |   8576 |      1 | f        | f        | f           | {88 .. 89}
         69 |   8704 |      1 | f        | f        | f           | {89 .. 90}
         70 |   8832 |      1 | f        | f        | f           | {90 .. 90}

On revient alors à la situation de départ.

Utilité d’un index BRIN

Pour qu’un index BRIN soit utile, il faut donc :

• que les données soit naturellement triées dans la table, et le restent (série temporelle, décisionnel avec imports réguliers…) ;
• que la table soit à « insertion seule » pour conserver l’ordre physique ;
• ou que l’on ait la disponibilité nécessaire pour reconstruire régulièrement la table avec CLUSTER et éviter que les performances se dégradent au fil du temps.

Sous ces conditions, les BRIN sont indiqués si l’on a des problèmes de volumétrie, ou de temps d’écritures dus aux index B-tree, ou pour éviter de partitionner une grosse table dont les requêtes ramènent une grande proportion.

Index BRIN sur clé composée

Prenons un autre exemple avec plusieurs colonnes et un type text :

CREATE TABLE test (id serial PRIMARY KEY, val text);
INSERT INTO test (val) SELECT md5(i::text) FROM generate_series(1, 10000000) i;

La colonne id sera corrélée (c’est une séquence), la colonne md5 ne sera pas du tout corrélée. L’index BRIN porte sur les deux colonnes :

CREATE INDEX test_brin_idx ON test USING brin (id,val);

Pour une table de 651 Mo, l’index ne fait ici que 104 ko.

Pour voir son contenu :

SELECT itemoffset, blknum, attnum,value
FROM brin_page_items(get_raw_page('test_brin_idx', 2),'test_brin_idx')
LIMIT 4 ;

 itemoffset | blknum | attnum |                 value
------------+--------+--------+----------------------------------------
          1 |      0 |      1 | {1 .. 15360}
          1 |      0 |      2 | {00003e3b9e5336685200ae85d21b4f5e .. fffb8ef15de06d87e6ba6c830f3b6284}
          2 |    128 |      1 | {15361 .. 30720}
          2 |    128 |      2 | {00053f5e11d1fe4e49a221165b39abc9 .. fffe9f664c2ddba4a37bcd35936c7422}

La colonne attnum correspond au numéro d’attribut du champ dans la table. L’id est bien corrélé aux numéros de bloc, contrairement à la colonne val. Ce que nous confirme bien la vue pg_stats :

SELECT tablename, attname, correlation
FROM   pg_stats WHERE  tablename='test' ORDER BY attname ;

 tablename | attname | correlation
-----------+---------+-------------
 test      | id      |           1
 test      | val     |  0.00528745

Si l’on teste la requête suivante, on s’aperçoit que PostgreSQL effectue un parcours complet (Seq Scan) de façon parallélisée ou non, et n’utilise donc pas l’index BRIN. Pour comprendre pourquoi, essayons de l’y forcer :

SET enable_seqscan TO off ;
SET max_parallel_workers_per_gather TO 0;

EXPLAIN (BUFFERS,ANALYZE) SELECT * FROM test WHERE val
BETWEEN 'a87ff679a2f3e71d9181a67b7542122c'
    AND 'eccbc87e4b5ce2fe28308fd9f2a7baf3';

                                   QUERY PLAN
--------------------------------------------------------------------------------
 Bitmap Heap Scan on test  (cost=721.46..234055.46 rows=2642373 width=37) (actual time=2.558..1622.646 rows=2668675 loops=1)
   Recheck Cond: ((val >= 'a87ff679a2f3e71d9181a67b7542122c'::text)
              AND (val <= 'eccbc87e4b5ce2fe28308fd9f2a7baf3'::text))
   Rows Removed by Index Recheck: 7331325
   Heap Blocks: lossy=83334
   Buffers: shared hit=83349
   ->  Bitmap Index Scan on test_brin_idx  (cost=0.00..60.86 rows=10000000 width=0) (actual time=2.523..2.523 rows=833340 loops=1)
         Index Cond: ((val >= 'a87ff679a2f3e71d9181a67b7542122c'::text)
                  AND (val <= 'eccbc87e4b5ce2fe28308fd9f2a7baf3'::text))
         Buffers: shared hit=15
 Planning:
   Buffers: shared hit=1
 Planning Time: 0.079 ms
 Execution Time: 1703.018 ms