27 SP-GiST

27.1 Overview

The first letters in the SP-GiST name stand for Space Partitioning. The space here is understood as an arbitrary set of values on which the search is performed; it is not necessarily the space in the conventional sense of the word (such as a two-dimensional plane). The GiST part of the name hints at certain similarity between GiST and SP-GiST methods: both of them are generalized search trees and serve as frameworks for indexing various data types.

The idea behind the SP-GiST method¹ is to split the search space into several non-overlapping regions, which are in turn can be recursively split into sub-regions. Such partitioning produces non-balanced trees (which differ from B-trees and GiST trees) and can be used to implement such well-known structures as quadtrees, k-D trees, and radix trees (tries).

Non-balanced trees typically have few branches and, consequently, large depth. For example, a quadtree node has four child nodes at the most, while a node of a k-D tree can have only two. It does not pose any problems if the tree is kept in memory; but when stored on disk, tree nodes have to be packed into pages as densely as possible to minimize I/O, and this task is not so trivial. B-tree and GiST indexes do not have to take care of it because each of their tree nodes takes the whole page.

An inner node of an SP-GiST tree contains a value that satisfies the condition that holds true for all its child nodes. Such a value is often called a prefix; it plays the same role as the predicate in GiST indexes. Pointers to SP-GiST child nodes may have labels.

Leaf node elements contain an indexed value (or its part) and the corresponding TID.

Just like GiST, SP-GiST implements only the main algorithms, taking care of such low-level details as concurrent access, locks, and logging. New data types and algorithms of space partitioning can be added via the operator class interface. The operator class provides most of the logic and defines many aspects of indexing functionality.

In SP-GiST, the search is depth-first, starting at the root node.² The nodes that are worth descending into are chosen by the consistency function, similar to the one used in GiST. For an inner node of the tree, this function returns a set of child nodes whose values do not contradict the search predicate. The consistency function does not descend into these nodes: it merely assesses the corresponding labels and prefixes. For leaf nodes, it determines whether the indexed value of this node matches the search predicate.

In a non-balanced tree, search time can vary depending on the branch depth.

There are two support functions that participate in insertion of values into an SP-GiST index. As the tree is being traversed from the root node, the choose function takes one of the following decisions: send the new value into an existing child node, create a new child node for this value, or split the current node (if the value does not match this node’s prefix). If the chosen leaf page does not have enough space, the picksplit function determines which nodes should be moved to a new page.

Now I will provide some examples to illustrate these algorithms.

27.2 Quadtrees for Points

Quadtrees are used for indexing points on a two-dimensional plane. The plane is recursively split into four regions (quadrants) with respect to the selected point. This point is called a centroid; it serves as the node prefix, that is, the condition that defines the location of child values.

The root node splits the plane into four quadrants.

Then each of them is further split into its own quadrants.

This procedure goes on until the desired number of partitions is reached.

This example uses an index built on an extended airports table. The illustrations show that branch depth depends on point density in the corresponding quadrants. For visual clarity, I set a small value of the fillfactor storage parameter, which makes the tree deeper: (p. 446) (default: 80)

=> CREATE INDEX airports_quad_idx ON airports_big
USING spgist(coordinates) WITH (fillfactor = 10);

The default operator class for points is quad_point_ops.

Operator Class

I have already mentioned SP-GiST support functions:³ the consistency function for search and the picksplit function for insertions.

Now let’s take a look at the list of support functions of the quad_point_ops operator class.⁴ All of them are mandatory.

=> SELECT amprocnum, amproc::regproc
FROM pg_am am
  JOIN pg_opclass opc ON opcmethod = am.oid
  JOIN pg_amproc amop ON amprocfamily = opcfamily
WHERE amname = 'spgist'
AND opcname = 'quad_point_ops'
ORDER BY amprocnum;
 amprocnum |          amproc
-----------+---------------------------
         1 | spg_quad_config
         2 | spg_quad_choose
         3 | spg_quad_picksplit
         4 | spg_quad_inner_consistent
         5 | spg_quad_leaf_consistent
(5 rows)

These functions perform the following tasks:

1. The config function reports basic information about the operator class to the access method.

2. The choose function select the node for insertions.

3. The picksplit function distributes nodes between pages after a page split.

4. The inner_consistent function checks whether the value of the inner node satisfies the search predicate.

5. The leaf_consistent function determines whether the value stored in the leaf node satisfies the search predicate.

There are also several optional functions.

⁵ The quad_point_ops operator class supports the same strategies as GiST: (p. 449)

=> SELECT amopopr::regoperator, oprcode::regproc, amopstrategy
FROM pg_am am
  JOIN pg_opclass opc ON opcmethod = am.oid
  JOIN pg_amop amop ON amopfamily = opcfamily
  JOIN pg_operator opr ON opr.oid = amopopr
WHERE amname = 'spgist'
AND opcname = 'quad_point_ops'
ORDER BY amopstrategy;
     amopopr      |    oprcode     | amopstrategy
------------------+----------------+--------------
 <<(point,point)  | point_left     |            1
 >>(point,point)  | point_right    |            5
 ~=(point,point)  | point_eq       |            6
 <@(point,box)    | on_pb          |            8
 <<|(point,point) | point_below    |           10
 |>>(point,point) | point_above    |           11
 <->(point,point) | point_distance |           15
 <^(point,point)  | point_below    |           29
 >^(point,point)  | point_above    |           30
(9 rows)

For example, you can use the above operator >^ to find the airports located to the North of Dikson:

=> SELECT airport_code, airport_name->>'en'
FROM airports_big
WHERE coordinates >^ '(80.3817,73.5167)'::point;
 airport_code |          ?column?
--------------+----------------------------
 THU          | Thule Air Base
 YEU          | Eureka Airport
 YLT          | Alert Airport
 YRB          | Resolute Bay Airport
 LYR          | Svalbard Airport, Longyear
 NAQ          | Qaanaaq Airport
 YGZ          | Grise Fiord Airport
 DKS          | Dikson Airport
(8 rows)
=> EXPLAIN (costs off) SELECT airport_code
FROM airports_big
WHERE coordinates >^ '(80.3817,73.5167)'::point;
                          QUERY PLAN
---------------------------------------------------------------
 Bitmap Heap Scan on airports_big
   Recheck Cond: (coordinates >^ '(80.3817,73.5167)'::point)
   -> Bitmap Index Scan on airports_quad_idx
       Index Cond: (coordinates >^ '(80.3817,73.5167)'::point)
(4 rows)

Let’s take a closer look at the structure and inner workings of a quadtree. We will use the same simple example with several points that we discussed in the chapter related to GiST. (p. 451)

Here is how the plane can be partitioned in this case:

The left illustration shows quadrant numbering at one of the tree levels; in the illustrations that follow, I will place child nodes from left to right in the same order for the sake of clarity. Points that lie on the boundaries are included into the quadrant with the smaller number. The right illustration shows the final partitioning.

You can see a possible structure of this index below. Each inner node references four child nodes at the most, and each of these pointers is labeled with the quadrant number:

Page Layout

Unlike B-tree and GiST indexes, SP-GiST has no one-to-one correspondence between tree nodes and pages. Since inner nodes usually do not have too many children, several nodes have to be packed into a single page. Different types of nodes are stored in different pages: inner nodes are stored in inner pages, while leaf nodes go to leaf pages.

Index entries stored in inner pages hold the value used as a prefix, as well as a set of pointers to child nodes; each pointer may be accompanied by a label.

Leaf page entries consist of a value and a TID.

All leaf nodes related to a particular inner node are stored together in a single page and are bound into a list. If the page cannot accommodate another node, this list can be moved to a different page,⁶ or the page can be split; one way or the other, a list never stretches over several pages.

To save space, the algorithm tries to add new nodes into the same pages until these pages are completely filled. The numbers of the last pages used are cached by backends and are periodically saved in the zero page, which is called a metapage. The metapage contains no reference to the root node, which we would have seen in a B-tree; the root of an SP-GiST index is always located in the first page.

Let’s get back to our example. The illustration below shows how tree nodes can be distributed between pages. The quad_point_ops operator class does not actually use labels. Since a node can have four child nodes at the most, the index keeps a fixed-size array of four pointers, some of which may be empty.

Search

Let’s use the same example to take a look at the algorithm of searching for points located above point (3,7).

The search starts at the root. The inner consistency function⁹ determines the child nodes to be descended into. Point (3,7) is compared with the root node’s centroid (5,5) to choose the quadrants that may contain the sought-after points; in this example, these are quadrants I and IV.

Once inside the node with centroid (7,7), we again have to choose the child nodes to descend into. They belong to quadrants I and IV, but since quadrant IV is empty, we only need to check one leaf node. The leaf consistency function¹⁰ compares the points of this node with point (3,7) specified in the query. The above condition is satisfied only for (8,9).

Now we just have to go back one level and check the node that corresponds to quadrant IV of the root node. It is empty, so the search is complete.

Insertion

When a value gets inserted into an SP-GiST tree,¹¹ each action that follows is determined by the choice function.¹² In this particular case, it simply directs the point to one of the existing nodes that corresponds to its quadrant.

For example, let’s add value (7,1):

The value belongs to quadrant II and will be added to the corresponding tree node:

If the list of leaf nodes in the selected quadrant becomes too big after insertion (it must fit a single page), the page is split. The picksplit function¹³ determines the new centroid by calculating the average value of all points’ coordinates, thus distributing the child nodes between new quadrants more or less uniformly.

The following picture illustrates the page overflow caused by point (2,1) insertion:

A new inner node with centroid (1,1) is added into the tree, while points (0,0), (1,2), and (2,1) get redistributed between the new quadrants:

Properties

Access method properties. The spgist method reports the following properties:

=> SELECT a.amname, p.name, pg_indexam_has_property(a.oid, p.name)
FROM pg_am a, unnest(array[
  'can_order', 'can_unique', 'can_multi_col',
  'can_exclude', 'can_include'
]) p(name)
WHERE a.amname = 'spgist';
 amname |     name      | pg_indexam_has_property
--------+---------------+-------------------------
 spgist | can_order     | f
 spgist | can_unique    | f
 spgist | can_multi_col | f
 spgist | can_exclude   | t
 spgist | can_include   | t
(5 rows)

No support is provided for sorting and uniqueness properties. Multicolumn indexes are not supported either.

Exclusion constraints are supported, just like in GiST.

An SP-GiST index can be created with additional INCLUDE columns. (v. 14)

Index-level properties. Unlike GiST, SP-GiST indexes do not support clusterization:

=>  SELECT p.name, pg_index_has_property('airports_quad_idx', p.name)
FROM unnest(array[
  'clusterable', 'index_scan', 'bitmap_scan', 'backward_scan'
]) p(name);
     name      | pg_index_has_property
---------------+-----------------------
 clusterable   | f
 index_scan    | t
 bitmap_scan   | t
 backward_scan | f
(4 rows)

Both ways of getting TIDs (either one by one or as a bitmap) are supported. Backward scanning is unavailable, as it does not make any sense for SP-GiST.

Column-level properties. For the most part, column-level properties are the same:

=> SELECT p.name,
  pg_index_column_has_property('airports_quad_idx', 1, p.name)
FROM unnest(array[
  'orderable', 'search_array', 'search_nulls'
]) p(name);
     name     | pg_index_column_has_property
--------------+------------------------------
 orderable    | f
 search_array | f
 search_nulls | t
(3 rows)

Sorting is not supported, so all the related properties do not make any sense and are disabled.

I have not said anything about NULL values so far, but as we can see in the index properties, they are supported. Unlike GiST, SP-GiST indexes do not store NULL values in the main tree. Instead, a separate tree is created; its root is located in the second index page. Thus, the first three pages always have the same meaning: the metapage, the root of the main tree, and the root of the tree for NULL values.

Some column-level properties may depend on the particular operator class:

=> SELECT p.name,
  pg_index_column_has_property('airports_quad_idx', 1, p.name)
FROM unnest(array[
  'returnable', 'distance_orderable'
]) p(name);
        name        | pg_index_column_has_property
--------------------+------------------------------
 returnable         | t
 distance_orderable | t
(2 rows)

Like in all the other examples in this chapter, this index can be used for index-only scans.

But in general, an operator class does not necessarily store full values in leaf pages, as it can recheck them by the table instead. It allows using SP-GiST indexes in PostGIS for potentially large geometry values, to give one example. (v. 11)

Nearest neighbor search is supported; we have seen the ordering operator <-> in the operator class. (v. 12)

27.3 K-Dimensional Trees for Points

Points on a plane can also be indexed using another approach to partitioning: we can split the plane into two sub-regions instead of four. Such partitioning is implemented by the kd_point_ops¹⁴ operator class:

=> CREATE INDEX airports_kd_idx ON airports_big
USING spgist(coordinates kd_point_ops);

Note that indexed values, prefixes, and labels may have different data types. For this operator class, values are represented as points, prefixes are real numbers, while labels are not provided (as in quad_point_ops).

Let’s select some coordinate on the Y-axis (it defines the latitude in the example with airports). This coordinate splits the plane into two sub-regions, the upper and the lower one:

For each of these sub-regions, select coordinates on the X-axis (longitude) that split them into two sub-regions, left and right:

We will continue splitting each of the resulting sub-regions, taking turns between horizontal and vertical partitioning, until the points in each part fit a single index page:

All inner leaf nodes of the tree built this way will have only two child nodes. The method can be easily generalized for space with arbitrary dimensions, so such trees are often referred to as k-dimensional (k-D trees).

27.4 Radix Trees for Strings

The text_ops operator class for SP-GiST implements a radix tree for strings.¹⁵ Here the prefix of an inner node is really a prefix, which is common to all the strings in the child nodes.

Pointers to child nodes are marked by the first byte of the values that follow the prefix.

Child nodes store parts of values that follow the prefix and the label. Leaf nodes keep only suffixes.

To reconstruct the full value of an index key in a leaf page, we can concatenate all prefixes and labels, starting from the root node.

Here is an example of a radix tree built over several names:

Operator Class

The text_ops operator class supports comparison operators typically used with ordinal data types, including text strings:

=> SELECT oprname, oprcode::regproc, amopstrategy
FROM pg_am am
  JOIN pg_opclass opc ON opcmethod = am.oid
  JOIN pg_amop amop ON amopfamily = opcfamily
  JOIN pg_operator opr ON opr.oid = amopopr
WHERE amname = 'spgist'
AND opcname = 'text_ops'
ORDER BY amopstrategy;
 oprname |     oprcode     | amopstrategy
---------+-----------------+--------------
 ~<~     | text_pattern_lt |            1
 ~<=~    | text_pattern_le |            2
 =       | texteq          |            3
 ~>=~    | text_pattern_ge |            4
 ~>~     | text_pattern_gt |            5
 <       | text_lt         |           11
 <=      | text_le         |           12
 >=      | text_ge         |           14
 >       | text_gt         |           15
 ^@      | starts_with     |           28
(10 rows)

Regular operators process characters, while operators with tildes deal with bytes. They do not take collation into account (just like the text_pattern_ops operator class for B-tree), so they can be used to speed up search by the LIKE condition: (p. 317)

=> CREATE INDEX tickets_spgist_idx ON tickets
  USING spgist(passenger_name);
=> EXPLAIN (costs off) SELECT *
FROM tickets
WHERE passenger_name LIKE 'IVAN%';
                        QUERY PLAN
-----------------------------------------------------------
 Bitmap Heap Scan on tickets
   Filter: (passenger_name ~~ 'IVAN%'::text)
   -> Bitmap Index Scan on tickets_spgist_idx
       Index Cond: ((passenger_name ~>=~ 'IVAN'::text) AND
       (passenger_name ~<~ 'IVAO'::text))
(5 rows)

For such cases of prefix search, the operator class provides the ^@ operator, which is more suitable: (v. 11)

=> EXPLAIN (costs off) SELECT *
FROM tickets
WHERE passenger_name ^@ 'IVAN';
                     QUERY PLAN
----------------------------------------------------
 Bitmap Heap Scan on tickets
   Recheck Cond: (passenger_name ^@ 'IVAN'::text)
   -> Bitmap Index Scan on tickets_spgist_idx
       Index Cond: (passenger_name ^@ 'IVAN'::text)
(4 rows)

A radix tree representation can sometimes turn out to be much more compact than that of a B-tree, as it does not keep full values: it reconstructs them as required while the tree is being traversed.

Search

Let’s run the following query on the names table:

SELECT * FROM names
WHERE name ~>=~ 'VALERIY'
  AND name ~<~ 'VLADISLAV';

First, the inner consistency function¹⁶ is called on the root to determine the child nodes to descend into. This function concatenates prefix V and labels A and L. The received value VA goes into the query condition; string literals are truncated there, so that their length does not exceed the length of the value being checked: VA ~>=~ 'VA'AND VA ~<~ 'VL'. The condition is satisfied, so the child node with label A needs to be checked. The VL value is checked in the same way. It is also a match, so the node with label L must be checked too.

Now let’s take the node that corresponds to value VA. Its prefix is empty, so for the three child nodes the inner consistency function reconstructs values VAD, VAL, and VAS by concatenating VA received at the previous step and the label. The condition VAD ~>=~ 'VAL' AND VAD ~<~ 'VER' is not true, but the other two values are suitable.

As the tree is being traversed this way, the algorithm filters out non-matching branches and gets to leaf nodes. The leaf consistency function¹⁷ checks whether the value reconstructed during the tree traversal satisfies the query condition. Matching values are returned as the result of an index scan.

Note that although the query uses greater than and less than operators, which are common to B-trees, range search by SP-GiST is much less efficient. In a B-tree, it is enough to descend into a single boundary value of the range and then scan the list of leaf pages.

Insertion

The choice function of operator classes for points can always direct a new value into one of the existing sub-regions (a quadrant or one of the halves). But it is not true for radix trees: a new value may not match any of the existing prefixes, and the inner node has to be split in this case.

Let’s add the name VLADA to an already built tree.

The choice function¹⁸ manages to descend from the root to the next node (V + L), but the remaining part of the value ADA does not match the ADI prefix. The node has to be split in two: one of the resulting nodes will contain the common part of the prefix (AD), while the rest of the prefix will be moved one level down:

Then the choice function is called again on the same node. The prefix now corresponds to the value, but there is no child node with a suitable label (A), so the function decides to create such a node. The final result is shown in the illustration below; the nodes that have been added or modified during the insertion are highlighted.

Properties

I have already described the access method and index-level properties above; they are common to all the classes. Most of the column-level properties also remain the same.

=> SELECT p.name,
  pg_index_column_has_property('tickets_spgist_idx', 1, p.name)
FROM unnest(array[
  'returnable', 'distance_orderable'
]) p(name);
        name        | pg_index_column_has_property
--------------------+------------------------------
 returnable         | t
 distance_orderable | f
(2 rows)

Even though indexed values are not explicitly stored in the tree, index-only scans are supported, since values are reconstructed as the tree is being traversed from the root to leaf nodes.

As for the distance operator, it is not defined for strings, so nearest neighbor search is not provided by this operator class.

27.5 Other Data Types

SP-GiST operator classes are not limited to indexing points and text strings that we have discussed above.

Geometric types. The box_ops¹⁹ operator class implements a quadtree for rectangles. Rectangles are represented by points in a four-dimensional space, so the area is split into sixteen partitions.

The poly_ops class can be used to index polygons. It is a fuzzy operator class: it actually uses bounding boxes instead of polygons, just like box_ops, and then rechecks the result by the table. (v. 11)

Whether to choose GiST or SP-GiST largely depends on the nature of data to be indexed. For example, PostGIS documentation recommends SP-GiST for objects with large overlaps (also known as “spaghetti data”).²⁰

Range types. The quadtree for ranges offers the range_ops operator class.²¹ An interval is defined by a two-dimensional point: the X-axis represents the lower boundary, while the Y-axis represents the upper boundary.

Network address types. For the inet data type, the inet_ops²² operator class implements a radix tree.