From 9100f534030c543f95c11a2f9c5f1571f55999b9 Mon Sep 17 00:00:00 2001 From: Tom Lane <tgl@sss.pgh.pa.us> 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 @@ </row> <row> <entry><literal>box_ops</></entry> - <entry>box</entry> + <entry><type>box</></entry> <entry> <literal><<</> <literal>&<</> @@ -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 <firstterm>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 <firstterm>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 <firstterm>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 <firstterm>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 <xref linkend="spgist-null-labels">.) + Optionally, an inner tuple can have a <firstterm>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 <acronym>SP-GiST</acronym> 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 + <firstterm>traverse values</>) during a tree descent. </para> <note> @@ -492,9 +496,8 @@ typedef struct spgPickSplitOut <structfield>prefixDatum</> to the prefix value. Set <structfield>nNodes</> to indicate the number of nodes that the new inner tuple will contain, and - set <structfield>nodeLabels</> to an array of their label values. - (If the nodes do not require labels, set <structfield>nodeLabels</> - to NULL; see <xref linkend="spgist-null-labels"> for details.) + set <structfield>nodeLabels</> to an array of their label values, + or to NULL if node labels are not required. Set <structfield>mapTuplesToNodes</> to an array that gives the index (from zero) of the node that each leaf tuple should be assigned to. Set <structfield>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; </programlisting> @@ -599,6 +601,11 @@ typedef struct spgInnerConsistentOut parent tuple; it is <literal>(Datum) 0</> at the root level or if the <function>inner_consistent</> function did not provide a value at the parent level. + <structfield>traversalValue</> is a pointer to any traverse data + passed down from the previous call of <function>inner_consistent</> + on the parent index tuple, or NULL at the root level. + <structfield>traversalMemoryContext</> is the memory context in which + to store output traverse values (see below). <structfield>level</> is the current inner tuple's level, starting at zero for the root level. <structfield>returnData</> is <literal>true</> if reconstructed data is @@ -615,9 +622,6 @@ typedef struct spgInnerConsistentOut inner tuple, and <structfield>nodeLabels</> is an array of their label values, or NULL if the nodes do not have labels. - <structfield>traversalValue</> is a pointer to data that - <function>inner_consistent</> gets when called on child nodes from an - outer call of <function>inner_consistent</> on parent nodes. </para> <para> @@ -633,17 +637,20 @@ typedef struct spgInnerConsistentOut <structfield>reconstructedValues</> to an array of the values reconstructed for each child node to be visited; otherwise, leave <structfield>reconstructedValues</> as NULL. + If it is desired to pass down additional out-of-band information + (<quote>traverse values</>) to lower levels of the tree search, + set <structfield>traversalValues</> to an array of the appropriate + traverse values, one for each child node to be visited; otherwise, + leave <structfield>traversalValues</> as NULL. Note that the <function>inner_consistent</> function is responsible for palloc'ing the - <structfield>nodeNumbers</>, <structfield>levelAdds</> and - <structfield>reconstructedValues</> arrays. - Sometimes accumulating some information is needed, while - descending from parent to child node was happened. In this case - <structfield>traversalValues</> array keeps pointers to - specific data you need to accumulate for every child node. - Memory for <structfield>traversalValues</> should be allocated in - the default context, but each element of it should be allocated in - <structfield>traversalMemoryContext</>. + <structfield>nodeNumbers</>, <structfield>levelAdds</>, + <structfield>reconstructedValues</>, and + <structfield>traversalValues</> arrays in the current memory context. + However, any output traverse values pointed to by + the <structfield>traversalValues</> array should be allocated + in <structfield>traversalMemoryContext</>. + Each traverse value must be a single palloc'd chunk. </para> </listitem> </varlistentry> @@ -700,6 +707,9 @@ typedef struct spgLeafConsistentOut parent tuple; it is <literal>(Datum) 0</> at the root level or if the <function>inner_consistent</> function did not provide a value at the parent level. + <structfield>traversalValue</> is a pointer to any traverse data + passed down from the previous call of <function>inner_consistent</> + on the parent index tuple, or NULL at the root level. <structfield>level</> is the current leaf tuple's level, starting at zero for the root level. <structfield>returnData</> is <literal>true</> if reconstructed data is @@ -859,11 +869,10 @@ typedef struct spgLeafConsistentOut <para> The <productname>PostgreSQL</productname> source distribution includes - several examples of index operator classes for - <acronym>SP-GiST</acronym>. 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 <filename>src/backend/access/spgist/</> to see the - code. + several examples of index operator classes for <acronym>SP-GiST</acronym>, + as described in <xref linkend="spgist-builtin-opclasses-table">. Look + into <filename>src/backend/access/spgist/</> + and <filename>src/backend/utils/adt/</> to see the code. </para> </sect1> -- 2.40.0