-<!-- $PostgreSQL: pgsql/doc/src/sgml/xindex.sgml,v 1.57 2007/01/31 20:56:20 momjian Exp $ -->
+<!-- doc/src/sgml/xindex.sgml -->
<sect1 id="xindex">
<title>Interfacing Extensions To Indexes</title>
</table>
<para>
- Hash indexes express only bitwise equality, and so they use only one
+ Hash indexes support only equality comparisons, and so they use only one
strategy, shown in <xref linkend="xindex-hash-strat-table">.
</para>
</table>
<para>
- GiST indexes are even more flexible: they do not have a fixed set of
+ GiST indexes are more flexible: they do not have a fixed set of
strategies at all. Instead, the <quote>consistency</> support routine
of each particular GiST operator class interprets the strategy numbers
however it likes. As an example, several of the built-in GiST index
</table>
<para>
- Notice that all strategy operators return Boolean values. In
- practice, all operators defined as index method strategies must
+ Notice that all the operators listed above return Boolean values. In
+ practice, all operators defined as index method search operators must
return type <type>boolean</type>, since they must appear at the top
level of a <literal>WHERE</> clause to be used with an index.
+ (Some index access methods also support <firstterm>ordering operators</>,
+ which typically don't return Boolean values; that feature is discussed
+ in <xref linkend="xindex-ordering-ops">.)
</para>
</sect2>
</para>
<para>
- B-trees require a single support function, shown in <xref
+ B-trees require a single support function, and allow a second one to be
+ supplied at the operator class author's option, as shown in <xref
linkend="xindex-btree-support-table">.
</para>
<entry>
Compare two keys and return an integer less than zero, zero, or
greater than zero, indicating whether the first key is less than,
- equal to, or greater than the second.
+ equal to, or greater than the second
</entry>
<entry>1</entry>
</row>
+ <row>
+ <entry>
+ Return the addresses of C-callable sort support function(s),
+ as documented in <filename>utils/sortsupport.h</> (optional)
+ </entry>
+ <entry>2</entry>
+ </row>
</tbody>
</tgroup>
</table>
<para>
- Hash indexes likewise require one support function, shown in <xref
+ Hash indexes require one support function, shown in <xref
linkend="xindex-hash-support-table">.
</para>
</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">.
+ (For more information see <xref linkend="GiST">.)
</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>determine distance from key to query value (optional)</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">.
+ (For more information see <xref linkend="GIN">.)
</para>
<table tocentry="1" id="xindex-gin-support-table">
<title>GIN 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><function>compare</></entry>
<entry>
- compare - compare two keys and return an integer less than zero, zero,
+ compare two keys and return an integer less than zero, zero,
or greater than zero, indicating whether the first key is less than,
equal to, or greater than the second
</entry>
<entry>1</entry>
</row>
<row>
- <entry>extractValue - extract keys from a value to be indexed</entry>
+ <entry><function>extractValue</></entry>
+ <entry>extract keys from a value to be indexed</entry>
<entry>2</entry>
</row>
<row>
- <entry>extractQuery - extract keys from a query condition</entry>
+ <entry><function>extractQuery</></entry>
+ <entry>extract keys from a query condition</entry>
<entry>3</entry>
</row>
<row>
- <entry>consistent - determine whether value matches query condition</entry>
+ <entry><function>consistent</></entry>
+ <entry>determine whether value matches query condition</entry>
<entry>4</entry>
</row>
+ <row>
+ <entry><function>comparePartial</></entry>
+ <entry>
+ compare partial key from
+ query and key from index, and return an integer less than zero, zero,
+ or greater than zero, indicating whether GIN should ignore this index
+ entry, treat the entry as a match, or stop the index scan (optional)
+ </entry>
+ <entry>5</entry>
+ </row>
</tbody>
</tgroup>
</table>
<para>
- Unlike strategy operators, support functions return whichever data
+ Unlike search operators, support functions return whichever data
type the particular index method expects; for example in the case
of the comparison function for B-trees, a signed integer. The number
and types of the arguments to each support function are likewise
- dependent on the index method. For B-tree and hash the support functions
+ dependent on the index method. For B-tree and hash the comparison and
+ hashing support functions
take the same input data types as do the operators included in the operator
class, but this is not the case for most GIN and GiST support functions.
</para>
is to write the B-tree comparison support function first, and then write the
other functions as one-line wrappers around the support function. This
reduces the odds of getting inconsistent results for corner cases.
- Following this approach, we first write
+ Following this approach, we first write:
-<programlisting>
-#define Mag(c) ((c)->x*(c)->x + (c)->y*(c)->y)
+<programlisting><![CDATA[
+#define Mag(c) ((c)->x*(c)->x + (c)->y*(c)->y)
static int
complex_abs_cmp_internal(Complex *a, Complex *b)
double amag = Mag(a),
bmag = Mag(b);
- if (amag < bmag)
+ if (amag < bmag)
return -1;
- if (amag > bmag)
+ if (amag > bmag)
return 1;
return 0;
}
+]]>
</programlisting>
- Now the less-than function looks like
+ Now the less-than function looks like:
-<programlisting>
+<programlisting><![CDATA[
PG_FUNCTION_INFO_V1(complex_abs_lt);
Datum
Complex *a = (Complex *) PG_GETARG_POINTER(0);
Complex *b = (Complex *) PG_GETARG_POINTER(1);
- PG_RETURN_BOOL(complex_abs_cmp_internal(a, b) < 0);
+ PG_RETURN_BOOL(complex_abs_cmp_internal(a, b) < 0);
}
+]]>
</programlisting>
The other four functions differ only in how they compare the internal
Now that we have the required operators and support routine,
we can finally create the operator class:
-<programlisting>
+<programlisting><![CDATA[
CREATE OPERATOR CLASS complex_abs_ops
DEFAULT FOR TYPE complex USING btree AS
- OPERATOR 1 < ,
- OPERATOR 2 <= ,
+ OPERATOR 1 < ,
+ OPERATOR 2 <= ,
OPERATOR 3 = ,
- OPERATOR 4 >= ,
- OPERATOR 5 > ,
+ OPERATOR 4 >= ,
+ OPERATOR 5 > ,
FUNCTION 1 complex_abs_cmp(complex, complex);
+]]>
</programlisting>
</para>
</para>
<para>
- We could have written the operator entries more verbosely, as in
+ We could have written the operator entries more verbosely, as in:
<programlisting>
OPERATOR 1 < (complex, complex) ,
</programlisting>
on one of these types can be searched using a comparison value of another
type. The family could be duplicated by these definitions:
-<programlisting>
+<programlisting><![CDATA[
CREATE OPERATOR FAMILY integer_ops USING btree;
CREATE OPERATOR CLASS int8_ops
DEFAULT FOR TYPE int8 USING btree FAMILY integer_ops AS
-- standard int8 comparisons
- OPERATOR 1 < ,
- OPERATOR 2 <= ,
+ OPERATOR 1 < ,
+ OPERATOR 2 <= ,
OPERATOR 3 = ,
- OPERATOR 4 >= ,
- OPERATOR 5 > ,
- FUNCTION 1 btint8cmp(int8, int8) ;
+ OPERATOR 4 >= ,
+ OPERATOR 5 > ,
+ FUNCTION 1 btint8cmp(int8, int8) ,
+ FUNCTION 2 btint8sortsupport(internal) ;
CREATE OPERATOR CLASS int4_ops
DEFAULT FOR TYPE int4 USING btree FAMILY integer_ops AS
-- standard int4 comparisons
- OPERATOR 1 < ,
- OPERATOR 2 <= ,
+ OPERATOR 1 < ,
+ OPERATOR 2 <= ,
OPERATOR 3 = ,
- OPERATOR 4 >= ,
- OPERATOR 5 > ,
- FUNCTION 1 btint4cmp(int4, int4) ;
+ OPERATOR 4 >= ,
+ OPERATOR 5 > ,
+ FUNCTION 1 btint4cmp(int4, int4) ,
+ FUNCTION 2 btint4sortsupport(internal) ;
CREATE OPERATOR CLASS int2_ops
DEFAULT FOR TYPE int2 USING btree FAMILY integer_ops AS
-- standard int2 comparisons
- OPERATOR 1 < ,
- OPERATOR 2 <= ,
+ OPERATOR 1 < ,
+ OPERATOR 2 <= ,
OPERATOR 3 = ,
- OPERATOR 4 >= ,
- OPERATOR 5 > ,
- FUNCTION 1 btint2cmp(int2, int2) ;
+ OPERATOR 4 >= ,
+ OPERATOR 5 > ,
+ FUNCTION 1 btint2cmp(int2, int2) ,
+ FUNCTION 2 btint2sortsupport(internal) ;
ALTER OPERATOR FAMILY integer_ops USING btree ADD
-- cross-type comparisons int8 vs int2
- OPERATOR 1 < (int8, int2) ,
- OPERATOR 2 <= (int8, int2) ,
+ OPERATOR 1 < (int8, int2) ,
+ OPERATOR 2 <= (int8, int2) ,
OPERATOR 3 = (int8, int2) ,
- OPERATOR 4 >= (int8, int2) ,
- OPERATOR 5 > (int8, int2) ,
+ OPERATOR 4 >= (int8, int2) ,
+ OPERATOR 5 > (int8, int2) ,
FUNCTION 1 btint82cmp(int8, int2) ,
-- cross-type comparisons int8 vs int4
- OPERATOR 1 < (int8, int4) ,
- OPERATOR 2 <= (int8, int4) ,
+ OPERATOR 1 < (int8, int4) ,
+ OPERATOR 2 <= (int8, int4) ,
OPERATOR 3 = (int8, int4) ,
- OPERATOR 4 >= (int8, int4) ,
- OPERATOR 5 > (int8, int4) ,
+ OPERATOR 4 >= (int8, int4) ,
+ OPERATOR 5 > (int8, int4) ,
FUNCTION 1 btint84cmp(int8, int4) ,
-- cross-type comparisons int4 vs int2
- OPERATOR 1 < (int4, int2) ,
- OPERATOR 2 <= (int4, int2) ,
+ OPERATOR 1 < (int4, int2) ,
+ OPERATOR 2 <= (int4, int2) ,
OPERATOR 3 = (int4, int2) ,
- OPERATOR 4 >= (int4, int2) ,
- OPERATOR 5 > (int4, int2) ,
+ OPERATOR 4 >= (int4, int2) ,
+ OPERATOR 5 > (int4, int2) ,
FUNCTION 1 btint42cmp(int4, int2) ,
-- cross-type comparisons int4 vs int8
- OPERATOR 1 < (int4, int8) ,
- OPERATOR 2 <= (int4, int8) ,
+ OPERATOR 1 < (int4, int8) ,
+ OPERATOR 2 <= (int4, int8) ,
OPERATOR 3 = (int4, int8) ,
- OPERATOR 4 >= (int4, int8) ,
- OPERATOR 5 > (int4, int8) ,
+ OPERATOR 4 >= (int4, int8) ,
+ OPERATOR 5 > (int4, int8) ,
FUNCTION 1 btint48cmp(int4, int8) ,
-- cross-type comparisons int2 vs int8
- OPERATOR 1 < (int2, int8) ,
- OPERATOR 2 <= (int2, int8) ,
+ OPERATOR 1 < (int2, int8) ,
+ OPERATOR 2 <= (int2, int8) ,
OPERATOR 3 = (int2, int8) ,
- OPERATOR 4 >= (int2, int8) ,
- OPERATOR 5 > (int2, int8) ,
+ OPERATOR 4 >= (int2, int8) ,
+ OPERATOR 5 > (int2, int8) ,
FUNCTION 1 btint28cmp(int2, int8) ,
-- cross-type comparisons int2 vs int4
- OPERATOR 1 < (int2, int4) ,
- OPERATOR 2 <= (int2, int4) ,
+ OPERATOR 1 < (int2, int4) ,
+ OPERATOR 2 <= (int2, int4) ,
OPERATOR 3 = (int2, int4) ,
- OPERATOR 4 >= (int2, int4) ,
- OPERATOR 5 > (int2, int4) ,
+ OPERATOR 4 >= (int2, int4) ,
+ OPERATOR 5 > (int2, int4) ,
FUNCTION 1 btint24cmp(int2, int4) ;
+]]>
</programlisting>
Notice that this definition <quote>overloads</> the operator strategy and
<para>
In a B-tree operator family, all the operators in the family must sort
compatibly, meaning that the transitive laws hold across all the data types
- supported by the family: <quote>if A = B and B = C, then A =
- C</>, and <quote>if A < B and B < C, then A < C</>. For each
+ supported by the family: <quote>if A = B and B = C, then A = C</>,
+ and <quote>if A < B and B < C, then A < C</>. Moreover, implicit
+ or binary coercion casts between types represented in the operator family
+ must not change the associated sort ordering. For each
operator in the family there must be a support function having the same
two input data types as the operator. It is recommended that a family be
complete, i.e., for each combination of data types, all operators are
- included. An operator class should include just the non-cross-type
+ included. Each operator class should include just the non-cross-type
operators and support function for its data type.
</para>
<para>
- At this writing, hash indexes do not support cross-type operations,
- and so there is little use for a hash operator family larger than one
- operator class. This is expected to be relaxed in the future.
+ To build a multiple-data-type hash operator family, compatible hash
+ support functions must be created for each data type supported by the
+ family. Here compatibility means that the functions are guaranteed to
+ return the same hash code for any two values that are considered equal
+ by the family's equality operators, even when the values are of different
+ types. This is usually difficult to accomplish when the types have
+ different physical representations, but it can be done in some cases.
+ Furthermore, casting a value from one data type represented in the operator
+ family to another data type also represented in the operator family via
+ an implicit or binary coercion cast must not change the computed hash value.
+ Notice that there is only one support function per data type, not one
+ per equality operator. It is recommended that a family be complete, i.e.,
+ provide an equality operator for each combination of data types.
+ Each operator class should include just the non-cross-type equality
+ operator and the support function for its data type.
</para>
<para>
any assumption about the behavior of operators with particular names.
</para>
</note>
+
+ <para>
+ Another important point is that an operator that
+ appears in a hash operator family is a candidate for hash joins,
+ hash aggregation, and related optimizations. The hash operator family
+ is essential here since it identifies the hash function(s) to use.
+ </para>
+ </sect2>
+
+ <sect2 id="xindex-ordering-ops">
+ <title>Ordering Operators</title>
+
+ <para>
+ Some index access methods (currently, only GiST) support the concept of
+ <firstterm>ordering operators</>. What we have been discussing so far
+ are <firstterm>search operators</>. A search operator is one for which
+ the index can be searched to find all rows satisfying
+ <literal>WHERE</>
+ <replaceable>indexed_column</>
+ <replaceable>operator</>
+ <replaceable>constant</>.
+ Note that nothing is promised about the order in which the matching rows
+ will be returned. In contrast, an ordering operator does not restrict the
+ set of rows that can be returned, but instead determines their order.
+ An ordering operator is one for which the index can be scanned to return
+ rows in the order represented by
+ <literal>ORDER BY</>
+ <replaceable>indexed_column</>
+ <replaceable>operator</>
+ <replaceable>constant</>.
+ The reason for defining ordering operators that way is that it supports
+ nearest-neighbor searches, if the operator is one that measures distance.
+ For example, a query like
+<programlisting><![CDATA[
+SELECT * FROM places ORDER BY location <-> point '(101,456)' LIMIT 10;
+]]>
+</programlisting>
+ finds the ten places closest to a given target point. A GiST index
+ on the location column can do this efficiently because
+ <literal><-></> is an ordering operator.
+ </para>
+
+ <para>
+ While search operators have to return Boolean results, ordering operators
+ usually return some other type, such as float or numeric for distances.
+ This type is normally not the same as the data type being indexed.
+ To avoid hard-wiring assumptions about the behavior of different data
+ types, the definition of an ordering operator is required to name
+ a B-tree operator family that specifies the sort ordering of the result
+ data type. As was stated in the previous section, B-tree operator families
+ define <productname>PostgreSQL</productname>'s notion of ordering, so
+ this is a natural representation. Since the point <literal><-></>
+ operator returns <type>float8</>, it could be specified in an operator
+ class creation command like this:
+<programlisting><![CDATA[
+OPERATOR 15 <-> (point, point) FOR ORDER BY float_ops
+]]>
+</programlisting>
+ where <literal>float_ops</> is the built-in operator family that includes
+ operations on <type>float8</>. This declaration states that the index
+ is able to return rows in order of increasing values of the
+ <literal><-></> operator.
+ </para>
</sect2>
<sect2 id="xindex-opclass-features">
<para>
Normally, declaring an operator as a member of an operator class
- (or family) means
- that the index method can retrieve exactly the set of rows
- that satisfy a <literal>WHERE</> condition using the operator. For example,
+ (or family) means that the index method can retrieve exactly the set of rows
+ that satisfy a <literal>WHERE</> condition using the operator. For example:
<programlisting>
SELECT * FROM table WHERE integer_column < 4;
</programlisting>
can be satisfied exactly by a B-tree index on the integer column.
But there are cases where an index is useful as an inexact guide to
- the matching rows. For example, if a GiST index stores only
- bounding boxes for objects, then it cannot exactly satisfy a <literal>WHERE</>
+ the matching rows. For example, if a GiST index stores only bounding boxes
+ for geometric objects, then it cannot exactly satisfy a <literal>WHERE</>
condition that tests overlap between nonrectangular objects such as
polygons. Yet we could use the index to find objects whose bounding
box overlaps the bounding box of the target object, and then do the
exact overlap test only on the objects found by the index. If this
scenario applies, the index is said to be <quote>lossy</> for the
- operator, and we add <literal>RECHECK</> to the <literal>OPERATOR</> clause
- in the <command>CREATE OPERATOR CLASS</> command.
- <literal>RECHECK</> is valid if the index is guaranteed to return
- all the required rows, plus perhaps some additional rows, which
- can be eliminated by performing the original operator invocation.
+ operator. Lossy index searches are implemented by having the index
+ method return a <firstterm>recheck</> flag when a row might or might
+ not really satisfy the query condition. The core system will then
+ test the original query condition on the retrieved row to see whether
+ it should be returned as a valid match. This approach works if
+ the index is guaranteed to return all the required rows, plus perhaps
+ some additional rows, which can be eliminated by performing the original
+ operator invocation. The index methods that support lossy searches
+ (currently, GiST and GIN) allow the support functions of individual
+ operator classes to set the recheck flag, and so this is essentially an
+ operator-class feature.
</para>
<para>
case there's not much value in storing the whole polygon in the index
entry — we might as well store just a simpler object of type
<type>box</>. This situation is expressed by the <literal>STORAGE</>
- option in <command>CREATE OPERATOR CLASS</>: we'd write something like
+ option in <command>CREATE OPERATOR CLASS</>: we'd write something like:
<programlisting>
CREATE OPERATOR CLASS polygon_ops
is used. In GIN, the <literal>STORAGE</> type identifies the type of
the <quote>key</> values, which normally is different from the type
of the indexed column — for example, an operator class for
- integer array columns might have keys that are just integers. The
+ integer-array columns might have keys that are just integers. The
GIN <function>extractValue</> and <function>extractQuery</> support
routines are responsible for extracting keys from indexed values.
</para>
projects / postgresql / blobdiff