(KO) PostgreSQL 인덱스 접근 방법 — IndexAmRoutine과 제네릭 인덱스 계층

학술적 배경
DBMS 공통 설계 패턴
PostgreSQL의 구현
소스 코드 가이드
소스 검증 (2026-06-05 기준)
PostgreSQL 너머 — 비교 설계와 연구 프론티어
출처

학술적 배경

인덱스(index)는 저장 공간을 조회 속도와 맞바꾸는 보조 자료 구조다. 이론적 출발점은 단순하다. 릴레이션을 순차 스캔하면 페이지 수 기준 O(n) 비용이 드는데, 순서가 있는 혹은 해시 기반의 보조 구조를 두면 동등 조회와 범위 조회를 O(log n) 또는 O(1)로 줄일 수 있다. 대신 쓰기마다 구조를 유지해야 하고 추가 저장 공간이 필요하다(Database System Concepts, Silberschatz 외, 7판, 14장 “Indexing”; Database Internals, Petrov, 6장 “B-Tree Variants”).

실용적으로 중요한 인덱스 계열은 세 가지다.

순서 트리 인덱스 (B+-트리 계열). 동등, 범위, 접두사 스캔을 모두 지원한다. Bayer & McCreight 1972가 정식화한 B+-트리는 대부분의 상용 DBMS 인덱스의 원형이다. 조회는 트리를 내려가고, 삽입·삭제는 페이지 분할과 병합으로 균형을 유지한다.
해시 인덱스. 동등 조회만 지원하지만 O(1) 상각 비용을 달성할 수 있다. PostgreSQL의 hash AM은 Litwin 1980 선형 해싱을 기반으로 하며, PostgreSQL 10부터 WAL 로깅을 지원한다.
다차원/근사 인덱스 (GiST, GIN, SP-GiST, BRIN). 기하 탐색, 전문 검색(full-text search), 희소 다중 키, 블록 범위 요약 등을 다룬다. 내부 구조는 각기 다르지만 쿼리 익스큐터에 제공하는 계약은 btree와 동일하다. 모두 같은 IndexAmRoutine 인터페이스를 구현한다.

시스템 수준에서 핵심 설계 질문은 이렇게 구조적으로 다른 인덱스 타입들이 익스큐터를 향한 인터페이스를 공유해야 하는가다. 익스큐터가 btree 함수를 직접 호출하도록 하드코딩하면 새 인덱스 타입을 추가할 때마다 플래너, 익스큐터, DDL 계층, 옵티마이저 비용 모델 모두를 수정해야 한다. 제네릭 인덱스 접근 방법 인터페이스는 이 관심사를 분리한다. 익스큐터와 플래너는 안정적인 연산 집합(build, insert, begin-scan, get-next-tid, get-bitmap, vacuum)만 다루고, 각 인덱스 AM이 그 뒤의 구현을 채운다.

이 패턴은 TableAmRoutine이 테이블 스토리지에 사용하는 vtable 디스패치와 동일하다(postgres-table-am.md 참조). 다만 인덱스 AM API가 더 오래됐고 테이블 AM 설계가 이를 본뜬 것이다.

DBMS 공통 설계 패턴

제네릭 인덱스 계층을 노출하는 데이터베이스 시스템들에는 반복적으로 등장하는 설계 관행이 있다.

루틴 구조체의 능력 플래그

모든 인덱스 타입이 같은 연산을 지원하지는 않는다. 해시 인덱스는 범위 스캔이나 ORDER BY에 사용할 수 없다. BRIN 인덱스는 손실 방식(lossy)이어서 정확한 TID를 반환하려면 힙에서 재확인이 필요하다. GIN 인덱스는 btree가 지원하지 않는 전문 검색 다중 키 쿼리를 지원한다. 이런 다양성을 처리하는 관행은 vtable 구조체에 불리언 능력 플래그를 직접 내장하는 것이다. 플래너와 DDL 코드는 이 플래그(amcanorder, amsearcharray, amsummarizing, ampredlocks 등)를 읽어 특정 AM이 특정 쿼리를 처리할 수 있는지 AM을 호출하지 않고도 판단한다.

이 방식은 필수/선택 콜백 분리보다 더 풍부한 표현력을 갖는다. AM이 amgettuple을 구현하면서도 amcanbackward = false로 설정하면 “튜플 단위 반환은 가능하지만 역방향 스캔은 불가”라고 명시적으로 알릴 수 있다. 플래그는 AM과 플래너 사이의 핵심 협상 메커니즘이다.

두 가지 스캔 모드 — 튜플 단위와 비트맵

인덱스 스캔에는 익스큐터 파이프라인이 다른 두 형태가 있다.

amgettuple (튜플 단위). AM이 호출마다 힙 TID를 하나씩 반환한다. 익스큐터는 즉시 그 힙 튜플을 페치하고, 가시성을 확인한 뒤 상위 플랜 노드로 올린다. 순서가 유지된다. 인덱스 선택도가 높거나 ORDER BY가 인덱스에서 나와야 할 때 적합하다.
amgetbitmap (비트맵). AM이 단일 호출로 TIDBitmap을 모든 적격 TID로 채우고 개수를 반환한다. 익스큐터는 비트맵에 언급된 각 페이지를 정확히 한 번 힙 스캔한다(BitmapHeapScan). 페이지당 다수의 TID를 처리해 랜덤 I/O를 상각한다. 순서는 유지되지 않는다. 선택도가 낮거나 여러 인덱스를 결합할 때(비트맵 OR/AND) 사용한다.

AM은 둘 중 하나 또는 둘 다 지원할 수 있다. amgettuple과 amgetbitmap은 모두 NULL 허용이다. 플래너는 amcanorder와 AM 능력을 보고 스캔 모드를 선택한다.

인덱스 전용 스캔

쿼리에 필요한 모든 컬럼이 인덱스(키 컬럼 또는 INCLUDE 컬럼)에 있으면, 익스큐터는 힙을 페치하지 않고 인덱스 튜플만으로 결과를 반환할 수 있다. 이를 **인덱스 전용 스캔(index-only scan)**이라 한다. AM은 컬럼별로 amcanreturn으로 이 능력을 알린다. 익스큐터는 여전히 가시성 맵을 확인한다. 해당 페이지가 아직 all-visible이 아니면 힙 페치가 필요하다(xs_recheck 플래그).

연산자 클래스 / 연산자 패밀리 협상

인덱스 AM은 임의의 데이터 타입에 직접 작동하지 않는다. AM은 전략(strategy) 집합(번호 붙은 연산: BTLessStrategyNumber = 1, …)과 지원 함수(support function) 집합(내부 헬퍼: 비교, 해싱, 일관성 검사)을 정의한다. 연산자 클래스(pg_opclass)는 하나의 AM을 위해 데이터 타입을 특정 연산자와 지원 함수 집합에 매핑한다. 연산자 패밀리(pg_opfamily)는 비교 의미론을 공유하는 연관된 연산자 클래스들을 묶어 타입 간 비교를 가능하게 한다.

이 간접 구조 덕분에 같은 btree AM 코드가 int4, text, timestamp는 물론 올바른 지원 함수를 제공하는 사용자 정의 타입도 처리한다. AM은 루틴 구조체에 amstrategies와 amsupport를 담고, index_getprocid / index_getprocinfo가 런타임에 속성별 지원 함수를 조회한다.

이론 ↔ PostgreSQL 인덱스 AM 대응표

설계 개념	PostgreSQL 인덱스 AM 이름
인덱스 AM vtable	`IndexAmRoutine` (`amapi.h`)
릴레이션에 저장된 vtable	`Relation.rd_indam` (relcache 필드)
AM 능력 플래그	`IndexAmRoutine`의 불리언 필드 (예: `amcanorder`)
튜플 단위 스캔 콜백	`amgettuple`
비트맵 스캔 콜백	`amgetbitmap`
인덱스 전용 스캔 능력	`amcanreturn` (컬럼별 콜백)
스캔 디스크립터	`IndexScanDescData` (`relscan.h`)
전략 번호 → 비교 타입 변환	`amtranslatestrategy` 콜백
연산자 클래스 검증	`amvalidate` 콜백
AM 등록 팩토리	`GetIndexAmRoutine` (`amapi.c`)
제네릭 래퍼	`indexam.c`의 `index_*` 함수들

PostgreSQL의 구현

AM이 릴레이션에 연결되는 방식

relcache가 인덱스 릴레이션 항목을 구성할 때, 인덱스의 pg_class 행에서 pg_am.amhandler를 읽어 GetIndexAmRoutine(amhandler)를 호출하고, 반환된 IndexAmRoutine *을 rel->rd_indam에 저장한다. 이후 그 릴레이션에서 발생하는 모든 index_* 호출은 이 포인터로 디스패치된다. 각 호출 지점에서 RELATION_CHECKS / SCAN_CHECKS 매크로가 rd_indam != NULL을 단언하고, 해당 인덱스가 현재 reindex 중이 아닌지도 확인한다.

flowchart TB
  IREL["인덱스 릴레이션 (relcache)\nrd_indam → IndexAmRoutine *"]
  EXEC["익스큐터 / Vacuum\n(nodeIndexscan, nodeBitmapIndexscan,\nindex_bulk_delete)"]
  WRAP["index_* 래퍼\n(indexam.c)"]
  AM["IndexAmRoutine\n(ambeginscan, amgettuple,\namgetbitmap, ambulkdelete, …)"]
  IMPL["AM 구현체\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

그림 1 — 인덱스 AM 디스패치 체인. 익스큐터는 indexam.c의 index_* 래퍼를 호출하고, 각 래퍼는 사전 조건을 확인한 뒤 rd_indam을 거쳐 디스패치한다. 튜플 단위 스캔에서 index_fetch_heap은 힙 측 table_index_fetch_tuple을 호출해 TID를 가시적 튜플로 변환한다.

`IndexAmRoutine` — 구조체와 능력 플래그

IndexAmRoutine은 src/include/access/amapi.h 230번 줄에 선언된다. 정수 카운트와 불리언 능력 플래그들로 시작하고, 그 뒤에 콜백 함수 포인터들이 이어진다.

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

    uint16      amstrategies;       /* 전략 연산자 수, 가변이면 0 */
    uint16      amsupport;          /* 지원 함수 수 */
    uint16      amoptsprocnum;      /* opclass 옵션 지원 함수 번호, 없으면 0 */

    /* 능력 플래그 */
    bool        amcanorder;         /* 인덱스 값으로 ORDER BY 지원? */
    bool        amcanorderbyop;     /* 연산자 결과로 ORDER BY 지원? */
    bool        amcanhash;          /* 해시 일관 동등 지원? */
    bool        amcanbackward;      /* 역방향 스캔 지원? */
    bool        amcanunique;        /* UNIQUE 인덱스 지원? */
    bool        amcanmulticol;      /* 다중 컬럼 인덱스 지원? */
    bool        amoptionalkey;      /* 첫 컬럼 조건 필수? */
    bool        amsearcharray;      /* ScalarArrayOpExpr 조건 처리? */
    bool        amsearchnulls;      /* IS NULL / IS NOT NULL 처리? */
    bool        amstorage;          /* 인덱스 저장 타입이 컬럼 타입과 달라도 되나? */
    bool        amclusterable;      /* 이 인덱스로 CLUSTER 가능? */
    bool        ampredlocks;        /* 술어 잠금을 내부에서 처리? */
    bool        amcanparallel;      /* 병렬 스캔 지원? */
    bool        amcanbuildparallel; /* 병렬 빌드 지원? */
    bool        amcaninclude;       /* INCLUDE 컬럼 지원? */
    bool        amsummarizing;      /* 블록 단위로만 데이터 저장? */
    /* ... 추가 필드 ... */

    /* 인터페이스 함수 */
    ambuild_function        ambuild;
    ambuildempty_function   ambuildempty;
    aminsert_function       aminsert;
    aminsertcleanup_function aminsertcleanup; /* NULL 허용 */
    ambulkdelete_function   ambulkdelete;
    amvacuumcleanup_function amvacuumcleanup;
    amcanreturn_function    amcanreturn;       /* NULL 허용 */
    amcostestimate_function amcostestimate;
    amoptions_function      amoptions;
    amvalidate_function     amvalidate;
    ambeginscan_function    ambeginscan;
    amrescan_function       amrescan;
    amgettuple_function     amgettuple;        /* NULL 허용 */
    amgetbitmap_function    amgetbitmap;        /* NULL 허용 */
    amendscan_function      amendscan;
    ammarkpos_function      ammarkpos;          /* NULL 허용 */
    amrestrpos_function     amrestrpos;         /* NULL 허용 */
    /* ... 병렬 스캔 및 전략 변환 콜백 ... */
} IndexAmRoutine;

ampredlocks 플래그에 주목할 필요가 있다. 이 플래그가 true면 AM이 술어 잠금을 내부에서 처리한다(btree는 CheckForSerializableConflictIn을 직접 호출해 그렇게 한다). false면 index_insert와 index_beginscan_internal이 술어 잠금 계층을 직접 호출하므로, AM은 추가 구현 없이 SSI 지원을 얻는다.

`GetIndexAmRoutine`과 `GetIndexAmRoutineByAmId`

GetIndexAmRoutine(amapi.c)은 핸들러 OID 함수를 호출하고 결과가 IndexAmRoutine 노드인지 확인한다.

// 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;
}

GetTableAmRoutine과 달리 GetIndexAmRoutine은 개별 콜백 슬롯을 단언하지 않는다. 대신 indexam.c의 RELATION_CHECKS와 CHECK_REL_PROCEDURE 매크로가 각 콜백을 호출 직전에 NULL인지 검사해 null 역참조 대신 명확한 오류를 발생시킨다.

GetIndexAmRoutineByAmId는 pg_am에서 OID로 AM을 조회하고, 타입이 AMTYPE_INDEX인지 검증한 뒤 핸들러 OID를 구해 GetIndexAmRoutine을 호출한다.

`IndexScanDescData` — 스캔 디스크립터

IndexScanDescData(relscan.h, 133번 줄)는 amgettuple과 amgetbitmap 스캔 모두에 사용되는 기본 디스크립터다. 주요 필드는 다음과 같다.

// IndexScanDescData — src/include/access/relscan.h (요약)
typedef struct IndexScanDescData
{
    Relation    heapRelation;   /* 힙 릴레이션, 비트맵 스캔이면 NULL */
    Relation    indexRelation;  /* 인덱스 릴레이션 */
    struct SnapshotData *xs_snapshot;  /* 가시성 판단용 스냅샷 */

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

    bool        kill_prior_tuple; /* 마지막 반환 튜플이 dead */
    bool        xs_heap_continue; /* HOT 체인 계속 순회 필요 */

    /* 인덱스 전용 스캔용 */
    IndexTuple  xs_itup;        /* AM이 반환한 인덱스 튜플 */
    HeapTuple   xs_hitup;       /* AM이 HeapTuple로 반환한 인덱스 데이터 */
    ItemPointerData xs_heaptid; /* amgettuple이 기록한 TID 결과 */

    bool        xs_recheck;     /* 힙에서 스캔 키 재확인 필요 */
    bool        xs_recheckorderby; /* ORDER BY 거리 재확인 필요 */

    struct ParallelIndexScanDescData *parallel_scan; /* 병렬 스캔이 아니면 NULL */
}   IndexScanDescData;

xs_heaptid는 amgettuple이 찾은 TID를 기록하는 곳이다. xs_heap_continue는 HOT 체인 플래그다. AM이 이를 설정하거나 index_fetch_heap이 table_index_fetch_tuple의 call_again 출력값으로 이를 설정하면, index_getnext_slot은 다음 TID를 가져오기 전에 같은 TID를 대상으로 index_fetch_heap을 한 번 더 호출한다.

RelationGetIndexScan(genam.c)이 디스크립터를 palloc하고 초기화한다. AM은 자신의 ambeginscan 콜백에서 이 함수를 호출한다.

스캔 생명주기 — `index_beginscan` → `index_getnext_slot` → `index_endscan`

index_beginscan은 IndexScanDesc를 할당하고 ambeginscan을 호출한다. 그런 다음 힙 릴레이션, 스냅샷, 계측(instrument) 포인터를 저장하고, 힙 측의 table_index_fetch_begin 핸들을 열어 xs_heapfetch에 저장한다. 이후 모든 index_fetch_heap 호출이 이 핸들을 사용한다.

flowchart TD
  BS["index_beginscan\n(indexam.c:256)"] --> AI["ambeginscan\nAM이 스캔 상태 할당"]
  AI --> HF["table_index_fetch_begin\n힙 페치 핸들 열기"]
  HF --> RS["index_rescan\namrescan이 스캔 키 설정"]
  RS --> LOOP["index_getnext_slot 루프"]
  LOOP --> GT["index_getnext_tid\namgettuple → xs_heaptid"]
  GT --> FH["index_fetch_heap\ntable_index_fetch_tuple\n→ xs_heap_continue"]
  FH --> RET["슬롯을 익스큐터에 반환"]
  FH --> LOOP
  GT --> DONE["tid == NULL → 완료"]
  DONE --> ES["index_endscan\namendscan + table_index_fetch_end\n+ IndexScanEnd"]

그림 2 — 인덱스 스캔 생명주기. index_beginscan이 AM 스캔과 힙 페치 핸들을 함께 연다. index_getnext_slot의 내부 루프는 index_getnext_tid(다음 TID 획득)와 index_fetch_heap(TID 해석) 사이를 교대로 오가며, xs_heap_continue가 설정된 동안은 HOT 체인의 다음 멤버를 위해 루프를 반복한다.

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;
}

xs_heap_continue는 새 TID를 페치하는 index_getnext_tid에서 false로 초기화된다. index_fetch_heap이 table_index_fetch_tuple의 call_again 신호를 받으면 다시 true로 설정된다. 즉, HOT 체인에 멤버가 남아 있음을 뜻한다.

`index_getnext_tid`와 `kill_prior_tuple` 피드백

index_getnext_tid는 amgettuple을 구동하고 dead 튜플 정보를 피드백한다.

// index_getnext_tid — src/backend/access/index/indexam.c (요약)
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은 index_fetch_heap에서 table_index_fetch_tuple이 all_dead = true를 보고할 때 설정된다. 이는 해당 TID의 HOT 체인에 있는 어떤 튜플도 어떤 백엔드에도 보이지 않는다는 뜻이다. 다음 amgettuple 호출 시 AM은 kill_prior_tuple = true를 보고 해당 인덱스 항목을 dead로 표시한다. 실제 물리적 제거는 다음 vacuum 패스로 미뤄진다.

`index_fetch_heap` — TID를 가시적 튜플로 변환

// index_fetch_heap — src/backend/access/index/indexam.c (요약)
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;
}

힙 측 table_index_fetch_tuple은 주어진 TID의 HOT 체인을 스캔의 스냅샷 하에 순회해 첫 번째 가시적 튜플을 반환한다. 힙 AM이 xs_heap_continue를 설정하면, index_getnext_slot은 새 TID 없이 index_fetch_heap을 다시 호출해 체인의 다음 멤버를 가져온다.

`index_insert`와 술어 잠금

index_insert는 쓰기 경로다. AM이 술어 잠금을 직접 처리하는지(ampredlocks) 확인하고, 그렇지 않으면 aminsert를 호출하기 전에 CheckForSerializableConflictIn을 먼저 호출한다.

// 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는 유일성 강제를 제어하는 열거형이다. UNIQUE_CHECK_NO(검사 없음), UNIQUE_CHECK_YES(즉시 강제, 필요시 블록), UNIQUE_CHECK_PARTIAL(검사만 하고 오류 없음 — 지연 제약 조건용), UNIQUE_CHECK_EXISTING(이미 삽입된 튜플의 재확인)으로 구성된다.

비트맵 스캔 경로 — `index_getbitmap`

비트맵 스캔은 index_getnext_tid와 index_fetch_heap을 완전히 우회한다. AM이 단일 호출로 TIDBitmap을 채운다.

// 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;
}

BitmapIndexScan 익스큐터 노드가 이를 호출하고, 그 위의 BitmapHeapScan 노드가 비트맵에서 페이지를 순회하며 SO_TYPE_BITMAPSCAN 플래그로 table_scan_getnextslot을 호출한다.

Vacuum 경로 — `ambulkdelete`와 `amvacuumcleanup`

Vacuum은 두 콜백으로 인덱스를 처리한다.

ambulkdelete — 반복 호출된다. dead TID 콜백을 전달하면 AM이 인덱스를 순회하며 각 항목마다 콜백을 호출한다. 콜백이 true를 반환하면 해당 항목을 제거한다. 통계(IndexBulkDeleteResult)를 반환한다.
amvacuumcleanup — 모든 ambulkdelete 패스가 끝난 뒤 한 번 호출된다. 삭제 후 정리에 사용된다(btree 페이지 재활용, GIN 펜딩 리스트 처리 등). analyze_only = true로 ANALYZE 시에도 호출된다.

IndexVacuumInfo가 힙 릴레이션, 인덱스, vacuum 파라미터를 담는다. IndexBulkDeleteResult 구조체는 남은 페이지 수, 제거된 튜플 수, dead/free 페이지 수를 누적해 pg_class 통계에 피드백된다.

`opclass`와 `opfamily` 지원 — `index_getprocid` / `index_getprocinfo`

지원 함수는 pg_amproc에 저장되고 relcache의 rd_support 배열에 캐싱된다. index_getprocid는 주어진 (attnum, procnum) 쌍에 대한 RegProcedure OID를 반환한다. index_getprocinfo는 완전히 해석된 FmgrInfo *(opclass 옵션 Const 노드가 미리 초기화된 상태, rd_supportinfo에 캐싱)를 반환한다.

// index_getprocid — src/backend/access/index/indexam.c (요약)
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];
}

rd_support[(amsupport * (attnum - 1)) + (procnum - 1)] 형태의 평면 배열 배치 덕분에 AM은 곱셈 두 번과 배열 접근 한 번으로 지원 함수를 조회할 수 있다.

`amtranslatestrategy` / `amtranslatecmptype` (PG18 추가)

REL_18에서 두 개의 선택적 콜백이 추가되어 제네릭 비교 타입 변환을 지원한다.

amtranslatestrategy(strategy, opfamily) → CompareType — AM 전략 번호(예: BTLessStrategyNumber = 1)를 제네릭 CompareType(COMPARE_LT = 1)으로 변환한다. btree의 경우 단순 형변환으로 충분해서, IndexAmTranslateStrategy는 btree는 AM 호출 없이 처리하는 빠른 경로를 사용한다.
amtranslatecmptype(cmptype, opfamily) → StrategyNumber — 역방향 변환이다.

이 콜백을 활용하면 플래너는 AM 전용 전략 상수 없이도 AM-중립적인 비교 타입 어휘로 정렬과 조인 조건을 추론할 수 있다.

소스 코드 가이드

심볼 이름을 기준으로 삼고, 줄 번호에 의존하지 않는다. 아래 위치 힌트 표의 줄 번호는 커밋 273fe94(REL_18_STABLE, 2026-06-05) 기준 빠른 참고용이다. 현재 위치는 git grep -n '<심볼>'로 확인한다.

AM 인터페이스 정의 (`src/include/access/amapi.h`)

typedef struct IndexAmRoutine — 능력 플래그와 콜백 포인터를 담은 약 30개 슬롯의 vtable.
IndexAMProperty — pg_indexam_has_property와 pg_index_has_property로 조회 가능한 속성 열거형. AMPROP_ORDERABLE, AMPROP_SEARCH_NULLS, AMPROP_CLUSTERABLE 등을 포함한다.
typedef struct OpFamilyMember — amadjustmembers가 opclass/opfamily 멤버의 의존성 타입을 기술하는 데 사용한다.
콜백 typedef: ambuild_function, aminsert_function, ambulkdelete_function, amvacuumcleanup_function, ambeginscan_function, amrescan_function, amgettuple_function, amgetbitmap_function, amendscan_function, 병렬 스캔 변형.
GetIndexAmRoutine(Oid amhandler) — 팩토리 함수. IndexAmRoutine *을 반환한다.
GetIndexAmRoutineByAmId(Oid amoid, bool noerror) — AM OID로 조회한다.

제네릭 인덱스 래퍼 (`src/backend/access/index/indexam.c`)

index_open / index_close — relation_open / relation_close의 얇은 래퍼. relkind가 RELKIND_INDEX 또는 RELKIND_PARTITIONED_INDEX인지 검증한다.
index_insert — 쓰기 경로. ampredlocks를 확인하고 aminsert를 호출한다.
index_insert_cleanup — aminsertcleanup이 NULL이 아니면 호출. 대량 삽입 후 사용된다.
index_beginscan / index_beginscan_bitmap — 스캔을 연다. 전자는 table_index_fetch_begin도 호출한다. 둘 다 index_beginscan_internal을 통한다.
index_rescan — 스캔 키를 갱신한다. table_index_fetch_reset 후 amrescan을 호출한다.
index_endscan — amendscan, table_index_fetch_end를 호출하고 relcache 참조 카운트를 해제한 뒤 IndexScanEnd를 호출한다.
index_getnext_tid — amgettuple을 구동하고 kill_prior_tuple과 xs_heap_continue를 초기화한다.
index_fetch_heap — table_index_fetch_tuple을 호출하고 kill_prior_tuple 피드백을 관리하며 pgstat_count_heap_fetch를 내보낸다.
index_getnext_slot — index_getnext_tid와 index_fetch_heap을 결합한 외부 루프. xs_heap_continue로 HOT 연속 처리를 지원한다.
index_getbitmap — 비트맵 스캔 경로. 단일 amgetbitmap 호출이다.
index_bulk_delete / index_vacuum_cleanup — vacuum 콜백. ambulkdelete / amvacuumcleanup으로 디스패치한다.
index_can_return — amcanreturn이 NULL이면 false를 반환하고, 그렇지 않으면 호출한다.
index_getprocid / index_getprocinfo — 지원 함수 조회 헬퍼.
index_parallelscan_estimate / index_parallelscan_initialize / index_parallelrescan / index_beginscan_parallel — 병렬 인덱스 스캔 인프라.
RELATION_CHECKS / SCAN_CHECKS / CHECK_REL_PROCEDURE / CHECK_SCAN_PROCEDURE — rd_indam != NULL을 단언하고, reindex 상태를 확인하며, 각 호출 전에 특정 콜백이 NULL이 아닌지 검사하는 매크로.

스캔 디스크립터 할당 (`src/backend/access/index/genam.c`)

RelationGetIndexScan — 올바른 키 배열 크기로 IndexScanDescData를 palloc하고 초기화한다. AM이 ambeginscan에서 이를 호출한다.
IndexScanEnd — 스캔 디스크립터를 pfree한다. index_endscan에서 호출된다.

스캔 디스크립터 (`src/include/access/relscan.h`)

typedef struct IndexScanDescData — xs_heaptid, xs_heap_continue, xs_recheck, kill_prior_tuple, xs_itup, xs_hitup을 포함하는 기본 스캔 구조체.
typedef struct ParallelIndexScanDescData — 병렬 스캔 조정 구조체. 병렬 워커들을 위한 공유 메모리 블록에 내장된다.
typedef enum IndexUniqueCheck — UNIQUE_CHECK_{NO,YES,PARTIAL,EXISTING}.

지원 타입 (`src/include/access/genam.h`)

typedef struct IndexBuildResult — heap_tuples, index_tuples. ambuild가 반환한다.
typedef struct IndexVacuumInfo — vacuum 입력: 인덱스, 힙 릴레이션, 플래그, num_heap_tuples, BufferAccessStrategy.
typedef struct IndexBulkDeleteResult — vacuum 출력: num_pages, num_index_tuples, tuples_removed, 페이지 수.
typedef struct IndexScanInstrumentation — nsearches 카운터. 병렬 스캔 통계를 위해 공유 메모리로 복사 가능하다.

위치 힌트 (2026-06-05 기준, REL_18 273fe94)

심볼	파일	줄
`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` 필드	`include/access/relscan.h`	172
`xs_heap_continue` 필드	`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` 매크로	`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

소스 검증 (2026-06-05 기준)

각 항목은 커밋 273fe94(REL_18_STABLE) 기준 현재 소스에 대한 사실이다. 확인 방법을 함께 기록한다.

검증된 사실

IndexAmRoutine은 amapi.h 230번 줄에 선언되고 323번 줄에서 닫힌다. 파일을 직접 읽어 확인했다. GetIndexAmRoutine에는 개별 콜백에 대한 필수 Assert 호출이 없다. 검증은 indexam.c의 CHECK_REL_PROCEDURE / CHECK_SCAN_PROCEDURE 호출 지점 매크로로 위임된다.
index_insert는 ampredlocks가 false일 때만 CheckForSerializableConflictIn을 호출한다. indexam.c 225–228번 줄에서 확인했다. btree는 ampredlocks = true로 설정하고 _bt_check_unique 내부에서 자체적으로 세밀한 술어 잠금을 수행한다. hash, GiST, GIN, SP-GiST, BRIN은 모두 ampredlocks = false다.
index_beginscan(bitmap이 아닌 것)만 table_index_fetch_begin 핸들을 연다. indexam.c 277번 줄에서 확인했다. index_beginscan_bitmap은 table_index_fetch_begin을 호출하지 않는다. 비트맵 스캔에서는 개별 힙 튜플 페치를 BitmapHeapScan 노드가 별도로 처리하기 때문이다.
index_getnext_slot은 다음 TID를 가져오기 전에 xs_heap_continue를 먼저 확인하는 루프 구조를 사용한다. indexam.c 720–749번 줄에서 확인했다. xs_heap_continue는 index_getnext_tid에서 false로 초기화되고, index_fetch_heap이 table_index_fetch_tuple의 call_again 출력을 받아 true로 다시 설정할 수 있다.
kill_prior_tuple은 복구 중이 아닐 때만 설정된다. indexam.c 696–699번 줄에서 확인했다. if (!scan->xactStartedInRecovery) scan->kill_prior_tuple = all_dead라는 조건이 있다. 이는 크래시 복구 재실행 중 MVCC를 위반하지 않기 위한 처리다.
amtranslatestrategy와 amtranslatecmptype은 REL_18에서 모두 NULL 허용이다. amapi.h 321–322번 줄에서 확인했다. amapi.c의 IndexAmTranslateStrategy는 콜백이 없을 때 COMPARE_INVALID를 반환한다(129–133번 줄).
IndexScanDescData에는 xs_itup / xs_itupdesc(인덱스 전용 스캔에서 IndexTuple 반환)와 xs_hitup / xs_hitupdesc(AM이 결과를 HeapTuple로 재구성할 때) 두 쌍이 모두 있다. relscan.h 167–170번 줄에서 확인했다. btree는 xs_itup을 사용한다. 인덱스 항목이 스캔 키를 힙 재확인 없이 만족하지 못할 수 있으면 AM은 xs_recheck = true를 설정한다.
index_getprocid는 (amsupport * (attnum - 1)) + (procnum - 1) 공식으로 rd_support 평면 배열 인덱스를 계산한다. indexam.c 882–886번 줄에서 확인했다.

미해결 질문

aminsertcleanup과 병렬 인덱스 빌드의 상호작용. aminsertcleanup 콜백은 병렬 빌드 후 btree의 정렬 상태를 플러시하기 위해 도입됐다. 워커 종료 후 한 번씩 호출된다. 워커 간 공유 정렬 상태를 사용하는 커스텀 AM이 추가 조정 없이 이 정리 패턴을 올바르게 구현할 수 있는지는 인터페이스 계약에 명시되어 있지 않다.
amgettreeheight 콜백의 용도. amgettreeheight_function typedef는 amapi.h 160번 줄에 있고 IndexAmRoutine 슬롯에 포함된다(NULL 허용). 플래너가 트리 순회 비용을 추정하는 데 사용한다. 트리 구조가 아닌 AM이 높이 함수 없이 비용 추정에 영향을 주려면 어떻게 해야 하는지는 문서화되어 있지 않다.
amsummarizing과 블록 단위 AM. BRIN은 amsummarizing = true로 설정한다. 익스큐터와 플래너는 이를 보고 BRIN 항목이 페이지 범위를 나타낸다는 것을 안다. 다른 요약 단위(예: 컬럼형 세그먼트 수준)를 가진 커스텀 AM이 기존 amsummarizing 불리언만으로 자신의 속성을 표현할 수 있는지, 아니면 더 풍부한 API가 필요한지는 열린 설계 질문으로 남아 있다.

PostgreSQL 너머 — 비교 설계와 연구 프론티어

분석이 아닌 출발점. 각 항목은 후속 문서를 위한 시작 고리다.

다섯 가지 내장 인덱스 AM이 핵심 소비자 집합이다. IndexAmRoutine을 이해하는 것은 절반에 불과하다. 나머지 절반은 각 AM이 인터페이스를 어떻게 채우는지 읽는 것이다. postgres-nbtree.md는 btree(amcanorder = true, amcanunique = true, ampredlocks = true)를 다룬다. GIN, GiST, SP-GiST, BRIN은 각기 다른 능력 플래그 패턴과 스캔 경로를 보여주며, 인터페이스의 어느 부분이 진정으로 AM-중립적인지 드러낸다.
테이블 AM ↔ 인덱스 AM 결합 — index_fetch_heap 경유. index_fetch_heap은 테이블 AM API인 table_index_fetch_tuple로 직접 위임한다. 이 결합이 의미하는 바는 커스텀 인덱스 AM이 힙 측의 테이블 AM과 함께 작동해야 한다는 것이다. heapam을 가정할 수 없다. 컬럼형 테이블 AM이 사용 중이라면 index_fetch_heap은 여전히 테이블 AM의 index_fetch_tuple 콜백을 거쳐 호출된다. 커스텀 테이블 × 인덱스 AM 조합 작업의 전제 조건이다. 테이블 AM 측은 postgres-table-am.md에서 다룬다.
일반화된 검색 트리(GiST) — Hellerstein 외 1995. Generalized Search Trees for Database Systems(Hellerstein, Naughton, Pfeffer, VLDB 1995)는 GiST 프레임워크를 제안했다. 분할·탐색 전략이 소수의 사용자 정의 메서드(Consistent, Union, Penalty, PickSplit)로 플러그인 가능한 균형 트리다. PostgreSQL의 GiST AM(access/gist/)은 그 직계 구현이다. GiST는 AM API를 한 단계 더 밀어붙인 결과를 보여준다. AM 자체가 자체 vtable 방식의 플러그인 메커니즘을 가진 프레임워크가 된다.
SSI 술어 잠금 경계로서의 인덱스 AM. ampredlocks = false이면 인덱스 계층이 AM 대신 릴레이션 수준 술어 잠금을 획득한다. ampredlocks = true인 btree는 _bt_check_unique와 btree 스캔 코드 내부에서 더 세밀한 단위(페이지, 키 범위)로 술어 잠금을 획득한다. 이 분리와 README-SSI 설계 근거는 postgres-ssi-predicate-locking 문서(출간 예정)에서 다룬다.
확장으로서의 커스텀 인덱스 AM. CREATE ACCESS METHOD ... TYPE INDEX로 pg_am에 핸들러를 등록한다. 써드파티 인덱스 타입들(contrib의 bloom 필터 인덱스, pgvector의 벡터 유사도 인덱스 등)은 정확히 IndexAmRoutine을 확장 지점으로 사용한다. contrib bloom 필터는 가장 단순한 예시다. amgettuple = NULL로 설정하고 amgetbitmap만 구현해 튜플 단위 스캔에 사용될 수 없음을 받아들인다.

출처

인-트리 문서

src/include/access/amapi.h — 1차 출처. 각 콜백 typedef에 간략한 주석이 달려 있다.
doc/src/sgml/indexam.sgml — 인덱스 AM 인터페이스에 관한 공식 문서 챕터. 각 콜백의 계약을 산문으로 설명한다.

교과서 챕터 (`knowledge/research/dbms-general/` 아래)

Database System Concepts (Silberschatz 외, 7판), 14장 “Indexing” — B+-트리, 해시, 비트맵 인덱스 이론.
Database Internals (Petrov), 6장 “B-Tree Variants” — 실용적 B-트리 구현 트레이드오프.

연구 논문 (`knowledge/research/dbms-papers/` 아래)

btree.md — Bayer & McCreight 1972 B-트리 논문. nbtree AM의 이론적 기반이다.
scalable-lock-manager.md — Kimura 외 2012. btree의 술어 잠금 전략과 관련이 있다.

PostgreSQL 소스 (`/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

교차 참조 (형제 문서)

postgres-table-am.md — 형제 테이블 AM 인터페이스(TableAmRoutine). table_index_fetch_begin / table_index_fetch_tuple과 모든 인덱스 스캔의 힙 측을 설명한다.
postgres-nbtree.md — 레퍼런스 구현으로서의 btree AM. BTScanOpaqueData, 페이지 수준 잠금, _bt_check_unique, HOT 처리를 다룬다.
postgres-heap-am.md — 힙 튜플 형식과 heap_hot_search_buffer. table_index_fetch_tuple이 호출하는 HOT 체인 순회를 설명한다.
postgres-mvcc-snapshots.md — index_beginscan과 table_index_fetch_tuple 가시성 검사에 전달되는 스냅샷 생성.
postgres-lock-manager.md — index_open / DDL이 획득하는 중량 잠금.
postgres-vacuum.md — index_bulk_delete / index_vacuum_cleanup 호출 측과 vacuum 프로토콜.

(KO) PostgreSQL 인덱스 접근 방법 — IndexAmRoutine과 제네릭 인덱스 계층

학술적 배경

DBMS 공통 설계 패턴

루틴 구조체의 능력 플래그

두 가지 스캔 모드 — 튜플 단위와 비트맵

인덱스 전용 스캔

연산자 클래스 / 연산자 패밀리 협상

이론 ↔ PostgreSQL 인덱스 AM 대응표

PostgreSQL의 구현

AM이 릴레이션에 연결되는 방식

IndexAmRoutine — 구조체와 능력 플래그

GetIndexAmRoutine과 GetIndexAmRoutineByAmId

IndexScanDescData — 스캔 디스크립터

스캔 생명주기 — index_beginscan → index_getnext_slot → index_endscan

index_getnext_tid와 kill_prior_tuple 피드백

index_fetch_heap — TID를 가시적 튜플로 변환

index_insert와 술어 잠금

비트맵 스캔 경로 — index_getbitmap

Vacuum 경로 — ambulkdelete와 amvacuumcleanup

opclass와 opfamily 지원 — index_getprocid / index_getprocinfo

amtranslatestrategy / amtranslatecmptype (PG18 추가)