62.2. GiST Indexes#
62.2.1. Introduction#
GiST stands for Generalized Search Tree. It is a balanced, tree-structured access method, that acts as a base template in which to implement arbitrary indexing schemes. B-trees, R-trees and many other indexing schemes can be implemented inGiST.
One advantage ofGiST is that it allows the development of custom data types with the appropriate access methods, by an expert in the domain of the data type, rather than a database expert.
Some of the information here is derived from the University of California at Berkeley's GiST Indexing Projectweb site and Marcel Kornacker's thesis, Access Methods for Next-Generation Database Systems. TheGiST implementation inPostgres Pro is primarily maintained by Teodor Sigaev and Oleg Bartunov, and there is more information on theirweb site.
62.2.2. Built-in Operator Classes#
The corePostgres Pro distribution includes theGiST operator classes shown inTable 62.1. (Some of the optional modules described inAppendix F provide additionalGiST operator classes.)
Table 62.1. Built-inGiST Operator Classes
Name | Indexable Operators | Ordering Operators |
---|---|---|
box_ops | << (box, box) | <-> (box, point) |
&< (box, box) | ||
&& (box, box) | ||
&> (box, box) | ||
>> (box, box) | ||
~= (box, box) | ||
@> (box, box) | ||
<@ (box, box) | ||
&<| (box, box) | ||
<<| (box, box) | ||
|>> (box, box) | ||
|&> (box, box) | ||
circle_ops | << (circle, circle) | <-> (circle, point) |
&< (circle, circle) | ||
&> (circle, circle) | ||
>> (circle, circle) | ||
<@ (circle, circle) | ||
@> (circle, circle) | ||
~= (circle, circle) | ||
&& (circle, circle) | ||
|>> (circle, circle) | ||
<<| (circle, circle) | ||
&<| (circle, circle) | ||
|&> (circle, circle) | ||
inet_ops | << (inet, inet) | |
<<= (inet, inet) | ||
>> (inet, inet) | ||
>>= (inet, inet) | ||
= (inet, inet) | ||
<> (inet, inet) | ||
< (inet, inet) | ||
<= (inet, inet) | ||
> (inet, inet) | ||
>= (inet, inet) | ||
&& (inet, inet) | ||
multirange_ops | = (anymultirange, anymultirange) | |
&& (anymultirange, anymultirange) | ||
&& (anymultirange, anyrange) | ||
@> (anymultirange, anyelement) | ||
@> (anymultirange, anymultirange) | ||
@> (anymultirange, anyrange) | ||
<@ (anymultirange, anymultirange) | ||
<@ (anymultirange, anyrange) | ||
<< (anymultirange, anymultirange) | ||
<< (anymultirange, anyrange) | ||
>> (anymultirange, anymultirange) | ||
>> (anymultirange, anyrange) | ||
&< (anymultirange, anymultirange) | ||
&< (anymultirange, anyrange) | ||
&> (anymultirange, anymultirange) | ||
&> (anymultirange, anyrange) | ||
-|- (anymultirange, anymultirange) | ||
-|- (anymultirange, anyrange) | ||
point_ops | |>> (point, point) | <-> (point, point) |
<< (point, point) | ||
>> (point, point) | ||
<<| (point, point) | ||
~= (point, point) | ||
<@ (point, box) | ||
<@ (point, polygon) | ||
<@ (point, circle) | ||
poly_ops | << (polygon, polygon) | <-> (polygon, point) |
&< (polygon, polygon) | ||
&> (polygon, polygon) | ||
>> (polygon, polygon) | ||
<@ (polygon, polygon) | ||
@> (polygon, polygon) | ||
~= (polygon, polygon) | ||
&& (polygon, polygon) | ||
<<| (polygon, polygon) | ||
&<| (polygon, polygon) | ||
|&> (polygon, polygon) | ||
|>> (polygon, polygon) | ||
range_ops | = (anyrange, anyrange) | |
&& (anyrange, anyrange) | ||
&& (anyrange, anymultirange) | ||
@> (anyrange, anyelement) | ||
@> (anyrange, anyrange) | ||
@> (anyrange, anymultirange) | ||
<@ (anyrange, anyrange) | ||
<@ (anyrange, anymultirange) | ||
<< (anyrange, anyrange) | ||
<< (anyrange, anymultirange) | ||
>> (anyrange, anyrange) | ||
>> (anyrange, anymultirange) | ||
&< (anyrange, anyrange) | ||
&< (anyrange, anymultirange) | ||
&> (anyrange, anyrange) | ||
&> (anyrange, anymultirange) | ||
-|- (anyrange, anyrange) | ||
-|- (anyrange, anymultirange) | ||
tsquery_ops | <@ (tsquery, tsquery) | |
@> (tsquery, tsquery) | ||
tsvector_ops | @@ (tsvector, tsquery) |
For historical reasons, theinet_ops
operator class is not the default class for typesinet
andcidr
. To use it, mention the class name inCREATE INDEX
, for example
CREATE INDEX ON my_table USING GIST (my_inet_column inet_ops);
Traditionally, implementing a new index access method meant a lot of difficult work. It was necessary to understand the inner workings of the database, such as the lock manager and Write-Ahead Log. TheGiST interface has a high level of abstraction, requiring the access method implementer only to implement the semantics of the data type being accessed. TheGiST layer itself takes care of concurrency, logging and searching the tree structure.
So if you index, say, an image collection with aPostgres Pro B-tree, you can only issue queries such as“is imagex equal to imagey”,“is imagex less than imagey” and“is imagex greater than imagey”. Depending on how you define“equals”,“less than” and“greater than” in this context, this could be useful. However, by using aGiST based index, you could create ways to ask domain-specific questions, perhaps“find all images of horses” or“find all over-exposed images”.
All it takes to get aGiST access method up and running is to implement several user-defined methods, which define the behavior of keys in the tree. Of course these methods have to be pretty fancy to support fancy queries, but for all the standard queries (B-trees, R-trees, etc.) they're relatively straightforward. In short,GiST combines extensibility along with generality, code reuse, and a clean interface.
There are five methods that an index operator class forGiST must provide, and six that are optional. Correctness of the index is ensured by proper implementation of thesame
,consistent
andunion
methods, while efficiency (size and speed) of the index will depend on thepenalty
andpicksplit
methods. Two optional methods arecompress
anddecompress
, which allow an index to have internal tree data of a different type than the data it indexes. The leaves are to be of the indexed data type, while the other tree nodes can be of any C struct (but you still have to followPostgres Pro data type rules here, see aboutvarlena
for variable sized data). If the tree's internal data type exists at the SQL level, theSTORAGE
option of theCREATE OPERATOR CLASS
command can be used. The optional eighth method isdistance
, which is needed if the operator class wishes to support ordered scans (nearest-neighbor searches). The optional ninth methodfetch
is needed if the operator class wishes to support index-only scans, except when thecompress
method is omitted. The optional tenth methodoptions
is needed if the operator class has user-specified parameters. The optional eleventh methodsortsupport
is used to speed up building aGiST index.
consistent
Given an index entry
p
and a query valueq
, this function determines whether the index entry is“consistent” with the query; that is, could the predicate“indexed_column
indexable_operator
q
” be true for any row represented by the index entry? For a leaf index entry this is equivalent to testing the indexable condition, while for an internal tree node this determines whether it is necessary to scan the subtree of the index represented by the tree node. When the result istrue
, arecheck
flag must also be returned. This indicates whether the predicate is certainly true or only possibly true. Ifrecheck
=false
then the index has tested the predicate condition exactly, whereas ifrecheck
=true
the row is only a candidate match. In that case the system will automatically evaluate theindexable_operator
against the actual row value to see if it is really a match. This convention allowsGiST to support both lossless and lossy index structures.TheSQL declaration of the function must look like this:
CREATE OR REPLACE FUNCTION my_consistent(internal, data_type, smallint, oid, internal)RETURNS boolAS 'MODULE_PATHNAME'LANGUAGE C STRICT;
And the matching code in the C module could then follow this skeleton:
PG_FUNCTION_INFO_V1(my_consistent);Datummy_consistent(PG_FUNCTION_ARGS){ GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); data_type *query = PG_GETARG_DATA_TYPE_P(1); StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2); /* Oid subtype = PG_GETARG_OID(3); */ bool *recheck = (bool *) PG_GETARG_POINTER(4); data_type *key = DatumGetDataType(entry->key); bool retval; /* * determine return value as a function of strategy, key and query. * * Use GIST_LEAF(entry) to know where you're called in the index tree, * which comes handy when supporting the = operator for example (you could * check for non empty union() in non-leaf nodes and equality in leaf * nodes). */ *recheck = true; /* or false if check is exact */ PG_RETURN_BOOL(retval);}
union
TheSQL declaration of the function must look like this:
CREATE OR REPLACE FUNCTION my_union(internal, internal)RETURNS storage_typeAS 'MODULE_PATHNAME'LANGUAGE C STRICT;
And the matching code in the C module could then follow this skeleton:
PG_FUNCTION_INFO_V1(my_union);Datummy_union(PG_FUNCTION_ARGS){ GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0); GISTENTRY *ent = entryvec->vector; data_type *out, *tmp, *old; int numranges, i = 0; numranges = entryvec->n; tmp = DatumGetDataType(ent[0].key); out = tmp; if (numranges == 1) { out = data_type_deep_copy(tmp); PG_RETURN_DATA_TYPE_P(out); } for (i = 1; i < numranges; i++) { old = out; tmp = DatumGetDataType(ent[i].key); out = my_union_implementation(out, tmp); } PG_RETURN_DATA_TYPE_P(out);}
As you can see, in this skeleton we're dealing with a data type where
union(X, Y, Z) = union(union(X, Y), Z)
. It's easy enough to support data types where this is not the case, by implementing the proper union algorithm in thisGiST support method.compress
TheSQL declaration of the function must look like this:
CREATE OR REPLACE FUNCTION my_compress(internal)RETURNS internalAS 'MODULE_PATHNAME'LANGUAGE C STRICT;
And the matching code in the C module could then follow this skeleton:
PG_FUNCTION_INFO_V1(my_compress);Datummy_compress(PG_FUNCTION_ARGS){ GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); GISTENTRY *retval; if (entry->leafkey) { /* replace entry->key with a compressed version */ compressed_data_type *compressed_data = palloc(sizeof(compressed_data_type)); /* fill *compressed_data from entry->key ... */ retval = palloc(sizeof(GISTENTRY)); gistentryinit(*retval, PointerGetDatum(compressed_data), entry->rel, entry->page, entry->offset, FALSE); } else { /* typically we needn't do anything with non-leaf entries */ retval = entry; } PG_RETURN_POINTER(retval);}
decompress
TheSQL declaration of the function must look like this:
CREATE OR REPLACE FUNCTION my_decompress(internal)RETURNS internalAS 'MODULE_PATHNAME'LANGUAGE C STRICT;
And the matching code in the C module could then follow this skeleton:
PG_FUNCTION_INFO_V1(my_decompress);Datummy_decompress(PG_FUNCTION_ARGS){ PG_RETURN_POINTER(PG_GETARG_POINTER(0));}
penalty
TheSQL declaration of the function must look like this:
CREATE OR REPLACE FUNCTION my_penalty(internal, internal, internal)RETURNS internalAS 'MODULE_PATHNAME'LANGUAGE C STRICT; -- in some cases penalty functions need not be strict
And the matching code in the C module could then follow this skeleton:
PG_FUNCTION_INFO_V1(my_penalty);Datummy_penalty(PG_FUNCTION_ARGS){ GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0); GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1); float *penalty = (float *) PG_GETARG_POINTER(2); data_type *orig = DatumGetDataType(origentry->key); data_type *new = DatumGetDataType(newentry->key); *penalty = my_penalty_implementation(orig, new); PG_RETURN_POINTER(penalty);}
picksplit
TheSQL declaration of the function must look like this:
CREATE OR REPLACE FUNCTION my_picksplit(internal, internal)RETURNS internalAS 'MODULE_PATHNAME'LANGUAGE C STRICT;
And the matching code in the C module could then follow this skeleton:
PG_FUNCTION_INFO_V1(my_picksplit);Datummy_picksplit(PG_FUNCTION_ARGS){ GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0); GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1); OffsetNumber maxoff = entryvec->n - 1; GISTENTRY *ent = entryvec->vector; int i, nbytes; OffsetNumber *left, *right; data_type *tmp_union; data_type *unionL; data_type *unionR; GISTENTRY **raw_entryvec; maxoff = entryvec->n - 1; nbytes = (maxoff + 1) * sizeof(OffsetNumber); v->spl_left = (OffsetNumber *) palloc(nbytes); left = v->spl_left; v->spl_nleft = 0; v->spl_right = (OffsetNumber *) palloc(nbytes); right = v->spl_right; v->spl_nright = 0; unionL = NULL; unionR = NULL; /* Initialize the raw entry vector. */ raw_entryvec = (GISTENTRY **) malloc(entryvec->n * sizeof(void *)); for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i)) raw_entryvec[i] = &(entryvec->vector[i]); for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i)) { int real_index = raw_entryvec[i] - entryvec->vector; tmp_union = DatumGetDataType(entryvec->vector[real_index].key); Assert(tmp_union != NULL); /* * Choose where to put the index entries and update unionL and unionR * accordingly. Append the entries to either v->spl_left or * v->spl_right, and care about the counters. */ if (my_choice_is_left(unionL, curl, unionR, curr)) { if (unionL == NULL) unionL = tmp_union; else unionL = my_union_implementation(unionL, tmp_union); *left = real_index; ++left; ++(v->spl_nleft); } else { /* * Same on the right */ } } v->spl_ldatum = DataTypeGetDatum(unionL); v->spl_rdatum = DataTypeGetDatum(unionR); PG_RETURN_POINTER(v);}
Like
penalty
, thepicksplit
function is crucial to good performance of the index. Designing suitablepenalty
andpicksplit
implementations is where the challenge of implementing well-performingGiST indexes lies.same
TheSQL declaration of the function must look like this:
CREATE OR REPLACE FUNCTION my_same(storage_type, storage_type, internal)RETURNS internalAS 'MODULE_PATHNAME'LANGUAGE C STRICT;
And the matching code in the C module could then follow this skeleton:
PG_FUNCTION_INFO_V1(my_same);Datummy_same(PG_FUNCTION_ARGS){ prefix_range *v1 = PG_GETARG_PREFIX_RANGE_P(0); prefix_range *v2 = PG_GETARG_PREFIX_RANGE_P(1); bool *result = (bool *) PG_GETARG_POINTER(2); *result = my_eq(v1, v2); PG_RETURN_POINTER(result);}
distance
TheSQL declaration of the function must look like this:
CREATE OR REPLACE FUNCTION my_distance(internal, data_type, smallint, oid, internal)RETURNS float8AS 'MODULE_PATHNAME'LANGUAGE C STRICT;
And the matching code in the C module could then follow this skeleton:
PG_FUNCTION_INFO_V1(my_distance);Datummy_distance(PG_FUNCTION_ARGS){ GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); data_type *query = PG_GETARG_DATA_TYPE_P(1); StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2); /* Oid subtype = PG_GETARG_OID(3); */ /* bool *recheck = (bool *) PG_GETARG_POINTER(4); */ data_type *key = DatumGetDataType(entry->key); double retval; /* * determine return value as a function of strategy, key and query. */ PG_RETURN_FLOAT8(retval);}
The arguments to the
distance
function are identical to the arguments of theconsistent
function.fetch
TheSQL declaration of the function must look like this:
CREATE OR REPLACE FUNCTION my_fetch(internal)RETURNS internalAS 'MODULE_PATHNAME'LANGUAGE C STRICT;
The matching code in the C module could then follow this skeleton:
PG_FUNCTION_INFO_V1(my_fetch);Datummy_fetch(PG_FUNCTION_ARGS){ GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); input_data_type *in = DatumGetPointer(entry->key); fetched_data_type *fetched_data; GISTENTRY *retval; retval = palloc(sizeof(GISTENTRY)); fetched_data = palloc(sizeof(fetched_data_type)); /* * Convert 'fetched_data' into the a Datum of the original datatype. */ /* fill *retval from fetched_data. */ gistentryinit(*retval, PointerGetDatum(converted_datum), entry->rel, entry->page, entry->offset, FALSE); PG_RETURN_POINTER(retval);}
options
Allows definition of user-visible parameters that control operator class behavior.
TheSQL declaration of the function must look like this:
CREATE OR REPLACE FUNCTION my_options(internal)RETURNS voidAS 'MODULE_PATHNAME'LANGUAGE C STRICT;
typedef enum MyEnumType{ MY_ENUM_ON, MY_ENUM_OFF, MY_ENUM_AUTO} MyEnumType;typedef struct{ int32 vl_len_; /* varlena header (do not touch directly!) */ int int_param; /* integer parameter */ double real_param; /* real parameter */ MyEnumType enum_param; /* enum parameter */ int str_param; /* string parameter */} MyOptionsStruct;/* String representation of enum values */static relopt_enum_elt_def myEnumValues[] ={ {"on", MY_ENUM_ON}, {"off", MY_ENUM_OFF}, {"auto", MY_ENUM_AUTO}, {(const char *) NULL} /* list terminator */};static char *str_param_default = "default";/* * Sample validator: checks that string is not longer than 8 bytes. */static voidvalidate_my_string_relopt(const char *value){ if (strlen(value) > 8) ereport(ERROR, (errcode(ERRCODE_INVALID_PARAMETER_VALUE), errmsg("str_param must be at most 8 bytes")));}/* * Sample filler: switches characters to lower case. */static Sizefill_my_string_relopt(const char *value, void *ptr){ char *tmp = str_tolower(value, strlen(value), DEFAULT_COLLATION_OID); int len = strlen(tmp); if (ptr) strcpy((char *) ptr, tmp); pfree(tmp); return len + 1;}PG_FUNCTION_INFO_V1(my_options);Datummy_options(PG_FUNCTION_ARGS){ local_relopts *relopts = (local_relopts *) PG_GETARG_POINTER(0); init_local_reloptions(relopts, sizeof(MyOptionsStruct)); add_local_int_reloption(relopts, "int_param", "integer parameter", 100, 0, 1000000, offsetof(MyOptionsStruct, int_param)); add_local_real_reloption(relopts, "real_param", "real parameter", 1.0, 0.0, 1000000.0, offsetof(MyOptionsStruct, real_param)); add_local_enum_reloption(relopts, "enum_param", "enum parameter", myEnumValues, MY_ENUM_ON, "Valid values are: \"on\", \"off\" and \"auto\".", offsetof(MyOptionsStruct, enum_param)); add_local_string_reloption(relopts, "str_param", "string parameter", str_param_default, &validate_my_string_relopt, &fill_my_string_relopt, offsetof(MyOptionsStruct, str_param)); PG_RETURN_VOID();}PG_FUNCTION_INFO_V1(my_compress);Datummy_compress(PG_FUNCTION_ARGS){ int int_param = 100; double real_param = 1.0; MyEnumType enum_param = MY_ENUM_ON; char *str_param = str_param_default; /* * Normally, when opclass contains 'options' method, then options are always * passed to support functions. However, if you add 'options' method to * existing opclass, previously defined indexes have no options, so the * check is required. */ if (PG_HAS_OPCLASS_OPTIONS()) { MyOptionsStruct *options = (MyOptionsStruct *) PG_GET_OPCLASS_OPTIONS(); int_param = options->int_param; real_param = options->real_param; enum_param = options->enum_param; str_param = GET_STRING_RELOPTION(options, str_param); } /* the rest implementation of support function */}
Since the representation of the key inGiST is flexible, it may depend on user-specified parameters. For instance, the length of key signature may be specified. See
gtsvector_options()
for example.sortsupport
TheSQL declaration of the function must look like this:
CREATE OR REPLACE FUNCTION my_sortsupport(internal)RETURNS voidAS 'MODULE_PATHNAME'LANGUAGE C STRICT;
The argument is a pointer to a
SortSupport
struct. At a minimum, the function must fill in its comparator field. The comparator takes three arguments: two Datums to compare, and a pointer to theSortSupport
struct. The Datums are the two indexed values in the format that they are stored in the index; that is, in the format returned by thecompress
method. The full API is defined insrc/include/utils/sortsupport.h
.The matching code in the C module could then follow this skeleton:
PG_FUNCTION_INFO_V1(my_sortsupport);static intmy_fastcmp(Datum x, Datum y, SortSupport ssup){ /* establish order between x and y by computing some sorting value z */ int z1 = ComputeSpatialCode(x); int z2 = ComputeSpatialCode(y); return z1 == z2 ? 0 : z1 > z2 ? 1 : -1;}Datummy_sortsupport(PG_FUNCTION_ARGS){ SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0); ssup->comparator = my_fastcmp; PG_RETURN_VOID();}
All the GiST support methods are normally called in short-lived memory contexts; that is,CurrentMemoryContext
will get reset after each tuple is processed. It is therefore not very important to worry about pfree'ing everything you palloc. However, in some cases it's useful for a support method to cache data across repeated calls. To do that, allocate the longer-lived data infcinfo->flinfo->fn_mcxt
, and keep a pointer to it infcinfo->flinfo->fn_extra
. Such data will survive for the life of the index operation (e.g., a single GiST index scan, index build, or index tuple insertion). Be careful to pfree the previous value when replacing afn_extra
value, or the leak will accumulate for the duration of the operation.
62.2.4. Implementation#
62.2.4.1. GiST Index Build Methods#
The simplest way to build a GiST index is just to insert all the entries, one by one. This tends to be slow for large indexes, because if the index tuples are scattered across the index and the index is large enough to not fit in cache, a lot of random I/O will be needed.Postgres Pro supports two alternative methods for initial build of a GiST index:sorted andbuffered modes.
The sorted method is only available if each of the opclasses used by the index provides asortsupport
function, as described inSection 62.2.3. If they do, this method is usually the best, so it is used by default.
The buffered method works by not inserting tuples directly into the index right away. It can dramatically reduce the amount of random I/O needed for non-ordered data sets. For well-ordered data sets the benefit is smaller or non-existent, because only a small number of pages receive new tuples at a time, and those pages fit in cache even if the index as a whole does not.
The buffered method needs to call thepenalty
function more often than the simple method does, which consumes some extra CPU resources. Also, the buffers need temporary disk space, up to the size of the resulting index. Buffering can also influence the quality of the resulting index, in both positive and negative directions. That influence depends on various factors, like the distribution of the input data and the operator class implementation.
If sorting is not possible, then by default a GiST index build switches to the buffering method when the index size reacheseffective_cache_size. Buffering can be manually forced or prevented by thebuffering
parameter to the CREATE INDEX command. The default behavior is good for most cases, but turning buffering off might speed up the build somewhat if the input data is ordered.
62.2.5. Examples#
ThePostgres Pro core system currently provides text search support (indexing fortsvector
andtsquery
) as well as R-Tree equivalent functionality for some of the built-in geometric data types. The followingcontrib
modules also containGiST operator classes: