1 <!-- $PostgreSQL: pgsql/doc/src/sgml/xindex.sgml,v 1.53 2006/12/01 23:46:46 tgl Exp $ -->
4 <title>Interfacing Extensions To Indexes</title>
6 <indexterm zone="xindex">
7 <primary>index</primary>
8 <secondary>for user-defined data type</secondary>
12 The procedures described thus far let you define new types, new
13 functions, and new operators. However, we cannot yet define an
14 index on a column of a new data type. To do this, we must define an
15 <firstterm>operator class</> for the new data type. Later in this
16 section, we will illustrate this concept in an example: a new
17 operator class for the B-tree index method that stores and sorts
18 complex numbers in ascending absolute value order.
23 Prior to <productname>PostgreSQL</productname> release 7.3, it was
24 necessary to make manual additions to the system catalogs
25 <classname>pg_amop</>, <classname>pg_amproc</>, and
26 <classname>pg_opclass</> in order to create a user-defined
27 operator class. That approach is now deprecated in favor of using
28 <xref linkend="sql-createopclass" endterm="sql-createopclass-title">,
29 which is a much simpler and less error-prone way of creating the
30 necessary catalog entries.
34 <sect2 id="xindex-im">
35 <title>Index Methods and Operator Classes</title>
38 The <classname>pg_am</classname> table contains one row for every
39 index method (internally known as access method). Support for
40 regular access to tables is built into
41 <productname>PostgreSQL</productname>, but all index methods are
42 described in <classname>pg_am</classname>. It is possible to add a
43 new index method by defining the required interface routines and
44 then creating a row in <classname>pg_am</classname> — but that is
45 beyond the scope of this chapter (see <xref linkend="indexam">).
49 The routines for an index method do not directly know anything
50 about the data types that the index method will operate on.
51 Instead, an <firstterm>operator
52 class</><indexterm><primary>operator class</></indexterm>
53 identifies the set of operations that the index method needs to use
54 to work with a particular data type. Operator classes are so
55 called because one thing they specify is the set of
56 <literal>WHERE</>-clause operators that can be used with an index
57 (i.e., can be converted into an index-scan qualification). An
58 operator class may also specify some <firstterm>support
59 procedures</> that are needed by the internal operations of the
60 index method, but do not directly correspond to any
61 <literal>WHERE</>-clause operator that can be used with the index.
65 It is possible to define multiple operator classes for the same
66 data type and index method. By doing this, multiple
67 sets of indexing semantics can be defined for a single data type.
68 For example, a B-tree index requires a sort ordering to be defined
69 for each data type it works on.
70 It might be useful for a complex-number data type
71 to have one B-tree operator class that sorts the data by complex
72 absolute value, another that sorts by real part, and so on.
73 Typically, one of the operator classes will be deemed most commonly
74 useful and will be marked as the default operator class for that
75 data type and index method.
79 The same operator class name
80 can be used for several different index methods (for example, both B-tree
81 and hash index methods have operator classes named
82 <literal>int4_ops</literal>), but each such class is an independent
83 entity and must be defined separately.
87 <sect2 id="xindex-strategies">
88 <title>Index Method Strategies</title>
91 The operators associated with an operator class are identified by
92 <quote>strategy numbers</>, which serve to identify the semantics of
93 each operator within the context of its operator class.
94 For example, B-trees impose a strict ordering on keys, lesser to greater,
95 and so operators like <quote>less than</> and <quote>greater than or equal
96 to</> are interesting with respect to a B-tree.
98 <productname>PostgreSQL</productname> allows the user to define operators,
99 <productname>PostgreSQL</productname> cannot look at the name of an operator
100 (e.g., <literal><</> or <literal>>=</>) and tell what kind of
101 comparison it is. Instead, the index method defines a set of
102 <quote>strategies</>, which can be thought of as generalized operators.
103 Each operator class specifies which actual operator corresponds to each
104 strategy for a particular data type and interpretation of the index
109 The B-tree index method defines five strategies, shown in <xref
110 linkend="xindex-btree-strat-table">.
113 <table tocentry="1" id="xindex-btree-strat-table">
114 <title>B-tree Strategies</title>
118 <entry>Operation</entry>
119 <entry>Strategy Number</entry>
124 <entry>less than</entry>
128 <entry>less than or equal</entry>
136 <entry>greater than or equal</entry>
140 <entry>greater than</entry>
148 Hash indexes express only bitwise equality, and so they use only one
149 strategy, shown in <xref linkend="xindex-hash-strat-table">.
152 <table tocentry="1" id="xindex-hash-strat-table">
153 <title>Hash Strategies</title>
157 <entry>Operation</entry>
158 <entry>Strategy Number</entry>
171 GiST indexes are even more flexible: they do not have a fixed set of
172 strategies at all. Instead, the <quote>consistency</> support routine
173 of each particular GiST operator class interprets the strategy numbers
174 however it likes. As an example, several of the built-in GiST index
175 operator classes index two-dimensional geometric objects, providing
176 the <quote>R-tree</> strategies shown in
177 <xref linkend="xindex-rtree-strat-table">. Four of these are true
178 two-dimensional tests (overlaps, same, contains, contained by);
179 four of them consider only the X direction; and the other four
180 provide the same tests in the Y direction.
183 <table tocentry="1" id="xindex-rtree-strat-table">
184 <title>GiST Two-Dimensional <quote>R-tree</> Strategies</title>
188 <entry>Operation</entry>
189 <entry>Strategy Number</entry>
194 <entry>strictly left of</entry>
198 <entry>does not extend to right of</entry>
202 <entry>overlaps</entry>
206 <entry>does not extend to left of</entry>
210 <entry>strictly right of</entry>
218 <entry>contains</entry>
222 <entry>contained by</entry>
226 <entry>does not extend above</entry>
230 <entry>strictly below</entry>
234 <entry>strictly above</entry>
238 <entry>does not extend below</entry>
246 GIN indexes are similar to GiST indexes in flexibility: they don't have a
247 fixed set of strategies. Instead the support routines of each operator
248 class interpret the strategy numbers according to the operator class's
249 definition. As an example, the strategy numbers used by the built-in
250 operator classes for arrays are
251 shown in <xref linkend="xindex-gin-array-strat-table">.
254 <table tocentry="1" id="xindex-gin-array-strat-table">
255 <title>GIN Array Strategies</title>
259 <entry>Operation</entry>
260 <entry>Strategy Number</entry>
265 <entry>overlap</entry>
269 <entry>contains</entry>
273 <entry>is contained by</entry>
285 Note that all strategy operators return Boolean values. In
286 practice, all operators defined as index method strategies must
287 return type <type>boolean</type>, since they must appear at the top
288 level of a <literal>WHERE</> clause to be used with an index.
292 By the way, the <structfield>amorderstrategy</structfield> column
293 in <classname>pg_am</> tells whether
294 the index method supports ordered scans. Zero means it doesn't; if it
295 does, <structfield>amorderstrategy</structfield> is the strategy
296 number that corresponds to the ordering operator. For example, B-tree
297 has <structfield>amorderstrategy</structfield> = 1, which is its
298 <quote>less than</quote> strategy number.
302 <sect2 id="xindex-support">
303 <title>Index Method Support Routines</title>
306 Strategies aren't usually enough information for the system to figure
307 out how to use an index. In practice, the index methods require
308 additional support routines in order to work. For example, the B-tree
309 index method must be able to compare two keys and determine whether one
310 is greater than, equal to, or less than the other. Similarly, the
311 hash index method must be able to compute hash codes for key values.
312 These operations do not correspond to operators used in qualifications in
313 SQL commands; they are administrative routines used by
314 the index methods, internally.
318 Just as with strategies, the operator class identifies which specific
319 functions should play each of these roles for a given data type and
320 semantic interpretation. The index method defines the set
321 of functions it needs, and the operator class identifies the correct
322 functions to use by assigning them to the <quote>support function numbers</>.
326 B-trees require a single support function, shown in <xref
327 linkend="xindex-btree-support-table">.
330 <table tocentry="1" id="xindex-btree-support-table">
331 <title>B-tree Support Functions</title>
335 <entry>Function</entry>
336 <entry>Support Number</entry>
342 Compare two keys and return an integer less than zero, zero, or
343 greater than zero, indicating whether the first key is less than, equal to,
344 or greater than the second.
353 Hash indexes likewise require one support function, shown in <xref
354 linkend="xindex-hash-support-table">.
357 <table tocentry="1" id="xindex-hash-support-table">
358 <title>Hash Support Functions</title>
362 <entry>Function</entry>
363 <entry>Support Number</entry>
368 <entry>Compute the hash value for a key</entry>
376 GiST indexes require seven support functions,
377 shown in <xref linkend="xindex-gist-support-table">.
380 <table tocentry="1" id="xindex-gist-support-table">
381 <title>GiST Support Functions</title>
385 <entry>Function</entry>
386 <entry>Support Number</entry>
391 <entry>consistent - determine whether key satisfies the
392 query qualifier</entry>
396 <entry>union - compute union of a set of keys</entry>
400 <entry>compress - compute a compressed representation of a key or value
401 to be indexed</entry>
405 <entry>decompress - compute a decompressed representation of a
406 compressed key</entry>
410 <entry>penalty - compute penalty for inserting new key into subtree
411 with given subtree's key</entry>
415 <entry>picksplit - determine which entries of a page are to be moved
416 to the new page and compute the union keys for resulting pages</entry>
420 <entry>equal - compare two keys and return true if they are equal</entry>
428 GIN indexes require four support functions,
429 shown in <xref linkend="xindex-gin-support-table">.
432 <table tocentry="1" id="xindex-gin-support-table">
433 <title>GIN Support Functions</title>
437 <entry>Function</entry>
438 <entry>Support Number</entry>
444 compare - compare two keys and return an integer less than zero, zero,
445 or greater than zero, indicating whether the first key is less than,
446 equal to, or greater than the second
451 <entry>extractValue - extract keys from a value to be indexed</entry>
455 <entry>extractQuery - extract keys from a query condition</entry>
459 <entry>consistent - determine whether value matches query condition</entry>
467 Unlike strategy operators, support functions return whichever data
468 type the particular index method expects; for example in the case
469 of the comparison function for B-trees, a signed integer.
473 <sect2 id="xindex-example">
474 <title>An Example</title>
477 Now that we have seen the ideas, here is the promised example of
478 creating a new operator class.
479 (You can find a working copy of this example in
480 <filename>src/tutorial/complex.c</filename> and
481 <filename>src/tutorial/complex.sql</filename> in the source
483 The operator class encapsulates
484 operators that sort complex numbers in absolute value order, so we
485 choose the name <literal>complex_abs_ops</literal>. First, we need
486 a set of operators. The procedure for defining operators was
487 discussed in <xref linkend="xoper">. For an operator class on
488 B-trees, the operators we require are:
490 <itemizedlist spacing="compact">
491 <listitem><simpara>absolute-value less-than (strategy 1)</></>
492 <listitem><simpara>absolute-value less-than-or-equal (strategy 2)</></>
493 <listitem><simpara>absolute-value equal (strategy 3)</></>
494 <listitem><simpara>absolute-value greater-than-or-equal (strategy 4)</></>
495 <listitem><simpara>absolute-value greater-than (strategy 5)</></>
500 The least error-prone way to define a related set of comparison operators
501 is to write the B-tree comparison support function first, and then write the
502 other functions as one-line wrappers around the support function. This
503 reduces the odds of getting inconsistent results for corner cases.
504 Following this approach, we first write
507 #define Mag(c) ((c)->x*(c)->x + (c)->y*(c)->y)
510 complex_abs_cmp_internal(Complex *a, Complex *b)
512 double amag = Mag(a),
523 Now the less-than function looks like
526 PG_FUNCTION_INFO_V1(complex_abs_lt);
529 complex_abs_lt(PG_FUNCTION_ARGS)
531 Complex *a = (Complex *) PG_GETARG_POINTER(0);
532 Complex *b = (Complex *) PG_GETARG_POINTER(1);
534 PG_RETURN_BOOL(complex_abs_cmp_internal(a, b) < 0);
538 The other four functions differ only in how they compare the internal
539 function's result to zero.
543 Next we declare the functions and the operators based on the functions
547 CREATE FUNCTION complex_abs_lt(complex, complex) RETURNS bool
548 AS '<replaceable>filename</replaceable>', 'complex_abs_lt'
549 LANGUAGE C IMMUTABLE STRICT;
551 CREATE OPERATOR < (
552 leftarg = complex, rightarg = complex, procedure = complex_abs_lt,
553 commutator = > , negator = >= ,
554 restrict = scalarltsel, join = scalarltjoinsel
557 It is important to specify the correct commutator and negator operators,
558 as well as suitable restriction and join selectivity
559 functions, otherwise the optimizer will be unable to make effective
560 use of the index. Note that the less-than, equal, and
561 greater-than cases should use different selectivity functions.
565 Other things worth noting are happening here:
570 There can only be one operator named, say, <literal>=</literal>
571 and taking type <type>complex</type> for both operands. In this
572 case we don't have any other operator <literal>=</literal> for
573 <type>complex</type>, but if we were building a practical data
574 type we'd probably want <literal>=</literal> to be the ordinary
575 equality operation for complex numbers (and not the equality of
576 the absolute values). In that case, we'd need to use some other
577 operator name for <function>complex_abs_eq</>.
583 Although <productname>PostgreSQL</productname> can cope with
584 functions having the same SQL name as long as they have different
585 argument data types, C can only cope with one global function
586 having a given name. So we shouldn't name the C function
587 something simple like <filename>abs_eq</filename>. Usually it's
588 a good practice to include the data type name in the C function
589 name, so as not to conflict with functions for other data types.
595 We could have made the SQL name
596 of the function <filename>abs_eq</filename>, relying on
597 <productname>PostgreSQL</productname> to distinguish it by
598 argument data types from any other SQL function of the same name.
599 To keep the example simple, we make the function have the same
600 names at the C level and SQL level.
607 The next step is the registration of the support routine required
608 by B-trees. The example C code that implements this is in the same
609 file that contains the operator functions. This is how we declare
613 CREATE FUNCTION complex_abs_cmp(complex, complex)
615 AS '<replaceable>filename</replaceable>'
616 LANGUAGE C IMMUTABLE STRICT;
621 Now that we have the required operators and support routine,
622 we can finally create the operator class:
625 CREATE OPERATOR CLASS complex_abs_ops
626 DEFAULT FOR TYPE complex USING btree AS
632 FUNCTION 1 complex_abs_cmp(complex, complex);
637 And we're done! It should now be possible to create
638 and use B-tree indexes on <type>complex</type> columns.
642 We could have written the operator entries more verbosely, as in
644 OPERATOR 1 < (complex, complex) ,
646 but there is no need to do so when the operators take the same data type
647 we are defining the operator class for.
651 The above example assumes that you want to make this new operator class the
652 default B-tree operator class for the <type>complex</type> data type.
653 If you don't, just leave out the word <literal>DEFAULT</>.
657 <sect2 id="xindex-opclass-crosstype">
658 <title>Cross-Data-Type Operator Classes</title>
661 So far we have implicitly assumed that an operator class deals with
662 only one data type. While there certainly can be only one data type in
663 a particular index column, it is often useful to index operations that
664 compare an indexed column to a value of a different data type. This is
665 presently supported by the B-tree and GiST index methods.
669 B-trees require the left-hand operand of each operator to be the indexed
670 data type, but the right-hand operand can be of a different type. There
671 must be a support function having a matching signature. For example,
672 the built-in operator class for type <type>bigint</> (<type>int8</>)
673 allows cross-type comparisons to <type>int4</> and <type>int2</>. It
674 could be duplicated by this definition:
677 CREATE OPERATOR CLASS int8_ops
678 DEFAULT FOR TYPE int8 USING btree AS
679 -- standard int8 comparisons
685 FUNCTION 1 btint8cmp(int8, int8) ,
687 -- cross-type comparisons to int2 (smallint)
688 OPERATOR 1 < (int8, int2) ,
689 OPERATOR 2 <= (int8, int2) ,
690 OPERATOR 3 = (int8, int2) ,
691 OPERATOR 4 >= (int8, int2) ,
692 OPERATOR 5 > (int8, int2) ,
693 FUNCTION 1 btint82cmp(int8, int2) ,
695 -- cross-type comparisons to int4 (integer)
696 OPERATOR 1 < (int8, int4) ,
697 OPERATOR 2 <= (int8, int4) ,
698 OPERATOR 3 = (int8, int4) ,
699 OPERATOR 4 >= (int8, int4) ,
700 OPERATOR 5 > (int8, int4) ,
701 FUNCTION 1 btint84cmp(int8, int4) ;
704 Notice that this definition <quote>overloads</> the operator strategy and
705 support function numbers. This is allowed (for B-tree operator classes
706 only) so long as each instance of a particular number has a different
707 right-hand data type. The instances that are not cross-type are the
708 default or primary operators of the operator class.
712 GiST indexes do not allow overloading of strategy or support function
713 numbers, but it is still possible to get the effect of supporting
714 multiple right-hand data types, by assigning a distinct strategy number
715 to each operator that needs to be supported. The <literal>consistent</>
716 support function must determine what it needs to do based on the strategy
717 number, and must be prepared to accept comparison values of the appropriate
722 <sect2 id="xindex-opclass-dependencies">
723 <title>System Dependencies on Operator Classes</title>
726 <primary>ordering operator</primary>
730 <productname>PostgreSQL</productname> uses operator classes to infer the
731 properties of operators in more ways than just whether they can be used
732 with indexes. Therefore, you might want to create operator classes
733 even if you have no intention of indexing any columns of your data type.
737 In particular, there are SQL features such as <literal>ORDER BY</> and
738 <literal>DISTINCT</> that require comparison and sorting of values.
739 To implement these features on a user-defined data type,
740 <productname>PostgreSQL</productname> looks for the default B-tree operator
741 class for the data type. The <quote>equals</> member of this operator
742 class defines the system's notion of equality of values for
743 <literal>GROUP BY</> and <literal>DISTINCT</>, and the sort ordering
744 imposed by the operator class defines the default <literal>ORDER BY</>
749 Comparison of arrays of user-defined types also relies on the semantics
750 defined by the default B-tree operator class.
754 If there is no default B-tree operator class for a data type, the system
755 will look for a default hash operator class. But since that kind of
756 operator class only provides equality, in practice it is only enough
757 to support array equality.
761 When there is no default operator class for a data type, you will get
762 errors like <quote>could not identify an ordering operator</> if you
763 try to use these SQL features with the data type.
768 In <productname>PostgreSQL</productname> versions before 7.4,
769 sorting and grouping operations would implicitly use operators named
770 <literal>=</>, <literal><</>, and <literal>></>. The new
771 behavior of relying on default operator classes avoids having to make
772 any assumption about the behavior of operators with particular names.
777 <sect2 id="xindex-opclass-features">
778 <title>Special Features of Operator Classes</title>
781 There are two special features of operator classes that we have
782 not discussed yet, mainly because they are not useful
783 with the most commonly used index methods.
787 Normally, declaring an operator as a member of an operator class means
788 that the index method can retrieve exactly the set of rows
789 that satisfy a <literal>WHERE</> condition using the operator. For example,
791 SELECT * FROM table WHERE integer_column < 4;
793 can be satisfied exactly by a B-tree index on the integer column.
794 But there are cases where an index is useful as an inexact guide to
795 the matching rows. For example, if a GiST index stores only
796 bounding boxes for objects, then it cannot exactly satisfy a <literal>WHERE</>
797 condition that tests overlap between nonrectangular objects such as
798 polygons. Yet we could use the index to find objects whose bounding
799 box overlaps the bounding box of the target object, and then do the
800 exact overlap test only on the objects found by the index. If this
801 scenario applies, the index is said to be <quote>lossy</> for the
802 operator, and we add <literal>RECHECK</> to the <literal>OPERATOR</> clause
803 in the <command>CREATE OPERATOR CLASS</> command.
804 <literal>RECHECK</> is valid if the index is guaranteed to return
805 all the required rows, plus perhaps some additional rows, which
806 can be eliminated by performing the original operator invocation.
810 Consider again the situation where we are storing in the index only
811 the bounding box of a complex object such as a polygon. In this
812 case there's not much value in storing the whole polygon in the index
813 entry — we may as well store just a simpler object of type
814 <type>box</>. This situation is expressed by the <literal>STORAGE</>
815 option in <command>CREATE OPERATOR CLASS</>: we'd write something like
818 CREATE OPERATOR CLASS polygon_ops
819 DEFAULT FOR TYPE polygon USING gist AS
824 At present, only the GiST and GIN index methods support a
825 <literal>STORAGE</> type that's different from the column data type.
826 The GiST <function>compress</> and <function>decompress</> support
827 routines must deal with data-type conversion when <literal>STORAGE</>
828 is used. In GIN, the <literal>STORAGE</> type identifies the type of
829 the <quote>key</> values, which normally is different from the type
830 of the indexed column — for example, an operator class for
831 integer array columns might have keys that are just integers. The
832 GIN <function>extractValue</> and <function>extractQuery</> support
833 routines are responsible for extracting keys from indexed values.
projects / postgresql / blob