This section covers implementation details and other tricks that are useful for implementers of SP-GiST operator classes to know.
65.4.1. SP-GiST Limits
Individual leaf tuples and inner tuples must fit on a single index page
(8kB by default). Therefore, when indexing values of variable-length
data types, long values can only be supported by methods such as radix
trees, in which each level of the tree includes a prefix that is short
enough to fit on a page, and the final leaf level includes a suffix also
short enough to fit on a page. The operator class should set
to true only if it is prepared to arrange for
this to happen. Otherwise, the
reject any request to index a value that is too large to fit
on an index page.
Likewise, it is the operator class's responsibility that inner tuples do not grow too large to fit on an index page; this limits the number of child nodes that can be used in one inner tuple, as well as the maximum size of a prefix value.
Another limitation is that when an inner tuple's node points to a set
of leaf tuples, those tuples must all be in the same index page.
(This is a design decision to reduce seeking and save space in the
links that chain such tuples together.) If the set of leaf tuples
grows too large for a page, a split is performed and an intermediate
inner tuple is inserted. For this to fix the problem, the new inner
divide the set of leaf values into more than one
node group. If the operator class's
fails to do that, the
core resorts to
extraordinary measures described in
is true, it is expected
that successive levels of the
absorb more and more information into the prefixes and node labels of
the inner tuples, making the required leaf datum smaller and smaller,
so that eventually it will fit on a page.
To prevent bugs in operator classes from causing infinite insertion
core will raise an error if the
leaf datum does not become any smaller within ten cycles
65.4.2. SP-GiST Without Node Labels
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 can return NULL for the
and likewise the
function can return NULL for
This will in turn result in
being NULL during
subsequent calls to
In principle, node labels could be used for some inner tuples and omitted
for others in the same index.
When working with an inner tuple having unlabeled nodes, it is an error
, since the set
of nodes is supposed to be fixed in such cases.
65.4.3. " All-the-same " Inner Tuples
core can override the results of the
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)
gave to the one node it did use, and the
leaf values are divided at random among these equivalent nodes.
flag is set on the inner tuple to warn the
functions that the
tuple does not have the node set that they might otherwise expect.
When dealing with an
is interpreted to mean that the new
value can be assigned to any of the equivalent nodes; the core code will
ignore the supplied
value and descend into one
of the nodes at random (so as to keep the tree balanced). It is an
that would make the nodes not all equivalent; the
action must be used if the value to be inserted
doesn't match the existing nodes.
When dealing with an
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
assumes about the meaning of the nodes.