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 the operators listed above return Boolean values. In
280
practice, all operators defined as index method search operators 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.
283
(Some index access methods also support <firstterm>ordering operators</>,
284
which typically don't return Boolean values; that feature is discussed
285
in <xref linkend="xindex-ordering-ops">.)
289
<sect2 id="xindex-support">
290
<title>Index Method Support Routines</title>
293
Strategies aren't usually enough information for the system to figure
294
out how to use an index. In practice, the index methods require
295
additional support routines in order to work. For example, the B-tree
296
index method must be able to compare two keys and determine whether one
297
is greater than, equal to, or less than the other. Similarly, the
298
hash index method must be able to compute hash codes for key values.
299
These operations do not correspond to operators used in qualifications in
300
SQL commands; they are administrative routines used by
301
the index methods, internally.
305
Just as with strategies, the operator class identifies which specific
306
functions should play each of these roles for a given data type and
307
semantic interpretation. The index method defines the set
308
of functions it needs, and the operator class identifies the correct
309
functions to use by assigning them to the <quote>support function numbers</>
310
specified by the index method.
314
B-trees require a single support function, shown in <xref
315
linkend="xindex-btree-support-table">.
318
<table tocentry="1" id="xindex-btree-support-table">
319
<title>B-tree Support Functions</title>
323
<entry>Function</entry>
324
<entry>Support Number</entry>
330
Compare two keys and return an integer less than zero, zero, or
331
greater than zero, indicating whether the first key is less than,
332
equal to, or greater than the second
341
Hash indexes likewise require one support function, shown in <xref
342
linkend="xindex-hash-support-table">.
345
<table tocentry="1" id="xindex-hash-support-table">
346
<title>Hash Support Functions</title>
350
<entry>Function</entry>
351
<entry>Support Number</entry>
356
<entry>Compute the hash value for a key</entry>
364
GiST indexes require seven support functions, with an optional eighth, as
365
shown in <xref linkend="xindex-gist-support-table">.
368
<table tocentry="1" id="xindex-gist-support-table">
369
<title>GiST Support Functions</title>
373
<entry>Function</entry>
374
<entry>Description</entry>
375
<entry>Support Number</entry>
380
<entry><function>consistent</></entry>
381
<entry>determine whether key satisfies the
382
query qualifier</entry>
386
<entry><function>union</></entry>
387
<entry>compute union of a set of keys</entry>
391
<entry><function>compress</></entry>
392
<entry>compute a compressed representation of a key or value
393
to be indexed</entry>
397
<entry><function>decompress</></entry>
398
<entry>compute a decompressed representation of a
399
compressed key</entry>
403
<entry><function>penalty</></entry>
404
<entry>compute penalty for inserting new key into subtree
405
with given subtree's key</entry>
409
<entry><function>picksplit</></entry>
410
<entry>determine which entries of a page are to be moved
411
to the new page and compute the union keys for resulting pages</entry>
415
<entry><function>equal</></entry>
416
<entry>compare two keys and return true if they are equal</entry>
420
<entry><function>distance</></entry>
422
(optional method) determine distance from key to query value
431
GIN indexes require four support functions, with an optional fifth, as
432
shown in <xref linkend="xindex-gin-support-table">.
435
<table tocentry="1" id="xindex-gin-support-table">
436
<title>GIN Support Functions</title>
440
<entry>Function</entry>
441
<entry>Description</entry>
442
<entry>Support Number</entry>
447
<entry><function>compare</></entry>
449
compare two keys and return an integer less than zero, zero,
450
or greater than zero, indicating whether the first key is less than,
451
equal to, or greater than the second
456
<entry><function>extractValue</></entry>
457
<entry>extract keys from a value to be indexed</entry>
461
<entry><function>extractQuery</></entry>
462
<entry>extract keys from a query condition</entry>
466
<entry><function>consistent</></entry>
467
<entry>determine whether value matches query condition</entry>
471
<entry><function>comparePartial</></entry>
473
(optional method) compare partial key from
474
query and key from index, and return an integer less than zero, zero,
475
or greater than zero, indicating whether GIN should ignore this index
476
entry, treat the entry as a match, or stop the index scan
485
Unlike search operators, support functions return whichever data
486
type the particular index method expects; for example in the case
487
of the comparison function for B-trees, a signed integer. The number
488
and types of the arguments to each support function are likewise
489
dependent on the index method. For B-tree and hash the support functions
490
take the same input data types as do the operators included in the operator
491
class, but this is not the case for most GIN and GiST support functions.
495
<sect2 id="xindex-example">
496
<title>An Example</title>
499
Now that we have seen the ideas, here is the promised example of
500
creating a new operator class.
501
(You can find a working copy of this example in
502
<filename>src/tutorial/complex.c</filename> and
503
<filename>src/tutorial/complex.sql</filename> in the source
505
The operator class encapsulates
506
operators that sort complex numbers in absolute value order, so we
507
choose the name <literal>complex_abs_ops</literal>. First, we need
508
a set of operators. The procedure for defining operators was
509
discussed in <xref linkend="xoper">. For an operator class on
510
B-trees, the operators we require are:
512
<itemizedlist spacing="compact">
513
<listitem><simpara>absolute-value less-than (strategy 1)</></>
514
<listitem><simpara>absolute-value less-than-or-equal (strategy 2)</></>
515
<listitem><simpara>absolute-value equal (strategy 3)</></>
516
<listitem><simpara>absolute-value greater-than-or-equal (strategy 4)</></>
517
<listitem><simpara>absolute-value greater-than (strategy 5)</></>
522
The least error-prone way to define a related set of comparison operators
523
is to write the B-tree comparison support function first, and then write the
524
other functions as one-line wrappers around the support function. This
525
reduces the odds of getting inconsistent results for corner cases.
526
Following this approach, we first write:
528
<programlisting><![CDATA[
529
#define Mag(c) ((c)->x*(c)->x + (c)->y*(c)->y)
532
complex_abs_cmp_internal(Complex *a, Complex *b)
534
double amag = Mag(a),
546
Now the less-than function looks like:
548
<programlisting><![CDATA[
549
PG_FUNCTION_INFO_V1(complex_abs_lt);
552
complex_abs_lt(PG_FUNCTION_ARGS)
554
Complex *a = (Complex *) PG_GETARG_POINTER(0);
555
Complex *b = (Complex *) PG_GETARG_POINTER(1);
557
PG_RETURN_BOOL(complex_abs_cmp_internal(a, b) < 0);
562
The other four functions differ only in how they compare the internal
563
function's result to zero.
567
Next we declare the functions and the operators based on the functions
571
CREATE FUNCTION complex_abs_lt(complex, complex) RETURNS bool
572
AS '<replaceable>filename</replaceable>', 'complex_abs_lt'
573
LANGUAGE C IMMUTABLE STRICT;
575
CREATE OPERATOR < (
576
leftarg = complex, rightarg = complex, procedure = complex_abs_lt,
577
commutator = > , negator = >= ,
578
restrict = scalarltsel, join = scalarltjoinsel
581
It is important to specify the correct commutator and negator operators,
582
as well as suitable restriction and join selectivity
583
functions, otherwise the optimizer will be unable to make effective
584
use of the index. Note that the less-than, equal, and
585
greater-than cases should use different selectivity functions.
589
Other things worth noting are happening here:
594
There can only be one operator named, say, <literal>=</literal>
595
and taking type <type>complex</type> for both operands. In this
596
case we don't have any other operator <literal>=</literal> for
597
<type>complex</type>, but if we were building a practical data
598
type we'd probably want <literal>=</literal> to be the ordinary
599
equality operation for complex numbers (and not the equality of
600
the absolute values). In that case, we'd need to use some other
601
operator name for <function>complex_abs_eq</>.
607
Although <productname>PostgreSQL</productname> can cope with
608
functions having the same SQL name as long as they have different
609
argument data types, C can only cope with one global function
610
having a given name. So we shouldn't name the C function
611
something simple like <filename>abs_eq</filename>. Usually it's
612
a good practice to include the data type name in the C function
613
name, so as not to conflict with functions for other data types.
619
We could have made the SQL name
620
of the function <filename>abs_eq</filename>, relying on
621
<productname>PostgreSQL</productname> to distinguish it by
622
argument data types from any other SQL function of the same name.
623
To keep the example simple, we make the function have the same
624
names at the C level and SQL level.
631
The next step is the registration of the support routine required
632
by B-trees. The example C code that implements this is in the same
633
file that contains the operator functions. This is how we declare
637
CREATE FUNCTION complex_abs_cmp(complex, complex)
639
AS '<replaceable>filename</replaceable>'
640
LANGUAGE C IMMUTABLE STRICT;
645
Now that we have the required operators and support routine,
646
we can finally create the operator class:
648
<programlisting><![CDATA[
649
CREATE OPERATOR CLASS complex_abs_ops
650
DEFAULT FOR TYPE complex USING btree AS
656
FUNCTION 1 complex_abs_cmp(complex, complex);
662
And we're done! It should now be possible to create
663
and use B-tree indexes on <type>complex</type> columns.
667
We could have written the operator entries more verbosely, as in:
669
OPERATOR 1 < (complex, complex) ,
671
but there is no need to do so when the operators take the same data type
672
we are defining the operator class for.
676
The above example assumes that you want to make this new operator class the
677
default B-tree operator class for the <type>complex</type> data type.
678
If you don't, just leave out the word <literal>DEFAULT</>.
682
<sect2 id="xindex-opfamily">
683
<title>Operator Classes and Operator Families</title>
686
So far we have implicitly assumed that an operator class deals with
687
only one data type. While there certainly can be only one data type in
688
a particular index column, it is often useful to index operations that
689
compare an indexed column to a value of a different data type. Also,
690
if there is use for a cross-data-type operator in connection with an
691
operator class, it is often the case that the other data type has a
692
related operator class of its own. It is helpful to make the connections
693
between related classes explicit, because this can aid the planner in
694
optimizing SQL queries (particularly for B-tree operator classes, since
695
the planner contains a great deal of knowledge about how to work with them).
699
To handle these needs, <productname>PostgreSQL</productname>
700
uses the concept of an <firstterm>operator
701
family</><indexterm><primary>operator family</></indexterm>.
702
An operator family contains one or more operator classes, and can also
703
contain indexable operators and corresponding support functions that
704
belong to the family as a whole but not to any single class within the
705
family. We say that such operators and functions are <quote>loose</>
706
within the family, as opposed to being bound into a specific class.
707
Typically each operator class contains single-data-type operators
708
while cross-data-type operators are loose in the family.
712
All the operators and functions in an operator family must have compatible
713
semantics, where the compatibility requirements are set by the index
714
method. You might therefore wonder why bother to single out particular
715
subsets of the family as operator classes; and indeed for many purposes
716
the class divisions are irrelevant and the family is the only interesting
717
grouping. The reason for defining operator classes is that they specify
718
how much of the family is needed to support any particular index.
719
If there is an index using an operator class, then that operator class
720
cannot be dropped without dropping the index — but other parts of
721
the operator family, namely other operator classes and loose operators,
722
could be dropped. Thus, an operator class should be specified to contain
723
the minimum set of operators and functions that are reasonably needed
724
to work with an index on a specific data type, and then related but
725
non-essential operators can be added as loose members of the operator
730
As an example, <productname>PostgreSQL</productname> has a built-in
731
B-tree operator family <literal>integer_ops</>, which includes operator
732
classes <literal>int8_ops</>, <literal>int4_ops</>, and
733
<literal>int2_ops</> for indexes on <type>bigint</> (<type>int8</>),
734
<type>integer</> (<type>int4</>), and <type>smallint</> (<type>int2</>)
735
columns respectively. The family also contains cross-data-type comparison
736
operators allowing any two of these types to be compared, so that an index
737
on one of these types can be searched using a comparison value of another
738
type. The family could be duplicated by these definitions:
740
<programlisting><![CDATA[
741
CREATE OPERATOR FAMILY integer_ops USING btree;
743
CREATE OPERATOR CLASS int8_ops
744
DEFAULT FOR TYPE int8 USING btree FAMILY integer_ops AS
745
-- standard int8 comparisons
751
FUNCTION 1 btint8cmp(int8, int8) ;
753
CREATE OPERATOR CLASS int4_ops
754
DEFAULT FOR TYPE int4 USING btree FAMILY integer_ops AS
755
-- standard int4 comparisons
761
FUNCTION 1 btint4cmp(int4, int4) ;
763
CREATE OPERATOR CLASS int2_ops
764
DEFAULT FOR TYPE int2 USING btree FAMILY integer_ops AS
765
-- standard int2 comparisons
771
FUNCTION 1 btint2cmp(int2, int2) ;
773
ALTER OPERATOR FAMILY integer_ops USING btree ADD
774
-- cross-type comparisons int8 vs int2
775
OPERATOR 1 < (int8, int2) ,
776
OPERATOR 2 <= (int8, int2) ,
777
OPERATOR 3 = (int8, int2) ,
778
OPERATOR 4 >= (int8, int2) ,
779
OPERATOR 5 > (int8, int2) ,
780
FUNCTION 1 btint82cmp(int8, int2) ,
782
-- cross-type comparisons int8 vs int4
783
OPERATOR 1 < (int8, int4) ,
784
OPERATOR 2 <= (int8, int4) ,
785
OPERATOR 3 = (int8, int4) ,
786
OPERATOR 4 >= (int8, int4) ,
787
OPERATOR 5 > (int8, int4) ,
788
FUNCTION 1 btint84cmp(int8, int4) ,
790
-- cross-type comparisons int4 vs int2
791
OPERATOR 1 < (int4, int2) ,
792
OPERATOR 2 <= (int4, int2) ,
793
OPERATOR 3 = (int4, int2) ,
794
OPERATOR 4 >= (int4, int2) ,
795
OPERATOR 5 > (int4, int2) ,
796
FUNCTION 1 btint42cmp(int4, int2) ,
798
-- cross-type comparisons int4 vs int8
799
OPERATOR 1 < (int4, int8) ,
800
OPERATOR 2 <= (int4, int8) ,
801
OPERATOR 3 = (int4, int8) ,
802
OPERATOR 4 >= (int4, int8) ,
803
OPERATOR 5 > (int4, int8) ,
804
FUNCTION 1 btint48cmp(int4, int8) ,
806
-- cross-type comparisons int2 vs int8
807
OPERATOR 1 < (int2, int8) ,
808
OPERATOR 2 <= (int2, int8) ,
809
OPERATOR 3 = (int2, int8) ,
810
OPERATOR 4 >= (int2, int8) ,
811
OPERATOR 5 > (int2, int8) ,
812
FUNCTION 1 btint28cmp(int2, int8) ,
814
-- cross-type comparisons int2 vs int4
815
OPERATOR 1 < (int2, int4) ,
816
OPERATOR 2 <= (int2, int4) ,
817
OPERATOR 3 = (int2, int4) ,
818
OPERATOR 4 >= (int2, int4) ,
819
OPERATOR 5 > (int2, int4) ,
820
FUNCTION 1 btint24cmp(int2, int4) ;
824
Notice that this definition <quote>overloads</> the operator strategy and
825
support function numbers: each number occurs multiple times within the
826
family. This is allowed so long as each instance of a
827
particular number has distinct input data types. The instances that have
828
both input types equal to an operator class's input type are the
829
primary operators and support functions for that operator class,
830
and in most cases should be declared as part of the operator class rather
831
than as loose members of the family.
835
In a B-tree operator family, all the operators in the family must sort
836
compatibly, meaning that the transitive laws hold across all the data types
837
supported by the family: <quote>if A = B and B = C, then A =
838
C</>, and <quote>if A < B and B < C, then A < C</>. For each
839
operator in the family there must be a support function having the same
840
two input data types as the operator. It is recommended that a family be
841
complete, i.e., for each combination of data types, all operators are
842
included. Each operator class should include just the non-cross-type
843
operators and support function for its data type.
847
To build a multiple-data-type hash operator family, compatible hash
848
support functions must be created for each data type supported by the
849
family. Here compatibility means that the functions are guaranteed to
850
return the same hash code for any two values that are considered equal
851
by the family's equality operators, even when the values are of different
852
types. This is usually difficult to accomplish when the types have
853
different physical representations, but it can be done in some cases.
854
Notice that there is only one support function per data type, not one
855
per equality operator. It is recommended that a family be complete, i.e.,
856
provide an equality operator for each combination of data types.
857
Each operator class should include just the non-cross-type equality
858
operator and the support function for its data type.
862
GIN and GiST indexes do not have any explicit notion of cross-data-type
863
operations. The set of operators supported is just whatever the primary
864
support functions for a given operator class can handle.
869
Prior to <productname>PostgreSQL</productname> 8.3, there was no concept
870
of operator families, and so any cross-data-type operators intended to be
871
used with an index had to be bound directly into the index's operator
872
class. While this approach still works, it is deprecated because it
873
makes an index's dependencies too broad, and because the planner can
874
handle cross-data-type comparisons more effectively when both data types
875
have operators in the same operator family.
880
<sect2 id="xindex-opclass-dependencies">
881
<title>System Dependencies on Operator Classes</title>
884
<primary>ordering operator</primary>
888
<productname>PostgreSQL</productname> uses operator classes to infer the
889
properties of operators in more ways than just whether they can be used
890
with indexes. Therefore, you might want to create operator classes
891
even if you have no intention of indexing any columns of your data type.
895
In particular, there are SQL features such as <literal>ORDER BY</> and
896
<literal>DISTINCT</> that require comparison and sorting of values.
897
To implement these features on a user-defined data type,
898
<productname>PostgreSQL</productname> looks for the default B-tree operator
899
class for the data type. The <quote>equals</> member of this operator
900
class defines the system's notion of equality of values for
901
<literal>GROUP BY</> and <literal>DISTINCT</>, and the sort ordering
902
imposed by the operator class defines the default <literal>ORDER BY</>
907
Comparison of arrays of user-defined types also relies on the semantics
908
defined by the default B-tree operator class.
912
If there is no default B-tree operator class for a data type, the system
913
will look for a default hash operator class. But since that kind of
914
operator class only provides equality, in practice it is only enough
915
to support array equality.
919
When there is no default operator class for a data type, you will get
920
errors like <quote>could not identify an ordering operator</> if you
921
try to use these SQL features with the data type.
926
In <productname>PostgreSQL</productname> versions before 7.4,
927
sorting and grouping operations would implicitly use operators named
928
<literal>=</>, <literal><</>, and <literal>></>. The new
929
behavior of relying on default operator classes avoids having to make
930
any assumption about the behavior of operators with particular names.
935
Another important point is that an operator that
936
appears in a hash operator family is a candidate for hash joins,
937
hash aggregation, and related optimizations. The hash operator family
938
is essential here since it identifies the hash function(s) to use.
942
<sect2 id="xindex-ordering-ops">
943
<title>Ordering Operators</title>
946
Some index access methods (currently, only GiST) support the concept of
947
<firstterm>ordering operators</>. What we have been discussing so far
948
are <firstterm>search operators</>. A search operator is one for which
949
the index can be searched to find all rows satisfying
951
<replaceable>indexed_column</>
952
<replaceable>operator</>
953
<replaceable>constant</>.
954
Note that nothing is promised about the order in which the matching rows
955
will be returned. In contrast, an ordering operator does not restrict the
956
set of rows that can be returned, but instead determines their order.
957
An ordering operator is one for which the index can be scanned to return
958
rows in the order represented by
960
<replaceable>indexed_column</>
961
<replaceable>operator</>
962
<replaceable>constant</>.
963
The reason for defining ordering operators that way is that it supports
964
nearest-neighbor searches, if the operator is one that measures distance.
965
For example, a query like
966
<programlisting><![CDATA[
967
SELECT * FROM places ORDER BY location <-> point '(101,456)' LIMIT 10;
970
finds the ten places closest to a given target point. A GiST index
971
on the location column can do this efficiently because
972
<literal><-></> is an ordering operator.
976
While search operators have to return Boolean results, ordering operators
977
usually return some other type, such as float or numeric for distances.
978
This type is normally not the same as the data type being indexed.
979
To avoid hard-wiring assumptions about the behavior of different data
980
types, the definition of an ordering operator is required to name
981
a B-tree operator family that specifies the sort ordering of the result
982
data type. As was stated in the previous section, B-tree operator families
983
define <productname>PostgreSQL</productname>'s notion of ordering, so
984
this is a natural representation. Since the point <literal><-></>
985
operator returns <type>float8</>, it could be specified in an operator
986
class creation command like this:
987
<programlisting><![CDATA[
988
OPERATOR 15 <-> (point, point) FOR ORDER BY float_ops
991
where <literal>float_ops</> is the built-in operator family that includes
992
operations on <type>float8</>. This declaration states that the index
993
is able to return rows in order of increasing values of the
994
<literal><-></> operator.
998
<sect2 id="xindex-opclass-features">
999
<title>Special Features of Operator Classes</title>
1002
There are two special features of operator classes that we have
1003
not discussed yet, mainly because they are not useful
1004
with the most commonly used index methods.
1008
Normally, declaring an operator as a member of an operator class
1009
(or family) means that the index method can retrieve exactly the set of rows
1010
that satisfy a <literal>WHERE</> condition using the operator. For example:
1012
SELECT * FROM table WHERE integer_column < 4;
1014
can be satisfied exactly by a B-tree index on the integer column.
1015
But there are cases where an index is useful as an inexact guide to
1016
the matching rows. For example, if a GiST index stores only bounding boxes
1017
for geometric objects, then it cannot exactly satisfy a <literal>WHERE</>
1018
condition that tests overlap between nonrectangular objects such as
1019
polygons. Yet we could use the index to find objects whose bounding
1020
box overlaps the bounding box of the target object, and then do the
1021
exact overlap test only on the objects found by the index. If this
1022
scenario applies, the index is said to be <quote>lossy</> for the
1023
operator. Lossy index searches are implemented by having the index
1024
method return a <firstterm>recheck</> flag when a row might or might
1025
not really satisfy the query condition. The core system will then
1026
test the original query condition on the retrieved row to see whether
1027
it should be returned as a valid match. This approach works if
1028
the index is guaranteed to return all the required rows, plus perhaps
1029
some additional rows, which can be eliminated by performing the original
1030
operator invocation. The index methods that support lossy searches
1031
(currently, GiST and GIN) allow the support functions of individual
1032
operator classes to set the recheck flag, and so this is essentially an
1033
operator-class feature.
1037
Consider again the situation where we are storing in the index only
1038
the bounding box of a complex object such as a polygon. In this
1039
case there's not much value in storing the whole polygon in the index
1040
entry — we might as well store just a simpler object of type
1041
<type>box</>. This situation is expressed by the <literal>STORAGE</>
1042
option in <command>CREATE OPERATOR CLASS</>: we'd write something like:
1045
CREATE OPERATOR CLASS polygon_ops
1046
DEFAULT FOR TYPE polygon USING gist AS
1051
At present, only the GiST and GIN index methods support a
1052
<literal>STORAGE</> type that's different from the column data type.
1053
The GiST <function>compress</> and <function>decompress</> support
1054
routines must deal with data-type conversion when <literal>STORAGE</>
1055
is used. In GIN, the <literal>STORAGE</> type identifies the type of
1056
the <quote>key</> values, which normally is different from the type
1057
of the indexed column — for example, an operator class for
1058
integer-array columns might have keys that are just integers. The
1059
GIN <function>extractValue</> and <function>extractQuery</> support
1060
routines are responsible for extracting keys from indexed values.