Documentation PostgreSQL 14.22 » Internes » Index SP-GiST » Extensibilité

Précédent | Niveau supérieur | Suivant
66.2. Classes d'opérateur internes | Sommaire | 66.4. Implémentation

## 66.3. Extensibilité

SP-GiST offre une interface avec un haut niveau d'abstraction, imposant au développeur des méthodes d'accès de n'implémenter que des méthodes spécifiques à un type de donnée spécifié. Le cœur de SP-GiST est responsable de l'efficacité du stockage sur le disque et de la recherche dans la structure arborescente. Il s'occupe aussi de la concurrence d'accès et des journaux.

Les lignes des feuilles d'un arbre SP-GiST contiennent habituellement des valeurs du même type de données que la colonne indexée, bien qu'il soit possible qu'ils contiennent des représentations à perte de la colonne indexée. Les enregistrements des feuilles stockés à la racine représenteront directement la valeur originale de la donnée indexée, mais les enregistrements des feuilles à des niveaux plus bas pourraient ne contenir qu'une valeur partielle, telle qu'un suffixe. Dans ce cas, les classes d'opérateurs des fonctions supportées devront être capables de reconstruire la valeur originale en utilisant les informations accumulées dans les lignes intermédiaires au travers du parcours de l'arbre et vers le niveau le plus bas.

Quand un index SP-GiST est créé avec des colonnes `INCLUDE`, les valeurs de ces colonnes sont aussi stockées dans des enregistrements feuilles. Les colonnes `INCLUDE` ne concernent pas la classe d'opérateurs SP-GiST, donc elles ne seront pas discutées avec plus de détails ici.

Les lignes internes sont plus complexes car elles relient des points dans l'arbre de recherche. Chaque ligne intermédiaire contient un ensemble d'au moins un nœud, qui représente des groupes de valeurs similaires de feuilles. Un nœud contient un lien qui mène vers un autre nœud de niveau inférieur, ou une petite liste de lignes de feuilles qui appartiennent toutes à la même page d'index. Chaque nœud a un label qui le décrit. Par exemple, dans un arbre radix, le label du nœud peut être le caractère suivant de la chaîne de caractère. (Sinon, une classe d'opérateurs peut omettre les labels des nœuds si elle fonctionne avec un ensemble fixe de nœuds pour les enregistrements internes ; voir Section 66.4.2.) En option, une ligne intermédiaire peut avoir une valeur de préfixe qui décrit tous ses membres. Dans un arbre radix, cela peut être le préfixe commun des chaînes représentant les données. La valeur du préfixe n'est pas nécessairement réellement un préfixe, mais peut être toute donnée utilisée par la classe d'opérateurs. Par exemple, pour un quadtree, il peut stocker le barycentre des quatre points représenté par chaque feuille. Une ligne intermédiaire d'un quadtree contiendra aussi quatre nœuds correspondants à des points autour de ce point central.

Quelques algorithmes de recherche arborescente nécessite la connaissance du niveau (ou profondeur) de la ligne en cours, et ainsi le cœur de SP-GiST fournit aux classes d'opérateurs la possibilité de gérer le décompte des niveaux lors du parcours de l'arbre. Il fournit aussi le moyen de reconstruire de façon incrémentale la valeur représentée lorsque cela est nécessaire, et pour passer des données supplémentaires (appelées valeurs traverses) lors de la descente de l'arbre.

### Note

Le code du cœur de SP-GiST tient aussi compte des valeurs NULL. Bien que les index SP-GiST stockent des entrées pour les valeurs NULL dans les colonnes indexées, cette implémentation reste non apparente au code de l'index de classe d'opérateur : aucune valeur NULL d'index ou de condition de recherche ne sera jamais transmis aux méthodes de la classe d'opérateurs (il est convenu que les opérateurs SP-GiST sont stricts et ainsi ne peuvent trouver des valeurs NULL). Le cas des valeurs NULL n'est ainsi plus abordé dans les paragraphes qui suivent.

Un index de classe d'opérateurs pour SP-GiST peut proposer cinq méthodes personnalisées, et deux optionnelles. Chacune de ces cinq méthodes obligatoires doit suivre la convention qui consiste à accepter deux arguments de type `internal`, le premier étant un pointeur vers une structure C contenant les valeurs en entrée de cette méthode, et le second étant un pointeur vers une structure C où les valeurs en sortie seront placées. Quatre de ces méthodes retournent `void` car leurs résultats sont présents dans la structure en sortie. Mais la méthode `leaf_consistent` retourne une valeur de type `boolean`. Les méthodes ne doivent modifier aucun des champs de la structure en entrée. Dans tous les cas, la structure en sortie est initialisée avec des zéros avant l'appel à la méthode personnalisée. La sixième méthode, optionnelle, `compress` accepte un `datum` à indexer comme seul argument et renvoie une valeur convenable pour un enregistrement physique dans une ligne feuille. La septième méthode, optionnelle, est appelée `options` et accepte un pointeur `internal` vers une structure C, remplie avec les paramètres spécifiques à la classe d'opérateurs, et renvoie `void`.

Les cinq méthodes personnalisées sont :

`config`

  Retourne des informations statiques concernant l'implémentation des index, incluant les OID du type de données du préfixe et le type de données du label du nœud.

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

      CREATE FUNCTION ma_configuration(internal, internal) RETURNS void ...

  Le premier argument est un pointeur vers une structure C `spgConfigIn`, qui contient les données en entrée de la fonction. Le second argument est un pointeur vers une structure C `spgConfigOut`, qui permet à la fonction d'y spécifier les données en sortie.

      typedef struct spgConfigIn
      {
          Oid         attType;        /* Le type de donnée à indexer */
      } spgConfigIn;

      typedef struct spgConfigOut
      {
          Oid         prefixType;     /* Le type de donnée des préfixe des tuples intermédiaires */
          Oid         labelType;      /* Le type de donnée des labels de nœud des tuples intermédiaires */
          Oid         leafType;       /* Type de données pour les valeurs de tuple feuille */
          bool        canReturnData;  /* Opclass peut reconstruire les données originales */
          bool        longValuesOK;   /* Opclass sait gérer les valeurs plus grandes qu'une page */
      } spgConfigOut;

  `attType` est fourni pour gérer les index polymorphiques de classe d'opérateurs. Pour les types de données ordinaires de classe d'opérateurs (fixés), il aura toujours la même valeur et peut ainsi être ignoré.

  Pour les classes d'opérateurs qui n'utilisent pas de préfixe, `prefixType` peut être défini à `VOIDOID`. De la même façon, pour les classes d'opérateurs qui n'utilisent pas de label de nœud, `labelType` peut être défini à `VOIDOID`. `canReturnData` peut être défini à true si la classe d'opérateurs est capable de reconstruire la valeur d'index fournie initialement. `longValuesOK` doit être défini à true uniquement lorsque `attType` est de longueur variable et que la classe d'opérateur est capable de segmenter les grandes valeurs en répétant les suffixes (voir Section 66.4.1).

  `leafType` doit correspondre au type de stockage de l'index défini par l'entrée de catalogue `opckeytype` de la classe d'opérateurs. (Notez que `opckeytype` peut valoir zéro, impliquant que le type de stockage est le même que le type en entrée de la classe d'opérateurs, ce qui est la situation la plus commune.) Pour des raisons de compatibilité ascendante, la méthode `config` peut configurer `leafType` à toute autre valeur, et cette valeur sera utilisée ; mais ceci est abandonné car le contenu de l'index est alors incorrectement identifié dans les catalogues. De plus, il est autorisé de laisser leave `leafType` non initialisé (zéro) ; ceci est interprété comme signifiant que le type de stockage de l'index est dérivé de `opckeytype`.

  Quand `attType` et `leafType` sont différents, alors la méthode optionnelle `compress` doit être fournie. La méthode `compress` est responsable de la transformation des datums pour les indexer de `attType` vers `leafType`.

`choose`

  Choisit une méthode pour insérer une nouvelle valeur dans une ligne intermédiaire.

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

      CREATE FUNCTION mon_choix(internal, internal) RETURNS void ...

  Le premier argument est un pointeur vers une structure C `spgChooseIn`, qui contient les données en entrée de la fonction. Le second argument est un pointeur vers une structure C `spgChooseOut`, qui permet à la fonction d'y spécifier les données en sortie.

      typedef struct spgChooseIn
      {
          Datum       datum;          /* donnée initiale à indexer */
          Datum       leafDatum;      /* donnée en cours à stocker dans la feuille */
          int         level;          /* niveau en cours (à partir de 0) */

          /* Données issues de la ligne intermédiaire */
          bool        allTheSame;     /* la ligne contient des valeurs équivalentes ? */
          bool        hasPrefix;      /* la ligne a-t-elle un préfixe? */
          Datum       prefixDatum;    /* si c'est le cas, la valeur de ce préfixe */
          int         nNodes;         /* nombre de nœuds dans la ligne intermédiaire */
          Datum      *nodeLabels;     /* valeurs du label du nœud (NULL sinon) */
      } spgChooseIn;

      typedef enum spgChooseResultType
      {
          spgMatchNode = 1,           /* descend dans le nœud existant */
          spgAddNode,                 /* ajoute un nœud dans la ligne intermédiaire */
          spgSplitTuple               /* scinde une ligne intermédiaire (modifie son préfixe) */
      } spgChooseResultType;

      typedef struct spgChooseOut
      {
          spgChooseResultType resultType;     /* code d'action, voir plus bas */
          union
          {
              struct                  /* resultats de spgMatchNode */
              {
                  int         nodeN;      /* descend dans ce nœud (à partir de 0) */
                  int         levelAdd;   /* incrémente le niveau de cette valeur */
                  Datum       restDatum;  /* nouvelle valeur de la feuille */
              }           matchNode;
              struct                  /* résultats de spgAddNode */
              {
                  Datum       nodeLabel;  /* nouveau label du nœud */
                  int         nodeN;      /* là où l'insérer (à partir de 0) */
              }           addNode;
              struct                  /* résultats pour spgSplitTuple */
              {
      	    /* Information pour former une ligne de niveau supérieur avec un nœud fils */
                  bool        prefixHasPrefix;    /* la ligne doit-elle avoir un préfixe ? */
                  Datum       prefixPrefixDatum;  /* si oui, sa valeur */
                  int         prefixNNodes;       /* nombre de nœuds */
                  Datum      *prefixNodeLabels;   /* leurs labels (ou NULL si
                                                   * aucun label) */
                  int         childNodeN;         /* quel nœud a un nœud fils */

                  /* Informations pour former une nouvelle ligne intermédaire de niveau inférieur
      			à partir de tous les anciens nœuds */
                  bool        postfixHasPrefix;   /* la ligne doit-elle avoir un préfixe ? */
                  Datum       postfixPrefixDatum; /* si oui, sa valeur */
              }           splitTuple;
          }           result;
      } spgChooseOut;

  `datum` est la valeur initiale de type `spgConfigIn`.`attType` de la donnée qui a été insérée dans l'index. `leafDatum` est une valeur de type `spgConfigOut`.`leafType` qui est initialement un résultat de la méthode `compress` appliquée à `datum` quand la méthode `compress` est fournie, ou la même valeur que `datum` dans le cas contraire. `leafDatum` peut changer à des niveaux inférieurs de l'arbre si la fonction `choose` ou `picksplit` change cette valeur. Lorsque la recherche liée à l'insertion atteint une feuille, la valeur actuelle de `leafDatum` sera stockée dans la nouvelle ligne de feuille créée. `level` est le niveau actuel de la ligne intermédiaire, en considérant que 0 est le niveau racine. `allTheSame` est true si la ligne intermédiaire actuelle est marquée comme contenant plusieurs nœuds équivalents. (voir Section 66.4.3). `hasPrefix` est vrai si la ligne intermédiaire actuelle contient un préfixe ; si c'est le cas, `prefixDatum` est sa valeur. `nNodes` est le nombre de nœuds enfants contenus dans la ligne intermédiaire, et `nodeLabels` est un tableau des valeurs de leurs labels, ou NULL s'il n'y a pas de labels.

  La fonction `choose` peut déterminer si la nouvelle valeur correspond à un des nœuds enfants existants, ou si un nouvel enfant doit être ajouté, ou si la nouvelle valeur n'est pas consistante avec les préfixes de ligne et qu'ainsi la ligne intermédiaire doit être découpée pour créer un préfixe moins restrictif.

  Si la nouvelle valeur correspond à un des nœuds enfants existants, définir `resultType` à `spgMatchNode`. et définir `nodeN` à l'index (à partir de 0) du nœud dans le tableau de nœud. Définir `levelAdd` à l'incrément de `level` nécessaire pour descendre au travers de ce nœud, ou le laisser à 0 si la classe d'opérateurs n'utilise pas de niveaux. Définir `restDatum` à la valeur de `leafDatum` si la classe d'opérateurs ne modifie pas les valeurs d'un niveau au suivant, ou dans le cas contraire, définir la valeur modifiée pour être utilisée comme valeur de `leafDatum` au niveau suivant.

  Si un nouveau nœud enfant doit être ajouté, définir `resultType` à `spgAddNode`. Définir `nodeLabel` au label à utiliser pour le nouveau nœud, et définir `nodeN` à l'index (de 0) auquel insérer le nœud dans le tableau de nœud. Après que ce nœud a été ajouté, la fonction `choose` sera appelée à nouveau avec la ligne intermédiaire modifiée. Cet appel devrait produire un résultat `spgMatchNode`.

  Si la nouvelle valeur est cohérente avec le préfixe de ligne, définir `resultType` à `spgSplitTuple`. Cette action déplace tous les nœuds existants dans le nouveau niveau inférieur de la ligne intermédiaire, et remplace la ligne intermédiaire existant avec une ligne qui dispose d'un unique nœud qui est lié à la nouvelle ligne intermédiaire de niveau inférieur. Définir `prefixHasPrefix` pour indiquer si les nouvelles lignes supérieures doivent avoir un préfixe, et si c'est le cas, définir `prefixPrefixDatum` à la valeur du préfixe. Cette nouvelle valeur de préfixe doit être suffisamment moins restrictive que l'original pour accepter que la nouvelle valeur soit indexée. Définir `prefixNNodes` au nombre de nœuds nécessaires pour la nouvelle ligne et définir `prefixNodeLabels` à un tableau alloué avec palloc de leurs labels, ou à NULL si les labels des nœuds ne sont pas nécessaires. Noter que la taille totale de la nouvelle ligne supérieure ne doit pas dépasser la taille totale de la ligne qu'elle remplace ; cela contraint les longueurs des nouveaux préfixes et labels. Définir `postfixHasPrefix` pour indiquer si la nouvelle ligne intermédiaire de niveau inférieur aura un préfixe, et dans ce cas définir `postfixPrefixDatum` à la valeur du préfixe. La combinaison de ces deux préfixes et le label additionnel doit avoir la même signification que le préfixe original car il n'y a pas de moyen de modifier le label du nœud qui est déplacé vers la nouvelle ligne de niveau inférieur, ni de modifier une quelconque entrée d'index enfant. Après que ce nœud ait été découpé, la fonction `choose` sera appelée à nouveau avec la ligne intermédiaire de remplacement. Cet appel devrait retourner un `spgAddNode` car, à priori, le label du nœud ajouté lors de l'étape de découpage ne correspondra pas à la nouvelle valeur. Ainsi, après cette étape, il y aura une troisième étape qui retournera finalement `spgMatchNode` et permettra l'insertion pour descendre au niveau feuille.

`picksplit`

  Décide de la manière à suivre pour créer une ligne intermédiaire à partir d'un ensemble de lignes de feuilles.

  La déclaration de fonction SQL doit ressembler à :

      CREATE FUNCTION mon_decoupage(internal, internal) RETURNS void ...

  Le premier argument est un pointeur vers une structure C `spgPickSplitIn`, qui contient les données en entrée de la fonction. Le second argument est un pointeur vers une structure C `spgPickSplitOut`, qui permet à la fonction d'y spécifier les données en sortie.

      typedef struct spgPickSplitIn
      {
          int         nTuples;        /* nombre de lignes feuilles */
          Datum      *datums;         /* leur données (tableau de taille nTuples) */
          int         level;          /* niveau actuel (à partir de 0) */
      } spgPickSplitIn;

      typedef struct spgPickSplitOut
      {
          bool        hasPrefix;      /* les nouvelles lignes intermédiaires doivent-elles avoir un préfixe ? */
          Datum       prefixDatum;    /* si oui, la valeur du préfixe */

          int         nNodes;         /* nombre de nœud pour une nouvelle ligne intermédiaire */
          Datum      *nodeLabels;     /* leurs labels (ou NULL s'il n'y a aucun label) */

          int        *mapTuplesToNodes;   /* index du nœud de chaque ligne feuille */
          Datum      *leafTupleDatums;    /* données à stocker dans chaque nouvelle ligne feuille */
      } spgPickSplitOut;

  `nTuples` est le nombre de lignes feuilles fournies. `datums` est un tableau de leurs données de type `spgConfigOut`.`leafType`. `level` est le niveau actuel que les lignes feuille concernées partagent, qui deviendra le niveau de la nouvelle ligne intermédiaire.

  Définir `hasPrefix` pour indiquer que la nouvelle ligne intermédiaire doit avoir un préfixe, et dans ce cas, définir `prefixDatum` à la valeur de ce préfixe. Définir `nNodes` pour indiquer le nombre de nœuds que contiendra la nouvelle ligne intermédiaire, et spécifier dans `nodeLabels` un tableau de leurs labels, ou NULL si les labels ne sont pas nécessaires. Attribuer à `mapTuplesToNodes` un tableau des index (à partir de zéro) des nœuds auxquels seront assignés chaque ligne feuille. Attribuer à `leafTupleDatums` un tableau des valeurs à stocker dans la nouvelle ligne de feuilles (ces valeurs seront les mêmes que celles des données `datums` fournies en paramètre si la classe d'opérateurs ne modifie pas les données d'un niveau à un autre). À noter que la fonction `picksplit` est responsable de l'allocation de mémoire des tableaux `nodeLabels`, `mapTuplesToNodes` et `leafTupleDatums`.

  Si plus d'une ligne de feuille est fournie, il est nécessaire que la fonction `picksplit` les classent en plus d'un nœud. Dans le cas contraire, il ne sera pas possible de répartir les lignes des feuilles sur des pages différentes, ce qui est pourtant l'objectif de cette opération. À cet effet, si la fonction `picksplit` se termine après avoir réparti toutes les lignes des feuilles dans le même nœud, le code du moteur de SP-GiST ne tiendra pas compte de cette décision, et générera une ligne intermédiaire dans lequel chaque ligne de feuille sera assigné aléatoirement à plusieurs nœuds de labels identiques. De telles lignes sont marquées `allTheSame` pour garder une trace de cette décision. Les fonctions `choose` et `inner_consistent` doivent tenir compte de ces lignes intermédiaires. Voir Section 66.4.3 pour plus d'informations.

  `picksplit` peut être appliqué à une unique ligne de feuille lorsque la fonction `config` définit `longValuesOK` à true et qu'une valeur plus large qu'une page est donnée en paramètre. Dans ce cas, l'objectif de la fonction est d'extraire un préfixe et de produire une donnée de feuille moins longue. Cet appel sera répété jusqu'à ce que la donnée de la feuille soit suffisamment petite pour tenir dans une page. Voir Section 66.4.1 pour plus d'information.

`inner_consistent`

  Retourne un ensemble de nœuds (branches) à suivre durant une recherche arborescente.

  La déclaration SQL de cette fonction doit ressembler à :

      CREATE FUNCTION ma_suite_de_nœuds(internal, internal) RETURNS void ...

  Le premier argument est un pointeur vers une structure C `spgInnerConsistentIn`, qui contient les données en entrée de la fonction. Le second argument est un pointeur vers une structure C `spgInnerConsistentOut`, qui permet à la fonction d'y spécifier les données en sortie.

      typedef struct spgInnerConsistentIn
      {
          ScanKey     scankeys;       /* tableau d'opérateurs et de valeurs de comparaison */
          ScanKey     orderbys;       /* tableau d'opérateurs de tri et comparaison */
                                       * de valeur */
          int         nkeys;          /* taille du tableau scankeys */
          int         norderbys;      /* taille du tableau orderbys */

          Datum       reconstructedValue;     /* valeur reconstruite au niveau parent */
          MemoryContext traversalMemoryContext;   /* placer les nouvelles valeurs ici */
          int         level;          /* niveau actuel (à partir de zéro) */
          bool        returnData;     /* retourner la valeur originale ? */

          /* Données du tuple intermédiaire en cours */
          bool        allTheSame;     /* la ligne est-elle identifiée comme all-the-same ? */
          bool        hasPrefix;      /* la ligne a-t-elle un préfixe ? */
          Datum       prefixDatum;    /* dans ce cas, la valeur du préfixe */
          int         nNodes;         /* nombre de nœuds dans la ligne intermédiaire */
          Datum      *nodeLabels;     /* labels du nœud (NULL si pas de labels) */
          void      **traversalValues;        /* valeurs traverses spécifiques de la classe d'opérateurs */
          double    **distances;              /* distances associées */
      } spgInnerConsistentIn;

      typedef struct spgInnerConsistentOut
      {
          int         nNodes;         /* nombre de nœuds enfants à visiter */
          int        *nodeNumbers;    /* leurs index dans le tableau de nœuds */
          int        *levelAdds;      /* l'incrément à apporter au niveau pour chaque enfant */
          Datum      *reconstructedValues;    /* valeurs reconstruites associées */
      } spgInnerConsistentOut;

  Le tableau `scankeys`, de longueur `nkeys`, décrit les conditions de recherche d'index. Ces conditions sont combinées avec un opérateur et seules les entrées d'index qui correspondent à toutes ces conditions sont conservées (à noter que `nkeys` = 0 implique que toutes les entrées d'index sont conservées). Généralement, la fonction `inner_consistent` ne tient compte que des champs `sk_strategy` et `sk_argument` de chaque entrée de tableau, qui fournissent respectivement l'opérateur indexé et la valeur de comparaison. En particulier, il n'est pas nécessaire de vérifier si `sk_flags` est NULL car le moteur de SP-GiST aura complété cette valeur. Le tableau `orderbys`, de longueur `norderbys`, décrit les opérateurs de tri (s'il y en a) de la même manière. `reconstructedValue` est la valeur reconstruite pour la ligne parent. La valeur est `(Datum) 0` au niveau le plus haut ou si la fonction `inner_consistent` ne fournit pas de valeur pour le niveau supérieur. `traversalValue` est un pointer vers toute donnée traverse passée à l'appel précédent de `inner_consistent` sur l'enregistrement parent de l'index, ou NULL à la racine. `traversalMemoryContext` est le contexte mémoire de stockage des valeurs traverses en sortie (voir ci-dessous). `level` est le niveau actuel de la ligne intermédiaire, en commençant à 0 pour le niveau racine. `returnData` est `true` pour la valeur reconstruite pour cette requête. Ce n'est le cas que si la fonction `config` définit `canReturnData`. `allTheSame` est true si la ligne intermédiaire en cours est marquée « all-the-same ». Dans ce cas, tous les nœuds ont le même label (si un label est défini) et ainsi soit ils correspondent tous à la requête, soit aucun ne correspond (voir Section 66.4.3). `hasPrefix` est true si la ligne intermédiaire en cours contient un préfixe. Dans ce cas, `prefixDatum` est sa valeur. `nNodes` est le nombre de nœuds enfants de la ligne intermédiaire, et `nodeLabels` est un tableau de leurs labels, ou NULL si les nœuds n'ont pas de labels.

  `nNodes` doit être défini comme le nombre de nœuds enfants qui doivent être visités durant la recherche, et `nodeNumbers` doit être défini comme le tableau de leurs index. Si la classe d'opérateurs effectue le suivi des niveaux, définir `levelAdds` comme un tableau des incréments à ajouter aux niveaux pour descendre vers chaque nœud à visiter (dans la plupart des cas, les incréments seront les mêmes pour chaque nœud, mais ce n'est pas systématique, et ainsi un tableau est employé). Si la reconstruction de la valeur est nécessaire, définir `reconstructedValues` en un tableau des valeurs reconstruites pour chaque nœud enfant à visiter. Sinon, laisser `reconstructedValues` à la valeur NULL. Si une recherche triée est exécutée, initialise `distances` à un tableau de valeurs de distance suivant le tableau `orderbys` (les nœuds avec les plus petites distances seront traitées en premier). Laisse NULL sinon. Les valeurs reconstruites sont supposées être de type `spgConfigOut`.`leafType`. (Néanmoins, comme le coeur du système ne fera rien avec elles sauf potentiellementles copier, il est suffisant qu'elles aient les mêmes propriétés `typlen` et `typbyval` que `leafType`.) S'il est souhaitable de passer les informations supplémentaires hors bande (« valeurs traverses ») pour diminuer les niveaux de l'arbre de recherche, initialiser `traversalValues` en un tableau des valeurs traverses appropriées, un pour chaque nœud enfants à visiter ; sinon laisser `traversalValues` à NULL. Notez que la fonction `inner_consistent` est responsable de l'allocation mémoire des tableaux `nodeNumbers`, `levelAdds`, `distances`, `reconstructedValues` et `traversalValues` dans le contexte mémoire actuel. Néanmoins, toute valeur traverse en sortie pointée par le tableau `traversalValues` devrait être allouée dans `traversalMemoryContext`. Chaque valeur traverse doit être un morceau simple alloué avec la fonction palloc.

`leaf_consistent`

  Retourne true si une ligne de feuille satisfait une requête.

  La déclaration SQL de cette fonction doit ressembler à :

      CREATE FUNCTION ma_fonction_leaf_consistent(internal, internal) RETURNS bool ...

  Le premier argument est un pointeur vers une structure C `spgLeafConsistentIn`, qui contient les données en entrée de la fonction. Le second argument est un pointeur vers une structure C `spgLeafConsistentOut`, qui permet à la fonction d'y spécifier les données en sortie.

      typedef struct spgLeafConsistentIn
      {
          ScanKey     scankeys;       /* tableau d'opérateurs et de valeurs de comparaison */
          ScanKey     orderbys;       /* tableau d'opérateurs de tri et comparaison */
                                       * de valeurs */
          int         nkeys;          /* taille du tableau scankeys */
          int         norderbys;      /* taille du tableau orderbys */

          Datum       reconstructedValue;     /* valeur reconstruite au parent */
          void       *traversalValue; /* valeur traverse spécifique à la classe d'opérateurs */
          int         level;          /* niveau actuel (à partir de zéro) */
          bool        returnData;     /* les données originales doivent-elles être reconstruites ? */

          Datum       leafDatum;      /* données de la ligne de feuille */
      } spgLeafConsistentIn;

      typedef struct spgLeafConsistentOut
      {
          Datum       leafValue;      /* données originales reconstruites, le cas échéant */
          bool        recheck;        /* définir à true si l'opérateur doit être revérifié */
          Datum       leafValue;        /* valeur d'origine reconstruite, le cas échéant */
          bool        recheck;          /* positionné à true si l'opérateur doit être revérifié */
          bool        recheckDistances; /* positionné à true si les distances doivent être revérifiées */
          double     *distances;        /* associated distances */
      } spgLeafConsistentOut;

  Le tableau `scankeys`, de longueur `nkeys`, décrit les conditions de recherche dans l'index. Ces conditions sont uniquement combinées avec AND -- Seules les entrées d'index qui satisfont toutes les conditions satisfont la requête (Notez que `nkeys` = 0 implique que toutes les entrées de l'index satisfont la requête). Généralement, la fonction de recherche ne tient compte que des champs `sk_strategy` et `sk_argument` de chaque entrée du tableau, qui correspondent respectivement à l'opérateur indexable et à la valeur de comparaison. En particulier, il n'est pas nécessaire de vérifier `sk_flags` pour savoir que la valeur de comparaison est NULL car le code du cœur de SP-GiST filtre ces conditions. Le tableau `orderbys`, de taille `norderbys`, décrit les opérateurs de tri de la même manière. `reconstructedValue` est la valeur reconstruite pour la ligne parent ; Il s'agit de `(Datum) 0` au niveau racine ou si la fonction `inner_consistent` ne fournit pas de valeur au niveau parent. `traversalValue` est un pointeur vers toute donnée traverse passée lors de l'appel précédent à `inner_consistent` de l'enregistrement parent de l'index ou NULL à la racine. `level` est le niveau actuel de la ligne de feuille, qui commence à zéro pour le niveau racine. `returnData` est `true` s'il est nécessaire de reconstruire les données pour cette requête. Cela ne sera le cas que lorsque la fonction `config` vérifie `canReturnData`. `leafDatum` est la valeur de la clé stockée de `spgConfigOut`.`leafType` dans la ligne de feuille en cours.

  La fonction doit retourner `true` si la ligne de feuille correspond à la requête ou `false` sinon. Dans le cas où la valeur serait `true`, et que `returnData` est `true` alors `leafValue` doit être défini à la valeur originale, de type `spgConfigIn`.`attType` fournie pour être indexée pour cette ligne de feuille. `recheck` peut être défini à `true` si la correspondance est incertaine et ainsi l'opérateur doit être réappliqué à la pile de ligne courante pour vérifier la correspondance. Si une recherche triée est effectuée, positionne `distances` à un tableau de distance suivant le tableau `orderbys` Laisse NULL sinon. Si au moins une des distances retournées n'est pas exacte, positionne `recheckDistances` à true. Dans ce cas, l'exécuteur recalculera la distance exacte après avoir récupéré toutes les lignes de la table, et réordonnera les lignes si besoin.

Les méthodes optionnelles définies par l'utilisateur sont :

`Datum compress(Datum in)`

  Convertit un élément de données dans un format convenable pour un stockage physique dans un enregistrement feuille d'un index. Elle accepte une valeur de type `spgConfigIn`.`attType` et renvoie une valeur de type `spgConfigOut`.`leafType`. La valeur en sortie ne doit pas contenir un pointeur TOAST hors ligne.

  Note : la méthode `compress` est seulement appliquée aux valeurs à enregistrer. Les méthodes cohérentes reçoivent les clés de parcours non modifiées, sans transformation utilisant `compress`.

`options`

  Définit un ensemble de paramètres visibles aux utilisateurs qui contrôlent le comportement d'une classe d'opérateurs.

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

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

  La fonction `options` se voit donné 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 la représentation de la clé dans SP-GiST est flexible, elle peut dépendre de paramètres spécifiés par l'utilisateur.

Toutes les méthodes permettant d'utiliser SP-GiST sont normalement exécutées dans un contexte mémoire de courte durée, c'est-à-dire que `CurrentMemoryContext` sera remis à zéro après le traitement de chaque ligne. Il n'est cependant pas réellement important de se soucier de désallouer la mémoire allouée avec palloc (la méthode `config` est une exception : elle essaiera d'éviter les fuites mémoire. Mais généralement, la méthode `config` ne nécessite rien si ce n'est assigner des constantes aux structures passées en paramètre).

Si la colonne indexée a un type de donnée collationnable, l'index de collationnement sera passé à toutes les méthodes, en utilisant le mécanisme standard `PG_GET_COLLATION()`.