GiST improvements:

[postgresql] / doc / src / sgml / gist.sgml

<!--
$PostgreSQL: pgsql/doc/src/sgml/gist.sgml,v 1.18 2005/05/17 00:59:30 neilc Exp $
-->

<chapter id="GiST">
<title>GiST Indexes</title>

<sect1 id="intro">
 <title>Introduction</title>

 <para>
   <indexterm>
    <primary>index</primary>
    <secondary>GiST</secondary>
   </indexterm>
   <indexterm>
    <primary>GiST</primary>
    <see>index</see>
   </indexterm>
   <acronym>GiST</acronym> 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 <acronym>GiST</acronym>.
 </para>

 <para>
  One advantage of <acronym>GiST</acronym> 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.
 </para>

  <para>
    Some of the information here is derived from the University of California at
    Berkeley's GiST Indexing Project<ulink
    url="http://gist.cs.berkeley.edu/">web site</ulink> and 
    <ulink url="http://citeseer.nj.nec.com/448594.html">
    Marcel Kornacker's thesis, Access Methods for Next-Generation Database Systems
    </ulink>.   The <acronym>GiST</acronym>
    implementation in <productname>PostgreSQL</productname> is primarily
    maintained by Teodor Sigaev and Oleg Bartunov, and there is more
    information on their<ulink url="http://www.sai.msu.su/~megera/postgres/gist/">
    website</ulink>.
  </para>

</sect1>

<sect1 id="extensibility">
 <title>Extensibility</title>

 <para>
   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
   <acronym>GiST</acronym> interface has a high level of abstraction,
   requiring the access method implementor to only implement the semantics of
   the data type being accessed.  The <acronym>GiST</acronym> layer itself
   takes care of concurrency, logging and searching the tree structure.
 </para>
 
 <para>
   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, <productname>PostgreSQL</productname> supports extensible B+-trees
   and R-trees. That means that you can use
   <productname>PostgreSQL</productname> to build a B+-tree or R-tree over any
   data type you want. But B+-trees only support range predicates
   (<literal>&lt;</literal>, <literal>=</literal>, <literal>&gt;</literal>),
   and R-trees only support n-D range queries (contains, contained, equals).
 </para>
 
 <para>
   So if you index, say, an image collection with a
   <productname>PostgreSQL</productname> B+-tree, you can only issue queries
   such as <quote>is imagex equal to imagey</quote>, <quote>is imagex less
   than imagey</quote> and <quote>is imagex greater than imagey</quote>?
   Depending on how you define <quote>equals</quote>, <quote>less than</quote>
   and <quote>greater than</quote> in this context, this could be useful.
   However, by using a <acronym>GiST</acronym> based index, you could create
   ways to ask domain-specific questions, perhaps <quote>find all images of
   horses</quote> or <quote>find all over-exposed images</quote>.
 </para>

 <para>
   All it takes to get a <acronym>GiST</acronym> 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,
   <acronym>GiST</acronym> combines extensibility along with generality, code
   reuse, and a clean interface.
  </para>

</sect1>

<sect1 id="implementation">
 <title>Implementation</title>
 
 <para>
   There are seven methods that an index operator class for
   <acronym>GiST</acronym> must provide:
 </para>

 <variablelist>
    <varlistentry>
     <term>consistent</term>
     <listitem>
      <para>
       Given a predicate <literal>p</literal> on a tree page, and a user
       query, <literal>q</literal>, this method will return false if it is
       certain that both <literal>p</literal> and <literal>q</literal> cannot
       be true for a given data item.
      </para>
     </listitem>
    </varlistentry>

    <varlistentry>
     <term>union</term>
     <listitem>
      <para>
       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.
      </para>
     </listitem>
    </varlistentry>

    <varlistentry>
     <term>compress</term>
     <listitem>
      <para>
       Converts the data item into a format suitable for physical storage in
       an index page.
      </para>
     </listitem>
    </varlistentry>

    <varlistentry>
     <term>decompress</term>
     <listitem>
      <para>
       The reverse of the <function>compress</function> method.  Converts the
       index representation of the data item into a format that can be
       manipulated by the database.
      </para>
     </listitem>
    </varlistentry>

    <varlistentry>
     <term>penalty</term>
     <listitem>
      <para>
       Returns a value indicating the <quote>cost</quote> of inserting the new
       entry into a particular branch of the tree.  items will be inserted
       down the path of least <function>penalty</function> in the tree.
      </para>
     </listitem>
    </varlistentry>

    <varlistentry>
     <term>picksplit</term>
     <listitem>
      <para>
       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.
      </para>
     </listitem>
    </varlistentry>

    <varlistentry>
     <term>same</term>
     <listitem>
      <para>
       Returns true if two entries are identical, false otherwise.
      </para>
     </listitem>
    </varlistentry>

  </variablelist>

</sect1>

<sect1 id="limitations">
 <title>Limitations</title>

 <para>
  The current implementation of <acronym>GiST</acronym> within
  <productname>PostgreSQL</productname> has some major limitations:
  <acronym>GiST</acronym> access is not concurrent; the
  <acronym>GiST</acronym> interface doesn't allow the development of certain
  data types, such as digital trees (see papers by Aoki et al); and there
  is not yet any support for write-ahead logging of updates in
  <acronym>GiST</acronym> indexes.
 </para>

 <para>
  Solutions to the concurrency problems appear in Marcel Kornacker's
  thesis; however these ideas have not yet been put into practice in the
  <productname>PostgreSQL</productname> implementation.
 </para>

 <para>
  The lack of write-ahead logging is just a small matter of programming,
  but since it isn't done yet, a crash could render a <acronym>GiST</acronym>
  index inconsistent, forcing a <command>REINDEX</command>.
 </para>

</sect1>

<sect1 id="examples">
 <title>Examples</title>

 <para>
  To see example implementations of index methods implemented using
  <acronym>GiST</acronym>, examine the following contrib modules:
 </para>
 
 <variablelist>
  <varlistentry>
   <term>btree_gist</term>
   <listitem>
    <para>B-Tree</para>
   </listitem>
  </varlistentry>

  <varlistentry>
   <term>cube</term>
   <listitem>
    <para>Indexing for multi-dimensional cubes</para>
   </listitem>
  </varlistentry>

  <varlistentry>
   <term>intarray</term>
   <listitem>
    <para>RD-Tree for one-dimensional array of int4 values</para>
   </listitem>
  </varlistentry>

  <varlistentry>
   <term>ltree</term>
   <listitem>
    <para>Indexing for tree-like stuctures</para>
   </listitem>
  </varlistentry>

  <varlistentry>
   <term>rtree_gist</term>
   <listitem>
    <para>R-Tree</para>
   </listitem>
  </varlistentry>

  <varlistentry>
   <term>seg</term>
   <listitem>
    <para>Storage and indexed access for <quote>float ranges</quote></para>
   </listitem>
  </varlistentry>

  <varlistentry>
   <term>tsearch and tsearch2</term>
   <listitem>
    <para>Full text indexing</para>
   </listitem>
  </varlistentry>
 </variablelist>

</sect1>

</chapter>