granicus.if.org Git - postgresql/blob - src/backend/access/index/indexam.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * indexam.c
   4  *        general index access method routines
   5  *
   6  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        $Header: /cvsroot/pgsql/src/backend/access/index/indexam.c,v 1.62 2002/09/04 20:31:09 momjian Exp $
  12  *
  13  * INTERFACE ROUTINES
  14  *              index_open              - open an index relation by relation OID
  15  *              index_openrv    - open an index relation specified by a RangeVar
  16  *              index_openr             - open a system index relation by name
  17  *              index_close             - close an index relation
  18  *              index_beginscan - start a scan of an index
  19  *              index_rescan    - restart a scan of an index
  20  *              index_endscan   - end a scan
  21  *              index_insert    - insert an index tuple into a relation
  22  *              index_markpos   - mark a scan position
  23  *              index_restrpos  - restore a scan position
  24  *              index_getnext   - get the next tuple from a scan
  25  *              index_bulk_delete       - bulk deletion of index tuples
  26  *              index_cost_estimator    - fetch amcostestimate procedure OID
  27  *              index_getprocid - get a support procedure OID
  28  *
  29  * NOTES
  30  *              This file contains the index_ routines which used
  31  *              to be a scattered collection of stuff in access/genam.
  32  *
  33  *
  34  * old comments
  35  *              Scans are implemented as follows:
  36  *
  37  *              `0' represents an invalid item pointer.
  38  *              `-' represents an unknown item pointer.
  39  *              `X' represents a known item pointers.
  40  *              `+' represents known or invalid item pointers.
  41  *              `*' represents any item pointers.
  42  *
  43  *              State is represented by a triple of these symbols in the order of
  44  *              previous, current, next.  Note that the case of reverse scans works
  45  *              identically.
  46  *
  47  *                              State   Result
  48  *              (1)             + + -   + 0 0                   (if the next item pointer is invalid)
  49  *              (2)                             + X -                   (otherwise)
  50  *              (3)             * 0 0   * 0 0                   (no change)
  51  *              (4)             + X 0   X 0 0                   (shift)
  52  *              (5)             * + X   + X -                   (shift, add unknown)
  53  *
  54  *              All other states cannot occur.
  55  *
  56  *              Note: It would be possible to cache the status of the previous and
  57  *                        next item pointer using the flags.
  58  *
  59  *-------------------------------------------------------------------------
  60  */
  61
  62 #include "postgres.h"
  63
  64 #include "access/genam.h"
  65 #include "access/heapam.h"
  66 #include "utils/relcache.h"
  67
  68 #include "pgstat.h"
  69
  70 /* ----------------------------------------------------------------
  71  *                                      macros used in index_ routines
  72  * ----------------------------------------------------------------
  73  */
  74 #define RELATION_CHECKS \
  75 ( \
  76         AssertMacro(RelationIsValid(indexRelation)), \
  77         AssertMacro(PointerIsValid(indexRelation->rd_am)) \
  78 )
  79
  80 #define SCAN_CHECKS \
  81 ( \
  82         AssertMacro(IndexScanIsValid(scan)), \
  83         AssertMacro(RelationIsValid(scan->indexRelation)), \
  84         AssertMacro(PointerIsValid(scan->indexRelation->rd_am)) \
  85 )
  86
  87 #define GET_REL_PROCEDURE(x,y) \
  88 ( \
  89         procedure = indexRelation->rd_am->y, \
  90         (!RegProcedureIsValid(procedure)) ? \
  91                 elog(ERROR, "index_%s: invalid %s regproc", \
  92                         CppAsString(x), CppAsString(y)) \
  93         : (void)NULL \
  94 )
  95
  96 #define GET_SCAN_PROCEDURE(x,y) \
  97 ( \
  98         procedure = scan->indexRelation->rd_am->y, \
  99         (!RegProcedureIsValid(procedure)) ? \
 100                 elog(ERROR, "index_%s: invalid %s regproc", \
 101                         CppAsString(x), CppAsString(y)) \
 102         : (void)NULL \
 103 )
 104
 105
 106 /* ----------------------------------------------------------------
 107  *                                 index_ interface functions
 108  * ----------------------------------------------------------------
 109  */
 110
 111 /* ----------------
 112  *              index_open - open an index relation by relation OID
 113  *
 114  *              Note: we acquire no lock on the index.  An AccessShareLock is
 115  *              acquired by index_beginscan (and released by index_endscan).
 116  *              Generally, the caller should already hold some type of lock on
 117  *              the parent relation to ensure that the index doesn't disappear.
 118  *
 119  *              This is a convenience routine adapted for indexscan use.
 120  *              Some callers may prefer to use relation_open directly.
 121  * ----------------
 122  */
 123 Relation
 124 index_open(Oid relationId)
 125 {
 126         Relation        r;
 127
 128         r = relation_open(relationId, NoLock);
 129
 130         if (r->rd_rel->relkind != RELKIND_INDEX)
 131                 elog(ERROR, "%s is not an index relation",
 132                          RelationGetRelationName(r));
 133
 134         pgstat_initstats(&r->pgstat_info, r);
 135
 136         return r;
 137 }
 138
 139 /* ----------------
 140  *              index_openrv - open an index relation specified
 141  *              by a RangeVar node
 142  *
 143  *              As above, but relation is specified by a RangeVar.
 144  * ----------------
 145  */
 146 Relation
 147 index_openrv(const RangeVar *relation)
 148 {
 149         Relation        r;
 150
 151         r = relation_openrv(relation, NoLock);
 152
 153         if (r->rd_rel->relkind != RELKIND_INDEX)
 154                 elog(ERROR, "%s is not an index relation",
 155                          RelationGetRelationName(r));
 156
 157         pgstat_initstats(&r->pgstat_info, r);
 158
 159         return r;
 160 }
 161
 162 /* ----------------
 163  *              index_openr - open a system index relation specified by name.
 164  *
 165  *              As above, but the relation is specified by an unqualified name;
 166  *              it is assumed to live in the system catalog namespace.
 167  * ----------------
 168  */
 169 Relation
 170 index_openr(const char *sysRelationName)
 171 {
 172         Relation        r;
 173
 174         r = relation_openr(sysRelationName, NoLock);
 175
 176         if (r->rd_rel->relkind != RELKIND_INDEX)
 177                 elog(ERROR, "%s is not an index relation",
 178                          RelationGetRelationName(r));
 179
 180         pgstat_initstats(&r->pgstat_info, r);
 181
 182         return r;
 183 }
 184
 185 /* ----------------
 186  *              index_close - close a index relation
 187  *
 188  *              presently the relcache routines do all the work we need
 189  *              to open/close index relations.
 190  * ----------------
 191  */
 192 void
 193 index_close(Relation relation)
 194 {
 195         RelationClose(relation);
 196 }
 197
 198 /* ----------------
 199  *              index_insert - insert an index tuple into a relation
 200  * ----------------
 201  */
 202 InsertIndexResult
 203 index_insert(Relation indexRelation,
 204                          Datum *datums,
 205                          char *nulls,
 206                          ItemPointer heap_t_ctid,
 207                          Relation heapRelation,
 208                          bool check_uniqueness)
 209 {
 210         RegProcedure procedure;
 211         InsertIndexResult specificResult;
 212
 213         RELATION_CHECKS;
 214         GET_REL_PROCEDURE(insert, aminsert);
 215
 216         /*
 217          * have the am's insert proc do all the work.
 218          */
 219         specificResult = (InsertIndexResult)
 220                 DatumGetPointer(OidFunctionCall6(procedure,
 221                                                                                  PointerGetDatum(indexRelation),
 222                                                                                  PointerGetDatum(datums),
 223                                                                                  PointerGetDatum(nulls),
 224                                                                                  PointerGetDatum(heap_t_ctid),
 225                                                                                  PointerGetDatum(heapRelation),
 226                                                                                  BoolGetDatum(check_uniqueness)));
 227
 228         /* must be pfree'ed */
 229         return specificResult;
 230 }
 231
 232 /* ----------------
 233  *              index_beginscan - start a scan of an index
 234  *
 235  * Note: heapRelation may be NULL if there is no intention of calling
 236  * index_getnext on this scan; index_getnext_indexitem will not use the
 237  * heapRelation link (nor the snapshot).  However, the caller had better
 238  * be holding some kind of lock on the heap relation in any case, to ensure
 239  * no one deletes it (or the index) out from under us.
 240  * ----------------
 241  */
 242 IndexScanDesc
 243 index_beginscan(Relation heapRelation,
 244                                 Relation indexRelation,
 245                                 Snapshot snapshot,
 246                                 int nkeys, ScanKey key)
 247 {
 248         IndexScanDesc scan;
 249         RegProcedure procedure;
 250
 251         RELATION_CHECKS;
 252         GET_REL_PROCEDURE(beginscan, ambeginscan);
 253
 254         RelationIncrementReferenceCount(indexRelation);
 255
 256         /*
 257          * Acquire AccessShareLock for the duration of the scan
 258          *
 259          * Note: we could get an SI inval message here and consequently have to
 260          * rebuild the relcache entry.  The refcount increment above ensures
 261          * that we will rebuild it and not just flush it...
 262          */
 263         LockRelation(indexRelation, AccessShareLock);
 264
 265         /*
 266          * Tell the AM to open a scan.
 267          */
 268         scan = (IndexScanDesc)
 269                 DatumGetPointer(OidFunctionCall3(procedure,
 270                                                                                  PointerGetDatum(indexRelation),
 271                                                                                  Int32GetDatum(nkeys),
 272                                                                                  PointerGetDatum(key)));
 273
 274         /*
 275          * Save additional parameters into the scandesc.  Everything else was
 276          * set up by RelationGetIndexScan.
 277          */
 278         scan->heapRelation = heapRelation;
 279         scan->xs_snapshot = snapshot;
 280
 281         /*
 282          * We want to look up the amgettuple procedure just once per scan, not
 283          * once per index_getnext call.  So do it here and save the fmgr info
 284          * result in the scan descriptor.
 285          */
 286         GET_SCAN_PROCEDURE(beginscan, amgettuple);
 287         fmgr_info(procedure, &scan->fn_getnext);
 288
 289         return scan;
 290 }
 291
 292 /* ----------------
 293  *              index_rescan  - (re)start a scan of an index
 294  *
 295  * The caller may specify a new set of scankeys (but the number of keys
 296  * cannot change).      Note that this is also called when first starting
 297  * an indexscan; see RelationGetIndexScan.
 298  * ----------------
 299  */
 300 void
 301 index_rescan(IndexScanDesc scan, ScanKey key)
 302 {
 303         RegProcedure procedure;
 304
 305         SCAN_CHECKS;
 306         GET_SCAN_PROCEDURE(rescan, amrescan);
 307
 308         scan->kill_prior_tuple = false;         /* for safety */
 309         scan->keys_are_unique = false;          /* may be set by amrescan */
 310         scan->got_tuple = false;
 311
 312         OidFunctionCall2(procedure,
 313                                          PointerGetDatum(scan),
 314                                          PointerGetDatum(key));
 315
 316         pgstat_reset_index_scan(&scan->xs_pgstat_info);
 317 }
 318
 319 /* ----------------
 320  *              index_endscan - end a scan
 321  * ----------------
 322  */
 323 void
 324 index_endscan(IndexScanDesc scan)
 325 {
 326         RegProcedure procedure;
 327
 328         SCAN_CHECKS;
 329         GET_SCAN_PROCEDURE(endscan, amendscan);
 330
 331         /* Release any held pin on a heap page */
 332         if (BufferIsValid(scan->xs_cbuf))
 333         {
 334                 ReleaseBuffer(scan->xs_cbuf);
 335                 scan->xs_cbuf = InvalidBuffer;
 336         }
 337
 338         /* End the AM's scan */
 339         OidFunctionCall1(procedure, PointerGetDatum(scan));
 340
 341         /* Release index lock and refcount acquired by index_beginscan */
 342
 343         UnlockRelation(scan->indexRelation, AccessShareLock);
 344
 345         RelationDecrementReferenceCount(scan->indexRelation);
 346
 347         /* Release the scan data structure itself */
 348         IndexScanEnd(scan);
 349 }
 350
 351 /* ----------------
 352  *              index_markpos  - mark a scan position
 353  * ----------------
 354  */
 355 void
 356 index_markpos(IndexScanDesc scan)
 357 {
 358         RegProcedure procedure;
 359
 360         SCAN_CHECKS;
 361         GET_SCAN_PROCEDURE(markpos, ammarkpos);
 362
 363         OidFunctionCall1(procedure, PointerGetDatum(scan));
 364 }
 365
 366 /* ----------------
 367  *              index_restrpos  - restore a scan position
 368  * ----------------
 369  */
 370 void
 371 index_restrpos(IndexScanDesc scan)
 372 {
 373         RegProcedure procedure;
 374
 375         SCAN_CHECKS;
 376         GET_SCAN_PROCEDURE(restrpos, amrestrpos);
 377
 378         scan->kill_prior_tuple = false;         /* for safety */
 379         scan->got_tuple = false;
 380
 381         OidFunctionCall1(procedure, PointerGetDatum(scan));
 382 }
 383
 384 /* ----------------
 385  *              index_getnext - get the next heap tuple from a scan
 386  *
 387  * The result is the next heap tuple satisfying the scan keys and the
 388  * snapshot, or NULL if no more matching tuples exist.  On success,
 389  * the buffer containing the heap tuple is pinned (the pin will be dropped
 390  * at the next index_getnext or index_endscan).  The index TID corresponding
 391  * to the heap tuple can be obtained if needed from scan->currentItemData.
 392  * ----------------
 393  */
 394 HeapTuple
 395 index_getnext(IndexScanDesc scan, ScanDirection direction)
 396 {
 397         HeapTuple       heapTuple = &scan->xs_ctup;
 398
 399         SCAN_CHECKS;
 400
 401         /* Release any previously held pin */
 402         if (BufferIsValid(scan->xs_cbuf))
 403         {
 404                 ReleaseBuffer(scan->xs_cbuf);
 405                 scan->xs_cbuf = InvalidBuffer;
 406         }
 407
 408         /* just make sure this is false... */
 409         scan->kill_prior_tuple = false;
 410
 411         /*
 412          * Can skip entering the index AM if we already got a tuple and it
 413          * must be unique.
 414          */
 415         if (scan->keys_are_unique && scan->got_tuple)
 416                 return NULL;
 417
 418         for (;;)
 419         {
 420                 bool            found;
 421                 uint16          sv_infomask;
 422
 423                 pgstat_count_index_scan(&scan->xs_pgstat_info);
 424
 425                 /*
 426                  * The AM's gettuple proc finds the next tuple matching the scan
 427                  * keys.  index_beginscan already set up fn_getnext.
 428                  */
 429                 found = DatumGetBool(FunctionCall2(&scan->fn_getnext,
 430                                                                                    PointerGetDatum(scan),
 431                                                                                    Int32GetDatum(direction)));
 432
 433                 /* Reset kill flag immediately for safety */
 434                 scan->kill_prior_tuple = false;
 435
 436                 if (!found)
 437                         return NULL;            /* failure exit */
 438
 439                 /*
 440                  * Fetch the heap tuple and see if it matches the snapshot.
 441                  */
 442                 if (heap_fetch(scan->heapRelation, scan->xs_snapshot,
 443                                            heapTuple, &scan->xs_cbuf, true,
 444                                            &scan->xs_pgstat_info))
 445                         break;
 446
 447                 /* Skip if no tuple at this location */
 448                 if (heapTuple->t_data == NULL)
 449                         continue;                       /* should we raise an error instead? */
 450
 451                 /*
 452                  * If we can't see it, maybe no one else can either.  Check to see
 453                  * if the tuple is dead to all transactions.  If so, signal the
 454                  * index AM to not return it on future indexscans.
 455                  *
 456                  * We told heap_fetch to keep a pin on the buffer, so we can
 457                  * re-access the tuple here.  But we must re-lock the buffer
 458                  * first. Also, it's just barely possible for an update of hint
 459                  * bits to occur here.
 460                  */
 461                 LockBuffer(scan->xs_cbuf, BUFFER_LOCK_SHARE);
 462                 sv_infomask = heapTuple->t_data->t_infomask;
 463
 464                 if (HeapTupleSatisfiesVacuum(heapTuple->t_data, RecentGlobalXmin) ==
 465                         HEAPTUPLE_DEAD)
 466                         scan->kill_prior_tuple = true;
 467
 468                 if (sv_infomask != heapTuple->t_data->t_infomask)
 469                         SetBufferCommitInfoNeedsSave(scan->xs_cbuf);
 470                 LockBuffer(scan->xs_cbuf, BUFFER_LOCK_UNLOCK);
 471                 ReleaseBuffer(scan->xs_cbuf);
 472                 scan->xs_cbuf = InvalidBuffer;
 473         }
 474
 475         /* Success exit */
 476         scan->got_tuple = true;
 477
 478         pgstat_count_index_getnext(&scan->xs_pgstat_info);
 479
 480         return heapTuple;
 481 }
 482
 483 /* ----------------
 484  *              index_getnext_indexitem - get the next index tuple from a scan
 485  *
 486  * Finds the next index tuple satisfying the scan keys.  Note that the
 487  * corresponding heap tuple is not accessed, and thus no time qual (snapshot)
 488  * check is done, other than the index AM's internal check for killed tuples
 489  * (which most callers of this routine will probably want to suppress by
 490  * setting scan->ignore_killed_tuples = false).
 491  *
 492  * On success (TRUE return), the found index TID is in scan->currentItemData,
 493  * and its heap TID is in scan->xs_ctup.t_self.  scan->xs_cbuf is untouched.
 494  * ----------------
 495  */
 496 bool
 497 index_getnext_indexitem(IndexScanDesc scan,
 498                                                 ScanDirection direction)
 499 {
 500         bool            found;
 501
 502         SCAN_CHECKS;
 503
 504         /* just make sure this is false... */
 505         scan->kill_prior_tuple = false;
 506
 507         /*
 508          * have the am's gettuple proc do all the work. index_beginscan
 509          * already set up fn_getnext.
 510          */
 511         found = DatumGetBool(FunctionCall2(&scan->fn_getnext,
 512                                                                            PointerGetDatum(scan),
 513                                                                            Int32GetDatum(direction)));
 514
 515         return found;
 516 }
 517
 518 /* ----------------
 519  *              index_bulk_delete - do mass deletion of index entries
 520  *
 521  *              callback routine tells whether a given main-heap tuple is
 522  *              to be deleted
 523  *
 524  *              return value is an optional palloc'd struct of statistics
 525  * ----------------
 526  */
 527 IndexBulkDeleteResult *
 528 index_bulk_delete(Relation indexRelation,
 529                                   IndexBulkDeleteCallback callback,
 530                                   void *callback_state)
 531 {
 532         RegProcedure procedure;
 533         IndexBulkDeleteResult *result;
 534
 535         RELATION_CHECKS;
 536         GET_REL_PROCEDURE(bulk_delete, ambulkdelete);
 537
 538         result = (IndexBulkDeleteResult *)
 539                 DatumGetPointer(OidFunctionCall3(procedure,
 540                                                                                  PointerGetDatum(indexRelation),
 541                                                                          PointerGetDatum((Pointer) callback),
 542                                                                            PointerGetDatum(callback_state)));
 543
 544         return result;
 545 }
 546
 547 /* ----------------
 548  *              index_cost_estimator
 549  *
 550  *              Fetch the amcostestimate procedure OID for an index.
 551  *
 552  *              We could combine fetching and calling the procedure,
 553  *              as index_insert does for example; but that would require
 554  *              importing a bunch of planner/optimizer stuff into this file.
 555  * ----------------
 556  */
 557 RegProcedure
 558 index_cost_estimator(Relation indexRelation)
 559 {
 560         RegProcedure procedure;
 561
 562         RELATION_CHECKS;
 563         GET_REL_PROCEDURE(cost_estimator, amcostestimate);
 564
 565         return procedure;
 566 }
 567
 568 /* ----------------
 569  *              index_getprocid
 570  *
 571  *              Some indexed access methods may require support routines that are
 572  *              not in the operator class/operator model imposed by pg_am.      These
 573  *              access methods may store the OIDs of registered procedures they
 574  *              need in pg_amproc.      These registered procedure OIDs are ordered in
 575  *              a way that makes sense to the access method, and used only by the
 576  *              access method.  The general index code doesn't know anything about
 577  *              the routines involved; it just builds an ordered list of them for
 578  *              each attribute on which an index is defined.
 579  *
 580  *              This routine returns the requested procedure OID for a particular
 581  *              indexed attribute.
 582  * ----------------
 583  */
 584 RegProcedure
 585 index_getprocid(Relation irel,
 586                                 AttrNumber attnum,
 587                                 uint16 procnum)
 588 {
 589         RegProcedure *loc;
 590         int                     nproc;
 591         int                     procindex;
 592
 593         nproc = irel->rd_am->amsupport;
 594
 595         Assert(procnum > 0 && procnum <= (uint16) nproc);
 596
 597         procindex = (nproc * (attnum - 1)) + (procnum - 1);
 598
 599         loc = irel->rd_support;
 600
 601         Assert(loc != NULL);
 602
 603         return loc[procindex];
 604 }
 605
 606 /* ----------------
 607  *              index_getprocinfo
 608  *
 609  *              This routine allows index AMs to keep fmgr lookup info for
 610  *              support procs in the relcache.
 611  * ----------------
 612  */
 613 struct FmgrInfo *
 614 index_getprocinfo(Relation irel,
 615                                   AttrNumber attnum,
 616                                   uint16 procnum)
 617 {
 618         FmgrInfo   *locinfo;
 619         int                     nproc;
 620         int                     procindex;
 621
 622         nproc = irel->rd_am->amsupport;
 623
 624         Assert(procnum > 0 && procnum <= (uint16) nproc);
 625
 626         procindex = (nproc * (attnum - 1)) + (procnum - 1);
 627
 628         locinfo = irel->rd_supportinfo;
 629
 630         Assert(locinfo != NULL);
 631
 632         locinfo += procindex;
 633
 634         /* Initialize the lookup info if first time through */
 635         if (locinfo->fn_oid == InvalidOid)
 636         {
 637                 RegProcedure *loc = irel->rd_support;
 638                 RegProcedure procId;
 639
 640                 Assert(loc != NULL);
 641
 642                 procId = loc[procindex];
 643
 644                 /*
 645                  * Complain if function was not found during
 646                  * IndexSupportInitialize. This should not happen unless the
 647                  * system tables contain bogus entries for the index opclass.  (If
 648                  * an AM wants to allow a support function to be optional, it can
 649                  * use index_getprocid.)
 650                  */
 651                 if (!RegProcedureIsValid(procId))
 652                         elog(ERROR, "Missing support function %d for attribute %d of index %s",
 653                                  procnum, attnum, RelationGetRelationName(irel));
 654
 655                 fmgr_info_cxt(procId, locinfo, irel->rd_indexcxt);
 656         }
 657
 658         return locinfo;
 659 }