<title>SP-GiST Without Node Labels</title>

  <para>
   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 <function>picksplit</function>
   function can return NULL for the <structfield>nodeLabels</structfield> array,
   and likewise the <function>choose</function> function can return NULL for
   the <structfield>prefixNodeLabels</structfield> array during
   a <literal>spgSplitTuple</literal> action.
   This will in turn result in <structfield>nodeLabels</structfield> being NULL during
   subsequent calls to <function>choose</function> and <function>inner_consistent</function>.
   In principle, node labels could be used for some inner tuples and omitted
   for others in the same index.
  </para>

  <para>
   When working with an inner tuple having unlabeled nodes, it is an error
   for <function>choose</function> to return <literal>spgAddNode</literal>, since the set
   of nodes is supposed to be fixed in such cases.
  </para>
 </sect3>

 <sect3 id="spgist-all-the-same">
  <title><quote>All-the-Same</quote> Inner Tuples</title>

  <para>
   The <acronym>SP-GiST</acronym> core can override the results of the
   operator class's <function>picksplit</function> function when
   <function>picksplit</function> 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 <function>picksplit</function> gave to the one node it did use, and the
   leaf values are divided at random among these equivalent nodes.
   The <literal>allTheSame</literal> flag is set on the inner tuple to warn the
   <function>choose</function> and <function>inner_consistent</function> functions that the
   tuple does not have the node set that they might otherwise expect.
  </para>

  <para>
   When dealing with an <literal>allTheSame</literal> tuple, a <function>choose</function>
   result of <literal>spgMatchNode</literal> is interpreted to mean that the new
   value can be assigned to any of the equivalent nodes; the core code will
   ignore the supplied  <structfield>nodeN</structfield> value and descend into one
   of the nodes at random (so as to keep the tree balanced).  It is an
   error for <function>choose</function> to return <literal>spgAddNode</literal>, since
   that would make the nodes not all equivalent; the
   <literal>spgSplitTuple</literal> action must be used if the value to be inserted
   doesn't match the existing nodes.
  </para>

  <para>
   When dealing with an <literal>allTheSame</literal> tuple, the
   <function>inner_consistent</function> 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 <function>inner_consistent</function> function normally
   assumes about the meaning of the nodes.
  </para>
 </sect3>

</sect2>

<sect2 id="spgist-examples">
 <title>Examples</title>

 <para>
  The <productname>PostgreSQL</productname> source distribution includes
  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/</filename>
  and <filename>src/backend/utils/adt/</filename> to see the code.
 </para>

</sect2>

</sect1>