From 8daeb5ddd698f661eb118f8e874e7c68cfd6ae09 Mon Sep 17 00:00:00 2001 From: Tom Lane Date: Sat, 17 Dec 2011 16:41:16 -0500 Subject: Add SP-GiST (space-partitioned GiST) index access method. SP-GiST is comparable to GiST in flexibility, but supports non-balanced partitioned search structures rather than balanced trees. As described at PGCon 2011, this new indexing structure can beat GiST in both index build time and query speed for search problems that it is well matched to. There are a number of areas that could still use improvement, but at this point the code seems committable. Teodor Sigaev and Oleg Bartunov, with considerable revisions by Tom Lane --- doc/src/sgml/acronyms.sgml | 9 + doc/src/sgml/filelist.sgml | 1 + doc/src/sgml/indices.sgml | 35 +- doc/src/sgml/mvcc.sgml | 8 +- doc/src/sgml/postgres.sgml | 1 + doc/src/sgml/ref/alter_opfamily.sgml | 8 +- doc/src/sgml/ref/create_index.sgml | 51 ++- doc/src/sgml/ref/create_opclass.sgml | 4 +- doc/src/sgml/ref/create_table.sgml | 3 +- doc/src/sgml/spgist.sgml | 706 +++++++++++++++++++++++++++++++++++ doc/src/sgml/xindex.sgml | 118 +++++- 11 files changed, 892 insertions(+), 52 deletions(-) create mode 100644 doc/src/sgml/spgist.sgml (limited to 'doc/src') diff --git a/doc/src/sgml/acronyms.sgml b/doc/src/sgml/acronyms.sgml index 8f6752f05d7..38f111ef9d9 100644 --- a/doc/src/sgml/acronyms.sgml +++ b/doc/src/sgml/acronyms.sgml @@ -569,6 +569,15 @@ + + SP-GiST + + + Space-Partitioned Generalized Search Tree + + + + SQL diff --git a/doc/src/sgml/filelist.sgml b/doc/src/sgml/filelist.sgml index 7a698e59b3e..b96dd656ad3 100644 --- a/doc/src/sgml/filelist.sgml +++ b/doc/src/sgml/filelist.sgml @@ -82,6 +82,7 @@ + diff --git a/doc/src/sgml/indices.sgml b/doc/src/sgml/indices.sgml index 2dedb153c06..3a46b96a9d2 100644 --- a/doc/src/sgml/indices.sgml +++ b/doc/src/sgml/indices.sgml @@ -116,7 +116,7 @@ CREATE INDEX test1_id_index ON test1 (id); PostgreSQL provides several index types: - B-tree, Hash, GiST and GIN. Each index type uses a different + B-tree, Hash, GiST, SP-GiST and GIN. Each index type uses a different algorithm that is best suited to different types of queries. By default, the CREATE INDEX command creates B-tree indexes, which fit the most common situations. @@ -253,6 +253,37 @@ SELECT * FROM places ORDER BY location <-> point '(101,456)' LIMIT 10; to do this is again dependent on the particular operator class being used. + + + index + SP-GiST + + + SP-GiST + index + + SP-GiST indexes, like GiST indexes, offer an infrastructure that supports + various kinds of searches. SP-GiST permits implementation of a wide range + of different non-balanced disk-based data structures, such as quadtrees, + k-d trees, and suffix trees (tries). As an example, the standard distribution of + PostgreSQL includes SP-GiST operator classes + for two-dimensional points, which support indexed + queries using these operators: + + + << + >> + ~= + <@ + <^ + >^ + + + (See for the meaning of + these operators.) + For more information see . + + index @@ -263,7 +294,7 @@ SELECT * FROM places ORDER BY location <-> point '(101,456)' LIMIT 10; index GIN indexes are inverted indexes which can handle values that contain more - than one key, arrays for example. Like GiST, GIN can support + than one key, arrays for example. Like GiST and SP-GiST, GIN can support many different user-defined indexing strategies and the particular operators with which a GIN index can be used vary depending on the indexing strategy. diff --git a/doc/src/sgml/mvcc.sgml b/doc/src/sgml/mvcc.sgml index b311d240109..96e160974ba 100644 --- a/doc/src/sgml/mvcc.sgml +++ b/doc/src/sgml/mvcc.sgml @@ -525,7 +525,7 @@ ERROR: could not serialize access due to concurrent update As an example, consider a table mytab, initially containing: - class | value + class | value -------+------- 1 | 10 1 | 20 @@ -1460,7 +1460,7 @@ SELECT pg_advisory_lock(q.id) FROM - B-tree and GiST indexes + B-tree, GiST and SP-GiST indexes @@ -1510,8 +1510,8 @@ SELECT pg_advisory_lock(q.id) FROM applications; since they also have more features than hash indexes, they are the recommended index type for concurrent applications that need to index scalar data. When dealing with - non-scalar data, B-trees are not useful, and GiST or GIN indexes should - be used instead. + non-scalar data, B-trees are not useful, and GiST, SP-GiST or GIN + indexes should be used instead. diff --git a/doc/src/sgml/postgres.sgml b/doc/src/sgml/postgres.sgml index ac1da22be89..7e80265eb35 100644 --- a/doc/src/sgml/postgres.sgml +++ b/doc/src/sgml/postgres.sgml @@ -242,6 +242,7 @@ &geqo; &indexam; &gist; + &spgist; &gin; &storage; &bki; diff --git a/doc/src/sgml/ref/alter_opfamily.sgml b/doc/src/sgml/ref/alter_opfamily.sgml index c95df95fa27..aad968d284a 100644 --- a/doc/src/sgml/ref/alter_opfamily.sgml +++ b/doc/src/sgml/ref/alter_opfamily.sgml @@ -144,8 +144,8 @@ ALTER OPERATOR FAMILY name USING op_type since the function's input data type(s) are always the correct ones to use. For B-tree sort - support functions and all functions in GiST and GIN operator classes, - it is necessary to specify the operand data type(s) the function + support functions and all functions in GiST, SP-GiST and GIN operator + classes, it is necessary to specify the operand data type(s) the function is to be used with. @@ -245,8 +245,8 @@ ALTER OPERATOR FAMILY name USING name PostgreSQL provides the index methods - B-tree, hash, GiST, and GIN. Users can also define their own index + B-tree, hash, GiST, SP-GiST, and GIN. Users can also define their own index methods, but that is fairly complicated. @@ -154,8 +154,8 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ name The name of the index method to be used. Choices are btree, hash, - gist, and gin. The - default method is btree. + gist, spgist and gin. + The default method is btree. @@ -281,12 +281,11 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ name The optional WITH clause specifies storage parameters for the index. Each index method has its own set of allowed - storage parameters. The B-tree, hash and GiST index methods all accept a - single parameter: + storage parameters. The B-tree, hash, GiST and SP-GiST index methods all + accept this parameter: - FILLFACTOR @@ -307,7 +306,25 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ name + + + + GiST indexes additionally accept this parameter: + + + + BUFFERING + + + Determines whether the buffering build technique described in + is used to build the index. With + OFF it is disabled, with ON it is enabled, and + with AUTO it is initially disabled, but turned on + on-the-fly once the index size reaches . The default is AUTO. + + + @@ -315,7 +332,6 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ name - FASTUPDATE @@ -339,27 +355,6 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ name - - - - GiST indexes additionally accept parameter: - - - - - - BUFFERING - - - Determines whether the buffering build technique described in - is used to build the index. With - OFF it is disabled, with ON it is enabled, and - with AUTO it is initially disabled, but turned on - on-the-fly once the index size reaches . The default is AUTO. - - - - diff --git a/doc/src/sgml/ref/create_opclass.sgml b/doc/src/sgml/ref/create_opclass.sgml index 78072d9f3c0..81b9e538af1 100644 --- a/doc/src/sgml/ref/create_opclass.sgml +++ b/doc/src/sgml/ref/create_opclass.sgml @@ -172,7 +172,7 @@ CREATE OPERATOR CLASS name [ DEFAUL the input data type(s) of the function (for B-tree comparison functions and hash functions) or the class's data type (for B-tree sort support functions and all - functions in GiST and GIN operator classes). These defaults + functions in GiST, SP-GiST and GIN operator classes). These defaults are correct, and so op_type need not be specified in FUNCTION clauses, except for the case of a B-tree sort @@ -232,7 +232,7 @@ CREATE OPERATOR CLASS name [ DEFAUL The data type actually stored in the index. Normally this is the same as the column data type, but some index methods - (currently GIN and GiST) allow it to be different. The + (currently GiST and GIN) allow it to be different. The STORAGE clause must be omitted unless the index method allows a different type to be used. diff --git a/doc/src/sgml/ref/create_table.sgml b/doc/src/sgml/ref/create_table.sgml index faff45900c4..d7b0fcf73a6 100644 --- a/doc/src/sgml/ref/create_table.sgml +++ b/doc/src/sgml/ref/create_table.sgml @@ -540,7 +540,8 @@ CREATE [ [ GLOBAL | LOCAL ] { TEMPORARY | TEMP } | UNLOGGED ] TABLE [ IF NOT EXI cannot be used. Although it's allowed, there is little point in using B-tree or hash indexes with an exclusion constraint, because this does nothing that an ordinary unique constraint doesn't do better. - So in practice the access method will always be GiST. + So in practice the access method will always be GiST or + SP-GiST. diff --git a/doc/src/sgml/spgist.sgml b/doc/src/sgml/spgist.sgml new file mode 100644 index 00000000000..70e0e9ff503 --- /dev/null +++ b/doc/src/sgml/spgist.sgml @@ -0,0 +1,706 @@ + + + +SP-GiST Indexes + + + index + SP-GiST + + + + Introduction + + + SP-GiST is an abbreviation for space-partitioned + GiST. SP-GiST supports partitioned + search trees, which facilitate development of a wide range of different + non-balanced data structures, such as quad-trees, k-d trees, and suffix + trees (tries). The common feature of these structures is that they + repeatedly divide the search space into partitions that need not be + of equal size. Searches that are well matched to the partitioning rule + can be very fast. + + + + These popular data structures were originally developed for in-memory + usage. In main memory, they are usually designed as a set of dynamically + allocated nodes linked by pointers. This is not suitable for direct + storing on disk, since these chains of pointers can be rather long which + would require too many disk accesses. In contrast, disk-based data + structures should have a high fanout to minimize I/O. The challenge + addressed by SP-GiST is to map search tree nodes to + disk pages in such a way that a search need access only a few disk pages, + even if it traverses many nodes. + + + + Like GiST, SP-GiST is meant to allow + the development of custom data types with the appropriate access methods, + by an expert in the domain of the data type, rather than a database expert. + + + + Some of the information here is derived from Purdue University's + SP-GiST Indexing Project + web site. + The SP-GiST implementation in + PostgreSQL is primarily maintained by Teodor + Sigaev and Oleg Bartunov, and there is more information on their + + web site. + + + + + + Extensibility + + + 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 suffix 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 suffix 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. + + + + 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 datatype 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 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 opclasses, 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. + 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 ). + + + + + + 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 ). + 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 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 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 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 +{ + StrategyNumber strategy; /* operator strategy number */ + Datum query; /* operator's RHS value */ + + Datum reconstructedValue; /* value reconstructed at parent */ + 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) */ +} 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; + + + strategy and + query describe the index search condition. + 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. + 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 ). + 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 +{ + StrategyNumber strategy; /* operator strategy number */ + Datum query; /* operator's RHS value */ + + Datum reconstructedValue; /* value reconstructed at parent */ + int level; /* current level (counting from zero) */ + + Datum leafDatum; /* datum in leaf tuple */ +} spgLeafConsistentIn; + +typedef struct spgLeafConsistentOut +{ + bool recheck; /* set true if operator must be rechecked */ +} spgLeafConsistentOut; + + + strategy and + query define the index search condition. + 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. + 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, + recheck may be set to true if the match + is uncertain and so the operator 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. + + + + + + Implementation + + + This section covers implementation details and other tricks that are + useful for implementors of SP-GiST operator classes to + know. + + + + SP-GiST Limits + + + 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 suffix + 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 set + longValuesOK to TRUE only if it is prepared to arrange for + this to happen. Otherwise, the SP-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 + tuple must divide the set of leaf values into more than one + node group. If the operator class's picksplit function + fails to do that, the SP-GiST core resorts to + extraordinary measures described in . + + + + + SP-GiST Without Node Labels + + + 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), the picksplit + function can return NULL for the nodeLabels array. + This will in turn result in nodeLabels being NULL during + subsequent calls to choose and inner_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 + for choose to return spgAddNode, since the set + of nodes is supposed to be fixed in such cases. Also, there is no + provision for generating an unlabeled node in spgSplitTuple + actions, since it is expected that an spgAddNode action will + be needed as well. + + + + + <quote>All-the-same</> Inner Tuples + + + The SP-GiST core can override the results of the + operator class's picksplit function when + picksplit 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) + that picksplit gave to the one node it did use, and the + leaf values are divided at random among these equivalent nodes. + The allTheSame flag is set on the inner tuple to warn the + choose and inner_consistent functions that the + tuple does not have the node set that they might otherwise expect. + + + + When dealing with an allTheSame tuple, a choose + result of spgMatchNode is interpreted to mean that the new + value can be assigned to any of the equivalent nodes; the core code will + ignore the supplied nodeN value and descend into one + of the nodes at random (so as to keep the tree balanced). It is an + error for choose to return spgAddNode, since + that would make the nodes not all equivalent; the + spgSplitTuple action must be used if the value to be inserted + doesn't match the existing nodes. + + + + When dealing with an allTheSame tuple, the + inner_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 the inner_consistent function normally + assumes about the meaning of the nodes. + + + + + + + Examples + + + The PostgreSQL source distribution includes + several examples of index operator classes for + SP-GiST. The core system currently provides suffix + trees over text columns and two types of trees over points: quad-tree and + k-d tree. Look into src/backend/access/spgist/ to see the + code. + + + + + diff --git a/doc/src/sgml/xindex.sgml b/doc/src/sgml/xindex.sgml index f3a9783e5c9..806b35824e4 100644 --- a/doc/src/sgml/xindex.sgml +++ b/doc/src/sgml/xindex.sgml @@ -237,12 +237,59 @@ - GIN indexes are similar to GiST indexes in flexibility: they don't have a - fixed set of strategies. Instead the support routines of each operator + SP-GiST indexes are similar to GiST indexes in flexibility: they don't have + a fixed set of strategies. Instead the support routines of each operator class interpret the strategy numbers according to the operator class's definition. As an example, the strategy numbers used by the built-in - operator classes for arrays are - shown in . + operator classes for points are shown in . + + + + SP-GiST Point Strategies + + + + Operation + Strategy Number + + + + + strictly left of + 1 + + + strictly right of + 5 + + + same + 6 + + + contained by + 8 + + + strictly below + 10 + + + strictly above + 11 + + + +
+ + + GIN indexes are similar to GiST and SP-GiST indexes, in that they don't + have a fixed set of strategies either. Instead the support routines of + each operator class interpret the strategy numbers according to the + operator class's definition. As an example, the strategy numbers used by + the built-in operator classes for arrays are shown in + . @@ -434,6 +481,54 @@
+ + SP-GiST indexes require five support functions, as + shown in . + (For more information see .) + + + + SP-GiST Support Functions + + + + Function + Description + Support Number + + + + + config + provide basic information about the operator class + 1 + + + choose + determine how to insert a new value into an inner tuple + 2 + + + picksplit + determine how to partition a set of values + 3 + + + inner_consistent + determine which sub-partitions need to be searched for a + query + 4 + + + leaf_consistent + determine whether key satisfies the + query qualifier + 5 + + + +
+ GIN indexes require four support functions, with an optional fifth, as shown in . @@ -495,9 +590,9 @@ of the comparison function for B-trees, a signed integer. The number and types of the arguments to each support function are likewise dependent on the index method. For B-tree and hash the comparison and - hashing support functions - take the same input data types as do the operators included in the operator - class, but this is not the case for most GIN and GiST support functions. + hashing support functions take the same input data types as do the + operators included in the operator class, but this is not the case for + most GiST, SP-GiST, and GIN support functions. @@ -876,9 +971,10 @@ ALTER OPERATOR FAMILY integer_ops USING btree ADD - GIN and GiST indexes do not have any explicit notion of cross-data-type - operations. The set of operators supported is just whatever the primary - support functions for a given operator class can handle. + GiST, SP-GiST, and GIN indexes do not have any explicit notion of + cross-data-type operations. The set of operators supported is just + whatever the primary support functions for a given operator class can + handle. @@ -1045,7 +1141,7 @@ SELECT * FROM table WHERE integer_column < 4; the index is guaranteed to return all the required rows, plus perhaps some additional rows, which can be eliminated by performing the original operator invocation. The index methods that support lossy searches - (currently, GiST and GIN) allow the support functions of individual + (currently, GiST, SP-GiST and GIN) allow the support functions of individual operator classes to set the recheck flag, and so this is essentially an operator-class feature. -- cgit v1.2.3