Movatterモバイル変換

Table 62.2. Built-inSP-GiST Operator Classes

Note

TheSP-GiST core code takes care of null entries. AlthoughSP-GiST indexes do store entries for nulls in indexed columns, this is hidden from the index operator class code: no null index entries or search conditions will ever be passed to the operator class methods. (It is assumed thatSP-GiST operators are strict and so cannot succeed for null values.) Null values are therefore not discussed further here.

config

Returns static information about the index implementation, including the data type OIDs of the prefix and node label data types.

TheSQL declaration of the function must look like this:

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

The first argument is a pointer to aspgConfigIn C struct, containing input data for the function. The second argument is a pointer to aspgConfigOut C struct, which the function must fill with result data.

typedef struct spgConfigIn{    Oid         attType;        /* Data type to be indexed */} spgConfigIn;typedef struct spgConfigOut{    Oid         prefixType;     /* Data type of inner-tuple prefixes */    Oid         labelType;      /* Data type of inner-tuple node labels */    Oid         leafType;       /* Data type of leaf-tuple values */    bool        canReturnData;  /* Opclass can reconstruct original data */    bool        longValuesOK;   /* Opclass can cope with values > 1 page */} spgConfigOut;

attType is passed in order to support polymorphic index operator classes; for ordinary fixed-data-type operator classes, it will always have the same value and so can be ignored.

For operator classes that do not use prefixes,prefixType can be set toVOIDOID. Likewise, for operator classes that do not use node labels,labelType can be set toVOIDOID.canReturnData should be set true if the operator class is capable of reconstructing the originally-supplied index value.longValuesOK should be set true only when theattType is of variable length and the operator class is capable of segmenting long values by repeated suffixing (seeSection 62.3.4.1).

leafType should match the index storage type defined by the operator class'sopckeytype catalog entry. (Note thatopckeytype can be zero, implying the storage type is the same as the operator class's input type, which is the most common situation.) For reasons of backward compatibility, theconfig method can setleafType to some other value, and that value will be used; but this is deprecated since the index contents are then incorrectly identified in the catalogs. Also, it's permissible to leaveleafType uninitialized (zero); that is interpreted as meaning the index storage type derived fromopckeytype.

WhenattType andleafType are different, the optional methodcompress must be provided. Methodcompress is responsible for transformation of datums to be indexed fromattType toleafType.

choose

Chooses a method for inserting a new value into an inner tuple.

TheSQL declaration of the function must look like this:

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

The first argument is a pointer to aspgChooseIn C struct, containing input data for the function. The second argument is a pointer to aspgChooseOut C struct, which the function must fill with result data.

typedef struct spgChooseIn{    Datum       datum;          /* original datum to be indexed */    Datum       leafDatum;      /* current datum to be stored at leaf */    int         level;          /* current level (counting from zero) */    /* Data from current inner tuple */    bool        allTheSame;     /* tuple is marked all-the-same? */    bool        hasPrefix;      /* tuple has a prefix? */    Datum       prefixDatum;    /* if so, the prefix value */    int         nNodes;         /* number of nodes in the inner tuple */    Datum      *nodeLabels;     /* node label values (NULL if none) */} spgChooseIn;typedef enum spgChooseResultType{    spgMatchNode = 1,           /* descend into existing node */    spgAddNode,                 /* add a node to the inner tuple */    spgSplitTuple               /* split inner tuple (change its prefix) */} spgChooseResultType;typedef struct spgChooseOut{    spgChooseResultType resultType;     /* action code, see above */    union    {        struct                  /* results for spgMatchNode */        {            int         nodeN;      /* descend to this node (index from 0) */            int         levelAdd;   /* increment level by this much */            Datum       restDatum;  /* new leaf datum */        }           matchNode;        struct                  /* results for spgAddNode */        {            Datum       nodeLabel;  /* new node's label */            int         nodeN;      /* where to insert it (index from 0) */        }           addNode;        struct                  /* results for spgSplitTuple */        {            /* Info to form new upper-level inner tuple with one child tuple */            bool        prefixHasPrefix;    /* tuple should have a prefix? */            Datum       prefixPrefixDatum;  /* if so, its value */            int         prefixNNodes;       /* number of nodes */            Datum      *prefixNodeLabels;   /* their labels (or NULL for                                             * no labels) */            int         childNodeN;         /* which node gets child tuple */            /* Info to form new lower-level inner tuple with all old nodes */            bool        postfixHasPrefix;   /* tuple should have a prefix? */            Datum       postfixPrefixDatum; /* if so, its value */        }           splitTuple;    }           result;} spgChooseOut;

datum is the original datum ofspgConfigIn.attType type that was to be inserted into the index.leafDatum is a value ofspgConfigOut.leafType type, which is initially a result of methodcompress applied todatum when methodcompress is provided, or the same value asdatum otherwise.leafDatum can change at lower levels of the tree if thechoose orpicksplit methods change it. When the insertion search reaches a leaf page, the current value ofleafDatum is what will be stored in the newly created leaf tuple.level is the current inner tuple's level, starting at zero for the root level.allTheSame is true if the current inner tuple is marked as containing multiple equivalent nodes (seeSection 62.3.4.3).hasPrefix is true if the current inner tuple contains a prefix; if so,prefixDatum is its value.nNodes is the number of child nodes contained in the inner tuple, andnodeLabels is an array of their label values, or NULL if there are no labels.

Thechoose function can determine either that the new value matches one of the existing child nodes, or that a new child node must be added, or that the new value is inconsistent with the tuple prefix and so the inner tuple must be split to create a less restrictive prefix.

If the new value matches one of the existing child nodes, setresultType tospgMatchNode. SetnodeN to the index (from zero) of that node in the node array. SetlevelAdd to the increment inlevel caused by descending through that node, or leave it as zero if the operator class does not use levels. SetrestDatum to equalleafDatum if the operator class does not modify datums from one level to the next, or otherwise set it to the modified value to be used asleafDatum at the next level.

If a new child node must be added, setresultType tospgAddNode. SetnodeLabel to the label to be used for the new node, and setnodeN to the index (from zero) at which to insert the node in the node array. After the node has been added, thechoose function will be called again with the modified inner tuple; that call should result in anspgMatchNode result.

If the new value is inconsistent with the tuple prefix, setresultType tospgSplitTuple. This action moves all the existing nodes into a new lower-level inner tuple, and replaces the existing inner tuple with a tuple having a single downlink pointing to the new lower-level inner tuple. SetprefixHasPrefix to indicate whether the new upper tuple should have a prefix, and if so setprefixPrefixDatum to the prefix value. This new prefix value must be sufficiently less restrictive than the original to accept the new value to be indexed. SetprefixNNodes to the number of nodes needed in the new tuple, and setprefixNodeLabels to a palloc'd array holding their labels, or to NULL if node labels are not required. Note that the total size of the new upper tuple must be no more than the total size of the tuple it is replacing; this constrains the lengths of the new prefix and new labels. SetchildNodeN to the index (from zero) of the node that will downlink to the new lower-level inner tuple. SetpostfixHasPrefix to indicate whether the new lower-level inner tuple should have a prefix, and if so setpostfixPrefixDatum to the prefix value. The combination of these two prefixes and the downlink node's label (if any) must have the same meaning as the original prefix, because there is no opportunity to alter the node labels that are moved to the new lower-level tuple, nor to change any child index entries. After the node has been split, thechoose function will be called again with the replacement inner tuple. That call may return anspgAddNode result, if no suitable node was created by thespgSplitTuple action. Eventuallychoose must returnspgMatchNode to allow the insertion to descend to the next level.

picksplit

Decides how to create a new inner tuple over a set of leaf tuples.

TheSQL declaration of the function must look like this:

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

The first argument is a pointer to aspgPickSplitIn C struct, containing input data for the function. The second argument is a pointer to aspgPickSplitOut C struct, which the function must fill with result data.

typedef struct spgPickSplitIn{    int         nTuples;        /* number of leaf tuples */    Datum      *datums;         /* their datums (array of length nTuples) */    int         level;          /* current level (counting from zero) */} spgPickSplitIn;typedef struct spgPickSplitOut{    bool        hasPrefix;      /* new inner tuple should have a prefix? */    Datum       prefixDatum;    /* if so, its value */    int         nNodes;         /* number of nodes for new inner tuple */    Datum      *nodeLabels;     /* their labels (or NULL for no labels) */    int        *mapTuplesToNodes;   /* node index for each leaf tuple */    Datum      *leafTupleDatums;    /* datum to store in each new leaf tuple */} spgPickSplitOut;

nTuples is the number of leaf tuples provided.datums is an array of their datum values ofspgConfigOut.leafType type.level is the current level that all the leaf tuples share, which will become the level of the new inner tuple.

SethasPrefix to indicate whether the new inner tuple should have a prefix, and if so setprefixDatum to the prefix value. SetnNodes to indicate the number of nodes that the new inner tuple will contain, and setnodeLabels to an array of their label values, or to NULL if node labels are not required. SetmapTuplesToNodes to an array that gives the index (from zero) of the node that each leaf tuple should be assigned to. SetleafTupleDatums to an array of the values to be stored in the new leaf tuples (these will be the same as the inputdatums if the operator class does not modify datums from one level to the next). Note that thepicksplit function is responsible for palloc'ing thenodeLabels,mapTuplesToNodes andleafTupleDatums arrays.

If more than one leaf tuple is supplied, it is expected that thepicksplit function will classify them into more than one node; otherwise it is not possible to split the leaf tuples across multiple pages, which is the ultimate purpose of this operation. Therefore, if thepicksplit function ends up placing all the leaf tuples in the same node, the core SP-GiST code will override that decision and generate an inner tuple in which the leaf tuples are assigned at random to several identically-labeled nodes. Such a tuple is markedallTheSame to signify that this has happened. Thechoose andinner_consistent functions must take suitable care with such inner tuples. SeeSection 62.3.4.3 for more information.

picksplit can be applied to a single leaf tuple only in the case that theconfig function setlongValuesOK to true and a larger-than-a-page input value has been supplied. In this case the point of the operation is to strip off a prefix and produce a new, shorter leaf datum value. The call will be repeated until a leaf datum short enough to fit on a page has been produced. SeeSection 62.3.4.1 for more information.

inner_consistent

Returns set of nodes (branches) to follow during tree search.

TheSQL declaration of the function must look like this:

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

The first argument is a pointer to aspgInnerConsistentIn C struct, containing input data for the function. The second argument is a pointer to aspgInnerConsistentOut C struct, which the function must fill with result data.

typedef struct spgInnerConsistentIn{    ScanKey     scankeys;       /* array of operators and comparison values */    ScanKey     orderbys;       /* array of ordering operators and comparison                                 * values */    int         nkeys;          /* length of scankeys array */    int         norderbys;      /* length of orderbys array */    Datum       reconstructedValue;     /* value reconstructed at parent */    void       *traversalValue; /* opclass-specific traverse value */    MemoryContext traversalMemoryContext;   /* put new traverse values here */    int         level;          /* current level (counting from zero) */    bool        returnData;     /* original data must be returned? */    /* Data from current inner tuple */    bool        allTheSame;     /* tuple is marked all-the-same? */    bool        hasPrefix;      /* tuple has a prefix? */    Datum       prefixDatum;    /* if so, the prefix value */    int         nNodes;         /* number of nodes in the inner tuple */    Datum      *nodeLabels;     /* node label values (NULL if none) */} spgInnerConsistentIn;typedef struct spgInnerConsistentOut{    int         nNodes;         /* number of child nodes to be visited */    int        *nodeNumbers;    /* their indexes in the node array */    int        *levelAdds;      /* increment level by this much for each */    Datum      *reconstructedValues;    /* associated reconstructed values */    void      **traversalValues;        /* opclass-specific traverse values */    double    **distances;              /* associated distances */} spgInnerConsistentOut;

The arrayscankeys, of lengthnkeys, describes the index search condition(s). These conditions are combined with AND — only index entries that satisfy all of them are interesting. (Note thatnkeys = 0 implies that all index entries satisfy the query.) Usually the consistent function only cares about thesk_strategy andsk_argument fields of each array entry, which respectively give the indexable operator and comparison value. In particular it is not necessary to checksk_flags to see if the comparison value is NULL, because the SP-GiST core code will filter out such conditions. The arrayorderbys, of lengthnorderbys, describes ordering operators (if any) in the same manner.reconstructedValue is the value reconstructed for the parent tuple; it is(Datum) 0 at the root level or if theinner_consistent function did not provide a value at the parent level.traversalValue is a pointer to any traverse data passed down from the previous call ofinner_consistent on the parent index tuple, or NULL at the root level.traversalMemoryContext is the memory context in which to store output traverse values (see below).level is the current inner tuple's level, starting at zero for the root level.returnData istrue if reconstructed data is required for this query; this will only be so if theconfig function assertedcanReturnData.allTheSame is true if the current inner tuple is marked“all-the-same”; in this case all the nodes have the same label (if any) and so either all or none of them match the query (seeSection 62.3.4.3).hasPrefix is true if the current inner tuple contains a prefix; if so,prefixDatum is its value.nNodes is the number of child nodes contained in the inner tuple, andnodeLabels is an array of their label values, or NULL if the nodes do not have labels.

nNodes must be set to the number of child nodes that need to be visited by the search, andnodeNumbers must be set to an array of their indexes. If the operator class keeps track of levels, setlevelAdds to an array of the level increments required when descending to each node to be visited. (Often these increments will be the same for all the nodes, but that's not necessarily so, so an array is used.) If value reconstruction is needed, setreconstructedValues to an array of the values reconstructed for each child node to be visited; otherwise, leavereconstructedValues as NULL. The reconstructed values are assumed to be of typespgConfigOut.leafType. (However, since the core system will do nothing with them except possibly copy them, it is sufficient for them to have the sametyplen andtypbyval properties asleafType.) If ordered search is performed, setdistances to an array of distance values according toorderbys array (nodes with lowest distances will be processed first). Leave it NULL otherwise. If it is desired to pass down additional out-of-band information (“traverse values”) to lower levels of the tree search, settraversalValues to an array of the appropriate traverse values, one for each child node to be visited; otherwise, leavetraversalValues as NULL. Note that theinner_consistent function is responsible for palloc'ing thenodeNumbers,levelAdds,distances,reconstructedValues, andtraversalValues arrays in the current memory context. However, any output traverse values pointed to by thetraversalValues array should be allocated intraversalMemoryContext. Each traverse value must be a single palloc'd chunk.

leaf_consistent

Returns true if a leaf tuple satisfies a query.

TheSQL declaration of the function must look like this:

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

The first argument is a pointer to aspgLeafConsistentIn C struct, containing input data for the function. The second argument is a pointer to aspgLeafConsistentOut C struct, which the function must fill with result data.

typedef struct spgLeafConsistentIn{    ScanKey     scankeys;       /* array of operators and comparison values */    ScanKey     orderbys;       /* array of ordering operators and comparison                                 * values */    int         nkeys;          /* length of scankeys array */    int         norderbys;      /* length of orderbys array */    Datum       reconstructedValue;     /* value reconstructed at parent */    void       *traversalValue; /* opclass-specific traverse value */    int         level;          /* current level (counting from zero) */    bool        returnData;     /* original data must be returned? */    Datum       leafDatum;      /* datum in leaf tuple */} spgLeafConsistentIn;typedef struct spgLeafConsistentOut{    Datum       leafValue;        /* reconstructed original data, if any */    bool        recheck;          /* set true if operator must be rechecked */    bool        recheckDistances; /* set true if distances must be rechecked */    double     *distances;        /* associated distances */} spgLeafConsistentOut;

The arrayscankeys, of lengthnkeys, describes the index search condition(s). These conditions are combined with AND — only index entries that satisfy all of them satisfy the query. (Note thatnkeys = 0 implies that all index entries satisfy the query.) Usually the consistent function only cares about thesk_strategy andsk_argument fields of each array entry, which respectively give the indexable operator and comparison value. In particular it is not necessary to checksk_flags to see if the comparison value is NULL, because the SP-GiST core code will filter out such conditions. The arrayorderbys, of lengthnorderbys, describes the ordering operators in the same manner.reconstructedValue is the value reconstructed for the parent tuple; it is(Datum) 0 at the root level or if theinner_consistent function did not provide a value at the parent level.traversalValue is a pointer to any traverse data passed down from the previous call ofinner_consistent on the parent index tuple, or NULL at the root level.level is the current leaf tuple's level, starting at zero for the root level.returnData istrue if reconstructed data is required for this query; this will only be so if theconfig function assertedcanReturnData.leafDatum is the key value ofspgConfigOut.leafType stored in the current leaf tuple.

The function must returntrue if the leaf tuple matches the query, orfalse if not. In thetrue case, ifreturnData istrue thenleafValue must be set to the value (of typespgConfigIn.attType) originally supplied to be indexed for this leaf tuple. Also,recheck may be set totrue if the match is uncertain and so the operator(s) must be re-applied to the actual heap tuple to verify the match. If ordered search is performed, setdistances to an array of distance values according toorderbys array. Leave it NULL otherwise. If at least one of returned distances is not exact, setrecheckDistances to true. In this case, the executor will calculate the exact distances after fetching the tuple from the heap, and will reorder the tuples if needed.

Datum compress(Datum in)

Converts a data item into a format suitable for physical storage in a leaf tuple of the index. It accepts a value of typespgConfigIn.attType and returns a value of typespgConfigOut.leafType. The output value must not contain an out-of-line TOAST pointer.

Note: thecompress method is only applied to values to be stored. The consistent methods receive queryscankeys unchanged, without transformation usingcompress.

options

Defines a set of user-visible parameters that control operator class behavior.

TheSQL declaration of the function must look like this:

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

The function is passed a pointer to alocal_relopts struct, which needs to be filled with a set of operator class specific options. The options can be accessed from other support functions using thePG_HAS_OPCLASS_OPTIONS() andPG_GET_OPCLASS_OPTIONS() macros.

Since the representation of the key inSP-GiST is flexible, it may depend on user-specified parameters.

Individual leaf tuples and inner tuples must fit on a single index page (8kB by default). Therefore, when indexing values of variable-length data types, long values can only be supported by methods such as radix trees, in which each level of the tree includes a prefix that is short enough to fit on a page, and the final leaf level includes a suffix also short enough to fit on a page. The operator class should setlongValuesOK to true only if it is prepared to arrange for this to happen. Otherwise, theSP-GiST core will reject any request to index a value that is too large to fit on an index page.

Likewise, it is the operator class's responsibility that inner tuples do not grow too large to fit on an index page; this limits the number of child nodes that can be used in one inner tuple, as well as the maximum size of a prefix value.

Another limitation is that when an inner tuple's node points to a set of leaf tuples, those tuples must all be in the same index page. (This is a design decision to reduce seeking and save space in the links that chain such tuples together.) If the set of leaf tuples grows too large for a page, a split is performed and an intermediate inner tuple is inserted. For this to fix the problem, the new inner tuplemust divide the set of leaf values into more than one node group. If the operator class'spicksplit function fails to do that, theSP-GiST core resorts to extraordinary measures described inSection 62.3.4.3.

WhenlongValuesOK is true, it is expected that successive levels of theSP-GiST tree will absorb more and more information into the prefixes and node labels of the inner tuples, making the required leaf datum smaller and smaller, so that eventually it will fit on a page. To prevent bugs in operator classes from causing infinite insertion loops, theSP-GiST core will raise an error if the leaf datum does not become any smaller within ten cycles ofchoose method calls.

Some tree algorithms use a fixed set of nodes for each inner tuple; for example, in a quad-tree there are always exactly four nodes corresponding to the four quadrants around the inner tuple's centroid point. In such a case the code typically works with the nodes by number, and there is no need for explicit node labels. To suppress node labels (and thereby save some space), thepicksplit function can return NULL for thenodeLabels array, and likewise thechoose function can return NULL for theprefixNodeLabels array during aspgSplitTuple action. This will in turn result innodeLabels being NULL during subsequent calls tochoose andinner_consistent. In principle, node labels could be used for some inner tuples and omitted for others in the same index.

When working with an inner tuple having unlabeled nodes, it is an error forchoose to returnspgAddNode, since the set of nodes is supposed to be fixed in such cases.

TheSP-GiST core can override the results of the operator class'spicksplit function whenpicksplit fails to divide the supplied leaf values into at least two node categories. When this happens, the new inner tuple is created with multiple nodes that each have the same label (if any) thatpicksplit gave to the one node it did use, and the leaf values are divided at random among these equivalent nodes. TheallTheSame flag is set on the inner tuple to warn thechoose andinner_consistent functions that the tuple does not have the node set that they might otherwise expect.

When dealing with anallTheSame tuple, achoose result ofspgMatchNode is interpreted to mean that the new value can be assigned to any of the equivalent nodes; the core code will ignore the suppliednodeN value and descend into one of the nodes at random (so as to keep the tree balanced). It is an error forchoose to returnspgAddNode, since that would make the nodes not all equivalent; thespgSplitTuple action must be used if the value to be inserted doesn't match the existing nodes.

When dealing with anallTheSame tuple, theinner_consistent function should return either all or none of the nodes as targets for continuing the index search, since they are all equivalent. This may or may not require any special-case code, depending on how much theinner_consistent function normally assumes about the meaning of the nodes.