Add SP-GiST (space-partitioned GiST) index access method.

SP-GiST is comparable to GiST in flexibility, but supports non-balanced
partitioned search structures rather than balanced trees.  As described at
PGCon 2011, this new indexing structure can beat GiST in both index build
time and query speed for search problems that it is well matched to.

There are a number of areas that could still use improvement, but at this
point the code seems committable.

Teodor Sigaev and Oleg Bartunov, with considerable revisions by Tom Lane

4 files changed, 31 insertions, 35 deletions

diff --git a/doc/src/sgml/ref/alter_opfamily.sgml b/doc/src/sgml/ref/alter_opfamily.sgml
index c95df95fa2..aad968d284 100644
--- a/doc/src/sgml/ref/alter_opfamily.sgml
+++ b/doc/src/sgml/ref/alter_opfamily.sgml
@@ -144,8 +144,8 @@ ALTER OPERATOR FAMILY <replaceable>name</replaceable> USING <replaceable class="
       and hash functions it is not necessary to specify <replaceable
       class="parameter">op_type</replaceable> since the function's input
       data type(s) are always the correct ones to use.  For B-tree sort
-      support functions and all functions in GiST and GIN operator classes,
-      it is necessary to specify the operand data type(s) the function
+      support functions and all functions in GiST, SP-GiST and GIN operator
+      classes, it is necessary to specify the operand data type(s) the function
       is to be used with.
      </para>
 
@@ -245,8 +245,8 @@ ALTER OPERATOR FAMILY <replaceable>name</replaceable> USING <replaceable class="
    type(s).  The name of the operator or function occupying the slot is not
    mentioned.  Also, for <literal>DROP FUNCTION</> the type(s) to specify
    are the input data type(s) the function is intended to support; for
-   GIN and GiST indexes this might have nothing to do with the actual input
-   argument types of the function.
+   GiST, SP-GiST and GIN indexes this might have nothing to do with the actual
+   input argument types of the function.
   </para>
 
   <para>
diff --git a/doc/src/sgml/ref/create_index.sgml b/doc/src/sgml/ref/create_index.sgml
index e8a7cafa3c..99a7e205a1 100644
--- a/doc/src/sgml/ref/create_index.sgml
+++ b/doc/src/sgml/ref/create_index.sgml
@@ -57,7 +57,7 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ <replaceable class="parameter">name</
 
   <para>
    <productname>PostgreSQL</productname> provides the index methods
-   B-tree, hash, GiST, and GIN.  Users can also define their own index
+   B-tree, hash, GiST, SP-GiST, and GIN.  Users can also define their own index
    methods, but that is fairly complicated.
   </para>
 
@@ -154,8 +154,8 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ <replaceable class="parameter">name</
        <para>
         The name of the index method to be used.  Choices are
         <literal>btree</literal>, <literal>hash</literal>,
-        <literal>gist</literal>, and <literal>gin</>.  The
-        default method is <literal>btree</literal>.
+        <literal>gist</literal>, <literal>spgist</> and <literal>gin</>.
+        The default method is <literal>btree</literal>.
        </para>
       </listitem>
      </varlistentry>
@@ -281,12 +281,11 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ <replaceable class="parameter">name</
    <para>
     The optional <literal>WITH</> clause specifies <firstterm>storage
     parameters</> for the index.  Each index method has its own set of allowed
-    storage parameters.  The B-tree, hash and GiST index methods all accept a
-    single parameter:
+    storage parameters.  The B-tree, hash, GiST and SP-GiST index methods all
+    accept this parameter:
    </para>
 
    <variablelist>
-
    <varlistentry>
     <term><literal>FILLFACTOR</></term>
     <listitem>
@@ -307,7 +306,25 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ <replaceable class="parameter">name</
      </para>
     </listitem>
    </varlistentry>
+   </variablelist>
+
+   <para>
+    GiST indexes additionally accept this parameter:
+   </para>
 
+   <variablelist>
+   <varlistentry>
+    <term><literal>BUFFERING</></term>
+    <listitem>
+    <para>
+     Determines whether the buffering build technique described in
+     <xref linkend="gist-buffering-build"> is used to build the index. With
+     <literal>OFF</> it is disabled, with <literal>ON</> it is enabled, and
+     with <literal>AUTO</> it is initially disabled, but turned on
+     on-the-fly once the index size reaches <xref linkend="guc-effective-cache-size">. The default is <literal>AUTO</>.
+    </para>
+    </listitem>
+   </varlistentry>
    </variablelist>
 
    <para>
@@ -315,7 +332,6 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ <replaceable class="parameter">name</
    </para>
 
    <variablelist>
-
    <varlistentry>
     <term><literal>FASTUPDATE</></term>
     <listitem>
@@ -339,27 +355,6 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ <replaceable class="parameter">name</
     </note>
     </listitem>
    </varlistentry>
-
-   </variablelist>
-   <para>
-    GiST indexes additionally accept parameter:
-   </para>
-
-   <variablelist>
-
-   <varlistentry>
-    <term><literal>BUFFERING</></term>
-    <listitem>
-    <para>
-     Determines whether the buffering build technique described in
-     <xref linkend="gist-buffering-build"> is used to build the index. With
-     <literal>OFF</> it is disabled, with <literal>ON</> it is enabled, and
-     with <literal>AUTO</> it is initially disabled, but turned on
-     on-the-fly once the index size reaches <xref linkend="guc-effective-cache-size">. The default is <literal>AUTO</>.
-    </para>
-    </listitem>
-   </varlistentry>
-
    </variablelist>
   </refsect2>
 
diff --git a/doc/src/sgml/ref/create_opclass.sgml b/doc/src/sgml/ref/create_opclass.sgml
index 78072d9f3c..81b9e538af 100644
--- a/doc/src/sgml/ref/create_opclass.sgml
+++ b/doc/src/sgml/ref/create_opclass.sgml
@@ -172,7 +172,7 @@ CREATE OPERATOR CLASS <replaceable class="parameter">name</replaceable> [ DEFAUL
       the input data type(s) of the function (for B-tree comparison functions
       and hash functions)
       or the class's data type (for B-tree sort support functions and all
-      functions in GiST and GIN operator classes).  These defaults
+      functions in GiST, SP-GiST and GIN operator classes).  These defaults
       are correct, and so <replaceable
       class="parameter">op_type</replaceable> need not be specified in
       <literal>FUNCTION</> clauses, except for the case of a B-tree sort
@@ -232,7 +232,7 @@ CREATE OPERATOR CLASS <replaceable class="parameter">name</replaceable> [ DEFAUL
      <para>
       The data type actually stored in the index.  Normally this is
       the same as the column data type, but some index methods
-      (currently GIN and GiST) allow it to be different.  The
+      (currently GiST and GIN) allow it to be different.  The
       <literal>STORAGE</> clause must be omitted unless the index
       method allows a different type to be used.
      </para>
diff --git a/doc/src/sgml/ref/create_table.sgml b/doc/src/sgml/ref/create_table.sgml
index faff45900c..d7b0fcf73a 100644
--- a/doc/src/sgml/ref/create_table.sgml
+++ b/doc/src/sgml/ref/create_table.sgml
@@ -540,7 +540,8 @@ CREATE [ [ GLOBAL | LOCAL ] { TEMPORARY | TEMP } | UNLOGGED ] TABLE [ IF NOT EXI
       cannot be used.  Although it's allowed, there is little point in using
       B-tree or hash indexes with an exclusion constraint, because this
       does nothing that an ordinary unique constraint doesn't do better.
-      So in practice the access method will always be <acronym>GiST</>.
+      So in practice the access method will always be <acronym>GiST</> or
+      <acronym>SP-GiST</>.
      </para>
 
      <para>