| blob | 6af93719b843921d2b2e7b3882e1145cb30afb38 |
1 <!-- doc/src/sgml/spgist.sgml -->
6 <indexterm>
9 </indexterm>
14 <para>
17 search trees, which facilitate development of a wide range of different
18 non-balanced data structures, such as quad-trees, k-d trees, and radix
19 trees (tries). The common feature of these structures is that they
20 repeatedly divide the search space into partitions that need not be
21 of equal size. Searches that are well matched to the partitioning rule
22 can be very fast.
23 </para>
25 <para>
26 These popular data structures were originally developed for in-memory
27 usage. In main memory, they are usually designed as a set of dynamically
28 allocated nodes linked by pointers. This is not suitable for direct
29 storing on disk, since these chains of pointers can be rather long which
30 would require too many disk accesses. In contrast, disk-based data
31 structures should have a high fanout to minimize I/O. The challenge
33 disk pages in such a way that a search need access only a few disk pages,
34 even if it traverses many nodes.
35 </para>
37 <para>
39 the development of custom data types with the appropriate access methods,
40 by an expert in the domain of the data type, rather than a database expert.
41 </para>
43 <para>
44 Some of the information here is derived from Purdue University's
45 SP-GiST Indexing Project
49 Sigaev and Oleg Bartunov, and there is more information on their
50 <!-- URL will be changed -->
52 </para>
54 </sect2>
59 <para>
63 </para>
68 <thead>
69 <row>
73 </row>
74 </thead>
75 <tbody>
76 <row>
80 </row>
93 <row>
97 </row>
109 <row>
113 </row>
120 <row>
124 </row>
137 <row>
141 </row>
148 <row>
152 </row>
163 <row>
167 </row>
177 </tbody>
178 </tgroup>
179 </table>
181 <para>
184 supports the same operators but uses a different index data structure that
185 may offer better performance in some applications.
186 </para>
187 <para>
191 search over indexed point or polygon data sets.
192 </para>
194 </sect2>
199 <para>
201 abstraction, requiring the access method developer to implement only
203 is responsible for efficient disk mapping and searching the tree structure.
204 It also takes care of concurrency and logging considerations.
205 </para>
207 <para>
209 of the same data type as the indexed column, although it is also possible
210 for them to contain lossy representations of the indexed column.
211 Leaf tuples stored at the root level will directly represent
212 the original indexed data value, but leaf tuples at lower
213 levels might contain only a partial value, such as a suffix.
214 In that case the operator class support functions must be able to
215 reconstruct the original value using information accumulated from the
216 inner tuples that are passed through to reach the leaf level.
217 </para>
219 <para>
224 not discussed further here.
225 </para>
227 <para>
228 Inner tuples are more complex, since they are branching points in the
229 search tree. Each inner tuple contains a set of one or more
231 A node contains a downlink that leads either to another, lower-level inner
232 tuple, or to a short list of leaf tuples that all lie on the same index page.
234 in a radix tree the node label could be the next character of the string
235 value. (Alternatively, an operator class can omit the node labels, if it
236 works with a fixed set of nodes for all inner tuples;
239 that describes all its members. In a radix tree this could be the common
240 prefix of the represented strings. The prefix value is not necessarily
241 really a prefix, but can be any data needed by the operator class;
242 for example, in a quad-tree it can store the central point that the four
243 quadrants are measured with respect to. A quad-tree inner tuple would
244 then also contain four nodes corresponding to the quadrants around this
245 central point.
246 </para>
248 <para>
249 Some tree algorithms require knowledge of level (or depth) of the current
251 operator classes to manage level counting while descending the tree.
252 There is also support for incrementally reconstructing the represented
253 value when that is needed, and for passing down additional data (called
255 </para>
257 <note>
258 <para>
261 in indexed columns, this is hidden from the index operator class code:
262 no null index entries or search conditions will ever be passed to the
264 operators are strict and so cannot succeed for null values.) Null values
265 are therefore not discussed further here.
266 </para>
267 </note>
269 <para>
270 There are five user-defined methods that an index operator class for
273 arguments, the first of which is a pointer to a C struct containing input
274 values for the support method, while the second argument is a pointer to a
275 C struct where output values must be placed. Four of the mandatory methods just
278 The methods must not modify any fields of their input structs. In all
279 cases, the output struct is initialized to zeroes before calling the
282 for physical storage in a leaf tuple. The optional seventh method
285 </para>
287 <para>
288 The five mandatory user-defined methods are:
289 </para>
291 <variablelist>
292 <varlistentry>
294 <listitem>
295 <para>
296 Returns static information about the index implementation, including
297 the data type OIDs of the prefix and node label data types.
298 </para>
299 <para>
301 <programlisting>
302 CREATE FUNCTION my_config(internal, internal) RETURNS void ...
303 </programlisting>
305 C struct, containing input data for the function.
307 C struct, which the function must fill with result data.
308 <programlisting>
309 typedef struct spgConfigIn
310 {
311 Oid attType; /* Data type to be indexed */
312 } spgConfigIn;
314 typedef struct spgConfigOut
315 {
316 Oid prefixType; /* Data type of inner-tuple prefixes */
317 Oid labelType; /* Data type of inner-tuple node labels */
318 Oid leafType; /* Data type of leaf-tuple values */
319 bool canReturnData; /* Opclass can reconstruct original data */
321 } spgConfigOut;
322 </programlisting>
325 index operator classes; for ordinary fixed-data-type operator classes, it
326 will always have the same value and so can be ignored.
327 </para>
329 <para>
330 For operator classes that do not use prefixes,
332 Likewise, for operator classes that do not use node labels,
335 is capable of reconstructing the originally-supplied index value.
338 class is capable of segmenting long values by repeated suffixing
340 </para>
342 <para>
345 catalog entry.
347 implying the storage type is the same as the operator class's input
348 type, which is the most common situation.)
351 and that value will be used; but this is deprecated since the index
352 contents are then incorrectly identified in the catalogs.
353 Also, it's permissible to
355 that is interpreted as meaning the index storage type derived from
357 </para>
359 <para>
366 </para>
367 </listitem>
368 </varlistentry>
370 <varlistentry>
372 <listitem>
373 <para>
374 Chooses a method for inserting a new value into an inner tuple.
375 </para>
377 <para>
379 <programlisting>
380 CREATE FUNCTION my_choose(internal, internal) RETURNS void ...
381 </programlisting>
383 C struct, containing input data for the function.
385 C struct, which the function must fill with result data.
386 <programlisting>
387 typedef struct spgChooseIn
388 {
389 Datum datum; /* original datum to be indexed */
390 Datum leafDatum; /* current datum to be stored at leaf */
391 int level; /* current level (counting from zero) */
393 /* Data from current inner tuple */
394 bool allTheSame; /* tuple is marked all-the-same? */
395 bool hasPrefix; /* tuple has a prefix? */
396 Datum prefixDatum; /* if so, the prefix value */
397 int nNodes; /* number of nodes in the inner tuple */
398 Datum *nodeLabels; /* node label values (NULL if none) */
399 } spgChooseIn;
401 typedef enum spgChooseResultType
402 {
403 spgMatchNode = 1, /* descend into existing node */
404 spgAddNode, /* add a node to the inner tuple */
405 spgSplitTuple /* split inner tuple (change its prefix) */
406 } spgChooseResultType;
408 typedef struct spgChooseOut
409 {
410 spgChooseResultType resultType; /* action code, see above */
411 union
412 {
413 struct /* results for spgMatchNode */
414 {
415 int nodeN; /* descend to this node (index from 0) */
416 int levelAdd; /* increment level by this much */
417 Datum restDatum; /* new leaf datum */
418 } matchNode;
419 struct /* results for spgAddNode */
420 {
421 Datum nodeLabel; /* new node's label */
422 int nodeN; /* where to insert it (index from 0) */
423 } addNode;
424 struct /* results for spgSplitTuple */
425 {
426 /* Info to form new upper-level inner tuple with one child tuple */
427 bool prefixHasPrefix; /* tuple should have a prefix? */
428 Datum prefixPrefixDatum; /* if so, its value */
429 int prefixNNodes; /* number of nodes */
430 Datum *prefixNodeLabels; /* their labels (or NULL for
431 * no labels) */
432 int childNodeN; /* which node gets child tuple */
434 /* Info to form new lower-level inner tuple with all old nodes */
435 bool postfixHasPrefix; /* tuple should have a prefix? */
436 Datum postfixPrefixDatum; /* if so, its value */
437 } splitTuple;
438 } result;
439 } spgChooseOut;
440 </programlisting>
444 type that was to be inserted into the index.
447 type, which is initially a result of method
453 methods change it. When the insertion search reaches a leaf page,
455 in the newly created leaf tuple.
457 zero for the root level.
459 marked as containing multiple equivalent nodes
462 a prefix; if so,
465 inner tuple, and
467 NULL if there are no labels.
468 </para>
470 <para>
472 the new value matches one of the existing child nodes, or that a new
473 child node must be added, or that the new value is inconsistent with
474 the tuple prefix and so the inner tuple must be split to create a
475 less restrictive prefix.
476 </para>
478 <para>
479 If the new value matches one of the existing child nodes,
482 the node array.
485 or leave it as zero if the operator class does not use levels.
487 if the operator class does not modify datums from one level to the
488 next, or otherwise set it to the modified value to be used as
490 </para>
492 <para>
493 If a new child node must be added,
497 to insert the node in the node array.
499 function will be called again with the modified inner tuple;
501 </para>
503 <para>
504 If the new value is inconsistent with the tuple prefix,
506 This action moves all the existing nodes into a new lower-level
507 inner tuple, and replaces the existing inner tuple with a tuple
508 having a single downlink pointing to the new lower-level inner tuple.
510 upper tuple should have a prefix, and if so set
512 prefix value must be sufficiently less restrictive than the original
513 to accept the new value to be indexed.
516 holding their labels, or to NULL if node labels are not required.
517 Note that the total size of the new upper tuple must be no more
518 than the total size of the tuple it is replacing; this constrains
519 the lengths of the new prefix and new labels.
521 that will downlink to the new lower-level inner tuple.
523 lower-level inner tuple should have a prefix, and if so set
525 combination of these two prefixes and the downlink node's label
526 (if any) must have the same meaning as the original prefix, because
527 there is no opportunity to alter the node labels that are moved to
528 the new lower-level tuple, nor to change any child index entries.
530 function will be called again with the replacement inner tuple.
534 allow the insertion to descend to the next level.
535 </para>
536 </listitem>
537 </varlistentry>
539 <varlistentry>
541 <listitem>
542 <para>
543 Decides how to create a new inner tuple over a set of leaf tuples.
544 </para>
546 <para>
548 <programlisting>
549 CREATE FUNCTION my_picksplit(internal, internal) RETURNS void ...
550 </programlisting>
552 C struct, containing input data for the function.
554 C struct, which the function must fill with result data.
555 <programlisting>
556 typedef struct spgPickSplitIn
557 {
558 int nTuples; /* number of leaf tuples */
559 Datum *datums; /* their datums (array of length nTuples) */
560 int level; /* current level (counting from zero) */
561 } spgPickSplitIn;
563 typedef struct spgPickSplitOut
564 {
565 bool hasPrefix; /* new inner tuple should have a prefix? */
566 Datum prefixDatum; /* if so, its value */
568 int nNodes; /* number of nodes for new inner tuple */
569 Datum *nodeLabels; /* their labels (or NULL for no labels) */
571 int *mapTuplesToNodes; /* node index for each leaf tuple */
572 Datum *leafTupleDatums; /* datum to store in each new leaf tuple */
573 } spgPickSplitOut;
574 </programlisting>
579 type.
581 share, which will become the level of the new inner tuple.
582 </para>
584 <para>
586 tuple should have a prefix, and if so set
589 the new inner tuple will contain, and
591 or to NULL if node labels are not required.
593 (from zero) of the node that each leaf tuple should be assigned to.
595 be stored in the new leaf tuples (these will be the same as the
597 datums from one level to the next).
599 responsible for palloc'ing the
602 </para>
604 <para>
605 If more than one leaf tuple is supplied, it is expected that the
607 one node; otherwise it is not possible to split the leaf tuples
608 across multiple pages, which is the ultimate purpose of this
610 ends up placing all the leaf tuples in the same node, the core
611 SP-GiST code will override that decision and generate an inner
612 tuple in which the leaf tuples are assigned at random to several
613 identically-labeled nodes. Such a tuple is marked
616 must take suitable care with such inner tuples.
618 </para>
620 <para>
624 value has been supplied. In this case the point of the operation is
625 to strip off a prefix and produce a new, shorter leaf datum value.
626 The call will be repeated until a leaf datum short enough to fit on
628 more information.
629 </para>
630 </listitem>
631 </varlistentry>
633 <varlistentry>
635 <listitem>
636 <para>
637 Returns set of nodes (branches) to follow during tree search.
638 </para>
640 <para>
642 <programlisting>
643 CREATE FUNCTION my_inner_consistent(internal, internal) RETURNS void ...
644 </programlisting>
646 C struct, containing input data for the function.
648 C struct, which the function must fill with result data.
650 <programlisting>
651 typedef struct spgInnerConsistentIn
652 {
653 ScanKey scankeys; /* array of operators and comparison values */
654 ScanKey orderbys; /* array of ordering operators and comparison
655 * values */
656 int nkeys; /* length of scankeys array */
657 int norderbys; /* length of orderbys array */
659 Datum reconstructedValue; /* value reconstructed at parent */
660 void *traversalValue; /* opclass-specific traverse value */
661 MemoryContext traversalMemoryContext; /* put new traverse values here */
662 int level; /* current level (counting from zero) */
663 bool returnData; /* original data must be returned? */
665 /* Data from current inner tuple */
666 bool allTheSame; /* tuple is marked all-the-same? */
667 bool hasPrefix; /* tuple has a prefix? */
668 Datum prefixDatum; /* if so, the prefix value */
669 int nNodes; /* number of nodes in the inner tuple */
670 Datum *nodeLabels; /* node label values (NULL if none) */
671 } spgInnerConsistentIn;
673 typedef struct spgInnerConsistentOut
674 {
675 int nNodes; /* number of child nodes to be visited */
676 int *nodeNumbers; /* their indexes in the node array */
677 int *levelAdds; /* increment level by this much for each */
678 Datum *reconstructedValues; /* associated reconstructed values */
679 void **traversalValues; /* opclass-specific traverse values */
680 double **distances; /* associated distances */
681 } spgInnerConsistentOut;
682 </programlisting>
685 describes the index search condition(s). These conditions are
686 combined with AND — only index entries that satisfy all of
688 that all index entries satisfy the query.) Usually the consistent
691 respectively give the indexable operator and comparison value.
693 see if the comparison value is NULL, because the SP-GiST core code
694 will filter out such conditions.
696 describes ordering operators (if any) in the same manner.
700 parent level.
703 on the parent index tuple, or NULL at the root level.
705 to store output traverse values (see below).
707 zero for the root level.
709 required for this query; this will only be so if the
713 same label (if any) and so either all or none of them match the query
716 a prefix; if so,
719 inner tuple, and
721 NULL if the nodes do not have labels.
722 </para>
724 <para>
726 need to be visited by the search, and
728 If the operator class keeps track of levels, set
730 required when descending to each node to be visited. (Often these
731 increments will be the same for all the nodes, but that's not
732 necessarily so, so an array is used.)
733 If value reconstruction is needed, set
735 reconstructed for each child node to be visited; otherwise, leave
737 The reconstructed values are assumed to be of type
739 (However, since the core system will do nothing with them except
740 possibly copy them, it is sufficient for them to have the
745 array (nodes with lowest distances will be processed first). Leave it
746 NULL otherwise.
747 If it is desired to pass down additional out-of-band information
750 traverse values, one for each child node to be visited; otherwise,
753 responsible for palloc'ing the
758 However, any output traverse values pointed to by
761 Each traverse value must be a single palloc'd chunk.
762 </para>
763 </listitem>
764 </varlistentry>
766 <varlistentry>
768 <listitem>
769 <para>
770 Returns true if a leaf tuple satisfies a query.
771 </para>
773 <para>
775 <programlisting>
776 CREATE FUNCTION my_leaf_consistent(internal, internal) RETURNS bool ...
777 </programlisting>
779 C struct, containing input data for the function.
781 C struct, which the function must fill with result data.
782 <programlisting>
783 typedef struct spgLeafConsistentIn
784 {
785 ScanKey scankeys; /* array of operators and comparison values */
786 ScanKey orderbys; /* array of ordering operators and comparison
787 * values */
788 int nkeys; /* length of scankeys array */
789 int norderbys; /* length of orderbys array */
791 Datum reconstructedValue; /* value reconstructed at parent */
792 void *traversalValue; /* opclass-specific traverse value */
793 int level; /* current level (counting from zero) */
794 bool returnData; /* original data must be returned? */
796 Datum leafDatum; /* datum in leaf tuple */
797 } spgLeafConsistentIn;
799 typedef struct spgLeafConsistentOut
800 {
801 Datum leafValue; /* reconstructed original data, if any */
802 bool recheck; /* set true if operator must be rechecked */
803 bool recheckDistances; /* set true if distances must be rechecked */
804 double *distances; /* associated distances */
805 } spgLeafConsistentOut;
806 </programlisting>
809 describes the index search condition(s). These conditions are
810 combined with AND — only index entries that satisfy all of
812 that all index entries satisfy the query.) Usually the consistent
815 respectively give the indexable operator and comparison value.
817 see if the comparison value is NULL, because the SP-GiST core code
818 will filter out such conditions.
820 describes the ordering operators in the same manner.
824 parent level.
827 on the parent index tuple, or NULL at the root level.
829 zero for the root level.
831 required for this query; this will only be so if the
835 stored in the current leaf tuple.
836 </para>
838 <para>
844 originally supplied to be indexed for this leaf tuple. Also,
846 is uncertain and so the operator(s) must be re-applied to the actual
847 heap tuple to verify the match.
850 array. Leave it NULL otherwise. If at least one of returned distances
852 In this case, the executor will calculate the exact distances after
853 fetching the tuple from the heap, and will reorder the tuples if needed.
854 </para>
855 </listitem>
856 </varlistentry>
857 </variablelist>
859 <para>
860 The optional user-defined methods are:
861 </para>
863 <variablelist>
864 <varlistentry>
866 <listitem>
867 <para>
868 Converts a data item into a format suitable for physical storage in
869 a leaf tuple of the index. It accepts a value of type
871 and returns a value of type
873 The output value must not contain an out-of-line TOAST pointer.
874 </para>
876 <para>
878 values to be stored. The consistent methods receive query
881 </para>
882 </listitem>
883 </varlistentry>
885 <varlistentry>
887 <listitem>
888 <para>
889 Defines a set of user-visible parameters that control operator class
890 behavior.
891 </para>
893 <para>
896 <programlisting>
897 CREATE OR REPLACE FUNCTION my_options(internal)
898 RETURNS void
899 AS 'MODULE_PATHNAME'
900 LANGUAGE C STRICT;
901 </programlisting>
902 </para>
904 <para>
906 struct, which needs to be filled with a set of operator class
907 specific options. The options can be accessed from other support
910 </para>
912 <para>
914 flexible, it may depend on user-specified parameters.
915 </para>
916 </listitem>
917 </varlistentry>
918 </variablelist>
920 <para>
921 All the SP-GiST support methods are normally called in a short-lived
923 after processing of each tuple. It is therefore not very important to
925 method is an exception: it should try to avoid leaking memory. But
927 constants into the passed parameter struct.)
928 </para>
930 <para>
931 If the indexed column is of a collatable data type, the index collation
932 will be passed to all the support methods, using the standard
934 </para>
936 </sect2>
941 <para>
942 This section covers implementation details and other tricks that are
944 know.
945 </para>
950 <para>
951 Individual leaf tuples and inner tuples must fit on a single index page
952 (8kB by default). Therefore, when indexing values of variable-length
953 data types, long values can only be supported by methods such as radix
954 trees, in which each level of the tree includes a prefix that is short
955 enough to fit on a page, and the final leaf level includes a suffix also
956 short enough to fit on a page. The operator class should set
959 reject any request to index a value that is too large to fit
960 on an index page.
961 </para>
963 <para>
964 Likewise, it is the operator class's responsibility that inner tuples
965 do not grow too large to fit on an index page; this limits the number
966 of child nodes that can be used in one inner tuple, as well as the
967 maximum size of a prefix value.
968 </para>
970 <para>
971 Another limitation is that when an inner tuple's node points to a set
972 of leaf tuples, those tuples must all be in the same index page.
973 (This is a design decision to reduce seeking and save space in the
974 links that chain such tuples together.) If the set of leaf tuples
975 grows too large for a page, a split is performed and an intermediate
976 inner tuple is inserted. For this to fix the problem, the new inner
981 </para>
983 <para>
986 absorb more and more information into the prefixes and node labels of
987 the inner tuples, making the required leaf datum smaller and smaller,
988 so that eventually it will fit on a page.
989 To prevent bugs in operator classes from causing infinite insertion
991 leaf datum does not become any smaller within ten cycles
993 </para>
994 </sect3>
999 <para>
1000 Some tree algorithms use a fixed set of nodes for each inner tuple;
1001 for example, in a quad-tree there are always exactly four nodes
1002 corresponding to the four quadrants around the inner tuple's centroid
1003 point. In such a case the code typically works with the nodes by
1004 number, and there is no need for explicit node labels. To suppress
1012 In principle, node labels could be used for some inner tuples and omitted
1013 for others in the same index.
1014 </para>
1016 <para>
1017 When working with an inner tuple having unlabeled nodes, it is an error
1019 of nodes is supposed to be fixed in such cases.
1020 </para>
1021 </sect3>
1026 <para>
1030 at least two node categories. When this happens, the new inner tuple
1031 is created with multiple nodes that each have the same label (if any)
1033 leaf values are divided at random among these equivalent nodes.
1036 tuple does not have the node set that they might otherwise expect.
1037 </para>
1039 <para>
1042 value can be assigned to any of the equivalent nodes; the core code will
1044 of the nodes at random (so as to keep the tree balanced). It is an
1046 that would make the nodes not all equivalent; the
1048 doesn't match the existing nodes.
1049 </para>
1051 <para>
1054 of the nodes as targets for continuing the index search, since they are
1055 all equivalent. This may or may not require any special-case code,
1057 assumes about the meaning of the nodes.
1058 </para>
1059 </sect3>
1061 </sect2>
1066 <para>
1072 </para>
1074 </sect2>
1076 </sect1>