index GiST 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 in GiST. One advantage of GiST 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 Project web site and Marcel Kornacker's thesis, Access Methods for Next-Generation Database Systems. The GiST implementation in PostgreSQL is primarily maintained by Teodor Sigaev and Oleg Bartunov, and there is more information on their website. 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. The GiST interface has a high level of abstraction, requiring the access method implementer to only implement the semantics of the data type being accessed. The GiST layer itself takes care of concurrency, logging and searching the tree structure. This extensibility should not be confused with the extensibility of the other standard search trees in terms of the data they can handle. For example, PostgreSQL supports extensible B-trees and hash indexes. That means that you can use PostgreSQL to build a B-tree or hash over any data type you want. But B-trees only support range predicates (<, =, >), and hash indexes only support equality queries. So if you index, say, an image collection with a PostgreSQL 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 a GiST 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 a GiST access method up and running is to implement seven 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 seven methods that an index operator class for GiST must provide: consistent Given a predicate p on a tree page, and a user query, q, this method will return false if it is certain that both p and q cannot be true for a given data item. union This method consolidates information in the tree. Given a set of entries, this function generates a new predicate that is true for all the entries. compress Converts the data item into a format suitable for physical storage in an index page. decompress The reverse of the compress method. Converts the index representation of the data item into a format that can be manipulated by the database. penalty Returns a value indicating the cost of inserting the new entry into a particular branch of the tree. items will be inserted down the path of least penalty in the tree. picksplit When a page split is necessary, this function decides which entries on the page are to stay on the old page, and which are to move to the new page. same Returns true if two entries are identical, false otherwise. The PostgreSQL source distribution includes several examples of index methods implemented using GiST. The core system currently provides R-Tree equivalent functionality for some of the built-in geometric data types (see src/backend/access/gist/gistproc.c). The following contrib modules also contain GiST operator classes: btree_gist B-Tree equivalent functionality for several data types cube Indexing for multidimensional cubes intarray RD-Tree for one-dimensional array of int4 values ltree Indexing for tree-like structures pg_trgm Text similarity using trigram matching seg Indexing for float ranges tsearch2 Full text indexing Usually, replay of the WAL log is sufficient to restore the integrity of a GiST index following a database crash. However, there are some corner cases in which the index state is not fully rebuilt. The index will still be functionally correct, but there might be some performance degradation. When this occurs, the index can be repaired by VACUUMing its table, or by rebuilding the index using REINDEX. In some cases a plain VACUUM is not sufficient, and either VACUUM FULL or REINDEX is needed. The need for one of these procedures is indicated by occurrence of this log message during crash recovery: LOG: index NNN/NNN/NNN needs VACUUM or REINDEX to finish crash recovery or this log message during routine index insertions: LOG: index "FOO" needs VACUUM or REINDEX to finish crash recovery If a plain VACUUM finds itself unable to complete recovery fully, it will return a notice: NOTICE: index "FOO" needs VACUUM FULL or REINDEX to finish crash recovery