(KO) PostgreSQL 힙 접근 방법 — 덮어쓰지 않는 MVCC 튜플, 슬롯 페이지, HOT

목차

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

학술적 배경

교과서적 의미의 *힙 파일(heap file)*은 레코드의 순서가 없는 집합이다. 관계의 행들은 페이지에 담기며, 페이지 번호와 슬롯 번호로 주소가 결정될 뿐 정렬 보장은 없다(Database System Concepts, 7판, 13장 “Data Storage Structures” §“File Organization”; Database Internals, Petrov, 3장 “File Formats”). 힙 구현이 반드시 답해야 할 질문은 두 가지다. 고정 크기 페이지 안에서 가변 길이 레코드를 어떻게 배치할 것인가, 그리고 레코드가 갱신·삭제될 때 이전 바이트를 어떻게 처리할 것인가.

배치 문제의 답은 사실상 보편적이다. 슬롯 페이지(slotted page), 또는 “슬롯 디렉터리” 페이지라고도 부른다. 페이지 앞에 헤더가 오고, 헤더 바로 뒤부터 작은 라인 포인터(line pointer) 배열이 아래쪽으로 자란다. 실제 레코드는 페이지 끝에서 위쪽으로 자란다. 두 방향이 만나기 전까지의 구멍이 여유 공간이다. 레코드의 주소는 (페이지, 슬롯 번호)이며, 슬롯이 안정적인 핸들이므로 압축 과정에서 레코드가 페이지 안에서 이동해도 슬롯을 거쳐 오는 참조는 깨지지 않는다(Database Internals, 3장 §“Slotted Pages”; Database System Concepts §“Organization of Records in Files”). 이 간접 참조 구조가 이 문서 전체의 토대다.

갱신·삭제 처리 방식은 엔진의 설계 방향을 가르는 분기점이다. 두 계열이 있다.

1. 제자리 덮어쓰기(update-in-place). 새 값이 이전 바이트를 덮어쓴다. 동시 읽기와 롤백을 위해 이전 이미지가 필요하다면 별도의 undo 영역에 보관한다. Oracle과 MySQL/InnoDB가 대표적인 제자리 덮어쓰기 엔진이다.
2. 덮어쓰지 않기(no-overwrite, 또는 append/versioned). 이전 버전을 그대로 두고 새 버전을 다른 곳에 기록한 뒤 두 버전을 연결한다. 독자는 타임스탬프나 트랜잭션 가시성으로 원하는 버전을 선택한다. 버클리 POSTGRES 스토리지 시스템의 계보가 바로 이 방식이다.

PostgreSQL은 덮어쓰지 않는 엔진의 대명사다. 이 설계는 Stonebraker의 The Design of the POSTGRES Storage System (VLDB 1987)으로 직접 이어진다. 그 논문의 핵심 주장은 스토리지가 커밋된 데이터를 절대 덮어쓰지 말아야 한다는 것이었다. 갱신은 새 튜플을 쓰고 이전 것을 역사적 상태로 남겨 두어, “시간 여행(time-travel)” 쿼리가 과거 임의 시점의 데이터베이스를 읽을 수 있게 하고 커밋 시 강제 플러시로 로그를 없애는 것이 목표였다. 현대 PostgreSQL은 덮어쓰지 않는 힙은 유지하되 논문의 커밋-시-강제-플러시 대신 일반적인 WAL을 쓴다(postgres-xlog-wal.md 참조). 시간 여행 기능은 제거됐지만, 덮어쓰지 않는 튜플은 다중 버전 동시성 제어(MVCC, Multiversion Concurrency Control) 가 읽기 경로에서 사실상 무비용이 되게 만드는 바로 그 메커니즘으로 남았다.

MVCC는 동시성 제어 계열의 하나다(Database Internals, 5장 “Transaction Processing and Recovery” §“Multiversion Concurrency Control”). “새 버전이 커밋되기 전까지 읽기 트랜잭션이 이전 값을 계속 참조할 수 있다”는 특성이 있다. 조율의 단위가 상호 배제가 아니라 가시성이다. 이 위에 얹는 지배적 격리 수준은 **스냅샷 격리(SI, Snapshot Isolation)**다. 트랜잭션은 논리적 스냅샷을 기준으로 읽고, 스냅샷 시점에 커밋된 버전을 보며, 아직 실행 중인 트랜잭션이 쓴 버전은 무시한다. 덮어쓰지 않는 힙은 SI의 자연스러운 기반이다. 스냅샷이 필요로 할 수 있는 모든 버전이 물리적으로 남아 있기 때문이다. 가시성 판단은 버전의 생성자·소멸자 트랜잭션 ID에 대한 술어 평가로 귀결된다.

세 가지 구현 선택이 이 문서의 구성을 결정한다.

1. 각 버전이 가시성 판단을 위해 보유하는 메타데이터. PostgreSQL에서는 xmin(삽입 트랜잭션), xmax(삭제·잠금 트랜잭션), 그리고 힌트·플래그 비트 한 워드다.
2. 한 행의 버전들을 연결하는 방법. PostgreSQL에서는 이전 튜플의 t_ctid가 (보통 같은 페이지의) 새 튜플 슬롯을 앞으로 가리킨다.
3. 죽은 버전을 회수하는 방법. PostgreSQL에서는 단일 페이지 **HOT 정리(HOT pruning)**가 빠른 경로이고, 인덱스까지 조율해야 하는 전체 vacuum은 postgres-vacuum.md에서 다룬다.

스냅샷 생성 — 실행 중인 XID 집합을 어떻게 포착하고 XidInMVCCSnapshot이 멤버십을 어떻게 판단하는가 — 은 postgres-mvcc-snapshots.md와 postgres-procarray.md의 주제다. 이 문서는 스냅샷을 주어진 오라클로 취급하고, 튜플에 집중한다. 튜플의 헤더, 페이지 위의 위치, 그리고 튜플을 쓰고 회수하는 삽입·갱신·삭제·정리 연산을 살핀다.

DBMS 공통 설계 패턴

교과서는 모델을 제시한다. 이 절은 힙 구현들 사이에서 반복해서 나타나는 공학적 관행을 정리한다. PostgreSQL의 구체적인 심볼들이 다음 절에서 발명처럼 보이지 않고, 공유된 설계 공간 안의 선택 하나로 읽히게 하려는 것이다.

버전별 가시성 메타데이터

모든 MVCC 엔진은 버전에 생성자와 소멸자 트랜잭션 식별자를 찍는다. 자주 쓰이는 가시성 판단을 단락(short-circuit)시키기 위한 플래그 상태도 함께 둔다. 최소 표현은 (created_by, deleted_by) 트랜잭션 ID 쌍이다. PostgreSQL은 이 쌍을 힙 튜플 위에 직접(xmin/xmax) 저장한다. Oracle과 InnoDB는 살아 있는 행에 포인터(undo 로케이터 / 롤백 포인터)만 두고 이전 이미지는 undo에 보관한다. “deleted_by” 질문은 undo를 걸어가야 답을 얻는다. 직접 저장 방식은 PostgreSQL의 읽기 경로를 튜플 헤더의 로컬 테스트로 만들어 준다. 대신 헤더를 모든 버전에 달아야 하고, 죽은 버전을 제거하는 vacuum이 필요하다.

두 번째 보편적 관행은 **힌트 비트(hint bits)**다. “삽입 트랜잭션이 커밋됐다 / 중단됐다”, 그리고 삭제자에 대해서도 동일한 사실을 버전과 함께 캐시하는 구조다. 커밋 로그(CLOG / pg_xact)에서 트랜잭션 커밋 상태를 읽는 것은 상대적으로 비싸다. 그래서 처음 그 결과를 알게 된 독자가 튜플 위에 기록하고, 이후 독자들은 조회를 건너뛴다. 힌트 비트는 파생 정보지 권위 있는 원본이 아니다. 커밋 로그에서 언제든 재계산할 수 있다. 그래서 지연 기록이 가능하고 WAL 없이도 설정할 수 있다.

간접 참조 슬롯이 있는 슬롯 페이지

슬롯 페이지는 거의 보편적이지만, 버전화된 힙에서 슬롯은 추가 역할을 맡는다. “이 레코드의 오프셋 + 길이”를 넘어 작은 상태 기계를 인코딩할 수 있다. 정상 슬롯은 튜플을 가리킨다. 리다이렉트(redirect) 슬롯은 자신의 튜플 없이 다른 슬롯을 가리킨다. dead 슬롯은 아무것도 가리키지 않지만 인덱스가 아직 참조하므로 재사용할 수 없다. unused 슬롯은 자유롭게 써도 된다. 이 네 상태 슬롯이 있어야 엔진은 죽은 버전의 튜플 바이트를 회수하면서도 슬롯은 안정적인 인덱스 대상으로 살려 둘 수 있다. 단일 페이지 회수의 핵심 트릭이 여기서 나온다.

페이지 내 앞방향 버전 체인

행이 갱신되면 이전 버전을 참조하는 독자가 새 버전을 찾아올 수 있어야 한다. 관행은 이전 버전에서 새 버전으로 가는 앞방향 링크(forward link), 즉 이전 버전 헤더의 “다음 버전” 포인터다. 제자리 덮어쓰기 엔진에서는 암묵적(행이 그냥 바뀌었으므로)이지만, 덮어쓰지 않는 엔진에서는 명시적이고 물리적이다. 체인을 가능하면 한 페이지 안에 두는 것이 추가 I/O 없이 체인을 따라가게 해 주는 최적화다.

갱신 시 인덱스 작업 중복 방지

덮어쓰지 않는 힙에서 UPDATE의 순진한 비용은 새 힙 튜플 하나 더하기 모든 인덱스의 새 항목 하나씩이다. 바뀐 인덱스 컬럼이 없더라도 새 튜플이 새 물리 주소(TID)를 갖기 때문이다. 진지한 덮어쓰기 없는 엔진들은 모두 여기에 대한 답을 갖는다. PostgreSQL의 답은 **Heap-Only Tuple(HOT)**이다. 인덱스 컬럼을 건드리지 않은 갱신이고 새 버전이 같은 페이지에 들어가면, 인덱스 항목을 추가하지 않는다. 새 버전은 기존 인덱스 항목이 가리키는 루트에서 페이지 내 체인을 따라가야만 도달할 수 있다.

회수: 싸고 빠른 단일 페이지 vs. 조율이 필요한 전체 회수

죽은 버전은 쌓이므로 회수는 필수고, 두 경로로 나뉜다.

• 단일 페이지 회수는 죽은 버전의 바이트를 인덱스를 건드리지 않고 제거한다. 단, 그 특정 버전을 인덱스가 직접 가리키지 않을 때만 가능하다. HOT 체인은 중간 버전에 인덱스 항목이 없도록 설계되어 있어, 정확히 이 조건을 만족한다.
• 조율이 필요한 회수(전체 vacuum)는 인덱스가 죽은 버전을 직접 가리킬 때 필요하다. 힙 슬롯을 해제하기 전에 인덱스를 먼저 스캔·정리해야 한다. 비싸고 테이블 전체를 대상으로 하는 경로다.

이론 ↔ PostgreSQL 매핑

이론 / 관행	PostgreSQL 이름
슬롯 페이지 레코드 배치	힙 페이지 (PageHeaderData + ItemIdData[] + 튜플) — postgres-page-layout.md
간접 참조 슬롯 (4-상태)	ItemIdData.lp_flags: LP_UNUSED / LP_NORMAL / LP_REDIRECT / LP_DEAD
버전 “생성자”	HeapTupleHeaderData.t_choice.t_heap.t_xmin
버전 “소멸자·잠금자”	HeapTupleHeaderData.t_choice.t_heap.t_xmax
가시성 힌트 비트	t_infomask: HEAP_XMIN_COMMITTED, HEAP_XMAX_COMMITTED, …
앞방향 버전 포인터	HeapTupleHeaderData.t_ctid (→ 다음 버전 슬롯, 또는 자기 자신)
인덱스 없는 같은 페이지 갱신	HOT 갱신 — HEAP_HOT_UPDATED (이전) + HEAP_ONLY_TUPLE (신규)
단일 페이지 회수	heap_page_prune_opt → heap_page_prune_and_freeze
조율 회수	vacuum — postgres-vacuum.md
스냅샷 멤버십 오라클	XidInMVCCSnapshot (postgres-mvcc-snapshots.md)
플러그인 가능 테이블 인터페이스	TableAmRoutine (힙 = heapam_methods) — postgres-table-am.md

PostgreSQL의 구현

PostgreSQL 힙은 테이블 접근 방법(table access method)의 기본 구현체다. 실행기는 heap_insert를 직접 호출하지 않는다. table_tuple_insert를 호출하고, 이 함수는 TableAmRoutine 함수 포인터 테이블로 디스패치한다. 일반 테이블의 경우 그 테이블은 heapam_methods이며, 슬롯들은 heapam_handler.c의 얇은 래퍼(heapam_tuple_insert, heapam_tuple_update, …)를 가리킨다. 래퍼는 실행기의 TupleTableSlot을 HeapTuple로 풀어 heapam.c의 실제 힙 함수를 호출한다. AM 경계 자체는 postgres-table-am.md가 소유한다. 여기서는 디스패치된 이후 힙이 무엇을 하는지에 집중한다.

flowchart TB
  EXEC["executor / ExecInsert, ExecUpdate, ExecDelete"] --> TAM["table_tuple_insert / _update / _delete\n(tableam.h inline wrappers)"]
  TAM --> RT["heapam_methods\n(const TableAmRoutine)"]
  RT --> H1["heapam_tuple_insert"]
  RT --> H2["heapam_tuple_update"]
  RT --> H3["heapam_tuple_delete"]
  RT --> H4["heapam_index_fetch_tuple"]
  H1 --> HI["heap_insert (heapam.c)"]
  H2 --> HU["heap_update (heapam.c)"]
  H3 --> HD["heap_delete (heapam.c)"]
  H4 --> HS["heap_hot_search_buffer (heapam.c)"]

그림 1 — 테이블 AM으로서의 힙. 실행기는 TableAmRoutine 인터페이스만 사용한다. heapam_methods가 그 슬롯들을 heapam_handler.c 래퍼에 묶고, 래퍼가 heapam.c의 실제 함수를 호출한다. heapam_methods를 다른 루틴(컬럼 형식 AM, 인메모리 AM 등)으로 교체하는 것이 플러그인 가능 스토리지 확장 지점이다 — postgres-table-am.md 참조.

루틴 자체는 단순한 static const 함수 포인터 구조체다.

// heapam_methods — src/backend/access/heap/heapam_handler.c (condensed)
static const TableAmRoutine heapam_methods = {
    .type = T_TableAmRoutine,
    .slot_callbacks = heapam_slot_callbacks,
    .scan_begin = heap_beginscan,
    .scan_getnextslot = heap_getnextslot,
    .index_fetch_tuple = heapam_index_fetch_tuple,
    .tuple_insert = heapam_tuple_insert,
    .multi_insert = heap_multi_insert,
    .tuple_delete = heapam_tuple_delete,
    .tuple_update = heapam_tuple_update,
    .tuple_satisfies_snapshot = heapam_tuple_satisfies_snapshot,
    .relation_vacuum = heap_vacuum_rel,
    /* ... ~40 callbacks total ... */
};

래퍼들은 의도적으로 얇다. heapam_tuple_insert는 본질적으로 “슬롯에서 HeapTuple을 꺼내 heap_insert를 호출하고 결과 TID를 슬롯에 복사한다”는 동작이다.

// heapam_tuple_insert — src/backend/access/heap/heapam_handler.c
static void
heapam_tuple_insert(Relation relation, TupleTableSlot *slot, CommandId cid,
                    int options, BulkInsertState bistate)
{
    bool        shouldFree = true;
    HeapTuple   tuple = ExecFetchSlotHeapTuple(slot, true, &shouldFree);

    slot->tts_tableOid = RelationGetRelid(relation);
    tuple->t_tableOid = slot->tts_tableOid;

    heap_insert(relation, tuple, cid, options, bistate);
    ItemPointerCopy(&tuple->t_self, &slot->tts_tid);

    if (shouldFree)
        pfree(tuple);
}

튜플 헤더 — HeapTupleHeaderData

디스크에 저장되는 모든 힙 튜플은 23바이트 고정 헤더로 시작한다. 뒤에 NULL 비트맵, 정렬 패딩, 사용자 데이터가 이어진다. MVCC가 사는 곳이 바로 이 헤더다.

// HeapTupleFields + HeapTupleHeaderData — src/include/access/htup_details.h (condensed)
typedef struct HeapTupleFields
{
    TransactionId t_xmin;       /* inserting xact ID */
    TransactionId t_xmax;       /* deleting or locking xact ID */
    union {
        CommandId   t_cid;      /* inserting or deleting command ID, or both */
        TransactionId t_xvac;   /* old-style VACUUM FULL xact ID */
    } t_field3;
} HeapTupleFields;

struct HeapTupleHeaderData
{
    union {
        HeapTupleFields t_heap;
        DatumTupleFields t_datum;   /* overlay for in-memory composite Datums */
    } t_choice;

    ItemPointerData t_ctid;     /* current TID of this or newer tuple (or a
                                 * speculative insertion token) */
    uint16      t_infomask2;    /* number of attributes + various flags */
    uint16      t_infomask;     /* various flag bits, see below */
    uint8       t_hoff;         /* sizeof header incl. bitmap, padding */
    /* ^ - 23 bytes - ^ */
    bits8       t_bits[FLEXIBLE_ARRAY_MEMBER];  /* bitmap of NULLs */
};

세 필드가 MVCC 전체 이야기를 담는다.

• t_xmin — 이 버전을 삽입한 트랜잭션의 XID. 독자의 스냅샷이 그 트랜잭션의 효과를 볼 수 있는지 판단한다.
• t_xmax — 이 버전을 삭제하거나 갱신해 버린 트랜잭션의 XID. 단순 잠금일 수도 있으며 HEAP_XMAX_LOCK_ONLY 플래그가 잠금인지 삭제인지를 구별한다. 0/유효하지 않으면 이 버전은 살아 있는 최신 버전이다.
• t_ctid — 보통은 튜플 자신의 슬롯을 가리킨다. UPDATE 후에는 이전 튜플의 t_ctid가 새 버전의 슬롯으로 재작성된다. 이것이 물리적 앞방향 체인이다. 투기적 삽입(speculative insert) 토큰이나 “다른 파티션으로 이동됨” 표시자로 오버로드되기도 한다.

t_infomask 플래그 워드에는 힌트 비트와 잠금 상태가 있다. t_infomask2 워드에는 어트리뷰트 개수와 두 HOT 플래그가 있다.

// selected flags — src/include/access/htup_details.h
#define HEAP_XMIN_COMMITTED   0x0100  /* t_xmin committed */
#define HEAP_XMIN_INVALID     0x0200  /* t_xmin invalid/aborted */
#define HEAP_XMIN_FROZEN      (HEAP_XMIN_COMMITTED|HEAP_XMIN_INVALID)
#define HEAP_XMAX_COMMITTED   0x0400  /* t_xmax committed */
#define HEAP_XMAX_INVALID     0x0800  /* t_xmax invalid/aborted */
#define HEAP_XMAX_IS_MULTI    0x1000  /* t_xmax is a MultiXactId */
#define HEAP_XMAX_LOCK_ONLY   0x0080  /* xmax, if valid, is only a locker */
/* ... in t_infomask2 ... */
#define HEAP_HOT_UPDATED      0x4000  /* tuple was HOT-updated */
#define HEAP_ONLY_TUPLE       0x8000  /* this is a heap-only tuple */

HEAP_XMIN_FROZEN은 프리징(freezing)에서 쓰는 비트 조합이다(postgres-vacuum.md 참조). 프리즈된 튜플의 xmin은 모든 사람에게 커밋·가시로 취급된다. 실제 XID는 32비트 래프어라운드 경계를 넘어 재사용될 수 있다. 동시에 커밋과 무효 비트가 모두 세팅된다는 것은 논리적으로 모순이지만, 바로 그 모순적 값이 프로즌 센티넬로 재활용된다는 점이 중요하다.

슬롯 힙 페이지와 라인 포인터

힙 튜플은 바이트 오프셋으로 주소를 얻지 않는다. 라인 포인터(line pointer) — 페이지 헤더 바로 아래에서 아래쪽으로 자라는 배열의 4바이트 슬롯 — 로 주소를 얻는다. 슬롯은 비트 패킹된 세 필드로 구성된다.

// ItemIdData — src/include/storage/itemid.h
typedef struct ItemIdData
{
    unsigned    lp_off:15,      /* offset to tuple (from start of page) */
                lp_flags:2,     /* state of line pointer, see below */
                lp_len:15;      /* byte length of tuple */
} ItemIdData;

#define LP_UNUSED   0   /* unused (should always have lp_len=0) */
#define LP_NORMAL   1   /* used (should always have lp_len>0) */
#define LP_REDIRECT 2   /* HOT redirect (should have lp_len=0) */
#define LP_DEAD     3   /* dead, may or may not have storage */

2비트 lp_flags가 §“DBMS 공통 설계 패턴”에서 말한 4-상태 간접 참조 슬롯이며, HOT의 핵심이다. LP_REDIRECT 슬롯은 자신의 튜플이 없다(lp_len == 0). lp_off가 다른 라인 포인터의 오프셋 번호를 담는다. LP_DEAD 슬롯은 아무것도 가리키지 않지만 인덱스가 아직 참조하므로 재사용할 수 없다. 페이지의 상세 기하(pd_lower, pd_upper, pd_special, PageAddItem)는 postgres-page-layout.md가 소유한다. 여기서 중요한 것은 인덱스가 저장하는 TID (블록, 오프셋)이 바이트 주소가 아니라 슬롯 인덱스라는 점이다. 슬롯이 유효한 인덱스 대상으로 남아 있는 한 튜플 바이트는 이동하거나 제거할 수 있다.

flowchart TB
  subgraph PAGE["힙 페이지 (슬롯 구조)"]
    direction TB
    HDR["PageHeaderData\n(pd_lower, pd_upper, pd_prune_xid, ...)"]
    subgraph LP["라인 포인터 배열 (아래로 자람)"]
      direction LR
      L1["ItemId 1\nLP_NORMAL\noff=upper-A, len"]
      L2["ItemId 2\nLP_NORMAL"]
      L3["ItemId 3\nLP_DEAD\nlen may be 0"]
    end
    FREE["여유 공간\n(pd_lower .. pd_upper)"]
    subgraph TUP["튜플 (위로 자람)"]
      direction LR
      T1["tuple A\n(header + data)"]
      T2["tuple B"]
    end
  end
  L1 --> T1
  L2 --> T2

그림 2 — 슬롯 힙 페이지. 헤더는 앞에 고정되고, 라인 포인터는 아래로 자라며, 튜플은 위로 자란다. pd_lower와 pd_upper 사이의 구멍이 여유 공간이다. 인덱스 항목은 (블록, 라인포인터-오프셋-번호)를 저장하므로, 라인 포인터 3이 LP_DEAD 상태여서 튜플 바이트가 이미 사라졌더라도 vacuum이 인덱스 항목을 정리하기 전까지는 합법적인 인덱스 대상이다. 전체 기하: postgres-page-layout.md.

INSERT — heap_insert

삽입은 단순한 경우다. 헤더를 찍고, 여유 있는 페이지를 찾아 튜플을 쓰고, WAL에 기록한다. heap_prepare_insert가 헤더를 채운다. 모든 가시성 비트를 지우고, xmin을 현재 XID로 설정하고, xmax를 무효로 표시하며, cmin을 설정한다.

// heap_prepare_insert — src/backend/access/heap/heapam.c (condensed)
tup->t_data->t_infomask &= ~(HEAP_XACT_MASK);
tup->t_data->t_infomask2 &= ~(HEAP2_XACT_MASK);
tup->t_data->t_infomask |= HEAP_XMAX_INVALID;
HeapTupleHeaderSetXmin(tup->t_data, xid);
if (options & HEAP_INSERT_FROZEN)
    HeapTupleHeaderSetXminFrozen(tup->t_data);
HeapTupleHeaderSetCmin(tup->t_data, cid);
HeapTupleHeaderSetXmax(tup->t_data, 0);     /* for cleanliness */
tup->t_tableOid = RelationGetRelid(relation);

heap_insert는 RelationGetBufferForTuple로 대상 버퍼를 고르고(여유 공간 맵 참조 — postgres-free-space-map.md), SSI 충돌 검사를 수행한 뒤 크리티컬 섹션 안에서 튜플을 배치한다.

// heap_insert — src/backend/access/heap/heapam.c (condensed)
heaptup = heap_prepare_insert(relation, tup, xid, cid, options);
buffer = RelationGetBufferForTuple(relation, heaptup->t_len, ...);
CheckForSerializableConflictIn(relation, NULL, InvalidBlockNumber);

START_CRIT_SECTION();
RelationPutHeapTuple(relation, buffer, heaptup,
                     (options & HEAP_INSERT_SPECULATIVE) != 0);
if (PageIsAllVisible(BufferGetPage(buffer)))
{
    all_visible_cleared = true;
    PageClearAllVisible(BufferGetPage(buffer));
    visibilitymap_clear(relation, ItemPointerGetBlockNumber(&heaptup->t_self),
                        vmbuffer, VISIBILITYMAP_VALID_BITS);
}
MarkBufferDirty(buffer);
/* ... XLogInsert(RM_HEAP_ID, XLOG_HEAP_INSERT) ... */
END_CRIT_SECTION();

RelationPutHeapTuple은 슬롯을 할당하고, 결정적으로, 새 튜플의 t_ctid가 자기 자신을 가리키게 설정한다. 방금 삽입된 버전은 그 행의 최신 버전이기 때문이다.

// RelationPutHeapTuple — src/backend/access/heap/hio.c (condensed)
offnum = PageAddItem(pageHeader, (Item) tuple->t_data,
                     tuple->t_len, InvalidOffsetNumber, false, true);
ItemPointerSet(&(tuple->t_self), BufferGetBlockNumber(buffer), offnum);
if (!token)
{
    ItemId itemId = PageGetItemId(pageHeader, offnum);
    HeapTupleHeader item = (HeapTupleHeader) PageGetItem(pageHeader, itemId);
    item->t_ctid = tuple->t_self;       /* point at self */
}

순서가 중요하다. 페이지 더티 표시와 WAL 기록이 START_CRIT_SECTION()/END_CRIT_SECTION() 안에서 이루어진다. WAL-먼저-플러시 규칙(postgres-xlog-wal.md 참조)이 더티 페이지가 디스크에 닿기 전에 삽입 레코드의 내구성을 보장한다. 페이지가 all-visible이었다면 가시성 맵 비트를 지우는 것이 postgres-visibility-map.md와의 경계다.

DELETE — heap_delete

삭제는 튜플을 절대 제거하지 않는다. xmax에 삭제 XID를 찍고, 커맨드 ID를 기록하며, 페이지에 정리 힌트를 설정할 뿐이다. 튜플은 완전한 형태로 페이지에 남아 있다가 정리(pruning)나 vacuum이 회수한다.

// heap_delete — src/backend/access/heap/heapam.c (condensed, the commit path)
PageSetPrunable(page, xid);                 /* this page now has a deletable tuple */

/* store transaction information of xact deleting the tuple */
tp.t_data->t_infomask &= ~(HEAP_XMAX_BITS | HEAP_MOVED);
tp.t_data->t_infomask2 &= ~HEAP_KEYS_UPDATED;
tp.t_data->t_infomask |= new_infomask;
tp.t_data->t_infomask2 |= new_infomask2;
HeapTupleHeaderClearHotUpdated(tp.t_data);
HeapTupleHeaderSetXmax(tp.t_data, new_xmax);
HeapTupleHeaderSetCmax(tp.t_data, cid, iscombo);
/* Make sure there is no forward chain link in t_ctid */
tp.t_data->t_ctid = tp.t_self;

이 지점에 도달하기 전에 heap_delete는 동시성을 해결한다. HeapTupleSatisfiesUpdate를 호출해 튜플을 분류하고(TM_Ok, TM_BeingModified, TM_Updated, TM_Deleted, …), 다른 트랜잭션이 xmax를 갖고 있다면 그 트랜잭션(또는 그 MultiXact)을 기다린 뒤 재검사한다. PageSetPrunable(page, xid)은 페이지 헤더의 pd_prune_xid에, 이 페이지의 어떤 튜플을 정리 가능하게 만들 가장 오래된 XID를 기록한다. 나중에 heap_page_prune_opt가 할 일 없는 페이지를 건너뛸 수 있게 해 주는 힌트다. t_ctid를 명시적으로 자기 자신으로 재설정한다. 단순 삭제는 앞방향 링크를 남기지 않는다.

UPDATE — heap_update와 HOT 결정

갱신은 삭제와 삽입을 결합해 두 버전을 연결한다. 이전 튜플에는 삭제와 마찬가지로 xmax가 설정되고, 새 튜플이 기록되며, 이전 튜플의 t_ctid가 새 튜플을 가리킨다. 흥미로운 결정은 갱신이 HOT이 될 수 있는가이다.

heap_update는 먼저 실제로 바뀐 컬럼을 계산하고(HeapDetermineColumnsInfo → modified_attrs), 릴레이션의 “중요한” 인덱스 컬럼 비트맵을 가져온다. 새 튜플을 놓을 페이지를 확보한 뒤, 두 가지를 묻는다. 새 튜플이 같은 페이지에 들어갔는가, 그리고 갱신이 HOT 차단 인덱스 컬럼과 겹치지 않는가?

// heap_update — src/backend/access/heap/heapam.c (the HOT decision, condensed)
if (newbuf == buffer)
{
    /* same page: maybe a HOT update */
    if (!bms_overlap(modified_attrs, hot_attrs))
    {
        use_hot_update = true;
        /* still must propagate to summarizing (e.g. BRIN) indexes */
        if (bms_overlap(modified_attrs, sum_attrs))
            summarized_update = true;
    }
}
else
{
    /* new tuple went to a different page: cold update */
    PageSetFull(page);          /* hint: old page wants prune/defrag */
}

HOT이 적용되면 이전 튜플에 HEAP_HOT_UPDATED, 새 튜플에 HEAP_ONLY_TUPLE 플래그가 설정된다. 그렇지 않으면 두 플래그 모두 지워진다. 그 뒤 새 튜플이 배치되고 앞방향 링크가 기록된다.

// heap_update — src/backend/access/heap/heapam.c (condensed)
if (use_hot_update)
{
    HeapTupleSetHotUpdated(&oldtup);    /* old: HEAP_HOT_UPDATED */
    HeapTupleSetHeapOnly(heaptup);      /* new: HEAP_ONLY_TUPLE */
    HeapTupleSetHeapOnly(newtup);
}
else
{
    HeapTupleClearHotUpdated(&oldtup);
    HeapTupleClearHeapOnly(heaptup);
    HeapTupleClearHeapOnly(newtup);
}
RelationPutHeapTuple(relation, newbuf, heaptup, false);  /* insert new version */

/* old tuple gets xmax + forward link */
HeapTupleHeaderSetXmax(oldtup.t_data, xmax_old_tuple);
oldtup.t_data->t_infomask |= infomask_old_tuple;
HeapTupleHeaderSetCmax(oldtup.t_data, cid, iscombo);
oldtup.t_data->t_ctid = heaptup->t_self;     /* OLD points to NEW */

의미적 결론은 이렇다. HEAP_ONLY_TUPLE에는 인덱스 항목이 없다. 이 튜플에 도달하는 유일한 방법은 체인의 루트를 가리키는 인덱스 항목에서 시작해 HEAP_HOT_UPDATED 플래그가 설정된 동안 t_ctid를 따라가는 것이다. 인덱스 스캔이 정확히 그 방식으로 동작한다(다음 소절). 체인이 단일 페이지 안에 제약되므로, 체인을 따라가는 데 추가 버퍼 페치가 필요 없다.

flowchart LR
  IDX["인덱스 항목\n(key, TID=block:1)"] --> LP1
  subgraph PAGE["힙 페이지 하나"]
    direction LR
    LP1["lp 1 (LP_NORMAL)\n루트 튜플 v1\nHEAP_HOT_UPDATED\nt_ctid -> lp 2"]
    LP2["lp 2 (LP_NORMAL)\n튜플 v2\nHEAP_ONLY_TUPLE, HEAP_HOT_UPDATED\nt_ctid -> lp 3"]
    LP3["lp 3 (LP_NORMAL)\n튜플 v3 (살아 있음)\nHEAP_ONLY_TUPLE\nt_ctid -> self"]
    LP1 --> LP2 --> LP3
  end

그림 3 — HOT 체인. 인덱스는 라인 포인터 1(루트)만 가리킨다. v2와 v3는 HEAP_ONLY_TUPLE이어서 인덱스 항목이 없다. lp 1에 도착한 인덱스 스캔은 HEAP_HOT_UPDATED가 설정된 동안 t_ctid를 따라가 자신의 스냅샷에 보이는 버전 하나를 찾는다. 세 버전 모두 같은 페이지에 있으므로 추가 I/O가 없다. (메커니즘 출처: access/heap/README.HOT.)

HOT의 조건은 엄격하다(README.HOT, §“Update Chains With a Single Index Entry”). 갱신이 임의의 비-요약-인덱스에서 참조하는 컬럼을 전혀 바꾸지 않아야 하고(함수형 인덱스 표현식이나 부분 인덱스 술어에 사용되는 컬럼 포함), 새 버전이 이전 버전의 페이지에 들어가야 한다. 요약 인덱스(BRIN)는 튜플별 TID를 갖지 않으므로, HOT 갱신이 진행될 수 있지만 새 값을 전파해야 한다(summarized_update). 동등성 검사는 데이터 타입의 동등 연산자가 아닌 비트 단위로 수행된다. 여러 인덱스가 어떤 동등성 개념을 쓰는지 엔진이 알 수 없기 때문이다.

HOT 체인에 대한 인덱스 스캔 — heap_hot_search_buffer

인덱스 스캔이 TID를 힙 튜플로 해석할 때, 그 TID가 원하는 버전을 여전히 가리키고 있다고 맹목적으로 믿지 않는다. heap_hot_search_buffer를 호출한다. 이 함수는 (리다이렉트됐을 수 있는) 루트 라인 포인터에서 시작해 체인을 걸어가며 스냅샷에 가시적인 첫 번째 멤버를 반환한다.

// heap_hot_search_buffer — src/backend/access/heap/heapam.c (condensed)
for (;;)
{
    lp = PageGetItemId(page, offnum);

    if (!ItemIdIsNormal(lp))
    {
        /* a redirect is only legal at the chain start */
        if (ItemIdIsRedirected(lp) && at_chain_start)
        {
            offnum = ItemIdGetRedirect(lp);
            at_chain_start = false;
            continue;
        }
        break;          /* unused/dead → end of chain */
    }

    heapTuple->t_data = (HeapTupleHeader) PageGetItem(page, lp);
    /* ... set t_len, t_self ... */

    /* xmin of this link must equal xmax of the previous, else chain broke */
    if (TransactionIdIsValid(prev_xmax) &&
        !TransactionIdEquals(prev_xmax, HeapTupleHeaderGetXmin(heapTuple->t_data)))
        break;

    if (!skip)
    {
        valid = HeapTupleSatisfiesVisibility(heapTuple, snapshot, buffer);
        HeapCheckForSerializableConflictOut(valid, relation, heapTuple, buffer, snapshot);
        if (valid)
        {
            ItemPointerSetOffsetNumber(tid, offnum);
            PredicateLockTID(relation, &heapTuple->t_self, snapshot, ...);
            return true;
        }
    }
    /* not visible: if HOT-updated, advance to t_ctid; else end of chain */
    /* ... prev_xmax = HeapTupleHeaderGetUpdateXid(...); offnum = ctid offset ... */
}

두 가지 정확성 레일이 나타난다. 첫째, xmin/xmax 일치 검사다. 앞방향 링크를 따라갈 때 다음 튜플의 xmin이 이전 튜플의 xmax와 같아야 한다. 같지 않으면 슬롯이 vacuum에 의해 무관한 튜플로 재사용된 것이고 체인이 실제로 끝났다(README.HOT, §“Abort Cases”). 둘째, MVCC 스냅샷 기준으로 최대 하나의 체인 멤버만 가시적이다. 따라서 호출자(heapam_index_fetch_tuple)는 call_again = !IsMVCCSnapshot(snapshot)으로 설정한다. 비-MVCC 스냅샷(예: SnapshotDirty)은 여러 버전을 볼 수 있으므로 반복 구동이 필요하다.

가시성 — 스냅샷과 헤더 대조

heap_hot_search_buffer는 실제 예/아니오 판단을 HeapTupleSatisfiesVisibility에 위임하고, 일반 쿼리에서는 HeapTupleSatisfiesMVCC로 라우팅된다. 여기서 튜플 헤더가 스냅샷을 만난다. 논리는 2단계 검사다. 먼저 xmin이 가시적인지 결정하고(이 버전이 내게 존재하는가), 그 다음 xmax가 가시적인지 결정한다(이 버전이 내 스냅샷 이전에 삭제됐는가).

// HeapTupleSatisfiesMVCC — src/backend/access/heap/heapam_visibility.c (heavily condensed)
if (!HeapTupleHeaderXminCommitted(tuple))
{
    if (HeapTupleHeaderXminInvalid(tuple))
        return false;                       /* inserter aborted: never visible */
    else if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmin(tuple)))
    {
        if (HeapTupleHeaderGetCmin(tuple) >= snapshot->curcid)
            return false;                   /* my own insert, but later command */
        /* ... then fall through to xmax checks for my own delete ... */
    }
    else if (XidInMVCCSnapshot(HeapTupleHeaderGetRawXmin(tuple), snapshot))
        return false;                       /* inserter still in-flight at snapshot */
    else if (TransactionIdDidCommit(HeapTupleHeaderGetRawXmin(tuple)))
        SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED, HeapTupleHeaderGetRawXmin(tuple));
    else
    {
        SetHintBits(tuple, buffer, HEAP_XMIN_INVALID, InvalidTransactionId);
        return false;                       /* inserter aborted */
    }
}
else /* xmin already hinted committed */
{
    if (!HeapTupleHeaderXminFrozen(tuple) &&
        XidInMVCCSnapshot(HeapTupleHeaderGetRawXmin(tuple), snapshot))
        return false;                       /* committed, but after my snapshot */
}

/* by here the inserter is visible; now is it deleted-and-visible-as-deleted? */
if (tuple->t_infomask & HEAP_XMAX_INVALID)      return true;    /* never deleted */
if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask)) return true;   /* only locked */
/* ... resolve xmax (incl. MultiXact), test XidInMVCCSnapshot / DidCommit ... */

결정 트리를 정리하면 다음과 같다.

flowchart TD
  A["튜플 헤더"] --> B{"xmin 커밋됨\n그리고 스냅샷에 가시?"}
  B -- "아니오: 실행 중 또는 스냅샷 이후" --> R1["가시 아님"]
  B -- "아니오: 삽입자 중단" --> R1
  B -- "예" --> C{"xmax 설정됨?\n(HEAP_XMAX_INVALID 비트 꺼짐)"}
  C -- "아니오" --> R2["가시\n(살아 있음, 삭제 없음)"]
  C -- "예" --> D{"xmax가 잠금만?\n(HEAP_XMAX_LOCK_ONLY)"}
  D -- "예" --> R2
  D -- "아니오" --> E{"삭제자 커밋됨\n그리고 스냅샷에 가시?"}
  E -- "아니오: 삭제자 실행 중 또는 중단" --> R3["가시\n(삭제 아직 효력 없음)"]
  E -- "예" --> R4["가시 아님\n(스냅샷 이전에 삭제됨)"]

그림 4 — HeapTupleSatisfiesMVCC 결정 트리. 삽입자가 커밋됐고 내 스냅샷보다 먼저이면서, 삭제자가 없거나 삭제자도 커밋됐지만 내 스냅샷보다 나중인 경우에 버전이 가시적이다. XidInMVCCSnapshot(postgres-mvcc-snapshots.md 소유)이 “내 스냅샷의 실행 중 집합에 속하는가?”를 답하고, 나머지는 튜플 헤더의 로컬 읽기로 처리된다.

SetHintBits 호출은 §“DBMS 공통 설계 패턴”에서 말한 지연 힌트 비트 캐시다. xmin/xmax를 커밋 로그와 대조해 처음 해석한 독자가 HEAP_XMIN_COMMITTED / HEAP_XMIN_INVALID / HEAP_XMAX_COMMITTED를 튜플에 기록하면, 이후 독자는 CLOG 조회를 건너뛴다. 비트는 조언적 성격으로 커밋 로그가 이미 확정한 값으로만 설정된다. WAL 없이 공유 잠금 아래서 기록할 수 있는 이유가 여기 있다.

정리(Pruning) — 단일 페이지 회수

죽은 버전은 두 체제로 회수된다. 빠른 경로는 HOT 정리로, 페이지에 접근할 때 기회주의적으로 발동된다. heap_page_prune_opt는 페이지의 pd_prune_xid 힌트와 여유 공간 기준을 검사한 뒤, 조건부 클린업 락을 잡고 핵심 함수 heap_page_prune_and_freeze를 호출한다.

// heap_page_prune_opt — src/backend/access/heap/pruneheap.c (condensed)
prune_xid = ((PageHeader) page)->pd_prune_xid;
if (!TransactionIdIsValid(prune_xid))
    return;                                 /* nothing was ever deleted here */

vistest = GlobalVisTestFor(relation);
if (!GlobalVisTestIsRemovableXid(vistest, prune_xid))
    return;                                 /* nothing removable yet */

minfree = Max(RelationGetTargetPageFreeSpace(relation, HEAP_DEFAULT_FILLFACTOR),
              BLCKSZ / 10);
if (PageIsFull(page) || PageGetHeapFreeSpace(page) < minfree)
{
    if (!ConditionalLockBufferForCleanup(buffer))
        return;                             /* don't block; try again later */
    /* recheck under lock, then: */
    heap_page_prune_and_freeze(relation, buffer, vistest, 0,
                               NULL, &presult, PRUNE_ON_ACCESS, &dummy_off_loc, NULL, NULL);
}

두 가지 설계 주안점이 있다. 첫째, 정리는 기회주의적이고 비차단적이다. 클린업 락(배타 락보다 강함: 다른 백엔드가 핀조차 잡고 있으면 안 됨. 정리가 다른 이가 포인터를 들고 있는 튜플을 이동할 수 있기 때문)이 필요하고, 조건부 변형을 써서 동시 접근이 많은 페이지는 기다리지 않고 건너뛴다. 최악의 결과는 UPDATE가 여유 공간 부족으로 새 버전을 다른 페이지에 놓아야 하는 것뿐이다. 둘째, 정리는 거의 꽉 찬 페이지(< 10% 여유)를 조회하는 도중 발동되므로, SELECT, UPDATE, DELETE 모두 발동할 수 있지만, 행을 조회하지 않는 INSERT ... VALUES는 보통 발동하지 않는다(README.HOT, §“When can/should we prune or defragment?”).

체인 축소 로직은 heap_prune_chain에 있다. 각 HOT 체인의 멤버를 HeapTupleSatisfiesVacuum 결과로 분류하며, 슬롯을 리다이렉트·dead·unused 중 어느 것으로 바꿀지 결정한다.

// heap_prune_chain — src/backend/access/heap/pruneheap.c (control flow, condensed)
for (;;)
{
    lp = PageGetItemId(page, offnum);
    if (ItemIdIsRedirected(lp)) { /* jump to redirect target at chain start */ }
    htup = (HeapTupleHeader) PageGetItem(page, lp);

    /* chain integrity: this link's xmin must equal prior link's xmax */
    if (TransactionIdIsValid(priorXmax) &&
        !TransactionIdEquals(HeapTupleHeaderGetXmin(htup), priorXmax))
        break;

    chainitems[nchain++] = offnum;
    switch (htsv_get_valid_status(prstate->htsv[offnum]))
    {
        case HEAPTUPLE_DEAD:            ndeadchain = nchain;  break;   /* removable */
        case HEAPTUPLE_RECENTLY_DEAD:   break;                        /* keep, may follow */
        case HEAPTUPLE_LIVE:
        case HEAPTUPLE_INSERT_IN_PROGRESS:
        case HEAPTUPLE_DELETE_IN_PROGRESS:  goto process_chain;       /* stop here */
    }
    if (!HeapTupleHeaderIsHotUpdated(htup))  goto process_chain;      /* end of chain */
    offnum = ItemPointerGetOffsetNumber(&htup->t_ctid);              /* advance */
    priorXmax = HeapTupleHeaderGetUpdateXid(htup);
}

체인 정리 결과는 README.HOT의 기술과 정확히 일치한다.

flowchart LR
  subgraph BEFORE["정리 전"]
    direction TB
    B1["lp 1 (LP_NORMAL) 루트\nv1 DEAD\nctid -> 2"]
    B2["lp 2 (LP_NORMAL)\nv2 살아 있음\nHEAP_ONLY_TUPLE"]
    B1 --> B2
    BI["인덱스 -> lp 1"] -.-> B1
  end
  subgraph AFTER["정리 후"]
    direction TB
    A1["lp 1 (LP_REDIRECT)\nlp_off = 2\n튜플 없음"]
    A2["lp 2 (LP_NORMAL)\nv2 살아 있음"]
    A1 --> A2
    AI["인덱스 -> lp 1"] -.-> A1
  end
  BEFORE --> AFTER

그림 5 — 정리가 HOT 체인을 축소한다. 루트 튜플 v1이 죽었으므로 바이트가 회수되고 라인 포인터 1이 라인 포인터 2를 가리키는 LP_REDIRECT로 변환된다. lp 1을 가리키는 인덱스 항목은 리다이렉트를 따라 살아 있는 v2에 도달한다. 체인의 마지막 살아 있는 멤버까지 죽으면 루트가 LP_REDIRECT 대신 LP_DEAD가 된다. 인덱스 항목이 아직 있으므로 해제할 수 없고, 다음 vacuum이 인덱스 항목과 함께 dead 슬롯을 제거한다. (메커니즘 출처: access/heap/README.HOT, §“Pruning”.)

여기서 vacuum(postgres-vacuum.md)과의 정확한 경계선이 드러난다. 정리는 페이지 로컬 조작만으로 튜플 바이트를 회수하고 체인을 축소하며 인덱스를 건드리지 않는다. 루트를 리다이렉트나 dead 라인 포인터로 강등할 수 있지만, dead 라인 포인터 자체는 해제할 수 없다. 인덱스 항목이 아직 그것을 가리키기 때문이다. dead 라인 포인터와 그것을 붙잡고 있는 인덱스 항목을 해제하는 것이 vacuum의 몫이다. 정리는 라인 포인터를 강등하고, vacuum은 그것을 매장한다.

소스 코드 가이드

심볼 이름에 닻을 내려야 한다. 줄 번호가 아니다. PostgreSQL 소스는 이동하지만 함수·구조체·매크로 이름은 대부분의 리팩터에서 살아남는다. git grep -n '<심볼>' src/backend/access/heap/으로 현재 위치를 찾는다. 위치 힌트 표의 줄 번호는 커밋 273fe94(REL_18_STABLE) 기준 빠른 힌트다.

튜플·페이지 배치 (src/include/)

• struct HeapTupleHeaderData (htup_details.h) — 온디스크 튜플 헤더. t_choice 유니온(t_heap: t_xmin/t_xmax/t_cid, 또는 인메모리 복합 Datum용 t_datum 오버레이), t_ctid, t_infomask2, t_infomask, t_hoff, t_bits[].
• HeapTupleHeaderGetXmin / …SetXmin / …GetRawXmax / …SetXmax (htup_details.h) — 정규 접근자. …GetXmin은 프리즈된 튜플이면 FrozenTransactionId를 반환한다.
• HeapTupleHeaderGetUpdateXid (htup_details.h) — HEAP_XMAX_IS_MULTI 설정 시 MultiXact를 거쳐 xmax를 해석한다.
• HeapTupleHeaderIsHotUpdated / …IsHeapOnly 및 Set/Clear 형태 — t_infomask2의 HOT 플래그 접근자.
• HEAP_XMIN_COMMITTED, HEAP_XMIN_INVALID, HEAP_XMIN_FROZEN, HEAP_XMAX_COMMITTED, HEAP_XMAX_INVALID, HEAP_XMAX_IS_MULTI, HEAP_XMAX_LOCK_ONLY (htup_details.h) — t_infomask 가시성 비트.
• HEAP_HOT_UPDATED, HEAP_ONLY_TUPLE (htup_details.h) — t_infomask2 HOT 플래그.
• struct ItemIdData와 LP_UNUSED / LP_NORMAL / LP_REDIRECT / LP_DEAD (storage/itemid.h) — 4-상태 라인 포인터.

테이블 AM 바인딩 (src/include/access/tableam.h, heapam_handler.c)

• struct TableAmRoutine (tableam.h) — 함수 포인터 인터페이스. tuple_insert, tuple_update, tuple_delete, index_fetch_tuple, scan_begin 등.
• heapam_methods (heapam_handler.c) — 힙의 완성된 루틴.
• GetHeapamTableAmRoutine / heap_tableam_handler (heapam_handler.c) — 루틴 반환(후자가 SQL-가시 am_handler).
• heapam_tuple_insert / heapam_tuple_update / heapam_tuple_delete / heapam_index_fetch_tuple (heapam_handler.c) — TupleTableSlot을 풀어 heapam.c 함수를 호출하는 얇은 래퍼.

힙 연산 (src/backend/access/heap/heapam.c)

• heap_insert — 헤더 도장, 튜플 배치, WAL. 중단 시 무연산인 정리 주석이 여기 있다.
• heap_prepare_insert — xmin/cmin 설정, xmax 초기화, 옵션 프리즈, 오버사이즈 시 TOAST.
• heap_multi_insert — 배치 삽입(페이지당 WAL 레코드 하나, 락 사이클 하나).
• heap_delete — HeapTupleSatisfiesUpdate로 동시성 해결, xmax + PageSetPrunable 설정, 튜플 제자리 유지.
• heap_update — modified_attrs 계산(HeapDetermineColumnsInfo), use_hot_update 결정, 새 튜플 배치, 이전 xmax와 t_ctid 앞방향 링크 설정.
• heap_hot_search_buffer — 루트에서 HOT 체인을 걸어가며 스냅샷에 가시적인 멤버를 반환. xmin/xmax 체인 무결성 검사 적용.

가시성 (src/backend/access/heap/heapam_visibility.c)

• HeapTupleSatisfiesVisibility — 스냅샷 유형별 디스패처.
• HeapTupleSatisfiesMVCC — xmin/xmax에 대한 SI 가시성 결정.
• HeapTupleSatisfiesUpdate — heap_delete/heap_update가 쓰는 쓰기 측 분류(TM_Ok, TM_BeingModified, …).
• HeapTupleSatisfiesVacuum / HeapTupleSatisfiesVacuumHorizon — 정리/vacuum 분류(HEAPTUPLE_DEAD, …_RECENTLY_DEAD, …).
• SetHintBits — 해석된 커밋 결과를 튜플에 지연 캐시.
• XidInMVCCSnapshot — 스냅샷 멤버십 검사. 스냅샷 기계는 postgres-mvcc-snapshots.md.

페이지 배치와 정리 (hio.c, pruneheap.c)

• RelationPutHeapTuple (hio.c) — PageAddItem + t_self 및 자기 참조 t_ctid 설정.
• RelationGetBufferForTuple (hio.c) — 여유 있는 페이지 찾기/확장(FSM 참조).
• heap_page_prune_opt (pruneheap.c) — 접근 시 기회주의적 정리 진입. pd_prune_xid와 여유 공간 기준 검사, 조건부 클린업 락.
• heap_page_prune_and_freeze (pruneheap.c) — 접근 시 정리와 vacuum이 공유하는 핵심 함수.
• heap_prune_chain (pruneheap.c) — HOT 체인 하나를 분류·축소.
• heap_page_prune_execute (pruneheap.c) — 리다이렉트/dead/unused 결정을 페이지에 적용.

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

심볼	파일	줄
struct HeapTupleFields	htup_details.h	122
struct HeapTupleHeaderData	htup_details.h	153
#define HEAP_XMIN_COMMITTED	htup_details.h	204
#define HEAP_HOT_UPDATED	htup_details.h	295
#define HEAP_ONLY_TUPLE	htup_details.h	296
HeapTupleHeaderGetUpdateXid	htup_details.h	402
HeapTupleHeaderIsHotUpdated	htup_details.h	539
struct ItemIdData	storage/itemid.h	25
typedef struct TableAmRoutine	access/tableam.h	288
heapam_index_fetch_tuple	heapam_handler.c	115
heapam_tuple_insert	heapam_handler.c	244
heapam_tuple_delete	heapam_handler.c	303
heapam_tuple_update	heapam_handler.c	317
heapam_methods	heapam_handler.c	2616
GetHeapamTableAmRoutine	heapam_handler.c	2676
heap_hot_search_buffer	heapam.c	1717
heap_insert	heapam.c	2080
heap_prepare_insert	heapam.c	2271
heap_multi_insert	heapam.c	2351
heap_delete	heapam.c	2773
heap_update	heapam.c	3242
HeapDetermineColumnsInfo	heapam.c	4396
SetHintBits	heapam_visibility.c	114
HeapTupleSatisfiesUpdate	heapam_visibility.c	458
HeapTupleSatisfiesMVCC	heapam_visibility.c	960
HeapTupleSatisfiesVacuum	heapam_visibility.c	1171
HeapTupleSatisfiesVisibility	heapam_visibility.c	1776
RelationPutHeapTuple	hio.c	35
RelationGetBufferForTuple	hio.c	502
heap_page_prune_opt	pruneheap.c	193
heap_page_prune_and_freeze	pruneheap.c	350
heap_prune_chain	pruneheap.c	999
heap_page_prune_execute	pruneheap.c	1561

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

각 항목은 커밋 273fe94(REL_18_STABLE) 현재 소스에 대한 사실이다. 외부 자료 없이 읽을 수 있다. 뒤에 붙는 주석은 검증 방법과 해석 한계를 보여 준다. 미해결 항목은 아래 미결 질문에 있다.

검증된 사실

• 힙 튜플 헤더는 NULL 비트맵 이전에 23바이트이며, xmin/xmax는 항상 물리적으로 저장되고, cmin/cmax/xvac는 4바이트 필드 하나를 공유한다. htup_details.h의 struct HeapTupleHeaderData와 HeapTupleFields를 읽어 확인(t_field3 유니온과 /* ^ - 23 bytes - ^ */ 마커). 구조체 위 주석 블록이 5개 가상 필드를 3개 물리 필드에 담는 방식과 콤보-CID 폴백(combocid.c)을 문서화한다.

• HEAP_XMIN_FROZEN은 HEAP_XMIN_COMMITTED와 HEAP_XMIN_INVALID의 비트 OR다. htup_details.h에서 확인: #define HEAP_XMIN_FROZEN (HEAP_XMIN_COMMITTED|HEAP_XMIN_INVALID). 논리적으로 모순인 조합이 프로즌 센티넬로 재활용된다. 프리즈 메커니즘은 postgres-vacuum.md에 있다.

• 방금 삽입된 튜플의 t_ctid는 자기 자신을 가리킨다. UPDATE는 이전 튜플의 t_ctid를 새 버전의 슬롯으로 재작성한다. RelationPutHeapTuple(hio.c, item->t_ctid = tuple->t_self)과 heap_update(oldtup.t_data->t_ctid = heaptup->t_self)에서 확인. heap_delete는 t_ctid를 명시적으로 자기 자신으로 재설정하므로(tp.t_data->t_ctid = tp.t_self) 단순 삭제는 앞방향 링크를 남기지 않는다.

• HOT 선택 조건은 새 튜플이 같은 페이지에 들어가는 것 AND 갱신이 HOT 차단 인덱스 컬럼과 겹치지 않는 것이다. heap_update에서 확인: if (newbuf == buffer) 가드가 if (!bms_overlap(modified_attrs, hot_attrs)) use_hot_update = true;를 감싼다. 요약 인덱스와의 겹침은 summarized_update를 설정하지만 HOT을 막지는 않는다.

• HOT 동등성은 데이터 타입 동등 연산자가 아닌 비트 단위로 검사한다. README.HOT(§“Update Chains…”, “We insist on bitwise equality rather than using datatype-specific equality routines”)에 명시되어 있고, heapam.c의 HeapDetermineColumnsInfo가 어트리뷰트 이미지를 비교하는 방식으로 구현된다.

• 앞방향 체인 링크를 따라갈 때 다음 튜플의 xmin이 이전 튜플의 xmax와 같아야 한다. 같지 않으면 체인이 끝난 것이다. heap_hot_search_buffer와 heap_prune_chain 모두에서 확인(TransactionIdEquals(..., priorXmax) / prev_xmax 가드). README.HOT §“Abort Cases”가 이 가드가 방어하는 경쟁 조건, 즉 슬롯 재사용 케이스를 설명한다.

• 접근 시 정리는 조건부 클린업 락이 필요하며, 얻지 못하면 페이지를 조용히 건너뛴다. heap_page_prune_opt에서 확인: if (!ConditionalLockBufferForCleanup(buffer)) return;. 여유 공간 기준은 Max(fillfactor 대상, BLCKSZ/10)이고, 정리 필요 힌트는 페이지 헤더의 pd_prune_xid다.

• 정리는 인덱스를 건드리지 않는다. 루트 라인 포인터를 LP_REDIRECT나 LP_DEAD로 강등할 수 있지만 dead 라인 포인터 자체는 해제할 수 없다. heap_prune_chain / heap_page_prune_execute를 읽어 확인(페이지의 라인 포인터와 튜플 저장소만 조작). README.HOT §“Pruning”과 §“VACUUM”으로 재확인. 라인 포인터 매장은 vacuum의 역할(postgres-vacuum.md).

• 힙은 heapam_methods TableAmRoutine 경로로만 도달한다. heap_tableam_handler가 &heapam_methods를 반환하고, 루틴의 tuple_insert/tuple_update/tuple_delete/index_fetch_tuple 슬롯이 heapam_handler.c의 heapam_* 래퍼를 가리키는 것을 확인. AM 계약은 postgres-table-am.md 소유.

미결 질문

1. HOT 체인 최대 길이와 라인 포인터 비대화. README.HOT은 페이지당 라인 포인터를 MaxHeapTuplesPerPage로 “임의로” 제한해 비대화를 막는다고 적고, 통계를 위한 잘라내기-to-라인-포인터 설계가 “아마도 추가 작업이 필요하다”고 언급한다. 같은 페이지를 반복 갱신하는 병리적 워크로드에서 콜드 갱신이 강제되기 전까지 체인이 실제로 얼마나 길어지는가, 그리고 vacuum 사이에 라인 포인터 비대화가 얼마나 지속되는가. 조사 경로: heap_prune_chain의 nchain을 계측하고 n_tup_hot_upd pgstats와 상관 분석.

2. pd_prune_xid 정밀도 대 낭비 정리 시도. heap_page_prune_opt는 락 없이 페이지 여유 공간을 휴리스틱으로 읽는다(“최악의 경우 잘못된 답을 얻을 수 있다”). 클린업 락 획득에 성공했지만 제거 가능한 것이 없는 경우가 얼마나 자주 발생하는가. 조사 경로: heap_page_prune_and_freeze에서 ndeleted가 0인 ConditionalLockBufferForCleanup 성공 횟수 계산.

3. 삭제·잠금 경로의 MultiXact 상호작용. heap_delete는 HEAP_XMAX_IS_MULTI에 따라 분기가 많고(MultiXactIdWait 대기), xmax가 일반 XID 대신 MultiXact를 가리킬 수 있다. 전체 MultiXact 수명 주기(할당, 멤버 저장, HEAP_XMAX_LOCK_ONLY 상호 작용)는 여기서 개략만 다뤘다. 조사 경로: 계획된 postgres-xid-wraparound-freeze.md / multixact 문서와 README.tuplock 교차 참조.

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

포인터이지 분석이 아니다. 각 항목은 후속 문서를 시작하기 위한 출발점이며 깊이는 의도적으로 얕다.

• 제자리 덮어쓰기 + undo (Oracle, MySQL/InnoDB). 이 엔진들은 살아 있는 행을 덮어쓰고 이전 이미지를 undo 세그먼트에 보관하며 행에 롤백 포인터를 단다. PostgreSQL과 대칭적인 트레이드오프다. 압축된 힙과 테이블 vacuum 불필요를 얻는 대신 undo 세그먼트 관리와 오래된 버전 재구성 시 읽기 증폭을 치른다. PostgreSQL HOT/정리 비용 대 InnoDB undo 비용을 측정해 비교하면 덮어쓰기 없는 방식의 세금을 정량화할 수 있다. (Stonebraker 1987이 덮어쓰기 없는 방식의 논거이고, Database Internals 5장이 두 계열을 모두 다룬다.)

• CUBRID의 외부 배치 MVCC. CUBRID는 PostgreSQL이 xmin/xmax를 찍는 것처럼 레코드 헤더에 mvcc_ins_id/mvcc_del_id를 찍지만, 이전 버전들을 힙 페이지에서 앞으로 체인으로 잇는 대신 prev_version_lsa로 로그를 역방향으로 연결한다. PostgreSQL의 같은 페이지 앞방향 HOT 체인과 대조하면 시사하는 바가 있다. CUBRID는 오래된 버전을 읽을 때 로그 간접 참조를 치르는 대신 힙을 컴팩트하게 유지하고, PostgreSQL은 비대화와 vacuum을 치르는 대신 이전 버전을 페이지 위에 둔다. knowledge/code-analysis/cubrid/cubrid-mvcc.md 참조.

• PostgreSQL을 위한 undo 로그: zheap. 미완성인 zheap 프로젝트는 비대화와 vacuum에서 벗어나기 위해 PostgreSQL에 undo가 있는 제자리 저장 AM을 추가하려 했다. 플러그인 가능한 TableAmRoutine이 근본적으로 다른 저장 모델을 수용하도록 설계됐다는 가장 명확한 증거다. zheap이 무엇을 바꾸려 했는지, 그리고 왜 중단됐는지를 추적하는 문서는 postgres-table-am.md 옆에 있어야 한다.

• 인메모리 MVCC 버전 레이아웃 (HyPer, Hekaton, Cicada). 캐시 의식적 인메모리 엔진들은 버전 체인을 재설계하고(최신-to-최고 델타, 튜플별 버전 벡터) 중앙 레지스트리를 흔히 없앤다. Wu et al., An Empirical Evaluation of In-Memory MVCC (VLDB 2017)가 이 공간을 조사한다. MVCC 자체에 내재된 비용과 디스크 상주, 덮어쓰기 없는 MVCC인 PostgreSQL에 내재된 비용을 구별하는 올바른 닻이다.

• 시간 여행, 원래의 목표. Stonebraker의 1987년 저장 논문은 AS OF 역사적 쿼리를 지원하고 WAL을 없애기 위해 모든 버전을 유지했다. PostgreSQL은 둘 다 버렸지만 덮어쓰지 않는 힙은 유지했다. 시간/시간 여행 기능의 현대적 재등장(SQL:2011 시스템-버전 테이블)은 “PostgreSQL이 무엇을 포기했고 되찾으려면 얼마나 드는가”를 역사적 관점으로 정리할 만한 주제다.

출처

트리 내 README

• src/backend/access/heap/README.HOT — 권위 있는 HOT 명세. 단일 인덱스 항목 갱신 체인, 리다이렉트/dead 라인 포인터, 정리 대 조각 모음, 중단 케이스 체인 무결성, CREATE INDEX [CONCURRENTLY] 상호 작용, 이 문서 전체에서 쓰인 용어 정의.

교과서 장 (knowledge/research/dbms-general/ 내)

• Database System Concepts (Silberschatz et al., 7판), 13장 “Data Storage Structures” — 파일 구성, 슬롯 페이지, 레코드 배치.
• Database Internals (Petrov), 3장 “File Formats”(슬롯 페이지)와 5장 “Transaction Processing and Recovery” §“Multiversion Concurrency Control” / §“Isolation Levels”.

논문 (knowledge/research/dbms-papers/와 서지 목록)

• Stonebraker, The Design of the POSTGRES Storage System (VLDB 1987) — PostgreSQL 힙이 물려받은 덮어쓰기 없는 저장 논거. .omc/plans/postgres-paper-bibliography.md §2(획득 대기 목록) 참조.

PostgreSQL 소스 (/data/hgryoo/references/postgres/, REL_18 273fe94)

• src/backend/access/heap/heapam.c
• src/backend/access/heap/heapam_handler.c
• src/backend/access/heap/heapam_visibility.c
• src/backend/access/heap/hio.c
• src/backend/access/heap/pruneheap.c
• src/include/access/htup_details.h
• src/include/access/tableam.h
• src/include/storage/itemid.h

교차 참조 (형제 문서)

• postgres-table-am.md — 힙이 구현하는 TableAmRoutine 계약.
• postgres-mvcc-snapshots.md — 스냅샷 생성과 XidInMVCCSnapshot.
• postgres-visibility-map.md — 삽입/삭제 시 지워지는 all-visible 비트.
• postgres-vacuum.md — 조율 회수, 프리징, dead 라인 포인터 매장.
• postgres-page-layout.md — 전체 힙 페이지 기하(PageHeaderData, PageAddItem).