Debian Codegraph @

doc/src/sgml/xindex.sgml

raw
1 <!-- doc/src/sgml/xindex.sgml -->
2
3 <sect1 id="xindex">
4 <title>Interfacing Extensions to Indexes</title>
5
6 <indexterm zone="xindex">
7 <primary>index</primary>
8 <secondary>for user-defined data type</secondary>
9 </indexterm>
10
11 <para>
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</firstterm> 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.
19 </para>
20
21 <para>
22 Operator classes can be grouped into <firstterm>operator families</firstterm>
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.
26 </para>
27
28 <sect2 id="xindex-opclass">
29 <title>Index Methods and Operator Classes</title>
30
31 <para>
32 Operator classes are associated with an index access method, such
33 as <link linkend="btree">B-Tree</link>
34 or <link linkend="gin">GIN</link>. Custom index access method may be
35 defined with <xref linkend="sql-create-access-method"/>. See
36 <xref linkend="indexam"/> for details.
37 </para>
38
39 <para>
40 The routines for an index method do not directly know anything
41 about the data types that the index method will operate on.
42 Instead, an <firstterm>operator
43 class</firstterm><indexterm><primary>operator class</primary></indexterm>
44 identifies the set of operations that the index method needs to use
45 to work with a particular data type. Operator classes are so
46 called because one thing they specify is the set of
47 <literal>WHERE</literal>-clause operators that can be used with an index
48 (i.e., can be converted into an index-scan qualification). An
49 operator class can also specify some <firstterm>support
50 function</firstterm> that are needed by the internal operations of the
51 index method, but do not directly correspond to any
52 <literal>WHERE</literal>-clause operator that can be used with the index.
53 </para>
54
55 <para>
56 It is possible to define multiple operator classes for the same
57 data type and index method. By doing this, multiple
58 sets of indexing semantics can be defined for a single data type.
59 For example, a B-tree index requires a sort ordering to be defined
60 for each data type it works on.
61 It might be useful for a complex-number data type
62 to have one B-tree operator class that sorts the data by complex
63 absolute value, another that sorts by real part, and so on.
64 Typically, one of the operator classes will be deemed most commonly
65 useful and will be marked as the default operator class for that
66 data type and index method.
67 </para>
68
69 <para>
70 The same operator class name
71 can be used for several different index methods (for example, both B-tree
72 and hash index methods have operator classes named
73 <literal>int4_ops</literal>), but each such class is an independent
74 entity and must be defined separately.
75 </para>
76 </sect2>
77
78 <sect2 id="xindex-strategies">
79 <title>Index Method Strategies</title>
80
81 <para>
82 The operators associated with an operator class are identified by
83 <quote>strategy numbers</quote>, which serve to identify the semantics of
84 each operator within the context of its operator class.
85 For example, B-trees impose a strict ordering on keys, lesser to greater,
86 and so operators like <quote>less than</quote> and <quote>greater than or equal
87 to</quote> are interesting with respect to a B-tree.
88 Because
89 <productname>PostgreSQL</productname> allows the user to define operators,
90 <productname>PostgreSQL</productname> cannot look at the name of an operator
91 (e.g., <literal>&lt;</literal> or <literal>&gt;=</literal>) and tell what kind of
92 comparison it is. Instead, the index method defines a set of
93 <quote>strategies</quote>, which can be thought of as generalized operators.
94 Each operator class specifies which actual operator corresponds to each
95 strategy for a particular data type and interpretation of the index
96 semantics.
97 </para>
98
99 <para>
100 The B-tree index method defines five strategies, shown in <xref
101 linkend="xindex-btree-strat-table"/>.
102 </para>
103
104 <table tocentry="1" id="xindex-btree-strat-table">
105 <title>B-Tree Strategies</title>
106 <tgroup cols="2">
107 <thead>
108 <row>
109 <entry>Operation</entry>
110 <entry>Strategy Number</entry>
111 </row>
112 </thead>
113 <tbody>
114 <row>
115 <entry>less than</entry>
116 <entry>1</entry>
117 </row>
118 <row>
119 <entry>less than or equal</entry>
120 <entry>2</entry>
121 </row>
122 <row>
123 <entry>equal</entry>
124 <entry>3</entry>
125 </row>
126 <row>
127 <entry>greater than or equal</entry>
128 <entry>4</entry>
129 </row>
130 <row>
131 <entry>greater than</entry>
132 <entry>5</entry>
133 </row>
134 </tbody>
135 </tgroup>
136 </table>
137
138 <para>
139 Hash indexes support only equality comparisons, and so they use only one
140 strategy, shown in <xref linkend="xindex-hash-strat-table"/>.
141 </para>
142
143 <table tocentry="1" id="xindex-hash-strat-table">
144 <title>Hash Strategies</title>
145 <tgroup cols="2">
146 <thead>
147 <row>
148 <entry>Operation</entry>
149 <entry>Strategy Number</entry>
150 </row>
151 </thead>
152 <tbody>
153 <row>
154 <entry>equal</entry>
155 <entry>1</entry>
156 </row>
157 </tbody>
158 </tgroup>
159 </table>
160
161 <para>
162 GiST indexes are more flexible: they do not have a fixed set of
163 strategies at all. Instead, the <quote>consistency</quote> support routine
164 of each particular GiST operator class interprets the strategy numbers
165 however it likes. As an example, several of the built-in GiST index
166 operator classes index two-dimensional geometric objects, providing
167 the <quote>R-tree</quote> strategies shown in
168 <xref linkend="xindex-rtree-strat-table"/>. Four of these are true
169 two-dimensional tests (overlaps, same, contains, contained by);
170 four of them consider only the X direction; and the other four
171 provide the same tests in the Y direction.
172 </para>
173
174 <table tocentry="1" id="xindex-rtree-strat-table">
175 <title>GiST Two-Dimensional <quote>R-tree</quote> Strategies</title>
176 <tgroup cols="2">
177 <thead>
178 <row>
179 <entry>Operation</entry>
180 <entry>Strategy Number</entry>
181 </row>
182 </thead>
183 <tbody>
184 <row>
185 <entry>strictly left of</entry>
186 <entry>1</entry>
187 </row>
188 <row>
189 <entry>does not extend to right of</entry>
190 <entry>2</entry>
191 </row>
192 <row>
193 <entry>overlaps</entry>
194 <entry>3</entry>
195 </row>
196 <row>
197 <entry>does not extend to left of</entry>
198 <entry>4</entry>
199 </row>
200 <row>
201 <entry>strictly right of</entry>
202 <entry>5</entry>
203 </row>
204 <row>
205 <entry>same</entry>
206 <entry>6</entry>
207 </row>
208 <row>
209 <entry>contains</entry>
210 <entry>7</entry>
211 </row>
212 <row>
213 <entry>contained by</entry>
214 <entry>8</entry>
215 </row>
216 <row>
217 <entry>does not extend above</entry>
218 <entry>9</entry>
219 </row>
220 <row>
221 <entry>strictly below</entry>
222 <entry>10</entry>
223 </row>
224 <row>
225 <entry>strictly above</entry>
226 <entry>11</entry>
227 </row>
228 <row>
229 <entry>does not extend below</entry>
230 <entry>12</entry>
231 </row>
232 </tbody>
233 </tgroup>
234 </table>
235
236 <para>
237 SP-GiST indexes are similar to GiST indexes in flexibility: they don't have
238 a fixed set of strategies. Instead the support routines of each operator
239 class interpret the strategy numbers according to the operator class's
240 definition. As an example, the strategy numbers used by the built-in
241 operator classes for points are shown in <xref
242 linkend="xindex-spgist-point-strat-table"/>.
243 </para>
244
245 <table tocentry="1" id="xindex-spgist-point-strat-table">
246 <title>SP-GiST Point Strategies</title>
247 <tgroup cols="2">
248 <thead>
249 <row>
250 <entry>Operation</entry>
251 <entry>Strategy Number</entry>
252 </row>
253 </thead>
254 <tbody>
255 <row>
256 <entry>strictly left of</entry>
257 <entry>1</entry>
258 </row>
259 <row>
260 <entry>strictly right of</entry>
261 <entry>5</entry>
262 </row>
263 <row>
264 <entry>same</entry>
265 <entry>6</entry>
266 </row>
267 <row>
268 <entry>contained by</entry>
269 <entry>8</entry>
270 </row>
271 <row>
272 <entry>strictly below</entry>
273 <entry>10</entry>
274 </row>
275 <row>
276 <entry>strictly above</entry>
277 <entry>11</entry>
278 </row>
279 </tbody>
280 </tgroup>
281 </table>
282
283 <para>
284 GIN indexes are similar to GiST and SP-GiST indexes, in that they don't
285 have a fixed set of strategies either. Instead the support routines of
286 each operator class interpret the strategy numbers according to the
287 operator class's definition. As an example, the strategy numbers used by
288 the built-in operator class for arrays are shown in
289 <xref linkend="xindex-gin-array-strat-table"/>.
290 </para>
291
292 <table tocentry="1" id="xindex-gin-array-strat-table">
293 <title>GIN Array Strategies</title>
294 <tgroup cols="2">
295 <thead>
296 <row>
297 <entry>Operation</entry>
298 <entry>Strategy Number</entry>
299 </row>
300 </thead>
301 <tbody>
302 <row>
303 <entry>overlap</entry>
304 <entry>1</entry>
305 </row>
306 <row>
307 <entry>contains</entry>
308 <entry>2</entry>
309 </row>
310 <row>
311 <entry>is contained by</entry>
312 <entry>3</entry>
313 </row>
314 <row>
315 <entry>equal</entry>
316 <entry>4</entry>
317 </row>
318 </tbody>
319 </tgroup>
320 </table>
321
322 <para>
323 BRIN indexes are similar to GiST, SP-GiST and GIN indexes in that they
324 don't have a fixed set of strategies either. Instead the support routines
325 of each operator class interpret the strategy numbers according to the
326 operator class's definition. As an example, the strategy numbers used by
327 the built-in <literal>Minmax</literal> operator classes are shown in
328 <xref linkend="xindex-brin-minmax-strat-table"/>.
329 </para>
330
331 <table tocentry="1" id="xindex-brin-minmax-strat-table">
332 <title>BRIN Minmax Strategies</title>
333 <tgroup cols="2">
334 <thead>
335 <row>
336 <entry>Operation</entry>
337 <entry>Strategy Number</entry>
338 </row>
339 </thead>
340 <tbody>
341 <row>
342 <entry>less than</entry>
343 <entry>1</entry>
344 </row>
345 <row>
346 <entry>less than or equal</entry>
347 <entry>2</entry>
348 </row>
349 <row>
350 <entry>equal</entry>
351 <entry>3</entry>
352 </row>
353 <row>
354 <entry>greater than or equal</entry>
355 <entry>4</entry>
356 </row>
357 <row>
358 <entry>greater than</entry>
359 <entry>5</entry>
360 </row>
361 </tbody>
362 </tgroup>
363 </table>
364
365 <para>
366 Notice that all the operators listed above return Boolean values. In
367 practice, all operators defined as index method search operators must
368 return type <type>boolean</type>, since they must appear at the top
369 level of a <literal>WHERE</literal> clause to be used with an index.
370 (Some index access methods also support <firstterm>ordering operators</firstterm>,
371 which typically don't return Boolean values; that feature is discussed
372 in <xref linkend="xindex-ordering-ops"/>.)
373 </para>
374 </sect2>
375
376 <sect2 id="xindex-support">
377 <title>Index Method Support Routines</title>
378
379 <para>
380 Strategies aren't usually enough information for the system to figure
381 out how to use an index. In practice, the index methods require
382 additional support routines in order to work. For example, the B-tree
383 index method must be able to compare two keys and determine whether one
384 is greater than, equal to, or less than the other. Similarly, the
385 hash index method must be able to compute hash codes for key values.
386 These operations do not correspond to operators used in qualifications in
387 SQL commands; they are administrative routines used by
388 the index methods, internally.
389 </para>
390
391 <para>
392 Just as with strategies, the operator class identifies which specific
393 functions should play each of these roles for a given data type and
394 semantic interpretation. The index method defines the set
395 of functions it needs, and the operator class identifies the correct
396 functions to use by assigning them to the <quote>support function numbers</quote>
397 specified by the index method.
398 </para>
399
400 <para>
401 Additionally, some opclasses allow users to specify parameters which
402 control their behavior. Each builtin index access method has an optional
403 <function>options</function> support function, which defines a set of
404 opclass-specific parameters.
405 </para>
406
407 <para>
408 B-trees require a comparison support function,
409 and allow four additional support functions to be
410 supplied at the operator class author's option, as shown in <xref
411 linkend="xindex-btree-support-table"/>.
412 The requirements for these support functions are explained further in
413 <xref linkend="btree-support-funcs"/>.
414 </para>
415
416 <table tocentry="1" id="xindex-btree-support-table">
417 <title>B-Tree Support Functions</title>
418 <tgroup cols="2">
419 <colspec colname="col1" colwidth="3*"/>
420 <colspec colname="col2" colwidth="1*"/>
421 <thead>
422 <row>
423 <entry>Function</entry>
424 <entry>Support Number</entry>
425 </row>
426 </thead>
427 <tbody>
428 <row>
429 <entry>
430 Compare two keys and return an integer less than zero, zero, or
431 greater than zero, indicating whether the first key is less than,
432 equal to, or greater than the second
433 </entry>
434 <entry>1</entry>
435 </row>
436 <row>
437 <entry>
438 Return the addresses of C-callable sort support function(s)
439 (optional)
440 </entry>
441 <entry>2</entry>
442 </row>
443 <row>
444 <entry>
445 Compare a test value to a base value plus/minus an offset, and return
446 true or false according to the comparison result (optional)
447 </entry>
448 <entry>3</entry>
449 </row>
450 <row>
451 <entry>
452 Determine if it is safe for indexes that use the operator
453 class to apply the btree deduplication optimization (optional)
454 </entry>
455 <entry>4</entry>
456 </row>
457 <row>
458 <entry>
459 Define options that are specific to this operator class
460 (optional)
461 </entry>
462 <entry>5</entry>
463 </row>
464 <row>
465 <entry>
466 Return the addresses of C-callable skip support function(s)
467 (optional)
468 </entry>
469 <entry>6</entry>
470 </row>
471 </tbody>
472 </tgroup>
473 </table>
474
475 <para>
476 Hash indexes require one support function, and allow two additional ones to
477 be supplied at the operator class author's option, as shown in <xref
478 linkend="xindex-hash-support-table"/>.
479 </para>
480
481 <table tocentry="1" id="xindex-hash-support-table">
482 <title>Hash Support Functions</title>
483 <tgroup cols="2">
484 <colspec colname="col1" colwidth="3*"/>
485 <colspec colname="col2" colwidth="1*"/>
486 <thead>
487 <row>
488 <entry>Function</entry>
489 <entry>Support Number</entry>
490 </row>
491 </thead>
492 <tbody>
493 <row>
494 <entry>Compute the 32-bit hash value for a key</entry>
495 <entry>1</entry>
496 </row>
497 <row>
498 <entry>
499 Compute the 64-bit hash value for a key given a 64-bit salt; if
500 the salt is 0, the low 32 bits of the result must match the value
501 that would have been computed by function 1
502 (optional)
503 </entry>
504 <entry>2</entry>
505 </row>
506 <row>
507 <entry>
508 Define options that are specific to this operator class
509 (optional)
510 </entry>
511 <entry>3</entry>
512 </row>
513 </tbody>
514 </tgroup>
515 </table>
516
517 <para>
518 GiST indexes have twelve support functions, seven of which are optional,
519 as shown in <xref linkend="xindex-gist-support-table"/>.
520 (For more information see <xref linkend="gist"/>.)
521 </para>
522
523 <table tocentry="1" id="xindex-gist-support-table">
524 <title>GiST Support Functions</title>
525 <tgroup cols="3">
526 <colspec colname="col1" colwidth="2*"/>
527 <colspec colname="col2" colwidth="3*"/>
528 <colspec colname="col3" colwidth="1*"/>
529 <thead>
530 <row>
531 <entry>Function</entry>
532 <entry>Description</entry>
533 <entry>Support Number</entry>
534 </row>
535 </thead>
536 <tbody>
537 <row>
538 <entry><function>consistent</function></entry>
539 <entry>determine whether key satisfies the
540 query qualifier</entry>
541 <entry>1</entry>
542 </row>
543 <row>
544 <entry><function>union</function></entry>
545 <entry>compute union of a set of keys</entry>
546 <entry>2</entry>
547 </row>
548 <row>
549 <entry><function>compress</function></entry>
550 <entry>compute a compressed representation of a key or value
551 to be indexed (optional)</entry>
552 <entry>3</entry>
553 </row>
554 <row>
555 <entry><function>decompress</function></entry>
556 <entry>compute a decompressed representation of a
557 compressed key (optional)</entry>
558 <entry>4</entry>
559 </row>
560 <row>
561 <entry><function>penalty</function></entry>
562 <entry>compute penalty for inserting new key into subtree
563 with given subtree's key</entry>
564 <entry>5</entry>
565 </row>
566 <row>
567 <entry><function>picksplit</function></entry>
568 <entry>determine which entries of a page are to be moved
569 to the new page and compute the union keys for resulting pages</entry>
570 <entry>6</entry>
571 </row>
572 <row>
573 <entry><function>same</function></entry>
574 <entry>compare two keys and return true if they are equal</entry>
575 <entry>7</entry>
576 </row>
577 <row>
578 <entry><function>distance</function></entry>
579 <entry>determine distance from key to query value (optional)</entry>
580 <entry>8</entry>
581 </row>
582 <row>
583 <entry><function>fetch</function></entry>
584 <entry>compute original representation of a compressed key for
585 index-only scans (optional)</entry>
586 <entry>9</entry>
587 </row>
588 <row>
589 <entry><function>options</function></entry>
590 <entry>define options that are specific to this operator class
591 (optional)</entry>
592 <entry>10</entry>
593 </row>
594 <row>
595 <entry><function>sortsupport</function></entry>
596 <entry>provide a sort comparator to be used in fast index builds
597 (optional)</entry>
598 <entry>11</entry>
599 </row>
600 <row>
601 <entry><function>translate_cmptype</function></entry>
602 <entry>translate compare types to strategy numbers
603 used by the operator class (optional)</entry>
604 <entry>12</entry>
605 </row>
606 </tbody>
607 </tgroup>
608 </table>
609
610 <para>
611 SP-GiST indexes have six support functions, one of which is optional, as
612 shown in <xref linkend="xindex-spgist-support-table"/>.
613 (For more information see <xref linkend="spgist"/>.)
614 </para>
615
616 <table tocentry="1" id="xindex-spgist-support-table">
617 <title>SP-GiST Support Functions</title>
618 <tgroup cols="3">
619 <colspec colname="col1" colwidth="2*"/>
620 <colspec colname="col2" colwidth="3*"/>
621 <colspec colname="col3" colwidth="1*"/>
622 <thead>
623 <row>
624 <entry>Function</entry>
625 <entry>Description</entry>
626 <entry>Support Number</entry>
627 </row>
628 </thead>
629 <tbody>
630 <row>
631 <entry><function>config</function></entry>
632 <entry>provide basic information about the operator class</entry>
633 <entry>1</entry>
634 </row>
635 <row>
636 <entry><function>choose</function></entry>
637 <entry>determine how to insert a new value into an inner tuple</entry>
638 <entry>2</entry>
639 </row>
640 <row>
641 <entry><function>picksplit</function></entry>
642 <entry>determine how to partition a set of values</entry>
643 <entry>3</entry>
644 </row>
645 <row>
646 <entry><function>inner_consistent</function></entry>
647 <entry>determine which sub-partitions need to be searched for a
648 query</entry>
649 <entry>4</entry>
650 </row>
651 <row>
652 <entry><function>leaf_consistent</function></entry>
653 <entry>determine whether key satisfies the
654 query qualifier</entry>
655 <entry>5</entry>
656 </row>
657 <row>
658 <entry><function>options</function></entry>
659 <entry>define options that are specific to this operator class
660 (optional)</entry>
661 <entry>6</entry>
662 </row>
663 </tbody>
664 </tgroup>
665 </table>
666
667 <para>
668 GIN indexes have seven support functions, four of which are optional,
669 as shown in <xref linkend="xindex-gin-support-table"/>.
670 (For more information see <xref linkend="gin"/>.)
671 </para>
672
673 <table tocentry="1" id="xindex-gin-support-table">
674 <title>GIN Support Functions</title>
675 <tgroup cols="3">
676 <colspec colname="col1" colwidth="2*"/>
677 <colspec colname="col2" colwidth="3*"/>
678 <colspec colname="col3" colwidth="1*"/>
679 <thead>
680 <row>
681 <entry>Function</entry>
682 <entry>Description</entry>
683 <entry>Support Number</entry>
684 </row>
685 </thead>
686 <tbody>
687 <row>
688 <entry><function>compare</function></entry>
689 <entry>
690 compare two keys and return an integer less than zero, zero,
691 or greater than zero, indicating whether the first key is less than,
692 equal to, or greater than the second
693 </entry>
694 <entry>1</entry>
695 </row>
696 <row>
697 <entry><function>extractValue</function></entry>
698 <entry>extract keys from a value to be indexed</entry>
699 <entry>2</entry>
700 </row>
701 <row>
702 <entry><function>extractQuery</function></entry>
703 <entry>extract keys from a query condition</entry>
704 <entry>3</entry>
705 </row>
706 <row>
707 <entry><function>consistent</function></entry>
708 <entry>
709 determine whether value matches query condition (Boolean variant)
710 (optional if support function 6 is present)
711 </entry>
712 <entry>4</entry>
713 </row>
714 <row>
715 <entry><function>comparePartial</function></entry>
716 <entry>
717 compare partial key from
718 query and key from index, and return an integer less than zero, zero,
719 or greater than zero, indicating whether GIN should ignore this index
720 entry, treat the entry as a match, or stop the index scan (optional)
721 </entry>
722 <entry>5</entry>
723 </row>
724 <row>
725 <entry><function>triConsistent</function></entry>
726 <entry>
727 determine whether value matches query condition (ternary variant)
728 (optional if support function 4 is present)
729 </entry>
730 <entry>6</entry>
731 </row>
732 <row>
733 <entry><function>options</function></entry>
734 <entry>
735 define options that are specific to this operator class
736 (optional)
737 </entry>
738 <entry>7</entry>
739 </row>
740 </tbody>
741 </tgroup>
742 </table>
743
744 <para>
745 BRIN indexes have five basic support functions, one of which is optional,
746 as shown in <xref linkend="xindex-brin-support-table"/>. Some versions of
747 the basic functions require additional support functions to be provided.
748 (For more information see <xref linkend="brin-extensibility"/>.)
749 </para>
750
751 <table tocentry="1" id="xindex-brin-support-table">
752 <title>BRIN Support Functions</title>
753 <tgroup cols="3">
754 <colspec colname="col1" colwidth="2*"/>
755 <colspec colname="col2" colwidth="3*"/>
756 <colspec colname="col3" colwidth="1*"/>
757 <thead>
758 <row>
759 <entry>Function</entry>
760 <entry>Description</entry>
761 <entry>Support Number</entry>
762 </row>
763 </thead>
764 <tbody>
765 <row>
766 <entry><function>opcInfo</function></entry>
767 <entry>
768 return internal information describing the indexed columns'
769 summary data
770 </entry>
771 <entry>1</entry>
772 </row>
773 <row>
774 <entry><function>add_value</function></entry>
775 <entry>add a new value to an existing summary index tuple</entry>
776 <entry>2</entry>
777 </row>
778 <row>
779 <entry><function>consistent</function></entry>
780 <entry>determine whether value matches query condition</entry>
781 <entry>3</entry>
782 </row>
783 <row>
784 <entry><function>union</function></entry>
785 <entry>
786 compute union of two summary tuples
787 </entry>
788 <entry>4</entry>
789 </row>
790 <row>
791 <entry><function>options</function></entry>
792 <entry>
793 define options that are specific to this operator class
794 (optional)
795 </entry>
796 <entry>5</entry>
797 </row>
798 </tbody>
799 </tgroup>
800 </table>
801
802 <para>
803 Unlike search operators, support functions return whichever data
804 type the particular index method expects; for example in the case
805 of the comparison function for B-trees, a signed integer. The number
806 and types of the arguments to each support function are likewise
807 dependent on the index method. For B-tree and hash the comparison and
808 hashing support functions take the same input data types as do the
809 operators included in the operator class, but this is not the case for
810 most GiST, SP-GiST, GIN, and BRIN support functions.
811 </para>
812 </sect2>
813
814 <sect2 id="xindex-example">
815 <title>An Example</title>
816
817 <para>
818 Now that we have seen the ideas, here is the promised example of
819 creating a new operator class.
820 (You can find a working copy of this example in
821 <filename>src/tutorial/complex.c</filename> and
822 <filename>src/tutorial/complex.sql</filename> in the source
823 distribution.)
824 The operator class encapsulates
825 operators that sort complex numbers in absolute value order, so we
826 choose the name <literal>complex_abs_ops</literal>. First, we need
827 a set of operators. The procedure for defining operators was
828 discussed in <xref linkend="xoper"/>. For an operator class on
829 B-trees, the operators we require are:
830
831 <itemizedlist spacing="compact">
832 <listitem><simpara>absolute-value less-than (strategy 1)</simpara></listitem>
833 <listitem><simpara>absolute-value less-than-or-equal (strategy 2)</simpara></listitem>
834 <listitem><simpara>absolute-value equal (strategy 3)</simpara></listitem>
835 <listitem><simpara>absolute-value greater-than-or-equal (strategy 4)</simpara></listitem>
836 <listitem><simpara>absolute-value greater-than (strategy 5)</simpara></listitem>
837 </itemizedlist>
838 </para>
839
840 <para>
841 The least error-prone way to define a related set of comparison operators
842 is to write the B-tree comparison support function first, and then write the
843 other functions as one-line wrappers around the support function. This
844 reduces the odds of getting inconsistent results for corner cases.
845 Following this approach, we first write:
846
847 <programlisting><![CDATA[
848 #define Mag(c) ((c)->x*(c)->x + (c)->y*(c)->y)
849
850 static int
851 complex_abs_cmp_internal(Complex *a, Complex *b)
852 {
853 double amag = Mag(a),
854 bmag = Mag(b);
855
856 if (amag < bmag)
857 return -1;
858 if (amag > bmag)
859 return 1;
860 return 0;
861 }
862 ]]>
863 </programlisting>
864
865 Now the less-than function looks like:
866
867 <programlisting><![CDATA[
868 PG_FUNCTION_INFO_V1(complex_abs_lt);
869
870 Datum
871 complex_abs_lt(PG_FUNCTION_ARGS)
872 {
873 Complex *a = (Complex *) PG_GETARG_POINTER(0);
874 Complex *b = (Complex *) PG_GETARG_POINTER(1);
875
876 PG_RETURN_BOOL(complex_abs_cmp_internal(a, b) < 0);
877 }
878 ]]>
879 </programlisting>
880
881 The other four functions differ only in how they compare the internal
882 function's result to zero.
883 </para>
884
885 <para>
886 Next we declare the functions and the operators based on the functions
887 to SQL:
888
889 <programlisting>
890 CREATE FUNCTION complex_abs_lt(complex, complex) RETURNS bool
891 AS '<replaceable>filename</replaceable>', 'complex_abs_lt'
892 LANGUAGE C IMMUTABLE STRICT;
893
894 CREATE OPERATOR &lt; (
895 leftarg = complex, rightarg = complex, procedure = complex_abs_lt,
896 commutator = &gt; , negator = &gt;= ,
897 restrict = scalarltsel, join = scalarltjoinsel
898 );
899 </programlisting>
900 It is important to specify the correct commutator and negator operators,
901 as well as suitable restriction and join selectivity
902 functions, otherwise the optimizer will be unable to make effective
903 use of the index.
904 </para>
905
906 <para>
907 Other things worth noting are happening here:
908
909 <itemizedlist>
910 <listitem>
911 <para>
912 There can only be one operator named, say, <literal>=</literal>
913 and taking type <type>complex</type> for both operands. In this
914 case we don't have any other operator <literal>=</literal> for
915 <type>complex</type>, but if we were building a practical data
916 type we'd probably want <literal>=</literal> to be the ordinary
917 equality operation for complex numbers (and not the equality of
918 the absolute values). In that case, we'd need to use some other
919 operator name for <function>complex_abs_eq</function>.
920 </para>
921 </listitem>
922
923 <listitem>
924 <para>
925 Although <productname>PostgreSQL</productname> can cope with
926 functions having the same SQL name as long as they have different
927 argument data types, C can only cope with one global function
928 having a given name. So we shouldn't name the C function
929 something simple like <filename>abs_eq</filename>. Usually it's
930 a good practice to include the data type name in the C function
931 name, so as not to conflict with functions for other data types.
932 </para>
933 </listitem>
934
935 <listitem>
936 <para>
937 We could have made the SQL name
938 of the function <filename>abs_eq</filename>, relying on
939 <productname>PostgreSQL</productname> to distinguish it by
940 argument data types from any other SQL function of the same name.
941 To keep the example simple, we make the function have the same
942 names at the C level and SQL level.
943 </para>
944 </listitem>
945 </itemizedlist>
946 </para>
947
948 <para>
949 The next step is the registration of the support routine required
950 by B-trees. The example C code that implements this is in the same
951 file that contains the operator functions. This is how we declare
952 the function:
953
954 <programlisting>
955 CREATE FUNCTION complex_abs_cmp(complex, complex)
956 RETURNS integer
957 AS '<replaceable>filename</replaceable>'
958 LANGUAGE C IMMUTABLE STRICT;
959 </programlisting>
960 </para>
961
962 <para>
963 Now that we have the required operators and support routine,
964 we can finally create the operator class:
965
966 <programlisting><![CDATA[
967 CREATE OPERATOR CLASS complex_abs_ops
968 DEFAULT FOR TYPE complex USING btree AS
969 OPERATOR 1 < ,
970 OPERATOR 2 <= ,
971 OPERATOR 3 = ,
972 OPERATOR 4 >= ,
973 OPERATOR 5 > ,
974 FUNCTION 1 complex_abs_cmp(complex, complex);
975 ]]>
976 </programlisting>
977 </para>
978
979 <para>
980 And we're done! It should now be possible to create
981 and use B-tree indexes on <type>complex</type> columns.
982 </para>
983
984 <para>
985 We could have written the operator entries more verbosely, as in:
986 <programlisting>
987 OPERATOR 1 &lt; (complex, complex) ,
988 </programlisting>
989 but there is no need to do so when the operators take the same data type
990 we are defining the operator class for.
991 </para>
992
993 <para>
994 The above example assumes that you want to make this new operator class the
995 default B-tree operator class for the <type>complex</type> data type.
996 If you don't, just leave out the word <literal>DEFAULT</literal>.
997 </para>
998 </sect2>
999
1000 <sect2 id="xindex-opfamily">
1001 <title>Operator Classes and Operator Families</title>
1002
1003 <para>
1004 So far we have implicitly assumed that an operator class deals with
1005 only one data type. While there certainly can be only one data type in
1006 a particular index column, it is often useful to index operations that
1007 compare an indexed column to a value of a different data type. Also,
1008 if there is use for a cross-data-type operator in connection with an
1009 operator class, it is often the case that the other data type has a
1010 related operator class of its own. It is helpful to make the connections
1011 between related classes explicit, because this can aid the planner in
1012 optimizing SQL queries (particularly for B-tree operator classes, since
1013 the planner contains a great deal of knowledge about how to work with them).
1014 </para>
1015
1016 <para>
1017 To handle these needs, <productname>PostgreSQL</productname>
1018 uses the concept of an <firstterm>operator
1019 family</firstterm><indexterm><primary>operator family</primary></indexterm>.
1020 An operator family contains one or more operator classes, and can also
1021 contain indexable operators and corresponding support functions that
1022 belong to the family as a whole but not to any single class within the
1023 family. We say that such operators and functions are <quote>loose</quote>
1024 within the family, as opposed to being bound into a specific class.
1025 Typically each operator class contains single-data-type operators
1026 while cross-data-type operators are loose in the family.
1027 </para>
1028
1029 <para>
1030 All the operators and functions in an operator family must have compatible
1031 semantics, where the compatibility requirements are set by the index
1032 method. You might therefore wonder why bother to single out particular
1033 subsets of the family as operator classes; and indeed for many purposes
1034 the class divisions are irrelevant and the family is the only interesting
1035 grouping. The reason for defining operator classes is that they specify
1036 how much of the family is needed to support any particular index.
1037 If there is an index using an operator class, then that operator class
1038 cannot be dropped without dropping the index &mdash; but other parts of
1039 the operator family, namely other operator classes and loose operators,
1040 could be dropped. Thus, an operator class should be specified to contain
1041 the minimum set of operators and functions that are reasonably needed
1042 to work with an index on a specific data type, and then related but
1043 non-essential operators can be added as loose members of the operator
1044 family.
1045 </para>
1046
1047 <para>
1048 As an example, <productname>PostgreSQL</productname> has a built-in
1049 B-tree operator family <literal>integer_ops</literal>, which includes operator
1050 classes <literal>int8_ops</literal>, <literal>int4_ops</literal>, and
1051 <literal>int2_ops</literal> for indexes on <type>bigint</type> (<type>int8</type>),
1052 <type>integer</type> (<type>int4</type>), and <type>smallint</type> (<type>int2</type>)
1053 columns respectively. The family also contains cross-data-type comparison
1054 operators allowing any two of these types to be compared, so that an index
1055 on one of these types can be searched using a comparison value of another
1056 type. The family could be duplicated by these definitions:
1057
1058 <programlisting><![CDATA[
1059 CREATE OPERATOR FAMILY integer_ops USING btree;
1060
1061 CREATE OPERATOR CLASS int8_ops
1062 DEFAULT FOR TYPE int8 USING btree FAMILY integer_ops AS
1063 -- standard int8 comparisons
1064 OPERATOR 1 < ,
1065 OPERATOR 2 <= ,
1066 OPERATOR 3 = ,
1067 OPERATOR 4 >= ,
1068 OPERATOR 5 > ,
1069 FUNCTION 1 btint8cmp(int8, int8) ,
1070 FUNCTION 2 btint8sortsupport(internal) ,
1071 FUNCTION 3 in_range(int8, int8, int8, boolean, boolean) ,
1072 FUNCTION 4 btequalimage(oid) ,
1073 FUNCTION 6 btint8skipsupport(internal) ;
1074
1075 CREATE OPERATOR CLASS int4_ops
1076 DEFAULT FOR TYPE int4 USING btree FAMILY integer_ops AS
1077 -- standard int4 comparisons
1078 OPERATOR 1 < ,
1079 OPERATOR 2 <= ,
1080 OPERATOR 3 = ,
1081 OPERATOR 4 >= ,
1082 OPERATOR 5 > ,
1083 FUNCTION 1 btint4cmp(int4, int4) ,
1084 FUNCTION 2 btint4sortsupport(internal) ,
1085 FUNCTION 3 in_range(int4, int4, int4, boolean, boolean) ,
1086 FUNCTION 4 btequalimage(oid) ,
1087 FUNCTION 6 btint4skipsupport(internal) ;
1088
1089 CREATE OPERATOR CLASS int2_ops
1090 DEFAULT FOR TYPE int2 USING btree FAMILY integer_ops AS
1091 -- standard int2 comparisons
1092 OPERATOR 1 < ,
1093 OPERATOR 2 <= ,
1094 OPERATOR 3 = ,
1095 OPERATOR 4 >= ,
1096 OPERATOR 5 > ,
1097 FUNCTION 1 btint2cmp(int2, int2) ,
1098 FUNCTION 2 btint2sortsupport(internal) ,
1099 FUNCTION 3 in_range(int2, int2, int2, boolean, boolean) ,
1100 FUNCTION 4 btequalimage(oid) ,
1101 FUNCTION 6 btint2skipsupport(internal) ;
1102
1103 ALTER OPERATOR FAMILY integer_ops USING btree ADD
1104 -- cross-type comparisons int8 vs int2
1105 OPERATOR 1 < (int8, int2) ,
1106 OPERATOR 2 <= (int8, int2) ,
1107 OPERATOR 3 = (int8, int2) ,
1108 OPERATOR 4 >= (int8, int2) ,
1109 OPERATOR 5 > (int8, int2) ,
1110 FUNCTION 1 btint82cmp(int8, int2) ,
1111
1112 -- cross-type comparisons int8 vs int4
1113 OPERATOR 1 < (int8, int4) ,
1114 OPERATOR 2 <= (int8, int4) ,
1115 OPERATOR 3 = (int8, int4) ,
1116 OPERATOR 4 >= (int8, int4) ,
1117 OPERATOR 5 > (int8, int4) ,
1118 FUNCTION 1 btint84cmp(int8, int4) ,
1119
1120 -- cross-type comparisons int4 vs int2
1121 OPERATOR 1 < (int4, int2) ,
1122 OPERATOR 2 <= (int4, int2) ,
1123 OPERATOR 3 = (int4, int2) ,
1124 OPERATOR 4 >= (int4, int2) ,
1125 OPERATOR 5 > (int4, int2) ,
1126 FUNCTION 1 btint42cmp(int4, int2) ,
1127
1128 -- cross-type comparisons int4 vs int8
1129 OPERATOR 1 < (int4, int8) ,
1130 OPERATOR 2 <= (int4, int8) ,
1131 OPERATOR 3 = (int4, int8) ,
1132 OPERATOR 4 >= (int4, int8) ,
1133 OPERATOR 5 > (int4, int8) ,
1134 FUNCTION 1 btint48cmp(int4, int8) ,
1135
1136 -- cross-type comparisons int2 vs int8
1137 OPERATOR 1 < (int2, int8) ,
1138 OPERATOR 2 <= (int2, int8) ,
1139 OPERATOR 3 = (int2, int8) ,
1140 OPERATOR 4 >= (int2, int8) ,
1141 OPERATOR 5 > (int2, int8) ,
1142 FUNCTION 1 btint28cmp(int2, int8) ,
1143
1144 -- cross-type comparisons int2 vs int4
1145 OPERATOR 1 < (int2, int4) ,
1146 OPERATOR 2 <= (int2, int4) ,
1147 OPERATOR 3 = (int2, int4) ,
1148 OPERATOR 4 >= (int2, int4) ,
1149 OPERATOR 5 > (int2, int4) ,
1150 FUNCTION 1 btint24cmp(int2, int4) ,
1151
1152 -- cross-type in_range functions
1153 FUNCTION 3 in_range(int4, int4, int8, boolean, boolean) ,
1154 FUNCTION 3 in_range(int4, int4, int2, boolean, boolean) ,
1155 FUNCTION 3 in_range(int2, int2, int8, boolean, boolean) ,
1156 FUNCTION 3 in_range(int2, int2, int4, boolean, boolean) ;
1157 ]]>
1158 </programlisting>
1159
1160 Notice that this definition <quote>overloads</quote> the operator strategy and
1161 support function numbers: each number occurs multiple times within the
1162 family. This is allowed so long as each instance of a
1163 particular number has distinct input data types. The instances that have
1164 both input types equal to an operator class's input type are the
1165 primary operators and support functions for that operator class,
1166 and in most cases should be declared as part of the operator class rather
1167 than as loose members of the family.
1168 </para>
1169
1170 <para>
1171 In a B-tree operator family, all the operators in the family must sort
1172 compatibly, as is specified in detail in <xref linkend="btree-behavior"/>.
1173 For each
1174 operator in the family there must be a support function having the same
1175 two input data types as the operator. It is recommended that a family be
1176 complete, i.e., for each combination of data types, all operators are
1177 included. Each operator class should include just the non-cross-type
1178 operators and support function for its data type.
1179 </para>
1180
1181 <para>
1182 To build a multiple-data-type hash operator family, compatible hash
1183 support functions must be created for each data type supported by the
1184 family. Here compatibility means that the functions are guaranteed to
1185 return the same hash code for any two values that are considered equal
1186 by the family's equality operators, even when the values are of different
1187 types. This is usually difficult to accomplish when the types have
1188 different physical representations, but it can be done in some cases.
1189 Furthermore, casting a value from one data type represented in the operator
1190 family to another data type also represented in the operator family via
1191 an implicit or binary coercion cast must not change the computed hash value.
1192 Notice that there is only one support function per data type, not one
1193 per equality operator. It is recommended that a family be complete, i.e.,
1194 provide an equality operator for each combination of data types.
1195 Each operator class should include just the non-cross-type equality
1196 operator and the support function for its data type.
1197 </para>
1198
1199 <para>
1200 GiST, SP-GiST, and GIN indexes do not have any explicit notion of
1201 cross-data-type operations. The set of operators supported is just
1202 whatever the primary support functions for a given operator class can
1203 handle.
1204 </para>
1205
1206 <para>
1207 In BRIN, the requirements depends on the framework that provides the
1208 operator classes. For operator classes based on <literal>minmax</literal>,
1209 the behavior required is the same as for B-tree operator families:
1210 all the operators in the family must sort compatibly, and casts must
1211 not change the associated sort ordering.
1212 </para>
1213
1214 <note>
1215 <para>
1216 Prior to <productname>PostgreSQL</productname> 8.3, there was no concept
1217 of operator families, and so any cross-data-type operators intended to be
1218 used with an index had to be bound directly into the index's operator
1219 class. While this approach still works, it is deprecated because it
1220 makes an index's dependencies too broad, and because the planner can
1221 handle cross-data-type comparisons more effectively when both data types
1222 have operators in the same operator family.
1223 </para>
1224 </note>
1225 </sect2>
1226
1227 <sect2 id="xindex-opclass-dependencies">
1228 <title>System Dependencies on Operator Classes</title>
1229
1230 <indexterm>
1231 <primary>ordering operator</primary>
1232 </indexterm>
1233
1234 <para>
1235 <productname>PostgreSQL</productname> uses operator classes to infer the
1236 properties of operators in more ways than just whether they can be used
1237 with indexes. Therefore, you might want to create operator classes
1238 even if you have no intention of indexing any columns of your data type.
1239 </para>
1240
1241 <para>
1242 In particular, there are SQL features such as <literal>ORDER BY</literal> and
1243 <literal>DISTINCT</literal> that require comparison and sorting of values.
1244 To implement these features on a user-defined data type,
1245 <productname>PostgreSQL</productname> looks for the default B-tree operator
1246 class for the data type. The <quote>equals</quote> member of this operator
1247 class defines the system's notion of equality of values for
1248 <literal>GROUP BY</literal> and <literal>DISTINCT</literal>, and the sort ordering
1249 imposed by the operator class defines the default <literal>ORDER BY</literal>
1250 ordering.
1251 </para>
1252
1253 <para>
1254 If there is no default B-tree operator class for a data type, the system
1255 will look for a default hash operator class. But since that kind of
1256 operator class only provides equality, it is only able to support grouping
1257 not sorting.
1258 </para>
1259
1260 <para>
1261 When there is no default operator class for a data type, you will get
1262 errors like <quote>could not identify an ordering operator</quote> if you
1263 try to use these SQL features with the data type.
1264 </para>
1265
1266 <note>
1267 <para>
1268 In <productname>PostgreSQL</productname> versions before 7.4,
1269 sorting and grouping operations would implicitly use operators named
1270 <literal>=</literal>, <literal>&lt;</literal>, and <literal>&gt;</literal>. The new
1271 behavior of relying on default operator classes avoids having to make
1272 any assumption about the behavior of operators with particular names.
1273 </para>
1274 </note>
1275
1276 <para>
1277 Sorting by a non-default B-tree operator class is possible by specifying
1278 the class's less-than operator in a <literal>USING</literal> option,
1279 for example
1280 <programlisting>
1281 SELECT * FROM mytable ORDER BY somecol USING ~&lt;~;
1282 </programlisting>
1283 Alternatively, specifying the class's greater-than operator
1284 in <literal>USING</literal> selects a descending-order sort.
1285 </para>
1286
1287 <para>
1288 Comparison of arrays of a user-defined type also relies on the semantics
1289 defined by the type's default B-tree operator class. If there is no
1290 default B-tree operator class, but there is a default hash operator class,
1291 then array equality is supported, but not ordering comparisons.
1292 </para>
1293
1294 <para>
1295 Another SQL feature that requires even more data-type-specific knowledge
1296 is the <literal>RANGE</literal> <replaceable>offset</replaceable>
1297 <literal>PRECEDING</literal>/<literal>FOLLOWING</literal> framing option
1298 for window functions (see <xref linkend="syntax-window-functions"/>).
1299 For a query such as
1300 <programlisting>
1301 SELECT sum(x) OVER (ORDER BY x RANGE BETWEEN 5 PRECEDING AND 10 FOLLOWING)
1302 FROM mytable;
1303 </programlisting>
1304 it is not sufficient to know how to order by <literal>x</literal>;
1305 the database must also understand how to <quote>subtract 5</quote> or
1306 <quote>add 10</quote> to the current row's value of <literal>x</literal>
1307 to identify the bounds of the current window frame. Comparing the
1308 resulting bounds to other rows' values of <literal>x</literal> is
1309 possible using the comparison operators provided by the B-tree operator
1310 class that defines the <literal>ORDER BY</literal> ordering &mdash; but
1311 addition and subtraction operators are not part of the operator class, so
1312 which ones should be used? Hard-wiring that choice would be undesirable,
1313 because different sort orders (different B-tree operator classes) might
1314 need different behavior. Therefore, a B-tree operator class can specify
1315 an <firstterm>in_range</firstterm> support function that encapsulates the
1316 addition and subtraction behaviors that make sense for its sort order.
1317 It can even provide more than one in_range support function, in case
1318 there is more than one data type that makes sense to use as the offset
1319 in <literal>RANGE</literal> clauses.
1320 If the B-tree operator class associated with the window's <literal>ORDER
1321 BY</literal> clause does not have a matching in_range support function,
1322 the <literal>RANGE</literal> <replaceable>offset</replaceable>
1323 <literal>PRECEDING</literal>/<literal>FOLLOWING</literal>
1324 option is not supported.
1325 </para>
1326
1327 <para>
1328 Another important point is that an equality operator that
1329 appears in a hash operator family is a candidate for hash joins,
1330 hash aggregation, and related optimizations. The hash operator family
1331 is essential here since it identifies the hash function(s) to use.
1332 </para>
1333 </sect2>
1334
1335 <sect2 id="xindex-ordering-ops">
1336 <title>Ordering Operators</title>
1337
1338 <para>
1339 Some index access methods (currently, only GiST and SP-GiST) support the concept of
1340 <firstterm>ordering operators</firstterm>. What we have been discussing so far
1341 are <firstterm>search operators</firstterm>. A search operator is one for which
1342 the index can be searched to find all rows satisfying
1343 <literal>WHERE</literal>
1344 <replaceable>indexed_column</replaceable>
1345 <replaceable>operator</replaceable>
1346 <replaceable>constant</replaceable>.
1347 Note that nothing is promised about the order in which the matching rows
1348 will be returned. In contrast, an ordering operator does not restrict the
1349 set of rows that can be returned, but instead determines their order.
1350 An ordering operator is one for which the index can be scanned to return
1351 rows in the order represented by
1352 <literal>ORDER BY</literal>
1353 <replaceable>indexed_column</replaceable>
1354 <replaceable>operator</replaceable>
1355 <replaceable>constant</replaceable>.
1356 The reason for defining ordering operators that way is that it supports
1357 nearest-neighbor searches, if the operator is one that measures distance.
1358 For example, a query like
1359 <programlisting><![CDATA[
1360 SELECT * FROM places ORDER BY location <-> point '(101,456)' LIMIT 10;
1361 ]]>
1362 </programlisting>
1363 finds the ten places closest to a given target point. A GiST index
1364 on the location column can do this efficiently because
1365 <literal>&lt;-&gt;</literal> is an ordering operator.
1366 </para>
1367
1368 <para>
1369 While search operators have to return Boolean results, ordering operators
1370 usually return some other type, such as float or numeric for distances.
1371 This type is normally not the same as the data type being indexed.
1372 To avoid hard-wiring assumptions about the behavior of different data
1373 types, the definition of an ordering operator is required to name
1374 a B-tree operator family that specifies the sort ordering of the result
1375 data type. As was stated in the previous section, B-tree operator families
1376 define <productname>PostgreSQL</productname>'s notion of ordering, so
1377 this is a natural representation. Since the point <literal>&lt;-&gt;</literal>
1378 operator returns <type>float8</type>, it could be specified in an operator
1379 class creation command like this:
1380 <programlisting><![CDATA[
1381 OPERATOR 15 <-> (point, point) FOR ORDER BY float_ops
1382 ]]>
1383 </programlisting>
1384 where <literal>float_ops</literal> is the built-in operator family that includes
1385 operations on <type>float8</type>. This declaration states that the index
1386 is able to return rows in order of increasing values of the
1387 <literal>&lt;-&gt;</literal> operator.
1388 </para>
1389 </sect2>
1390
1391 <sect2 id="xindex-opclass-features">
1392 <title>Special Features of Operator Classes</title>
1393
1394 <para>
1395 There are two special features of operator classes that we have
1396 not discussed yet, mainly because they are not useful
1397 with the most commonly used index methods.
1398 </para>
1399
1400 <para>
1401 Normally, declaring an operator as a member of an operator class
1402 (or family) means that the index method can retrieve exactly the set of rows
1403 that satisfy a <literal>WHERE</literal> condition using the operator. For example:
1404 <programlisting>
1405 SELECT * FROM table WHERE integer_column &lt; 4;
1406 </programlisting>
1407 can be satisfied exactly by a B-tree index on the integer column.
1408 But there are cases where an index is useful as an inexact guide to
1409 the matching rows. For example, if a GiST index stores only bounding boxes
1410 for geometric objects, then it cannot exactly satisfy a <literal>WHERE</literal>
1411 condition that tests overlap between nonrectangular objects such as
1412 polygons. Yet we could use the index to find objects whose bounding
1413 box overlaps the bounding box of the target object, and then do the
1414 exact overlap test only on the objects found by the index. If this
1415 scenario applies, the index is said to be <quote>lossy</quote> for the
1416 operator. Lossy index searches are implemented by having the index
1417 method return a <firstterm>recheck</firstterm> flag when a row might or might
1418 not really satisfy the query condition. The core system will then
1419 test the original query condition on the retrieved row to see whether
1420 it should be returned as a valid match. This approach works if
1421 the index is guaranteed to return all the required rows, plus perhaps
1422 some additional rows, which can be eliminated by performing the original
1423 operator invocation. The index methods that support lossy searches
1424 (currently, GiST, SP-GiST and GIN) allow the support functions of individual
1425 operator classes to set the recheck flag, and so this is essentially an
1426 operator-class feature.
1427 </para>
1428
1429 <para>
1430 Consider again the situation where we are storing in the index only
1431 the bounding box of a complex object such as a polygon. In this
1432 case there's not much value in storing the whole polygon in the index
1433 entry &mdash; we might as well store just a simpler object of type
1434 <type>box</type>. This situation is expressed by the <literal>STORAGE</literal>
1435 option in <command>CREATE OPERATOR CLASS</command>: we'd write something like:
1436
1437 <programlisting>
1438 CREATE OPERATOR CLASS polygon_ops
1439 DEFAULT FOR TYPE polygon USING gist AS
1440 ...
1441 STORAGE box;
1442 </programlisting>
1443
1444 At present, only the GiST, SP-GiST, GIN and BRIN index methods support a
1445 <literal>STORAGE</literal> type that's different from the column data type.
1446 The GiST <function>compress</function> and <function>decompress</function> support
1447 routines must deal with data-type conversion when <literal>STORAGE</literal>
1448 is used. SP-GiST likewise requires a <function>compress</function>
1449 support function to convert to the storage type, when that is different;
1450 if an SP-GiST opclass also supports retrieving data, the reverse
1451 conversion must be handled by the <function>consistent</function> function.
1452 In GIN, the <literal>STORAGE</literal> type identifies the type of
1453 the <quote>key</quote> values, which normally is different from the type
1454 of the indexed column &mdash; for example, an operator class for
1455 integer-array columns might have keys that are just integers. The
1456 GIN <function>extractValue</function> and <function>extractQuery</function> support
1457 routines are responsible for extracting keys from indexed values.
1458 BRIN is similar to GIN: the <literal>STORAGE</literal> type identifies the
1459 type of the stored summary values, and operator classes' support
1460 procedures are responsible for interpreting the summary values
1461 correctly.
1462 </para>
1463 </sect2>
1464
1465 </sect1>