granicus.if.org Git - postgresql/blob - doc/src/sgml/gist.sgml

   1 <!-- doc/src/sgml/gist.sgml -->
   2
   3 <chapter id="GiST">
   4 <title>GiST Indexes</title>
   5
   6    <indexterm>
   7     <primary>index</primary>
   8     <secondary>GiST</secondary>
   9    </indexterm>
  10
  11 <sect1 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 </sect1>
  42
  43 <sect1 id="gist-extensibility">
  44  <title>Extensibility</title>
  45
  46  <para>
  47    Traditionally, implementing a new index access method meant a lot of
  48    difficult work.  It was necessary to understand the inner workings of the
  49    database, such as the lock manager and Write-Ahead Log.  The
  50    <acronym>GiST</acronym> interface has a high level of abstraction,
  51    requiring the access method implementer only to implement the semantics of
  52    the data type being accessed.  The <acronym>GiST</acronym> layer itself
  53    takes care of concurrency, logging and searching the tree structure.
  54  </para>
  55
  56  <para>
  57    This extensibility should not be confused with the extensibility of the
  58    other standard search trees in terms of the data they can handle.  For
  59    example, <productname>PostgreSQL</productname> supports extensible B-trees
  60    and hash indexes. That means that you can use
  61    <productname>PostgreSQL</productname> to build a B-tree or hash over any
  62    data type you want. But B-trees only support range predicates
  63    (<literal>&lt;</literal>, <literal>=</literal>, <literal>&gt;</literal>),
  64    and hash indexes only support equality queries.
  65  </para>
  66
  67  <para>
  68    So if you index, say, an image collection with a
  69    <productname>PostgreSQL</productname> B-tree, you can only issue queries
  70    such as <quote>is imagex equal to imagey</quote>, <quote>is imagex less
  71    than imagey</quote> and <quote>is imagex greater than imagey</quote>.
  72    Depending on how you define <quote>equals</quote>, <quote>less than</quote>
  73    and <quote>greater than</quote> in this context, this could be useful.
  74    However, by using a <acronym>GiST</acronym> based index, you could create
  75    ways to ask domain-specific questions, perhaps <quote>find all images of
  76    horses</quote> or <quote>find all over-exposed images</quote>.
  77  </para>
  78
  79  <para>
  80    All it takes to get a <acronym>GiST</acronym> access method up and running
  81    is to implement several user-defined methods, which define the behavior of
  82    keys in the tree. Of course these methods have to be pretty fancy to
  83    support fancy queries, but for all the standard queries (B-trees,
  84    R-trees, etc.) they're relatively straightforward. In short,
  85    <acronym>GiST</acronym> combines extensibility along with generality, code
  86    reuse, and a clean interface.
  87   </para>
  88
  89  <para>
  90    There are seven methods that an index operator class for
  91    <acronym>GiST</acronym> must provide, and an eighth that is optional.
  92    Correctness of the index is ensured
  93    by proper implementation of the <function>same</>, <function>consistent</>
  94    and <function>union</> methods, while efficiency (size and speed) of the
  95    index will depend on the <function>penalty</> and <function>picksplit</>
  96    methods.
  97    The remaining two basic methods are <function>compress</> and
  98    <function>decompress</>, which allow an index to have internal tree data of
  99    a different type than the data it indexes. The leaves are to be of the
 100    indexed data type, while the other tree nodes can be of any C struct (but
 101    you still have to follow <productname>PostgreSQL</> data type rules here,
 102    see about <literal>varlena</> for variable sized data). If the tree's
 103    internal data type exists at the SQL level, the <literal>STORAGE</> option
 104    of the <command>CREATE OPERATOR CLASS</> command can be used.
 105    The optional eighth method is <function>distance</>, which is needed
 106    if the operator class wishes to support ordered scans (nearest-neighbor
 107    searches).
 108  </para>
 109
 110  <variablelist>
 111     <varlistentry>
 112      <term><function>consistent</></term>
 113      <listitem>
 114       <para>
 115        Given an index entry <literal>p</> and a query value <literal>q</>,
 116        this function determines whether the index entry is
 117        <quote>consistent</> with the query; that is, could the predicate
 118        <quote><replaceable>indexed_column</>
 119        <replaceable>indexable_operator</> <literal>q</></quote> be true for
 120        any row represented by the index entry?  For a leaf index entry this is
 121        equivalent to testing the indexable condition, while for an internal
 122        tree node this determines whether it is necessary to scan the subtree
 123        of the index represented by the tree node.  When the result is
 124        <literal>true</>, a <literal>recheck</> flag must also be returned.
 125        This indicates whether the predicate is certainly true or only possibly
 126        true.  If <literal>recheck</> = <literal>false</> then the index has
 127        tested the predicate condition exactly, whereas if <literal>recheck</>
 128        = <literal>true</> the row is only a candidate match.  In that case the
 129        system will automatically evaluate the
 130        <replaceable>indexable_operator</> against the actual row value to see
 131        if it is really a match.  This convention allows
 132        <acronym>GiST</acronym> to support both lossless and lossy index
 133        structures.
 134       </para>
 135
 136       <para>
 137         The <acronym>SQL</> declaration of the function must look like this:
 138
 139 <programlisting>
 140 CREATE OR REPLACE FUNCTION my_consistent(internal, data_type, smallint, oid, internal)
 141 RETURNS bool
 142 AS 'MODULE_PATHNAME'
 143 LANGUAGE C STRICT;
 144 </programlisting>
 145
 146         And the matching code in the C module could then follow this skeleton:
 147
 148 <programlisting>
 149 Datum       my_consistent(PG_FUNCTION_ARGS);
 150 PG_FUNCTION_INFO_V1(my_consistent);
 151
 152 Datum
 153 my_consistent(PG_FUNCTION_ARGS)
 154 {
 155     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
 156     data_type  *query = PG_GETARG_DATA_TYPE_P(1);
 157     StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
 158     /* Oid subtype = PG_GETARG_OID(3); */
 159     bool       *recheck = (bool *) PG_GETARG_POINTER(4);
 160     data_type  *key = DatumGetDataType(entry-&gt;key);
 161     bool        retval;
 162
 163     /*
 164      * determine return value as a function of strategy, key and query.
 165      *
 166      * Use GIST_LEAF(entry) to know where you're called in the index tree,
 167      * which comes handy when supporting the = operator for example (you could
 168      * check for non empty union() in non-leaf nodes and equality in leaf
 169      * nodes).
 170      */
 171
 172     *recheck = true;        /* or false if check is exact */
 173
 174     PG_RETURN_BOOL(retval);
 175 }
 176 </programlisting>
 177
 178        Here, <varname>key</> is an element in the index and <varname>query</>
 179        the value being looked up in the index. The <literal>StrategyNumber</>
 180        parameter indicates which operator of your operator class is being
 181        applied &mdash; it matches one of the operator numbers in the
 182        <command>CREATE OPERATOR CLASS</> command.  Depending on what operators
 183        you have included in the class, the data type of <varname>query</> could
 184        vary with the operator, but the above skeleton assumes it doesn't.
 185       </para>
 186
 187      </listitem>
 188     </varlistentry>
 189
 190     <varlistentry>
 191      <term><function>union</></term>
 192      <listitem>
 193       <para>
 194        This method consolidates information in the tree.  Given a set of
 195        entries, this function generates a new index entry that represents
 196        all the given entries.
 197       </para>
 198
 199       <para>
 200         The <acronym>SQL</> declaration of the function must look like this:
 201
 202 <programlisting>
 203 CREATE OR REPLACE FUNCTION my_union(internal, internal)
 204 RETURNS internal
 205 AS 'MODULE_PATHNAME'
 206 LANGUAGE C STRICT;
 207 </programlisting>
 208
 209         And the matching code in the C module could then follow this skeleton:
 210
 211 <programlisting>
 212 Datum       my_union(PG_FUNCTION_ARGS);
 213 PG_FUNCTION_INFO_V1(my_union);
 214
 215 Datum
 216 my_union(PG_FUNCTION_ARGS)
 217 {
 218     GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
 219     GISTENTRY  *ent = entryvec-&gt;vector;
 220     data_type  *out,
 221                *tmp,
 222                *old;
 223     int         numranges,
 224                 i = 0;
 225
 226     numranges = entryvec-&gt;n;
 227     tmp = DatumGetDataType(ent[0].key);
 228     out = tmp;
 229
 230     if (numranges == 1)
 231     {
 232         out = data_type_deep_copy(tmp);
 233
 234         PG_RETURN_DATA_TYPE_P(out);
 235     }
 236
 237     for (i = 1; i &lt; numranges; i++)
 238     {
 239         old = out;
 240         tmp = DatumGetDataType(ent[i].key);
 241         out = my_union_implementation(out, tmp);
 242     }
 243
 244     PG_RETURN_DATA_TYPE_P(out);
 245 }
 246 </programlisting>
 247       </para>
 248
 249       <para>
 250         As you can see, in this skeleton we're dealing with a data type
 251         where <literal>union(X, Y, Z) = union(union(X, Y), Z)</>. It's easy
 252         enough to support data types where this is not the case, by
 253         implementing the proper union algorithm in this
 254         <acronym>GiST</> support method.
 255       </para>
 256
 257       <para>
 258         The <function>union</> implementation function should return a
 259         pointer to newly <function>palloc()</>ed memory. You can't just
 260         return whatever the input is.
 261       </para>
 262      </listitem>
 263     </varlistentry>
 264
 265     <varlistentry>
 266      <term><function>compress</></term>
 267      <listitem>
 268       <para>
 269        Converts the data item into a format suitable for physical storage in
 270        an index page.
 271       </para>
 272
 273       <para>
 274         The <acronym>SQL</> declaration of the function must look like this:
 275
 276 <programlisting>
 277 CREATE OR REPLACE FUNCTION my_compress(internal)
 278 RETURNS internal
 279 AS 'MODULE_PATHNAME'
 280 LANGUAGE C STRICT;
 281 </programlisting>
 282
 283         And the matching code in the C module could then follow this skeleton:
 284
 285 <programlisting>
 286 Datum       my_compress(PG_FUNCTION_ARGS);
 287 PG_FUNCTION_INFO_V1(my_compress);
 288
 289 Datum
 290 my_compress(PG_FUNCTION_ARGS)
 291 {
 292     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
 293     GISTENTRY  *retval;
 294
 295     if (entry-&gt;leafkey)
 296     {
 297         /* replace entry-&gt;key with a compressed version */
 298         compressed_data_type *compressed_data = palloc(sizeof(compressed_data_type));
 299
 300         /* fill *compressed_data from entry-&gt;key ... */
 301
 302         retval = palloc(sizeof(GISTENTRY));
 303         gistentryinit(*retval, PointerGetDatum(compressed_data),
 304                       entry-&gt;rel, entry-&gt;page, entry-&gt;offset, FALSE);
 305     }
 306     else
 307     {
 308         /* typically we needn't do anything with non-leaf entries */
 309         retval = entry;
 310     }
 311
 312     PG_RETURN_POINTER(retval);
 313 }
 314 </programlisting>
 315       </para>
 316
 317       <para>
 318        You have to adapt <replaceable>compressed_data_type</> to the specific
 319        type you're converting to in order to compress your leaf nodes, of
 320        course.
 321       </para>
 322
 323       <para>
 324         Depending on your needs, you could also need to care about
 325         compressing <literal>NULL</> values in there, storing for example
 326         <literal>(Datum) 0</> like <literal>gist_circle_compress</> does.
 327       </para>
 328      </listitem>
 329     </varlistentry>
 330
 331     <varlistentry>
 332      <term><function>decompress</></term>
 333      <listitem>
 334       <para>
 335        The reverse of the <function>compress</function> method.  Converts the
 336        index representation of the data item into a format that can be
 337        manipulated by the database.
 338       </para>
 339
 340       <para>
 341         The <acronym>SQL</> declaration of the function must look like this:
 342
 343 <programlisting>
 344 CREATE OR REPLACE FUNCTION my_decompress(internal)
 345 RETURNS internal
 346 AS 'MODULE_PATHNAME'
 347 LANGUAGE C STRICT;
 348 </programlisting>
 349
 350         And the matching code in the C module could then follow this skeleton:
 351
 352 <programlisting>
 353 Datum       my_decompress(PG_FUNCTION_ARGS);
 354 PG_FUNCTION_INFO_V1(my_decompress);
 355
 356 Datum
 357 my_decompress(PG_FUNCTION_ARGS)
 358 {
 359     PG_RETURN_POINTER(PG_GETARG_POINTER(0));
 360 }
 361 </programlisting>
 362
 363         The above skeleton is suitable for the case where no decompression
 364         is needed.
 365       </para>
 366      </listitem>
 367     </varlistentry>
 368
 369     <varlistentry>
 370      <term><function>penalty</></term>
 371      <listitem>
 372       <para>
 373        Returns a value indicating the <quote>cost</quote> of inserting the new
 374        entry into a particular branch of the tree.  Items will be inserted
 375        down the path of least <function>penalty</function> in the tree.
 376        Values returned by <function>penalty</function> should be non-negative.
 377        If a negative value is returned, it will be treated as zero.
 378       </para>
 379
 380       <para>
 381         The <acronym>SQL</> declaration of the function must look like this:
 382
 383 <programlisting>
 384 CREATE OR REPLACE FUNCTION my_penalty(internal, internal, internal)
 385 RETURNS internal
 386 AS 'MODULE_PATHNAME'
 387 LANGUAGE C STRICT;  -- in some cases penalty functions need not be strict
 388 </programlisting>
 389
 390         And the matching code in the C module could then follow this skeleton:
 391
 392 <programlisting>
 393 Datum       my_penalty(PG_FUNCTION_ARGS);
 394 PG_FUNCTION_INFO_V1(my_penalty);
 395
 396 Datum
 397 my_penalty(PG_FUNCTION_ARGS)
 398 {
 399     GISTENTRY  *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
 400     GISTENTRY  *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
 401     float      *penalty = (float *) PG_GETARG_POINTER(2);
 402     data_type  *orig = DatumGetDataType(origentry-&gt;key);
 403     data_type  *new = DatumGetDataType(newentry-&gt;key);
 404
 405     *penalty = my_penalty_implementation(orig, new);
 406     PG_RETURN_POINTER(penalty);
 407 }
 408 </programlisting>
 409       </para>
 410
 411       <para>
 412         The <function>penalty</> function is crucial to good performance of
 413         the index. It'll get used at insertion time to determine which branch
 414         to follow when choosing where to add the new entry in the tree. At
 415         query time, the more balanced the index, the quicker the lookup.
 416       </para>
 417      </listitem>
 418     </varlistentry>
 419
 420     <varlistentry>
 421      <term><function>picksplit</></term>
 422      <listitem>
 423       <para>
 424        When an index page split is necessary, this function decides which
 425        entries on the page are to stay on the old page, and which are to move
 426        to the new page.
 427       </para>
 428
 429       <para>
 430         The <acronym>SQL</> declaration of the function must look like this:
 431
 432 <programlisting>
 433 CREATE OR REPLACE FUNCTION my_picksplit(internal, internal)
 434 RETURNS internal
 435 AS 'MODULE_PATHNAME'
 436 LANGUAGE C STRICT;
 437 </programlisting>
 438
 439         And the matching code in the C module could then follow this skeleton:
 440
 441 <programlisting>
 442 Datum       my_picksplit(PG_FUNCTION_ARGS);
 443 PG_FUNCTION_INFO_V1(my_picksplit);
 444
 445 Datum
 446 my_picksplit(PG_FUNCTION_ARGS)
 447 {
 448     GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
 449     OffsetNumber maxoff = entryvec-&gt;n - 1;
 450     GISTENTRY  *ent = entryvec-&gt;vector;
 451     GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
 452     int         i,
 453                 nbytes;
 454     OffsetNumber *left,
 455                *right;
 456     data_type  *tmp_union;
 457     data_type  *unionL;
 458     data_type  *unionR;
 459     GISTENTRY **raw_entryvec;
 460
 461     maxoff = entryvec-&gt;n - 1;
 462     nbytes = (maxoff + 1) * sizeof(OffsetNumber);
 463
 464     v-&gt;spl_left = (OffsetNumber *) palloc(nbytes);
 465     left = v-&gt;spl_left;
 466     v-&gt;spl_nleft = 0;
 467
 468     v-&gt;spl_right = (OffsetNumber *) palloc(nbytes);
 469     right = v-&gt;spl_right;
 470     v-&gt;spl_nright = 0;
 471
 472     unionL = NULL;
 473     unionR = NULL;
 474
 475     /* Initialize the raw entry vector. */
 476     raw_entryvec = (GISTENTRY **) malloc(entryvec-&gt;n * sizeof(void *));
 477     for (i = FirstOffsetNumber; i &lt;= maxoff; i = OffsetNumberNext(i))
 478         raw_entryvec[i] = &amp;(entryvec-&gt;vector[i]);
 479
 480     for (i = FirstOffsetNumber; i &lt;= maxoff; i = OffsetNumberNext(i))
 481     {
 482         int         real_index = raw_entryvec[i] - entryvec-&gt;vector;
 483
 484         tmp_union = DatumGetDataType(entryvec-&gt;vector[real_index].key);
 485         Assert(tmp_union != NULL);
 486
 487         /*
 488          * Choose where to put the index entries and update unionL and unionR
 489          * accordingly. Append the entries to either v_spl_left or
 490          * v_spl_right, and care about the counters.
 491          */
 492
 493         if (my_choice_is_left(unionL, curl, unionR, curr))
 494         {
 495             if (unionL == NULL)
 496                 unionL = tmp_union;
 497             else
 498                 unionL = my_union_implementation(unionL, tmp_union);
 499
 500             *left = real_index;
 501             ++left;
 502             ++(v-&gt;spl_nleft);
 503         }
 504         else
 505         {
 506             /*
 507              * Same on the right
 508              */
 509         }
 510     }
 511
 512     v-&gt;spl_ldatum = DataTypeGetDatum(unionL);
 513     v-&gt;spl_rdatum = DataTypeGetDatum(unionR);
 514     PG_RETURN_POINTER(v);
 515 }
 516 </programlisting>
 517       </para>
 518
 519       <para>
 520         Like <function>penalty</>, the <function>picksplit</> function
 521         is crucial to good performance of the index.  Designing suitable
 522         <function>penalty</> and <function>picksplit</> implementations
 523         is where the challenge of implementing well-performing
 524         <acronym>GiST</> indexes lies.
 525       </para>
 526      </listitem>
 527     </varlistentry>
 528
 529     <varlistentry>
 530      <term><function>same</></term>
 531      <listitem>
 532       <para>
 533        Returns true if two index entries are identical, false otherwise.
 534       </para>
 535
 536       <para>
 537         The <acronym>SQL</> declaration of the function must look like this:
 538
 539 <programlisting>
 540 CREATE OR REPLACE FUNCTION my_same(internal, internal, internal)
 541 RETURNS internal
 542 AS 'MODULE_PATHNAME'
 543 LANGUAGE C STRICT;
 544 </programlisting>
 545
 546         And the matching code in the C module could then follow this skeleton:
 547
 548 <programlisting>
 549 Datum       my_same(PG_FUNCTION_ARGS);
 550 PG_FUNCTION_INFO_V1(my_same);
 551
 552 Datum
 553 my_same(PG_FUNCTION_ARGS)
 554 {
 555     prefix_range *v1 = PG_GETARG_PREFIX_RANGE_P(0);
 556     prefix_range *v2 = PG_GETARG_PREFIX_RANGE_P(1);
 557     bool       *result = (bool *) PG_GETARG_POINTER(2);
 558
 559     *result = my_eq(v1, v2);
 560     PG_RETURN_POINTER(result);
 561 }
 562 </programlisting>
 563
 564         For historical reasons, the <function>same</> function doesn't
 565         just return a Boolean result; instead it has to store the flag
 566         at the location indicated by the third argument.
 567       </para>
 568      </listitem>
 569     </varlistentry>
 570
 571     <varlistentry>
 572      <term><function>distance</></term>
 573      <listitem>
 574       <para>
 575        Given an index entry <literal>p</> and a query value <literal>q</>,
 576        this function determines the index entry's
 577        <quote>distance</> from the query value.  This function must be
 578        supplied if the operator class contains any ordering operators.
 579        A query using the ordering operator will be implemented by returning
 580        index entries with the smallest <quote>distance</> values first,
 581        so the results must be consistent with the operator's semantics.
 582        For a leaf index entry the result just represents the distance to
 583        the index entry; for an internal tree node, the result must be the
 584        smallest distance that any child entry could have.
 585       </para>
 586
 587       <para>
 588         The <acronym>SQL</> declaration of the function must look like this:
 589
 590 <programlisting>
 591 CREATE OR REPLACE FUNCTION my_distance(internal, data_type, smallint, oid)
 592 RETURNS float8
 593 AS 'MODULE_PATHNAME'
 594 LANGUAGE C STRICT;
 595 </programlisting>
 596
 597         And the matching code in the C module could then follow this skeleton:
 598
 599 <programlisting>
 600 Datum       my_distance(PG_FUNCTION_ARGS);
 601 PG_FUNCTION_INFO_V1(my_distance);
 602
 603 Datum
 604 my_distance(PG_FUNCTION_ARGS)
 605 {
 606     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
 607     data_type  *query = PG_GETARG_DATA_TYPE_P(1);
 608     StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
 609     /* Oid subtype = PG_GETARG_OID(3); */
 610     data_type  *key = DatumGetDataType(entry-&gt;key);
 611     double      retval;
 612
 613     /*
 614      * determine return value as a function of strategy, key and query.
 615      */
 616
 617     PG_RETURN_FLOAT8(retval);
 618 }
 619 </programlisting>
 620
 621        The arguments to the <function>distance</> function are identical to
 622        the arguments of the <function>consistent</> function, except that no
 623        recheck flag is used.  The distance to a leaf index entry must always
 624        be determined exactly, since there is no way to re-order the tuples
 625        once they are returned.  Some approximation is allowed when determining
 626        the distance to an internal tree node, so long as the result is never
 627        greater than any child's actual distance.  Thus, for example, distance
 628        to a bounding box is usually sufficient in geometric applications.  The
 629        result value can be any finite <type>float8</> value.  (Infinity and
 630        minus infinity are used internally to handle cases such as nulls, so it
 631        is not recommended that <function>distance</> functions return these
 632        values.)
 633       </para>
 634
 635      </listitem>
 636     </varlistentry>
 637
 638   </variablelist>
 639
 640   <para>
 641    All the GiST support methods are normally called in short-lived memory
 642    contexts; that is, <varname>CurrentMemoryContext</> will get reset after
 643    each tuple is processed.  It is therefore not very important to worry about
 644    pfree'ing everything you palloc.  However, in some cases it's useful for a
 645    support method to cache data across repeated calls.  To do that, allocate
 646    the longer-lived data in <literal>fcinfo-&gt;flinfo-&gt;fn_mcxt</>, and
 647    keep a pointer to it in <literal>fcinfo-&gt;flinfo-&gt;fn_extra</>.  Such
 648    data will survive for the life of the index operation (e.g., a single GiST
 649    index scan, index build, or index tuple insertion).  Be careful to pfree
 650    the previous value when replacing a <literal>fn_extra</> value, or the leak
 651    will accumulate for the duration of the operation.
 652   </para>
 653
 654 </sect1>
 655
 656 <sect1 id="gist-implementation">
 657  <title>Implementation</title>
 658
 659  <sect2 id="gist-buffering-build">
 660   <title>GiST buffering build</title>
 661   <para>
 662    Building large GiST indexes by simply inserting all the tuples tends to be
 663    slow, because if the index tuples are scattered across the index and the
 664    index is large enough to not fit in cache, the insertions need to perform
 665    a lot of random I/O.  Beginning in version 9.2, PostgreSQL supports a more
 666    efficient method to build GiST indexes based on buffering, which can
 667    dramatically reduce the number of random I/Os needed for non-ordered data
 668    sets. For well-ordered data sets the benefit is smaller or non-existent,
 669    because only a small number of pages receive new tuples at a time, and
 670    those pages fit in cache even if the index as whole does not.
 671   </para>
 672
 673   <para>
 674    However, buffering index build needs to call the <function>penalty</>
 675    function more often, which consumes some extra CPU resources. Also, the
 676    buffers used in the buffering build need temporary disk space, up to
 677    the size of the resulting index. Buffering can also influence the quality
 678    of the resulting index, in both positive and negative directions. That
 679    influence depends on various factors, like the distribution of the input
 680    data and the operator class implementation.
 681   </para>
 682
 683   <para>
 684    By default, a GiST index build switches to the buffering method when the
 685    index size reaches <xref linkend="guc-effective-cache-size">. It can
 686    be manually turned on or off by the <literal>BUFFERING</literal> parameter
 687    to the CREATE INDEX command. The default behavior is good for most cases,
 688    but turning buffering off might speed up the build somewhat if the input
 689    data is ordered.
 690   </para>
 691
 692  </sect2>
 693 </sect1>
 694
 695 <sect1 id="gist-examples">
 696  <title>Examples</title>
 697
 698  <para>
 699   The <productname>PostgreSQL</productname> source distribution includes
 700   several examples of index methods implemented using
 701   <acronym>GiST</acronym>.  The core system currently provides text search
 702   support (indexing for <type>tsvector</> and <type>tsquery</>) as well as
 703   R-Tree equivalent functionality for some of the built-in geometric data types
 704   (see <filename>src/backend/access/gist/gistproc.c</>).  The following
 705   <filename>contrib</> modules also contain <acronym>GiST</acronym>
 706   operator classes:
 707
 708  <variablelist>
 709   <varlistentry>
 710    <term><filename>btree_gist</></term>
 711    <listitem>
 712     <para>B-tree equivalent functionality for several data types</para>
 713    </listitem>
 714   </varlistentry>
 715
 716   <varlistentry>
 717    <term><filename>cube</></term>
 718    <listitem>
 719     <para>Indexing for multidimensional cubes</para>
 720    </listitem>
 721   </varlistentry>
 722
 723   <varlistentry>
 724    <term><filename>hstore</></term>
 725    <listitem>
 726     <para>Module for storing (key, value) pairs</para>
 727    </listitem>
 728   </varlistentry>
 729
 730   <varlistentry>
 731    <term><filename>intarray</></term>
 732    <listitem>
 733     <para>RD-Tree for one-dimensional array of int4 values</para>
 734    </listitem>
 735   </varlistentry>
 736
 737   <varlistentry>
 738    <term><filename>ltree</></term>
 739    <listitem>
 740     <para>Indexing for tree-like structures</para>
 741    </listitem>
 742   </varlistentry>
 743
 744   <varlistentry>
 745    <term><filename>pg_trgm</></term>
 746    <listitem>
 747     <para>Text similarity using trigram matching</para>
 748    </listitem>
 749   </varlistentry>
 750
 751   <varlistentry>
 752    <term><filename>seg</></term>
 753    <listitem>
 754     <para>Indexing for <quote>float ranges</quote></para>
 755    </listitem>
 756   </varlistentry>
 757  </variablelist>
 758  </para>
 759
 760 </sect1>
 761
 762 </chapter>