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.49.0