I notice that the current GiST docs are pretty crazy. Here's my first
attempt at actually making them useful.
Interestingly enough, I had a chat with Joe Hellerstein while trying to
write this - he was interested in how GiST was going in PostgreSQL and
gave us permission to paraphrase his old GiST site for these docs.
I also had a bit of feedback from Oleg.
I'm sure I've made shocking errors all through this, but I just wanted
to get the ball rolling with respect to getting that awful GiST page
Title: GiST Indexes
Some of the information here is derived from
the University of California, Berkeley, The 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:
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.
Traditionally, implementing a new 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 implementor 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 R-trees. That means
that you can use PostgreSQL to build a B+-tree or R-tree over any data type
you want. But B+-trees only support range predicates (<, =, >), and R-trees
only support n-d range queries (contains, contained, equals).
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 may be useful. However, by using
a GiST based index, you could ask questions such as "find all
images of horses" and "find all over-exposed images".
All it takes to get a GiST access method up and running is to
implement four 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 (a la B+-trees, R-trees, etc.) they're relatively straightforward. In
short, the GiST combines extensibility along with
generality, code reuse, and a clean interface.
There are seven methods required of the access method to use the GiST interface:
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.
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.
Converts the data item into a format suitable for physical storage in the page.
The reverse of the compress method. Converts the page representation
of the data item into a format that can be manipulated by the database.
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.
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.
Returns true if two entries are identical, false otherwise.
The current implementation of GiST withing PostgreSQL
has two major limitations: GiST access is not concurrent and the GiST
interface doesn't allow the development of certain data types, such as digital trees. (See papers
by Aoki et. al)
Solutions to the first of these problems appear in Marcel Kornacker's Thesis, however these ideas
have not yet been put into practice in the PostgreSQL
To see example implementations of index methods implemented using GiST, examine
the following contrib modules:
Indexing for multi-dimensional cubes
RD-Tree for one-dimensional array of int4 values
Indexing for tree-like stuctures
Storage and indexed access for 'float ranges'
tsearch and tsearch2
Full text indexing
---------------------------(end of broadcast)---------------------------
TIP 2: you can get off all lists at once with the unregister command
(send "unregister YourEmailAddressHere" to [EMAIL PROTECTED])