Introduction aux index PostgreSQL

• Les index PostgreSQL sont des structures essentielles pour accélérer l’accès aux données, en réduisant la quantité de données à lire sur le disque afin d’améliorer les performances des requêtes
• Les index existent sous différentes formes, notamment Btree, Hash, BRIN, GIN, GiST, SP-GiST, chacune étant optimisée pour des caractéristiques de données et des modèles de requêtes différents
• Les index impliquent plusieurs coûts, notamment en espace disque, performances d’écriture, complexité du query planner et utilisation mémoire
• Des fonctionnalités avancées comme les index partiels, index multicolonnes, index de couverture et index d’expression permettent de maximiser l’efficacité dans des cas précis
• Le choix et la gestion appropriés des index sont présentés comme un élément clé de l’optimisation des performances de PostgreSQL

---

Concepts de base des index

• Un index est une structure qui permet à la base de données de réduire la quantité de données lues sur le disque afin d’accélérer les requêtes
  • Les clés primaires, clés uniques et contraintes d’exclusion sont également implémentées via des index
  • Un index est efficace lorsque le résultat de la requête représente moins de 15 à 20 % de la table entière ; au-delà, un sequential scan peut être plus efficace
• PostgreSQL fournit par défaut 6 types d’index, et d’autres peuvent être utilisés via des extensions
  • Chaque index relie une valeur de clé à la position correspondante des données (TID)

Structure des données stockées sur disque

• Les tables PostgreSQL sont stockées sous forme de fichiers heap, organisés en pages de 8 KB
• Chaque ligne (tuple) est stockée sans ordre particulier, et son adresse interne est identifiée par ctid (current tuple id)
  • Exemple : (0,1) signifie le premier tuple de la page 0
• Les index relient ces positions dans le heap (ctid) dans une structure arborescente afin de permettre une recherche rapide

Comment les index accélèrent l’accès aux données

• Sans index, PostgreSQL effectue un sequential scan en lisant toutes les pages
  • Dans l’exemple de requête, la recherche de name='Ronaldo' lit 6272 pages et prend 265 ms
• Avec un index, l’exécution bascule vers un Index Scan, qui ne lit que 4 pages et se termine en 0,077 ms
  • L’index associe les valeurs à leur ctid afin de retrouver rapidement uniquement les lignes nécessaires
• La taille d’un fichier d’index peut être comparable à celle de la table (ex. : table de 30 MB → index de 30 MB)

---

Les coûts liés aux index

• Au-delà du gain de performance, les index s’accompagnent de plusieurs contraintes

Espace disque

• Les index occupent un espace de stockage séparé et peuvent être plus volumineux que la table
  • Cela engendre des coûts supplémentaires lors des sauvegardes, de la réplication et de la reprise après incident
  • L’efficacité de l’espace peut être améliorée avec des index partiels, index multicolonnes, BRIN, etc.

Opérations d’écriture

• Lors de UPDATE, INSERT et DELETE, si une colonne indexée est modifiée, cela entraîne un surcoût de mise à jour de l’index

Query planner

• Plus il y a d’index, plus les options à considérer par le planner augmentent, ce qui allonge le temps nécessaire à l’établissement du plan de requête

Utilisation mémoire

• Les pages d’index sont chargées et mises en cache dans le shared buffer, ce qui augmente la pression mémoire quand les index se multiplient
• En raison de la limite de taille des nœuds btree, plus les colonnes sont volumineuses, plus la profondeur de l’arbre augmente
• Des opérations comme le tri, les scans multicolonnes, vacuum, reindex, etc. consomment également davantage de work memory

---

Principaux types d’index

Btree

• Structure d’index par défaut de PostgreSQL, c’est l’index générique utilisé par la plupart des SGBD
  • Il permet des recherches rapides avec une complexité temporelle de O(log n)
  • Il repose sur une structure d’arbre équilibré où toutes les feuilles ont la même profondeur
  • Il est avantageux pour les opérations ORDER BY et JOIN, et sert aux contraintes de clé primaire et clé unique
• Les nœuds internes stockent des pointeurs vers les nœuds inférieurs, tandis que les feuilles stockent les clés et les pointeurs vers le heap
• Des pointeurs vers les nœuds gauche et droit permettent une navigation bidirectionnelle

Utilisation de plusieurs index

• PostgreSQL peut combiner plusieurs index via des opérations bitmap AND/OR pour traiter des conditions composées
  • Exemple : pour la condition age=30 AND login_count=100, les bitmaps de deux index sont combinés

Index multicolonnes

• Il est possible de regrouper plusieurs colonnes dans un seul index pour économiser de l’espace et améliorer la vitesse
  • Toutefois, l’ordre des colonnes est important, et seules les conditions correspondant au préfixe gauche peuvent utiliser l’index

Index partiels

• Ils indexent uniquement certaines lignes à l’aide d’une condition
  • Réduction de la taille de l’index, meilleure adaptation à la RAM et amélioration de la vitesse de lecture
  • Exemple : create index on rules(status) where status='enabled';
  • Ils sont utiles lorsque la distribution des valeurs est déséquilibrée (status <> 'TODO', etc.)

Index de couverture

• Si toutes les colonnes nécessaires à la requête sont incluses dans l’index, il est possible de retourner le résultat sans accès au heap (index-only scan)
  • create index abc_cov_idx on bar(a, b) including c;
  • Ils sont plus efficaces en espace que les index multicolonnes

Index d’expression

• Ils indexent non pas la valeur brute d’une colonne, mais le résultat d’une fonction ou d’une expression
  • Exemple : CREATE INDEX idx_lower_name ON customers (lower(name));
  • Ils sont utiles pour les recherches sur des valeurs transformées comme LOWER(name)
  • Seules les fonctions immutables peuvent être utilisées

---

Hash

• Index basé sur une structure de table de hachage, efficace en espace pour les longues chaînes ou les UUID
  • Il stocke un code de hachage sur 32 bits afin de réduire la taille
  • Il ne prend en charge que les comparaisons d’égalité (=), et ne permet ni tri ni index multicolonnes
  • Lorsque la distribution de hachage est uniforme, il peut offrir des performances de lecture supérieures à Btree
• Selon la documentation officielle, les index hash réduisent les E/S sur les grandes tables grâce à un accès direct aux pages de bucket

---

BRIN (Block Range Index)

• Index qui ne stocke que les valeurs minimales et maximales de chaque plage de blocs
  • Il est extrêmement compact et favorable au cache
  • Il convient aux très grandes tables, aux données append-only et aux séries temporelles
• Si les lignes sont souvent mises à jour, son efficacité diminue à cause des duplications liées au MVCC
• Le paramètre pages_per_range permet d’ajuster le compromis entre précision et taille

---

GIN (Generalized Inverted Index)

• Index adapté à la recherche dans des données composées
  • Il prend en charge la recherche d’éléments spécifiques dans du texte, des tableaux, du JSONB, etc.
  • Il utilise des stratégies dédiées (opclass) selon le type de données
  • Pour JSON, il est recommandé d’utiliser des colonnes JSONB ; pour le texte, tsvector ou l’extension pg_trgm

---

GiST & SP-GiST

• Le Generalized Search Tree (GiST) et le Space-Partitioned GiST (SP-GiST) sont des frameworks d’implémentation d’index pour certains types de données
  • GiST prend en charge une structure équilibrée, tandis que SP-GiST prend en charge une structure déséquilibrée
  • Ils sont utilisés pour les données géographiques, inet, intervalles, vecteurs de texte, etc.
  • GIN offre des lectures plus rapides, tandis que GiST coûte moins cher à construire et à maintenir
  • Pour la recherche plein texte, le choix entre les deux dépend des besoins

---

Conclusion

• Les index sont au cœur de l’optimisation des performances de PostgreSQL, et il est essentiel de trouver un équilibre entre vitesse de lecture et coûts d’écriture et de stockage
• En choisissant le type d’index adapté aux caractéristiques des données et aux modèles de requêtes, il est possible d’exploiter une base de données plus rapide et plus efficace
• Une conception appropriée des index est un élément indispensable pour garantir la scalabilité et la stabilité des systèmes à grande échelle

[GN⁺]

Réactions sur Hacker News

• La documentation officielle de PostgreSQL est vraiment très bien écrite et agréable à lire, donc je la partage.
  Document d’introduction aux index PostgreSQL

• La partie sur les index multicolonnes correspond presque exactement à ce que j’avais appris.
  Mais je me demandais si c’était toujours vrai dans les versions récentes de PostgreSQL.
  J’ai déjà vu un bitmap index scan être utilisé sur une requête similaire au troisième exemple, et depuis, j’ai recommencé à remettre en question la « doctrine » habituelle.
  Au passage, pour tout ce qui touche aux index, je pense que le site et le livre Use The Index, Luke sont des classiques que toute l’équipe devrait lire.

  • Dans PostgreSQL 18, index skip scan a été ajouté, ce qui permet désormais des recherches efficaces en se basant uniquement sur les colonnes secondaires d’un index multicolonne.
    C’était déjà possible dans les versions précédentes, mais cela nécessitait alors un scan complet de l’index, donc c’était inefficace.
    Vidéo associée : lien YouTube
  • Un bitmap index scan permet de réduire l’ensemble des pages susceptibles de contenir les données, mais comme il faut ensuite revérifier les conditions réelles, les performances sont inférieures à celles d’un scan d’index classique.

• J’aimerais bien que PostgreSQL prenne en charge nativement l’incremental view maintenance.
  C’est un concept qui, comme un index, se met automatiquement à jour quand les données de base changent, mais qui s’applique à des vues arbitraires plutôt qu’à une vue spécifique.

  • C’est un problème assez difficile, car il implique la gestion des transactions.
    Il existe beaucoup de projets sur le sujet : Noria, Materialize, Apache Flink, GCP Continuous Queries, Spark Streaming Tables, Delta Tables, ClickHouse streaming tables, TimescaleDB, ksqlDB, StreamSQL, etc.
    Côté PostgreSQL, une extension appelée pg_ivm a récemment commencé à s’attaquer à ce problème.
  • Pour les données de séries temporelles, la fonctionnalité continuous aggregates de TimescaleDB remplit déjà ce rôle.

• La discussion B-tree vs index Hash est intéressante.
  Beaucoup pensent qu’un hash est meilleur pour une colonne d’ID, mais en pratique, le B-tree par défaut est plus efficace.
  En particulier, quand on insère des valeurs presque séquentielles, la structure en arbre est plus avantageuse.
  Cela dit, dans le billet de blog mentionné cette fois-ci, c’est au contraire le hash qui a gagné au benchmark.

• Le timing de cet article tombait bien.
  La règle de la colonne de tête pour les index multicolonnes m’a toujours semblé confuse, mais grâce au bitmap index scan, ce n’est plus aussi critique qu’avant.
  La fonctionnalité skip scan de PostgreSQL 18 change fortement les idées reçues, donc si vous avez appris cela sur la base d’anciennes versions, il faut mettre à jour votre modèle mental.

• Je trouve que c’est un excellent texte de référence sur PostgreSQL.
  Pour les index B-tree, je consulte souvent Use The Index, Luke depuis longtemps.

• Je pense que c’est une lecture indispensable.
  On est bien au-delà d’une simple introduction : c’est approfondi tout en restant tout à fait lisible, tant qu’on n’entre pas dans les structures internes.

• J’aime bien ce style d’écriture simple et humble.
  C’est une bonne manière de transmettre directement le savoir.