PostgreSQLLa base de données la plus sophistiquée au monde.
Documentation PostgreSQL 14.13 » Internes » Index GIN » Implantation

67.4. Implantation

En interne, un index GIN contient un index B-tree construit sur des clés, où chaque clé est une partie d'un ou plusieurs éléments indexé (un membre d'un tableau, par exemple) et où chaque enregistrement d'une page feuille contient soit un pointeur vers un B-tree de pointeurs vers la table (un « posting tree »), ou une liste simple de pointeurs vers les enregistrements (une « posting list ») quand la liste est suffisamment courte pour tenir dans un seul enregistrement d'index avec la valeur de la clé. Figure 67.1 illustre ces composants d'un index GIN.

À partir de PostgreSQL 9.1, des valeurs NULL de clé peuvent être incluses dans l'index. Par ailleurs, des NULLs fictifs sont inclus dans l'index pour des éléments indexés qui sont NULL ou ne contiennent aucune clé d'après extractValue. Cela permet des recherches retournant des éléments vides.

Les index multi-colonnes GIN sont implantés en construisant un seul B-tree sur des valeurs composites (numéro de colonne, valeur de clé). Les valeurs de clés pour les différentes colonnes peuvent être de types différents.

Figure 67.1. Cœur de GIN


67.4.1. Technique GIN de mise à jour rapide

Mettre à jour un index GIN a tendance à être lent en raison de la nature intrinsèque des index inversés : insérer ou mettre à jour un ligne de la table peut causer de nombreuses insertions dans l'index(une pour chaque clé extraite de l'élément indexé). GIN est capable de reporter à plus tard la plupart de ce travail en insérant les nouveaux enregistrements dans une liste temporaire et non triée des entrées en attente. Quand un vacuum ou autoanalyze est déclenché sur la table, ou quand la fonction gin_clean_pending_list est appelée, ou si la liste en attente devient plus importante que gin_pending_list_limit, les entrées sont déplacées vers la structure de données GIN principale en utilisant la même technique d'insertion de masse que durant la création de l'index. Ceci améliore grandement la vitesse de mise à jour de l'index GIN, même en prenant en compte le surcoût engendré au niveau du vacuum. De plus, ce travail supplémentaire peut être attribué à un processus d'arrière-plan plutôt qu'à la requête en avant-plan.

Le principal défaut de cette approche est que les recherches doivent parcourir la liste d'entrées en attente en plus de l'index habituel, et que, par conséquent, une grande liste d'entrées en attente ralentira les recherches de manière significative. Un autre défaut est que, bien que la majorité des mises à jour sont rapides, une mise à jour qui rend la liste d'attente « trop grande » déclenchera un cycle de nettoyage immédiat et sera donc bien plus lente que les autres mises à jour. Une utilisation appropriée d'autovacuum peut minimiser ces deux problèmes.

Si la cohérence des temps de réponse est plus importante que la vitesse de mise à jour, l'utilisation de liste d'entrées en attente peut être désactivée en désactivant le paramètre de stockage fastupdate pour un index GIN. Voir CREATE INDEX pour plus de détails.

67.4.2. Algorithme de mise en correspondance partielle

GIN peut accepter des requêtes de « correspondances partielles », dans lesquelles la requête ne détermine pas une correspondance parfaite pour une ou plusieurs clés, mais que la correspondance tombe à une distance suffisamment proche des valeurs de clé (dans l'ordre de tri des clés déterminé par la méthode d'appui compare). Au lieu de retourner une valeur de clé à mettre en correspondance de façon exacte, la méthode extractQuery retourne une valeur de clé qui est la limite inférieure de la plage à rechercher, et retourne l'indicateur pmatch positionné à true. La plage de clé est alors parcourue en utilisant la méthode comparePartial. comparePartial doit renvoyer 0 pour une clé d'index correspondante, une valeur négative pour une non-correspondance qui est toujours dans la plage de recherche, et une valeur positive si la clé d'index est en dehors de la plage de correspondance.