2 $Header: /cvsroot/pgsql/doc/src/sgml/xindex.sgml,v 1.31 2003/08/17 22:09:00 tgl Exp $
6 <title>Interfacing Extensions To Indexes</title>
9 The procedures described thus far let you define new types, new
10 functions, and new operators. However, we cannot yet define an
11 index on a column of a new data type. To do this, we must define an
12 <firstterm>operator class</> for the new data type. Later in this
13 section, we will illustrate this concept in an example: a new
14 operator class for the B-tree index method that stores and sorts
15 complex numbers in ascending absolute value order.
20 Prior to <productname>PostgreSQL</productname> release 7.3, it was
21 necessary to make manual additions to the system catalogs
22 <classname>pg_amop</>, <classname>pg_amproc</>, and
23 <classname>pg_opclass</> in order to create a user-defined
24 operator class. That approach is now deprecated in favor of
25 using <command>CREATE OPERATOR CLASS</>, which is a much simpler
26 and less error-prone way of creating the necessary catalog entries.
30 <sect2 id="xindex-im">
31 <title>Index Methods and Operator Classes</title>
34 The <classname>pg_am</classname> table contains one row for every
35 index method (internally known as access method). Support for
36 regular access to tables is built into
37 <productname>PostgreSQL</productname>, but all index methods are
38 described in <classname>pg_am</classname>. It is possible to add a
39 new index method by defining the required interface routines and
40 then creating a row in <classname>pg_am</classname> --- but that is
41 far beyond the scope of this chapter.
45 The routines for an index method do not directly know anything
46 about the data types that the index method will operate on. Instead, an
47 <firstterm>operator class</> identifies the set of operations that the
48 index method needs to use to work with a particular data type.
49 Operator classes are so called because one thing they specify is the set
50 of <literal>WHERE</>-clause operators that can be used with an index (i.e., can be
51 converted into an index-scan qualification). An operator class may also
52 specify some <firstterm>support procedures</> that are needed by the
53 internal operations of the index method, but do not directly
54 correspond to any <literal>WHERE</>-clause operator that can be used with the index.
58 It is possible to define multiple operator classes for the same
59 data type and index method. By doing this, multiple
60 sets of indexing semantics can be defined for a single data type.
61 For example, a B-tree index requires a sort ordering to be defined
62 for each data type it works on.
63 It might be useful for a complex-number data type
64 to have one B-tree operator class that sorts the data by complex
65 absolute value, another that sorts by real part, and so on.
66 Typically, one of the operator classes will be deemed most commonly
67 useful and will be marked as the default operator class for that
68 data type and index method.
72 The same operator class name
73 can be used for several different index methods (for example, both B-tree
74 and hash index methods have operator classes named
75 <literal>oid_ops</literal>), but each such class is an independent
76 entity and must be defined separately.
80 <sect2 id="xindex-strategies">
81 <title>Index Method Strategies</title>
84 The operators associated with an operator class are identified by
85 <quote>strategy numbers</>, which serve to identify the semantics of
86 each operator within the context of its operator class.
87 For example, B-trees impose a strict ordering on keys, lesser to greater,
88 and so operators like <quote>less than</> and <quote>greater than or equal
89 to</> are interesting with respect to a B-tree.
91 <productname>PostgreSQL</productname> allows the user to define operators,
92 <productname>PostgreSQL</productname> cannot look at the name of an operator
93 (e.g., <literal><</> or <literal>>=</>) and tell what kind of
94 comparison it is. Instead, the index method defines a set of
95 <quote>strategies</>, which can be thought of as generalized operators.
96 Each operator class specifies which actual operator corresponds to each
97 strategy for a particular data type and interpretation of the index
102 The B-tree index method defines five strategies, shown in <xref
103 linkend="xindex-btree-strat-table">.
106 <table tocentry="1" id="xindex-btree-strat-table">
107 <title>B-tree Strategies</title>
111 <entry>Operation</entry>
112 <entry>Strategy Number</entry>
117 <entry>less than</entry>
121 <entry>less than or equal</entry>
129 <entry>greater than or equal</entry>
133 <entry>greater than</entry>
141 Hash indexes express only bitwise equality, and so they use only one
142 strategy, shown in <xref linkend="xindex-hash-strat-table">.
145 <table tocentry="1" id="xindex-hash-strat-table">
146 <title>Hash Strategies</title>
150 <entry>Operation</entry>
151 <entry>Strategy Number</entry>
164 R-tree indexes express rectangle-containment relationships.
165 They use eight strategies, shown in <xref linkend="xindex-rtree-strat-table">.
168 <table tocentry="1" id="xindex-rtree-strat-table">
169 <title>R-tree Strategies</title>
173 <entry>Operation</entry>
174 <entry>Strategy Number</entry>
179 <entry>left of</entry>
183 <entry>left of or overlapping</entry>
187 <entry>overlapping</entry>
191 <entry>right of or overlapping</entry>
195 <entry>right of</entry>
203 <entry>contains</entry>
207 <entry>contained by</entry>
215 GiST indexes are even more flexible: they do not have a fixed set of
216 strategies at all. Instead, the <quote>consistency</> support routine
217 of each particular GiST operator class interprets the strategy numbers
222 Note that all strategy operators return Boolean values. In
223 practice, all operators defined as index method strategies must
224 return type <type>boolean</type>, since they must appear at the top
225 level of a <literal>WHERE</> clause to be used with an index.
229 By the way, the <structfield>amorderstrategy</structfield> column
230 in <classname>pg_am</> tells whether
231 the index method supports ordered scans. Zero means it doesn't; if it
232 does, <structfield>amorderstrategy</structfield> is the strategy
233 number that corresponds to the ordering operator. For example, B-tree
234 has <structfield>amorderstrategy</structfield> = 1, which is its
235 <quote>less than</quote> strategy number.
239 <sect2 id="xindex-support">
240 <title>Index Method Support Routines</title>
243 Strategies aren't usually enough information for the system to figure
244 out how to use an index. In practice, the index methods require
245 additional support routines in order to work. For example, the B-tree
246 index method must be able to compare two keys and determine whether one
247 is greater than, equal to, or less than the other. Similarly, the
248 R-tree index method must be able to compute
249 intersections, unions, and sizes of rectangles. These
250 operations do not correspond to operators used in qualifications in
251 SQL commands; they are administrative routines used by
252 the index methods, internally.
256 Just as with strategies, the operator class identifies which specific
257 functions should play each of these roles for a given data type and
258 semantic interpretation. The index method defines the set
259 of functions it needs, and the operator class identifies the correct
260 functions to use by assigning them to the <quote>support function numbers</>.
264 B-trees require a single support function, shown in <xref
265 linkend="xindex-btree-support-table">.
268 <table tocentry="1" id="xindex-btree-support-table">
269 <title>B-tree Support Functions</title>
273 <entry>Function</entry>
274 <entry>Support Number</entry>
280 Compare two keys and return an integer less than zero, zero, or
281 greater than zero, indicating whether the first key is less than, equal to,
282 or greater than the second.
291 Hash indexes likewise require one support function, shown in <xref
292 linkend="xindex-hash-support-table">.
295 <table tocentry="1" id="xindex-hash-support-table">
296 <title>Hash Support Functions</title>
300 <entry>Function</entry>
301 <entry>Support Number</entry>
306 <entry>Compute the hash value for a key</entry>
314 R-tree indexes require three support functions,
315 shown in <xref linkend="xindex-rtree-support-table">.
318 <table tocentry="1" id="xindex-rtree-support-table">
319 <title>R-tree Support Functions</title>
323 <entry>Function</entry>
324 <entry>Support Number</entry>
333 <entry>intersection</entry>
345 GiST indexes require seven support functions,
346 shown in <xref linkend="xindex-gist-support-table">.
349 <table tocentry="1" id="xindex-gist-support-table">
350 <title>GiST Support Functions</title>
354 <entry>Function</entry>
355 <entry>Support Number</entry>
360 <entry>consistent</entry>
368 <entry>compress</entry>
372 <entry>decompress</entry>
376 <entry>penalty</entry>
380 <entry>picksplit</entry>
392 Unlike strategy operators, support functions return whichever data
393 type the particular index method expects, for example in the case
394 of the comparison function for B-trees, a signed integer.
398 <sect2 id="xindex-example">
399 <title>An Example</title>
402 Now that we have seen the ideas, here is the promised example of
403 creating a new operator class. The operator class encapsulates
404 operators that sort complex numbers in absolute value order, so we
405 choose the name <literal>complex_abs_ops</literal>. First, we need
406 a set of operators. The procedure for defining operators was
407 discussed in <xref linkend="xoper">. For an operator class on
408 B-trees, the operators we require are:
410 <itemizedlist spacing="compact">
411 <listitem><simpara>absolute-value less-than (strategy 1)</></>
412 <listitem><simpara>absolute-value less-than-or-equal (strategy 2)</></>
413 <listitem><simpara>absolute-value equal (strategy 3)</></>
414 <listitem><simpara>absolute-value greater-than-or-equal (strategy 4)</></>
415 <listitem><simpara>absolute-value greater-than (strategy 5)</></>
420 The C code for the equality operator look like this:
423 #define Mag(c) ((c)->x*(c)->x + (c)->y*(c)->y)
426 complex_abs_eq(Complex *a, Complex *b)
428 double amag = Mag(a), bmag = Mag(b);
429 return (amag == bmag);
432 The other four operators are very similar. You can find their code
433 in <filename>src/tutorial/complex.c</filename> and
434 <filename>src/tutorial/complex.sql</filename> in the source
439 Now declare the functions and the operators based on the functions:
441 CREATE FUNCTION complex_abs_eq(complex, complex) RETURNS boolean
442 AS '<replaceable>filename</replaceable>', 'complex_abs_eq'
448 procedure = complex_abs_eq,
453 It is important to specify the restriction and join selectivity
454 functions, otherwise the optimizer will be unable to make effective
455 use of the index. Note that the less-than, equal, and
456 greater-than cases should use different selectivity functions.
460 Other things worth noting are happening here:
465 There can only be one operator named, say, <literal>=</literal>
466 and taking type <type>complex</type> for both operands. In this
467 case we don't have any other operator <literal>=</literal> for
468 <type>complex</type>, but if we were building a practical data
469 type we'd probably want <literal>=</literal> to be the ordinary
470 equality operation for complex numbers (and not the equality of
471 the absolute values). In that case, we'd need to use some other
472 operator name for <function>complex_abs_eq</>.
478 Although <productname>PostgreSQL</productname> can cope with
479 functions having the same name as long as they have different
480 argument data types, C can only cope with one global function
481 having a given name. So we shouldn't name the C function
482 something simple like <filename>abs_eq</filename>. Usually it's
483 a good practice to include the data type name in the C function
484 name, so as not to conflict with functions for other data types.
490 We could have made the <productname>PostgreSQL</productname> name
491 of the function <filename>abs_eq</filename>, relying on
492 <productname>PostgreSQL</productname> to distinguish it by
493 argument data types from any other
494 <productname>PostgreSQL</productname> function of the same name.
495 To keep the example simple, we make the function have the same
496 names at the C level and <productname>PostgreSQL</productname>
504 The next step is the registration of the support routine required
505 by B-trees. The example C code that implements this is in the same
506 file that contains the operator functions. This is how we declare
510 CREATE FUNCTION complex_abs_cmp(complex, complex)
512 AS '<replaceable>filename</replaceable>'
518 Now that we have the required operators and support routine,
519 we can finally create the operator class:
522 CREATE OPERATOR CLASS complex_abs_ops
523 DEFAULT FOR TYPE complex USING btree AS
529 FUNCTION 1 complex_abs_cmp(complex, complex);
534 And we're done! It should now be possible to create
535 and use B-tree indexes on <type>complex</type> columns.
539 We could have written the operator entries more verbosely, as in
541 OPERATOR 1 < (complex, complex) ,
543 but there is no need to do so when the operators take the same data type
544 we are defining the operator class for.
548 The above example assumes that you want to make this new operator class the
549 default B-tree operator class for the <type>complex</type> data type.
550 If you don't, just leave out the word <literal>DEFAULT</>.
554 <sect2 id="xindex-opclass-dependencies">
555 <title>System Dependencies on Operator Classes</title>
558 <primary>ordering operator</primary>
562 <productname>PostgreSQL</productname> uses operator classes to infer the
563 properties of operators in more ways than just whether they can be used
564 with indexes. Therefore, you might want to create operator classes
565 even if you have no intention of indexing any columns of your datatype.
569 In particular, there are SQL features such as <literal>ORDER BY</> and
570 <literal>DISTINCT</> that require comparison and sorting of values.
571 To implement these features on a user-defined datatype,
572 <productname>PostgreSQL</productname> looks for the default B-tree operator
573 class for the datatype. The <quote>equals</> member of this operator
574 class defines the system's notion of equality of values for
575 <literal>GROUP BY</> and <literal>DISTINCT</>, and the sort ordering
576 imposed by the operator class defines the default <literal>ORDER BY</>
581 Comparison of arrays of user-defined types also relies on the semantics
582 defined by the default B-tree operator class.
586 If there is no default B-tree operator class for a datatype, the system
587 will look for a default hash operator class. But since that kind of
588 operator class only provides equality, in practice it is only enough
589 to support array equality.
593 When there is no default operator class for a datatype, you will get
594 errors like <quote>could not identify an ordering operator</> if you
595 try to use these SQL features with the datatype.
600 In <ProductName>PostgreSQL</ProductName> versions before 7.4,
601 sorting and grouping operations would implicitly use operators named
602 <literal>=</>, <literal><</>, and <literal>></>. The new
603 behavior of relying on default operator classes avoids having to make
604 any assumption about the behavior of operators with particular names.
609 <sect2 id="xindex-opclass-features">
610 <title>Special Features of Operator Classes</title>
613 There are two special features of operator classes that we have
614 not discussed yet, mainly because they are not useful
615 with the most commonly used index methods.
619 Normally, declaring an operator as a member of an operator class means
620 that the index method can retrieve exactly the set of rows
621 that satisfy a <literal>WHERE</> condition using the operator. For example,
623 SELECT * FROM table WHERE integer_column < 4;
625 can be satisfied exactly by a B-tree index on the integer column.
626 But there are cases where an index is useful as an inexact guide to
627 the matching rows. For example, if an R-tree index stores only
628 bounding boxes for objects, then it cannot exactly satisfy a <literal>WHERE</>
629 condition that tests overlap between nonrectangular objects such as
630 polygons. Yet we could use the index to find objects whose bounding
631 box overlaps the bounding box of the target object, and then do the
632 exact overlap test only on the objects found by the index. If this
633 scenario applies, the index is said to be <quote>lossy</> for the
634 operator, and we add <literal>RECHECK</> to the <literal>OPERATOR</> clause
635 in the <command>CREATE OPERATOR CLASS</> command.
636 <literal>RECHECK</> is valid if the index is guaranteed to return
637 all the required rows, plus perhaps some additional rows, which
638 can be eliminated by performing the original operator invocation.
642 Consider again the situation where we are storing in the index only
643 the bounding box of a complex object such as a polygon. In this
644 case there's not much value in storing the whole polygon in the index
645 entry --- we may as well store just a simpler object of type
646 <type>box</>. This situation is expressed by the <literal>STORAGE</>
647 option in <command>CREATE OPERATOR CLASS</>: we'd write something like
650 CREATE OPERATOR CLASS polygon_ops
651 DEFAULT FOR TYPE polygon USING gist AS
656 At present, only the GiST index method supports a
657 <literal>STORAGE</> type that's different from the column data type.
658 The GiST <literal>compress</> and <literal>decompress</> support
659 routines must deal with data-type conversion when <literal>STORAGE</>
666 <!-- Keep this comment at the end of the file
671 sgml-minimize-attributes:nil
672 sgml-always-quote-attributes:t
675 sgml-parent-document:nil
676 sgml-default-dtd-file:"./reference.ced"
677 sgml-exposed-tags:nil
678 sgml-local-catalogs:("/usr/lib/sgml/catalog")
679 sgml-local-ecat-files:nil
projects / postgresql / blob