codekingpro/portable-devtools

1<?xml version="1.0" encoding="UTF-8" standalone="no"?>2<!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>69.4. Implementation</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 Vsnapshot" /><link rel="prev" href="spgist-extensibility.html" title="69.3. Extensibility" /><link rel="next" href="spgist-examples.html" title="69.5. Examples" /></head><body id="docContent" class="container-fluid col-10"><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="5" align="center">69.4. Implementation</th></tr><tr><td width="10%" align="left"><a accesskey="p" href="spgist-extensibility.html" title="69.3. Extensibility">Prev</a> </td><td width="10%" align="left"><a accesskey="u" href="spgist.html" title="Chapter 69. SP-GiST Indexes">Up</a></td><th width="60%" align="center">Chapter 69. SP-GiST Indexes</th><td width="10%" align="right"><a accesskey="h" href="index.html" title="PostgreSQL 16.3 Documentation">Home</a></td><td width="10%" align="right"> <a accesskey="n" href="spgist-examples.html" title="69.5. Examples">Next</a></td></tr></table><hr /></div><div class="sect1" id="SPGIST-IMPLEMENTATION"><div class="titlepage"><div><div><h2 class="title" style="clear: both">69.4. Implementation <a href="#SPGIST-IMPLEMENTATION" class="id_link">#</a></h2></div></div></div><div class="toc"><dl class="toc"><dt><span class="sect2"><a href="spgist-implementation.html#SPGIST-LIMITS">69.4.1. SP-GiST Limits</a></span></dt><dt><span class="sect2"><a href="spgist-implementation.html#SPGIST-NULL-LABELS">69.4.2. SP-GiST Without Node Labels</a></span></dt><dt><span class="sect2"><a href="spgist-implementation.html#SPGIST-ALL-THE-SAME">69.4.3. <span class="quote">“<span class="quote">All-the-Same</span>”</span> Inner Tuples</a></span></dt></dl></div><p>3   This section covers implementation details and other tricks that are4   useful for implementers of <acronym class="acronym">SP-GiST</acronym> operator classes to5   know.6  </p><div class="sect2" id="SPGIST-LIMITS"><div class="titlepage"><div><div><h3 class="title">69.4.1. SP-GiST Limits <a href="#SPGIST-LIMITS" class="id_link">#</a></h3></div></div></div><p>7   Individual leaf tuples and inner tuples must fit on a single index page8   (8kB by default).  Therefore, when indexing values of variable-length9   data types, long values can only be supported by methods such as radix10   trees, in which each level of the tree includes a prefix that is short11   enough to fit on a page, and the final leaf level includes a suffix also12   short enough to fit on a page.  The operator class should set13   <code class="structfield">longValuesOK</code> to true only if it is prepared to arrange for14   this to happen.  Otherwise, the <acronym class="acronym">SP-GiST</acronym> core will15   reject any request to index a value that is too large to fit16   on an index page.17  </p><p>18   Likewise, it is the operator class's responsibility that inner tuples19   do not grow too large to fit on an index page; this limits the number20   of child nodes that can be used in one inner tuple, as well as the21   maximum size of a prefix value.22  </p><p>23   Another limitation is that when an inner tuple's node points to a set24   of leaf tuples, those tuples must all be in the same index page.25   (This is a design decision to reduce seeking and save space in the26   links that chain such tuples together.)  If the set of leaf tuples27   grows too large for a page, a split is performed and an intermediate28   inner tuple is inserted.  For this to fix the problem, the new inner29   tuple <span class="emphasis"><em>must</em></span> divide the set of leaf values into more than one30   node group.  If the operator class's <code class="function">picksplit</code> function31   fails to do that, the <acronym class="acronym">SP-GiST</acronym> core resorts to32   extraordinary measures described in <a class="xref" href="spgist-implementation.html#SPGIST-ALL-THE-SAME" title="69.4.3. “All-the-Same” Inner Tuples">Section 69.4.3</a>.33  </p><p>34   When <code class="structfield">longValuesOK</code> is true, it is expected35   that successive levels of the <acronym class="acronym">SP-GiST</acronym> tree will36   absorb more and more information into the prefixes and node labels of37   the inner tuples, making the required leaf datum smaller and smaller,38   so that eventually it will fit on a page.39   To prevent bugs in operator classes from causing infinite insertion40   loops, the <acronym class="acronym">SP-GiST</acronym> core will raise an error if the41   leaf datum does not become any smaller within ten cycles42   of <code class="function">choose</code> method calls.43  </p></div><div class="sect2" id="SPGIST-NULL-LABELS"><div class="titlepage"><div><div><h3 class="title">69.4.2. SP-GiST Without Node Labels <a href="#SPGIST-NULL-LABELS" class="id_link">#</a></h3></div></div></div><p>44   Some tree algorithms use a fixed set of nodes for each inner tuple;45   for example, in a quad-tree there are always exactly four nodes46   corresponding to the four quadrants around the inner tuple's centroid47   point.  In such a case the code typically works with the nodes by48   number, and there is no need for explicit node labels.  To suppress49   node labels (and thereby save some space), the <code class="function">picksplit</code>50   function can return NULL for the <code class="structfield">nodeLabels</code> array,51   and likewise the <code class="function">choose</code> function can return NULL for52   the <code class="structfield">prefixNodeLabels</code> array during53   a <code class="literal">spgSplitTuple</code> action.54   This will in turn result in <code class="structfield">nodeLabels</code> being NULL during55   subsequent calls to <code class="function">choose</code> and <code class="function">inner_consistent</code>.56   In principle, node labels could be used for some inner tuples and omitted57   for others in the same index.58  </p><p>59   When working with an inner tuple having unlabeled nodes, it is an error60   for <code class="function">choose</code> to return <code class="literal">spgAddNode</code>, since the set61   of nodes is supposed to be fixed in such cases.62  </p></div><div class="sect2" id="SPGIST-ALL-THE-SAME"><div class="titlepage"><div><div><h3 class="title">69.4.3. <span class="quote">“<span class="quote">All-the-Same</span>”</span> Inner Tuples <a href="#SPGIST-ALL-THE-SAME" class="id_link">#</a></h3></div></div></div><p>63   The <acronym class="acronym">SP-GiST</acronym> core can override the results of the64   operator class's <code class="function">picksplit</code> function when65   <code class="function">picksplit</code> fails to divide the supplied leaf values into66   at least two node categories.  When this happens, the new inner tuple67   is created with multiple nodes that each have the same label (if any)68   that <code class="function">picksplit</code> gave to the one node it did use, and the69   leaf values are divided at random among these equivalent nodes.70   The <code class="literal">allTheSame</code> flag is set on the inner tuple to warn the71   <code class="function">choose</code> and <code class="function">inner_consistent</code> functions that the72   tuple does not have the node set that they might otherwise expect.73  </p><p>74   When dealing with an <code class="literal">allTheSame</code> tuple, a <code class="function">choose</code>75   result of <code class="literal">spgMatchNode</code> is interpreted to mean that the new76   value can be assigned to any of the equivalent nodes; the core code will77   ignore the supplied  <code class="structfield">nodeN</code> value and descend into one78   of the nodes at random (so as to keep the tree balanced).  It is an79   error for <code class="function">choose</code> to return <code class="literal">spgAddNode</code>, since80   that would make the nodes not all equivalent; the81   <code class="literal">spgSplitTuple</code> action must be used if the value to be inserted82   doesn't match the existing nodes.83  </p><p>84   When dealing with an <code class="literal">allTheSame</code> tuple, the85   <code class="function">inner_consistent</code> function should return either all or none86   of the nodes as targets for continuing the index search, since they are87   all equivalent.  This may or may not require any special-case code,88   depending on how much the <code class="function">inner_consistent</code> function normally89   assumes about the meaning of the nodes.90  </p></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="spgist-extensibility.html" title="69.3. Extensibility">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="spgist.html" title="Chapter 69. SP-GiST Indexes">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="spgist-examples.html" title="69.5. Examples">Next</a></td></tr><tr><td width="40%" align="left" valign="top">69.3. Extensibility </td><td width="20%" align="center"><a accesskey="h" href="index.html" title="PostgreSQL 16.3 Documentation">Home</a></td><td width="40%" align="right" valign="top"> 69.5. Examples</td></tr></table></div></body></html>