2 $PostgreSQL: pgsql/doc/src/sgml/xindex.sgml,v 1.39 2005/02/13 03:04:15 tgl Exp $
6 <title>Interfacing Extensions To Indexes</title>
8 <indexterm zone="xindex">
9 <primary>index</primary>
10 <secondary>for user-defined data type</secondary>
14 The procedures described thus far let you define new types, new
15 functions, and new operators. However, we cannot yet define an
16 index on a column of a new data type. To do this, we must define an
17 <firstterm>operator class</> for the new data type. Later in this
18 section, we will illustrate this concept in an example: a new
19 operator class for the B-tree index method that stores and sorts
20 complex numbers in ascending absolute value order.
25 Prior to <productname>PostgreSQL</productname> release 7.3, it was
26 necessary to make manual additions to the system catalogs
27 <classname>pg_amop</>, <classname>pg_amproc</>, and
28 <classname>pg_opclass</> in order to create a user-defined
29 operator class. That approach is now deprecated in favor of
30 using <command>CREATE OPERATOR CLASS</>, which is a much simpler
31 and less error-prone way of creating the necessary catalog entries.
35 <sect2 id="xindex-im">
36 <title>Index Methods and Operator Classes</title>
39 The <classname>pg_am</classname> table contains one row for every
40 index method (internally known as access method). Support for
41 regular access to tables is built into
42 <productname>PostgreSQL</productname>, but all index methods are
43 described in <classname>pg_am</classname>. It is possible to add a
44 new index method by defining the required interface routines and
45 then creating a row in <classname>pg_am</classname> — but that is
46 beyond the scope of this chapter (see <xref linkend="indexam">).
50 The routines for an index method do not directly know anything
51 about the data types that the index method will operate on.
52 Instead, an <firstterm>operator
53 class</><indexterm><primary>operator class</></indexterm>
54 identifies the set of operations that the index method needs to use
55 to work with a particular data type. Operator classes are so
56 called because one thing they specify is the set of
57 <literal>WHERE</>-clause operators that can be used with an index
58 (i.e., can be converted into an index-scan qualification). An
59 operator class may also specify some <firstterm>support
60 procedures</> that are needed by the internal operations of the
61 index method, but do not directly correspond to any
62 <literal>WHERE</>-clause operator that can be used with the index.
66 It is possible to define multiple operator classes for the same
67 data type and index method. By doing this, multiple
68 sets of indexing semantics can be defined for a single data type.
69 For example, a B-tree index requires a sort ordering to be defined
70 for each data type it works on.
71 It might be useful for a complex-number data type
72 to have one B-tree operator class that sorts the data by complex
73 absolute value, another that sorts by real part, and so on.
74 Typically, one of the operator classes will be deemed most commonly
75 useful and will be marked as the default operator class for that
76 data type and index method.
80 The same operator class name
81 can be used for several different index methods (for example, both B-tree
82 and hash index methods have operator classes named
83 <literal>int4_ops</literal>), but each such class is an independent
84 entity and must be defined separately.
88 <sect2 id="xindex-strategies">
89 <title>Index Method Strategies</title>
92 The operators associated with an operator class are identified by
93 <quote>strategy numbers</>, which serve to identify the semantics of
94 each operator within the context of its operator class.
95 For example, B-trees impose a strict ordering on keys, lesser to greater,
96 and so operators like <quote>less than</> and <quote>greater than or equal
97 to</> are interesting with respect to a B-tree.
99 <productname>PostgreSQL</productname> allows the user to define operators,
100 <productname>PostgreSQL</productname> cannot look at the name of an operator
101 (e.g., <literal><</> or <literal>>=</>) and tell what kind of
102 comparison it is. Instead, the index method defines a set of
103 <quote>strategies</>, which can be thought of as generalized operators.
104 Each operator class specifies which actual operator corresponds to each
105 strategy for a particular data type and interpretation of the index
110 The B-tree index method defines five strategies, shown in <xref
111 linkend="xindex-btree-strat-table">.
114 <table tocentry="1" id="xindex-btree-strat-table">
115 <title>B-tree Strategies</title>
119 <entry>Operation</entry>
120 <entry>Strategy Number</entry>
125 <entry>less than</entry>
129 <entry>less than or equal</entry>
137 <entry>greater than or equal</entry>
141 <entry>greater than</entry>
149 Hash indexes express only bitwise equality, and so they use only one
150 strategy, shown in <xref linkend="xindex-hash-strat-table">.
153 <table tocentry="1" id="xindex-hash-strat-table">
154 <title>Hash Strategies</title>
158 <entry>Operation</entry>
159 <entry>Strategy Number</entry>
172 R-tree indexes express rectangle-containment relationships.
173 They use eight strategies, shown in <xref linkend="xindex-rtree-strat-table">.
176 <table tocentry="1" id="xindex-rtree-strat-table">
177 <title>R-tree Strategies</title>
181 <entry>Operation</entry>
182 <entry>Strategy Number</entry>
187 <entry>left of</entry>
191 <entry>left of or overlapping</entry>
195 <entry>overlapping</entry>
199 <entry>right of or overlapping</entry>
203 <entry>right of</entry>
211 <entry>contains</entry>
215 <entry>contained by</entry>
223 GiST indexes are even more flexible: they do not have a fixed set of
224 strategies at all. Instead, the <quote>consistency</> support routine
225 of each particular GiST operator class interprets the strategy numbers
230 Note that all strategy operators return Boolean values. In
231 practice, all operators defined as index method strategies must
232 return type <type>boolean</type>, since they must appear at the top
233 level of a <literal>WHERE</> clause to be used with an index.
237 By the way, the <structfield>amorderstrategy</structfield> column
238 in <classname>pg_am</> tells whether
239 the index method supports ordered scans. Zero means it doesn't; if it
240 does, <structfield>amorderstrategy</structfield> is the strategy
241 number that corresponds to the ordering operator. For example, B-tree
242 has <structfield>amorderstrategy</structfield> = 1, which is its
243 <quote>less than</quote> strategy number.
247 <sect2 id="xindex-support">
248 <title>Index Method Support Routines</title>
251 Strategies aren't usually enough information for the system to figure
252 out how to use an index. In practice, the index methods require
253 additional support routines in order to work. For example, the B-tree
254 index method must be able to compare two keys and determine whether one
255 is greater than, equal to, or less than the other. Similarly, the
256 R-tree index method must be able to compute
257 intersections, unions, and sizes of rectangles. These
258 operations do not correspond to operators used in qualifications in
259 SQL commands; they are administrative routines used by
260 the index methods, internally.
264 Just as with strategies, the operator class identifies which specific
265 functions should play each of these roles for a given data type and
266 semantic interpretation. The index method defines the set
267 of functions it needs, and the operator class identifies the correct
268 functions to use by assigning them to the <quote>support function numbers</>.
272 B-trees require a single support function, shown in <xref
273 linkend="xindex-btree-support-table">.
276 <table tocentry="1" id="xindex-btree-support-table">
277 <title>B-tree Support Functions</title>
281 <entry>Function</entry>
282 <entry>Support Number</entry>
288 Compare two keys and return an integer less than zero, zero, or
289 greater than zero, indicating whether the first key is less than, equal to,
290 or greater than the second.
299 Hash indexes likewise require one support function, shown in <xref
300 linkend="xindex-hash-support-table">.
303 <table tocentry="1" id="xindex-hash-support-table">
304 <title>Hash Support Functions</title>
308 <entry>Function</entry>
309 <entry>Support Number</entry>
314 <entry>Compute the hash value for a key</entry>
322 R-tree indexes require three support functions,
323 shown in <xref linkend="xindex-rtree-support-table">.
326 <table tocentry="1" id="xindex-rtree-support-table">
327 <title>R-tree Support Functions</title>
331 <entry>Function</entry>
332 <entry>Support Number</entry>
341 <entry>intersection</entry>
353 GiST indexes require seven support functions,
354 shown in <xref linkend="xindex-gist-support-table">.
357 <table tocentry="1" id="xindex-gist-support-table">
358 <title>GiST Support Functions</title>
362 <entry>Function</entry>
363 <entry>Support Number</entry>
368 <entry>consistent</entry>
376 <entry>compress</entry>
380 <entry>decompress</entry>
384 <entry>penalty</entry>
388 <entry>picksplit</entry>
400 Unlike strategy operators, support functions return whichever data
401 type the particular index method expects, for example in the case
402 of the comparison function for B-trees, a signed integer.
406 <sect2 id="xindex-example">
407 <title>An Example</title>
410 Now that we have seen the ideas, here is the promised example of
411 creating a new operator class.
412 (You can find a working copy of this example in
413 <filename>src/tutorial/complex.c</filename> and
414 <filename>src/tutorial/complex.sql</filename> in the source
416 The operator class encapsulates
417 operators that sort complex numbers in absolute value order, so we
418 choose the name <literal>complex_abs_ops</literal>. First, we need
419 a set of operators. The procedure for defining operators was
420 discussed in <xref linkend="xoper">. For an operator class on
421 B-trees, the operators we require are:
423 <itemizedlist spacing="compact">
424 <listitem><simpara>absolute-value less-than (strategy 1)</></>
425 <listitem><simpara>absolute-value less-than-or-equal (strategy 2)</></>
426 <listitem><simpara>absolute-value equal (strategy 3)</></>
427 <listitem><simpara>absolute-value greater-than-or-equal (strategy 4)</></>
428 <listitem><simpara>absolute-value greater-than (strategy 5)</></>
433 The least error-prone way to define a related set of comparison operators
434 is to write the B-tree comparison support function first, and then write the
435 other functions as one-line wrappers around the support function. This
436 reduces the odds of getting inconsistent results for corner cases.
437 Following this approach, we first write
440 #define Mag(c) ((c)->x*(c)->x + (c)->y*(c)->y)
443 complex_abs_cmp_internal(Complex *a, Complex *b)
445 double amag = Mag(a),
456 Now the less-than function looks like
459 PG_FUNCTION_INFO_V1(complex_abs_lt);
462 complex_abs_lt(PG_FUNCTION_ARGS)
464 Complex *a = (Complex *) PG_GETARG_POINTER(0);
465 Complex *b = (Complex *) PG_GETARG_POINTER(1);
467 PG_RETURN_BOOL(complex_abs_cmp_internal(a, b) < 0);
471 The other four functions differ only in how they compare the internal
472 function's result to zero.
476 Next we declare the functions and the operators based on the functions
480 CREATE FUNCTION complex_abs_lt(complex, complex) RETURNS bool
481 AS '<replaceable>filename</replaceable>', 'complex_abs_lt'
482 LANGUAGE C IMMUTABLE STRICT;
484 CREATE OPERATOR < (
485 leftarg = complex, rightarg = complex, procedure = complex_abs_lt,
486 commutator = > , negator = >= ,
487 restrict = scalarltsel, join = scalarltjoinsel
490 It is important to specify the correct commutator and negator operators,
491 as well as suitable restriction and join selectivity
492 functions, otherwise the optimizer will be unable to make effective
493 use of the index. Note that the less-than, equal, and
494 greater-than cases should use different selectivity functions.
498 Other things worth noting are happening here:
503 There can only be one operator named, say, <literal>=</literal>
504 and taking type <type>complex</type> for both operands. In this
505 case we don't have any other operator <literal>=</literal> for
506 <type>complex</type>, but if we were building a practical data
507 type we'd probably want <literal>=</literal> to be the ordinary
508 equality operation for complex numbers (and not the equality of
509 the absolute values). In that case, we'd need to use some other
510 operator name for <function>complex_abs_eq</>.
516 Although <productname>PostgreSQL</productname> can cope with
517 functions having the same SQL name as long as they have different
518 argument data types, C can only cope with one global function
519 having a given name. So we shouldn't name the C function
520 something simple like <filename>abs_eq</filename>. Usually it's
521 a good practice to include the data type name in the C function
522 name, so as not to conflict with functions for other data types.
528 We could have made the SQL name
529 of the function <filename>abs_eq</filename>, relying on
530 <productname>PostgreSQL</productname> to distinguish it by
531 argument data types from any other SQL function of the same name.
532 To keep the example simple, we make the function have the same
533 names at the C level and SQL level.
540 The next step is the registration of the support routine required
541 by B-trees. The example C code that implements this is in the same
542 file that contains the operator functions. This is how we declare
546 CREATE FUNCTION complex_abs_cmp(complex, complex)
548 AS '<replaceable>filename</replaceable>'
549 LANGUAGE C IMMUTABLE STRICT;
554 Now that we have the required operators and support routine,
555 we can finally create the operator class:
558 CREATE OPERATOR CLASS complex_abs_ops
559 DEFAULT FOR TYPE complex USING btree AS
565 FUNCTION 1 complex_abs_cmp(complex, complex);
570 And we're done! It should now be possible to create
571 and use B-tree indexes on <type>complex</type> columns.
575 We could have written the operator entries more verbosely, as in
577 OPERATOR 1 < (complex, complex) ,
579 but there is no need to do so when the operators take the same data type
580 we are defining the operator class for.
584 The above example assumes that you want to make this new operator class the
585 default B-tree operator class for the <type>complex</type> data type.
586 If you don't, just leave out the word <literal>DEFAULT</>.
590 <sect2 id="xindex-opclass-crosstype">
591 <title>Cross-Data-Type Operator Classes</title>
594 So far we have implicitly assumed that an operator class deals with
595 only one data type. While there certainly can be only one data type in
596 a particular index column, it is often useful to index operations that
597 compare an indexed column to a value of a different data type. This is
598 presently supported by the B-tree and GiST index methods.
602 B-trees require the left-hand operand of each operator to be the indexed
603 data type, but the right-hand operand can be of a different type. There
604 must be a support function having a matching signature. For example,
605 the built-in operator class for type <type>bigint</> (<type>int8</>)
606 allows cross-type comparisons to <type>int4</> and <type>int2</>. It
607 could be duplicated by this definition:
610 CREATE OPERATOR CLASS int8_ops
611 DEFAULT FOR TYPE int8 USING btree AS
612 -- standard int8 comparisons
618 FUNCTION 1 btint8cmp(int8, int8) ,
620 -- cross-type comparisons to int2 (smallint)
621 OPERATOR 1 < (int8, int2) ,
622 OPERATOR 2 <= (int8, int2) ,
623 OPERATOR 3 = (int8, int2) ,
624 OPERATOR 4 >= (int8, int2) ,
625 OPERATOR 5 > (int8, int2) ,
626 FUNCTION 1 btint82cmp(int8, int2) ,
628 -- cross-type comparisons to int4 (integer)
629 OPERATOR 1 < (int8, int4) ,
630 OPERATOR 2 <= (int8, int4) ,
631 OPERATOR 3 = (int8, int4) ,
632 OPERATOR 4 >= (int8, int4) ,
633 OPERATOR 5 > (int8, int4) ,
634 FUNCTION 1 btint84cmp(int8, int4) ;
637 Notice that this definition <quote>overloads</> the operator strategy and
638 support function numbers. This is allowed (for B-tree operator classes
639 only) so long as each instance of a particular number has a different
640 right-hand data type. The instances that are not cross-type are the
641 default or primary operators of the operator class.
645 GiST indexes do not allow overloading of strategy or support function
646 numbers, but it is still possible to get the effect of supporting
647 multiple right-hand data types, by assigning a distinct strategy number
648 to each operator that needs to be supported. The <literal>consistent</>
649 support function must determine what it needs to do based on the strategy
650 number, and must be prepared to accept comparison values of the appropriate
655 <sect2 id="xindex-opclass-dependencies">
656 <title>System Dependencies on Operator Classes</title>
659 <primary>ordering operator</primary>
663 <productname>PostgreSQL</productname> uses operator classes to infer the
664 properties of operators in more ways than just whether they can be used
665 with indexes. Therefore, you might want to create operator classes
666 even if you have no intention of indexing any columns of your data type.
670 In particular, there are SQL features such as <literal>ORDER BY</> and
671 <literal>DISTINCT</> that require comparison and sorting of values.
672 To implement these features on a user-defined data type,
673 <productname>PostgreSQL</productname> looks for the default B-tree operator
674 class for the data type. The <quote>equals</> member of this operator
675 class defines the system's notion of equality of values for
676 <literal>GROUP BY</> and <literal>DISTINCT</>, and the sort ordering
677 imposed by the operator class defines the default <literal>ORDER BY</>
682 Comparison of arrays of user-defined types also relies on the semantics
683 defined by the default B-tree operator class.
687 If there is no default B-tree operator class for a data type, the system
688 will look for a default hash operator class. But since that kind of
689 operator class only provides equality, in practice it is only enough
690 to support array equality.
694 When there is no default operator class for a data type, you will get
695 errors like <quote>could not identify an ordering operator</> if you
696 try to use these SQL features with the data type.
701 In <productname>PostgreSQL</productname> versions before 7.4,
702 sorting and grouping operations would implicitly use operators named
703 <literal>=</>, <literal><</>, and <literal>></>. The new
704 behavior of relying on default operator classes avoids having to make
705 any assumption about the behavior of operators with particular names.
710 <sect2 id="xindex-opclass-features">
711 <title>Special Features of Operator Classes</title>
714 There are two special features of operator classes that we have
715 not discussed yet, mainly because they are not useful
716 with the most commonly used index methods.
720 Normally, declaring an operator as a member of an operator class means
721 that the index method can retrieve exactly the set of rows
722 that satisfy a <literal>WHERE</> condition using the operator. For example,
724 SELECT * FROM table WHERE integer_column < 4;
726 can be satisfied exactly by a B-tree index on the integer column.
727 But there are cases where an index is useful as an inexact guide to
728 the matching rows. For example, if an R-tree index stores only
729 bounding boxes for objects, then it cannot exactly satisfy a <literal>WHERE</>
730 condition that tests overlap between nonrectangular objects such as
731 polygons. Yet we could use the index to find objects whose bounding
732 box overlaps the bounding box of the target object, and then do the
733 exact overlap test only on the objects found by the index. If this
734 scenario applies, the index is said to be <quote>lossy</> for the
735 operator, and we add <literal>RECHECK</> to the <literal>OPERATOR</> clause
736 in the <command>CREATE OPERATOR CLASS</> command.
737 <literal>RECHECK</> is valid if the index is guaranteed to return
738 all the required rows, plus perhaps some additional rows, which
739 can be eliminated by performing the original operator invocation.
743 Consider again the situation where we are storing in the index only
744 the bounding box of a complex object such as a polygon. In this
745 case there's not much value in storing the whole polygon in the index
746 entry — we may as well store just a simpler object of type
747 <type>box</>. This situation is expressed by the <literal>STORAGE</>
748 option in <command>CREATE OPERATOR CLASS</>: we'd write something like
751 CREATE OPERATOR CLASS polygon_ops
752 DEFAULT FOR TYPE polygon USING gist AS
757 At present, only the GiST index method supports a
758 <literal>STORAGE</> type that's different from the column data type.
759 The GiST <literal>compress</> and <literal>decompress</> support
760 routines must deal with data-type conversion when <literal>STORAGE</>
767 <!-- Keep this comment at the end of the file
772 sgml-minimize-attributes:nil
773 sgml-always-quote-attributes:t
776 sgml-parent-document:nil
777 sgml-default-dtd-file:"./reference.ced"
778 sgml-exposed-tags:nil
779 sgml-local-catalogs:("/usr/lib/sgml/catalog")
780 sgml-local-ecat-files:nil
projects / postgresql / blob