GIN est l'acronyme de Generalized Inverted Index (ou index générique inversé). GIN est prévu pour traiter les cas où les éléments à indexer sont des valeurs composites, et où les requêtes devant utiliser l'index doivent rechercher des valeurs d'éléments apparaissant dans ces éléments composites. Par exemple, les éléments pourraient être des documents, et les requêtes pourraient être des recherches de documents contenant des mots spécifiques.
Nous utilisons le mot élément (item en version originale) pour désigner une valeur composite qui doit être indexée, et le mot clé (clé en version originale) pour désigner une des valeurs d'un élément. GIN stocke et recherche toujours des clés, jamais des éléments eux même.
Un index GIN stocke un jeu de paires de (clé, liste), où liste (posting list en version originale) est un ensemble d'identifiants de ligne (row ID en version originale) où la clé existe. Le même identifiant peut apparaître dans plusieurs listes, puisqu'un élément peut contenir plus d'une clé. Chaque clé est stockée une seule fois, ce qui fait qu'un index GIN est très compact dans le cas où une clé apparaît de nombreuses fois.
GIN est générique dans le sens où la méthode d'accès GIN n'a pas besoin de connaître les opérations spécifiques qu'elle accélère. À la place, elle utilise les stratégies spécifiques définies pour des types de données. La stratégie définit comment extraire les clés des éléments à indexer et des conditions des requêtes, et comment déterminer si une ligne qui contient des valeurs de clés d'une requête répond réellement à la requête.
Un des avantages de GIN est la possibilité qu'il offre que des types de données personnalisés avec des méthodes d'accès appropriées soient développés par un expert du domaine du type de données, plutôt que par un expert en bases de données. La méthode GiST offre le même avantage.
L'implantation de GIN dans PostgreSQL est principalement l'œuvre de Teodor Sigaev et Oleg Bartunov. Plus d'informations sur GIN sont disponibles sur leur site web.
La distribution PostgreSQL inclut les classes d'opérateur GIN affichées dans Tableau 64.3. (Certains des modules optionnels décrits dans Annexe F fournissent des classes d'opérateurs GIN supplémentaires.)
Tableau 64.3. Classes d'opérateur GIN natives
Nom | Opérateurs indexables |
---|---|
array_ops | && (anyarray,anyarray) |
@> (anyarray,anyarray) | |
<@ (anyarray,anyarray) | |
= (anyarray,anyarray) | |
jsonb_ops | @> (jsonb,jsonb) |
@? (jsonb,jsonpath) | |
@@ (jsonb,jsonpath) | |
? (jsonb,text) | |
?| (jsonb,text[]) | |
?& (jsonb,text[]) | |
jsonb_path_ops | @> (jsonb,jsonb) |
@? (jsonb,jsonpath) | |
@@ (jsonb,jsonpath) | |
tsvector_ops | @@ (tsvector,tsquery) |
Des deux classes d'opérateur pour le type jsonb
,
jsonb_ops
est l'opérateur par défaut.
jsonb_path_ops
supporte moins d'opérateurs mais offre
de meilleures performances pour ces opérateurs. Voir Section 8.14.4 pour plus de détails.
L'interface GIN a un haut niveau d'abstraction. De ce fait, la personne qui code la méthode d'accès n'a besoin d'implanter que les sémantiques du type de données accédé. La couche GIN prend en charge la gestion de la concurrence, des traces et des recherches dans la structure de l'arbre.
Pour développer une méthode d'accès GIN fonctionnelle, il suffit d'implanter quelques méthodes utilisateur. Celles-ci définissent le comportement des clés dans l'arbre et les relations entre clés, valeurs d'éléments indexées et requêtes indexables. En résumé, GIN combine extensibilité, généricité, ré-utilisation du code, et une interface claire.
Voici les deux méthodes qu'une classe d'opérateur GIN doit fournir sont :
Datum *extractValue(Datum inputValue, int32 *nkeys,
bool **nullFlags)
Retourne un tableau de clés alloué par palloc en fonction d'un élément à
indexer. Le nombre de clés renvoyées doit être stocké dans
*nkeys
. Si une des clés peut être nulle, allouez
aussi par palloc un tableau de *nkeys
champs de type
bool
, stockez son adresse dans
*nullFlags
, et positionnez les drapeaux null où ils
doivent l'être. *nullFlags
peut être laissé à
NULL
(sa valeur initiale) si aucune clé n'est nulle.
La valeur retournée peut être NULL
si l'élément ne
contient aucune clé.
Datum *extractQuery(Datum query, int32 *nkeys,
StrategyNumber n, bool **pmatch, Pointer **extra_data,
bool **nullFlags, int32 *searchMode)
Renvoie un tableau de clés en fonction de la valeur à rechercher ;
c'est-à-dire que query
est la valeur du côté droit
d'un opérateur indexable dont le côté gauche est la colonne indexée.
n
est le numéro de stratégie de l'opérateur dans la
classe d'opérateur (voir Section 36.16.2). Souvent,
extractQuery
doit consulter n
pour déterminer le type de données de query
et la
méthode à utiliser pour extraire les valeurs des clés. Le nombre de
clés renvoyées doit être stocké dans *nkeys
. Si une
des clés peut être nulle, allouez aussi par palloc un tableau de
*nkeys
champs de type bool
, stockez son
adresse dans *nullFlags
, et positionnez les drapeaux
NULL
où ils doivent l'être.
*nullFlags
peut être laissé à NULL (sa valeur
initiale) si aucune clé n'est nulle. La valeur de retour peut être
NULL
si query
ne contient aucune
clé.
searchMode
est un argument de sortie qui permet à
extractQuery
de spécifier des détails sur comment
la recherche sera effectuée. Si *searchMode
est
positionné à GIN_SEARCH_MODE_DEFAULT
(qui est la
valeur à laquelle il est initialisé avant l'appel), seuls les éléments
qui correspondent à au moins une des clés retournées sont considérés
comme des candidats de correspondance. Si
*searchMode
est positionné à
GIN_SEARCH_MODE_INCLUDE_EMPTY
, alors en plus des
éléments qui contiennent au moins une clé correspondante, les éléments
qui ne contiennent aucune clé sont aussi considérées comme des
candidats de correspondance. (Ce mode est utile pour implémenter un
opérateur « est le sous-ensemble de », par exemple.) Si
*searchMode
est positionné à
GIN_SEARCH_MODE_ALL
, alors tous les éléments non
nuls de l'index sont candidats de correspondance, qu'ils aient une clé
qui corresponde à celles retournées ou non. (Ce mode est beaucoup plus
lent que les deux autres, mais il peut être nécessaire pour implanter
des cas exceptionnels correctement. Un opérateur qui a besoin de ce
mode dans la plupart des cas n'est probablement pas un bon candidat
pour une classe d'opérateur GIN.) Les symboles à utiliser pour
configurer ce mode sont définis dans
access/gin.h
.
pmatch
est un argument de sortie à utiliser quand une
correspondance partielle est permise. Pour l'utiliser,
extractQuery
doit allouer un tableau de booléens
*nkeys
et stocker son adresse dans
*pmatch
. Chaque élément du tableau devrait être
positionné à true si la clé correspondante nécessite une
correspondance partielle, et à false sinon. Si
*pmatch
est configuré à NULL
, alors
GIN suppose qu'une correspondance partielle n'est pas nécessaire. La
variable est initialisée à NULL
avant l'appel, et peut
donc être simplement ignorée par les classes d'opérateurs qui ne gèrent
pas les correspondances partielles.
extra_data
est un argument de sortie qui autorise
extractQuery
à passer des données supplémentaires
aux méthodes consistent
et
comparePartial
. Pour l'utiliser,
extractQuery
doit allouer un tableau de pointeurs
*nkeys
et stocker son adresse dans
*extra_data
, puis stocker ce qu'il souhaite dans les
pointeurs individuels. La variable est initialisée à
NULL
avant l'appel, afin que ce paramètre soit
simplement ignoré par une classe d'opérateurs qui n'a pas besoin de
données supplémentaires. Si *extra_data
est
positionné, le tableau dans son ensemble est passé à la méthode
consistent
, et l'élément approprié à la méthode
comparePartial
.
Une classe d'opérateur doit aussi fournir une fonction pour vérifier si un
élément indexé correspond à la requête. Elle vient en deux versions, une
fonction booléenne consistent
et une fonction
ternaire triConsistent
. Cette dernière couvre les
fonctionnalités des deux, donc fournir uniquement
triConsistent
est suffisant. Cependant, si la
variante booléenne est bien moins coûteuse à calculer, il peut être
avantageux de fournir les deux. Si seule la variante booléenne est
fournie, certaines optimisations dépendant de la réfutation d'éléments
d'index avant de récupérer toutes les clés sont désactivées.
bool consistent(bool check[], StrategyNumber n, Datum query,
int32 nkeys, Pointer extra_data[], bool *recheck,
Datum queryKeys[], bool nullFlags[])
Retourne true si un élément indexé répond à l'opérateur de requête
possédant le numéro de stratégie n
(ou pourrait le
satisfaire si l'indication recheck est retournée). Cette fonction n'a
pas d'accès direct aux valeurs des éléments indexés. Au lieu de cela,
ce qui est disponible, c'est la connaissance de quelles valeurs de clés
extraites de la requête apparaissent dans un élément indexé donné. Le
tableau check
a une longueur de
nkeys
, qui est identique au nombre de clés retourné
précédemment par extractQuery
pour cette donnée
query
. Chaque élément du tableau
check
est true si l'élément indexé contient la clé
de requête correspondante, c'est à dire, si (check[i] == true), la
i-ème clé du tableau résultat de extractQuery
est
présente dans l'élément indexé. La donnée query
originale est passée au cas où la méthode
consistent
aurait besoin de le consulter, de même
que les tableaux queryKeys[]
et nullFlags
[]
retournés précédemment par
extractQuery
. extra_data
est le
tableau de données supplémentaires renvoyé par
extractQuery
, ou NULL
si aucun.
Quand extractQuery
renvoie une clé nulle dans
queryKeys[]
, l'élément correspondant de
check[]
est true si l'élément indexé contient une
clé nulle ; c'est-à-dire que la sémantique de check
[]
est comme celle de IS NOT DISTINCT
FROM
. La fonction consistent
peut
examiner l'élément correspondant de nullFlags[]
si
elle a besoin de faire la différence entre une correspondance de
valeur « normale » et une correspondance nulle.
En cas de réussite, *recheck
devrait être positionné
à true si les enregistrements de la table doivent être revérifiées par
rapport à l'opérateur de la requête, ou à false si le test d'index est
exact. Autrement dit, une valeur de retour à false garantit que
l'enregistrement de la table ne correspond pas ; une valeur de
retour à true avec *recheck
à false garantit que
l'enregistrement de la table correspond à la requête ; et une
valeur de retour à true avec *recheck
à true
signifie que l'enregistrement de la table pourrait correspondre à la
requête, et qu'il doit être récupéré et re-vérifié en évaluant
l'opérateur de la requête directement sur l'élément initialement
indexé.
GinTernaryValue triConsistent(GinTernaryValue check[], StrategyNumber n, Datum query,
int32 nkeys, Pointer extra_data[],
Datum queryKeys[], bool nullFlags[])
triConsistent
est similaire à
consistent
, mais en lieu de booléens dans le
vecteur check
, il y a trois valeurs possibles pour
chaque clé : GIN_TRUE
,
GIN_FALSE
et GIN_MAYBE
.
GIN_FALSE
et GIN_TRUE
ont la même
signification que des valeurs booléennes standards alors que
GIN_MAYBE
signifie que la présence de cette clé est
inconnue. Quand des valeurs GIN_MAYBE
sont
présentes, la fonction devrait seulement renvoyer
GIN_TRUE
si l'élément correspond à coup sûr que
l'élément de l'index contient ou non les clés de la requête
correspondante. De la même façon, la fonction doit renvoyer
GIN_FALSE
seulement si l'élément ne correspond pas,
qu'il contienne ou non des clés GIN_MAYBE
. Si le
résultat dépend des entrées GIN_MAYBE
, autrement dit
si la correspondance ne peut pas être confirmée ou réfutée en se basant
sur les clés connues de la requête, la fonction doit renvoyer
GIN_MAYBE
.
Quand il n'y a pas de valeurs GIN_MAYBE
dans le
vecteur check
, la valeur de retour
GIN_MAYBE
est équivalent à configurer l'indicateur
recheck
dans la fonction booléenne
consistent
.
De plus, GIN doit avoir un moyen de trier les valeurs des clés stockées dans l'index. La classe d'opérateur peut définir l'ordre de tri en spécifiant une méthode de comparaison :
int compare(Datum a, Datum b)
Compare deux clés (pas des éléments indexés) et renvoie un entier inférieur à zéro, égal à zéro ou supérieur à zéro, indiquant si la première clé est inférieure à, égale à ou supérieure à la seconde. Les clés nulles ne sont jamais fournies en argument à cette fonction.
Sinon, si la classe d'opérateur ne fournit pas de méthode
compare
, GIN cherchera la classe d'opérateur B-Tree
par défaut pour le type de donnée de la clé d'index, et utilisera sa
fonction de comparaison. Il est recommandé de spécifier la fonction de
comparaison dans une classe d'opérateur GIN destinée à un seul type de
donnée, car rechercher la classe d'opérateur B-Tree coûte quelques cycles
CPU. Cependant, les classes d'opérateur GIN polymorphiques (telle que
array_ops
) ne peuvent typiquement pas spécifier une
seule fonction de comparaison.
Une classe d'opérateurs pour GIN peut fournir en option les méthodes suivantes :
int comparePartial(Datum partial_key, Datum key, StrategyNumber n,
Pointer extra_data)
Compare une clé d'une requête de correspondance partielle à une clé
d'index. Renvoie un entier dont le signe indique le résultat :
inférieur à zéro signifie que la clé d'index ne correspond pas à la
requête mais que le parcours d'index va continuer ; zéro signifie
que la clé d'index ne correspond pas à la requête ; supérieur à
zéro indique que le parcours d'index doit s'arrêter car il n'existe pas
d'autres correspondances. Le numéro de stratégie n
de l'opérateur qui a engendré la requête de correspondance partielle
est fourni au cas où sa sémantique serait nécessaire pour déterminer la
fin du parcours. De plus, extra_data
est l'élément
correspondant du tableau renvoyé par extractQuery
(NULL
sinon). Les clés nulles ne sont jamais passées à
cette fonction.
void options(local_relopts *relopts)
Définit un ensemble de paramètres visibles aux utilisateurs qui contrôle le comportement d'une classe d'opérateur.
La fonction options
se voit donner un pointeur vers
une structure local_relopts
qui doit être
remplie avec un ensemble d'options spécifiques à la classe d'opérateur.
Les options peuvent être accédées à partir des autres fonctions de
support en utilisant les macros PG_HAS_OPCLASS_OPTIONS
()
et PG_GET_OPCLASS_OPTIONS()
.
Étant donné que l'extraction des clés des valeurs indexées et la représentation de la clé dans GIN sont flexibles, elles peuvent dépendre de paramètres spécifiés par l'utilisateur.
Pour supporter des requêtes à « correspondance partielle », une
classe d'opérateur doit fournir la méthode
comparePartial
, et sa méthode
extractQuery
doit positionner le paramètre
pmatch
quand une requête à correspondance partielle est
rencontrée. Voir Section 64.4.4.2 pour les détails.
Le type de données réel des différentes valeurs Datum
mentionnées ci-dessus varient en fonction de la classe d'opérateurs. Les
valeurs d'élément passées à extractValue
sont
toujours du type en entrée de la classe d'opérateur, et toutes les valeurs
de clé doivent être du type STORAGE
de la classe. Le
type de l'argument query
passé aux fonctions
extractQuery
, consistent
et
triConsistent
est le type de l'argument côté droit de
l'opérateur du membre de la classe identifié par le numéro de stratégie.
Ce n'est pas nécessairement le même que l'élément indexé, tant que des
valeurs de clés d'un type correct peuvent en être extraites. Néanmoins, il
est recommandé que les déclarations SQL de ces trois fonctions de support
utilisent le type de données indexé de la classe d'opérateur pour
l'argument query
, même si le type réel pourrait être
différent suivant l'opérateur.
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 64.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 64.1. Cœur de GIN
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.
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.
L'insertion dans un index GIN peut être lente du fait de la probabilité d'insertion de nombreuses clés pour chaque élément. C'est pourquoi, pour les chargements massifs dans une table, il est conseillé de supprimer l'index GIN et de le re-créer après le chargement.
Quand fastupdate
est activé pour
GIN(voir Section 64.4.4.1 pour les
détails), la pénalité est moindre que quand il n'est pas activé. Mais
pour les très grosses mises à jour, il peut toujours être plus efficace
de détruire et recréer l'index.
Le temps de construction d'un index GIN dépend
grandement du paramètre maintenance_work_mem
;
il est contre-productif de limiter la mémoire de travail lors de la
création d'un index.
Durant une série d'insertions dans un index GIN
existant pour lequel l'option fastupdate
est activé,
le système nettoiera la liste d'entrées en attente dès qu'elle
deviendra plus grosse que la limite indiquée par
gin_pending_list_limit
. Afin d'éviter des
fluctuations mesurables de temps de réponse, il est souhaitable d'avoir
un nettoyage de la liste d'attente en arrière-plan (c'est-à-dire via
autovacuum). Les opérations de nettoyage en avant-plan peuvent être
évitées en augmentant gin_pending_list_limit
ou en
rendant le processus autovacuum plus aggressif. Toutefois, augmenter la
limite de l'opération de nettoyage implique que si un nettoyage en
avant-plan se produit, il prendra encore plus de temps.
gin_pending_list_limit
peut être surchargé sur
certains index en modifiant les paramètres de stockage, ce qui permet à
chaque index d'avoir sa propre limite de nettoyage. Par exemple, il est
possible d'augmenter la limite uniquement pour un index GIN fortement
mis à jour ou de la diminuer dans le cas contraire.
La raison principale qui a poussé le développement des index GIN a été la volonté d'ajouter les recherches plein texte dans PostgreSQL et il arrive fréquemment qu'une recherche de ce type renvoie un ensemble volumineux de résultats. Cela arrive d'autant plus fréquemment que la requête contient des mots très fréquents, auquel cas l'ensemble de résultats n'est même pas utile. Puisque la lecture des lignes sur disque et leur tri prend beaucoup de temps, cette situation est inacceptable en production. (La recherche dans l'index est, elle, très rapide.)
Pour faciliter l'exécution contrôlée de telles requêtes,
GIN dispose d'une limite supérieure souple
configurable du nombre de lignes renvoyées, le paramètre de
configuration gin_fuzzy_search_limit
. Par défaut, il
est positionné à 0 (c'est-à-dire sans limite). Si une limite différente
de 0 est choisie, alors l'ensemble renvoyé est un sous-ensemble du
résultat complet, choisi aléatoirement.
« Souple » signifie que le nombre réel de résultats renvoyés peut différer légèrement de la limite indiquée, en fonction de la requête et de la qualité du générateur de nombres aléatoires du système.
D'expérience, des valeurs de l'ordre de quelques milliers (5000 -- 20000) fonctionnent bien.
GIN part de l'hypothèse que les opérateurs indexables
sont stricts. Cela signifie que la fonction
extractValue
ne sera pas appelée du tout sur une
valeur d'élément nul (à la place, une entrée d'index factice sera créée
automatiquement), et que la fonction extractQuery
ne
sera pas appelée non plus pour une valeur de requête nulle (à la place, la
requête est considérée comme impossible à satisfaire). Notez toutefois que
des valeurs de clé nulles contenues dans un élément composite ou une
valeur de requête non nul sont supportées.
Le noyau de la distribution PostgreSQL inclut la
classe d'opérateur GIN précédemment montrée dans Tableau 64.3. Les modules
contrib
suivants contiennent aussi des classes
d'opérateurs GIN :
btree-gin
Fonctionnalité équivalente à B-Tree pour plusieurs types de données
hstore
Module pour le stockage des paires (clé, valeur)
Support amélioré pour le type int[]
pg_trgm
Similarité de texte par correspondance de trigramme