1 /*-------------------------------------------------------------------------
4 * general index access method routines
6 * Portions Copyright (c) 1996-2006, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
11 * $PostgreSQL: pgsql/src/backend/access/index/indexam.c,v 1.92 2006/05/02 22:25:10 tgl Exp $
14 * index_open - open an index relation by relation OID
15 * index_openrv - open an index relation specified by a RangeVar
16 * index_close - close an index relation
17 * index_beginscan - start a scan of an index with amgettuple
18 * index_beginscan_multi - start a scan of an index with amgetmulti
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_getmulti - get multiple tuples from a scan
26 * index_bulk_delete - bulk deletion of index tuples
27 * index_vacuum_cleanup - post-deletion cleanup of an index
28 * index_getprocid - get a support procedure OID
29 * index_getprocinfo - get a support procedure's lookup info
32 * This file contains the index_ routines which used
33 * to be a scattered collection of stuff in access/genam.
37 * Scans are implemented as follows:
39 * `0' represents an invalid item pointer.
40 * `-' represents an unknown item pointer.
41 * `X' represents a known item pointers.
42 * `+' represents known or invalid item pointers.
43 * `*' represents any item pointers.
45 * State is represented by a triple of these symbols in the order of
46 * previous, current, next. Note that the case of reverse scans works
50 * (1) + + - + 0 0 (if the next item pointer is invalid)
51 * (2) + X - (otherwise)
52 * (3) * 0 0 * 0 0 (no change)
53 * (4) + X 0 X 0 0 (shift)
54 * (5) * + X + X - (shift, add unknown)
56 * All other states cannot occur.
58 * Note: It would be possible to cache the status of the previous and
59 * next item pointer using the flags.
61 *-------------------------------------------------------------------------
66 #include "access/genam.h"
67 #include "access/heapam.h"
69 #include "utils/relcache.h"
72 /* ----------------------------------------------------------------
73 * macros used in index_ routines
74 * ----------------------------------------------------------------
76 #define RELATION_CHECKS \
78 AssertMacro(RelationIsValid(indexRelation)), \
79 AssertMacro(PointerIsValid(indexRelation->rd_am)) \
84 AssertMacro(IndexScanIsValid(scan)), \
85 AssertMacro(RelationIsValid(scan->indexRelation)), \
86 AssertMacro(PointerIsValid(scan->indexRelation->rd_am)) \
89 #define GET_REL_PROCEDURE(pname) \
91 procedure = &indexRelation->rd_aminfo->pname; \
92 if (!OidIsValid(procedure->fn_oid)) \
94 RegProcedure procOid = indexRelation->rd_am->pname; \
95 if (!RegProcedureIsValid(procOid)) \
96 elog(ERROR, "invalid %s regproc", CppAsString(pname)); \
97 fmgr_info_cxt(procOid, procedure, indexRelation->rd_indexcxt); \
101 #define GET_SCAN_PROCEDURE(pname) \
103 procedure = &scan->indexRelation->rd_aminfo->pname; \
104 if (!OidIsValid(procedure->fn_oid)) \
106 RegProcedure procOid = scan->indexRelation->rd_am->pname; \
107 if (!RegProcedureIsValid(procOid)) \
108 elog(ERROR, "invalid %s regproc", CppAsString(pname)); \
109 fmgr_info_cxt(procOid, procedure, scan->indexRelation->rd_indexcxt); \
113 static IndexScanDesc index_beginscan_internal(Relation indexRelation,
114 bool need_index_lock,
115 int nkeys, ScanKey key);
118 /* ----------------------------------------------------------------
119 * index_ interface functions
120 * ----------------------------------------------------------------
124 * index_open - open an index relation by relation OID
126 * Note: we acquire no lock on the index. A lock is not needed when
127 * simply examining the index reldesc; the index's schema information
128 * is considered to be protected by the lock that the caller had better
129 * be holding on the parent relation. Some type of lock should be
130 * obtained on the index before physically accessing it, however.
131 * This is handled automatically for most uses by index_beginscan
132 * and index_endscan for scan cases, or by ExecOpenIndices and
133 * ExecCloseIndices for update cases. Other callers will need to
134 * obtain their own locks.
136 * This is a convenience routine adapted for indexscan use.
137 * Some callers may prefer to use relation_open directly.
141 index_open(Oid relationId)
145 r = relation_open(relationId, NoLock);
147 if (r->rd_rel->relkind != RELKIND_INDEX)
149 (errcode(ERRCODE_WRONG_OBJECT_TYPE),
150 errmsg("\"%s\" is not an index",
151 RelationGetRelationName(r))));
153 pgstat_initstats(&r->pgstat_info, r);
159 * index_openrv - open an index relation specified
162 * As above, but relation is specified by a RangeVar.
166 index_openrv(const RangeVar *relation)
170 r = relation_openrv(relation, NoLock);
172 if (r->rd_rel->relkind != RELKIND_INDEX)
174 (errcode(ERRCODE_WRONG_OBJECT_TYPE),
175 errmsg("\"%s\" is not an index",
176 RelationGetRelationName(r))));
178 pgstat_initstats(&r->pgstat_info, r);
184 * index_close - close a index relation
186 * presently the relcache routines do all the work we need
187 * to open/close index relations.
191 index_close(Relation relation)
193 RelationClose(relation);
197 * index_insert - insert an index tuple into a relation
201 index_insert(Relation indexRelation,
204 ItemPointer heap_t_ctid,
205 Relation heapRelation,
206 bool check_uniqueness)
211 GET_REL_PROCEDURE(aminsert);
214 * have the am's insert proc do all the work.
216 return DatumGetBool(FunctionCall6(procedure,
217 PointerGetDatum(indexRelation),
218 PointerGetDatum(values),
219 PointerGetDatum(isnull),
220 PointerGetDatum(heap_t_ctid),
221 PointerGetDatum(heapRelation),
222 BoolGetDatum(check_uniqueness)));
226 * index_beginscan - start a scan of an index with amgettuple
228 * Note: heapRelation may be NULL if there is no intention of calling
229 * index_getnext on this scan; index_getnext_indexitem will not use the
230 * heapRelation link (nor the snapshot). However, the caller had better
231 * be holding some kind of lock on the heap relation in any case, to ensure
232 * no one deletes it (or the index) out from under us.
234 * Most callers should pass need_index_lock = true to cause the index code
235 * to take AccessShareLock on the index for the duration of the scan. But
236 * if it is known that a lock is already held on the index, pass false to
237 * skip taking an unnecessary lock.
240 index_beginscan(Relation heapRelation,
241 Relation indexRelation,
242 bool need_index_lock,
244 int nkeys, ScanKey key)
248 scan = index_beginscan_internal(indexRelation, need_index_lock,
252 * Save additional parameters into the scandesc. Everything else was set
253 * up by RelationGetIndexScan.
255 scan->is_multiscan = false;
256 scan->heapRelation = heapRelation;
257 scan->xs_snapshot = snapshot;
263 * index_beginscan_multi - start a scan of an index with amgetmulti
265 * As above, caller had better be holding some lock on the parent heap
266 * relation, even though it's not explicitly mentioned here.
269 index_beginscan_multi(Relation indexRelation,
270 bool need_index_lock,
272 int nkeys, ScanKey key)
276 scan = index_beginscan_internal(indexRelation, need_index_lock,
280 * Save additional parameters into the scandesc. Everything else was set
281 * up by RelationGetIndexScan.
283 scan->is_multiscan = true;
284 scan->xs_snapshot = snapshot;
290 * index_beginscan_internal --- common code for index_beginscan variants
293 index_beginscan_internal(Relation indexRelation,
294 bool need_index_lock,
295 int nkeys, ScanKey key)
302 RelationIncrementReferenceCount(indexRelation);
305 * Acquire AccessShareLock for the duration of the scan, unless caller
306 * says it already has lock on the index.
308 * Note: we could get an SI inval message here and consequently have to
309 * rebuild the relcache entry. The refcount increment above ensures that
310 * we will rebuild it and not just flush it...
313 LockRelation(indexRelation, AccessShareLock);
316 * LockRelation can clean rd_aminfo structure, so fill procedure after
320 GET_REL_PROCEDURE(ambeginscan);
323 * Tell the AM to open a scan.
325 scan = (IndexScanDesc)
326 DatumGetPointer(FunctionCall3(procedure,
327 PointerGetDatum(indexRelation),
328 Int32GetDatum(nkeys),
329 PointerGetDatum(key)));
331 /* Save flag to tell index_endscan whether to release lock */
332 scan->have_lock = need_index_lock;
338 * index_rescan - (re)start a scan of an index
340 * The caller may specify a new set of scankeys (but the number of keys
341 * cannot change). To restart the scan without changing keys, pass NULL
344 * Note that this is also called when first starting an indexscan;
345 * see RelationGetIndexScan. Keys *must* be passed in that case,
346 * unless scan->numberOfKeys is zero.
350 index_rescan(IndexScanDesc scan, ScanKey key)
355 GET_SCAN_PROCEDURE(amrescan);
357 /* Release any held pin on a heap page */
358 if (BufferIsValid(scan->xs_cbuf))
360 ReleaseBuffer(scan->xs_cbuf);
361 scan->xs_cbuf = InvalidBuffer;
364 scan->kill_prior_tuple = false; /* for safety */
365 scan->keys_are_unique = false; /* may be set by index AM */
366 scan->got_tuple = false;
367 scan->unique_tuple_pos = 0;
368 scan->unique_tuple_mark = 0;
370 FunctionCall2(procedure,
371 PointerGetDatum(scan),
372 PointerGetDatum(key));
376 * index_endscan - end a scan
380 index_endscan(IndexScanDesc scan)
385 GET_SCAN_PROCEDURE(amendscan);
387 /* Release any held pin on a heap page */
388 if (BufferIsValid(scan->xs_cbuf))
390 ReleaseBuffer(scan->xs_cbuf);
391 scan->xs_cbuf = InvalidBuffer;
394 /* End the AM's scan */
395 FunctionCall1(procedure, PointerGetDatum(scan));
397 /* Release index lock and refcount acquired by index_beginscan */
400 UnlockRelation(scan->indexRelation, AccessShareLock);
402 RelationDecrementReferenceCount(scan->indexRelation);
404 /* Release the scan data structure itself */
409 * index_markpos - mark a scan position
413 index_markpos(IndexScanDesc scan)
418 GET_SCAN_PROCEDURE(ammarkpos);
420 scan->unique_tuple_mark = scan->unique_tuple_pos;
422 FunctionCall1(procedure, PointerGetDatum(scan));
426 * index_restrpos - restore a scan position
428 * NOTE: this only restores the internal scan state of the index AM.
429 * The current result tuple (scan->xs_ctup) doesn't change. See comments
430 * for ExecRestrPos().
434 index_restrpos(IndexScanDesc scan)
439 GET_SCAN_PROCEDURE(amrestrpos);
441 scan->kill_prior_tuple = false; /* for safety */
444 * We do not reset got_tuple; so if the scan is actually being
445 * short-circuited by index_getnext, the effective position restoration is
446 * done by restoring unique_tuple_pos.
448 scan->unique_tuple_pos = scan->unique_tuple_mark;
450 FunctionCall1(procedure, PointerGetDatum(scan));
454 * index_getnext - get the next heap tuple from a scan
456 * The result is the next heap tuple satisfying the scan keys and the
457 * snapshot, or NULL if no more matching tuples exist. On success,
458 * the buffer containing the heap tuple is pinned (the pin will be dropped
459 * at the next index_getnext or index_endscan). The index TID corresponding
460 * to the heap tuple can be obtained if needed from scan->currentItemData.
464 index_getnext(IndexScanDesc scan, ScanDirection direction)
466 HeapTuple heapTuple = &scan->xs_ctup;
470 GET_SCAN_PROCEDURE(amgettuple);
473 * If we already got a tuple and it must be unique, there's no need to
474 * make the index AM look through any additional tuples. (This can save a
475 * useful amount of work in scenarios where there are many dead tuples due
476 * to heavy update activity.)
478 * To do this we must keep track of the logical scan position
479 * (before/on/after tuple). Also, we have to be sure to release scan
480 * resources before returning NULL; if we fail to do so then a multi-index
481 * scan can easily run the system out of free buffers. We can release
482 * index-level resources fairly cheaply by calling index_rescan. This
483 * means there are two persistent states as far as the index AM is
484 * concerned: on-tuple and rescanned. If we are actually asked to
485 * re-fetch the single tuple, we have to go through a fresh indexscan
486 * startup, which penalizes that (infrequent) case.
488 if (scan->keys_are_unique && scan->got_tuple)
490 int new_tuple_pos = scan->unique_tuple_pos;
492 if (ScanDirectionIsForward(direction))
494 if (new_tuple_pos <= 0)
499 if (new_tuple_pos >= 0)
502 if (new_tuple_pos == 0)
505 * We are moving onto the unique tuple from having been off it. We
506 * just fall through and let the index AM do the work. Note we
507 * should get the right answer regardless of scan direction.
509 scan->unique_tuple_pos = 0; /* need to update position */
514 * Moving off the tuple; must do amrescan to release index-level
515 * pins before we return NULL. Since index_rescan will reset my
516 * state, must save and restore...
518 int unique_tuple_mark = scan->unique_tuple_mark;
520 index_rescan(scan, NULL /* no change to key */ );
522 scan->keys_are_unique = true;
523 scan->got_tuple = true;
524 scan->unique_tuple_pos = new_tuple_pos;
525 scan->unique_tuple_mark = unique_tuple_mark;
531 /* just make sure this is false... */
532 scan->kill_prior_tuple = false;
539 * The AM's gettuple proc finds the next tuple matching the scan keys.
541 found = DatumGetBool(FunctionCall2(procedure,
542 PointerGetDatum(scan),
543 Int32GetDatum(direction)));
545 /* Reset kill flag immediately for safety */
546 scan->kill_prior_tuple = false;
550 /* Release any held pin on a heap page */
551 if (BufferIsValid(scan->xs_cbuf))
553 ReleaseBuffer(scan->xs_cbuf);
554 scan->xs_cbuf = InvalidBuffer;
556 return NULL; /* failure exit */
559 pgstat_count_index_tuples(&scan->xs_pgstat_info, 1);
562 * Fetch the heap tuple and see if it matches the snapshot.
564 if (heap_release_fetch(scan->heapRelation, scan->xs_snapshot,
565 heapTuple, &scan->xs_cbuf, true,
566 &scan->xs_pgstat_info))
569 /* Skip if no undeleted tuple at this location */
570 if (heapTuple->t_data == NULL)
574 * If we can't see it, maybe no one else can either. Check to see if
575 * the tuple is dead to all transactions. If so, signal the index AM
576 * to not return it on future indexscans.
578 * We told heap_release_fetch to keep a pin on the buffer, so we can
579 * re-access the tuple here. But we must re-lock the buffer first.
581 LockBuffer(scan->xs_cbuf, BUFFER_LOCK_SHARE);
583 if (HeapTupleSatisfiesVacuum(heapTuple->t_data, RecentGlobalXmin,
584 scan->xs_cbuf) == HEAPTUPLE_DEAD)
585 scan->kill_prior_tuple = true;
587 LockBuffer(scan->xs_cbuf, BUFFER_LOCK_UNLOCK);
591 scan->got_tuple = true;
594 * If we just fetched a known-unique tuple, then subsequent calls will go
595 * through the short-circuit code above. unique_tuple_pos has been
596 * initialized to 0, which is the correct state ("on row").
603 * index_getnext_indexitem - get the next index tuple from a scan
605 * Finds the next index tuple satisfying the scan keys. Note that the
606 * corresponding heap tuple is not accessed, and thus no time qual (snapshot)
607 * check is done, other than the index AM's internal check for killed tuples
608 * (which most callers of this routine will probably want to suppress by
609 * setting scan->ignore_killed_tuples = false).
611 * On success (TRUE return), the found index TID is in scan->currentItemData,
612 * and its heap TID is in scan->xs_ctup.t_self. scan->xs_cbuf is untouched.
616 index_getnext_indexitem(IndexScanDesc scan,
617 ScanDirection direction)
623 GET_SCAN_PROCEDURE(amgettuple);
625 /* just make sure this is false... */
626 scan->kill_prior_tuple = false;
629 * have the am's gettuple proc do all the work.
631 found = DatumGetBool(FunctionCall2(procedure,
632 PointerGetDatum(scan),
633 Int32GetDatum(direction)));
636 pgstat_count_index_tuples(&scan->xs_pgstat_info, 1);
642 * index_getmulti - get multiple tuples from an index scan
644 * Collects the TIDs of multiple heap tuples satisfying the scan keys.
645 * Since there's no interlock between the index scan and the eventual heap
646 * access, this is only safe to use with MVCC-based snapshots: the heap
647 * item slot could have been replaced by a newer tuple by the time we get
650 * A TRUE result indicates more calls should occur; a FALSE result says the
651 * scan is done. *returned_tids could be zero or nonzero in either case.
655 index_getmulti(IndexScanDesc scan,
656 ItemPointer tids, int32 max_tids,
657 int32 *returned_tids)
663 GET_SCAN_PROCEDURE(amgetmulti);
665 /* just make sure this is false... */
666 scan->kill_prior_tuple = false;
669 * have the am's getmulti proc do all the work.
671 found = DatumGetBool(FunctionCall4(procedure,
672 PointerGetDatum(scan),
673 PointerGetDatum(tids),
674 Int32GetDatum(max_tids),
675 PointerGetDatum(returned_tids)));
677 pgstat_count_index_tuples(&scan->xs_pgstat_info, *returned_tids);
683 * index_bulk_delete - do mass deletion of index entries
685 * callback routine tells whether a given main-heap tuple is
688 * return value is an optional palloc'd struct of statistics
691 IndexBulkDeleteResult *
692 index_bulk_delete(IndexVacuumInfo *info,
693 IndexBulkDeleteResult *stats,
694 IndexBulkDeleteCallback callback,
695 void *callback_state)
697 Relation indexRelation = info->index;
699 IndexBulkDeleteResult *result;
702 GET_REL_PROCEDURE(ambulkdelete);
704 result = (IndexBulkDeleteResult *)
705 DatumGetPointer(FunctionCall4(procedure,
706 PointerGetDatum(info),
707 PointerGetDatum(stats),
708 PointerGetDatum((Pointer) callback),
709 PointerGetDatum(callback_state)));
715 * index_vacuum_cleanup - do post-deletion cleanup of an index
717 * return value is an optional palloc'd struct of statistics
720 IndexBulkDeleteResult *
721 index_vacuum_cleanup(IndexVacuumInfo *info,
722 IndexBulkDeleteResult *stats)
724 Relation indexRelation = info->index;
726 IndexBulkDeleteResult *result;
729 GET_REL_PROCEDURE(amvacuumcleanup);
731 result = (IndexBulkDeleteResult *)
732 DatumGetPointer(FunctionCall2(procedure,
733 PointerGetDatum(info),
734 PointerGetDatum(stats)));
742 * Some indexed access methods may require support routines that are
743 * not in the operator class/operator model imposed by pg_am. These
744 * access methods may store the OIDs of registered procedures they
745 * need in pg_amproc. These registered procedure OIDs are ordered in
746 * a way that makes sense to the access method, and used only by the
747 * access method. The general index code doesn't know anything about
748 * the routines involved; it just builds an ordered list of them for
749 * each attribute on which an index is defined.
751 * This routine returns the requested procedure OID for a particular
756 index_getprocid(Relation irel,
764 nproc = irel->rd_am->amsupport;
766 Assert(procnum > 0 && procnum <= (uint16) nproc);
768 procindex = (nproc * (attnum - 1)) + (procnum - 1);
770 loc = irel->rd_support;
774 return loc[procindex];
780 * This routine allows index AMs to keep fmgr lookup info for
781 * support procs in the relcache.
783 * Note: the return value points into cached data that will be lost during
784 * any relcache rebuild! Therefore, either use the callinfo right away,
785 * or save it only after having acquired some type of lock on the index rel.
789 index_getprocinfo(Relation irel,
797 nproc = irel->rd_am->amsupport;
799 Assert(procnum > 0 && procnum <= (uint16) nproc);
801 procindex = (nproc * (attnum - 1)) + (procnum - 1);
803 locinfo = irel->rd_supportinfo;
805 Assert(locinfo != NULL);
807 locinfo += procindex;
809 /* Initialize the lookup info if first time through */
810 if (locinfo->fn_oid == InvalidOid)
812 RegProcedure *loc = irel->rd_support;
817 procId = loc[procindex];
820 * Complain if function was not found during IndexSupportInitialize.
821 * This should not happen unless the system tables contain bogus
822 * entries for the index opclass. (If an AM wants to allow a support
823 * function to be optional, it can use index_getprocid.)
825 if (!RegProcedureIsValid(procId))
826 elog(ERROR, "missing support function %d for attribute %d of index \"%s\"",
827 procnum, attnum, RelationGetRelationName(irel));
829 fmgr_info_cxt(procId, locinfo, irel->rd_indexcxt);