From 9100f534030c543f95c11a2f9c5f1571f55999b9 Mon Sep 17 00:00:00 2001 From: Tom Lane Date: Mon, 29 Aug 2016 08:57:34 -0400 Subject: [PATCH] Doc: improve 9.6 description of SP-GiST traverse values. Sync relevant parts of commit d2ddee63b back to 9.6 branch. --- doc/src/sgml/spgist.sgml | 65 +++++++++++++++++++++++----------------- 1 file changed, 37 insertions(+), 28 deletions(-) diff --git a/doc/src/sgml/spgist.sgml b/doc/src/sgml/spgist.sgml index f40c790612..7ec1d0a0db 100644 --- a/doc/src/sgml/spgist.sgml +++ b/doc/src/sgml/spgist.sgml @@ -114,7 +114,7 @@ box_ops - box + box << &< @@ -183,11 +183,14 @@ 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, + A node contains a downlink that leads either to another, lower-level inner + tuple, or to a short list of leaf tuples that all lie on the same index page. + Each node normally 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 + value. (Alternatively, an operator class can omit the node labels, if it + works with a fixed set of nodes for all inner tuples; + see .) + 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; @@ -202,7 +205,8 @@ 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. + value when that is needed, and for passing down additional data (called + traverse values) during a tree descent. @@ -492,9 +496,8 @@ typedef struct spgPickSplitOut 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 nodeLabels to an array of their label values, + or to NULL if node labels are not required. 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 @@ -561,7 +564,7 @@ typedef struct spgInnerConsistentIn Datum reconstructedValue; /* value reconstructed at parent */ void *traversalValue; /* opclass-specific traverse value */ - MemoryContext traversalMemoryContext; + MemoryContext traversalMemoryContext; /* put new traverse values here */ int level; /* current level (counting from zero) */ bool returnData; /* original data must be returned? */ @@ -580,7 +583,6 @@ typedef struct spgInnerConsistentOut int *levelAdds; /* increment level by this much for each */ Datum *reconstructedValues; /* associated reconstructed values */ void **traversalValues; /* opclass-specific traverse values */ - } spgInnerConsistentOut; @@ -599,6 +601,11 @@ typedef struct spgInnerConsistentOut 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. + traversalValue is a pointer to any traverse data + passed down from the previous call of inner_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 is true if reconstructed data is @@ -615,9 +622,6 @@ typedef struct spgInnerConsistentOut inner tuple, and nodeLabels is an array of their label values, or NULL if the nodes do not have labels. - traversalValue is a pointer to data that - inner_consistent gets when called on child nodes from an - outer call of inner_consistent on parent nodes. @@ -633,17 +637,20 @@ typedef struct spgInnerConsistentOut reconstructedValues to an array of the values reconstructed for each child node to be visited; otherwise, leave reconstructedValues as NULL. + If it is desired to pass down additional out-of-band information + (traverse values) to lower levels of the tree search, + set traversalValues to an array of the appropriate + traverse values, one for each child node to be visited; otherwise, + leave traversalValues as NULL. Note that the inner_consistent function is responsible for palloc'ing the - nodeNumbers, levelAdds and - reconstructedValues arrays. - Sometimes accumulating some information is needed, while - descending from parent to child node was happened. In this case - traversalValues array keeps pointers to - specific data you need to accumulate for every child node. - Memory for traversalValues should be allocated in - the default context, but each element of it should be allocated in - traversalMemoryContext. + nodeNumbers, levelAdds, + reconstructedValues, and + traversalValues arrays in the current memory context. + However, any output traverse values pointed to by + the traversalValues array should be allocated + in traversalMemoryContext. + Each traverse value must be a single palloc'd chunk. @@ -700,6 +707,9 @@ typedef struct spgLeafConsistentOut 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. + traversalValue is a pointer to any traverse data + passed down from the previous call of inner_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 is true if reconstructed data is @@ -859,11 +869,10 @@ typedef struct spgLeafConsistentOut The PostgreSQL source distribution includes - several examples of index operator classes for - SP-GiST. The core system currently provides radix - 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. + several examples of index operator classes for SP-GiST, + as described in . Look + into src/backend/access/spgist/ + and src/backend/utils/adt/ to see the code. -- 2.40.0