PostgreSQLLa base de données la plus sophistiquée au monde.
Documentation PostgreSQL 17.0 » Internes » Méthodes d'accès natives des index » Index GiST

64.2. Index GiST #

64.2.1. Introduction #

GiST est un acronyme de Generalized Search Tree, c'est-à-dire arbre de recherche généralisé. C'est une méthode d'accès balancée à structure de type arbre, qui agit comme un modèle de base dans lequel il est possible d'implanter des schémas d'indexage arbitraires. B-trees, R-trees et de nombreux autres schémas d'indexage peuvent être implantés en GiST.

GiST a pour avantage d'autoriser le développement de types de données personnalisés avec les méthodes d'accès appropriées, par un expert en types de données, plutôt que par un expert en bases de données.

Quelques informations disponibles ici sont dérivées du site web du projet d'indexage GiST de l'université de Californie à Berkeley et de la thèse de Marcel Kornacker, Méthodes d'accès pour les systèmes de bases de données de la prochaine génération. L'implantation GiST de PostgreSQL est principalement maintenu par Teodor Sigaev et Oleg Bartunov. Leur site web fournit de plus amples informations.

64.2.2. Classes d'opérateur internes #

La distribution de PostgreSQL inclut les classes d'opérateur GiST indiquées dans Tableau 64.1. (Quelques modules optionnels décrits dans Annexe F fournissent des classes d'opérateur GiST supplémentaires.)

Tableau 64.1. Classes d'opérateur GiST internes

NomOpérateurs indexablesOpérateurs de tri
box_ops<< (box, box)<-> (box, point)
&< (box, box)
&& (box, box)
&> (box, box)
>> (box, box)
~= (box, box)
@> (box, box)
<@ (box, box)
&<| (box, box)
<<| (box, box)
|>> (box, box)
|&> (box, box)
circle_ops<< (circle, circle)<-> (circle, point)
&< (circle, circle)
&> (circle, circle)
>> (circle, circle)
<@ (circle, circle)
@> (circle, circle)
~= (circle, circle)
&& (circle, circle)
|>> (circle, circle)
<<| (circle, circle)
&<| (circle, circle)
|&> (circle, circle)
inet_ops<< (inet, inet) 
<<= (inet, inet)
>> (inet, inet)
>>= (inet, inet)
= (inet, inet)
<> (inet, inet)
< (inet, inet)
<= (inet, inet)
> (inet, inet)
>= (inet, inet)
&& (inet, inet)
multirange_ops= (anymultirange, anymultirange) 
&& (anymultirange, anymultirange)
&& (anymultirange, anyrange)
@> (anymultirange, anyelement)
@> (anymultirange, anymultirange)
@> (anymultirange, anyrange)
<@ (anymultirange, anymultirange)
<@ (anymultirange, anyrange)
<< (anymultirange, anymultirange)
<< (anymultirange, anyrange)
>> (anymultirange, anymultirange)
>> (anymultirange, anyrange)
&< (anymultirange, anymultirange)
&< (anymultirange, anyrange)
&> (anymultirange, anymultirange)
&> (anymultirange, anyrange)
-|- (anymultirange, anymultirange)
-|- (anymultirange, anyrange)
point_ops|>> (point, point)<-> (point, point)
<< (point, point)
>> (point, point)
<<| (point, point)
~= (point, point)
<@ (point, box)
<@ (point, polygon)
<@ (point, circle)
poly_ops<< (polygon, polygon)<-> (polygon, point)
&< (polygon, polygon)
&> (polygon, polygon)
>> (polygon, polygon)
<@ (polygon, polygon)
@> (polygon, polygon)
~= (polygon, polygon)
&& (polygon, polygon)
<<| (polygon, polygon)
&<| (polygon, polygon)
|&> (polygon, polygon)
|>> (polygon, polygon)
range_ops= (anyrange, anyrange) 
&& (anyrange, anyrange)
&& (anyrange, anymultirange)
@> (anyrange, anyelement)
@> (anyrange, anyrange)
@> (anyrange, anymultirange)
<@ (anyrange, anyrange)
<@ (anyrange, anymultirange)
<< (anyrange, anyrange)
<< (anyrange, anymultirange)
>> (anyrange, anyrange)
>> (anyrange, anymultirange)
&< (anyrange, anyrange)
&< (anyrange, anymultirange)
&> (anyrange, anyrange)
&> (anyrange, anymultirange)
-|- (anyrange, anyrange)
-|- (anyrange, anymultirange)
tsquery_ops<@ (tsquery, tsquery) 
@> (tsquery, tsquery)
tsvector_ops@@ (tsvector, tsquery) 

Pour des raisons historiques, la classe d'opérateur inet_ops n'est pas la classe par défaut pour les types inet et cidr. Pour l'utiliser, mentionnez le nom de la classe dans la commande CREATE INDEX, par exemple

CREATE INDEX ON ma_table USING GIST (ma_colonne_inet inet_ops);
   

64.2.3. Extensibilité #

L'implantation d'une nouvelle méthode d'accès à un index a toujours été un travail complexe. Il est, en effet, nécessaire de comprendre le fonctionnement interne de la base de données, tel que le gestionnaire de verrous ou le WAL.

L'interface GiST dispose d'un haut niveau d'abstraction, ce qui autorise le codeur de la méthode d'accès à ne coder que la sémantique du type de données accédé. La couche GiST se charge elle-même de la gestion des accès concurrents, des traces et de la recherche dans la structure en arbre.

Cette extensibilité n'est pas comparable à celle des autres arbres de recherche standard en termes de données gérées. Par exemple, PostgreSQL supporte les B-trees et les index de hachage extensibles. Cela signifie qu'il est possible d'utiliser PostgreSQL pour construire un B-tree ou un hachage sur tout type de données. Mais, les B-trees ne supportent que les prédicats d'échelle (<, =, >), les index de hachage que les requêtes d'égalité.

Donc, lors de l'indexation d'une collection d'images, par exemple, avec un B-tree PostgreSQL, seules peuvent être lancées des requêtes de type « est-ce que imagex est égale à imagey », « est-ce que imagex est plus petite que imagey » et « est-ce que imagex est plus grande que imagey ». En fonction de la définition donnée à « égale à », « inférieure à » ou « supérieure à », cela peut avoir une utilité. Néanmoins, l'utilisation d'un index basé sur GiST permet de créer de nombreuses possibilités de poser des questions spécifiques au domaine, telles que « trouver toutes les images de chevaux » ou « trouver toutes les images sur-exposées ».

Pour obtenir une méthode d'accès GiST fonctionnelle, il suffit de coder plusieurs méthodes utilisateur définissant le comportement des clés dans l'arbre. Ces méthodes doivent être suffisamment élaborées pour supporter des requêtes avancées, mais pour toutes les requêtes standard (B-trees, R-trees, etc.) elles sont relativement simples. En bref, GiST combine extensibilité, généralité, ré-utilisation de code et interface claire.

Une classe d'opérateur d'index GiST doit fournir cinq méthodes, et six supplémentaires optionnelles. La précision de l'index est assurée par l'implantation des méthodes same, consistent et union alors que l'efficacité (taille et rapidité) de l'index dépendra des méthodes penalty et picksplit. Deux fonctions optionnelles sont compress et decompress, qui permettent à un index d'avoir des données internes de l'arbre d'un type différent de ceux des données qu'il indexe. Les feuilles doivent être du type des données indexées alors que les autres nœuds peuvent être de n'importe quelle structure C (mais vous devez toujours suivre les règles des types de données de PostgreSQL dans ce cas, voir ce qui concerne varlena pour les données de taille variable). Si le type de données interne de l'arbre existe au niveau SQL, l'option STORAGE de la commande CREATE OPERATOR CLASS peut être utilisée. La huitième méthode, optionnelle, est distance, qui est nécessaire si la classe d'opérateur souhaite supporter les parcours ordonnées (intéressant dans le cadre des recherches du voisin-le-plus-proche, nearest-neighbor). La neuvième méthode, optionnelle, nommée fetch, est nécessaire si la classe d'opérateur souhaite supporter les parcours d'index seuls, sauf quand la méthode compress est omise. La dixième méthode, optionnelle, est options et est nécessaire si l'opérateur de classe a des paramètres définis par l'utilisateur. La onzième méthode, sortsupport, est aussi optionnelle et est utilisée pour accélérer la construction d'un index GiST.

consistent

Étant donné une entrée d'index p et une valeur de requête q, cette fonction détermine si l'entrée de l'index est cohérente (« consistent » en anglais) avec la requête ; c'est-à-dire, est-ce que le prédicat « colonne_indexée opérateur_indexable q » soit vrai pour toute ligne représentée par l'entrée de l'index ? Pour une entrée de l'index de type feuille, c'est l'équivalent pour tester la condition indexable, alors que pour un nœud interne de l'arbre, ceci détermine s'il est nécessaire de parcourir le sous-arbre de l'index représenté par le nœud. Quand le résultat est true, un drapeau recheck doit aussi être renvoyé. Ceci indique si le prédicat est vrai à coup sûr ou seulement peut-être vrai. Si recheck = false, alors l'index a testé exactement la condition du prédicat, alors que si recheck = true, la ligne est seulement un correspondance de candidat. Dans ce cas, le système évaluera automatiquement l'opérateur_indexable avec la valeur actuelle de la ligne pour voir s'il s'agit réellement d'une correspondance. Cette convention permet à GiST de supporter à la fois les structures sans pertes et celles avec perte de l'index.

La déclaration SQL de la fonction doit ressembler à ceci :

CREATE OR REPLACE FUNCTION my_consistent(internal, data_type, smallint, oid, internal)
RETURNS bool
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;
      

Et le code correspondant dans le module C peut alors suivre ce squelette :

PG_FUNCTION_INFO_V1(my_consistent);

Datum
my_consistent(PG_FUNCTION_ARGS)
{
    GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
    data_type  *query = PG_GETARG_DATA_TYPE_P(1);
    StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
    /* Oid subtype = PG_GETARG_OID(3); */
    bool       *recheck = (bool *) PG_GETARG_POINTER(4);
    data_type  *key = DatumGetDataType(entry->key);
    bool        retval;

    /*
     * determine return value as a function of strategy, key and query.
     *
     * Use GIST_LEAF(entry) to know where you're called in the index tree,
     * which comes handy when supporting the = operator for example (you could
     * check for non empty union() in non-leaf nodes and equality in leaf
     * nodes).
     */

    *recheck = true;        /* or false if check is exact */

    PG_RETURN_BOOL(retval);
}
      

Ici, key est un élément dans l'index et query la valeur la recherchée dans l'index. Le paramètre StrategyNumber indique l'opérateur appliqué de votre classe d'opérateur. Il correspond à un des nombres d'opérateurs dans la commande CREATE OPERATOR CLASS.

Suivant les opérateurs inclus dans la classe, le type de données de query pourrait varier avec l'opérateur car il sera du type de ce qui se trouver sur le côté droit de l'opérateur, qui pourrait être différent du type de la donnée indexée apparaissant du côté gauche. (Le squelette de code ci-dessus suppose qu'un seul type est possible ; dans le cas contraire, récupérer la valeur de l'argument query pourrait devoir dépendre de l'opérateur.) Il est recommendé que la déclaration SQL de la fonction consistent utilise le type de la donnée indexée 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.

union

Cette méthode consolide l'information dans l'arbre. Suivant un ensemble d'entrées, cette fonction génère une nouvelle entrée d'index qui représente toutes les entrées données.

La déclaration SQL de la fonction doit ressembler à ceci :

CREATE OR REPLACE FUNCTION my_union(internal, internal)
RETURNS storage_type
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;
      

Et le code correspondant dans le module C peut alors suivre ce squelette :

PG_FUNCTION_INFO_V1(my_union);

Datum
my_union(PG_FUNCTION_ARGS)
{
    GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
    GISTENTRY  *ent = entryvec->vector;
    data_type  *out,
               *tmp,
               *old;
    int         numranges,
                i = 0;

    numranges = entryvec->n;
    tmp = DatumGetDataType(ent[0].key);
    out = tmp;

    if (numranges == 1)
    {
        out = data_type_deep_copy(tmp);

        PG_RETURN_DATA_TYPE_P(out);
    }

    for (i = 1; i < numranges; i++)
    {
        old = out;
        tmp = DatumGetDataType(ent[i].key);
        out = my_union_implementation(out, tmp);
    }

    PG_RETURN_DATA_TYPE_P(out);
}
      

Comme vous pouvez le voir dans ce squelette, nous gérons un type de données où union(X, Y, Z) = union(union(X, Y), Z). C'est assez simple pour supporter les types de données où ce n'est pas le cas, en implantant un autre algorithme d'union dans cette méthode de support GiST.

Le résultat de la fonction union doit être une valeur du type de stockage de l'index, quelqu'il soit (il pourrait être ou non différent du type de la colonne indexée). La fonction union doit renvoyer un pointeur vers la mémoire nouvellement allouée avec palloc(). Vous ne pouvez pas seulement renvoyer la valeur en entrée directement, même s'il n'y a pas de changement de type.

Comme indiqué ci-dessus, le premier argument internal de la fonction union est en réalité un pointeur GistEntryVector. Le deuxième argument est un pointeur vers une variable entière qui peut être ignorée. (Il était requis que la fonction union enregistre la taille de sa valeur résultat dans cette variable, mais ce n'est plus nécessaire.)

compress

Convertit l'élément de données dans un format compatible avec le stockage physique dans une page d'index. Si la méthode compress est omise, les éléments des données sont enregistrés dans l'index sans modification.

La déclaration SQL de la fonction doit ressembler à ceci :

CREATE OR REPLACE FUNCTION my_compress(internal)
RETURNS internal
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;
      

Et le code correspondant dans le module C peut alors suivre ce squelette :

PG_FUNCTION_INFO_V1(my_compress);

Datum
my_compress(PG_FUNCTION_ARGS)
{
    GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
    GISTENTRY  *retval;

    if (entry->leafkey)
    {
        /* replace entry->key with a compressed version */
        compressed_data_type *compressed_data = palloc(sizeof(compressed_data_type));

        /* fill *compressed_data from entry->key ... */

        retval = palloc(sizeof(GISTENTRY));
        gistentryinit(*retval, PointerGetDatum(compressed_data),
                      entry->rel, entry->page, entry->offset, FALSE);
    }
    else
    {
        /* typically we needn't do anything with non-leaf entries */
        retval = entry;
    }

    PG_RETURN_POINTER(retval);
}
      

Vous devez adapter compressed_data_type au type spécifique que vous essayez d'obtenir pour compresser les nœuds finaux.

decompress

Convertit la représentation enregistrée d'un élément des données dans un format manipulable par les autres méthodes GiST dans la classe d'opérateur. Si la méthode decompress est omise, il est supposé que les autres méthodes GiST peuvent fonctionner directement dans le format de la donnée. (decompress n'est pas nécessairement l'inverse de la méthode compress ; en particulier, si compress est à perte, alors il est impossible pour decompress de reconstruire exactement la donnée originale. decompress n'est pas nécessairement équivalent à fetch, car les autres méthodes GiST pourraient ne pas nécessiter la reconstruction complète des données.)

La déclaration SQL de la fonction doit ressembler à ceci :

CREATE OR REPLACE FUNCTION my_decompress(internal)
RETURNS internal
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;
      

Et le code correspondant dans le module C peut alors suivre ce squelette :

PG_FUNCTION_INFO_V1(my_decompress);

Datum
my_decompress(PG_FUNCTION_ARGS)
{
    PG_RETURN_POINTER(PG_GETARG_POINTER(0));
}
      

Le squelette ci-dessus est convenable dans le cas iù aucune décompression n'est nécessaire. (Mais, bien sûr, omettre la méthode est encore plus simple et même recommendé dans ce cas.)

penalty

Renvoie une valeur indiquant le « coût » d'insertion d'une nouvelle entrée dans une branche particulière de l'arbre. Les éléments seront insérés dans l'ordre des pénalités moindres (penalty) de l'arbre. Les valeurs renvoyées par penalty doivent être positives ou nulles. Si une valeur négative est renvoyée, elle sera traitée comme valant zéro.

La déclaration SQL de la fonction doit ressembler à ceci :

CREATE OR REPLACE FUNCTION my_penalty(internal, internal, internal)
RETURNS internal
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;  -- in some cases penalty functions need not be strict
      

Et le code correspondant dans le module C peut alors suivre ce squelette :

PG_FUNCTION_INFO_V1(my_penalty);

Datum
my_penalty(PG_FUNCTION_ARGS)
{
    GISTENTRY  *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
    GISTENTRY  *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
    float      *penalty = (float *) PG_GETARG_POINTER(2);
    data_type  *orig = DatumGetDataType(origentry->key);
    data_type  *new = DatumGetDataType(newentry->key);

    *penalty = my_penalty_implementation(orig, new);
    PG_RETURN_POINTER(penalty);
}
      

Pour des raisons historiques, la fonction penalty ne renvoie pas seulement un résultat de type float ; à la place, il enregistre la valeur à l'emplacement indiqué par le troisième argument. La valeur de retour est ignorée, bien que, par convention, l'adresse de l'argument est renvoyée.

La fonction penalty est crucial pour de bonnes performances de l'index. Elle sera utilisée lors de l'insertion pour déterminer la branche à suivre pour savoir où ajouter la nouvelle entrée dans l'arbre. Lors de l'exécution de la requête, plus l'arbre sera bien balancé, plus l'exécution sera rapide.

picksplit

Quand une division de page est nécessaire pour un index, cette fonction décide des entrées de la page qui resteront sur l'ancienne page et de celles qui seront déplacées sur la nouvelle page.

La déclaration SQL de la fonction doit ressembler à ceci :

CREATE OR REPLACE FUNCTION my_picksplit(internal, internal)
RETURNS internal
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;
      

Et le code correspondant dans le module C peut alors suivre ce squelette :

PG_FUNCTION_INFO_V1(my_picksplit);

Datum
my_picksplit(PG_FUNCTION_ARGS)
{
    GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
    GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
    OffsetNumber maxoff = entryvec->n - 1;
    GISTENTRY  *ent = entryvec->vector;
    GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
    int         i,
                nbytes;
    OffsetNumber *left,
               *right;
    data_type  *tmp_union;
    data_type  *unionL;
    data_type  *unionR;
    GISTENTRY **raw_entryvec;

    maxoff = entryvec->n - 1;
    nbytes = (maxoff + 1) * sizeof(OffsetNumber);

    v->spl_left = (OffsetNumber *) palloc(nbytes);
    left = v->spl_left;
    v->spl_nleft = 0;

    v->spl_right = (OffsetNumber *) palloc(nbytes);
    right = v->spl_right;
    v->spl_nright = 0;

    unionL = NULL;
    unionR = NULL;

    /* Initialize the raw entry vector. */
    raw_entryvec = (GISTENTRY **) malloc(entryvec->n * sizeof(void *));
    for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
        raw_entryvec[i] = &(entryvec->vector[i]);

    for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
    {
        int         real_index = raw_entryvec[i] - entryvec->vector;

        tmp_union = DatumGetDataType(entryvec->vector[real_index].key);
        Assert(tmp_union != NULL);

        /*
         * Choose where to put the index entries and update unionL and unionR
         * accordingly. Append the entries to either v->spl_left or
         * v->spl_right, and care about the counters.
         */

        if (my_choice_is_left(unionL, curl, unionR, curr))
        {
            if (unionL == NULL)
                unionL = tmp_union;
            else
                unionL = my_union_implementation(unionL, tmp_union);

            *left = real_index;
            ++left;
            ++(v->spl_nleft);
        }
        else
        {
            /*
             * Same on the right
             */
        }
    }

    v->spl_ldatum = DataTypeGetDatum(unionL);
    v->spl_rdatum = DataTypeGetDatum(unionR);
    PG_RETURN_POINTER(v);
}
      

Notez que le résultat de la fonction picksplit est fourni en modifiant la structure v en référence. La valeur de retour réelle est ignorée, bien que la convention est de passer l'adresse de v.

Comme penalty, la fonction picksplit est cruciale pour de bonnes performances de l'index. Concevoir des implantations convenables des fonctions penalty et picksplit est le challenge d'un index GiST performant.

same

Renvoit true si les deux entrées de l'index sont identiques, faux sinon. (Un « enregistrement d'index » est une valeur du type de stockage de l'index, pas nécessairement le type original de la colonne indexée.)

La déclaration SQL de la fonction ressemble à ceci :

CREATE OR REPLACE FUNCTION my_same(storage_type, storage_type, internal)
RETURNS internal
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;
      

Et le code correspondant dans le module C peut alors suivre ce squelette :

PG_FUNCTION_INFO_V1(my_same);

Datum
my_same(PG_FUNCTION_ARGS)
{
    prefix_range *v1 = PG_GETARG_PREFIX_RANGE_P(0);
    prefix_range *v2 = PG_GETARG_PREFIX_RANGE_P(1);
    bool       *result = (bool *) PG_GETARG_POINTER(2);

    *result = my_eq(v1, v2);
    PG_RETURN_POINTER(result);
}
      

Pour des raisons historiques, la fonction same ne renvoie pas seulement un résultat booléen ; à la place, il doit enregistrer le drapeau à l'emplacement indiqué par le troisième argument. La valeur de retour est ignoré, bien qu'il soit par convention de passer l'adresse de cet argument.

distance

À partir d'une entrée d'index p et une valeur recherchée q, cette fonction détermine la « distance » entre l'entrée de l'index et la valeur recherchée. Cette fonction doit être fournie si la classe d'opérateur contient des opérateurs de tri. Une requête utilisant l'opérateur de tri sera implémentée en renvoyant les entrées d'index dont les valeurs de « distance » sont les plus petites, donc les résultats doivent être cohérents avec la sémantique de l'opérateur. Pour une entrée d'index de type feuille, le résultat représente seulement la distance vers l'entrée d'index. Pour un nœud de l'arbre interne, le résultat doit être la plus petite distance que toute entrée enfant représente.

La déclaration SQL de la fonction doit ressembler à ceci :

CREATE OR REPLACE FUNCTION my_distance(internal, data_type, smallint, oid, internal)
RETURNS float8
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;
      

Et le code correspondant dans le module C peut correspondre à ce squelette :

PG_FUNCTION_INFO_V1(my_distance);

Datum
my_distance(PG_FUNCTION_ARGS)
{
    GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
    data_type  *query = PG_GETARG_DATA_TYPE_P(1);
    StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
    /* Oid subtype = PG_GETARG_OID(3); */
    /* bool *recheck = (bool *) PG_GETARG_POINTER(4); */
    data_type  *key = DatumGetDataType(entry->key);
    double      retval;

    /*
     * determine return value as a function of strategy, key and query.
     */

    PG_RETURN_FLOAT8(retval);
}
      

Les arguments de la fonction distance sont identiques aux arguments de la fonction consistent.

Quelques approximations sont autorisées pour déterminer la distance, pour que le résultat ne soit jamais plus grand que la distance réelle de l'entrée. De ce fait, par exemple, une distance dans une bounding box est généralement suffisante dans les applications géométriques. Pour un nœud d'un arbre interne, la distance renvoyée ne doit pas être plus grande que la distance vers tous les nœuds cibles. Si la distance renvoyée n'est pas exacte, la fonction doit configurer *recheck à true. (Ceci n'est pas nécessaire pour les nœuds de l'arbre interne ; en ce qui les concerne, le calcul est supposé toujours inexact.) Dans ce cas, l'exécuteur calculera la distance précise après la récupération de la ligne à partir de la pile, et réordonnera les lignes si nécessaires.

Si la fonction distance renvoie *recheck = true pour tout nœud feuille, le type de retour de l'opération de tri original doit être float8 ou float4, et les valeurs résultats de la fonction distance doivent être comparables à ceux de l'opérateur original de tri, car l'exécuteur triera en utilisant les résultats de la fonction de distance et les résultats recalculés de l'opérateur de tri. Dans le cas contraire, les valeurs de résultats de la fonction distance peuvent être toute valeur float8 finie, tant est que l'ordre relatif des valeurs résultats correspond à l'ordre renvoyé par l'opérateur de tri. (l'infinité, positif comme négatif, est utilisé en interne pour gérer des cas comme les valeurs NULL, donc il n'est pas recommandé que les fonctions distance renvoient ces valeurs.)

fetch

Convertit la représentation compressée de l'index pour un élément de données vers le type de données original pour les parcours d'index seuls. Les données renvoyées doivent être une copie exacte, sans perte de la valeur indexée à l'origine.

La déclaration SQL de la fonction doit ressembler à ceci :

CREATE OR REPLACE FUNCTION my_fetch(internal)
RETURNS internal
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;
      

L'argument est un pointeur vers une structure GISTENTRY. En entrée, son champ key contient une donnée non NULL compressée. La valeur de retour est une autre structure GISTENTRY dont le champ key contient la même donnée que l'original, mais non compressée. Si la fonction de compression de la classe d'opérateur ne fait rien pour les enregistrements feuilles, la méthode fetch peut renvoyer l'argument tel quel. Ou, si la classe d'opérateur n'a pas de fonction de compression, la méthode fetch peut aussi être omise car elle ne ferait rien de toute façon.

Le code correspondant dans le module C doit alors suivre ce squelette :

PG_FUNCTION_INFO_V1(my_fetch);

Datum
my_fetch(PG_FUNCTION_ARGS)
{
    GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
    input_data_type *in = DatumGetPointer(entry->key);
    fetched_data_type *fetched_data;
    GISTENTRY  *retval;

    retval = palloc(sizeof(GISTENTRY));
    fetched_data = palloc(sizeof(fetched_data_type));

    /*
     * Convertit 'fetched_data' en un Datum du type de données original.
     */

    /* remplit *retval à partir de fetched_data. */
    gistentryinit(*retval, PointerGetDatum(converted_datum),
                  entry->rel, entry->page, entry->offset, FALSE);

    PG_RETURN_POINTER(retval);
}
      

Si la méthode de compression est à perte pour les entrées feuilles, la classe d'opérateur ne supporte pas les parcours d'index seuls, et ne doit pas définir une fonction fetch.

options

Permet la définition des paramètres visibles par l'utilisateur et contrôlant le comportement des classes d'opérateur.

La déclaration SQL de la fonction doit ressembler à ça :

CREATE OR REPLACE FUNCTION my_options(internal)
RETURNS void
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;
      

La fonction est passée sous forme de pointeur à une structure local_relopts, qui doit être nécessairement alimentée avec un ensemble d'options spécifiques de classe d'opérateur. Les options peuvent être accédées par d'autres fonctions support en utilisant les macros PG_HAS_OPCLASS_OPTIONS() et PG_GET_OPCLASS_OPTIONS().

Un exemple d'implémentation de my_options() et de l'utilisation des paramètres depuis une autre fonction support est donné ci-dessous :

typedef enum MyEnumType
{
    MY_ENUM_ON,
    MY_ENUM_OFF,
    MY_ENUM_AUTO
} MyEnumType;

typedef struct
{
    int32   vl_len_;    /* varlena header (do not touch directly!) */
    int     int_param;  /* integer parameter */
    double  real_param; /* real parameter */
    MyEnumType enum_param; /* enum parameter */
    int     str_param;  /* string parameter */
} MyOptionsStruct;

/* String representation of enum values */
static relopt_enum_elt_def myEnumValues[] =
{
    {"on", MY_ENUM_ON},
    {"off", MY_ENUM_OFF},
    {"auto", MY_ENUM_AUTO},
    {(const char *) NULL}   /* list terminator */
};

static char *str_param_default = "default";

/*
 * Sample validator: checks that string is not longer than 8 bytes.
 */
static void
validate_my_string_relopt(const char *value)
{
    if (strlen(value) > 8)
        ereport(ERROR,
                (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
                 errmsg("str_param must be at most 8 bytes")));
}

/*
 * Sample filler: switches characters to lower case.
 */
static Size
fill_my_string_relopt(const char *value, void *ptr)
{
    char   *tmp = str_tolower(value, strlen(value), DEFAULT_COLLATION_OID);
    int     len = strlen(tmp);

    if (ptr)
        strcpy((char *) ptr, tmp);

    pfree(tmp);
    return len + 1;
}

PG_FUNCTION_INFO_V1(my_options);

Datum
my_options(PG_FUNCTION_ARGS)
{
    local_relopts *relopts = (local_relopts *) PG_GETARG_POINTER(0);

    init_local_reloptions(relopts, sizeof(MyOptionsStruct));
    add_local_int_reloption(relopts, "int_param", "integer parameter",
                            100, 0, 1000000,
                            offsetof(MyOptionsStruct, int_param));
    add_local_real_reloption(relopts, "real_param", "real parameter",
                             1.0, 0.0, 1000000.0,
                             offsetof(MyOptionsStruct, real_param));
    add_local_enum_reloption(relopts, "enum_param", "enum parameter",
                             myEnumValues, MY_ENUM_ON,
                             "Valid values are: \"on\", \"off\" et \"auto\".",
                             offsetof(MyOptionsStruct, enum_param));
    add_local_string_reloption(relopts, "str_param", "string parameter",
                               str_param_default,
                               &validate_my_string_relopt,
                               &fill_my_string_relopt,
                               offsetof(MyOptionsStruct, str_param));

    PG_RETURN_VOID();
}

PG_FUNCTION_INFO_V1(my_compress);

Datum
my_compress(PG_FUNCTION_ARGS)
{
    int     int_param = 100;
    double  real_param = 1.0;
    MyEnumType enum_param = MY_ENUM_ON;
    char   *str_param = str_param_default;

    /*
     * Normally, when opclass contains 'options' method, then options are always
     * passed to support functions.  However, if you add 'options' method to
     * existing opclass, previously defined indexes have no options, so the
     * check is required.
     */
    if (PG_HAS_OPCLASS_OPTIONS())
    {
        MyOptionsStruct *options = (MyOptionsStruct *) PG_GET_OPCLASS_OPTIONS();

        int_param = options->int_param;
        real_param = options->real_param;
        enum_param = options->enum_param;
        str_param = GET_STRING_RELOPTION(options, str_param);
    }

    /* the rest implementation of support function */
}

      

Comme la représentation de la clé dans GiST est flexible, elle peut dépendre des paramètres définis par l'utilisateur. Voir gtsvector_options() pour exemple.

sortsupport

Renvoie une fonction de comparaison pour trier lesdonnées d'une façon qui préserve l'emplacement. Elle est utilisée par les commandes CREATE INDEX et REINDEX. La qualité de l'index créé dépend decomment l'ordre de tri déterminé par la fonction de comparaison préserve l'emplacement des entrées.

La méthode sortsupport est optionnelle. Si elle n'est pas fournie, CREATE INDEX construit l'index en insérant chaque ligne dans l'arbre en utilisant les fonctions penalty et picksplit, qui sont plus lentes.

La déclaration SQL de la fonction doit ressembler à ceci :

CREATE OR REPLACE FUNCTION my_sortsupport(internal)
RETURNS void
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;

L'argument est un pointeur vers une structure SortSupport. Au minimum, la fonction doit remplir son champ de comparaison. La fonction prends trois arguments : deux Datums à comparer, et un pointeur vers la structure SortSupport. Les Datums sont les deux valeurs indexées dans le format où elles sont stockées dans l'index ; c'est-à-dire dans le format renvoyé par la méthode compress. L'API complète est définie dans src/include/utils/sortsupport.h.

Le code correspondant dans un module C pourrait suivre ce squelette :

PG_FUNCTION_INFO_V1(my_sortsupport);

static int
my_fastcmp(Datum x, Datum y, SortSupport ssup)
{
  /* établir l'ordre entre x et y en calculant une valeur de tri z */

  int z1 = ComputeSpatialCode(x);
  int z2 = ComputeSpatialCode(y);

  return z1 == z2 ? 0 : z1 > z2 ? 1 : -1;
}

Datum
my_sortsupport(PG_FUNCTION_ARGS)
{
  SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);

  ssup->comparator = my_fastcmp;
  PG_RETURN_VOID();
}

Toutes les méthodes de support GiST sont habituellement appelées dans des contextes mémoires à durée limitée. En fait, CurrentMemoryContext sera réinitialisé après le traitement de chaque ligne. Il n'est donc pas très important de s'inquiéter de libérer avec pfree tout ce que vous avez alloué avec palloc. Néanmoins, dans certains cas, une méthode de support peut avoir besoin de cacher des données à utiliser lors des prochains appels. Pour cela, allouez les données à durée de vie longue dans fcinfo->flinfo->fn_mcxt et conservez un pointeur vers ces données dans fcinfo->flinfo->fn_extra. Ce type de données va survivre pendant toute la durée de l'opération sur l'index (par exemple, un seul parcours d'index GiST, une construction d'index ou l'insertion d'une ligne dans un index). Faites attention à libérer avec pfree la valeur précédente lors du remplacement d'une valeur fn_extra. Dans le cas contraire, une perte mémoire s'accumulera pendant la durée de l'opération.

64.2.4. Implémentation #

64.2.4.1. Méthodes de construction d'index GiST #

La façon la plus simple de construire un index GiST est justement d'insérer toutes les entrées, une par une. Ceci tend à être lent pour les index volumineux parce que, si les entrées d'index sont réparties partout dans l'index et que l'index est suffisamment gros pour ne pas tenir en cache, un grand nombre d'accès disque aléatoires seront nécessaires. PostgreSQL accepte deux méthodes alternatives pour une construction initiale d'un indexGiST : le mode sorted (trié) et le mode buffered (tampon).

La méthode par tri est seulement disponible si chacune des classes d'opérateur utilisée par l'index fournit une fonction sortsupport, comme décrit dans Section 64.2.3. Si c'est le cas, cette méthode est généralement la meilleure, donc elle est utilisée par défaut.

La méthode par cache fonctionne en n'insérant pas les lignes directement et immédiatement dans l'index. Il peut réduire fortement la quantité d'accès disques aléatoires nécessaire pour les ensembles de données non triés. Pour les ensembles de données bien triés, le bénéfice est plus petit, voire inexistant car seul un petit nombre de blocs reçoit de nouvelles lignes à un instant t, et ces blocs tiennent en cache même si l'index complet ne le peut pas.

La méthode par cache a besoin d'appeler la fonction penalty plus souvent que ne le fait la méthode simple, ce qui consomme des ressources CPU supplémentaires. De plus, le cache a besoin d'un espace disque supplémentaire allant jusqu'à la taille de l'index résultant. L'utilisation de tampons peut aussi influencer la qualité de l'index résultant, de façon positive et négative. Cette influence dépend de plusieurs facteurs, comme la distribution des données en entrée et de l'implémentation de la classe d'opérateur.

Si le tri n'est pas possible, alors par défaut la construction d'un index GiST bascule sur la méthode par cache quand la taille de l'index atteint effective_cache_size. L'utilisation du cache peut être forcée ou empêchée manuellement avec le paramètre buffering de la commande CREATE INDEX. Le comportement par défaut est bon dans la plupart des cas mais désactiver le cache pourrait accélérer un peu la construction si les données en entrée sont triées.

64.2.5. Exemples #

La distribution source de PostgreSQL inclut plusieurs exemples de méthodes d'indexation implantées selon GiST. Le système principal fournit des fonctionnalités de recherche plein texte (indexation des tsvector et tsquery) ainsi que des fonctionnalités équivalentes aux R-Tree pour certains types de données géométriques (voir src/backend/access/gist/gistproc.c). Les modules contrib suivants contiennent aussi des classes d'opérateur GiST :

btree_gist

Fonctionnalités équivalentes aux B-Tree pour plusieurs types de données

cube

Indexation de cubes multi-dimensionnels

hstore

Module pour le stockage des paires (clé, valeur)

intarray

RD-Tree pour tableaux uni-dimensionnels de valeurs int4

ltree

Indexation des structures de type arbre

pg_trgm

Similarité textuelle par correspondance de trigrammes

seg

Indexation pour les « nombres flottants »