PostgreSQL 9.3.25 Documentation | ||||
---|---|---|---|---|
Prev | Up | Chapter 56. SP-GiST Indexes | Next |
SP-GiST offers an interface with a high level of abstraction, requiring the access method developer to implement only methods specific to a given data type. The SP-GiST core is responsible for efficient disk mapping and searching the tree structure. It also takes care of concurrency and logging considerations.
Leaf tuples of an SP-GiST tree contain values of the same data type as the indexed column. Leaf tuples at the root level will always contain the original indexed data value, but leaf tuples at lower levels might contain only a compressed representation, such as a suffix. In that case the operator class support functions must be able to reconstruct the original value using information accumulated from the inner tuples that are passed through to reach the leaf level.
Inner tuples are more complex, since they are branching points in the search tree. Each inner tuple contains a set of one or more nodes, which represent groups of similar leaf values. A node contains a downlink that leads to either another, lower-level inner tuple, or a short list of leaf tuples that all lie on the same index page. Each node has a label that describes it; for example, in a radix tree the node label could be the next character of the string value. Optionally, an inner tuple can have a prefix value that describes all its members. In a radix tree this could be the common prefix of the represented strings. The prefix value is not necessarily really a prefix, but can be any data needed by the operator class; for example, in a quad-tree it can store the central point that the four quadrants are measured with respect to. A quad-tree inner tuple would then also contain four nodes corresponding to the quadrants around this central point.
Some tree algorithms require knowledge of level (or depth) of the current tuple, so the SP-GiST core provides the possibility for operator classes to manage level counting while descending the tree. There is also support for incrementally reconstructing the represented value when that is needed.
Note: The SP-GiST core code takes care of null entries. Although SP-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 that SP-GiST operators are strict and so cannot succeed for null values.) Null values are therefore not discussed further here.
There are five user-defined methods that an index operator class
for SP-GiST must provide. All
five follow the convention of accepting two internal arguments, the first of which is a pointer to
a C struct containing input values for the support method, while
the second argument is a pointer to a C struct where output values
must be placed. Four of the methods just return void, since all their results appear in the output
struct; but leaf_consistent
additionally returns a boolean result. The
methods must not modify any fields of their input structs. In all
cases, the output struct is initialized to zeroes before calling
the user-defined method.
The five user-defined methods are:
config
Returns static information about the index implementation, including the data type OIDs of the prefix and node label data types.
The SQL declaration of the function must look like this:
CREATE FUNCTION my_config(internal, internal) RETURNS void ...
The first argument is a pointer to a spgConfigIn C struct, containing input data for the function. The second argument is a pointer to a spgConfigOut 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 */ 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 to VOIDOID. Likewise, for operator classes that do not use node labels, labelType can be set to VOIDOID. 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 the attType is of variable length and the operator class is capable of segmenting long values by repeated suffixing (see Section 56.3.1).
choose
Chooses a method for inserting a new value into an inner tuple.
The SQL declaration of the function must look like this:
CREATE FUNCTION my_choose(internal, internal) RETURNS void ...
The first argument is a pointer to a spgChooseIn C struct, containing input data for the function. The second argument is a pointer to a spgChooseOut 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 inner tuple with one node */ bool prefixHasPrefix; /* tuple should have a prefix? */ Datum prefixPrefixDatum; /* if so, its value */ Datum nodeLabel; /* node's label */ /* 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 that
was to be inserted into the index. leafDatum is initially the same as datum, but can change at lower levels of the
tree if the choose
or picksplit
methods change it. When the insertion
search reaches a leaf page, the current value of leafDatum 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 (see
Section
56.3.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, and nodeLabels is an
array of their label values, or NULL if there are no labels.
The choose
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, set resultType to spgMatchNode. Set nodeN to the index (from zero) of that node in the node array. Set levelAdd to the increment in level caused by descending through that node, or leave it as zero if the operator class does not use levels. Set restDatum to equal datum 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 as leafDatum at the next level.
If a new child node must be added, set resultType to spgAddNode. Set nodeLabel to the label to be used for the new
node, and set nodeN to the index (from
zero) at which to insert the node in the node array. After the node
has been added, the choose
function
will be called again with the modified inner tuple; that call
should result in an spgMatchNode
result.
If the new value is inconsistent with the tuple prefix, set
resultType to spgSplitTuple. 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 node that links to the new
lower-level inner tuple. Set prefixHasPrefix to indicate whether the new
upper tuple should have a prefix, and if so set prefixPrefixDatum to the prefix value. This new
prefix value must be sufficiently less restrictive than the
original to accept the new value to be indexed, and it should be no
longer than the original prefix. Set nodeLabel to the label to be used for the node
that will point to the new lower-level inner tuple. Set postfixHasPrefix to indicate whether the new
lower-level inner tuple should have a prefix, and if so set
postfixPrefixDatum to the prefix
value. The combination of these two prefixes and the additional
label 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, the choose
function will be called again with the
replacement inner tuple. That call will usually result in an
spgAddNode result, since presumably the
node label added in the split step will not match the new value; so
after that, there will be a third call that finally returns
spgMatchNode and allows the insertion to
descend to the leaf level.
picksplit
Decides how to create a new inner tuple over a set of leaf tuples.
The SQL declaration of the function must look like this:
CREATE FUNCTION my_picksplit(internal, internal) RETURNS void ...
The first argument is a pointer to a spgPickSplitIn C struct, containing input data for the function. The second argument is a pointer to a spgPickSplitOut 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. level is the current level that all the leaf tuples share, which will become the level of the new inner tuple.
Set hasPrefix to indicate whether
the new inner tuple should have a prefix, and if so set prefixDatum to the prefix value. Set nNodes to indicate the number of nodes that the
new inner tuple will contain, and set nodeLabels to an array of their label values.
(If the nodes do not require labels, set nodeLabels to NULL; see Section 56.3.2
for details.) Set mapTuplesToNodes to
an array that gives the index (from zero) of the node that each
leaf tuple should be assigned to. Set leafTupleDatums to an array of the values to be
stored in the new leaf tuples (these will be the same as the input
datums if the operator class does not
modify datums from one level to the next). Note that the
picksplit
function is responsible for
palloc'ing the nodeLabels, mapTuplesToNodes and leafTupleDatums arrays.
If more than one leaf tuple is supplied, it is expected that the
picksplit
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 the picksplit
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 marked allTheSame to signify that
this has happened. The choose
and
inner_consistent
functions must take
suitable care with such inner tuples. See Section 56.3.3
for more information.
picksplit
can be applied to a
single leaf tuple only in the case that the config
function set longValuesOK 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. See Section 56.3.1 for
more information.
inner_consistent
Returns set of nodes (branches) to follow during tree search.
The SQL declaration of the function must look like this:
CREATE FUNCTION my_inner_consistent(internal, internal) RETURNS void ...
The first argument is a pointer to a spgInnerConsistentIn C struct, containing input data for the function. The second argument is a pointer to a spgInnerConsistentOut C struct, which the function must fill with result data.
typedef struct spgInnerConsistentIn { ScanKey scankeys; /* array of operators and comparison values */ int nkeys; /* length of array */ Datum reconstructedValue; /* value reconstructed at parent */ 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 */ } spgInnerConsistentOut;
The array scankeys, of length
nkeys, describes the index search
condition(s). These conditions are combined with AND — only index
entries that satisfy all of them are interesting. (Note that
nkeys = 0 implies that all index
entries satisfy the query.) Usually the consistent function only
cares about the sk_strategy and
sk_argument fields of each array
entry, which respectively give the indexable operator and
comparison value. In particular it is not necessary to check
sk_flags to see if the comparison
value is NULL, because the SP-GiST core code will filter out such
conditions. reconstructedValue is the
value reconstructed for the parent tuple; it is (Datum) 0 at the root level or if the inner_consistent
function did not provide a value
at the parent level. level is the
current inner tuple's level, starting at zero for the root level.
returnData is true if reconstructed data is required for this
query; this will only be so if the config
function asserted canReturnData. 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 (see Section
56.3.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, and nodeLabels 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, and nodeNumbers must be set to an array of their
indexes. If the operator class keeps track of levels, set
levelAdds 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, set reconstructedValues to an array of the values
reconstructed for each child node to be visited; otherwise, leave
reconstructedValues as NULL. Note that
the inner_consistent
function is
responsible for palloc'ing the nodeNumbers, levelAdds and reconstructedValues arrays.
leaf_consistent
Returns true if a leaf tuple satisfies a query.
The SQL declaration of the function must look like this:
CREATE FUNCTION my_leaf_consistent(internal, internal) RETURNS bool ...
The first argument is a pointer to a spgLeafConsistentIn C struct, containing input data for the function. The second argument is a pointer to a spgLeafConsistentOut C struct, which the function must fill with result data.
typedef struct spgLeafConsistentIn { ScanKey scankeys; /* array of operators and comparison values */ int nkeys; /* length of array */ Datum reconstructedValue; /* value reconstructed at parent */ 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 */ } spgLeafConsistentOut;
The array scankeys, of length
nkeys, describes the index search
condition(s). These conditions are combined with AND — only index
entries that satisfy all of them satisfy the query. (Note that
nkeys = 0 implies that all index
entries satisfy the query.) Usually the consistent function only
cares about the sk_strategy and
sk_argument fields of each array
entry, which respectively give the indexable operator and
comparison value. In particular it is not necessary to check
sk_flags to see if the comparison
value is NULL, because the SP-GiST core code will filter out such
conditions. reconstructedValue is the
value reconstructed for the parent tuple; it is (Datum) 0 at the root level or if the inner_consistent
function did not provide a value
at the parent level. level is the
current leaf tuple's level, starting at zero for the root level.
returnData is true if reconstructed data is required for this
query; this will only be so if the config
function asserted canReturnData. leafDatum is the key value stored in the current
leaf tuple.
The function must return true if the leaf tuple matches the query, or false if not. In the true case, if returnData is true then leafValue must be set to the value originally supplied to be indexed for this leaf tuple. Also, recheck may be set to true if the match is uncertain and so the operator(s) must be re-applied to the actual heap tuple to verify the match.
All the SP-GiST support methods are normally called in a
short-lived memory context; that is, CurrentMemoryContext will be reset after processing
of each tuple. It is therefore not very important to worry about
pfree'ing everything you palloc. (The config
method is an exception: it should try to
avoid leaking memory. But usually the config
method need do nothing but assign
constants into the passed parameter struct.)
If the indexed column is of a collatable data type, the index
collation will be passed to all the support methods, using the
standard PG_GET_COLLATION()
mechanism.