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><
added
removed
doc/src/sgml/xindex.sgml
