PostgreSQLLa base de données la plus sophistiquée au monde.

Version anglaise

60.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 des valeurs du même type de données que la colonne indexée. Les lignes des feuilles à la racine contiendront toujours la valeur originale de la donnée indexée, mais les lignes des feuilles à des niveaux inférieurs peuvent en contenir seulement des représentations réduites, comme un suffixe. Dans ce cas, les classes d'opérateur 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.

Les lignes intermédiaires 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. 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érateur. 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érateur 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.

[Note]

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érateur (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érateur pour SP-GiST peut proposer cinq méthodes personnalisées. Chacune de ces cinq méthodes 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ésent dans la structure en sortie. Mais la méthode leaf_consistent retourne en complément 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.

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 */
    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 60.4.1, « Limites de SP-GiST »).

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 */
        {
            /* 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 60.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.

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 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. (si les nœuds ne nécessitent pas de label, définir nodeLabels à NULL ; voir Section 60.4.2, « SP-GiST sans label de nœud » pour plus de détails.) 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 60.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 60.4.1, « Limites de SP-GiST » 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 */
    int         nkeys;          /* taille du tableau */

    Datum       reconstructedValue;     /* valeur reconstruite au niveau parent */
    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) */
} 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. 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 60.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. Notez que la fonction inner_consistent est responsable de l'allocation mémoire des tableaux nodeNumbers, levelAdds et reconstructedValues.

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

    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. 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.

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().