doc/src/sgml/gist.sgml

   1 <!-- $PostgreSQL$ -->
   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 seven 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 </sect1>
  90
  91 <sect1 id="gist-implementation">
  92  <title>Implementation</title>
  93
  94  <para>
  95    There are seven methods that an index operator class for
  96    <acronym>GiST</acronym> must provide. Correctness of the index is ensured
  97    by proper implementation of the <function>same</>, <function>consistent</>
  98    and <function>union</> methods, while efficiency (size and speed) of the
  99    index will depend on the <function>penalty</> and <function>picksplit</>
 100    methods.
 101    The remaining two methods are <function>compress</> and
 102    <function>decompress</>, which allow an index to have internal tree data of
 103    a different type than the data it indexes. The leaves are to be of the
 104    indexed data type, while the other tree nodes can be of any C struct (but
 105    you still have to follow <productname>PostgreSQL</> datatype rules here,
 106    see about <literal>varlena</> for variable sized data). If the tree's
 107    internal data type exists at the SQL level, the <literal>STORAGE</> option
 108    of the <command>CREATE OPERATOR CLASS</> command can be used.
 109  </para>
 110
 111  <variablelist>
 112     <varlistentry>
 113      <term><function>consistent</></term>
 114      <listitem>
 115       <para>
 116        Given an index entry <literal>p</> and a query value <literal>q</>,
 117        this function determines whether the index entry is
 118        <quote>consistent</> with the query; that is, could the predicate
 119        <quote><replaceable>indexed_column</>
 120        <replaceable>indexable_operator</> <literal>q</></quote> be true for
 121        any row represented by the index entry?  For a leaf index entry this is
 122        equivalent to testing the indexable condition, while for an internal
 123        tree node this determines whether it is necessary to scan the subtree
 124        of the index represented by the tree node.  When the result is
 125        <literal>true</>, a <literal>recheck</> flag must also be returned.
 126        This indicates whether the predicate is certainly true or only possibly
 127        true.  If <literal>recheck</> = <literal>false</> then the index has
 128        tested the predicate condition exactly, whereas if <literal>recheck</>
 129        = <literal>true</> the row is only a candidate match.  In that case the
 130        system will automatically evaluate the
 131        <replaceable>indexable_operator</> against the actual row value to see
 132        if it is really a match.  This convention allows
 133        <acronym>GiST</acronym> to support both lossless and lossy index
 134        structures.
 135       </para>
 136
 137       <para>
 138         The <acronym>SQL</> declaration of the function must look like this:
 139
 140 <programlisting>
 141 CREATE OR REPLACE FUNCTION my_consistent(internal, data_type, smallint, oid, internal)
 142 RETURNS bool
 143 AS 'MODULE_PATHNAME'
 144 LANGUAGE C STRICT;
 145 </programlisting>
 146
 147         And the matching code in the C module could then follow this skeleton:
 148
 149 <programlisting>
 150 Datum       my_consistent(PG_FUNCTION_ARGS);
 151 PG_FUNCTION_INFO_V1(my_consistent);
 152
 153 Datum
 154 my_consistent(PG_FUNCTION_ARGS)
 155 {
 156     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
 157     data_type  *query = PG_GETARG_DATA_TYPE_P(1);
 158     StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
 159     /* Oid subtype = PG_GETARG_OID(3); */
 160     bool       *recheck = (bool *) PG_GETARG_POINTER(4);
 161     data_type  *key = DatumGetDataType(entry-&gt;key);
 162     bool        retval;
 163
 164     /*
 165      * determine return value as a function of strategy, key and query.
 166      *
 167      * Use GIST_LEAF(entry) to know where you're called in the index tree,
 168      * which comes handy when supporting the = operator for example (you could
 169      * check for non empty union() in non-leaf nodes and equality in leaf
 170      * nodes).
 171      */
 172
 173     *recheck = true;        /* or false if check is exact */
 174
 175     PG_RETURN_BOOL(retval);
 176 }
 177 </programlisting>
 178
 179        Here, <varname>key</> is an element in the index and <varname>query</>
 180        the value being looked up in the index. The <literal>StrategyNumber</>
 181        parameter indicates which operator of your operator class is being
 182        applied &mdash; it matches one of the operator numbers in the
 183        <command>CREATE OPERATOR CLASS</> command.  Depending on what operators
 184        you have included in the class, the data type of <varname>query</> could
 185        vary with the operator, but the above skeleton assumes it doesn't.
 186       </para>
 187
 188      </listitem>
 189     </varlistentry>
 190
 191     <varlistentry>
 192      <term><function>union</></term>
 193      <listitem>
 194       <para>
 195        This method consolidates information in the tree.  Given a set of
 196        entries, this function generates a new index entry that represents
 197        all the given entries.
 198       </para>
 199
 200       <para>
 201         The <acronym>SQL</> declaration of the function must look like this:
 202
 203 <programlisting>
 204 CREATE OR REPLACE FUNCTION my_union(internal, internal)
 205 RETURNS internal
 206 AS 'MODULE_PATHNAME'
 207 LANGUAGE C STRICT;
 208 </programlisting>
 209
 210         And the matching code in the C module could then follow this skeleton:
 211
 212 <programlisting>
 213 Datum       my_union(PG_FUNCTION_ARGS);
 214 PG_FUNCTION_INFO_V1(my_union);
 215
 216 Datum
 217 my_union(PG_FUNCTION_ARGS)
 218 {
 219     GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
 220     GISTENTRY  *ent = entryvec-&gt;vector;
 221     data_type  *out,
 222                *tmp,
 223                *old;
 224     int         numranges,
 225                 i = 0;
 226
 227     numranges = entryvec-&gt;n;
 228     tmp = DatumGetDataType(ent[0].key);
 229     out = tmp;
 230
 231     if (numranges == 1)
 232     {
 233         out = data_type_deep_copy(tmp);
 234
 235         PG_RETURN_DATA_TYPE_P(out);
 236     }
 237
 238     for (i = 1; i &lt; numranges; i++)
 239     {
 240         old = out;
 241         tmp = DatumGetDataType(ent[i].key);
 242         out = my_union_implementation(out, tmp);
 243     }
 244
 245     PG_RETURN_DATA_TYPE_P(out);
 246 }
 247 </programlisting>
 248       </para>
 249
 250       <para>
 251         As you can see, in this skeleton we're dealing with a data type
 252         where <literal>union(X, Y, Z) = union(union(X, Y), Z)</>. It's easy
 253         enough to support data types where this is not the case, by
 254         implementing the proper union algorithm in this
 255         <acronym>GiST</> support method.
 256       </para>
 257
 258       <para>
 259         The <function>union</> implementation function should return a
 260         pointer to newly <function>palloc()</>ed memory. You can't just
 261         return whatever the input is.
 262       </para>
 263      </listitem>
 264     </varlistentry>
 265
 266     <varlistentry>
 267      <term><function>compress</></term>
 268      <listitem>
 269       <para>
 270        Converts the data item into a format suitable for physical storage in
 271        an index page.
 272       </para>
 273
 274       <para>
 275         The <acronym>SQL</> declaration of the function must look like this:
 276
 277 <programlisting>
 278 CREATE OR REPLACE FUNCTION my_compress(internal)
 279 RETURNS internal
 280 AS 'MODULE_PATHNAME'
 281 LANGUAGE C STRICT;
 282 </programlisting>
 283
 284         And the matching code in the C module could then follow this skeleton:
 285
 286 <programlisting>
 287 Datum       my_compress(PG_FUNCTION_ARGS);
 288 PG_FUNCTION_INFO_V1(my_compress);
 289
 290 Datum
 291 my_compress(PG_FUNCTION_ARGS)
 292 {
 293     GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
 294     GISTENTRY  *retval;
 295
 296     if (entry-&gt;leafkey)
 297     {
 298         /* replace entry-&gt;key with a compressed version */
 299         compressed_data_type *compressed_data = palloc(sizeof(compressed_data_type));
 300
 301         /* fill *compressed_data from entry-&gt;key ... */
 302
 303         retval = palloc(sizeof(GISTENTRY));
 304         gistentryinit(*retval, PointerGetDatum(compressed_data),
 305                       entry-&gt;rel, entry-&gt;page, entry-&gt;offset, FALSE);
 306     }
 307     else
 308     {
 309         /* typically we needn't do anything with non-leaf entries */
 310         retval = entry;
 311     }
 312
 313     PG_RETURN_POINTER(retval);
 314 }
 315 </programlisting>
 316       </para>
 317
 318       <para>
 319        You have to adapt <replaceable>compressed_data_type</> to the specific
 320        type you're converting to in order to compress your leaf nodes, of
 321        course.
 322       </para>
 323
 324       <para>
 325         Depending on your needs, you could also need to care about
 326         compressing <literal>NULL</> values in there, storing for example
 327         <literal>(Datum) 0</> like <literal>gist_circle_compress</> does.
 328       </para>
 329      </listitem>
 330     </varlistentry>
 331
 332     <varlistentry>
 333      <term><function>decompress</></term>
 334      <listitem>
 335       <para>
 336        The reverse of the <function>compress</function> method.  Converts the
 337        index representation of the data item into a format that can be
 338        manipulated by the database.
 339       </para>
 340
 341       <para>
 342         The <acronym>SQL</> declaration of the function must look like this:
 343
 344 <programlisting>
 345 CREATE OR REPLACE FUNCTION my_decompress(internal)
 346 RETURNS internal
 347 AS 'MODULE_PATHNAME'
 348 LANGUAGE C STRICT;
 349 </programlisting>
 350
 351         And the matching code in the C module could then follow this skeleton:
 352
 353 <programlisting>
 354 Datum       my_decompress(PG_FUNCTION_ARGS);
 355 PG_FUNCTION_INFO_V1(my_decompress);
 356
 357 Datum
 358 my_decompress(PG_FUNCTION_ARGS)
 359 {
 360     PG_RETURN_POINTER(PG_GETARG_POINTER(0));
 361 }
 362 </programlisting>
 363
 364         The above skeleton is suitable for the case where no decompression
 365         is needed.
 366       </para>
 367      </listitem>
 368     </varlistentry>
 369
 370     <varlistentry>
 371      <term><function>penalty</></term>
 372      <listitem>
 373       <para>
 374        Returns a value indicating the <quote>cost</quote> of inserting the new
 375        entry into a particular branch of the tree.  Items will be inserted
 376        down the path of least <function>penalty</function> in the tree.
 377       </para>
 378
 379       <para>
 380         The <acronym>SQL</> declaration of the function must look like this:
 381
 382 <programlisting>
 383 CREATE OR REPLACE FUNCTION my_penalty(internal, internal, internal)
 384 RETURNS internal
 385 AS 'MODULE_PATHNAME'
 386 LANGUAGE C STRICT;  -- in some cases penalty functions need not be strict
 387 </programlisting>
 388
 389         And the matching code in the C module could then follow this skeleton:
 390
 391 <programlisting>
 392 Datum       my_penalty(PG_FUNCTION_ARGS);
 393 PG_FUNCTION_INFO_V1(my_penalty);
 394
 395 Datum
 396 my_penalty(PG_FUNCTION_ARGS)
 397 {
 398     GISTENTRY  *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
 399     GISTENTRY  *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
 400     float      *penalty = (float *) PG_GETARG_POINTER(2);
 401     data_type  *orig = DatumGetDataType(origentry-&gt;key);
 402     data_type  *new = DatumGetDataType(newentry-&gt;key);
 403
 404     *penalty = my_penalty_implementation(orig, new);
 405     PG_RETURN_POINTER(penalty);
 406 }
 407 </programlisting>
 408       </para>
 409
 410       <para>
 411         The <function>penalty</> function is crucial to good performance of
 412         the index. It'll get used at insertion time to determine which branch
 413         to follow when choosing where to add the new entry in the tree. At
 414         query time, the more balanced the index, the quicker the lookup.
 415       </para>
 416      </listitem>
 417     </varlistentry>
 418
 419     <varlistentry>
 420      <term><function>picksplit</></term>
 421      <listitem>
 422       <para>
 423        When an index page split is necessary, this function decides which
 424        entries on the page are to stay on the old page, and which are to move
 425        to the new page.
 426       </para>
 427
 428       <para>
 429         The <acronym>SQL</> declaration of the function must look like this:
 430
 431 <programlisting>
 432 CREATE OR REPLACE FUNCTION my_picksplit(internal, internal)
 433 RETURNS internal
 434 AS 'MODULE_PATHNAME'
 435 LANGUAGE C STRICT;
 436 </programlisting>
 437
 438         And the matching code in the C module could then follow this skeleton:
 439
 440 <programlisting>
 441 Datum       my_picksplit(PG_FUNCTION_ARGS);
 442 PG_FUNCTION_INFO_V1(my_picksplit);
 443
 444 Datum
 445 my_picksplit(PG_FUNCTION_ARGS)
 446 {
 447     GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
 448     OffsetNumber maxoff = entryvec-&gt;n - 1;
 449     GISTENTRY  *ent = entryvec-&gt;vector;
 450     GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
 451     int         i,
 452                 nbytes;
 453     OffsetNumber *left,
 454                *right;
 455     data_type  *tmp_union;
 456     data_type  *unionL;
 457     data_type  *unionR;
 458     GISTENTRY **raw_entryvec;
 459
 460     maxoff = entryvec-&gt;n - 1;
 461     nbytes = (maxoff + 1) * sizeof(OffsetNumber);
 462
 463     v-&gt;spl_left = (OffsetNumber *) palloc(nbytes);
 464     left = v-&gt;spl_left;
 465     v-&gt;spl_nleft = 0;
 466
 467     v-&gt;spl_right = (OffsetNumber *) palloc(nbytes);
 468     right = v-&gt;spl_right;
 469     v-&gt;spl_nright = 0;
 470
 471     unionL = NULL;
 472     unionR = NULL;
 473
 474     /* Initialize the raw entry vector. */
 475     raw_entryvec = (GISTENTRY **) malloc(entryvec-&gt;n * sizeof(void *));
 476     for (i = FirstOffsetNumber; i &lt;= maxoff; i = OffsetNumberNext(i))
 477         raw_entryvec[i] = &amp;(entryvec-&gt;vector[i]);
 478
 479     for (i = FirstOffsetNumber; i &lt;= maxoff; i = OffsetNumberNext(i))
 480     {
 481         int         real_index = raw_entryvec[i] - entryvec-&gt;vector;
 482
 483         tmp_union = DatumGetDataType(entryvec-&gt;vector[real_index].key);
 484         Assert(tmp_union != NULL);
 485
 486         /*
 487          * Choose where to put the index entries and update unionL and unionR
 488          * accordingly. Append the entries to either v_spl_left or
 489          * v_spl_right, and care about the counters.
 490          */
 491
 492         if (my_choice_is_left(unionL, curl, unionR, curr))
 493         {
 494             if (unionL == NULL)
 495                 unionL = tmp_union;
 496             else
 497                 unionL = my_union_implementation(unionL, tmp_union);
 498
 499             *left = real_index;
 500             ++left;
 501             ++(v-&gt;spl_nleft);
 502         }
 503         else
 504         {
 505             /*
 506              * Same on the right
 507              */
 508         }
 509     }
 510
 511     v-&gt;spl_ldatum = DataTypeGetDatum(unionL);
 512     v-&gt;spl_rdatum = DataTypeGetDatum(unionR);
 513     PG_RETURN_POINTER(v);
 514 }
 515 </programlisting>
 516       </para>
 517
 518       <para>
 519         Like <function>penalty</>, the <function>picksplit</> function
 520         is crucial to good performance of the index.  Designing suitable
 521         <function>penalty</> and <function>picksplit</> implementations
 522         is where the challenge of implementing well-performing
 523         <acronym>GiST</> indexes lies.
 524       </para>
 525      </listitem>
 526     </varlistentry>
 527
 528     <varlistentry>
 529      <term><function>same</></term>
 530      <listitem>
 531       <para>
 532        Returns true if two index entries are identical, false otherwise.
 533       </para>
 534
 535       <para>
 536         The <acronym>SQL</> declaration of the function must look like this:
 537
 538 <programlisting>
 539 CREATE OR REPLACE FUNCTION my_same(internal, internal, internal)
 540 RETURNS internal
 541 AS 'MODULE_PATHNAME'
 542 LANGUAGE C STRICT;
 543 </programlisting>
 544
 545         And the matching code in the C module could then follow this skeleton:
 546
 547 <programlisting>
 548 Datum       my_same(PG_FUNCTION_ARGS);
 549 PG_FUNCTION_INFO_V1(my_same);
 550
 551 Datum
 552 my_same(PG_FUNCTION_ARGS)
 553 {
 554     prefix_range *v1 = PG_GETARG_PREFIX_RANGE_P(0);
 555     prefix_range *v2 = PG_GETARG_PREFIX_RANGE_P(1);
 556     bool       *result = (bool *) PG_GETARG_POINTER(2);
 557
 558     *result = my_eq(v1, v2);
 559     PG_RETURN_POINTER(result);
 560 }
 561 </programlisting>
 562
 563         For historical reasons, the <function>same</> function doesn't
 564         just return a boolean result; instead it has to store the flag
 565         at the location indicated by the third argument.
 566       </para>
 567      </listitem>
 568     </varlistentry>
 569
 570   </variablelist>
 571
 572 </sect1>
 573
 574 <sect1 id="gist-examples">
 575  <title>Examples</title>
 576
 577  <para>
 578   The <productname>PostgreSQL</productname> source distribution includes
 579   several examples of index methods implemented using
 580   <acronym>GiST</acronym>.  The core system currently provides text search
 581   support (indexing for <type>tsvector</> and <type>tsquery</>) as well as
 582   R-Tree equivalent functionality for some of the built-in geometric data types
 583   (see <filename>src/backend/access/gist/gistproc.c</>).  The following
 584   <filename>contrib</> modules also contain <acronym>GiST</acronym>
 585   operator classes:
 586  </para>
 587
 588  <variablelist>
 589   <varlistentry>
 590    <term>btree_gist</term>
 591    <listitem>
 592     <para>B-Tree equivalent functionality for several data types</para>
 593    </listitem>
 594   </varlistentry>
 595
 596   <varlistentry>
 597    <term>cube</term>
 598    <listitem>
 599     <para>Indexing for multidimensional cubes</para>
 600    </listitem>
 601   </varlistentry>
 602
 603   <varlistentry>
 604    <term>hstore</term>
 605    <listitem>
 606     <para>Module for storing (key, value) pairs</para>
 607    </listitem>
 608   </varlistentry>
 609
 610   <varlistentry>
 611    <term>intarray</term>
 612    <listitem>
 613     <para>RD-Tree for one-dimensional array of int4 values</para>
 614    </listitem>
 615   </varlistentry>
 616
 617   <varlistentry>
 618    <term>ltree</term>
 619    <listitem>
 620     <para>Indexing for tree-like structures</para>
 621    </listitem>
 622   </varlistentry>
 623
 624   <varlistentry>
 625    <term>pg_trgm</term>
 626    <listitem>
 627     <para>Text similarity using trigram matching</para>
 628    </listitem>
 629   </varlistentry>
 630
 631   <varlistentry>
 632    <term>seg</term>
 633    <listitem>
 634     <para>Indexing for <quote>float ranges</quote></para>
 635    </listitem>
 636   </varlistentry>
 637  </variablelist>
 638
 639 </sect1>
 640
 641 <sect1 id="gist-recovery">
 642  <title>Crash Recovery</title>
 643
 644  <para>
 645   Usually, replay of the WAL log is sufficient to restore the integrity
 646   of a GiST index following a database crash.  However, there are some
 647   corner cases in which the index state is not fully rebuilt.  The index
 648   will still be functionally correct, but there might be some performance
 649   degradation.  When this occurs, the index can be repaired by
 650   <command>VACUUM</>ing its table, or by rebuilding the index using
 651   <command>REINDEX</>.  In some cases a plain <command>VACUUM</> is
 652   not sufficient, and either <command>VACUUM FULL</> or <command>REINDEX</>
 653   is needed.  The need for one of these procedures is indicated by occurrence
 654   of this log message during crash recovery:
 655 <programlisting>
 656 LOG:  index NNN/NNN/NNN needs VACUUM or REINDEX to finish crash recovery
 657 </programlisting>
 658   or this log message during routine index insertions:
 659 <programlisting>
 660 LOG:  index "FOO" needs VACUUM or REINDEX to finish crash recovery
 661 </programlisting>
 662   If a plain <command>VACUUM</> finds itself unable to complete recovery
 663   fully, it will return a notice:
 664 <programlisting>
 665 NOTICE:  index "FOO" needs VACUUM FULL or REINDEX to finish crash recovery
 666 </programlisting>
 667  </para>
 668 </sect1>
 669
 670 </chapter>