summaryrefslogtreecommitdiffstats
path: root/doc/src/sgml/html/spgist-extensibility.html
diff options
context:
space:
mode:
Diffstat (limited to 'doc/src/sgml/html/spgist-extensibility.html')
-rw-r--r--doc/src/sgml/html/spgist-extensibility.html597
1 files changed, 597 insertions, 0 deletions
diff --git a/doc/src/sgml/html/spgist-extensibility.html b/doc/src/sgml/html/spgist-extensibility.html
new file mode 100644
index 0000000..184f57b
--- /dev/null
+++ b/doc/src/sgml/html/spgist-extensibility.html
@@ -0,0 +1,597 @@
+<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>65.3. Extensibility</title><link rel="stylesheet" type="text/css" href="stylesheet.css" /><link rev="made" href="pgsql-docs@lists.postgresql.org" /><meta name="generator" content="DocBook XSL Stylesheets V1.79.1" /><link rel="prev" href="spgist-builtin-opclasses.html" title="65.2. Built-in Operator Classes" /><link rel="next" href="spgist-implementation.html" title="65.4. Implementation" /></head><body id="docContent" class="container-fluid col-10"><div xmlns="http://www.w3.org/TR/xhtml1/transitional" class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="5" align="center">65.3. Extensibility</th></tr><tr><td width="10%" align="left"><a accesskey="p" href="spgist-builtin-opclasses.html" title="65.2. Built-in Operator Classes">Prev</a> </td><td width="10%" align="left"><a accesskey="u" href="spgist.html" title="Chapter 65. SP-GiST Indexes">Up</a></td><th width="60%" align="center">Chapter 65. SP-GiST Indexes</th><td width="10%" align="right"><a accesskey="h" href="index.html" title="PostgreSQL 13.4 Documentation">Home</a></td><td width="10%" align="right"> <a accesskey="n" href="spgist-implementation.html" title="65.4. Implementation">Next</a></td></tr></table><hr></hr></div><div class="sect1" id="SPGIST-EXTENSIBILITY"><div class="titlepage"><div><div><h2 class="title" style="clear: both">65.3. Extensibility</h2></div></div></div><p>
+ <acronym class="acronym">SP-GiST</acronym> 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 <acronym class="acronym">SP-GiST</acronym> core
+ is responsible for efficient disk mapping and searching the tree structure.
+ It also takes care of concurrency and logging considerations.
+ </p><p>
+ Leaf tuples of an <acronym class="acronym">SP-GiST</acronym> 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.
+ </p><p>
+ Inner tuples are more complex, since they are branching points in the
+ search tree. Each inner tuple contains a set of one or more
+ <em class="firstterm">nodes</em>, which represent groups of similar leaf values.
+ 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 <em class="firstterm">label</em> that describes it; for example,
+ in a radix tree the node label could be the next character of the string
+ value. (Alternatively, an operator class can omit the node labels, if it
+ works with a fixed set of nodes for all inner tuples;
+ see <a class="xref" href="spgist-implementation.html#SPGIST-NULL-LABELS" title="65.4.2. SP-GiST Without Node Labels">Section 65.4.2</a>.)
+ Optionally, an inner tuple can have a <em class="firstterm">prefix</em> 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.
+ </p><p>
+ Some tree algorithms require knowledge of level (or depth) of the current
+ tuple, so the <acronym class="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, and for passing down additional data (called
+ <em class="firstterm">traverse values</em>) during a tree descent.
+ </p><div class="note"><h3 class="title">Note</h3><p>
+ The <acronym class="acronym">SP-GiST</acronym> core code takes care of null entries.
+ Although <acronym class="acronym">SP-GiST</acronym> 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 <acronym class="acronym">SP-GiST</acronym>
+ operators are strict and so cannot succeed for null values.) Null values
+ are therefore not discussed further here.
+ </p></div><p>
+ There are five user-defined methods that an index operator class for
+ <acronym class="acronym">SP-GiST</acronym> must provide, and two are optional. All five
+ mandatory methods follow the convention of accepting two <code class="type">internal</code>
+ 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 mandatory methods just
+ return <code class="type">void</code>, since all their results appear in the output struct; but
+ <code class="function">leaf_consistent</code> returns a <code class="type">boolean</code> 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 optional sixth method <code class="function">compress</code>
+ accepts a <code class="type">datum</code> to be indexed as the only argument and returns a value suitable
+ for physical storage in a leaf tuple. The optional seventh method
+ <code class="function">options</code> accepts an <code class="type">internal</code> pointer to a C struct, where
+ opclass-specific parameters should be placed, and returns <code class="type">void</code>.
+ </p><p>
+ The five mandatory user-defined methods are:
+ </p><div class="variablelist"><dl class="variablelist"><dt><span class="term"><code class="function">config</code></span></dt><dd><p>
+ Returns static information about the index implementation, including
+ the data type OIDs of the prefix and node label data types.
+ </p><p>
+ The <acronym class="acronym">SQL</acronym> declaration of the function must look like this:
+</p><pre class="programlisting">
+CREATE FUNCTION my_config(internal, internal) RETURNS void ...
+</pre><p>
+ The first argument is a pointer to a <code class="structname">spgConfigIn</code>
+ C struct, containing input data for the function.
+ The second argument is a pointer to a <code class="structname">spgConfigOut</code>
+ C struct, which the function must fill with result data.
+</p><pre class="programlisting">
+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 */
+ Oid leafType; /* Data type of leaf-tuple values */
+ bool canReturnData; /* Opclass can reconstruct original data */
+ bool longValuesOK; /* Opclass can cope with values &gt; 1 page */
+} spgConfigOut;
+</pre><p>
+
+ <code class="structfield">attType</code> 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.
+ </p><p>
+ For operator classes that do not use prefixes,
+ <code class="structfield">prefixType</code> can be set to <code class="literal">VOIDOID</code>.
+ Likewise, for operator classes that do not use node labels,
+ <code class="structfield">labelType</code> can be set to <code class="literal">VOIDOID</code>.
+ <code class="structfield">canReturnData</code> should be set true if the operator class
+ is capable of reconstructing the originally-supplied index value.
+ <code class="structfield">longValuesOK</code> should be set true only when the
+ <code class="structfield">attType</code> is of variable length and the operator
+ class is capable of segmenting long values by repeated suffixing
+ (see <a class="xref" href="spgist-implementation.html#SPGIST-LIMITS" title="65.4.1. SP-GiST Limits">Section 65.4.1</a>).
+ </p><p>
+ <code class="structfield">leafType</code> is typically the same as
+ <code class="structfield">attType</code>. For the reasons of backward
+ compatibility, method <code class="function">config</code> can
+ leave <code class="structfield">leafType</code> uninitialized; that would
+ give the same effect as setting <code class="structfield">leafType</code> equal
+ to <code class="structfield">attType</code>. When <code class="structfield">attType</code>
+ and <code class="structfield">leafType</code> are different, then optional
+ method <code class="function">compress</code> must be provided.
+ Method <code class="function">compress</code> is responsible
+ for transformation of datums to be indexed from <code class="structfield">attType</code>
+ to <code class="structfield">leafType</code>.
+ Note: both consistent functions will get <code class="structfield">scankeys</code>
+ unchanged, without transformation using <code class="function">compress</code>.
+ </p></dd><dt><span class="term"><code class="function">choose</code></span></dt><dd><p>
+ Chooses a method for inserting a new value into an inner tuple.
+ </p><p>
+ The <acronym class="acronym">SQL</acronym> declaration of the function must look like this:
+</p><pre class="programlisting">
+CREATE FUNCTION my_choose(internal, internal) RETURNS void ...
+</pre><p>
+ The first argument is a pointer to a <code class="structname">spgChooseIn</code>
+ C struct, containing input data for the function.
+ The second argument is a pointer to a <code class="structname">spgChooseOut</code>
+ C struct, which the function must fill with result data.
+</p><pre class="programlisting">
+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 upper-level inner tuple with one child tuple */
+ bool prefixHasPrefix; /* tuple should have a prefix? */
+ Datum prefixPrefixDatum; /* if so, its value */
+ int prefixNNodes; /* number of nodes */
+ Datum *prefixNodeLabels; /* their labels (or NULL for
+ * no labels) */
+ int childNodeN; /* which node gets child tuple */
+
+ /* 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;
+</pre><p>
+
+ <code class="structfield">datum</code> is the original datum of
+ <code class="structname">spgConfigIn</code>.<code class="structfield">attType</code>
+ type that was to be inserted into the index.
+ <code class="structfield">leafDatum</code> is a value of
+ <code class="structname">spgConfigOut</code>.<code class="structfield">leafType</code>
+ type, which is initially a result of method
+ <code class="function">compress</code> applied to <code class="structfield">datum</code>
+ when method <code class="function">compress</code> is provided, or the same value as
+ <code class="structfield">datum</code> otherwise.
+ <code class="structfield">leafDatum</code> can change at lower levels of the tree
+ if the <code class="function">choose</code> or <code class="function">picksplit</code>
+ methods change it. When the insertion search reaches a leaf page,
+ the current value of <code class="structfield">leafDatum</code> is what will be stored
+ in the newly created leaf tuple.
+ <code class="structfield">level</code> is the current inner tuple's level, starting at
+ zero for the root level.
+ <code class="structfield">allTheSame</code> is true if the current inner tuple is
+ marked as containing multiple equivalent nodes
+ (see <a class="xref" href="spgist-implementation.html#SPGIST-ALL-THE-SAME" title="65.4.3. “All-the-Same” Inner Tuples">Section 65.4.3</a>).
+ <code class="structfield">hasPrefix</code> is true if the current inner tuple contains
+ a prefix; if so,
+ <code class="structfield">prefixDatum</code> is its value.
+ <code class="structfield">nNodes</code> is the number of child nodes contained in the
+ inner tuple, and
+ <code class="structfield">nodeLabels</code> is an array of their label values, or
+ NULL if there are no labels.
+ </p><p>
+ The <code class="function">choose</code> 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.
+ </p><p>
+ If the new value matches one of the existing child nodes,
+ set <code class="structfield">resultType</code> to <code class="literal">spgMatchNode</code>.
+ Set <code class="structfield">nodeN</code> to the index (from zero) of that node in
+ the node array.
+ Set <code class="structfield">levelAdd</code> to the increment in
+ <code class="structfield">level</code> caused by descending through that node,
+ or leave it as zero if the operator class does not use levels.
+ Set <code class="structfield">restDatum</code> to equal <code class="structfield">leafDatum</code>
+ 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
+ <code class="structfield">leafDatum</code> at the next level.
+ </p><p>
+ If a new child node must be added,
+ set <code class="structfield">resultType</code> to <code class="literal">spgAddNode</code>.
+ Set <code class="structfield">nodeLabel</code> to the label to be used for the new
+ node, and set <code class="structfield">nodeN</code> to the index (from zero) at which
+ to insert the node in the node array.
+ After the node has been added, the <code class="function">choose</code>
+ function will be called again with the modified inner tuple;
+ that call should result in an <code class="literal">spgMatchNode</code> result.
+ </p><p>
+ If the new value is inconsistent with the tuple prefix,
+ set <code class="structfield">resultType</code> to <code class="literal">spgSplitTuple</code>.
+ 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 downlink pointing to the new lower-level inner tuple.
+ Set <code class="structfield">prefixHasPrefix</code> to indicate whether the new
+ upper tuple should have a prefix, and if so set
+ <code class="structfield">prefixPrefixDatum</code> to the prefix value. This new
+ prefix value must be sufficiently less restrictive than the original
+ to accept the new value to be indexed.
+ Set <code class="structfield">prefixNNodes</code> to the number of nodes needed in the
+ new tuple, and set <code class="structfield">prefixNodeLabels</code> to a palloc'd array
+ holding their labels, or to NULL if node labels are not required.
+ Note that the total size of the new upper tuple must be no more
+ than the total size of the tuple it is replacing; this constrains
+ the lengths of the new prefix and new labels.
+ Set <code class="structfield">childNodeN</code> to the index (from zero) of the node
+ that will downlink to the new lower-level inner tuple.
+ Set <code class="structfield">postfixHasPrefix</code> to indicate whether the new
+ lower-level inner tuple should have a prefix, and if so set
+ <code class="structfield">postfixPrefixDatum</code> to the prefix value. The
+ combination of these two prefixes and the downlink node's label
+ (if any) 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 <code class="function">choose</code>
+ function will be called again with the replacement inner tuple.
+ That call may return an <code class="literal">spgAddNode</code> result, if no suitable
+ node was created by the <code class="literal">spgSplitTuple</code> action. Eventually
+ <code class="function">choose</code> must return <code class="literal">spgMatchNode</code> to
+ allow the insertion to descend to the next level.
+ </p></dd><dt><span class="term"><code class="function">picksplit</code></span></dt><dd><p>
+ Decides how to create a new inner tuple over a set of leaf tuples.
+ </p><p>
+ The <acronym class="acronym">SQL</acronym> declaration of the function must look like this:
+</p><pre class="programlisting">
+CREATE FUNCTION my_picksplit(internal, internal) RETURNS void ...
+</pre><p>
+ The first argument is a pointer to a <code class="structname">spgPickSplitIn</code>
+ C struct, containing input data for the function.
+ The second argument is a pointer to a <code class="structname">spgPickSplitOut</code>
+ C struct, which the function must fill with result data.
+</p><pre class="programlisting">
+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;
+</pre><p>
+
+ <code class="structfield">nTuples</code> is the number of leaf tuples provided.
+ <code class="structfield">datums</code> is an array of their datum values of
+ <code class="structname">spgConfigOut</code>.<code class="structfield">leafType</code>
+ type.
+ <code class="structfield">level</code> is the current level that all the leaf tuples
+ share, which will become the level of the new inner tuple.
+ </p><p>
+ Set <code class="structfield">hasPrefix</code> to indicate whether the new inner
+ tuple should have a prefix, and if so set
+ <code class="structfield">prefixDatum</code> to the prefix value.
+ Set <code class="structfield">nNodes</code> to indicate the number of nodes that
+ the new inner tuple will contain, and
+ set <code class="structfield">nodeLabels</code> to an array of their label values,
+ or to NULL if node labels are not required.
+ Set <code class="structfield">mapTuplesToNodes</code> to an array that gives the index
+ (from zero) of the node that each leaf tuple should be assigned to.
+ Set <code class="structfield">leafTupleDatums</code> to an array of the values to
+ be stored in the new leaf tuples (these will be the same as the
+ input <code class="structfield">datums</code> if the operator class does not modify
+ datums from one level to the next).
+ Note that the <code class="function">picksplit</code> function is
+ responsible for palloc'ing the
+ <code class="structfield">nodeLabels</code>, <code class="structfield">mapTuplesToNodes</code> and
+ <code class="structfield">leafTupleDatums</code> arrays.
+ </p><p>
+ If more than one leaf tuple is supplied, it is expected that the
+ <code class="function">picksplit</code> 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 <code class="function">picksplit</code> 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
+ <code class="literal">allTheSame</code> to signify that this has happened. The
+ <code class="function">choose</code> and <code class="function">inner_consistent</code> functions
+ must take suitable care with such inner tuples.
+ See <a class="xref" href="spgist-implementation.html#SPGIST-ALL-THE-SAME" title="65.4.3. “All-the-Same” Inner Tuples">Section 65.4.3</a> for more information.
+ </p><p>
+ <code class="function">picksplit</code> can be applied to a single leaf tuple only
+ in the case that the <code class="function">config</code> function set
+ <code class="structfield">longValuesOK</code> 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 <a class="xref" href="spgist-implementation.html#SPGIST-LIMITS" title="65.4.1. SP-GiST Limits">Section 65.4.1</a> for
+ more information.
+ </p></dd><dt><span class="term"><code class="function">inner_consistent</code></span></dt><dd><p>
+ Returns set of nodes (branches) to follow during tree search.
+ </p><p>
+ The <acronym class="acronym">SQL</acronym> declaration of the function must look like this:
+</p><pre class="programlisting">
+CREATE FUNCTION my_inner_consistent(internal, internal) RETURNS void ...
+</pre><p>
+ The first argument is a pointer to a <code class="structname">spgInnerConsistentIn</code>
+ C struct, containing input data for the function.
+ The second argument is a pointer to a <code class="structname">spgInnerConsistentOut</code>
+ C struct, which the function must fill with result data.
+
+</p><pre class="programlisting">
+typedef struct spgInnerConsistentIn
+{
+ ScanKey scankeys; /* array of operators and comparison values */
+ ScanKey orderbys; /* array of ordering operators and comparison
+ * values */
+ int nkeys; /* length of scankeys array */
+ int norderbys; /* length of orderbys array */
+
+ Datum reconstructedValue; /* value reconstructed at parent */
+ void *traversalValue; /* opclass-specific traverse value */
+ MemoryContext traversalMemoryContext; /* put new traverse values here */
+ 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 */
+ void **traversalValues; /* opclass-specific traverse values */
+ double **distances; /* associated distances */
+} spgInnerConsistentOut;
+</pre><p>
+
+ The array <code class="structfield">scankeys</code>, of length <code class="structfield">nkeys</code>,
+ describes the index search condition(s). These conditions are
+ combined with AND — only index entries that satisfy all of
+ them are interesting. (Note that <code class="structfield">nkeys</code> = 0 implies
+ that all index entries satisfy the query.) Usually the consistent
+ function only cares about the <code class="structfield">sk_strategy</code> and
+ <code class="structfield">sk_argument</code> fields of each array entry, which
+ respectively give the indexable operator and comparison value.
+ In particular it is not necessary to check <code class="structfield">sk_flags</code> to
+ see if the comparison value is NULL, because the SP-GiST core code
+ will filter out such conditions.
+ The array <code class="structfield">orderbys</code>, of length <code class="structfield">norderbys</code>,
+ describes ordering operators (if any) in the same manner.
+ <code class="structfield">reconstructedValue</code> is the value reconstructed for the
+ parent tuple; it is <code class="literal">(Datum) 0</code> at the root level or if the
+ <code class="function">inner_consistent</code> function did not provide a value at the
+ parent level. <code class="structfield">reconstructedValue</code> is always of
+ <code class="structname">spgConfigOut</code>.<code class="structfield">leafType</code> type.
+ <code class="structfield">traversalValue</code> is a pointer to any traverse data
+ passed down from the previous call of <code class="function">inner_consistent</code>
+ on the parent index tuple, or NULL at the root level.
+ <code class="structfield">traversalMemoryContext</code> is the memory context in which
+ to store output traverse values (see below).
+ <code class="structfield">level</code> is the current inner tuple's level, starting at
+ zero for the root level.
+ <code class="structfield">returnData</code> is <code class="literal">true</code> if reconstructed data is
+ required for this query; this will only be so if the
+ <code class="function">config</code> function asserted <code class="structfield">canReturnData</code>.
+ <code class="structfield">allTheSame</code> is true if the current inner tuple is
+ marked <span class="quote">“<span class="quote">all-the-same</span>”</span>; in this case all the nodes have the
+ same label (if any) and so either all or none of them match the query
+ (see <a class="xref" href="spgist-implementation.html#SPGIST-ALL-THE-SAME" title="65.4.3. “All-the-Same” Inner Tuples">Section 65.4.3</a>).
+ <code class="structfield">hasPrefix</code> is true if the current inner tuple contains
+ a prefix; if so,
+ <code class="structfield">prefixDatum</code> is its value.
+ <code class="structfield">nNodes</code> is the number of child nodes contained in the
+ inner tuple, and
+ <code class="structfield">nodeLabels</code> is an array of their label values, or
+ NULL if the nodes do not have labels.
+ </p><p>
+ <code class="structfield">nNodes</code> must be set to the number of child nodes that
+ need to be visited by the search, and
+ <code class="structfield">nodeNumbers</code> must be set to an array of their indexes.
+ If the operator class keeps track of levels, set
+ <code class="structfield">levelAdds</code> 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
+ <code class="structfield">reconstructedValues</code> to an array of the values
+ of <code class="structname">spgConfigOut</code>.<code class="structfield">leafType</code> type
+ reconstructed for each child node to be visited; otherwise, leave
+ <code class="structfield">reconstructedValues</code> as NULL.
+ If ordered search is performed, set <code class="structfield">distances</code>
+ to an array of distance values according to <code class="structfield">orderbys</code>
+ array (nodes with lowest distances will be processed first). Leave it
+ NULL otherwise.
+ If it is desired to pass down additional out-of-band information
+ (<span class="quote">“<span class="quote">traverse values</span>”</span>) to lower levels of the tree search,
+ set <code class="structfield">traversalValues</code> to an array of the appropriate
+ traverse values, one for each child node to be visited; otherwise,
+ leave <code class="structfield">traversalValues</code> as NULL.
+ Note that the <code class="function">inner_consistent</code> function is
+ responsible for palloc'ing the
+ <code class="structfield">nodeNumbers</code>, <code class="structfield">levelAdds</code>,
+ <code class="structfield">distances</code>,
+ <code class="structfield">reconstructedValues</code>, and
+ <code class="structfield">traversalValues</code> arrays in the current memory context.
+ However, any output traverse values pointed to by
+ the <code class="structfield">traversalValues</code> array should be allocated
+ in <code class="structfield">traversalMemoryContext</code>.
+ Each traverse value must be a single palloc'd chunk.
+ </p></dd><dt><span class="term"><code class="function">leaf_consistent</code></span></dt><dd><p>
+ Returns true if a leaf tuple satisfies a query.
+ </p><p>
+ The <acronym class="acronym">SQL</acronym> declaration of the function must look like this:
+</p><pre class="programlisting">
+CREATE FUNCTION my_leaf_consistent(internal, internal) RETURNS bool ...
+</pre><p>
+ The first argument is a pointer to a <code class="structname">spgLeafConsistentIn</code>
+ C struct, containing input data for the function.
+ The second argument is a pointer to a <code class="structname">spgLeafConsistentOut</code>
+ C struct, which the function must fill with result data.
+</p><pre class="programlisting">
+typedef struct spgLeafConsistentIn
+{
+ ScanKey scankeys; /* array of operators and comparison values */
+ ScanKey orderbys; /* array of ordering operators and comparison
+ * values */
+ int nkeys; /* length of scankeys array */
+ int norderbys; /* length of orderbys array */
+
+ Datum reconstructedValue; /* value reconstructed at parent */
+ void *traversalValue; /* opclass-specific traverse value */
+ 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 */
+ bool recheckDistances; /* set true if distances must be rechecked */
+ double *distances; /* associated distances */
+} spgLeafConsistentOut;
+</pre><p>
+
+ The array <code class="structfield">scankeys</code>, of length <code class="structfield">nkeys</code>,
+ 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 <code class="structfield">nkeys</code> = 0 implies
+ that all index entries satisfy the query.) Usually the consistent
+ function only cares about the <code class="structfield">sk_strategy</code> and
+ <code class="structfield">sk_argument</code> fields of each array entry, which
+ respectively give the indexable operator and comparison value.
+ In particular it is not necessary to check <code class="structfield">sk_flags</code> to
+ see if the comparison value is NULL, because the SP-GiST core code
+ will filter out such conditions.
+ The array <code class="structfield">orderbys</code>, of length <code class="structfield">norderbys</code>,
+ describes the ordering operators in the same manner.
+ <code class="structfield">reconstructedValue</code> is the value reconstructed for the
+ parent tuple; it is <code class="literal">(Datum) 0</code> at the root level or if the
+ <code class="function">inner_consistent</code> function did not provide a value at the
+ parent level. <code class="structfield">reconstructedValue</code> is always of
+ <code class="structname">spgConfigOut</code>.<code class="structfield">leafType</code> type.
+ <code class="structfield">traversalValue</code> is a pointer to any traverse data
+ passed down from the previous call of <code class="function">inner_consistent</code>
+ on the parent index tuple, or NULL at the root level.
+ <code class="structfield">level</code> is the current leaf tuple's level, starting at
+ zero for the root level.
+ <code class="structfield">returnData</code> is <code class="literal">true</code> if reconstructed data is
+ required for this query; this will only be so if the
+ <code class="function">config</code> function asserted <code class="structfield">canReturnData</code>.
+ <code class="structfield">leafDatum</code> is the key value of
+ <code class="structname">spgConfigOut</code>.<code class="structfield">leafType</code>
+ stored in the current leaf tuple.
+ </p><p>
+ The function must return <code class="literal">true</code> if the leaf tuple matches the
+ query, or <code class="literal">false</code> if not. In the <code class="literal">true</code> case,
+ if <code class="structfield">returnData</code> is <code class="literal">true</code> then
+ <code class="structfield">leafValue</code> must be set to the value of
+ <code class="structname">spgConfigIn</code>.<code class="structfield">attType</code> type
+ originally supplied to be indexed for this leaf tuple. Also,
+ <code class="structfield">recheck</code> may be set to <code class="literal">true</code> if the match
+ is uncertain and so the operator(s) must be re-applied to the actual
+ heap tuple to verify the match.
+ If ordered search is performed, set <code class="structfield">distances</code>
+ to an array of distance values according to <code class="structfield">orderbys</code>
+ array. Leave it NULL otherwise. If at least one of returned distances
+ is not exact, set <code class="structfield">recheckDistances</code> to true.
+ In this case, the executor will calculate the exact distances after
+ fetching the tuple from the heap, and will reorder the tuples if needed.
+ </p></dd></dl></div><p>
+ The optional user-defined method are:
+ </p><div class="variablelist"><dl class="variablelist"><dt><span class="term"><code class="function">Datum compress(Datum in)</code></span></dt><dd><p>
+ Converts the data item into a format suitable for physical storage in
+ a leaf tuple of index page. It accepts
+ <code class="structname">spgConfigIn</code>.<code class="structfield">attType</code>
+ value and returns
+ <code class="structname">spgConfigOut</code>.<code class="structfield">leafType</code>
+ value. Output value should not be toasted.
+ </p></dd><dt><span class="term"><code class="function">options</code></span></dt><dd><p>
+ Defines a set of user-visible parameters that control operator class
+ behavior.
+ </p><p>
+ The <acronym class="acronym">SQL</acronym> declaration of the function must look like this:
+
+</p><pre class="programlisting">
+CREATE OR REPLACE FUNCTION my_options(internal)
+RETURNS void
+AS 'MODULE_PATHNAME'
+LANGUAGE C STRICT;
+</pre><p>
+ </p><p>
+ The function is passed a pointer to a <em class="replaceable"><code>local_relopts</code></em>
+ struct, which needs to be filled with a set of operator class
+ specific options. The options can be accessed from other support
+ functions using the <code class="literal">PG_HAS_OPCLASS_OPTIONS()</code> and
+ <code class="literal">PG_GET_OPCLASS_OPTIONS()</code> macros.
+ </p><p>
+ Since the representation of the key in <acronym class="acronym">SP-GiST</acronym> is
+ flexible, it may depend on user-specified parameters.
+ </p></dd></dl></div><p>
+ All the SP-GiST support methods are normally called in a short-lived
+ memory context; that is, <code class="varname">CurrentMemoryContext</code> will be reset
+ after processing of each tuple. It is therefore not very important to
+ worry about pfree'ing everything you palloc. (The <code class="function">config</code>
+ method is an exception: it should try to avoid leaking memory. But
+ usually the <code class="function">config</code> method need do nothing but assign
+ constants into the passed parameter struct.)
+ </p><p>
+ If the indexed column is of a collatable data type, the index collation
+ will be passed to all the support methods, using the standard
+ <code class="function">PG_GET_COLLATION()</code> mechanism.
+ </p></div><div xmlns="http://www.w3.org/TR/xhtml1/transitional" class="navfooter"><hr></hr><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="spgist-builtin-opclasses.html" title="65.2. Built-in Operator Classes">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="spgist.html" title="Chapter 65. SP-GiST Indexes">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="spgist-implementation.html" title="65.4. Implementation">Next</a></td></tr><tr><td width="40%" align="left" valign="top">65.2. Built-in Operator Classes </td><td width="20%" align="center"><a accesskey="h" href="index.html" title="PostgreSQL 13.4 Documentation">Home</a></td><td width="40%" align="right" valign="top"> 65.4. Implementation</td></tr></table></div></body></html> \ No newline at end of file