| 1 |
<!-- doc/src/sgml/gist.sgml --> |
| 2 |
|
| 3 |
<sect1 id="gist"> |
| 4 |
<title>GiST Indexes</title> |
| 5 |
|
| 6 |
<indexterm> |
| 7 |
<primary>index</primary> |
| 8 |
<secondary>GiST</secondary> |
| 9 |
</indexterm> |
| 10 |
|
| 11 |
<sect2 id="gist-intro"> |
| 12 |
<title>Introduction</title> |
| 13 |
|
| 14 |
<para> |
| 15 |
<acronym>GiST</acronym> stands for Generalized Search Tree. It is a |
| 16 |
balanced, tree-structured access method, that acts as a base template in |
| 17 |
which to implement arbitrary indexing schemes. B-trees, R-trees and many |
| 18 |
other indexing schemes can be implemented in <acronym>GiST</acronym>. |
| 19 |
</para> |
| 20 |
|
| 21 |
<para> |
| 22 |
One advantage of <acronym>GiST</acronym> is that it allows the development |
| 23 |
of custom data types with the appropriate access methods, by |
| 24 |
an expert in the domain of the data type, rather than a database expert. |
| 25 |
</para> |
| 26 |
|
| 27 |
<para> |
| 28 |
Some of the information here is derived from the University of California |
| 29 |
at Berkeley's GiST Indexing Project |
| 30 |
<ulink url="http://gist.cs.berkeley.edu/">web site</ulink> and |
| 31 |
Marcel Kornacker's thesis, |
| 32 |
<ulink url="http://www.sai.msu.su/~megera/postgres/gist/papers/concurrency/access-methods-for-next-generation.pdf.gz"> |
| 33 |
Access Methods for Next-Generation Database Systems</ulink>. |
| 34 |
The <acronym>GiST</acronym> |
| 35 |
implementation in <productname>PostgreSQL</productname> is primarily |
| 36 |
maintained by Teodor Sigaev and Oleg Bartunov, and there is more |
| 37 |
information on their |
| 38 |
<ulink url="http://www.sai.msu.su/~megera/postgres/gist/">web site</ulink>. |
| 39 |
</para> |
| 40 |
|
| 41 |
</sect2> |
| 42 |
|
| 43 |
<sect2 id="gist-builtin-opclasses"> |
| 44 |
<title>Built-in Operator Classes</title> |
| 45 |
|
| 46 |
<para> |
| 47 |
The core <productname>PostgreSQL</productname> distribution |
| 48 |
includes the <acronym>GiST</acronym> operator classes shown in |
| 49 |
<xref linkend="gist-builtin-opclasses-table"/>. |
| 50 |
(Some of the optional modules described in <xref linkend="contrib"/> |
| 51 |
provide additional <acronym>GiST</acronym> operator classes.) |
| 52 |
</para> |
| 53 |
|
| 54 |
<table id="gist-builtin-opclasses-table"> |
| 55 |
<title>Built-in <acronym>GiST</acronym> Operator Classes</title> |
| 56 |
<tgroup cols="3"> |
| 57 |
<colspec colname="col1" colwidth="2*"/> |
| 58 |
<colspec colname="col2" colwidth="3*"/> |
| 59 |
<colspec colname="col3" colwidth="2*"/> |
| 60 |
<thead> |
| 61 |
<row> |
| 62 |
<entry>Name</entry> |
| 63 |
<entry>Indexable Operators</entry> |
| 64 |
<entry>Ordering Operators</entry> |
| 65 |
</row> |
| 66 |
</thead> |
| 67 |
<tbody> |
| 68 |
<row> |
| 69 |
<entry valign="middle" morerows="11"><literal>box_ops</literal></entry> |
| 70 |
<entry><literal><< (box, box)</literal></entry> |
| 71 |
<entry valign="middle" morerows="11"><literal><-> (box, point)</literal></entry> |
| 72 |
</row> |
| 73 |
<row><entry><literal>&< (box, box)</literal></entry></row> |
| 74 |
<row><entry><literal>&& (box, box)</literal></entry></row> |
| 75 |
<row><entry><literal>&> (box, box)</literal></entry></row> |
| 76 |
<row><entry><literal>>> (box, box)</literal></entry></row> |
| 77 |
<row><entry><literal>~= (box, box)</literal></entry></row> |
| 78 |
<row><entry><literal>@> (box, box)</literal></entry></row> |
| 79 |
<row><entry><literal><@ (box, box)</literal></entry></row> |
| 80 |
<row><entry><literal>&<| (box, box)</literal></entry></row> |
| 81 |
<row><entry><literal><<| (box, box)</literal></entry></row> |
| 82 |
<row><entry><literal>|>> (box, box)</literal></entry></row> |
| 83 |
<row><entry><literal>|&> (box, box)</literal></entry></row> |
| 84 |
|
| 85 |
<row> |
| 86 |
<entry valign="middle" morerows="11"><literal>circle_ops</literal></entry> |
| 87 |
<entry><literal><< (circle, circle)</literal></entry> |
| 88 |
<entry valign="middle" morerows="11"><literal><-> (circle, point)</literal></entry> |
| 89 |
</row> |
| 90 |
<row><entry><literal>&< (circle, circle)</literal></entry></row> |
| 91 |
<row><entry><literal>&> (circle, circle)</literal></entry></row> |
| 92 |
<row><entry><literal>>> (circle, circle)</literal></entry></row> |
| 93 |
<row><entry><literal><@ (circle, circle)</literal></entry></row> |
| 94 |
<row><entry><literal>@> (circle, circle)</literal></entry></row> |
| 95 |
<row><entry><literal>~= (circle, circle)</literal></entry></row> |
| 96 |
<row><entry><literal>&& (circle, circle)</literal></entry></row> |
| 97 |
<row><entry><literal>|>> (circle, circle)</literal></entry></row> |
| 98 |
<row><entry><literal><<| (circle, circle)</literal></entry></row> |
| 99 |
<row><entry><literal>&<| (circle, circle)</literal></entry></row> |
| 100 |
<row><entry><literal>|&> (circle, circle)</literal></entry></row> |
| 101 |
|
| 102 |
<row> |
| 103 |
<entry valign="middle" morerows="10"><literal>inet_ops</literal></entry> |
| 104 |
<entry><literal><< (inet, inet)</literal></entry> |
| 105 |
<entry valign="middle" morerows="10"></entry> |
| 106 |
</row> |
| 107 |
<row><entry><literal><<= (inet, inet)</literal></entry></row> |
| 108 |
<row><entry><literal>>> (inet, inet)</literal></entry></row> |
| 109 |
<row><entry><literal>>>= (inet, inet)</literal></entry></row> |
| 110 |
<row><entry><literal>= (inet, inet)</literal></entry></row> |
| 111 |
<row><entry><literal><> (inet, inet)</literal></entry></row> |
| 112 |
<row><entry><literal>< (inet, inet)</literal></entry></row> |
| 113 |
<row><entry><literal><= (inet, inet)</literal></entry></row> |
| 114 |
<row><entry><literal>> (inet, inet)</literal></entry></row> |
| 115 |
<row><entry><literal>>= (inet, inet)</literal></entry></row> |
| 116 |
<row><entry><literal>&& (inet, inet)</literal></entry></row> |
| 117 |
|
| 118 |
<row> |
| 119 |
<entry valign="middle" morerows="17"><literal>multirange_ops</literal></entry> |
| 120 |
<entry><literal>= (anymultirange, anymultirange)</literal></entry> |
| 121 |
<entry valign="middle" morerows="17"></entry> |
| 122 |
</row> |
| 123 |
<row><entry><literal>&& (anymultirange, anymultirange)</literal></entry></row> |
| 124 |
<row><entry><literal>&& (anymultirange, anyrange)</literal></entry></row> |
| 125 |
<row><entry><literal>@> (anymultirange, anyelement)</literal></entry></row> |
| 126 |
<row><entry><literal>@> (anymultirange, anymultirange)</literal></entry></row> |
| 127 |
<row><entry><literal>@> (anymultirange, anyrange)</literal></entry></row> |
| 128 |
<row><entry><literal><@ (anymultirange, anymultirange)</literal></entry></row> |
| 129 |
<row><entry><literal><@ (anymultirange, anyrange)</literal></entry></row> |
| 130 |
<row><entry><literal><< (anymultirange, anymultirange)</literal></entry></row> |
| 131 |
<row><entry><literal><< (anymultirange, anyrange)</literal></entry></row> |
| 132 |
<row><entry><literal>>> (anymultirange, anymultirange)</literal></entry></row> |
| 133 |
<row><entry><literal>>> (anymultirange, anyrange)</literal></entry></row> |
| 134 |
<row><entry><literal>&< (anymultirange, anymultirange)</literal></entry></row> |
| 135 |
<row><entry><literal>&< (anymultirange, anyrange)</literal></entry></row> |
| 136 |
<row><entry><literal>&> (anymultirange, anymultirange)</literal></entry></row> |
| 137 |
<row><entry><literal>&> (anymultirange, anyrange)</literal></entry></row> |
| 138 |
<row><entry><literal>-|- (anymultirange, anymultirange)</literal></entry></row> |
| 139 |
<row><entry><literal>-|- (anymultirange, anyrange)</literal></entry></row> |
| 140 |
|
| 141 |
<row> |
| 142 |
<entry valign="middle" morerows="7"><literal>point_ops</literal></entry> |
| 143 |
<entry><literal>|>> (point, point)</literal></entry> |
| 144 |
<entry valign="middle" morerows="7"><literal><-> (point, point)</literal></entry> |
| 145 |
</row> |
| 146 |
<row><entry><literal><< (point, point)</literal></entry></row> |
| 147 |
<row><entry><literal>>> (point, point)</literal></entry></row> |
| 148 |
<row><entry><literal><<| (point, point)</literal></entry></row> |
| 149 |
<row><entry><literal>~= (point, point)</literal></entry></row> |
| 150 |
<row><entry><literal><@ (point, box)</literal></entry></row> |
| 151 |
<row><entry><literal><@ (point, polygon)</literal></entry></row> |
| 152 |
<row><entry><literal><@ (point, circle)</literal></entry></row> |
| 153 |
|
| 154 |
<row> |
| 155 |
<entry valign="middle" morerows="11"><literal>poly_ops</literal></entry> |
| 156 |
<entry><literal><< (polygon, polygon)</literal></entry> |
| 157 |
<entry valign="middle" morerows="11"><literal><-> (polygon, point)</literal></entry> |
| 158 |
</row> |
| 159 |
<row><entry><literal>&< (polygon, polygon)</literal></entry></row> |
| 160 |
<row><entry><literal>&> (polygon, polygon)</literal></entry></row> |
| 161 |
<row><entry><literal>>> (polygon, polygon)</literal></entry></row> |
| 162 |
<row><entry><literal><@ (polygon, polygon)</literal></entry></row> |
| 163 |
<row><entry><literal>@> (polygon, polygon)</literal></entry></row> |
| 164 |
<row><entry><literal>~= (polygon, polygon)</literal></entry></row> |
| 165 |
<row><entry><literal>&& (polygon, polygon)</literal></entry></row> |
| 166 |
<row><entry><literal><<| (polygon, polygon)</literal></entry></row> |
| 167 |
<row><entry><literal>&<| (polygon, polygon)</literal></entry></row> |
| 168 |
<row><entry><literal>|&> (polygon, polygon)</literal></entry></row> |
| 169 |
<row><entry><literal>|>> (polygon, polygon)</literal></entry></row> |
| 170 |
|
| 171 |
<row> |
| 172 |
<entry valign="middle" morerows="17"><literal>range_ops</literal></entry> |
| 173 |
<entry><literal>= (anyrange, anyrange)</literal></entry> |
| 174 |
<entry valign="middle" morerows="17"></entry> |
| 175 |
</row> |
| 176 |
<row><entry><literal>&& (anyrange, anyrange)</literal></entry></row> |
| 177 |
<row><entry><literal>&& (anyrange, anymultirange)</literal></entry></row> |
| 178 |
<row><entry><literal>@> (anyrange, anyelement)</literal></entry></row> |
| 179 |
<row><entry><literal>@> (anyrange, anyrange)</literal></entry></row> |
| 180 |
<row><entry><literal>@> (anyrange, anymultirange)</literal></entry></row> |
| 181 |
<row><entry><literal><@ (anyrange, anyrange)</literal></entry></row> |
| 182 |
<row><entry><literal><@ (anyrange, anymultirange)</literal></entry></row> |
| 183 |
<row><entry><literal><< (anyrange, anyrange)</literal></entry></row> |
| 184 |
<row><entry><literal><< (anyrange, anymultirange)</literal></entry></row> |
| 185 |
<row><entry><literal>>> (anyrange, anyrange)</literal></entry></row> |
| 186 |
<row><entry><literal>>> (anyrange, anymultirange)</literal></entry></row> |
| 187 |
<row><entry><literal>&< (anyrange, anyrange)</literal></entry></row> |
| 188 |
<row><entry><literal>&< (anyrange, anymultirange)</literal></entry></row> |
| 189 |
<row><entry><literal>&> (anyrange, anyrange)</literal></entry></row> |
| 190 |
<row><entry><literal>&> (anyrange, anymultirange)</literal></entry></row> |
| 191 |
<row><entry><literal>-|- (anyrange, anyrange)</literal></entry></row> |
| 192 |
<row><entry><literal>-|- (anyrange, anymultirange)</literal></entry></row> |
| 193 |
|
| 194 |
<row> |
| 195 |
<entry valign="middle" morerows="1"><literal>tsquery_ops</literal></entry> |
| 196 |
<entry><literal><@ (tsquery, tsquery)</literal></entry> |
| 197 |
<entry valign="middle" morerows="1"></entry> |
| 198 |
</row> |
| 199 |
<row><entry><literal>@> (tsquery, tsquery)</literal></entry></row> |
| 200 |
<row> |
| 201 |
<entry valign="middle"><literal>tsvector_ops</literal></entry> |
| 202 |
<entry><literal>@@ (tsvector, tsquery)</literal></entry> |
| 203 |
<entry></entry> |
| 204 |
</row> |
| 205 |
</tbody> |
| 206 |
</tgroup> |
| 207 |
</table> |
| 208 |
|
| 209 |
<para> |
| 210 |
For historical reasons, the <literal>inet_ops</literal> operator class is |
| 211 |
not the default class for types <type>inet</type> and <type>cidr</type>. |
| 212 |
To use it, mention the class name in <command>CREATE INDEX</command>, |
| 213 |
for example |
| 214 |
<programlisting> |
| 215 |
CREATE INDEX ON my_table USING GIST (my_inet_column inet_ops); |
| 216 |
</programlisting> |
| 217 |
</para> |
| 218 |
|
| 219 |
</sect2> |
| 220 |
|
| 221 |
<sect2 id="gist-extensibility"> |
| 222 |
<title>Extensibility</title> |
| 223 |
|
| 224 |
<para> |
| 225 |
Traditionally, implementing a new index access method meant a lot of |
| 226 |
difficult work. It was necessary to understand the inner workings of the |
| 227 |
database, such as the lock manager and Write-Ahead Log. The |
| 228 |
<acronym>GiST</acronym> interface has a high level of abstraction, |
| 229 |
requiring the access method implementer only to implement the semantics of |
| 230 |
the data type being accessed. The <acronym>GiST</acronym> layer itself |
| 231 |
takes care of concurrency, logging and searching the tree structure. |
| 232 |
</para> |
| 233 |
|
| 234 |
<para> |
| 235 |
This extensibility should not be confused with the extensibility of the |
| 236 |
other standard search trees in terms of the data they can handle. For |
| 237 |
example, <productname>PostgreSQL</productname> supports extensible B-trees |
| 238 |
and hash indexes. That means that you can use |
| 239 |
<productname>PostgreSQL</productname> to build a B-tree or hash over any |
| 240 |
data type you want. But B-trees only support range predicates |
| 241 |
(<literal><</literal>, <literal>=</literal>, <literal>></literal>), |
| 242 |
and hash indexes only support equality queries. |
| 243 |
</para> |
| 244 |
|
| 245 |
<para> |
| 246 |
So if you index, say, an image collection with a |
| 247 |
<productname>PostgreSQL</productname> B-tree, you can only issue queries |
| 248 |
such as <quote>is imagex equal to imagey</quote>, <quote>is imagex less |
| 249 |
than imagey</quote> and <quote>is imagex greater than imagey</quote>. |
| 250 |
Depending on how you define <quote>equals</quote>, <quote>less than</quote> |
| 251 |
and <quote>greater than</quote> in this context, this could be useful. |
| 252 |
However, by using a <acronym>GiST</acronym> based index, you could create |
| 253 |
ways to ask domain-specific questions, perhaps <quote>find all images of |
| 254 |
horses</quote> or <quote>find all over-exposed images</quote>. |
| 255 |
</para> |
| 256 |
|
| 257 |
<para> |
| 258 |
All it takes to get a <acronym>GiST</acronym> access method up and running |
| 259 |
is to implement several user-defined methods, which define the behavior of |
| 260 |
keys in the tree. Of course these methods have to be pretty fancy to |
| 261 |
support fancy queries, but for all the standard queries (B-trees, |
| 262 |
R-trees, etc.) they're relatively straightforward. In short, |
| 263 |
<acronym>GiST</acronym> combines extensibility along with generality, code |
| 264 |
reuse, and a clean interface. |
| 265 |
</para> |
| 266 |
|
| 267 |
<para> |
| 268 |
There are five methods that an index operator class for |
| 269 |
<acronym>GiST</acronym> must provide, and seven that are optional. |
| 270 |
Correctness of the index is ensured |
| 271 |
by proper implementation of the <function>same</function>, <function>consistent</function> |
| 272 |
and <function>union</function> methods, while efficiency (size and speed) of the |
| 273 |
index will depend on the <function>penalty</function> and <function>picksplit</function> |
| 274 |
methods. |
| 275 |
Two optional methods are <function>compress</function> and |
| 276 |
<function>decompress</function>, which allow an index to have internal tree data of |
| 277 |
a different type than the data it indexes. The leaves are to be of the |
| 278 |
indexed data type, while the other tree nodes can be of any C struct (but |
| 279 |
you still have to follow <productname>PostgreSQL</productname> data type rules here, |
| 280 |
see about <literal>varlena</literal> for variable sized data). If the tree's |
| 281 |
internal data type exists at the SQL level, the <literal>STORAGE</literal> option |
| 282 |
of the <command>CREATE OPERATOR CLASS</command> command can be used. |
| 283 |
The optional eighth method is <function>distance</function>, which is needed |
| 284 |
if the operator class wishes to support ordered scans (nearest-neighbor |
| 285 |
searches). The optional ninth method <function>fetch</function> is needed if the |
| 286 |
operator class wishes to support index-only scans, except when the |
| 287 |
<function>compress</function> method is omitted. The optional tenth method |
| 288 |
<function>options</function> is needed if the operator class has |
| 289 |
user-specified parameters. |
| 290 |
The optional eleventh method <function>sortsupport</function> is used to |
| 291 |
speed up building a <acronym>GiST</acronym> index. |
| 292 |
The optional twelfth method <function>stratnum</function> is used to |
| 293 |
translate compare types (from |
| 294 |
<filename>src/include/access/cmptype.h</filename>) into strategy numbers |
| 295 |
used by the operator class. This lets the core code look up operators for |
| 296 |
temporal constraint indexes. |
| 297 |
</para> |
| 298 |
|
| 299 |
<variablelist> |
| 300 |
<varlistentry> |
| 301 |
<term><function>consistent</function></term> |
| 302 |
<listitem> |
| 303 |
<para> |
| 304 |
Given an index entry <literal>p</literal> and a query value <literal>q</literal>, |
| 305 |
this function determines whether the index entry is |
| 306 |
<quote>consistent</quote> with the query; that is, could the predicate |
| 307 |
<quote><replaceable>indexed_column</replaceable> |
| 308 |
<replaceable>indexable_operator</replaceable> <literal>q</literal></quote> be true for |
| 309 |
any row represented by the index entry? For a leaf index entry this is |
| 310 |
equivalent to testing the indexable condition, while for an internal |
| 311 |
tree node this determines whether it is necessary to scan the subtree |
| 312 |
of the index represented by the tree node. When the result is |
| 313 |
<literal>true</literal>, a <literal>recheck</literal> flag must also be returned. |
| 314 |
This indicates whether the predicate is certainly true or only possibly |
| 315 |
true. If <literal>recheck</literal> = <literal>false</literal> then the index has |
| 316 |
tested the predicate condition exactly, whereas if <literal>recheck</literal> |
| 317 |
= <literal>true</literal> the row is only a candidate match. In that case the |
| 318 |
system will automatically evaluate the |
| 319 |
<replaceable>indexable_operator</replaceable> against the actual row value to see |
| 320 |
if it is really a match. This convention allows |
| 321 |
<acronym>GiST</acronym> to support both lossless and lossy index |
| 322 |
structures. |
| 323 |
</para> |
| 324 |
|
| 325 |
<para> |
| 326 |
The <acronym>SQL</acronym> declaration of the function must look like this: |
| 327 |
|
| 328 |
<programlisting> |
| 329 |
CREATE OR REPLACE FUNCTION my_consistent(internal, data_type, smallint, oid, internal) |
| 330 |
RETURNS bool |
| 331 |
AS 'MODULE_PATHNAME' |
| 332 |
LANGUAGE C STRICT; |
| 333 |
</programlisting> |
| 334 |
|
| 335 |
And the matching code in the C module could then follow this skeleton: |
| 336 |
|
| 337 |
<programlisting> |
| 338 |
PG_FUNCTION_INFO_V1(my_consistent); |
| 339 |
|
| 340 |
Datum |
| 341 |
my_consistent(PG_FUNCTION_ARGS) |
| 342 |
{ |
| 343 |
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); |
| 344 |
data_type *query = PG_GETARG_DATA_TYPE_P(1); |
| 345 |
StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2); |
| 346 |
/* Oid subtype = PG_GETARG_OID(3); */ |
| 347 |
bool *recheck = (bool *) PG_GETARG_POINTER(4); |
| 348 |
data_type *key = DatumGetDataType(entry->key); |
| 349 |
bool retval; |
| 350 |
|
| 351 |
/* |
| 352 |
* determine return value as a function of strategy, key and query. |
| 353 |
* |
| 354 |
* Use GIST_LEAF(entry) to know where you're called in the index tree, |
| 355 |
* which comes handy when supporting the = operator for example (you could |
| 356 |
* check for non empty union() in non-leaf nodes and equality in leaf |
| 357 |
* nodes). |
| 358 |
*/ |
| 359 |
|
| 360 |
*recheck = true; /* or false if check is exact */ |
| 361 |
|
| 362 |
PG_RETURN_BOOL(retval); |
| 363 |
} |
| 364 |
</programlisting> |
| 365 |
|
| 366 |
Here, <varname>key</varname> is an element in the index and <varname>query</varname> |
| 367 |
the value being looked up in the index. The <literal>StrategyNumber</literal> |
| 368 |
parameter indicates which operator of your operator class is being |
| 369 |
applied — it matches one of the operator numbers in the |
| 370 |
<command>CREATE OPERATOR CLASS</command> command. |
| 371 |
</para> |
| 372 |
|
| 373 |
<para> |
| 374 |
Depending on which operators you have included in the class, the data |
| 375 |
type of <varname>query</varname> could vary with the operator, since it will |
| 376 |
be whatever type is on the right-hand side of the operator, which might |
| 377 |
be different from the indexed data type appearing on the left-hand side. |
| 378 |
(The above code skeleton assumes that only one type is possible; if |
| 379 |
not, fetching the <varname>query</varname> argument value would have to depend |
| 380 |
on the operator.) It is recommended that the SQL declaration of |
| 381 |
the <function>consistent</function> function use the opclass's indexed data |
| 382 |
type for the <varname>query</varname> argument, even though the actual type |
| 383 |
might be something else depending on the operator. |
| 384 |
</para> |
| 385 |
|
| 386 |
</listitem> |
| 387 |
</varlistentry> |
| 388 |
|
| 389 |
<varlistentry> |
| 390 |
<term><function>union</function></term> |
| 391 |
<listitem> |
| 392 |
<para> |
| 393 |
This method consolidates information in the tree. Given a set of |
| 394 |
entries, this function generates a new index entry that represents |
| 395 |
all the given entries. |
| 396 |
</para> |
| 397 |
|
| 398 |
<para> |
| 399 |
The <acronym>SQL</acronym> declaration of the function must look like this: |
| 400 |
|
| 401 |
<programlisting> |
| 402 |
CREATE OR REPLACE FUNCTION my_union(internal, internal) |
| 403 |
RETURNS storage_type |
| 404 |
AS 'MODULE_PATHNAME' |
| 405 |
LANGUAGE C STRICT; |
| 406 |
</programlisting> |
| 407 |
|
| 408 |
And the matching code in the C module could then follow this skeleton: |
| 409 |
|
| 410 |
<programlisting> |
| 411 |
PG_FUNCTION_INFO_V1(my_union); |
| 412 |
|
| 413 |
Datum |
| 414 |
my_union(PG_FUNCTION_ARGS) |
| 415 |
{ |
| 416 |
GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0); |
| 417 |
GISTENTRY *ent = entryvec->vector; |
| 418 |
data_type *out, |
| 419 |
*tmp, |
| 420 |
*old; |
| 421 |
int numranges, |
| 422 |
i = 0; |
| 423 |
|
| 424 |
numranges = entryvec->n; |
| 425 |
tmp = DatumGetDataType(ent[0].key); |
| 426 |
out = tmp; |
| 427 |
|
| 428 |
if (numranges == 1) |
| 429 |
{ |
| 430 |
out = data_type_deep_copy(tmp); |
| 431 |
|
| 432 |
PG_RETURN_DATA_TYPE_P(out); |
| 433 |
} |
| 434 |
|
| 435 |
for (i = 1; i < numranges; i++) |
| 436 |
{ |
| 437 |
old = out; |
| 438 |
tmp = DatumGetDataType(ent[i].key); |
| 439 |
out = my_union_implementation(out, tmp); |
| 440 |
} |
| 441 |
|
| 442 |
PG_RETURN_DATA_TYPE_P(out); |
| 443 |
} |
| 444 |
</programlisting> |
| 445 |
</para> |
| 446 |
|
| 447 |
<para> |
| 448 |
As you can see, in this skeleton we're dealing with a data type |
| 449 |
where <literal>union(X, Y, Z) = union(union(X, Y), Z)</literal>. It's easy |
| 450 |
enough to support data types where this is not the case, by |
| 451 |
implementing the proper union algorithm in this |
| 452 |
<acronym>GiST</acronym> support method. |
| 453 |
</para> |
| 454 |
|
| 455 |
<para> |
| 456 |
The result of the <function>union</function> function must be a value of the |
| 457 |
index's storage type, whatever that is (it might or might not be |
| 458 |
different from the indexed column's type). The <function>union</function> |
| 459 |
function should return a pointer to newly <function>palloc()</function>ed |
| 460 |
memory. You can't just return the input value as-is, even if there is |
| 461 |
no type change. |
| 462 |
</para> |
| 463 |
|
| 464 |
<para> |
| 465 |
As shown above, the <function>union</function> function's |
| 466 |
first <type>internal</type> argument is actually |
| 467 |
a <structname>GistEntryVector</structname> pointer. The second argument is a |
| 468 |
pointer to an integer variable, which can be ignored. (It used to be |
| 469 |
required that the <function>union</function> function store the size of its |
| 470 |
result value into that variable, but this is no longer necessary.) |
| 471 |
</para> |
| 472 |
</listitem> |
| 473 |
</varlistentry> |
| 474 |
|
| 475 |
<varlistentry> |
| 476 |
<term><function>compress</function></term> |
| 477 |
<listitem> |
| 478 |
<para> |
| 479 |
Converts a data item into a format suitable for physical storage in |
| 480 |
an index page. |
| 481 |
If the <function>compress</function> method is omitted, data items are stored |
| 482 |
in the index without modification. |
| 483 |
</para> |
| 484 |
|
| 485 |
<para> |
| 486 |
The <acronym>SQL</acronym> declaration of the function must look like this: |
| 487 |
|
| 488 |
<programlisting> |
| 489 |
CREATE OR REPLACE FUNCTION my_compress(internal) |
| 490 |
RETURNS internal |
| 491 |
AS 'MODULE_PATHNAME' |
| 492 |
LANGUAGE C STRICT; |
| 493 |
</programlisting> |
| 494 |
|
| 495 |
And the matching code in the C module could then follow this skeleton: |
| 496 |
|
| 497 |
<programlisting> |
| 498 |
PG_FUNCTION_INFO_V1(my_compress); |
| 499 |
|
| 500 |
Datum |
| 501 |
my_compress(PG_FUNCTION_ARGS) |
| 502 |
{ |
| 503 |
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); |
| 504 |
GISTENTRY *retval; |
| 505 |
|
| 506 |
if (entry->leafkey) |
| 507 |
{ |
| 508 |
/* replace entry->key with a compressed version */ |
| 509 |
compressed_data_type *compressed_data = palloc(sizeof(compressed_data_type)); |
| 510 |
|
| 511 |
/* fill *compressed_data from entry->key ... */ |
| 512 |
|
| 513 |
retval = palloc(sizeof(GISTENTRY)); |
| 514 |
gistentryinit(*retval, PointerGetDatum(compressed_data), |
| 515 |
entry->rel, entry->page, entry->offset, FALSE); |
| 516 |
} |
| 517 |
else |
| 518 |
{ |
| 519 |
/* typically we needn't do anything with non-leaf entries */ |
| 520 |
retval = entry; |
| 521 |
} |
| 522 |
|
| 523 |
PG_RETURN_POINTER(retval); |
| 524 |
} |
| 525 |
</programlisting> |
| 526 |
</para> |
| 527 |
|
| 528 |
<para> |
| 529 |
You have to adapt <replaceable>compressed_data_type</replaceable> to the specific |
| 530 |
type you're converting to in order to compress your leaf nodes, of |
| 531 |
course. |
| 532 |
</para> |
| 533 |
</listitem> |
| 534 |
</varlistentry> |
| 535 |
|
| 536 |
<varlistentry> |
| 537 |
<term><function>decompress</function></term> |
| 538 |
<listitem> |
| 539 |
<para> |
| 540 |
Converts the stored representation of a data item into a format that |
| 541 |
can be manipulated by the other GiST methods in the operator class. |
| 542 |
If the <function>decompress</function> method is omitted, it is assumed that |
| 543 |
the other GiST methods can work directly on the stored data format. |
| 544 |
(<function>decompress</function> is not necessarily the reverse of |
| 545 |
the <function>compress</function> method; in particular, |
| 546 |
if <function>compress</function> is lossy then it's impossible |
| 547 |
for <function>decompress</function> to exactly reconstruct the original |
| 548 |
data. <function>decompress</function> is not necessarily equivalent |
| 549 |
to <function>fetch</function>, either, since the other GiST methods might not |
| 550 |
require full reconstruction of the data.) |
| 551 |
</para> |
| 552 |
|
| 553 |
<para> |
| 554 |
The <acronym>SQL</acronym> declaration of the function must look like this: |
| 555 |
|
| 556 |
<programlisting> |
| 557 |
CREATE OR REPLACE FUNCTION my_decompress(internal) |
| 558 |
RETURNS internal |
| 559 |
AS 'MODULE_PATHNAME' |
| 560 |
LANGUAGE C STRICT; |
| 561 |
</programlisting> |
| 562 |
|
| 563 |
And the matching code in the C module could then follow this skeleton: |
| 564 |
|
| 565 |
<programlisting> |
| 566 |
PG_FUNCTION_INFO_V1(my_decompress); |
| 567 |
|
| 568 |
Datum |
| 569 |
my_decompress(PG_FUNCTION_ARGS) |
| 570 |
{ |
| 571 |
PG_RETURN_POINTER(PG_GETARG_POINTER(0)); |
| 572 |
} |
| 573 |
</programlisting> |
| 574 |
|
| 575 |
The above skeleton is suitable for the case where no decompression |
| 576 |
is needed. (But, of course, omitting the method altogether is even |
| 577 |
easier, and is recommended in such cases.) |
| 578 |
</para> |
| 579 |
</listitem> |
| 580 |
</varlistentry> |
| 581 |
|
| 582 |
<varlistentry> |
| 583 |
<term><function>penalty</function></term> |
| 584 |
<listitem> |
| 585 |
<para> |
| 586 |
Returns a value indicating the <quote>cost</quote> of inserting the new |
| 587 |
entry into a particular branch of the tree. Items will be inserted |
| 588 |
down the path of least <function>penalty</function> in the tree. |
| 589 |
Values returned by <function>penalty</function> should be non-negative. |
| 590 |
If a negative value is returned, it will be treated as zero. |
| 591 |
</para> |
| 592 |
|
| 593 |
<para> |
| 594 |
The <acronym>SQL</acronym> declaration of the function must look like this: |
| 595 |
|
| 596 |
<programlisting> |
| 597 |
CREATE OR REPLACE FUNCTION my_penalty(internal, internal, internal) |
| 598 |
RETURNS internal |
| 599 |
AS 'MODULE_PATHNAME' |
| 600 |
LANGUAGE C STRICT; -- in some cases penalty functions need not be strict |
| 601 |
</programlisting> |
| 602 |
|
| 603 |
And the matching code in the C module could then follow this skeleton: |
| 604 |
|
| 605 |
<programlisting> |
| 606 |
PG_FUNCTION_INFO_V1(my_penalty); |
| 607 |
|
| 608 |
Datum |
| 609 |
my_penalty(PG_FUNCTION_ARGS) |
| 610 |
{ |
| 611 |
GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0); |
| 612 |
GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1); |
| 613 |
float *penalty = (float *) PG_GETARG_POINTER(2); |
| 614 |
data_type *orig = DatumGetDataType(origentry->key); |
| 615 |
data_type *new = DatumGetDataType(newentry->key); |
| 616 |
|
| 617 |
*penalty = my_penalty_implementation(orig, new); |
| 618 |
PG_RETURN_POINTER(penalty); |
| 619 |
} |
| 620 |
</programlisting> |
| 621 |
|
| 622 |
For historical reasons, the <function>penalty</function> function doesn't |
| 623 |
just return a <type>float</type> result; instead it has to store the value |
| 624 |
at the location indicated by the third argument. The return |
| 625 |
value per se is ignored, though it's conventional to pass back the |
| 626 |
address of that argument. |
| 627 |
</para> |
| 628 |
|
| 629 |
<para> |
| 630 |
The <function>penalty</function> function is crucial to good performance of |
| 631 |
the index. It'll get used at insertion time to determine which branch |
| 632 |
to follow when choosing where to add the new entry in the tree. At |
| 633 |
query time, the more balanced the index, the quicker the lookup. |
| 634 |
</para> |
| 635 |
</listitem> |
| 636 |
</varlistentry> |
| 637 |
|
| 638 |
<varlistentry> |
| 639 |
<term><function>picksplit</function></term> |
| 640 |
<listitem> |
| 641 |
<para> |
| 642 |
When an index page split is necessary, this function decides which |
| 643 |
entries on the page are to stay on the old page, and which are to move |
| 644 |
to the new page. |
| 645 |
</para> |
| 646 |
|
| 647 |
<para> |
| 648 |
The <acronym>SQL</acronym> declaration of the function must look like this: |
| 649 |
|
| 650 |
<programlisting> |
| 651 |
CREATE OR REPLACE FUNCTION my_picksplit(internal, internal) |
| 652 |
RETURNS internal |
| 653 |
AS 'MODULE_PATHNAME' |
| 654 |
LANGUAGE C STRICT; |
| 655 |
</programlisting> |
| 656 |
|
| 657 |
And the matching code in the C module could then follow this skeleton: |
| 658 |
|
| 659 |
<programlisting> |
| 660 |
PG_FUNCTION_INFO_V1(my_picksplit); |
| 661 |
|
| 662 |
Datum |
| 663 |
my_picksplit(PG_FUNCTION_ARGS) |
| 664 |
{ |
| 665 |
GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0); |
| 666 |
GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1); |
| 667 |
OffsetNumber maxoff = entryvec->n - 1; |
| 668 |
GISTENTRY *ent = entryvec->vector; |
| 669 |
int i, |
| 670 |
nbytes; |
| 671 |
OffsetNumber *left, |
| 672 |
*right; |
| 673 |
data_type *tmp_union; |
| 674 |
data_type *unionL; |
| 675 |
data_type *unionR; |
| 676 |
GISTENTRY **raw_entryvec; |
| 677 |
|
| 678 |
maxoff = entryvec->n - 1; |
| 679 |
nbytes = (maxoff + 1) * sizeof(OffsetNumber); |
| 680 |
|
| 681 |
v->spl_left = (OffsetNumber *) palloc(nbytes); |
| 682 |
left = v->spl_left; |
| 683 |
v->spl_nleft = 0; |
| 684 |
|
| 685 |
v->spl_right = (OffsetNumber *) palloc(nbytes); |
| 686 |
right = v->spl_right; |
| 687 |
v->spl_nright = 0; |
| 688 |
|
| 689 |
unionL = NULL; |
| 690 |
unionR = NULL; |
| 691 |
|
| 692 |
/* Initialize the raw entry vector. */ |
| 693 |
raw_entryvec = (GISTENTRY **) malloc(entryvec->n * sizeof(void *)); |
| 694 |
for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i)) |
| 695 |
raw_entryvec[i] = &(entryvec->vector[i]); |
| 696 |
|
| 697 |
for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i)) |
| 698 |
{ |
| 699 |
int real_index = raw_entryvec[i] - entryvec->vector; |
| 700 |
|
| 701 |
tmp_union = DatumGetDataType(entryvec->vector[real_index].key); |
| 702 |
Assert(tmp_union != NULL); |
| 703 |
|
| 704 |
/* |
| 705 |
* Choose where to put the index entries and update unionL and unionR |
| 706 |
* accordingly. Append the entries to either v->spl_left or |
| 707 |
* v->spl_right, and care about the counters. |
| 708 |
*/ |
| 709 |
|
| 710 |
if (my_choice_is_left(unionL, curl, unionR, curr)) |
| 711 |
{ |
| 712 |
if (unionL == NULL) |
| 713 |
unionL = tmp_union; |
| 714 |
else |
| 715 |
unionL = my_union_implementation(unionL, tmp_union); |
| 716 |
|
| 717 |
*left = real_index; |
| 718 |
++left; |
| 719 |
++(v->spl_nleft); |
| 720 |
} |
| 721 |
else |
| 722 |
{ |
| 723 |
/* |
| 724 |
* Same on the right |
| 725 |
*/ |
| 726 |
} |
| 727 |
} |
| 728 |
|
| 729 |
v->spl_ldatum = DataTypeGetDatum(unionL); |
| 730 |
v->spl_rdatum = DataTypeGetDatum(unionR); |
| 731 |
PG_RETURN_POINTER(v); |
| 732 |
} |
| 733 |
</programlisting> |
| 734 |
|
| 735 |
Notice that the <function>picksplit</function> function's result is delivered |
| 736 |
by modifying the passed-in <structname>v</structname> structure. The return |
| 737 |
value per se is ignored, though it's conventional to pass back the |
| 738 |
address of <structname>v</structname>. |
| 739 |
</para> |
| 740 |
|
| 741 |
<para> |
| 742 |
Like <function>penalty</function>, the <function>picksplit</function> function |
| 743 |
is crucial to good performance of the index. Designing suitable |
| 744 |
<function>penalty</function> and <function>picksplit</function> implementations |
| 745 |
is where the challenge of implementing well-performing |
| 746 |
<acronym>GiST</acronym> indexes lies. |
| 747 |
</para> |
| 748 |
</listitem> |
| 749 |
</varlistentry> |
| 750 |
|
| 751 |
<varlistentry> |
| 752 |
<term><function>same</function></term> |
| 753 |
<listitem> |
| 754 |
<para> |
| 755 |
Returns true if two index entries are identical, false otherwise. |
| 756 |
(An <quote>index entry</quote> is a value of the index's storage type, |
| 757 |
not necessarily the original indexed column's type.) |
| 758 |
</para> |
| 759 |
|
| 760 |
<para> |
| 761 |
The <acronym>SQL</acronym> declaration of the function must look like this: |
| 762 |
|
| 763 |
<programlisting> |
| 764 |
CREATE OR REPLACE FUNCTION my_same(storage_type, storage_type, internal) |
| 765 |
RETURNS internal |
| 766 |
AS 'MODULE_PATHNAME' |
| 767 |
LANGUAGE C STRICT; |
| 768 |
</programlisting> |
| 769 |
|
| 770 |
And the matching code in the C module could then follow this skeleton: |
| 771 |
|
| 772 |
<programlisting> |
| 773 |
PG_FUNCTION_INFO_V1(my_same); |
| 774 |
|
| 775 |
Datum |
| 776 |
my_same(PG_FUNCTION_ARGS) |
| 777 |
{ |
| 778 |
prefix_range *v1 = PG_GETARG_PREFIX_RANGE_P(0); |
| 779 |
prefix_range *v2 = PG_GETARG_PREFIX_RANGE_P(1); |
| 780 |
bool *result = (bool *) PG_GETARG_POINTER(2); |
| 781 |
|
| 782 |
*result = my_eq(v1, v2); |
| 783 |
PG_RETURN_POINTER(result); |
| 784 |
} |
| 785 |
</programlisting> |
| 786 |
|
| 787 |
For historical reasons, the <function>same</function> function doesn't |
| 788 |
just return a Boolean result; instead it has to store the flag |
| 789 |
at the location indicated by the third argument. The return |
| 790 |
value per se is ignored, though it's conventional to pass back the |
| 791 |
address of that argument. |
| 792 |
</para> |
| 793 |
</listitem> |
| 794 |
</varlistentry> |
| 795 |
|
| 796 |
<varlistentry> |
| 797 |
<term><function>distance</function></term> |
| 798 |
<listitem> |
| 799 |
<para> |
| 800 |
Given an index entry <literal>p</literal> and a query value <literal>q</literal>, |
| 801 |
this function determines the index entry's |
| 802 |
<quote>distance</quote> from the query value. This function must be |
| 803 |
supplied if the operator class contains any ordering operators. |
| 804 |
A query using the ordering operator will be implemented by returning |
| 805 |
index entries with the smallest <quote>distance</quote> values first, |
| 806 |
so the results must be consistent with the operator's semantics. |
| 807 |
For a leaf index entry the result just represents the distance to |
| 808 |
the index entry; for an internal tree node, the result must be the |
| 809 |
smallest distance that any child entry could have. |
| 810 |
</para> |
| 811 |
|
| 812 |
<para> |
| 813 |
The <acronym>SQL</acronym> declaration of the function must look like this: |
| 814 |
|
| 815 |
<programlisting> |
| 816 |
CREATE OR REPLACE FUNCTION my_distance(internal, data_type, smallint, oid, internal) |
| 817 |
RETURNS float8 |
| 818 |
AS 'MODULE_PATHNAME' |
| 819 |
LANGUAGE C STRICT; |
| 820 |
</programlisting> |
| 821 |
|
| 822 |
And the matching code in the C module could then follow this skeleton: |
| 823 |
|
| 824 |
<programlisting> |
| 825 |
PG_FUNCTION_INFO_V1(my_distance); |
| 826 |
|
| 827 |
Datum |
| 828 |
my_distance(PG_FUNCTION_ARGS) |
| 829 |
{ |
| 830 |
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); |
| 831 |
data_type *query = PG_GETARG_DATA_TYPE_P(1); |
| 832 |
StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2); |
| 833 |
/* Oid subtype = PG_GETARG_OID(3); */ |
| 834 |
/* bool *recheck = (bool *) PG_GETARG_POINTER(4); */ |
| 835 |
data_type *key = DatumGetDataType(entry->key); |
| 836 |
double retval; |
| 837 |
|
| 838 |
/* |
| 839 |
* determine return value as a function of strategy, key and query. |
| 840 |
*/ |
| 841 |
|
| 842 |
PG_RETURN_FLOAT8(retval); |
| 843 |
} |
| 844 |
</programlisting> |
| 845 |
|
| 846 |
The arguments to the <function>distance</function> function are identical to |
| 847 |
the arguments of the <function>consistent</function> function. |
| 848 |
</para> |
| 849 |
|
| 850 |
<para> |
| 851 |
Some approximation is allowed when determining the distance, so long |
| 852 |
as the result is never greater than the entry's actual distance. Thus, |
| 853 |
for example, distance to a bounding box is usually sufficient in |
| 854 |
geometric applications. For an internal tree node, the distance |
| 855 |
returned must not be greater than the distance to any of the child |
| 856 |
nodes. If the returned distance is not exact, the function must set |
| 857 |
<literal>*recheck</literal> to true. (This is not necessary for internal tree |
| 858 |
nodes; for them, the calculation is always assumed to be inexact.) In |
| 859 |
this case the executor will calculate the accurate distance after |
| 860 |
fetching the tuple from the heap, and reorder the tuples if necessary. |
| 861 |
</para> |
| 862 |
|
| 863 |
<para> |
| 864 |
If the distance function returns <literal>*recheck = true</literal> for any |
| 865 |
leaf node, the original ordering operator's return type must |
| 866 |
be <type>float8</type> or <type>float4</type>, and the distance function's |
| 867 |
result values must be comparable to those of the original ordering |
| 868 |
operator, since the executor will sort using both distance function |
| 869 |
results and recalculated ordering-operator results. Otherwise, the |
| 870 |
distance function's result values can be any finite <type>float8</type> |
| 871 |
values, so long as the relative order of the result values matches the |
| 872 |
order returned by the ordering operator. (Infinity and minus infinity |
| 873 |
are used internally to handle cases such as nulls, so it is not |
| 874 |
recommended that <function>distance</function> functions return these values.) |
| 875 |
</para> |
| 876 |
|
| 877 |
</listitem> |
| 878 |
</varlistentry> |
| 879 |
|
| 880 |
<varlistentry> |
| 881 |
<term><function>fetch</function></term> |
| 882 |
<listitem> |
| 883 |
<para> |
| 884 |
Converts the compressed index representation of a data item into the |
| 885 |
original data type, for index-only scans. The returned data must be an |
| 886 |
exact, non-lossy copy of the originally indexed value. |
| 887 |
</para> |
| 888 |
|
| 889 |
<para> |
| 890 |
The <acronym>SQL</acronym> declaration of the function must look like this: |
| 891 |
|
| 892 |
<programlisting> |
| 893 |
CREATE OR REPLACE FUNCTION my_fetch(internal) |
| 894 |
RETURNS internal |
| 895 |
AS 'MODULE_PATHNAME' |
| 896 |
LANGUAGE C STRICT; |
| 897 |
</programlisting> |
| 898 |
|
| 899 |
The argument is a pointer to a <structname>GISTENTRY</structname> struct. On |
| 900 |
entry, its <structfield>key</structfield> field contains a non-NULL leaf datum in |
| 901 |
compressed form. The return value is another <structname>GISTENTRY</structname> |
| 902 |
struct, whose <structfield>key</structfield> field contains the same datum in its |
| 903 |
original, uncompressed form. If the opclass's compress function does |
| 904 |
nothing for leaf entries, the <function>fetch</function> method can return the |
| 905 |
argument as-is. Or, if the opclass does not have a compress function, |
| 906 |
the <function>fetch</function> method can be omitted as well, since it would |
| 907 |
necessarily be a no-op. |
| 908 |
</para> |
| 909 |
|
| 910 |
<para> |
| 911 |
The matching code in the C module could then follow this skeleton: |
| 912 |
|
| 913 |
<programlisting> |
| 914 |
PG_FUNCTION_INFO_V1(my_fetch); |
| 915 |
|
| 916 |
Datum |
| 917 |
my_fetch(PG_FUNCTION_ARGS) |
| 918 |
{ |
| 919 |
GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); |
| 920 |
input_data_type *in = DatumGetPointer(entry->key); |
| 921 |
fetched_data_type *fetched_data; |
| 922 |
GISTENTRY *retval; |
| 923 |
|
| 924 |
retval = palloc(sizeof(GISTENTRY)); |
| 925 |
fetched_data = palloc(sizeof(fetched_data_type)); |
| 926 |
|
| 927 |
/* |
| 928 |
* Convert 'fetched_data' into the a Datum of the original datatype. |
| 929 |
*/ |
| 930 |
|
| 931 |
/* fill *retval from fetched_data. */ |
| 932 |
gistentryinit(*retval, PointerGetDatum(converted_datum), |
| 933 |
entry->rel, entry->page, entry->offset, FALSE); |
| 934 |
|
| 935 |
PG_RETURN_POINTER(retval); |
| 936 |
} |
| 937 |
</programlisting> |
| 938 |
</para> |
| 939 |
|
| 940 |
<para> |
| 941 |
If the compress method is lossy for leaf entries, the operator class |
| 942 |
cannot support index-only scans, and must not define |
| 943 |
a <function>fetch</function> function. |
| 944 |
</para> |
| 945 |
|
| 946 |
</listitem> |
| 947 |
</varlistentry> |
| 948 |
|
| 949 |
<varlistentry> |
| 950 |
<term><function>options</function></term> |
| 951 |
<listitem> |
| 952 |
<para> |
| 953 |
Allows definition of user-visible parameters that control operator |
| 954 |
class behavior. |
| 955 |
</para> |
| 956 |
|
| 957 |
<para> |
| 958 |
The <acronym>SQL</acronym> declaration of the function must look like this: |
| 959 |
|
| 960 |
<programlisting> |
| 961 |
CREATE OR REPLACE FUNCTION my_options(internal) |
| 962 |
RETURNS void |
| 963 |
AS 'MODULE_PATHNAME' |
| 964 |
LANGUAGE C STRICT; |
| 965 |
</programlisting> |
| 966 |
</para> |
| 967 |
|
| 968 |
<para> |
| 969 |
The function is passed a pointer to a <structname>local_relopts</structname> |
| 970 |
struct, which needs to be filled with a set of operator class |
| 971 |
specific options. The options can be accessed from other support |
| 972 |
functions using the <literal>PG_HAS_OPCLASS_OPTIONS()</literal> and |
| 973 |
<literal>PG_GET_OPCLASS_OPTIONS()</literal> macros. |
| 974 |
</para> |
| 975 |
|
| 976 |
<para> |
| 977 |
An example implementation of my_options() and parameters use |
| 978 |
from other support functions are given below: |
| 979 |
|
| 980 |
<programlisting> |
| 981 |
typedef enum MyEnumType |
| 982 |
{ |
| 983 |
MY_ENUM_ON, |
| 984 |
MY_ENUM_OFF, |
| 985 |
MY_ENUM_AUTO |
| 986 |
} MyEnumType; |
| 987 |
|
| 988 |
typedef struct |
| 989 |
{ |
| 990 |
int32 vl_len_; /* varlena header (do not touch directly!) */ |
| 991 |
int int_param; /* integer parameter */ |
| 992 |
double real_param; /* real parameter */ |
| 993 |
MyEnumType enum_param; /* enum parameter */ |
| 994 |
int str_param; /* string parameter */ |
| 995 |
} MyOptionsStruct; |
| 996 |
|
| 997 |
/* String representation of enum values */ |
| 998 |
static relopt_enum_elt_def myEnumValues[] = |
| 999 |
{ |
| 1000 |
{"on", MY_ENUM_ON}, |
| 1001 |
{"off", MY_ENUM_OFF}, |
| 1002 |
{"auto", MY_ENUM_AUTO}, |
| 1003 |
{(const char *) NULL} /* list terminator */ |
| 1004 |
}; |
| 1005 |
|
| 1006 |
static char *str_param_default = "default"; |
| 1007 |
|
| 1008 |
/* |
| 1009 |
* Sample validator: checks that string is not longer than 8 bytes. |
| 1010 |
*/ |
| 1011 |
static void |
| 1012 |
validate_my_string_relopt(const char *value) |
| 1013 |
{ |
| 1014 |
if (strlen(value) > 8) |
| 1015 |
ereport(ERROR, |
| 1016 |
(errcode(ERRCODE_INVALID_PARAMETER_VALUE), |
| 1017 |
errmsg("str_param must be at most 8 bytes"))); |
| 1018 |
} |
| 1019 |
|
| 1020 |
/* |
| 1021 |
* Sample filler: switches characters to lower case. |
| 1022 |
*/ |
| 1023 |
static Size |
| 1024 |
fill_my_string_relopt(const char *value, void *ptr) |
| 1025 |
{ |
| 1026 |
char *tmp = str_tolower(value, strlen(value), DEFAULT_COLLATION_OID); |
| 1027 |
int len = strlen(tmp); |
| 1028 |
|
| 1029 |
if (ptr) |
| 1030 |
strcpy(ptr, tmp); |
| 1031 |
|
| 1032 |
pfree(tmp); |
| 1033 |
return len + 1; |
| 1034 |
} |
| 1035 |
|
| 1036 |
PG_FUNCTION_INFO_V1(my_options); |
| 1037 |
|
| 1038 |
Datum |
| 1039 |
my_options(PG_FUNCTION_ARGS) |
| 1040 |
{ |
| 1041 |
local_relopts *relopts = (local_relopts *) PG_GETARG_POINTER(0); |
| 1042 |
|
| 1043 |
init_local_reloptions(relopts, sizeof(MyOptionsStruct)); |
| 1044 |
add_local_int_reloption(relopts, "int_param", "integer parameter", |
| 1045 |
100, 0, 1000000, |
| 1046 |
offsetof(MyOptionsStruct, int_param)); |
| 1047 |
add_local_real_reloption(relopts, "real_param", "real parameter", |
| 1048 |
1.0, 0.0, 1000000.0, |
| 1049 |
offsetof(MyOptionsStruct, real_param)); |
| 1050 |
add_local_enum_reloption(relopts, "enum_param", "enum parameter", |
| 1051 |
myEnumValues, MY_ENUM_ON, |
| 1052 |
"Valid values are: \"on\", \"off\" and \"auto\".", |
| 1053 |
offsetof(MyOptionsStruct, enum_param)); |
| 1054 |
add_local_string_reloption(relopts, "str_param", "string parameter", |
| 1055 |
str_param_default, |
| 1056 |
&validate_my_string_relopt, |
| 1057 |
&fill_my_string_relopt, |
| 1058 |
offsetof(MyOptionsStruct, str_param)); |
| 1059 |
|
| 1060 |
PG_RETURN_VOID(); |
| 1061 |
} |
| 1062 |
|
| 1063 |
PG_FUNCTION_INFO_V1(my_compress); |
| 1064 |
|
| 1065 |
Datum |
| 1066 |
my_compress(PG_FUNCTION_ARGS) |
| 1067 |
{ |
| 1068 |
int int_param = 100; |
| 1069 |
double real_param = 1.0; |
| 1070 |
MyEnumType enum_param = MY_ENUM_ON; |
| 1071 |
char *str_param = str_param_default; |
| 1072 |
|
| 1073 |
/* |
| 1074 |
* Normally, when opclass contains 'options' method, then options are always |
| 1075 |
* passed to support functions. However, if you add 'options' method to |
| 1076 |
* existing opclass, previously defined indexes have no options, so the |
| 1077 |
* check is required. |
| 1078 |
*/ |
| 1079 |
if (PG_HAS_OPCLASS_OPTIONS()) |
| 1080 |
{ |
| 1081 |
MyOptionsStruct *options = (MyOptionsStruct *) PG_GET_OPCLASS_OPTIONS(); |
| 1082 |
|
| 1083 |
int_param = options->int_param; |
| 1084 |
real_param = options->real_param; |
| 1085 |
enum_param = options->enum_param; |
| 1086 |
str_param = GET_STRING_RELOPTION(options, str_param); |
| 1087 |
} |
| 1088 |
|
| 1089 |
/* the rest implementation of support function */ |
| 1090 |
} |
| 1091 |
|
| 1092 |
</programlisting> |
| 1093 |
</para> |
| 1094 |
|
| 1095 |
<para> |
| 1096 |
Since the representation of the key in <acronym>GiST</acronym> is |
| 1097 |
flexible, it may depend on user-specified parameters. For instance, |
| 1098 |
the length of key signature may be specified. See |
| 1099 |
<literal>gtsvector_options()</literal> for example. |
| 1100 |
</para> |
| 1101 |
</listitem> |
| 1102 |
</varlistentry> |
| 1103 |
|
| 1104 |
<varlistentry> |
| 1105 |
<term><function>sortsupport</function></term> |
| 1106 |
<listitem> |
| 1107 |
<para> |
| 1108 |
Returns a comparator function to sort data in a way that preserves |
| 1109 |
locality. It is used by <command>CREATE INDEX</command> and |
| 1110 |
<command>REINDEX</command> commands. The quality of the created index |
| 1111 |
depends on how well the sort order determined by the comparator function |
| 1112 |
preserves locality of the inputs. |
| 1113 |
</para> |
| 1114 |
<para> |
| 1115 |
The <function>sortsupport</function> method is optional. If it is not |
| 1116 |
provided, <command>CREATE INDEX</command> builds the index by inserting |
| 1117 |
each tuple to the tree using the <function>penalty</function> and |
| 1118 |
<function>picksplit</function> functions, which is much slower. |
| 1119 |
</para> |
| 1120 |
|
| 1121 |
<para> |
| 1122 |
The <acronym>SQL</acronym> declaration of the function must look like |
| 1123 |
this: |
| 1124 |
|
| 1125 |
<programlisting> |
| 1126 |
CREATE OR REPLACE FUNCTION my_sortsupport(internal) |
| 1127 |
RETURNS void |
| 1128 |
AS 'MODULE_PATHNAME' |
| 1129 |
LANGUAGE C STRICT; |
| 1130 |
</programlisting> |
| 1131 |
|
| 1132 |
The argument is a pointer to a <structname>SortSupport</structname> |
| 1133 |
struct. At a minimum, the function must fill in its comparator field. |
| 1134 |
The comparator takes three arguments: two Datums to compare, and |
| 1135 |
a pointer to the <structname>SortSupport</structname> struct. The |
| 1136 |
Datums are the two indexed values in the format that they are stored |
| 1137 |
in the index; that is, in the format returned by the |
| 1138 |
<function>compress</function> method. The full API is defined in |
| 1139 |
<filename>src/include/utils/sortsupport.h</filename>. |
| 1140 |
</para> |
| 1141 |
|
| 1142 |
<para> |
| 1143 |
The matching code in the C module could then follow this skeleton: |
| 1144 |
|
| 1145 |
<programlisting> |
| 1146 |
PG_FUNCTION_INFO_V1(my_sortsupport); |
| 1147 |
|
| 1148 |
static int |
| 1149 |
my_fastcmp(Datum x, Datum y, SortSupport ssup) |
| 1150 |
{ |
| 1151 |
/* establish order between x and y by computing some sorting value z */ |
| 1152 |
|
| 1153 |
int z1 = ComputeSpatialCode(x); |
| 1154 |
int z2 = ComputeSpatialCode(y); |
| 1155 |
|
| 1156 |
return z1 == z2 ? 0 : z1 > z2 ? 1 : -1; |
| 1157 |
} |
| 1158 |
|
| 1159 |
Datum |
| 1160 |
my_sortsupport(PG_FUNCTION_ARGS) |
| 1161 |
{ |
| 1162 |
SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0); |
| 1163 |
|
| 1164 |
ssup->comparator = my_fastcmp; |
| 1165 |
PG_RETURN_VOID(); |
| 1166 |
} |
| 1167 |
</programlisting> |
| 1168 |
</para> |
| 1169 |
</listitem> |
| 1170 |
</varlistentry> |
| 1171 |
|
| 1172 |
<varlistentry> |
| 1173 |
<term><function>translate_cmptype</function></term> |
| 1174 |
<listitem> |
| 1175 |
<para> |
| 1176 |
Given a <literal>CompareType</literal> value from |
| 1177 |
<filename>src/include/access/cmptype.h</filename>, returns a strategy |
| 1178 |
number used by this operator class for matching functionality. The |
| 1179 |
function should return <literal>InvalidStrategy</literal> if the |
| 1180 |
operator class has no matching strategy. |
| 1181 |
</para> |
| 1182 |
|
| 1183 |
<para> |
| 1184 |
This is used for temporal index constraints (i.e., <literal>PRIMARY |
| 1185 |
KEY</literal> and <literal>UNIQUE</literal>). If the operator class |
| 1186 |
provides this function and it returns results for |
| 1187 |
<literal>COMPARE_EQ</literal>, it can be used in the |
| 1188 |
non-<literal>WITHOUT OVERLAPS</literal> part(s) of an index constraint. |
| 1189 |
</para> |
| 1190 |
|
| 1191 |
<para> |
| 1192 |
This support function corresponds to the index access method callback |
| 1193 |
function <structfield>amtranslatecmptype</structfield> (see <xref |
| 1194 |
linkend="index-functions"/>). The |
| 1195 |
<structfield>amtranslatecmptype</structfield> callback function for |
| 1196 |
GiST indexes merely calls down to the |
| 1197 |
<function>translate_cmptype</function> support function of the |
| 1198 |
respective operator family, since the GiST index access method has no |
| 1199 |
fixed strategy numbers itself. |
| 1200 |
</para> |
| 1201 |
|
| 1202 |
<para> |
| 1203 |
The <acronym>SQL</acronym> declaration of the function must look like |
| 1204 |
this: |
| 1205 |
|
| 1206 |
<programlisting> |
| 1207 |
CREATE OR REPLACE FUNCTION my_translate_cmptype(integer) |
| 1208 |
RETURNS smallint |
| 1209 |
AS 'MODULE_PATHNAME' |
| 1210 |
LANGUAGE C STRICT; |
| 1211 |
</programlisting> |
| 1212 |
|
| 1213 |
And the operator family registration must look like this: |
| 1214 |
<programlisting> |
| 1215 |
ALTER OPERATOR FAMILY my_opfamily USING gist ADD |
| 1216 |
FUNCTION 12 ("any", "any") my_translate_cmptype(int); |
| 1217 |
</programlisting> |
| 1218 |
</para> |
| 1219 |
|
| 1220 |
<para> |
| 1221 |
The matching code in the C module could then follow this skeleton: |
| 1222 |
|
| 1223 |
<programlisting> |
| 1224 |
PG_FUNCTION_INFO_V1(my_translate_cmptype); |
| 1225 |
|
| 1226 |
Datum |
| 1227 |
my_translate_cmptype(PG_FUNCTION_ARGS) |
| 1228 |
{ |
| 1229 |
CompareType cmptype = PG_GETARG_INT32(0); |
| 1230 |
StrategyNumber ret = InvalidStrategy; |
| 1231 |
|
| 1232 |
switch (cmptype) |
| 1233 |
{ |
| 1234 |
case COMPARE_EQ: |
| 1235 |
ret = BTEqualStrategyNumber; |
| 1236 |
} |
| 1237 |
|
| 1238 |
PG_RETURN_UINT16(ret); |
| 1239 |
} |
| 1240 |
</programlisting> |
| 1241 |
</para> |
| 1242 |
|
| 1243 |
<para> |
| 1244 |
One translation function is provided by |
| 1245 |
<productname>PostgreSQL</productname>: |
| 1246 |
<literal>gist_translate_cmptype_common</literal> is for operator classes that |
| 1247 |
use the <literal>RT*StrategyNumber</literal> constants. |
| 1248 |
The <literal>btree_gist</literal> |
| 1249 |
extension defines a second translation function, |
| 1250 |
<literal>gist_translate_cmptype_btree</literal>, for operator classes that use |
| 1251 |
the <literal>BT*StrategyNumber</literal> constants. |
| 1252 |
</para> |
| 1253 |
</listitem> |
| 1254 |
</varlistentry> |
| 1255 |
</variablelist> |
| 1256 |
|
| 1257 |
<para> |
| 1258 |
All the GiST support methods are normally called in short-lived memory |
| 1259 |
contexts; that is, <varname>CurrentMemoryContext</varname> will get reset after |
| 1260 |
each tuple is processed. It is therefore not very important to worry about |
| 1261 |
pfree'ing everything you palloc. However, in some cases it's useful for a |
| 1262 |
support method to cache data across repeated calls. To do that, allocate |
| 1263 |
the longer-lived data in <literal>fcinfo->flinfo->fn_mcxt</literal>, and |
| 1264 |
keep a pointer to it in <literal>fcinfo->flinfo->fn_extra</literal>. Such |
| 1265 |
data will survive for the life of the index operation (e.g., a single GiST |
| 1266 |
index scan, index build, or index tuple insertion). Be careful to pfree |
| 1267 |
the previous value when replacing a <literal>fn_extra</literal> value, or the leak |
| 1268 |
will accumulate for the duration of the operation. |
| 1269 |
</para> |
| 1270 |
|
| 1271 |
</sect2> |
| 1272 |
|
| 1273 |
<sect2 id="gist-implementation"> |
| 1274 |
<title>Implementation</title> |
| 1275 |
|
| 1276 |
<sect3 id="gist-buffering-build"> |
| 1277 |
<title>GiST Index Build Methods</title> |
| 1278 |
|
| 1279 |
<para> |
| 1280 |
The simplest way to build a GiST index is just to insert all the entries, |
| 1281 |
one by one. This tends to be slow for large indexes, because if the |
| 1282 |
index tuples are scattered across the index and the index is large enough |
| 1283 |
to not fit in cache, a lot of random I/O will be |
| 1284 |
needed. <productname>PostgreSQL</productname> supports two alternative |
| 1285 |
methods for initial build of a GiST index: <firstterm>sorted</firstterm> |
| 1286 |
and <firstterm>buffered</firstterm> modes. |
| 1287 |
</para> |
| 1288 |
|
| 1289 |
<para> |
| 1290 |
The sorted method is only available if each of the opclasses used by the |
| 1291 |
index provides a <function>sortsupport</function> function, as described |
| 1292 |
in <xref linkend="gist-extensibility"/>. If they do, this method is |
| 1293 |
usually the best, so it is used by default. |
| 1294 |
</para> |
| 1295 |
|
| 1296 |
<para> |
| 1297 |
The buffered method works by not inserting tuples directly into the index |
| 1298 |
right away. It can dramatically reduce the amount of random I/O needed |
| 1299 |
for non-ordered data sets. For well-ordered data sets the benefit is |
| 1300 |
smaller or non-existent, because only a small number of pages receive new |
| 1301 |
tuples at a time, and those pages fit in cache even if the index as a |
| 1302 |
whole does not. |
| 1303 |
</para> |
| 1304 |
|
| 1305 |
<para> |
| 1306 |
The buffered method needs to call the <function>penalty</function> |
| 1307 |
function more often than the simple method does, which consumes some |
| 1308 |
extra CPU resources. Also, the buffers need temporary disk space, up to |
| 1309 |
the size of the resulting index. Buffering can also influence the quality |
| 1310 |
of the resulting index, in both positive and negative directions. That |
| 1311 |
influence depends on various factors, like the distribution of the input |
| 1312 |
data and the operator class implementation. |
| 1313 |
</para> |
| 1314 |
|
| 1315 |
<para> |
| 1316 |
If sorting is not possible, then by default a GiST index build switches |
| 1317 |
to the buffering method when the index size reaches |
| 1318 |
<xref linkend="guc-effective-cache-size"/>. Buffering can be manually |
| 1319 |
forced or prevented by the <literal>buffering</literal> parameter to the |
| 1320 |
CREATE INDEX command. The default behavior is good for most cases, but |
| 1321 |
turning buffering off might speed up the build somewhat if the input data |
| 1322 |
is ordered. |
| 1323 |
</para> |
| 1324 |
|
| 1325 |
</sect3> |
| 1326 |
</sect2> |
| 1327 |
|
| 1328 |
<sect2 id="gist-examples"> |
| 1329 |
<title>Examples</title> |
| 1330 |
|
| 1331 |
<para> |
| 1332 |
The <productname>PostgreSQL</productname> source distribution includes |
| 1333 |
several examples of index methods implemented using |
| 1334 |
<acronym>GiST</acronym>. The core system currently provides text search |
| 1335 |
support (indexing for <type>tsvector</type> and <type>tsquery</type>) as well as |
| 1336 |
R-Tree equivalent functionality for some of the built-in geometric data types |
| 1337 |
(see <filename>src/backend/access/gist/gistproc.c</filename>). The following |
| 1338 |
<filename>contrib</filename> modules also contain <acronym>GiST</acronym> |
| 1339 |
operator classes: |
| 1340 |
|
| 1341 |
<variablelist> |
| 1342 |
<varlistentry> |
| 1343 |
<term><filename>btree_gist</filename></term> |
| 1344 |
<listitem> |
| 1345 |
<para>B-tree equivalent functionality for several data types</para> |
| 1346 |
</listitem> |
| 1347 |
</varlistentry> |
| 1348 |
|
| 1349 |
<varlistentry> |
| 1350 |
<term><filename>cube</filename></term> |
| 1351 |
<listitem> |
| 1352 |
<para>Indexing for multidimensional cubes</para> |
| 1353 |
</listitem> |
| 1354 |
</varlistentry> |
| 1355 |
|
| 1356 |
<varlistentry> |
| 1357 |
<term><filename>hstore</filename></term> |
| 1358 |
<listitem> |
| 1359 |
<para>Module for storing (key, value) pairs</para> |
| 1360 |
</listitem> |
| 1361 |
</varlistentry> |
| 1362 |
|
| 1363 |
<varlistentry> |
| 1364 |
<term><filename>intarray</filename></term> |
| 1365 |
<listitem> |
| 1366 |
<para>RD-Tree for one-dimensional array of int4 values</para> |
| 1367 |
</listitem> |
| 1368 |
</varlistentry> |
| 1369 |
|
| 1370 |
<varlistentry> |
| 1371 |
<term><filename>ltree</filename></term> |
| 1372 |
<listitem> |
| 1373 |
<para>Indexing for tree-like structures</para> |
| 1374 |
</listitem> |
| 1375 |
</varlistentry> |
| 1376 |
|
| 1377 |
<varlistentry> |
| 1378 |
<term><filename>pg_trgm</filename></term> |
| 1379 |
<listitem> |
| 1380 |
<para>Text similarity using trigram matching</para> |
| 1381 |
</listitem> |
| 1382 |
</varlistentry> |
| 1383 |
|
| 1384 |
<varlistentry> |
| 1385 |
<term><filename>seg</filename></term> |
| 1386 |
<listitem> |
| 1387 |
<para>Indexing for <quote>float ranges</quote></para> |
| 1388 |
</listitem> |
| 1389 |
</varlistentry> |
| 1390 |
</variablelist> |
| 1391 |
</para> |
| 1392 |
|
| 1393 |
</sect2> |
| 1394 |
|
| 1395 |
</sect1> |