62.3. Extensibilité

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 */
    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érateur. Pour les types de données ordinaires de classe d'opérateur (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érateur 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 62.4.1, « Limites de SP-GiST »).

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 */
        {
            /* Informations pour former a nouveau tuple intermédiaire avec un nœud */
            bool        prefixHasPrefix;    /* la ligne doit-elle avoir un préfixe ? */
            Datum       prefixPrefixDatum;  /* si oui, sa valeur */
            Datum       nodeLabel;          /* label du nœud */

            /* 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 la donnée qui a été insérée dans l'index. leafDatum est initialement le même que datum, mais 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 62.4.3, « Lignes intermédiaires « All-the-same » »). 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érateur n'utilise pas de niveaux. Définir restDatum à la valeur de datum si la classe d'opérateur 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 ait é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, et ne doit pas être plus longue que le préfixe original. Définir nodeLabel à la valeur du label à utiliser pour le nœud qui pointera vers la ligne intermédiaire de niveau inférieur. 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.

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 lgne 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. 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 auquels 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érateur 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 62.4.3, « Lignes intermédiaires « All-the-same » » 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 62.4.1, « Limites de SP-GiST » pour plus d'information.

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 */
    int         nkeys;          /* taille du tableau */

    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érateur */
} 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. Seuls 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. 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 62.4.3, « Lignes intermédiaires « All-the-same » »). 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érateur 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 comme le tableau des valeurs reconstruites pour chaque nœud enfant à visiter. Sinon, laisser reconstructedValues à la valeur NULL. 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œuds enfants à visiter ; sinon laisser traversalValues à NULL. Notez que la fonction inner_consistent est responsable de l'allocation mémoire des tableaux nodeNumbers, levelAdds 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.

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 */
    int         nkeys;          /* longueur d'un tableau */

    void       *traversalValue; /* valeur traverse spécifique à la classe d'opérateur */
    Datum       reconstructedValue;     /* valeur reconstruite au parent */
    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é */
} 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. 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 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 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.