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