summaryrefslogtreecommitdiffstats
path: root/doc/src/sgml/html/btree-support-funcs.html
blob: 72310b2804a175d5da684dc149f90d1a97c64069 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>67.3. B-Tree Support Functions</title><link rel="stylesheet" type="text/css" href="stylesheet.css" /><link rev="made" href="pgsql-docs@lists.postgresql.org" /><meta name="generator" content="DocBook XSL Stylesheets Vsnapshot" /><link rel="prev" href="btree-behavior.html" title="67.2. Behavior of B-Tree Operator Classes" /><link rel="next" href="btree-implementation.html" title="67.4. Implementation" /></head><body id="docContent" class="container-fluid col-10"><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="5" align="center">67.3. B-Tree Support Functions</th></tr><tr><td width="10%" align="left"><a accesskey="p" href="btree-behavior.html" title="67.2. Behavior of B-Tree Operator Classes">Prev</a> </td><td width="10%" align="left"><a accesskey="u" href="btree.html" title="Chapter 67. B-Tree Indexes">Up</a></td><th width="60%" align="center">Chapter 67. B-Tree Indexes</th><td width="10%" align="right"><a accesskey="h" href="index.html" title="PostgreSQL 15.5 Documentation">Home</a></td><td width="10%" align="right"> <a accesskey="n" href="btree-implementation.html" title="67.4. Implementation">Next</a></td></tr></table><hr /></div><div class="sect1" id="BTREE-SUPPORT-FUNCS"><div class="titlepage"><div><div><h2 class="title" style="clear: both">67.3. B-Tree Support Functions</h2></div></div></div><p>
  As shown in <a class="xref" href="xindex.html#XINDEX-BTREE-SUPPORT-TABLE" title="Table 38.9. B-Tree Support Functions">Table 38.9</a>, btree defines
  one required and four optional support functions.  The five
  user-defined methods are:
 </p><div class="variablelist"><dl class="variablelist"><dt><span class="term"><code class="function">order</code></span></dt><dd><p>
     For each combination of data types that a btree operator family
     provides comparison operators for, it must provide a comparison
     support function, registered in
     <code class="structname">pg_amproc</code> with support function number 1
     and
     <code class="structfield">amproclefttype</code>/<code class="structfield">amprocrighttype</code>
     equal to the left and right data types for the comparison (i.e.,
     the same data types that the matching operators are registered
     with in <code class="structname">pg_amop</code>).  The comparison
     function must take two non-null values
     <em class="replaceable"><code>A</code></em> and <em class="replaceable"><code>B</code></em> and
     return an <code class="type">int32</code> value that is
     <code class="literal">&lt;</code> <code class="literal">0</code>,
     <code class="literal">0</code>, or <code class="literal">&gt;</code>
     <code class="literal">0</code> when <em class="replaceable"><code>A</code></em>
     <code class="literal">&lt;</code> <em class="replaceable"><code>B</code></em>,
     <em class="replaceable"><code>A</code></em> <code class="literal">=</code>
     <em class="replaceable"><code>B</code></em>, or <em class="replaceable"><code>A</code></em>
     <code class="literal">&gt;</code> <em class="replaceable"><code>B</code></em>,
     respectively.  A null result is disallowed: all values of the
     data type must be comparable.  See
     <code class="filename">src/backend/access/nbtree/nbtcompare.c</code> for
     examples.
    </p><p>
     If the compared values are of a collatable data type, the
     appropriate collation OID will be passed to the comparison
     support function, using the standard
     <code class="function">PG_GET_COLLATION()</code> mechanism.
    </p></dd><dt><span class="term"><code class="function">sortsupport</code></span></dt><dd><p>
     Optionally, a btree operator family may provide <em class="firstterm">sort
      support</em> function(s), registered under support
     function number 2.  These functions allow implementing
     comparisons for sorting purposes in a more efficient way than
     naively calling the comparison support function.  The APIs
     involved in this are defined in
     <code class="filename">src/include/utils/sortsupport.h</code>.
    </p></dd><dt><span class="term"><code class="function">in_range</code></span></dt><dd><a id="id-1.10.18.5.3.3.2.1" class="indexterm"></a><a id="id-1.10.18.5.3.3.2.2" class="indexterm"></a><p>
     Optionally, a btree operator family may provide
     <em class="firstterm">in_range</em> support function(s), registered
     under support function number 3.  These are not used during btree
     index operations; rather, they extend the semantics of the
     operator family so that it can support window clauses containing
     the <code class="literal">RANGE</code> <em class="replaceable"><code>offset</code></em>
     <code class="literal">PRECEDING</code> and <code class="literal">RANGE</code>
     <em class="replaceable"><code>offset</code></em> <code class="literal">FOLLOWING</code>
     frame bound types (see <a class="xref" href="sql-expressions.html#SYNTAX-WINDOW-FUNCTIONS" title="4.2.8. Window Function Calls">Section 4.2.8</a>).  Fundamentally, the extra
     information provided is how to add or subtract an
     <em class="replaceable"><code>offset</code></em> value in a way that is
     compatible with the family's data ordering.
    </p><p>
     An <code class="function">in_range</code> function must have the signature
</p><pre class="synopsis">
in_range(<em class="replaceable"><code>val</code></em> type1, <em class="replaceable"><code>base</code></em> type1, <em class="replaceable"><code>offset</code></em> type2, <em class="replaceable"><code>sub</code></em> bool, <em class="replaceable"><code>less</code></em> bool)
returns bool
</pre><p>
     <em class="replaceable"><code>val</code></em> and
     <em class="replaceable"><code>base</code></em> must be of the same type, which
     is one of the types supported by the operator family (i.e., a
     type for which it provides an ordering).  However,
     <em class="replaceable"><code>offset</code></em> could be of a different type,
     which might be one otherwise unsupported by the family.  An
     example is that the built-in <code class="literal">time_ops</code> family
     provides an <code class="function">in_range</code> function that has
     <em class="replaceable"><code>offset</code></em> of type <code class="type">interval</code>.
     A family can provide <code class="function">in_range</code> functions for
     any of its supported types and one or more
     <em class="replaceable"><code>offset</code></em> types.  Each
     <code class="function">in_range</code> function should be entered in
     <code class="structname">pg_amproc</code> with
     <code class="structfield">amproclefttype</code> equal to
     <code class="type">type1</code> and <code class="structfield">amprocrighttype</code>
     equal to <code class="type">type2</code>.
    </p><p>
     The essential semantics of an <code class="function">in_range</code>
     function depend on the two Boolean flag parameters.  It should
     add or subtract <em class="replaceable"><code>base</code></em> and
     <em class="replaceable"><code>offset</code></em>, then compare
     <em class="replaceable"><code>val</code></em> to the result, as follows:
     </p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"><p>
        if <code class="literal">!</code><em class="replaceable"><code>sub</code></em> and
        <code class="literal">!</code><em class="replaceable"><code>less</code></em>, return
        <em class="replaceable"><code>val</code></em> <code class="literal">&gt;=</code>
        (<em class="replaceable"><code>base</code></em> <code class="literal">+</code>
        <em class="replaceable"><code>offset</code></em>)
       </p></li><li class="listitem"><p>
        if <code class="literal">!</code><em class="replaceable"><code>sub</code></em> and
        <em class="replaceable"><code>less</code></em>, return
        <em class="replaceable"><code>val</code></em> <code class="literal">&lt;=</code>
        (<em class="replaceable"><code>base</code></em> <code class="literal">+</code>
        <em class="replaceable"><code>offset</code></em>)
       </p></li><li class="listitem"><p>
        if <em class="replaceable"><code>sub</code></em> and
        <code class="literal">!</code><em class="replaceable"><code>less</code></em>, return
        <em class="replaceable"><code>val</code></em> <code class="literal">&gt;=</code>
        (<em class="replaceable"><code>base</code></em> <code class="literal">-</code>
        <em class="replaceable"><code>offset</code></em>)
       </p></li><li class="listitem"><p>
        if <em class="replaceable"><code>sub</code></em> and
        <em class="replaceable"><code>less</code></em>, return
        <em class="replaceable"><code>val</code></em> <code class="literal">&lt;=</code>
        (<em class="replaceable"><code>base</code></em> <code class="literal">-</code>
        <em class="replaceable"><code>offset</code></em>)
       </p></li></ul></div><p>
     Before doing so, the function should check the sign of
     <em class="replaceable"><code>offset</code></em>: if it is less than zero, raise
     error
     <code class="literal">ERRCODE_INVALID_PRECEDING_OR_FOLLOWING_SIZE</code>
     (22013) with error text like <span class="quote"><span class="quote">invalid preceding or
      following size in window function</span></span>.  (This is required by
     the SQL standard, although nonstandard operator families might
     perhaps choose to ignore this restriction, since there seems to
     be little semantic necessity for it.) This requirement is
     delegated to the <code class="function">in_range</code> function so that
     the core code needn't understand what <span class="quote"><span class="quote">less than
      zero</span></span> means for a particular data type.
    </p><p>
     An additional expectation is that <code class="function">in_range</code>
     functions should, if practical, avoid throwing an error if
     <em class="replaceable"><code>base</code></em> <code class="literal">+</code>
     <em class="replaceable"><code>offset</code></em> or
     <em class="replaceable"><code>base</code></em> <code class="literal">-</code>
     <em class="replaceable"><code>offset</code></em> would overflow.  The correct
     comparison result can be determined even if that value would be
     out of the data type's range.  Note that if the data type
     includes concepts such as <span class="quote"><span class="quote">infinity</span></span> or
     <span class="quote"><span class="quote">NaN</span></span>, extra care may be needed to ensure that
     <code class="function">in_range</code>'s results agree with the normal
     sort order of the operator family.
    </p><p>
     The results of the <code class="function">in_range</code> function must be
     consistent with the sort ordering imposed by the operator family.
     To be precise, given any fixed values of
     <em class="replaceable"><code>offset</code></em> and
     <em class="replaceable"><code>sub</code></em>, then:
     </p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"><p>
        If <code class="function">in_range</code> with
        <em class="replaceable"><code>less</code></em> = true is true for some
        <em class="replaceable"><code>val1</code></em> and
        <em class="replaceable"><code>base</code></em>, it must be true for every
        <em class="replaceable"><code>val2</code></em> <code class="literal">&lt;=</code>
        <em class="replaceable"><code>val1</code></em> with the same
        <em class="replaceable"><code>base</code></em>.
       </p></li><li class="listitem"><p>
        If <code class="function">in_range</code> with
        <em class="replaceable"><code>less</code></em> = true is false for some
        <em class="replaceable"><code>val1</code></em> and
        <em class="replaceable"><code>base</code></em>, it must be false for every
        <em class="replaceable"><code>val2</code></em> <code class="literal">&gt;=</code>
        <em class="replaceable"><code>val1</code></em> with the same
        <em class="replaceable"><code>base</code></em>.
       </p></li><li class="listitem"><p>
        If <code class="function">in_range</code> with
        <em class="replaceable"><code>less</code></em> = true is true for some
        <em class="replaceable"><code>val</code></em> and
        <em class="replaceable"><code>base1</code></em>, it must be true for every
        <em class="replaceable"><code>base2</code></em> <code class="literal">&gt;=</code>
        <em class="replaceable"><code>base1</code></em> with the same
        <em class="replaceable"><code>val</code></em>.
       </p></li><li class="listitem"><p>
        If <code class="function">in_range</code> with
        <em class="replaceable"><code>less</code></em> = true is false for some
        <em class="replaceable"><code>val</code></em> and
        <em class="replaceable"><code>base1</code></em>, it must be false for every
        <em class="replaceable"><code>base2</code></em> <code class="literal">&lt;=</code>
        <em class="replaceable"><code>base1</code></em> with the same
        <em class="replaceable"><code>val</code></em>.
       </p></li></ul></div><p>
     Analogous statements with inverted conditions hold when
     <em class="replaceable"><code>less</code></em> = false.
    </p><p>
     If the type being ordered (<code class="type">type1</code>) is collatable, the
     appropriate collation OID will be passed to the
     <code class="function">in_range</code> function, using the standard
     PG_GET_COLLATION() mechanism.
    </p><p>
     <code class="function">in_range</code> functions need not handle NULL
     inputs, and typically will be marked strict.
    </p></dd><dt><span class="term"><code class="function">equalimage</code></span></dt><dd><p>
     Optionally, a btree operator family may provide
     <code class="function">equalimage</code> (<span class="quote"><span class="quote">equality implies image
      equality</span></span>) support functions, registered under support
     function number 4.  These functions allow the core code to
     determine when it is safe to apply the btree deduplication
     optimization.  Currently, <code class="function">equalimage</code>
     functions are only called when building or rebuilding an index.
    </p><p>
     An <code class="function">equalimage</code> function must have the
     signature
</p><pre class="synopsis">
equalimage(<em class="replaceable"><code>opcintype</code></em> <code class="type">oid</code>) returns bool
</pre><p>
     The return value is static information about an operator class
     and collation.  Returning <code class="literal">true</code> indicates that
     the <code class="function">order</code> function for the operator class is
     guaranteed to only return <code class="literal">0</code> (<span class="quote"><span class="quote">arguments
      are equal</span></span>) when its <em class="replaceable"><code>A</code></em> and
     <em class="replaceable"><code>B</code></em> arguments are also interchangeable
     without any loss of semantic information.  Not registering an
     <code class="function">equalimage</code> function or returning
     <code class="literal">false</code> indicates that this condition cannot be
     assumed to hold.
    </p><p>
     The <em class="replaceable"><code>opcintype</code></em> argument is the
     <code class="literal"><code class="structname">pg_type</code>.oid</code> of the
     data type that the operator class indexes.  This is a convenience
     that allows reuse of the same underlying
     <code class="function">equalimage</code> function across operator classes.
     If <em class="replaceable"><code>opcintype</code></em> is a collatable data
     type, the appropriate collation OID will be passed to the
     <code class="function">equalimage</code> function, using the standard
     <code class="function">PG_GET_COLLATION()</code> mechanism.
    </p><p>
     As far as the operator class is concerned, returning
     <code class="literal">true</code> indicates that deduplication is safe (or
     safe for the collation whose OID was passed to its
     <code class="function">equalimage</code> function).  However, the core
     code will only deem deduplication safe for an index when
     <span class="emphasis"><em>every</em></span> indexed column uses an operator class
     that registers an <code class="function">equalimage</code> function, and
     each function actually returns <code class="literal">true</code> when
     called.
    </p><p>
     Image equality is <span class="emphasis"><em>almost</em></span> the same condition
     as simple bitwise equality.  There is one subtle difference: When
     indexing a varlena data type, the on-disk representation of two
     image equal datums may not be bitwise equal due to inconsistent
     application of <acronym class="acronym">TOAST</acronym> compression on input.
     Formally, when an operator class's
     <code class="function">equalimage</code> function returns
     <code class="literal">true</code>, it is safe to assume that the
     <code class="literal">datum_image_eq()</code> C function will always agree
     with the operator class's <code class="function">order</code> function
     (provided that the same collation OID is passed to both the
     <code class="function">equalimage</code> and <code class="function">order</code>
     functions).
    </p><p>
     The core code is fundamentally unable to deduce anything about
     the <span class="quote"><span class="quote">equality implies image equality</span></span> status of an
     operator class within a multiple-data-type family based on
     details from other operator classes in the same family.  Also, it
     is not sensible for an operator family to register a cross-type
     <code class="function">equalimage</code> function, and attempting to do so
     will result in an error.  This is because <span class="quote"><span class="quote">equality implies
      image equality</span></span> status does not just depend on
     sorting/equality semantics, which are more or less defined at the
     operator family level.  In general, the semantics that one
     particular data type implements must be considered separately.
    </p><p>
     The convention followed by the operator classes included with the
     core <span class="productname">PostgreSQL</span> distribution is to
     register a stock, generic <code class="function">equalimage</code>
     function.  Most operator classes register
     <code class="function">btequalimage()</code>, which indicates that
     deduplication is safe unconditionally.  Operator classes for
     collatable data types such as <code class="type">text</code> register
     <code class="function">btvarstrequalimage()</code>, which indicates that
     deduplication is safe with deterministic collations.  Best
     practice for third-party extensions is to register their own
     custom function to retain control.
    </p></dd><dt><span class="term"><code class="function">options</code></span></dt><dd><p>
     Optionally, a B-tree operator family may provide
     <code class="function">options</code> (<span class="quote"><span class="quote">operator class specific
     options</span></span>) support functions, registered under support
     function number 5.  These functions define a set of user-visible
     parameters that control operator class behavior.
    </p><p>
     An <code class="function">options</code> support function must have the
     signature
</p><pre class="synopsis">
options(<em class="replaceable"><code>relopts</code></em> <code class="type">local_relopts *</code>) returns void
</pre><p>
     The function is passed a pointer to a <code class="structname">local_relopts</code>
     struct, which needs to be filled with a set of operator class
     specific options.  The options can be accessed from other support
     functions using the <code class="literal">PG_HAS_OPCLASS_OPTIONS()</code> and
     <code class="literal">PG_GET_OPCLASS_OPTIONS()</code> macros.
    </p><p>
     Currently, no B-Tree operator class has an <code class="function">options</code>
     support function.  B-tree doesn't allow flexible representation of keys
     like GiST, SP-GiST, GIN and BRIN do.  So, <code class="function">options</code>
     probably doesn't have much application in the current B-tree index
     access method.  Nevertheless, this support function was added to B-tree
     for uniformity, and will probably find uses during further
     evolution of B-tree in <span class="productname">PostgreSQL</span>.
    </p></dd></dl></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="btree-behavior.html" title="67.2. Behavior of B-Tree Operator Classes">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="btree.html" title="Chapter 67. B-Tree Indexes">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="btree-implementation.html" title="67.4. Implementation">Next</a></td></tr><tr><td width="40%" align="left" valign="top">67.2. Behavior of B-Tree Operator Classes </td><td width="20%" align="center"><a accesskey="h" href="index.html" title="PostgreSQL 15.5 Documentation">Home</a></td><td width="40%" align="right" valign="top"> 67.4. Implementation</td></tr></table></div></body></html>