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
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
|
<?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>65.3. Extensibility</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 V1.79.1" /><link rel="prev" href="spgist-builtin-opclasses.html" title="65.2. Built-in Operator Classes" /><link rel="next" href="spgist-implementation.html" title="65.4. Implementation" /></head><body id="docContent" class="container-fluid col-10"><div xmlns="http://www.w3.org/TR/xhtml1/transitional" class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="5" align="center">65.3. Extensibility</th></tr><tr><td width="10%" align="left"><a accesskey="p" href="spgist-builtin-opclasses.html" title="65.2. Built-in Operator Classes">Prev</a> </td><td width="10%" align="left"><a accesskey="u" href="spgist.html" title="Chapter 65. SP-GiST Indexes">Up</a></td><th width="60%" align="center">Chapter 65. SP-GiST Indexes</th><td width="10%" align="right"><a accesskey="h" href="index.html" title="PostgreSQL 13.4 Documentation">Home</a></td><td width="10%" align="right"> <a accesskey="n" href="spgist-implementation.html" title="65.4. Implementation">Next</a></td></tr></table><hr></hr></div><div class="sect1" id="SPGIST-EXTENSIBILITY"><div class="titlepage"><div><div><h2 class="title" style="clear: both">65.3. Extensibility</h2></div></div></div><p>
<acronym class="acronym">SP-GiST</acronym> offers an interface with a high level of
abstraction, requiring the access method developer to implement only
methods specific to a given data type. The <acronym class="acronym">SP-GiST</acronym> core
is responsible for efficient disk mapping and searching the tree structure.
It also takes care of concurrency and logging considerations.
</p><p>
Leaf tuples of an <acronym class="acronym">SP-GiST</acronym> tree contain values of the
same data type as the indexed column. Leaf tuples at the root level will
always contain the original indexed data value, but leaf tuples at lower
levels might contain only a compressed representation, such as a suffix.
In that case the operator class support functions must be able to
reconstruct the original value using information accumulated from the
inner tuples that are passed through to reach the leaf level.
</p><p>
Inner tuples are more complex, since they are branching points in the
search tree. Each inner tuple contains a set of one or more
<em class="firstterm">nodes</em>, which represent groups of similar leaf values.
A node contains a downlink that leads either to another, lower-level inner
tuple, or to a short list of leaf tuples that all lie on the same index page.
Each node normally has a <em class="firstterm">label</em> that describes it; for example,
in a radix tree the node label could be the next character of the string
value. (Alternatively, an operator class can omit the node labels, if it
works with a fixed set of nodes for all inner tuples;
see <a class="xref" href="spgist-implementation.html#SPGIST-NULL-LABELS" title="65.4.2. SP-GiST Without Node Labels">Section 65.4.2</a>.)
Optionally, an inner tuple can have a <em class="firstterm">prefix</em> value
that describes all its members. In a radix tree this could be the common
prefix of the represented strings. The prefix value is not necessarily
really a prefix, but can be any data needed by the operator class;
for example, in a quad-tree it can store the central point that the four
quadrants are measured with respect to. A quad-tree inner tuple would
then also contain four nodes corresponding to the quadrants around this
central point.
</p><p>
Some tree algorithms require knowledge of level (or depth) of the current
tuple, so the <acronym class="acronym">SP-GiST</acronym> core provides the possibility for
operator classes to manage level counting while descending the tree.
There is also support for incrementally reconstructing the represented
value when that is needed, and for passing down additional data (called
<em class="firstterm">traverse values</em>) during a tree descent.
</p><div class="note"><h3 class="title">Note</h3><p>
The <acronym class="acronym">SP-GiST</acronym> core code takes care of null entries.
Although <acronym class="acronym">SP-GiST</acronym> indexes do store entries for nulls
in indexed columns, this is hidden from the index operator class code:
no null index entries or search conditions will ever be passed to the
operator class methods. (It is assumed that <acronym class="acronym">SP-GiST</acronym>
operators are strict and so cannot succeed for null values.) Null values
are therefore not discussed further here.
</p></div><p>
There are five user-defined methods that an index operator class for
<acronym class="acronym">SP-GiST</acronym> must provide, and two are optional. All five
mandatory methods follow the convention of accepting two <code class="type">internal</code>
arguments, the first of which is a pointer to a C struct containing input
values for the support method, while the second argument is a pointer to a
C struct where output values must be placed. Four of the mandatory methods just
return <code class="type">void</code>, since all their results appear in the output struct; but
<code class="function">leaf_consistent</code> returns a <code class="type">boolean</code> result.
The methods must not modify any fields of their input structs. In all
cases, the output struct is initialized to zeroes before calling the
user-defined method. The optional sixth method <code class="function">compress</code>
accepts a <code class="type">datum</code> to be indexed as the only argument and returns a value suitable
for physical storage in a leaf tuple. The optional seventh method
<code class="function">options</code> accepts an <code class="type">internal</code> pointer to a C struct, where
opclass-specific parameters should be placed, and returns <code class="type">void</code>.
</p><p>
The five mandatory user-defined methods are:
</p><div class="variablelist"><dl class="variablelist"><dt><span class="term"><code class="function">config</code></span></dt><dd><p>
Returns static information about the index implementation, including
the data type OIDs of the prefix and node label data types.
</p><p>
The <acronym class="acronym">SQL</acronym> declaration of the function must look like this:
</p><pre class="programlisting">
CREATE FUNCTION my_config(internal, internal) RETURNS void ...
</pre><p>
The first argument is a pointer to a <code class="structname">spgConfigIn</code>
C struct, containing input data for the function.
The second argument is a pointer to a <code class="structname">spgConfigOut</code>
C struct, which the function must fill with result data.
</p><pre class="programlisting">
typedef struct spgConfigIn
{
Oid attType; /* Data type to be indexed */
} spgConfigIn;
typedef struct spgConfigOut
{
Oid prefixType; /* Data type of inner-tuple prefixes */
Oid labelType; /* Data type of inner-tuple node labels */
Oid leafType; /* Data type of leaf-tuple values */
bool canReturnData; /* Opclass can reconstruct original data */
bool longValuesOK; /* Opclass can cope with values > 1 page */
} spgConfigOut;
</pre><p>
<code class="structfield">attType</code> is passed in order to support polymorphic
index operator classes; for ordinary fixed-data-type operator classes, it
will always have the same value and so can be ignored.
</p><p>
For operator classes that do not use prefixes,
<code class="structfield">prefixType</code> can be set to <code class="literal">VOIDOID</code>.
Likewise, for operator classes that do not use node labels,
<code class="structfield">labelType</code> can be set to <code class="literal">VOIDOID</code>.
<code class="structfield">canReturnData</code> should be set true if the operator class
is capable of reconstructing the originally-supplied index value.
<code class="structfield">longValuesOK</code> should be set true only when the
<code class="structfield">attType</code> is of variable length and the operator
class is capable of segmenting long values by repeated suffixing
(see <a class="xref" href="spgist-implementation.html#SPGIST-LIMITS" title="65.4.1. SP-GiST Limits">Section 65.4.1</a>).
</p><p>
<code class="structfield">leafType</code> is typically the same as
<code class="structfield">attType</code>. For the reasons of backward
compatibility, method <code class="function">config</code> can
leave <code class="structfield">leafType</code> uninitialized; that would
give the same effect as setting <code class="structfield">leafType</code> equal
to <code class="structfield">attType</code>. When <code class="structfield">attType</code>
and <code class="structfield">leafType</code> are different, then optional
method <code class="function">compress</code> must be provided.
Method <code class="function">compress</code> is responsible
for transformation of datums to be indexed from <code class="structfield">attType</code>
to <code class="structfield">leafType</code>.
Note: both consistent functions will get <code class="structfield">scankeys</code>
unchanged, without transformation using <code class="function">compress</code>.
</p></dd><dt><span class="term"><code class="function">choose</code></span></dt><dd><p>
Chooses a method for inserting a new value into an inner tuple.
</p><p>
The <acronym class="acronym">SQL</acronym> declaration of the function must look like this:
</p><pre class="programlisting">
CREATE FUNCTION my_choose(internal, internal) RETURNS void ...
</pre><p>
The first argument is a pointer to a <code class="structname">spgChooseIn</code>
C struct, containing input data for the function.
The second argument is a pointer to a <code class="structname">spgChooseOut</code>
C struct, which the function must fill with result data.
</p><pre class="programlisting">
typedef struct spgChooseIn
{
Datum datum; /* original datum to be indexed */
Datum leafDatum; /* current datum to be stored at leaf */
int level; /* current level (counting from zero) */
/* Data from current inner tuple */
bool allTheSame; /* tuple is marked all-the-same? */
bool hasPrefix; /* tuple has a prefix? */
Datum prefixDatum; /* if so, the prefix value */
int nNodes; /* number of nodes in the inner tuple */
Datum *nodeLabels; /* node label values (NULL if none) */
} spgChooseIn;
typedef enum spgChooseResultType
{
spgMatchNode = 1, /* descend into existing node */
spgAddNode, /* add a node to the inner tuple */
spgSplitTuple /* split inner tuple (change its prefix) */
} spgChooseResultType;
typedef struct spgChooseOut
{
spgChooseResultType resultType; /* action code, see above */
union
{
struct /* results for spgMatchNode */
{
int nodeN; /* descend to this node (index from 0) */
int levelAdd; /* increment level by this much */
Datum restDatum; /* new leaf datum */
} matchNode;
struct /* results for spgAddNode */
{
Datum nodeLabel; /* new node's label */
int nodeN; /* where to insert it (index from 0) */
} addNode;
struct /* results for spgSplitTuple */
{
/* Info to form new upper-level inner tuple with one child tuple */
bool prefixHasPrefix; /* tuple should have a prefix? */
Datum prefixPrefixDatum; /* if so, its value */
int prefixNNodes; /* number of nodes */
Datum *prefixNodeLabels; /* their labels (or NULL for
* no labels) */
int childNodeN; /* which node gets child tuple */
/* Info to form new lower-level inner tuple with all old nodes */
bool postfixHasPrefix; /* tuple should have a prefix? */
Datum postfixPrefixDatum; /* if so, its value */
} splitTuple;
} result;
} spgChooseOut;
</pre><p>
<code class="structfield">datum</code> is the original datum of
<code class="structname">spgConfigIn</code>.<code class="structfield">attType</code>
type that was to be inserted into the index.
<code class="structfield">leafDatum</code> is a value of
<code class="structname">spgConfigOut</code>.<code class="structfield">leafType</code>
type, which is initially a result of method
<code class="function">compress</code> applied to <code class="structfield">datum</code>
when method <code class="function">compress</code> is provided, or the same value as
<code class="structfield">datum</code> otherwise.
<code class="structfield">leafDatum</code> can change at lower levels of the tree
if the <code class="function">choose</code> or <code class="function">picksplit</code>
methods change it. When the insertion search reaches a leaf page,
the current value of <code class="structfield">leafDatum</code> is what will be stored
in the newly created leaf tuple.
<code class="structfield">level</code> is the current inner tuple's level, starting at
zero for the root level.
<code class="structfield">allTheSame</code> is true if the current inner tuple is
marked as containing multiple equivalent nodes
(see <a class="xref" href="spgist-implementation.html#SPGIST-ALL-THE-SAME" title="65.4.3. “All-the-Same” Inner Tuples">Section 65.4.3</a>).
<code class="structfield">hasPrefix</code> is true if the current inner tuple contains
a prefix; if so,
<code class="structfield">prefixDatum</code> is its value.
<code class="structfield">nNodes</code> is the number of child nodes contained in the
inner tuple, and
<code class="structfield">nodeLabels</code> is an array of their label values, or
NULL if there are no labels.
</p><p>
The <code class="function">choose</code> function can determine either that
the new value matches one of the existing child nodes, or that a new
child node must be added, or that the new value is inconsistent with
the tuple prefix and so the inner tuple must be split to create a
less restrictive prefix.
</p><p>
If the new value matches one of the existing child nodes,
set <code class="structfield">resultType</code> to <code class="literal">spgMatchNode</code>.
Set <code class="structfield">nodeN</code> to the index (from zero) of that node in
the node array.
Set <code class="structfield">levelAdd</code> to the increment in
<code class="structfield">level</code> caused by descending through that node,
or leave it as zero if the operator class does not use levels.
Set <code class="structfield">restDatum</code> to equal <code class="structfield">leafDatum</code>
if the operator class does not modify datums from one level to the
next, or otherwise set it to the modified value to be used as
<code class="structfield">leafDatum</code> at the next level.
</p><p>
If a new child node must be added,
set <code class="structfield">resultType</code> to <code class="literal">spgAddNode</code>.
Set <code class="structfield">nodeLabel</code> to the label to be used for the new
node, and set <code class="structfield">nodeN</code> to the index (from zero) at which
to insert the node in the node array.
After the node has been added, the <code class="function">choose</code>
function will be called again with the modified inner tuple;
that call should result in an <code class="literal">spgMatchNode</code> result.
</p><p>
If the new value is inconsistent with the tuple prefix,
set <code class="structfield">resultType</code> to <code class="literal">spgSplitTuple</code>.
This action moves all the existing nodes into a new lower-level
inner tuple, and replaces the existing inner tuple with a tuple
having a single downlink pointing to the new lower-level inner tuple.
Set <code class="structfield">prefixHasPrefix</code> to indicate whether the new
upper tuple should have a prefix, and if so set
<code class="structfield">prefixPrefixDatum</code> to the prefix value. This new
prefix value must be sufficiently less restrictive than the original
to accept the new value to be indexed.
Set <code class="structfield">prefixNNodes</code> to the number of nodes needed in the
new tuple, and set <code class="structfield">prefixNodeLabels</code> to a palloc'd array
holding their labels, or to NULL if node labels are not required.
Note that the total size of the new upper tuple must be no more
than the total size of the tuple it is replacing; this constrains
the lengths of the new prefix and new labels.
Set <code class="structfield">childNodeN</code> to the index (from zero) of the node
that will downlink to the new lower-level inner tuple.
Set <code class="structfield">postfixHasPrefix</code> to indicate whether the new
lower-level inner tuple should have a prefix, and if so set
<code class="structfield">postfixPrefixDatum</code> to the prefix value. The
combination of these two prefixes and the downlink node's label
(if any) must have the same meaning as the original prefix, because
there is no opportunity to alter the node labels that are moved to
the new lower-level tuple, nor to change any child index entries.
After the node has been split, the <code class="function">choose</code>
function will be called again with the replacement inner tuple.
That call may return an <code class="literal">spgAddNode</code> result, if no suitable
node was created by the <code class="literal">spgSplitTuple</code> action. Eventually
<code class="function">choose</code> must return <code class="literal">spgMatchNode</code> to
allow the insertion to descend to the next level.
</p></dd><dt><span class="term"><code class="function">picksplit</code></span></dt><dd><p>
Decides how to create a new inner tuple over a set of leaf tuples.
</p><p>
The <acronym class="acronym">SQL</acronym> declaration of the function must look like this:
</p><pre class="programlisting">
CREATE FUNCTION my_picksplit(internal, internal) RETURNS void ...
</pre><p>
The first argument is a pointer to a <code class="structname">spgPickSplitIn</code>
C struct, containing input data for the function.
The second argument is a pointer to a <code class="structname">spgPickSplitOut</code>
C struct, which the function must fill with result data.
</p><pre class="programlisting">
typedef struct spgPickSplitIn
{
int nTuples; /* number of leaf tuples */
Datum *datums; /* their datums (array of length nTuples) */
int level; /* current level (counting from zero) */
} spgPickSplitIn;
typedef struct spgPickSplitOut
{
bool hasPrefix; /* new inner tuple should have a prefix? */
Datum prefixDatum; /* if so, its value */
int nNodes; /* number of nodes for new inner tuple */
Datum *nodeLabels; /* their labels (or NULL for no labels) */
int *mapTuplesToNodes; /* node index for each leaf tuple */
Datum *leafTupleDatums; /* datum to store in each new leaf tuple */
} spgPickSplitOut;
</pre><p>
<code class="structfield">nTuples</code> is the number of leaf tuples provided.
<code class="structfield">datums</code> is an array of their datum values of
<code class="structname">spgConfigOut</code>.<code class="structfield">leafType</code>
type.
<code class="structfield">level</code> is the current level that all the leaf tuples
share, which will become the level of the new inner tuple.
</p><p>
Set <code class="structfield">hasPrefix</code> to indicate whether the new inner
tuple should have a prefix, and if so set
<code class="structfield">prefixDatum</code> to the prefix value.
Set <code class="structfield">nNodes</code> to indicate the number of nodes that
the new inner tuple will contain, and
set <code class="structfield">nodeLabels</code> to an array of their label values,
or to NULL if node labels are not required.
Set <code class="structfield">mapTuplesToNodes</code> to an array that gives the index
(from zero) of the node that each leaf tuple should be assigned to.
Set <code class="structfield">leafTupleDatums</code> to an array of the values to
be stored in the new leaf tuples (these will be the same as the
input <code class="structfield">datums</code> if the operator class does not modify
datums from one level to the next).
Note that the <code class="function">picksplit</code> function is
responsible for palloc'ing the
<code class="structfield">nodeLabels</code>, <code class="structfield">mapTuplesToNodes</code> and
<code class="structfield">leafTupleDatums</code> arrays.
</p><p>
If more than one leaf tuple is supplied, it is expected that the
<code class="function">picksplit</code> function will classify them into more than
one node; otherwise it is not possible to split the leaf tuples
across multiple pages, which is the ultimate purpose of this
operation. Therefore, if the <code class="function">picksplit</code> function
ends up placing all the leaf tuples in the same node, the core
SP-GiST code will override that decision and generate an inner
tuple in which the leaf tuples are assigned at random to several
identically-labeled nodes. Such a tuple is marked
<code class="literal">allTheSame</code> to signify that this has happened. The
<code class="function">choose</code> and <code class="function">inner_consistent</code> functions
must take suitable care with such inner tuples.
See <a class="xref" href="spgist-implementation.html#SPGIST-ALL-THE-SAME" title="65.4.3. “All-the-Same” Inner Tuples">Section 65.4.3</a> for more information.
</p><p>
<code class="function">picksplit</code> can be applied to a single leaf tuple only
in the case that the <code class="function">config</code> function set
<code class="structfield">longValuesOK</code> to true and a larger-than-a-page input
value has been supplied. In this case the point of the operation is
to strip off a prefix and produce a new, shorter leaf datum value.
The call will be repeated until a leaf datum short enough to fit on
a page has been produced. See <a class="xref" href="spgist-implementation.html#SPGIST-LIMITS" title="65.4.1. SP-GiST Limits">Section 65.4.1</a> for
more information.
</p></dd><dt><span class="term"><code class="function">inner_consistent</code></span></dt><dd><p>
Returns set of nodes (branches) to follow during tree search.
</p><p>
The <acronym class="acronym">SQL</acronym> declaration of the function must look like this:
</p><pre class="programlisting">
CREATE FUNCTION my_inner_consistent(internal, internal) RETURNS void ...
</pre><p>
The first argument is a pointer to a <code class="structname">spgInnerConsistentIn</code>
C struct, containing input data for the function.
The second argument is a pointer to a <code class="structname">spgInnerConsistentOut</code>
C struct, which the function must fill with result data.
</p><pre class="programlisting">
typedef struct spgInnerConsistentIn
{
ScanKey scankeys; /* array of operators and comparison values */
ScanKey orderbys; /* array of ordering operators and comparison
* values */
int nkeys; /* length of scankeys array */
int norderbys; /* length of orderbys array */
Datum reconstructedValue; /* value reconstructed at parent */
void *traversalValue; /* opclass-specific traverse value */
MemoryContext traversalMemoryContext; /* put new traverse values here */
int level; /* current level (counting from zero) */
bool returnData; /* original data must be returned? */
/* Data from current inner tuple */
bool allTheSame; /* tuple is marked all-the-same? */
bool hasPrefix; /* tuple has a prefix? */
Datum prefixDatum; /* if so, the prefix value */
int nNodes; /* number of nodes in the inner tuple */
Datum *nodeLabels; /* node label values (NULL if none) */
} spgInnerConsistentIn;
typedef struct spgInnerConsistentOut
{
int nNodes; /* number of child nodes to be visited */
int *nodeNumbers; /* their indexes in the node array */
int *levelAdds; /* increment level by this much for each */
Datum *reconstructedValues; /* associated reconstructed values */
void **traversalValues; /* opclass-specific traverse values */
double **distances; /* associated distances */
} spgInnerConsistentOut;
</pre><p>
The array <code class="structfield">scankeys</code>, of length <code class="structfield">nkeys</code>,
describes the index search condition(s). These conditions are
combined with AND — only index entries that satisfy all of
them are interesting. (Note that <code class="structfield">nkeys</code> = 0 implies
that all index entries satisfy the query.) Usually the consistent
function only cares about the <code class="structfield">sk_strategy</code> and
<code class="structfield">sk_argument</code> fields of each array entry, which
respectively give the indexable operator and comparison value.
In particular it is not necessary to check <code class="structfield">sk_flags</code> to
see if the comparison value is NULL, because the SP-GiST core code
will filter out such conditions.
The array <code class="structfield">orderbys</code>, of length <code class="structfield">norderbys</code>,
describes ordering operators (if any) in the same manner.
<code class="structfield">reconstructedValue</code> is the value reconstructed for the
parent tuple; it is <code class="literal">(Datum) 0</code> at the root level or if the
<code class="function">inner_consistent</code> function did not provide a value at the
parent level. <code class="structfield">reconstructedValue</code> is always of
<code class="structname">spgConfigOut</code>.<code class="structfield">leafType</code> type.
<code class="structfield">traversalValue</code> is a pointer to any traverse data
passed down from the previous call of <code class="function">inner_consistent</code>
on the parent index tuple, or NULL at the root level.
<code class="structfield">traversalMemoryContext</code> is the memory context in which
to store output traverse values (see below).
<code class="structfield">level</code> is the current inner tuple's level, starting at
zero for the root level.
<code class="structfield">returnData</code> is <code class="literal">true</code> if reconstructed data is
required for this query; this will only be so if the
<code class="function">config</code> function asserted <code class="structfield">canReturnData</code>.
<code class="structfield">allTheSame</code> is true if the current inner tuple is
marked <span class="quote">“<span class="quote">all-the-same</span>”</span>; in this case all the nodes have the
same label (if any) and so either all or none of them match the query
(see <a class="xref" href="spgist-implementation.html#SPGIST-ALL-THE-SAME" title="65.4.3. “All-the-Same” Inner Tuples">Section 65.4.3</a>).
<code class="structfield">hasPrefix</code> is true if the current inner tuple contains
a prefix; if so,
<code class="structfield">prefixDatum</code> is its value.
<code class="structfield">nNodes</code> is the number of child nodes contained in the
inner tuple, and
<code class="structfield">nodeLabels</code> is an array of their label values, or
NULL if the nodes do not have labels.
</p><p>
<code class="structfield">nNodes</code> must be set to the number of child nodes that
need to be visited by the search, and
<code class="structfield">nodeNumbers</code> must be set to an array of their indexes.
If the operator class keeps track of levels, set
<code class="structfield">levelAdds</code> to an array of the level increments
required when descending to each node to be visited. (Often these
increments will be the same for all the nodes, but that's not
necessarily so, so an array is used.)
If value reconstruction is needed, set
<code class="structfield">reconstructedValues</code> to an array of the values
of <code class="structname">spgConfigOut</code>.<code class="structfield">leafType</code> type
reconstructed for each child node to be visited; otherwise, leave
<code class="structfield">reconstructedValues</code> as NULL.
If ordered search is performed, set <code class="structfield">distances</code>
to an array of distance values according to <code class="structfield">orderbys</code>
array (nodes with lowest distances will be processed first). Leave it
NULL otherwise.
If it is desired to pass down additional out-of-band information
(<span class="quote">“<span class="quote">traverse values</span>”</span>) to lower levels of the tree search,
set <code class="structfield">traversalValues</code> to an array of the appropriate
traverse values, one for each child node to be visited; otherwise,
leave <code class="structfield">traversalValues</code> as NULL.
Note that the <code class="function">inner_consistent</code> function is
responsible for palloc'ing the
<code class="structfield">nodeNumbers</code>, <code class="structfield">levelAdds</code>,
<code class="structfield">distances</code>,
<code class="structfield">reconstructedValues</code>, and
<code class="structfield">traversalValues</code> arrays in the current memory context.
However, any output traverse values pointed to by
the <code class="structfield">traversalValues</code> array should be allocated
in <code class="structfield">traversalMemoryContext</code>.
Each traverse value must be a single palloc'd chunk.
</p></dd><dt><span class="term"><code class="function">leaf_consistent</code></span></dt><dd><p>
Returns true if a leaf tuple satisfies a query.
</p><p>
The <acronym class="acronym">SQL</acronym> declaration of the function must look like this:
</p><pre class="programlisting">
CREATE FUNCTION my_leaf_consistent(internal, internal) RETURNS bool ...
</pre><p>
The first argument is a pointer to a <code class="structname">spgLeafConsistentIn</code>
C struct, containing input data for the function.
The second argument is a pointer to a <code class="structname">spgLeafConsistentOut</code>
C struct, which the function must fill with result data.
</p><pre class="programlisting">
typedef struct spgLeafConsistentIn
{
ScanKey scankeys; /* array of operators and comparison values */
ScanKey orderbys; /* array of ordering operators and comparison
* values */
int nkeys; /* length of scankeys array */
int norderbys; /* length of orderbys array */
Datum reconstructedValue; /* value reconstructed at parent */
void *traversalValue; /* opclass-specific traverse value */
int level; /* current level (counting from zero) */
bool returnData; /* original data must be returned? */
Datum leafDatum; /* datum in leaf tuple */
} spgLeafConsistentIn;
typedef struct spgLeafConsistentOut
{
Datum leafValue; /* reconstructed original data, if any */
bool recheck; /* set true if operator must be rechecked */
bool recheckDistances; /* set true if distances must be rechecked */
double *distances; /* associated distances */
} spgLeafConsistentOut;
</pre><p>
The array <code class="structfield">scankeys</code>, of length <code class="structfield">nkeys</code>,
describes the index search condition(s). These conditions are
combined with AND — only index entries that satisfy all of
them satisfy the query. (Note that <code class="structfield">nkeys</code> = 0 implies
that all index entries satisfy the query.) Usually the consistent
function only cares about the <code class="structfield">sk_strategy</code> and
<code class="structfield">sk_argument</code> fields of each array entry, which
respectively give the indexable operator and comparison value.
In particular it is not necessary to check <code class="structfield">sk_flags</code> to
see if the comparison value is NULL, because the SP-GiST core code
will filter out such conditions.
The array <code class="structfield">orderbys</code>, of length <code class="structfield">norderbys</code>,
describes the ordering operators in the same manner.
<code class="structfield">reconstructedValue</code> is the value reconstructed for the
parent tuple; it is <code class="literal">(Datum) 0</code> at the root level or if the
<code class="function">inner_consistent</code> function did not provide a value at the
parent level. <code class="structfield">reconstructedValue</code> is always of
<code class="structname">spgConfigOut</code>.<code class="structfield">leafType</code> type.
<code class="structfield">traversalValue</code> is a pointer to any traverse data
passed down from the previous call of <code class="function">inner_consistent</code>
on the parent index tuple, or NULL at the root level.
<code class="structfield">level</code> is the current leaf tuple's level, starting at
zero for the root level.
<code class="structfield">returnData</code> is <code class="literal">true</code> if reconstructed data is
required for this query; this will only be so if the
<code class="function">config</code> function asserted <code class="structfield">canReturnData</code>.
<code class="structfield">leafDatum</code> is the key value of
<code class="structname">spgConfigOut</code>.<code class="structfield">leafType</code>
stored in the current leaf tuple.
</p><p>
The function must return <code class="literal">true</code> if the leaf tuple matches the
query, or <code class="literal">false</code> if not. In the <code class="literal">true</code> case,
if <code class="structfield">returnData</code> is <code class="literal">true</code> then
<code class="structfield">leafValue</code> must be set to the value of
<code class="structname">spgConfigIn</code>.<code class="structfield">attType</code> type
originally supplied to be indexed for this leaf tuple. Also,
<code class="structfield">recheck</code> may be set to <code class="literal">true</code> if the match
is uncertain and so the operator(s) must be re-applied to the actual
heap tuple to verify the match.
If ordered search is performed, set <code class="structfield">distances</code>
to an array of distance values according to <code class="structfield">orderbys</code>
array. Leave it NULL otherwise. If at least one of returned distances
is not exact, set <code class="structfield">recheckDistances</code> to true.
In this case, the executor will calculate the exact distances after
fetching the tuple from the heap, and will reorder the tuples if needed.
</p></dd></dl></div><p>
The optional user-defined method are:
</p><div class="variablelist"><dl class="variablelist"><dt><span class="term"><code class="function">Datum compress(Datum in)</code></span></dt><dd><p>
Converts the data item into a format suitable for physical storage in
a leaf tuple of index page. It accepts
<code class="structname">spgConfigIn</code>.<code class="structfield">attType</code>
value and returns
<code class="structname">spgConfigOut</code>.<code class="structfield">leafType</code>
value. Output value should not be toasted.
</p></dd><dt><span class="term"><code class="function">options</code></span></dt><dd><p>
Defines a set of user-visible parameters that control operator class
behavior.
</p><p>
The <acronym class="acronym">SQL</acronym> declaration of the function must look like this:
</p><pre class="programlisting">
CREATE OR REPLACE FUNCTION my_options(internal)
RETURNS void
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;
</pre><p>
</p><p>
The function is passed a pointer to a <em class="replaceable"><code>local_relopts</code></em>
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>
Since the representation of the key in <acronym class="acronym">SP-GiST</acronym> is
flexible, it may depend on user-specified parameters.
</p></dd></dl></div><p>
All the SP-GiST support methods are normally called in a short-lived
memory context; that is, <code class="varname">CurrentMemoryContext</code> will be reset
after processing of each tuple. It is therefore not very important to
worry about pfree'ing everything you palloc. (The <code class="function">config</code>
method is an exception: it should try to avoid leaking memory. But
usually the <code class="function">config</code> method need do nothing but assign
constants into the passed parameter struct.)
</p><p>
If the indexed column is of a collatable data type, the index collation
will be passed to all the support methods, using the standard
<code class="function">PG_GET_COLLATION()</code> mechanism.
</p></div><div xmlns="http://www.w3.org/TR/xhtml1/transitional" class="navfooter"><hr></hr><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="spgist-builtin-opclasses.html" title="65.2. Built-in Operator Classes">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="spgist.html" title="Chapter 65. SP-GiST Indexes">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="spgist-implementation.html" title="65.4. Implementation">Next</a></td></tr><tr><td width="40%" align="left" valign="top">65.2. Built-in Operator Classes </td><td width="20%" align="center"><a accesskey="h" href="index.html" title="PostgreSQL 13.4 Documentation">Home</a></td><td width="40%" align="right" valign="top"> 65.4. Implementation</td></tr></table></div></body></html>
|
