Add external documentation for KNNGIST.

4 files changed, 144 insertions, 20 deletions

diff --git a/doc/src/sgml/gist.sgml b/doc/src/sgml/gist.sgml
index 74afae69f15..b8cb2914670 100644
--- a/doc/src/sgml/gist.sgml
+++ b/doc/src/sgml/gist.sgml
@@ -78,7 +78,7 @@
 
  <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
+   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,
@@ -93,12 +93,13 @@
 
  <para>
    There are seven methods that an index operator class for
-   <acronym>GiST</acronym> must provide. Correctness of the index is ensured
+   <acronym>GiST</acronym> must provide, and an eighth that is optional.
+   Correctness of the index is ensured
    by proper implementation of the <function>same</>, <function>consistent</>
    and <function>union</> methods, while efficiency (size and speed) of the
    index will depend on the <function>penalty</> and <function>picksplit</>
    methods.
-   The remaining two methods are <function>compress</> and
+   The remaining two basic methods are <function>compress</> and
    <function>decompress</>, 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
@@ -106,6 +107,9 @@
    see about <literal>varlena</> for variable sized data). If the tree's
    internal data type exists at the SQL level, the <literal>STORAGE</> option
    of the <command>CREATE OPERATOR CLASS</> command can be used.
+   The optional eighth method is <function>distance</>, which is needed
+   if the operator class wishes to support ordered scans (nearest-neighbor
+   searches).
  </para>
 
  <variablelist>
@@ -567,6 +571,73 @@ my_same(PG_FUNCTION_ARGS)
      </listitem>
     </varlistentry>
 
+    <varlistentry>
+     <term><function>distance</></term>
+     <listitem>
+      <para>
+       Given an index entry <literal>p</> and a query value <literal>q</>,
+       this function determines the index entry's
+       <quote>distance</> from the query value.  This function must be
+       supplied if the operator class contains any ordering operators.
+       A query using the ordering operator will be implemented by returning
+       index entries with the smallest <quote>distance</> values first,
+       so the results must be consistent with the operator's semantics.
+       For a leaf index entry the result just represents the distance to
+       the index entry; for an internal tree node, the result must be the
+       smallest distance that any child entry could have.
+      </para>
+
+      <para>
+        The <acronym>SQL</> declaration of the function must look like this:
+
+<programlisting>
+CREATE OR REPLACE FUNCTION my_distance(internal, data_type, smallint, oid)
+RETURNS float8
+AS 'MODULE_PATHNAME'
+LANGUAGE C STRICT;
+</programlisting>
+
+        And the matching code in the C module could then follow this skeleton:
+
+<programlisting>
+Datum       my_distance(PG_FUNCTION_ARGS);
+PG_FUNCTION_INFO_V1(my_distance);
+
+Datum
+my_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); */
+    data_type  *key = DatumGetDataType(entry-&gt;key);
+    double      retval;
+
+    /*
+     * determine return value as a function of strategy, key and query.
+     */
+
+    PG_RETURN_FLOAT8(retval);
+}
+</programlisting>
+
+       The arguments to the <function>distance</> function are identical to
+       the arguments of the <function>consistent</> function, except that no
+       recheck flag is used.  The distance to a leaf index entry must always
+       be determined exactly, since there is no way to re-order the tuples
+       once they are returned.  Some approximation is allowed when determining
+       the distance to an internal tree node, so long as the result is never
+       greater than any child's actual distance.  Thus, for example, distance
+       to a bounding box is usually sufficient in geometric applications.  The
+       result value can be any finite <type>float8</> value.  (Infinity and
+       minus infinity are used internally to handle cases such as nulls, so it
+       is not recommended that <function>distance</> functions return these
+       values.)
+      </para>
+
+     </listitem>
+    </varlistentry>
+
   </variablelist>
 
 </sect1>
diff --git a/doc/src/sgml/indexam.sgml b/doc/src/sgml/indexam.sgml
index d0905eb3e28..c4eb59f7be7 100644
--- a/doc/src/sgml/indexam.sgml
+++ b/doc/src/sgml/indexam.sgml
@@ -505,11 +505,31 @@ amrestrpos (IndexScanDesc scan);
 
   <para>
    Some access methods return index entries in a well-defined order, others
-   do not.  If entries are returned in sorted order, the access method should
-   set <structname>pg_am</>.<structfield>amcanorder</> true to indicate that
-   it supports ordered scans.
-   All such access methods must use btree-compatible strategy numbers for
-   their equality and ordering operators.
+   do not.  There are actually two different ways that an access method can
+   support sorted output:
+
+    <itemizedlist>
+     <listitem>
+      <para>
+       Access methods that always return entries in the natural ordering
+       of their data (such as btree) should set
+       <structname>pg_am</>.<structfield>amcanorder</> to true.
+       Currently, such access methods must use btree-compatible strategy
+       numbers for their equality and ordering operators.
+      </para>
+     </listitem>
+     <listitem>
+      <para>
+       Access methods that support ordering operators should set
+       <structname>pg_am</>.<structfield>amcanorderbyop</> to true.
+       This indicates that the index is capable of returning entries in
+       an order satisfying <literal>ORDER BY</> <replaceable>index_key</>
+       <replaceable>operator</> <replaceable>constant</>.  Scan modifiers
+       of that form can be passed to <function>amrescan</> as described
+       previously.
+      </para>
+     </listitem>
+    </itemizedlist>
   </para>
 
   <para>
@@ -521,7 +541,7 @@ amrestrpos (IndexScanDesc scan);
    the normal front-to-back direction, so <function>amgettuple</> must return
    the last matching tuple in the index, rather than the first one as it
    normally would.  (This will only occur for access
-   methods that advertise they support ordered scans.)  After the
+   methods that set <structfield>amcanorder</> to true.)  After the
    first call, <function>amgettuple</> must be prepared to advance the scan in
    either direction from the most recently returned entry.  (But if
    <structname>pg_am</>.<structfield>amcanbackward</> is false, all subsequent
@@ -563,7 +583,8 @@ amrestrpos (IndexScanDesc scan);
    tuples at once and marking or restoring scan positions isn't
    supported. Secondly, the tuples are returned in a bitmap which doesn't
    have any specific ordering, which is why <function>amgetbitmap</> doesn't
-   take a <literal>direction</> argument.  Finally, <function>amgetbitmap</>
+   take a <literal>direction</> argument.  (Ordering operators will never be
+   supplied for such a scan, either.)  Finally, <function>amgetbitmap</>
    does not guarantee any locking of the returned tuples, with implications
    spelled out in <xref linkend="index-locking">.
   </para>
diff --git a/doc/src/sgml/indices.sgml b/doc/src/sgml/indices.sgml
index 98d5b38ed6c..8fec13ee1d8 100644
--- a/doc/src/sgml/indices.sgml
+++ b/doc/src/sgml/indices.sgml
@@ -167,6 +167,11 @@ CREATE INDEX test1_id_index ON test1 (id);
    upper/lower case conversion.
   </para>
 
+  <para>
+   B-tree indexes can also be used to retrieve data in sorted order.
+   This is not always faster than a simple scan and sort, but it is
+   often helpful.
+  </para>
 
   <para>
    <indexterm>
@@ -236,6 +241,18 @@ CREATE INDEX <replaceable>name</replaceable> ON <replaceable>table</replaceable>
    classes are available in the <literal>contrib</> collection or as separate
    projects.  For more information see <xref linkend="GiST">.
   </para>
+
+  <para>
+   GiST indexes are also capable of optimizing <quote>nearest-neighbor</>
+   searches, such as
+<programlisting><![CDATA[
+SELECT * FROM places ORDER BY location <-> point '(101,456)' LIMIT 10;
+]]>
+</programlisting>
+   which finds the ten places closest to a given target point.  The ability
+   to do this is again dependent on the particular operator class being used.
+  </para>
+
   <para>
    <indexterm>
     <primary>index</primary>
diff --git a/doc/src/sgml/xindex.sgml b/doc/src/sgml/xindex.sgml
index 6d059bda706..a90b4e2a725 100644
--- a/doc/src/sgml/xindex.sgml
+++ b/doc/src/sgml/xindex.sgml
@@ -361,59 +361,74 @@
    </table>
 
   <para>
-   GiST indexes require seven support functions,
+   GiST indexes require seven support functions, with an optional eighth, as
    shown in <xref linkend="xindex-gist-support-table">.
   </para>
 
    <table tocentry="1" id="xindex-gist-support-table">
     <title>GiST Support Functions</title>
-    <tgroup cols="2">
+    <tgroup cols="3">
      <thead>
       <row>
        <entry>Function</entry>
+       <entry>Description</entry>
        <entry>Support Number</entry>
       </row>
      </thead>
      <tbody>
       <row>
-       <entry>consistent - determine whether key satisfies the
+       <entry><function>consistent</></entry>
+       <entry>determine whether key satisfies the
         query qualifier</entry>
        <entry>1</entry>
       </row>
       <row>
-       <entry>union - compute union of a set of keys</entry>
+       <entry><function>union</></entry>
+       <entry>compute union of a set of keys</entry>
        <entry>2</entry>
       </row>
       <row>
-       <entry>compress - compute a compressed representation of a key or value
+       <entry><function>compress</></entry>
+       <entry>compute a compressed representation of a key or value
         to be indexed</entry>
        <entry>3</entry>
       </row>
       <row>
-       <entry>decompress - compute a decompressed representation of a
+       <entry><function>decompress</></entry>
+       <entry>compute a decompressed representation of a
         compressed key</entry>
        <entry>4</entry>
       </row>
       <row>
-       <entry>penalty - compute penalty for inserting new key into subtree
+       <entry><function>penalty</></entry>
+       <entry>compute penalty for inserting new key into subtree
        with given subtree's key</entry>
        <entry>5</entry>
       </row>
       <row>
-       <entry>picksplit - determine which entries of a page are to be moved
+       <entry><function>picksplit</></entry>
+       <entry>determine which entries of a page are to be moved
        to the new page and compute the union keys for resulting pages</entry>
        <entry>6</entry>
       </row>
       <row>
-       <entry>equal - compare two keys and return true if they are equal</entry>
+       <entry><function>equal</></entry>
+       <entry>compare two keys and return true if they are equal</entry>
        <entry>7</entry>
       </row>
+      <row>
+       <entry><function>distance</></entry>
+       <entry>
+        (optional method) determine distance from key to query value
+       </entry>
+       <entry>8</entry>
+      </row>
      </tbody>
     </tgroup>
    </table>
 
   <para>
-   GIN indexes require four support functions,
+   GIN indexes require four support functions, with an optional fifth, as
    shown in <xref linkend="xindex-gin-support-table">.
   </para>