1 <!-- doc/src/sgml/xindex.sgml -->
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.
22 Operator classes can be grouped into <firstterm>operator families</>
23 to show the relationships between semantically compatible classes.
24 When only a single data type is involved, an operator class is sufficient,
25 so we'll focus on that case first and then return to operator families.
28 <sect2 id="xindex-opclass">
29 <title>Index Methods and Operator Classes</title>
32 The <classname>pg_am</classname> table contains one row for every
33 index method (internally known as access method). Support for
34 regular access to tables is built into
35 <productname>PostgreSQL</productname>, but all index methods are
36 described in <classname>pg_am</classname>. It is possible to add a
37 new index method by defining the required interface routines and
38 then creating a row in <classname>pg_am</classname> — but that is
39 beyond the scope of this chapter (see <xref linkend="indexam">).
43 The routines for an index method do not directly know anything
44 about the data types that the index method will operate on.
45 Instead, an <firstterm>operator
46 class</><indexterm><primary>operator class</></indexterm>
47 identifies the set of operations that the index method needs to use
48 to work with a particular data type. Operator classes are so
49 called because one thing they specify is the set of
50 <literal>WHERE</>-clause operators that can be used with an index
51 (i.e., can be converted into an index-scan qualification). An
52 operator class can also specify some <firstterm>support
53 procedures</> that are needed by the internal operations of the
54 index method, but do not directly correspond to any
55 <literal>WHERE</>-clause operator that can be used with the index.
59 It is possible to define multiple operator classes for the same
60 data type and index method. By doing this, multiple
61 sets of indexing semantics can be defined for a single data type.
62 For example, a B-tree index requires a sort ordering to be defined
63 for each data type it works on.
64 It might be useful for a complex-number data type
65 to have one B-tree operator class that sorts the data by complex
66 absolute value, another that sorts by real part, and so on.
67 Typically, one of the operator classes will be deemed most commonly
68 useful and will be marked as the default operator class for that
69 data type and index method.
73 The same operator class name
74 can be used for several different index methods (for example, both B-tree
75 and hash index methods have operator classes named
76 <literal>int4_ops</literal>), but each such class is an independent
77 entity and must be defined separately.
81 <sect2 id="xindex-strategies">
82 <title>Index Method Strategies</title>
85 The operators associated with an operator class are identified by
86 <quote>strategy numbers</>, which serve to identify the semantics of
87 each operator within the context of its operator class.
88 For example, B-trees impose a strict ordering on keys, lesser to greater,
89 and so operators like <quote>less than</> and <quote>greater than or equal
90 to</> are interesting with respect to a B-tree.
92 <productname>PostgreSQL</productname> allows the user to define operators,
93 <productname>PostgreSQL</productname> cannot look at the name of an operator
94 (e.g., <literal><</> or <literal>>=</>) and tell what kind of
95 comparison it is. Instead, the index method defines a set of
96 <quote>strategies</>, which can be thought of as generalized operators.
97 Each operator class specifies which actual operator corresponds to each
98 strategy for a particular data type and interpretation of the index
103 The B-tree index method defines five strategies, shown in <xref
104 linkend="xindex-btree-strat-table">.
107 <table tocentry="1" id="xindex-btree-strat-table">
108 <title>B-tree Strategies</title>
112 <entry>Operation</entry>
113 <entry>Strategy Number</entry>
118 <entry>less than</entry>
122 <entry>less than or equal</entry>
130 <entry>greater than or equal</entry>
134 <entry>greater than</entry>
142 Hash indexes support only equality comparisons, and so they use only one
143 strategy, shown in <xref linkend="xindex-hash-strat-table">.
146 <table tocentry="1" id="xindex-hash-strat-table">
147 <title>Hash Strategies</title>
151 <entry>Operation</entry>
152 <entry>Strategy Number</entry>
165 GiST indexes are more flexible: they do not have a fixed set of
166 strategies at all. Instead, the <quote>consistency</> support routine
167 of each particular GiST operator class interprets the strategy numbers
168 however it likes. As an example, several of the built-in GiST index
169 operator classes index two-dimensional geometric objects, providing
170 the <quote>R-tree</> strategies shown in
171 <xref linkend="xindex-rtree-strat-table">. Four of these are true
172 two-dimensional tests (overlaps, same, contains, contained by);
173 four of them consider only the X direction; and the other four
174 provide the same tests in the Y direction.
177 <table tocentry="1" id="xindex-rtree-strat-table">
178 <title>GiST Two-Dimensional <quote>R-tree</> Strategies</title>
182 <entry>Operation</entry>
183 <entry>Strategy Number</entry>
188 <entry>strictly left of</entry>
192 <entry>does not extend to right of</entry>
196 <entry>overlaps</entry>
200 <entry>does not extend to left of</entry>
204 <entry>strictly right of</entry>
212 <entry>contains</entry>
216 <entry>contained by</entry>
220 <entry>does not extend above</entry>
224 <entry>strictly below</entry>
228 <entry>strictly above</entry>
232 <entry>does not extend below</entry>
240 GIN indexes are similar to GiST indexes in flexibility: they don't have a
241 fixed set of strategies. Instead the support routines of each operator
242 class interpret the strategy numbers according to the operator class's
243 definition. As an example, the strategy numbers used by the built-in
244 operator classes for arrays are
245 shown in <xref linkend="xindex-gin-array-strat-table">.
248 <table tocentry="1" id="xindex-gin-array-strat-table">
249 <title>GIN Array Strategies</title>
253 <entry>Operation</entry>
254 <entry>Strategy Number</entry>
259 <entry>overlap</entry>
263 <entry>contains</entry>
267 <entry>is contained by</entry>
279 Notice that all strategy operators return Boolean values. In
280 practice, all operators defined as index method strategies must
281 return type <type>boolean</type>, since they must appear at the top
282 level of a <literal>WHERE</> clause to be used with an index.
286 <sect2 id="xindex-support">
287 <title>Index Method Support Routines</title>
290 Strategies aren't usually enough information for the system to figure
291 out how to use an index. In practice, the index methods require
292 additional support routines in order to work. For example, the B-tree
293 index method must be able to compare two keys and determine whether one
294 is greater than, equal to, or less than the other. Similarly, the
295 hash index method must be able to compute hash codes for key values.
296 These operations do not correspond to operators used in qualifications in
297 SQL commands; they are administrative routines used by
298 the index methods, internally.
302 Just as with strategies, the operator class identifies which specific
303 functions should play each of these roles for a given data type and
304 semantic interpretation. The index method defines the set
305 of functions it needs, and the operator class identifies the correct
306 functions to use by assigning them to the <quote>support function numbers</>
307 specified by the index method.
311 B-trees require a single support function, shown in <xref
312 linkend="xindex-btree-support-table">.
315 <table tocentry="1" id="xindex-btree-support-table">
316 <title>B-tree Support Functions</title>
320 <entry>Function</entry>
321 <entry>Support Number</entry>
327 Compare two keys and return an integer less than zero, zero, or
328 greater than zero, indicating whether the first key is less than,
329 equal to, or greater than the second
338 Hash indexes likewise require one support function, shown in <xref
339 linkend="xindex-hash-support-table">.
342 <table tocentry="1" id="xindex-hash-support-table">
343 <title>Hash Support Functions</title>
347 <entry>Function</entry>
348 <entry>Support Number</entry>
353 <entry>Compute the hash value for a key</entry>
361 GiST indexes require seven support functions,
362 shown in <xref linkend="xindex-gist-support-table">.
365 <table tocentry="1" id="xindex-gist-support-table">
366 <title>GiST Support Functions</title>
370 <entry>Function</entry>
371 <entry>Support Number</entry>
376 <entry>consistent - determine whether key satisfies the
377 query qualifier</entry>
381 <entry>union - compute union of a set of keys</entry>
385 <entry>compress - compute a compressed representation of a key or value
386 to be indexed</entry>
390 <entry>decompress - compute a decompressed representation of a
391 compressed key</entry>
395 <entry>penalty - compute penalty for inserting new key into subtree
396 with given subtree's key</entry>
400 <entry>picksplit - determine which entries of a page are to be moved
401 to the new page and compute the union keys for resulting pages</entry>
405 <entry>equal - compare two keys and return true if they are equal</entry>
413 GIN indexes require four support functions,
414 shown in <xref linkend="xindex-gin-support-table">.
417 <table tocentry="1" id="xindex-gin-support-table">
418 <title>GIN Support Functions</title>
422 <entry>Function</entry>
423 <entry>Description</entry>
424 <entry>Support Number</entry>
429 <entry><function>compare</></entry>
431 compare two keys and return an integer less than zero, zero,
432 or greater than zero, indicating whether the first key is less than,
433 equal to, or greater than the second
438 <entry><function>extractValue</></entry>
439 <entry>extract keys from a value to be indexed</entry>
443 <entry><function>extractQuery</></entry>
444 <entry>extract keys from a query condition</entry>
448 <entry><function>consistent</></entry>
449 <entry>determine whether value matches query condition</entry>
453 <entry><function>comparePartial</></entry>
455 (optional method) compare partial key from
456 query and key from index, and return an integer less than zero, zero,
457 or greater than zero, indicating whether GIN should ignore this index
458 entry, treat the entry as a match, or stop the index scan
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. The number
470 and types of the arguments to each support function are likewise
471 dependent on the index method. For B-tree and hash the support functions
472 take the same input data types as do the operators included in the operator
473 class, but this is not the case for most GIN and GiST support functions.
477 <sect2 id="xindex-example">
478 <title>An Example</title>
481 Now that we have seen the ideas, here is the promised example of
482 creating a new operator class.
483 (You can find a working copy of this example in
484 <filename>src/tutorial/complex.c</filename> and
485 <filename>src/tutorial/complex.sql</filename> in the source
487 The operator class encapsulates
488 operators that sort complex numbers in absolute value order, so we
489 choose the name <literal>complex_abs_ops</literal>. First, we need
490 a set of operators. The procedure for defining operators was
491 discussed in <xref linkend="xoper">. For an operator class on
492 B-trees, the operators we require are:
494 <itemizedlist spacing="compact">
495 <listitem><simpara>absolute-value less-than (strategy 1)</></>
496 <listitem><simpara>absolute-value less-than-or-equal (strategy 2)</></>
497 <listitem><simpara>absolute-value equal (strategy 3)</></>
498 <listitem><simpara>absolute-value greater-than-or-equal (strategy 4)</></>
499 <listitem><simpara>absolute-value greater-than (strategy 5)</></>
504 The least error-prone way to define a related set of comparison operators
505 is to write the B-tree comparison support function first, and then write the
506 other functions as one-line wrappers around the support function. This
507 reduces the odds of getting inconsistent results for corner cases.
508 Following this approach, we first write:
510 <programlisting><![CDATA[
511 #define Mag(c) ((c)->x*(c)->x + (c)->y*(c)->y)
514 complex_abs_cmp_internal(Complex *a, Complex *b)
516 double amag = Mag(a),
528 Now the less-than function looks like:
530 <programlisting><![CDATA[
531 PG_FUNCTION_INFO_V1(complex_abs_lt);
534 complex_abs_lt(PG_FUNCTION_ARGS)
536 Complex *a = (Complex *) PG_GETARG_POINTER(0);
537 Complex *b = (Complex *) PG_GETARG_POINTER(1);
539 PG_RETURN_BOOL(complex_abs_cmp_internal(a, b) < 0);
544 The other four functions differ only in how they compare the internal
545 function's result to zero.
549 Next we declare the functions and the operators based on the functions
553 CREATE FUNCTION complex_abs_lt(complex, complex) RETURNS bool
554 AS '<replaceable>filename</replaceable>', 'complex_abs_lt'
555 LANGUAGE C IMMUTABLE STRICT;
557 CREATE OPERATOR < (
558 leftarg = complex, rightarg = complex, procedure = complex_abs_lt,
559 commutator = > , negator = >= ,
560 restrict = scalarltsel, join = scalarltjoinsel
563 It is important to specify the correct commutator and negator operators,
564 as well as suitable restriction and join selectivity
565 functions, otherwise the optimizer will be unable to make effective
566 use of the index. Note that the less-than, equal, and
567 greater-than cases should use different selectivity functions.
571 Other things worth noting are happening here:
576 There can only be one operator named, say, <literal>=</literal>
577 and taking type <type>complex</type> for both operands. In this
578 case we don't have any other operator <literal>=</literal> for
579 <type>complex</type>, but if we were building a practical data
580 type we'd probably want <literal>=</literal> to be the ordinary
581 equality operation for complex numbers (and not the equality of
582 the absolute values). In that case, we'd need to use some other
583 operator name for <function>complex_abs_eq</>.
589 Although <productname>PostgreSQL</productname> can cope with
590 functions having the same SQL name as long as they have different
591 argument data types, C can only cope with one global function
592 having a given name. So we shouldn't name the C function
593 something simple like <filename>abs_eq</filename>. Usually it's
594 a good practice to include the data type name in the C function
595 name, so as not to conflict with functions for other data types.
601 We could have made the SQL name
602 of the function <filename>abs_eq</filename>, relying on
603 <productname>PostgreSQL</productname> to distinguish it by
604 argument data types from any other SQL function of the same name.
605 To keep the example simple, we make the function have the same
606 names at the C level and SQL level.
613 The next step is the registration of the support routine required
614 by B-trees. The example C code that implements this is in the same
615 file that contains the operator functions. This is how we declare
619 CREATE FUNCTION complex_abs_cmp(complex, complex)
621 AS '<replaceable>filename</replaceable>'
622 LANGUAGE C IMMUTABLE STRICT;
627 Now that we have the required operators and support routine,
628 we can finally create the operator class:
630 <programlisting><![CDATA[
631 CREATE OPERATOR CLASS complex_abs_ops
632 DEFAULT FOR TYPE complex USING btree AS
638 FUNCTION 1 complex_abs_cmp(complex, complex);
644 And we're done! It should now be possible to create
645 and use B-tree indexes on <type>complex</type> columns.
649 We could have written the operator entries more verbosely, as in:
651 OPERATOR 1 < (complex, complex) ,
653 but there is no need to do so when the operators take the same data type
654 we are defining the operator class for.
658 The above example assumes that you want to make this new operator class the
659 default B-tree operator class for the <type>complex</type> data type.
660 If you don't, just leave out the word <literal>DEFAULT</>.
664 <sect2 id="xindex-opfamily">
665 <title>Operator Classes and Operator Families</title>
668 So far we have implicitly assumed that an operator class deals with
669 only one data type. While there certainly can be only one data type in
670 a particular index column, it is often useful to index operations that
671 compare an indexed column to a value of a different data type. Also,
672 if there is use for a cross-data-type operator in connection with an
673 operator class, it is often the case that the other data type has a
674 related operator class of its own. It is helpful to make the connections
675 between related classes explicit, because this can aid the planner in
676 optimizing SQL queries (particularly for B-tree operator classes, since
677 the planner contains a great deal of knowledge about how to work with them).
681 To handle these needs, <productname>PostgreSQL</productname>
682 uses the concept of an <firstterm>operator
683 family</><indexterm><primary>operator family</></indexterm>.
684 An operator family contains one or more operator classes, and can also
685 contain indexable operators and corresponding support functions that
686 belong to the family as a whole but not to any single class within the
687 family. We say that such operators and functions are <quote>loose</>
688 within the family, as opposed to being bound into a specific class.
689 Typically each operator class contains single-data-type operators
690 while cross-data-type operators are loose in the family.
694 All the operators and functions in an operator family must have compatible
695 semantics, where the compatibility requirements are set by the index
696 method. You might therefore wonder why bother to single out particular
697 subsets of the family as operator classes; and indeed for many purposes
698 the class divisions are irrelevant and the family is the only interesting
699 grouping. The reason for defining operator classes is that they specify
700 how much of the family is needed to support any particular index.
701 If there is an index using an operator class, then that operator class
702 cannot be dropped without dropping the index — but other parts of
703 the operator family, namely other operator classes and loose operators,
704 could be dropped. Thus, an operator class should be specified to contain
705 the minimum set of operators and functions that are reasonably needed
706 to work with an index on a specific data type, and then related but
707 non-essential operators can be added as loose members of the operator
712 As an example, <productname>PostgreSQL</productname> has a built-in
713 B-tree operator family <literal>integer_ops</>, which includes operator
714 classes <literal>int8_ops</>, <literal>int4_ops</>, and
715 <literal>int2_ops</> for indexes on <type>bigint</> (<type>int8</>),
716 <type>integer</> (<type>int4</>), and <type>smallint</> (<type>int2</>)
717 columns respectively. The family also contains cross-data-type comparison
718 operators allowing any two of these types to be compared, so that an index
719 on one of these types can be searched using a comparison value of another
720 type. The family could be duplicated by these definitions:
722 <programlisting><![CDATA[
723 CREATE OPERATOR FAMILY integer_ops USING btree;
725 CREATE OPERATOR CLASS int8_ops
726 DEFAULT FOR TYPE int8 USING btree FAMILY integer_ops AS
727 -- standard int8 comparisons
733 FUNCTION 1 btint8cmp(int8, int8) ;
735 CREATE OPERATOR CLASS int4_ops
736 DEFAULT FOR TYPE int4 USING btree FAMILY integer_ops AS
737 -- standard int4 comparisons
743 FUNCTION 1 btint4cmp(int4, int4) ;
745 CREATE OPERATOR CLASS int2_ops
746 DEFAULT FOR TYPE int2 USING btree FAMILY integer_ops AS
747 -- standard int2 comparisons
753 FUNCTION 1 btint2cmp(int2, int2) ;
755 ALTER OPERATOR FAMILY integer_ops USING btree ADD
756 -- cross-type comparisons int8 vs int2
757 OPERATOR 1 < (int8, int2) ,
758 OPERATOR 2 <= (int8, int2) ,
759 OPERATOR 3 = (int8, int2) ,
760 OPERATOR 4 >= (int8, int2) ,
761 OPERATOR 5 > (int8, int2) ,
762 FUNCTION 1 btint82cmp(int8, int2) ,
764 -- cross-type comparisons int8 vs int4
765 OPERATOR 1 < (int8, int4) ,
766 OPERATOR 2 <= (int8, int4) ,
767 OPERATOR 3 = (int8, int4) ,
768 OPERATOR 4 >= (int8, int4) ,
769 OPERATOR 5 > (int8, int4) ,
770 FUNCTION 1 btint84cmp(int8, int4) ,
772 -- cross-type comparisons int4 vs int2
773 OPERATOR 1 < (int4, int2) ,
774 OPERATOR 2 <= (int4, int2) ,
775 OPERATOR 3 = (int4, int2) ,
776 OPERATOR 4 >= (int4, int2) ,
777 OPERATOR 5 > (int4, int2) ,
778 FUNCTION 1 btint42cmp(int4, int2) ,
780 -- cross-type comparisons int4 vs int8
781 OPERATOR 1 < (int4, int8) ,
782 OPERATOR 2 <= (int4, int8) ,
783 OPERATOR 3 = (int4, int8) ,
784 OPERATOR 4 >= (int4, int8) ,
785 OPERATOR 5 > (int4, int8) ,
786 FUNCTION 1 btint48cmp(int4, int8) ,
788 -- cross-type comparisons int2 vs int8
789 OPERATOR 1 < (int2, int8) ,
790 OPERATOR 2 <= (int2, int8) ,
791 OPERATOR 3 = (int2, int8) ,
792 OPERATOR 4 >= (int2, int8) ,
793 OPERATOR 5 > (int2, int8) ,
794 FUNCTION 1 btint28cmp(int2, int8) ,
796 -- cross-type comparisons int2 vs int4
797 OPERATOR 1 < (int2, int4) ,
798 OPERATOR 2 <= (int2, int4) ,
799 OPERATOR 3 = (int2, int4) ,
800 OPERATOR 4 >= (int2, int4) ,
801 OPERATOR 5 > (int2, int4) ,
802 FUNCTION 1 btint24cmp(int2, int4) ;
806 Notice that this definition <quote>overloads</> the operator strategy and
807 support function numbers: each number occurs multiple times within the
808 family. This is allowed so long as each instance of a
809 particular number has distinct input data types. The instances that have
810 both input types equal to an operator class's input type are the
811 primary operators and support functions for that operator class,
812 and in most cases should be declared as part of the operator class rather
813 than as loose members of the family.
817 In a B-tree operator family, all the operators in the family must sort
818 compatibly, meaning that the transitive laws hold across all the data types
819 supported by the family: <quote>if A = B and B = C, then A =
820 C</>, and <quote>if A < B and B < C, then A < C</>. For each
821 operator in the family there must be a support function having the same
822 two input data types as the operator. It is recommended that a family be
823 complete, i.e., for each combination of data types, all operators are
824 included. Each operator class should include just the non-cross-type
825 operators and support function for its data type.
829 To build a multiple-data-type hash operator family, compatible hash
830 support functions must be created for each data type supported by the
831 family. Here compatibility means that the functions are guaranteed to
832 return the same hash code for any two values that are considered equal
833 by the family's equality operators, even when the values are of different
834 types. This is usually difficult to accomplish when the types have
835 different physical representations, but it can be done in some cases.
836 Notice that there is only one support function per data type, not one
837 per equality operator. It is recommended that a family be complete, i.e.,
838 provide an equality operator for each combination of data types.
839 Each operator class should include just the non-cross-type equality
840 operator and the support function for its data type.
844 GIN and GiST indexes do not have any explicit notion of cross-data-type
845 operations. The set of operators supported is just whatever the primary
846 support functions for a given operator class can handle.
851 Prior to <productname>PostgreSQL</productname> 8.3, there was no concept
852 of operator families, and so any cross-data-type operators intended to be
853 used with an index had to be bound directly into the index's operator
854 class. While this approach still works, it is deprecated because it
855 makes an index's dependencies too broad, and because the planner can
856 handle cross-data-type comparisons more effectively when both data types
857 have operators in the same operator family.
862 <sect2 id="xindex-opclass-dependencies">
863 <title>System Dependencies on Operator Classes</title>
866 <primary>ordering operator</primary>
870 <productname>PostgreSQL</productname> uses operator classes to infer the
871 properties of operators in more ways than just whether they can be used
872 with indexes. Therefore, you might want to create operator classes
873 even if you have no intention of indexing any columns of your data type.
877 In particular, there are SQL features such as <literal>ORDER BY</> and
878 <literal>DISTINCT</> that require comparison and sorting of values.
879 To implement these features on a user-defined data type,
880 <productname>PostgreSQL</productname> looks for the default B-tree operator
881 class for the data type. The <quote>equals</> member of this operator
882 class defines the system's notion of equality of values for
883 <literal>GROUP BY</> and <literal>DISTINCT</>, and the sort ordering
884 imposed by the operator class defines the default <literal>ORDER BY</>
889 Comparison of arrays of user-defined types also relies on the semantics
890 defined by the default B-tree operator class.
894 If there is no default B-tree operator class for a data type, the system
895 will look for a default hash operator class. But since that kind of
896 operator class only provides equality, in practice it is only enough
897 to support array equality.
901 When there is no default operator class for a data type, you will get
902 errors like <quote>could not identify an ordering operator</> if you
903 try to use these SQL features with the data type.
908 In <productname>PostgreSQL</productname> versions before 7.4,
909 sorting and grouping operations would implicitly use operators named
910 <literal>=</>, <literal><</>, and <literal>></>. The new
911 behavior of relying on default operator classes avoids having to make
912 any assumption about the behavior of operators with particular names.
917 Another important point is that an operator that
918 appears in a hash operator family is a candidate for hash joins,
919 hash aggregation, and related optimizations. The hash operator family
920 is essential here since it identifies the hash function(s) to use.
924 <sect2 id="xindex-opclass-features">
925 <title>Special Features of Operator Classes</title>
928 There are two special features of operator classes that we have
929 not discussed yet, mainly because they are not useful
930 with the most commonly used index methods.
934 Normally, declaring an operator as a member of an operator class
935 (or family) means that the index method can retrieve exactly the set of rows
936 that satisfy a <literal>WHERE</> condition using the operator. For example:
938 SELECT * FROM table WHERE integer_column < 4;
940 can be satisfied exactly by a B-tree index on the integer column.
941 But there are cases where an index is useful as an inexact guide to
942 the matching rows. For example, if a GiST index stores only bounding boxes
943 for geometric objects, then it cannot exactly satisfy a <literal>WHERE</>
944 condition that tests overlap between nonrectangular objects such as
945 polygons. Yet we could use the index to find objects whose bounding
946 box overlaps the bounding box of the target object, and then do the
947 exact overlap test only on the objects found by the index. If this
948 scenario applies, the index is said to be <quote>lossy</> for the
949 operator. Lossy index searches are implemented by having the index
950 method return a <firstterm>recheck</> flag when a row might or might
951 not really satisfy the query condition. The core system will then
952 test the original query condition on the retrieved row to see whether
953 it should be returned as a valid match. This approach works if
954 the index is guaranteed to return all the required rows, plus perhaps
955 some additional rows, which can be eliminated by performing the original
956 operator invocation. The index methods that support lossy searches
957 (currently, GiST and GIN) allow the support functions of individual
958 operator classes to set the recheck flag, and so this is essentially an
959 operator-class feature.
963 Consider again the situation where we are storing in the index only
964 the bounding box of a complex object such as a polygon. In this
965 case there's not much value in storing the whole polygon in the index
966 entry — we might as well store just a simpler object of type
967 <type>box</>. This situation is expressed by the <literal>STORAGE</>
968 option in <command>CREATE OPERATOR CLASS</>: we'd write something like:
971 CREATE OPERATOR CLASS polygon_ops
972 DEFAULT FOR TYPE polygon USING gist AS
977 At present, only the GiST and GIN index methods support a
978 <literal>STORAGE</> type that's different from the column data type.
979 The GiST <function>compress</> and <function>decompress</> support
980 routines must deal with data-type conversion when <literal>STORAGE</>
981 is used. In GIN, the <literal>STORAGE</> type identifies the type of
982 the <quote>key</> values, which normally is different from the type
983 of the indexed column — for example, an operator class for
984 integer-array columns might have keys that are just integers. The
985 GIN <function>extractValue</> and <function>extractQuery</> support
986 routines are responsible for extracting keys from indexed values.