PostgreSQL Index Access Method — IndexAmRoutine and the Generic Index Layer

Contents:

• Theoretical Background
• Common DBMS Design
• PostgreSQL’s Approach
• Source Walkthrough
• Source verification (as of 2026-06-05)
• Beyond PostgreSQL — Comparative Designs & Research Frontiers
• Sources

Theoretical Background

An index is a redundant data structure that trades storage for lookup speed. The theoretical treatment starts from the observation that a sequential scan of a relation costs O(n) in the number of pages, and that an ordered or hashed auxiliary structure can reduce point-lookup and range-lookup costs to O(log n) or O(1) — at the cost of maintaining the structure on every write and consuming additional storage (Database System Concepts, Silberschatz et al., 7e, ch. 14 “Indexing”; Database Internals, Petrov, ch. 6 “B-Tree Variants”).

Three index families cover nearly all practical cases:

1. Ordered tree indexes (B+-tree family). Support equality, range, and prefix scans. The B+-tree from Bayer & McCreight 1972, later formalized as the structure behind most production DBMS indexes, is the canonical example. Lookups walk the tree; insertions and deletions keep the tree balanced through page splits and merges.
2. Hash indexes. Support equality only but can offer O(1) amortized lookup. PostgreSQL’s hash AM builds on Litwin 1980 linear hashing (extendible over pages); it has been WAL-logged since PostgreSQL 10.
3. Multidimensional / approximate indexes (GiST, GIN, SP-GiST, BRIN). These cover geometric search, full-text, sparse multi-key, and block-range summaries. Each uses its own internal structure; what they share with btree is the contract to the query executor — the same IndexAmRoutine interface.

The design question at the system level is whether these structurally distinct index types should share a query-executor-facing interface. The alternative — hardwiring the executor to call btree functions directly — would make adding a new index type require patching the planner, executor, DDL layer, and optimizer cost model. A generic index access method interface separates those concerns: the executor and planner deal with a stable set of operations (build, insert, begin-scan, get-next-tid, get-bitmap, vacuum), and each index AM fills in the implementation behind that interface.

This is the same vtable dispatch pattern that TableAmRoutine uses for table storage (see postgres-table-am.md), but the Index AM API is older and its shape influenced the table AM design.

Common DBMS Design

Several engineering conventions recur across database systems that expose a generic index layer.

Capability flags on the routine struct

Not all index types support the same operations. A hash index cannot be used for range scans or ORDER BY; a BRIN index is lossy and cannot return exact TIDs without a recheck; a GIN index supports full-text multi-key queries that a btree does not. The convention is to embed boolean capability flags directly in the vtable struct. Planner and DDL code reads the flags (amcanorder, amsearcharray, amsummarizing, ampredlocks, …) to decide whether a given AM can serve a given query or satisfy a constraint, without calling into the AM at all.

This is more expressive than a mandatory/optional callback split alone: an AM can fill in amgettuple but set amcanbackward = false, telling the system “I can return tuples one by one but not in reverse order.” The flags are the first-class negotiation mechanism between the AM and the planner.

Two scan modes: tuple-at-a-time vs. bitmap

Index scans come in two shapes that require different executor pipelines:

• amgettuple (tuple-at-a-time). The AM returns one heap TID per call. The executor immediately fetches that heap tuple, checks visibility, and, if visible, returns it to the upper plan node. Ordering is preserved. Suitable when the index is highly selective or when the plan needs ORDER BY from the index.
• amgetbitmap (bitmap). The AM fills a TIDBitmap with all qualifying TIDs in a single call, then returns the count. The executor heap-scans each page mentioned in the bitmap exactly once (BitmapHeapScan), amortizing random I/O across many TIDs per page. Ordering is not preserved. Used when selectivity is lower or when multiple indexes are combined (bitmap OR / AND).

An AM may support one or both. amgettuple and amgetbitmap are both NULL-able; the planner checks amcanorder and the AM’s capability to choose the scan mode.

Index-only scan

When all columns needed by the query are present in the index (either key columns or INCLUDE columns), the executor can return the index tuple directly without fetching the heap — an index-only scan. The AM signals this capability per column through amcanreturn. The executor still checks the visibility map; a page not yet all-visible requires a heap fetch to confirm the tuple’s visibility (the xs_recheck flag).

Opclass / operator-family negotiation

An index AM does not operate on arbitrary data types directly. It defines a set of strategies (numbered operations: BTLessStrategyNumber = 1, …) and support functions (internal helpers: comparison, hashing, consistency check). An operator class (pg_opclass) maps a data type onto a specific set of operators and support functions for one AM. An operator family (pg_opfamily) groups related opclasses that share comparison semantics, enabling cross-type comparisons.

This indirection means the same btree AM code handles int4, text, timestamp, and any user-defined type that provides the right support functions. The AM carries amstrategies (count of strategies) and amsupport (count of support functions) in the routine struct, and index_getprocid / index_getprocinfo look up the per-attribute support function at runtime.

Theory ↔ PostgreSQL Index AM mapping

Design concept	PostgreSQL Index AM name
Index AM vtable	IndexAmRoutine (in amapi.h)
Vtable on relation	Relation.rd_indam (relcache field)
AM capability flags	boolean fields in IndexAmRoutine (e.g., amcanorder)
Tuple-at-a-time scan callback	amgettuple
Bitmap scan callback	amgetbitmap
Index-only scan capability	amcanreturn (per-column callback)
Scan descriptor	IndexScanDescData (in relscan.h)
Strategy number → compare type	amtranslatestrategy callback
Opclass validation	amvalidate callback
AM registration factory	GetIndexAmRoutine (in amapi.c)
Generic wrappers	index_* functions in indexam.c

PostgreSQL’s Approach

How the AM gets onto the relation

When the relcache builds an index relation entry, it reads pg_am.amhandler from the index’s pg_class row, calls GetIndexAmRoutine(amhandler), and stores the returned IndexAmRoutine * in rel->rd_indam. Every subsequent index_* call on that relation dispatches through this pointer via the RELATION_CHECKS / SCAN_CHECKS macros that assert rd_indam != NULL and check that the index is not currently being reindexed.

flowchart TB
  IREL["Index Relation (relcache)\nrd_indam → IndexAmRoutine *"]
  EXEC["Executor / Vacuum\n(nodeIndexscan, nodeBitmapIndexscan,\nindex_bulk_delete)"]
  WRAP["index_* wrappers\n(indexam.c)"]
  AM["IndexAmRoutine\n(ambeginscan, amgettuple,\namgetbitmap, ambulkdelete, …)"]
  IMPL["AM implementation\n(nbtree, hash, gist, gin, spgist, brin)"]
  HEAP["table_index_fetch_tuple\n(tableam.h → heapam_handler.c)"]

  EXEC --> WRAP
  WRAP --> AM
  AM --> IMPL
  WRAP --> HEAP
  IREL --> AM

Figure 1 — Index AM dispatch chain. The executor calls index_* wrappers in indexam.c; each wrapper checks preconditions and dispatches through rd_indam. For tuple-at-a-time scans, index_fetch_heap calls table_index_fetch_tuple on the heap side to resolve a TID to a visible tuple.

IndexAmRoutine — the struct and its capability flags

IndexAmRoutine is declared in src/include/access/amapi.h at line 230. It begins with integer counts and boolean capability flags, then lists the callback function pointers.

// IndexAmRoutine — src/include/access/amapi.h
typedef struct IndexAmRoutine
{
    NodeTag     type;

    uint16      amstrategies;       /* # of strategy operators, 0 if variable */
    uint16      amsupport;          /* # of support functions */
    uint16      amoptsprocnum;      /* opclass options support func number, or 0 */

    /* capability flags */
    bool        amcanorder;         /* supports ORDER BY indexed value? */
    bool        amcanorderbyop;     /* supports ORDER BY result of operator? */
    bool        amcanhash;          /* supports hash-consistent equality? */
    bool        amcanbackward;      /* supports backward scanning? */
    bool        amcanunique;        /* supports UNIQUE indexes? */
    bool        amcanmulticol;      /* supports multi-column indexes? */
    bool        amoptionalkey;      /* first column constraint required? */
    bool        amsearcharray;      /* handles ScalarArrayOpExpr quals? */
    bool        amsearchnulls;      /* handles IS NULL / IS NOT NULL? */
    bool        amstorage;          /* can index storage type differ from col type? */
    bool        amclusterable;      /* can cluster on this index? */
    bool        ampredlocks;        /* handles predicate locks internally? */
    bool        amcanparallel;      /* supports parallel scan? */
    bool        amcanbuildparallel; /* supports parallel build? */
    bool        amcaninclude;       /* supports INCLUDE columns? */
    bool        amsummarizing;      /* stores data at block granularity only? */
    /* ... more fields ... */

    /* interface functions */
    ambuild_function        ambuild;
    ambuildempty_function   ambuildempty;
    aminsert_function       aminsert;
    aminsertcleanup_function aminsertcleanup; /* can be NULL */
    ambulkdelete_function   ambulkdelete;
    amvacuumcleanup_function amvacuumcleanup;
    amcanreturn_function    amcanreturn;       /* can be NULL */
    amcostestimate_function amcostestimate;
    amoptions_function      amoptions;
    amvalidate_function     amvalidate;
    ambeginscan_function    ambeginscan;
    amrescan_function       amrescan;
    amgettuple_function     amgettuple;        /* can be NULL */
    amgetbitmap_function    amgetbitmap;        /* can be NULL */
    amendscan_function      amendscan;
    ammarkpos_function      ammarkpos;          /* can be NULL */
    amrestrpos_function     amrestrpos;         /* can be NULL */
    /* ... parallel scan and strategy-translation callbacks ... */
} IndexAmRoutine;

The ampredlocks flag is notable: when true, the AM handles predicate locking internally (as btree does via CheckForSerializableConflictIn). When false, index_insert and index_beginscan_internal call into the predicate-locking layer themselves, so the AM gets SSI support for free.

GetIndexAmRoutine and GetIndexAmRoutineByAmId

GetIndexAmRoutine (in amapi.c) calls the handler OID function and validates the result is an IndexAmRoutine node:

// GetIndexAmRoutine — src/backend/access/index/amapi.c
IndexAmRoutine *
GetIndexAmRoutine(Oid amhandler)
{
    Datum         datum   = OidFunctionCall0(amhandler);
    IndexAmRoutine *routine = (IndexAmRoutine *) DatumGetPointer(datum);

    if (routine == NULL || !IsA(routine, IndexAmRoutine))
        elog(ERROR, "index access method handler function %u did not return "
             "an IndexAmRoutine struct", amhandler);

    return routine;
}

Unlike GetTableAmRoutine, GetIndexAmRoutine does not assert individual callback slots — there are no mandatory-callback asserts. The RELATION_CHECKS and CHECK_REL_PROCEDURE macros in indexam.c check each specific callback immediately before it is called, producing a clean error rather than a null dereference.

GetIndexAmRoutineByAmId looks up the AM by OID in pg_am, validates that it is AMTYPE_INDEX, fetches the handler OID, and calls GetIndexAmRoutine.

IndexScanDescData — the scan descriptor

IndexScanDescData (in relscan.h, line 133) is the base descriptor used by both amgettuple and amgetbitmap scans. Key fields:

// IndexScanDescData — src/include/access/relscan.h (condensed)
typedef struct IndexScanDescData
{
    Relation    heapRelation;   /* heap relation, or NULL for bitmap */
    Relation    indexRelation;  /* index relation */
    struct SnapshotData *xs_snapshot;  /* snapshot to see */

    /* ... nkeys, orderbykeys, scankeys ... */

    bool        kill_prior_tuple; /* last-returned tuple is dead */
    bool        xs_heap_continue; /* must keep walking HOT chain */

    /* for index-only scans */
    IndexTuple  xs_itup;        /* index tuple returned by AM */
    HeapTuple   xs_hitup;       /* index data returned as HeapTuple */
    ItemPointerData xs_heaptid; /* TID result from amgettuple */

    bool        xs_recheck;     /* scan keys must be rechecked on heap */
    bool        xs_recheckorderby; /* ORDER BY distances must be rechecked */

    struct ParallelIndexScanDescData *parallel_scan; /* NULL if not parallel */
}   IndexScanDescData;

xs_heaptid is where amgettuple writes the TID it found. xs_heap_continue is the HOT-chain flag: when the AM sets it (or when index_fetch_heap sets it via the call_again output from table_index_fetch_tuple), index_getnext_slot re-enters index_fetch_heap for the same TID before fetching the next one from the index.

RelationGetIndexScan (in genam.c) allocates and zeroes the descriptor; AMs call this from their ambeginscan callback.

Scan lifecycle: index_beginscan → index_getnext_slot → index_endscan

index_beginscan allocates the IndexScanDesc, calls ambeginscan, stores the heap relation, snapshot, and instrument pointer, and opens a table_index_fetch_begin handle on the heap side. The heap-fetch handle (xs_heapfetch) is a IndexFetchTableData * used by every subsequent index_fetch_heap call.

flowchart TD
  BS["index_beginscan\n(indexam.c:256)"] --> AI["ambeginscan\nAM allocates scan state"]
  AI --> HF["table_index_fetch_begin\nopen heap-fetch handle"]
  HF --> RS["index_rescan\namrescan sets scan keys"]
  RS --> LOOP["index_getnext_slot loop"]
  LOOP --> GT["index_getnext_tid\namgettuple → xs_heaptid"]
  GT --> FH["index_fetch_heap\ntable_index_fetch_tuple\n→ xs_heap_continue"]
  FH --> RET["return slot to executor"]
  FH --> LOOP
  GT --> DONE["tid == NULL → done"]
  DONE --> ES["index_endscan\namendscan + table_index_fetch_end\n+ IndexScanEnd"]

Figure 2 — Index scan lifecycle. index_beginscan opens both the AM scan and the heap-fetch handle. The inner loop in index_getnext_slot alternates between index_getnext_tid (for the next TID) and index_fetch_heap (to resolve it), looping on xs_heap_continue when a HOT chain has more members.

The loop in index_getnext_slot:

// index_getnext_slot — src/backend/access/index/indexam.c
bool
index_getnext_slot(IndexScanDesc scan, ScanDirection direction,
                   TupleTableSlot *slot)
{
    for (;;)
    {
        if (!scan->xs_heap_continue)
        {
            ItemPointer tid = index_getnext_tid(scan, direction);
            if (tid == NULL)
                break;
        }
        if (index_fetch_heap(scan, slot))
            return true;
    }
    return false;
}

The xs_heap_continue flag is reset to false in index_getnext_tid after each new TID fetch, and set to true by index_fetch_heap when the heap AM’s table_index_fetch_tuple signals call_again (i.e., the HOT chain has more members for this TID).

index_getnext_tid and the kill_prior_tuple feedback

index_getnext_tid drives amgettuple and feeds back dead-tuple information:

// index_getnext_tid — src/backend/access/index/indexam.c (condensed)
ItemPointer
index_getnext_tid(IndexScanDesc scan, ScanDirection direction)
{
    bool found = scan->indexRelation->rd_indam->amgettuple(scan, direction);

    scan->kill_prior_tuple = false;
    scan->xs_heap_continue = false;

    if (!found) {
        if (scan->xs_heapfetch)
            table_index_fetch_reset(scan->xs_heapfetch);
        return NULL;
    }
    pgstat_count_index_tuples(scan->indexRelation, 1);
    return &scan->xs_heaptid;
}

kill_prior_tuple is set by index_fetch_heap when table_index_fetch_tuple reports all_dead = true (no backend can see any tuple in the HOT chain at this TID). On the next amgettuple call the AM sees kill_prior_tuple = true and marks the index entry as dead — deferring the physical removal to the next vacuum pass.

index_fetch_heap — resolving a TID to a visible tuple

// index_fetch_heap — src/backend/access/index/indexam.c (condensed)
bool
index_fetch_heap(IndexScanDesc scan, TupleTableSlot *slot)
{
    bool all_dead = false;

    bool found = table_index_fetch_tuple(scan->xs_heapfetch,
                                         &scan->xs_heaptid,
                                         scan->xs_snapshot,
                                         slot,
                                         &scan->xs_heap_continue,
                                         &all_dead);
    if (found)
        pgstat_count_heap_fetch(scan->indexRelation);

    if (!scan->xactStartedInRecovery)
        scan->kill_prior_tuple = all_dead;

    return found;
}

The heap-side table_index_fetch_tuple walks the HOT chain for the given TID under the scan’s snapshot and returns the first visible tuple. If the heap AM sets xs_heap_continue, index_getnext_slot will call index_fetch_heap again (without fetching a new TID) to get the next member of the chain.

index_insert and predicate locking

index_insert is the write path. It checks whether the AM handles predicate locks itself (ampredlocks); if not, it calls CheckForSerializableConflictIn before dispatching to aminsert:

// index_insert — src/backend/access/index/indexam.c
bool
index_insert(Relation indexRelation,
             Datum *values, bool *isnull,
             ItemPointer heap_t_ctid,
             Relation heapRelation,
             IndexUniqueCheck checkUnique,
             bool indexUnchanged,
             IndexInfo *indexInfo)
{
    RELATION_CHECKS;
    CHECK_REL_PROCEDURE(aminsert);

    if (!(indexRelation->rd_indam->ampredlocks))
        CheckForSerializableConflictIn(indexRelation,
                                       (ItemPointer) NULL,
                                       InvalidBlockNumber);

    return indexRelation->rd_indam->aminsert(indexRelation, values, isnull,
                                             heap_t_ctid, heapRelation,
                                             checkUnique, indexUnchanged,
                                             indexInfo);
}

IndexUniqueCheck is the enum controlling uniqueness enforcement: UNIQUE_CHECK_NO (no check), UNIQUE_CHECK_YES (immediate, possibly blocking), UNIQUE_CHECK_PARTIAL (test but don’t error — for deferred constraints), and UNIQUE_CHECK_EXISTING (recheck an already-inserted tuple).

Bitmap scan path: index_getbitmap

Bitmap scans bypass index_getnext_tid and index_fetch_heap entirely. The AM fills a TIDBitmap in one call:

// index_getbitmap — src/backend/access/index/indexam.c
int64
index_getbitmap(IndexScanDesc scan, TIDBitmap *bitmap)
{
    SCAN_CHECKS;
    CHECK_SCAN_PROCEDURE(amgetbitmap);
    scan->kill_prior_tuple = false;
    int64 ntids = scan->indexRelation->rd_indam->amgetbitmap(scan, bitmap);
    pgstat_count_index_tuples(scan->indexRelation, ntids);
    return ntids;
}

The BitmapIndexScan executor node calls this; the BitmapHeapScan node above it then iterates pages from the bitmap and calls table_scan_getnextslot with SO_TYPE_BITMAPSCAN.

Vacuum path: ambulkdelete and amvacuumcleanup

Vacuum drives the index via two callbacks:

1. ambulkdelete — called repeatedly, passing a dead-TID callback. The AM walks the index and calls the callback for each entry; if the callback returns true, the entry is dead and should be removed. Returns statistics (IndexBulkDeleteResult).
2. amvacuumcleanup — called once after all ambulkdelete passes. Used for post-deletion compaction (btree page recycling, GIN pending-list processing). Also called with analyze_only = true for ANALYZE.

IndexVacuumInfo carries the heap relation, the index, and vacuum parameters. The IndexBulkDeleteResult struct accumulates pages remaining, tuples removed, and dead/free page counts — fed back into pg_class statistics.

opclass and opfamily support: index_getprocid / index_getprocinfo

Support functions are stored in pg_amproc and cached in the relcache rd_support array. index_getprocid returns the RegProcedure OID for a given (attnum, procnum) pair; index_getprocinfo returns a fully-resolved FmgrInfo * (cached in rd_supportinfo) with opclass-option Const nodes pre-initialized.

// index_getprocid — src/backend/access/index/indexam.c (condensed)
RegProcedure
index_getprocid(Relation irel, AttrNumber attnum, uint16 procnum)
{
    int nproc     = irel->rd_indam->amsupport;
    int procindex = (nproc * (attnum - 1)) + (procnum - 1);
    return irel->rd_support[procindex];
}

The flat layout rd_support[(amsupport * (attnum - 1)) + (procnum - 1)] lets AMs look up a support function with two multiplications and one array access.

amtranslatestrategy / amtranslatecmptype (PG18 addition)

Two new optional callbacks in REL_18 support generic comparison type translation:

• amtranslatestrategy(strategy, opfamily) → CompareType — converts an AM strategy number (e.g., BTLessStrategyNumber = 1) to a generic CompareType (COMPARE_LT = 1). For btree, a direct cast suffices; IndexAmTranslateStrategy takes a fast path that avoids an AM call for btree.
• amtranslatecmptype(cmptype, opfamily) → StrategyNumber — the reverse.

These let the planner reason about ordering and join conditions using a AM-agnostic compare-type vocabulary without importing AM-specific strategy constants.

Source Walkthrough

Anchor on symbol names, not line numbers. The position-hint table below records line numbers observed at commit 273fe94 (REL_18_STABLE, 2026-06-05) as quick hints only — use git grep -n '<symbol>' to find the current position.

AM interface definition (src/include/access/amapi.h)

• typedef struct IndexAmRoutine — the ~30-slot vtable with capability flags and callback pointers.
• IndexAMProperty — enum of properties queryable via pg_indexam_has_property and pg_index_has_property; includes AMPROP_ORDERABLE, AMPROP_SEARCH_NULLS, AMPROP_CLUSTERABLE, etc.
• typedef struct OpFamilyMember — used by amadjustmembers to describe dependency types for opclass / opfamily members.
• Callback typedefs: ambuild_function, aminsert_function, ambulkdelete_function, amvacuumcleanup_function, ambeginscan_function, amrescan_function, amgettuple_function, amgetbitmap_function, amendscan_function, and parallel-scan variants.
• GetIndexAmRoutine(Oid amhandler) — factory; returns IndexAmRoutine *.
• GetIndexAmRoutineByAmId(Oid amoid, bool noerror) — looks up by AM OID.

Generic index wrappers (src/backend/access/index/indexam.c)

• index_open / index_close — thin wrappers around relation_open / relation_close; validate relkind is RELKIND_INDEX or RELKIND_PARTITIONED_INDEX.
• index_insert — write path; checks ampredlocks, calls aminsert.
• index_insert_cleanup — calls aminsertcleanup if non-NULL; used after bulk inserts.
• index_beginscan / index_beginscan_bitmap — open a scan; the former also calls table_index_fetch_begin; both call index_beginscan_internal.
• index_rescan — update scan keys; calls table_index_fetch_reset then amrescan.
• index_endscan — calls amendscan, table_index_fetch_end, releases the relcache reference, calls IndexScanEnd.
• index_getnext_tid — drives amgettuple; manages kill_prior_tuple and xs_heap_continue reset.
• index_fetch_heap — calls table_index_fetch_tuple; manages kill_prior_tuple feedback; emits pgstat_count_heap_fetch.
• index_getnext_slot — the outer loop combining index_getnext_tid and index_fetch_heap, handling HOT continuation via xs_heap_continue.
• index_getbitmap — bitmap-scan path; single amgetbitmap call.
• index_bulk_delete / index_vacuum_cleanup — vacuum callbacks; dispatch to ambulkdelete / amvacuumcleanup.
• index_can_return — returns false if amcanreturn is NULL; otherwise calls it.
• index_getprocid / index_getprocinfo — support-function lookup helpers.
• index_parallelscan_estimate / index_parallelscan_initialize / index_parallelrescan / index_beginscan_parallel — parallel index scan infrastructure.
• RELATION_CHECKS / SCAN_CHECKS / CHECK_REL_PROCEDURE / CHECK_SCAN_PROCEDURE — macros that assert rd_indam != NULL, check reindex status, and verify the specific callback is non-NULL before each call.

Scan-descriptor allocation (src/backend/access/index/genam.c)

• RelationGetIndexScan — palloc + zero-fill an IndexScanDescData with the right key array sizes; AMs call this from ambeginscan.
• IndexScanEnd — pfree the scan descriptor; called from index_endscan.

Scan descriptor (src/include/access/relscan.h)

• typedef struct IndexScanDescData — base scan struct with xs_heaptid, xs_heap_continue, xs_recheck, kill_prior_tuple, xs_itup, xs_hitup.
• typedef struct ParallelIndexScanDescData — parallel scan coordination struct; embedded in the shared memory block for parallel workers.
• typedef enum IndexUniqueCheck — UNIQUE_CHECK_{NO,YES,PARTIAL,EXISTING}.

Support types (src/include/access/genam.h)

• typedef struct IndexBuildResult — heap_tuples, index_tuples; returned by ambuild.
• typedef struct IndexVacuumInfo — vacuum input: index, heap relation, flags, num_heap_tuples, BufferAccessStrategy.
• typedef struct IndexBulkDeleteResult — vacuum output: num_pages, num_index_tuples, tuples_removed, page counts.
• typedef struct IndexScanInstrumentation — nsearches counter, copyable into shared memory for parallel scan stats.

Position hints (as of 2026-06-05, REL_18 273fe94)

Symbol	File	Line
typedef struct IndexAmRoutine	include/access/amapi.h	230
} IndexAmRoutine	include/access/amapi.h	323
GetIndexAmRoutine	index/amapi.c	33
GetIndexAmRoutineByAmId	index/amapi.c	56
typedef struct IndexScanDescData	include/access/relscan.h	133
xs_heaptid field	include/access/relscan.h	172
xs_heap_continue field	include/access/relscan.h	173
typedef enum IndexUniqueCheck	include/access/genam.h	138
typedef struct IndexBuildResult	include/access/genam.h	53
typedef struct IndexVacuumInfo	include/access/genam.h	64
typedef struct IndexBulkDeleteResult	include/access/genam.h	97
RelationGetIndexScan	index/genam.c	80
IndexScanEnd	index/genam.c	145
RELATION_CHECKS macro	index/indexam.c	75
index_open	index/indexam.c	133
index_insert	index/indexam.c	213
index_beginscan	index/indexam.c	256
index_beginscan_bitmap	index/indexam.c	289
index_beginscan_internal	index/indexam.c	314
index_rescan	index/indexam.c	356
index_endscan	index/indexam.c	382
index_markpos	index/indexam.c	412
index_restrpos	index/indexam.c	436
index_parallelscan_estimate	index/indexam.c	461
index_parallelscan_initialize	index/indexam.c	510
index_parallelrescan	index/indexam.c	565
index_beginscan_parallel	index/indexam.c	583
index_getnext_tid	index/indexam.c	621
index_fetch_heap	index/indexam.c	679
index_getnext_slot	index/indexam.c	720
index_getbitmap	index/indexam.c	765
index_bulk_delete	index/indexam.c	795
index_vacuum_cleanup	index/indexam.c	816
index_can_return	index/indexam.c	835
index_getprocid	index/indexam.c	873
index_getprocinfo	index/indexam.c	907

Source verification (as of 2026-06-05)

Each entry is a fact about the current source at commit 273fe94 (REL_18_STABLE). The trailing note shows how it was checked.

Verified facts

• IndexAmRoutine is declared at line 230 of amapi.h and closed at line 323. Verified by reading the file. There are no mandatory-callback Assert calls in GetIndexAmRoutine — validation is deferred to the CHECK_REL_PROCEDURE / CHECK_SCAN_PROCEDURE call-site macros in indexam.c.

• index_insert calls CheckForSerializableConflictIn only when ampredlocks is false. Verified at lines 225–228 of indexam.c. Btree sets ampredlocks = true and performs its own granular predicate locking via CheckForSerializableConflictIn inside _bt_check_unique; hash, GiST, GIN, SP-GiST, BRIN all set ampredlocks = false.

• index_beginscan (not index_beginscan_bitmap) opens a table_index_fetch_begin handle. Verified at line 277 of indexam.c. index_beginscan_bitmap does not call table_index_fetch_begin — it never fetches individual heap tuples; the BitmapHeapScan node does that separately using the TIDBitmap.

• index_getnext_slot loops on xs_heap_continue before fetching the next TID. Verified at lines 720–749 of indexam.c. The xs_heap_continue flag is reset to false in index_getnext_tid and may be set to true again by index_fetch_heap via table_index_fetch_tuple’s call_again output.

• kill_prior_tuple is set only outside recovery. Verified at lines 696–699 of indexam.c: if (!scan->xactStartedInRecovery) scan->kill_prior_tuple = all_dead. This avoids violating MVCC during crash recovery replays.

• amtranslatestrategy and amtranslatecmptype are both NULL-able in REL_18. Verified in amapi.h lines 321–322 — no /* can be NULL */ comment appears (the NULL-ability is implicit from the callback typedef), and IndexAmTranslateStrategy in amapi.c falls back to COMPARE_INVALID if the callback is absent (lines 129–133).

• IndexScanDescData has both xs_itup / xs_itupdesc (for index-only scans returning an IndexTuple) and xs_hitup / xs_hitupdesc (for AMs that reconstruct the result as a HeapTuple). Verified at lines 167–170 of relscan.h. Btree uses xs_itup; the AM sets xs_recheck = true when the index entry may not satisfy the scan keys without rechecking the heap.

• index_getprocid uses the formula (amsupport * (attnum - 1)) + (procnum - 1) as the flat array index into rd_support. Verified at lines 882–886 of indexam.c.

Open questions

1. Interaction between aminsertcleanup and parallel index builds. The aminsertcleanup callback (introduced to allow btree to flush its sort state after a parallel build) is called once per worker after all inserts complete. Whether a custom AM that uses a shared sort state across workers can safely implement this cleanup pattern without additional coordination is not spelled out in the interface contract.

2. amgettreeheight callback purpose. The amgettreeheight_function typedef appears in amapi.h (line 160) and is listed in the IndexAmRoutine slot (it is NULL-able). The planner uses this to estimate tree-traversal cost. How a non-tree AM that wants to influence cost estimation without implementing a height function should proceed is not documented.

3. amsummarizing and block-granularity AMs. BRIN sets amsummarizing = true. The executor and planner use this to know that BRIN entries represent page ranges, not exact TIDs. Whether custom AMs with different summarization granularities (e.g., columnar segment-level) can express their properties via the existing amsummarizing boolean or need a richer API is an open design question.

Beyond PostgreSQL — Comparative Designs & Research Frontiers

Pointers, not analysis. Each bullet is a starting handle for a follow-up doc.

• The five built-in index AMs as the canonical consumer set. Understanding IndexAmRoutine is only half the picture; the other half is reading how each AM fills it. postgres-nbtree.md covers btree (amcanorder = true, amcanunique = true, ampredlocks = true). GIN, GiST, SP-GiST, and BRIN each expose different capability-flag patterns and scan paths that show which parts of the interface are truly AM-neutral.

• Table AM ↔ Index AM coupling via index_fetch_heap. index_fetch_heap delegates directly to table_index_fetch_tuple (the Table AM API). This coupling means a custom index AM must work with whatever table AM is on the heap side — it cannot assume heapam. If a columnar table AM is in use, index_fetch_heap still calls through the table AM’s index_fetch_tuple callback, which the columnar AM must implement correctly. Understanding this seam is prerequisite for any work on custom table × index AM combinations. See postgres-table-am.md for the table-AM side.

• Generalized Search Trees (GiST) — Hellerstein et al. 1995. Generalized Search Trees for Database Systems (Hellerstein, Naughton, Pfeffer, VLDB 1995) introduced the GiST framework: a balanced tree where split/search strategies are pluggable via a small set of user-defined methods (Consistent, Union, Penalty, PickSplit). PostgreSQL’s GiST AM (access/gist/) is a direct descendant. GiST shows what happens when the AM API is pushed one level further — the AM itself becomes a framework with its own vtable-like plug-in mechanism.

• Index AM as the SSI predicate-lock boundary. When ampredlocks = false, the index layer acquires relation-level predicate locks on behalf of the AM. When ampredlocks = true (btree), predicate locks are acquired at a finer granularity (page, key-range) inside _bt_check_unique and the btree scan code. The postgres-ssi-predicate-locking doc (forthcoming) covers this split and the README-SSI design rationale.

• Custom index AMs as extensions. CREATE ACCESS METHOD ... TYPE INDEX registers a handler in pg_am. Third-party index types (bloom filter indexes from contrib/bloom, vector similarity indexes from pgvector, etc.) use exactly IndexAmRoutine as their extension point. The contrib bloom filter is the simplest example: it sets amgettuple = NULL and amgetbitmap only, accepting the consequence that it cannot be used for tuple-at-a-time scans.

Sources

In-tree documentation

• src/include/access/amapi.h — primary source; every callback typedef is documented with a brief comment.
• doc/src/sgml/indexam.sgml — the official documentation chapter on the index AM interface; describes each callback’s contract in prose.

Textbook chapters (under knowledge/research/dbms-general/)

• Database System Concepts (Silberschatz et al., 7e), ch. 14 “Indexing” — B+-tree, hash, and bitmap index theory.
• Database Internals (Petrov), ch. 6 “B-Tree Variants” — practical B-tree implementation tradeoffs.

Research papers (under knowledge/research/dbms-papers/)

• btree.md — the Bayer & McCreight 1972 B-tree paper, foundational for the nbtree AM.
• scalable-lock-manager.md — Kimura et al. 2012; relevant to btree’s predicate locking strategy.

PostgreSQL source (under /data/hgryoo/references/postgres/, REL_18 273fe94)

• src/include/access/amapi.h
• src/include/access/genam.h
• src/include/access/relscan.h
• src/backend/access/index/indexam.c
• src/backend/access/index/amapi.c
• src/backend/access/index/genam.c

Cross-references (sibling docs)

• postgres-table-am.md — the sibling Table AM interface (TableAmRoutine); explains table_index_fetch_begin / table_index_fetch_tuple, the heap side of every index scan.
• postgres-nbtree.md — the btree AM as the reference implementation; covers BTScanOpaqueData, page-level locking, _bt_check_unique, HOT awareness.
• postgres-heap-am.md — heap tuple format and heap_hot_search_buffer, the HOT-chain traversal called by table_index_fetch_tuple.
• postgres-mvcc-snapshots.md — the snapshot passed to index_beginscan and used in table_index_fetch_tuple visibility checks.
• postgres-lock-manager.md — heavyweight locking that index_open / DDL acquire.
• postgres-vacuum.md — index_bulk_delete / index_vacuum_cleanup callers and the vacuum protocol.