(KO) PostgreSQL 스캔 노드 — 순차 스캔, 인덱스 스캔, 비트맵 스캔, TID 스캔

목차

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

학술적 배경

리프 스캔 노드(leaf scan node)는 Volcano 이터레이터 모델이 물리적 저장소와 만나는 지점이다. 모든 쿼리 플랜 트리는 리프에 스캔을 둔다. 스캔 노드는 실제로 릴레이션에서 튜플을 읽어 내는 유일한 노드이고, 그 위의 조인·정렬·집계 노드들은 스캔 노드로부터 튜플을 끌어올린다. Database System Concepts(Silberschatz, 7판, 15장 “Query Processing”)는 스캔 전략을 데이터를 통과하는 경로로 구분한다.

• 풀 테이블 스캔(full table scan). 어떤 튜플이 필요한지와 무관하게 릴레이션의 모든 페이지를 읽은 뒤 선택 조건(selection predicate)으로 걸러 낸다. 비용은 릴레이션의 블록 수에 비례하고 조건의 선택도와는 무관하다. 큰 릴레이션에서 선택도가 낮은 조건을 처리할 때는 순차적이고 예측 가능한 I/O 덕분에 이 방식이 가장 저렴한 경우가 많다(§12.3).
• 인덱스 스캔(index scan). 인덱스를 검색 키 순서로 탐색해 조건을 만족하는 튜플의 레코드 식별자(RID)만 먼저 가져온 뒤, 각 RID로 힙 튜플을 가져온다. 비용은 인덱스 탐색 비용과 힙 페치 비용의 합이다. 인덱스가 매우 선택적이고 릴레이션이 클 때는 RID마다 서로 다른 디스크 블록을 가리킬 수 있어 힙 페치 비용(무작위 I/O)이 지배한다. 선택도가 낮으면 총 무작위 I/O 비용이 풀 스캔을 초과할 수 있다.
• 인덱스 전용 스캔(index-only scan). 쿼리가 인덱스에 저장된 속성만 조회하는 경우(커버링 인덱스), 엔진은 힙을 전혀 읽지 않고 인덱스만으로 쿼리를 완결할 수 있다. 교과서는 이를 covering-index scan 또는 key-only scan이라 부른다. 비용은 인덱스 탐색 비용뿐이다(§15.3.1).

교과서는 또한 비트맵 기반 스캔의 동기를 설명한다(§15.3.3). 조건의 서로 다른 부분을 각각 커버하는 인덱스가 여럿 있을 때, 엔진은 인덱스별로 독립적으로 평가한 결과 비트맵을 AND 또는 OR로 합산하고, 최종 비트맵에 등장하는 힙 페이지만 가져온다. 핵심 통찰은 힙 접근을 블록 번호 순서로 정렬하면 다수의 무작위 I/O가 대부분 순차적인 패스로 바뀐다는 점이다. MySQL(“index merge”), Oracle(“bitmap AND/OR”) 등 주요 상용 엔진이 이 기법을 채택하고 있다.

실제 스캔 구현을 좌우하는 설계 축이 두 가지 있다.

1. 조건 평가 위치. 조건을 스캔 내부로 밀어 넣어 튜플 단위로 평가할 수도 있고, 스캔 위의 조인·필터 레이어에서 평가할 수도 있다. PostgreSQL은 ExecScan 안으로 qual(조건) 평가를 밀어 넣어 조건을 통과하지 못한 튜플은 스캔 노드를 절대 벗어나지 않게 한다.

2. 가시성 게이팅(visibility gating). 힙에 저장된 튜플이 인덱스의 가리킴을 받더라도 현재 스냅샷에서 보이지 않을 수 있다 (postgres-mvcc-snapshots.md 참고). 스캔은 튜플 반환 과정의 일부로 MVCC 가시성 검사를 반드시 수행해야 한다. 이 검사를 지연할 수도 있고(힙 페치 후 가시성 검사), 가시성 맵을 이용해 생략할 수도 있다 (아래 참고).

DBMS 공통 설계 패턴

프로덕션 엔진 대부분은 스캔 노드 설계에서 동일한 구조적 선택에 수렴한다. 이 공유 설계 공간을 파악하면 PostgreSQL의 구체적 선택들이 더 잘 읽힌다.

두 함수 접근 메서드 인터페이스

스캔은 두 AM 콜백으로 표현된다. 다음 원시 튜플을 반환하는 접근 함수 (access function) 와, 인덱스가 손실 있는(lossy) 경우(페이지 수준 술어를 저장해 정밀도가 낮을 때) 힙 튜플의 인덱스 조건을 재검사하는 재검사 함수(recheck function) 가 그것이다. PostgreSQL은 이를 ExecScanAccessMtd와 ExecScanRecheckMtd로 표현한다. qual 평가, 프로젝션, EPQ 처리 등 외부 루프 로직은 여섯 노드 유형이 공유하는 ExecScan/ExecScanExtended 함수로 인수분해된다. 노드 유형마다 다른 것은 접근 함수와 재검사 함수뿐이다.

스캔 디스크립터의 지연 초기화

모든 엔진은 첫 번째 next() 호출 시점까지 스캔 디스크립터 열기를 미룬다. 이는 중요한 설계 결정이다. 플랜은 실행 전에 구성되고, 일부 노드(예: 중첩 루프의 내부 측)는 외부 행마다 다시 열린다. Init 시점에 스캔 디스크립터를 열면 실행되지 않는 분기에서 불필요한 작업이 생긴다. PostgreSQL은 접근 함수 첫 호출 시 ss_currentScanDesc == NULL을 확인하고 그 자리에서 디스크립터를 연다.

DSM 확장으로서의 병렬 스캔

병렬 테이블 스캔(순차·인덱스 모두)은 동적 공유 메모리(DSM)에 할당된 공유 스캔 디스크립터로 작업을 분배한다. PostgreSQL의 모든 스캔 노드 유형에 걸쳐 일관된 네 함수 프로토콜이 사용된다. Estimate(DSM 영역 크기 산정), InitializeDSM(리더가 공유 디스크립터 설정), ReInitializeDSM(재스캔을 위한 재설정), InitializeWorker (워커가 공유 디스크립터에 붙기). 실제 작업 분할 로직은 AM 레이어 (table_parallelscan_*, index_parallelscan_* 패밀리)에 있다.

조건 유무에 따른 스캔 특화

qual 없음 + 프로젝션 없음 조합은 두 가지가 모두 있는 경우보다 단순하게 더 빠르다. 내부 루프가 다음 튜플을 가져다 반환하는 것 말고 아무것도 하지 않기 때문이다. PostgreSQL의 ExecInitSeqScan은 qual, 프로젝션, EPQ 유무에 따라 ExecProcNode를 다섯 특화 변형 중 하나로 설정한다. ExecSeqScan, ExecSeqScanWithQual, ExecSeqScanWithProject, ExecSeqScanWithQualProject, ExecSeqScanEPQ가 그것이다. 각 변형은 없는 컴포넌트에 컴파일 타임 NULL 상수를 전달하여, 컴파일러가 공통 빠른 경로에서 그 분기를 제거하도록 한다.

두 단계 연산으로서의 비트맵 스캔

비트맵 스캔은 두 개의 분리된 플랜 노드로 구성된다. BitmapIndexScan(또는 그것들의 BitmapAnd/BitmapOr 트리)이 외부 서브플랜으로 실행되어 개별 튜플이 아닌 TIDBitmap을 MultiExecProcNode로 반환한다. BitmapHeapScan 노드는 그 비트맵을 순회하면서 힙 블록 번호 순서로 접근을 묶어 무작위 I/O를 줄인다. 비트맵 자체는 TID당 1비트의 정확 모드로 시작하고, work_mem을 초과하면 페이지 수준 손실 모드로 자연스럽게 저하된다.

PostgreSQL의 구현

PostgreSQL은 ExecScan 프레임워크에 연결된 여섯 종류의 리프 스캔 노드를 제공한다. 노드들은 세 계열로 깔끔하게 나뉜다.

flowchart TD
  ES["ExecScan / ExecScanExtended<br/>qual 평가 + 프로젝션 + EPQ"]
  SS["SeqScan<br/>table_beginscan + table_scan_getnextslot"]
  IS["IndexScan<br/>index_beginscan + index_getnext_slot<br/>+ 힙 페치"]
  IOS["IndexOnlyScan<br/>index_beginscan xs_want_itup=true<br/>VM 확인 → all-visible이면 힙 생략"]
  BHS["BitmapHeapScan<br/>MultiExecProcNode → TIDBitmap<br/>table_scan_bitmap_next_tuple"]
  BIS["BitmapIndexScan<br/>MultiExecProcNode가 TIDBitmap 반환"]
  TS["TidScan<br/>table_tuple_fetch_row_version<br/>명시적 ctid 목록 사용"]
  TRS["TidRangeScan<br/>table_beginscan_tidrange<br/>ctid 범위 경계 사용"]
  ES --> SS
  ES --> IS
  ES --> IOS
  ES --> BHS
  BHS --> BIS
  ES --> TS
  ES --> TRS

그림 1 — 여섯 스캔 노드 유형이 ExecScan 외부 루프를 공유한다. BitmapHeapScan의 내부 서브플랜은 BitmapIndexScan(또는 And/Or 트리)이며, MultiExecProcNode로 TIDBitmap을 반환한다.

공유 스캔 루프: ExecScan과 ExecScanExtended

ExecScan은 노드에서 epqstate, qual, projInfo를 읽어 ExecScanExtended에 위임하는 얇은 래퍼다. 확장 형태는 이 값들을 명시적 파라미터로 받아, 특화된 SeqScan 변형들이 컴파일 타임 NULL 상수를 전달할 수 있게 한다.

// ExecScan — src/backend/executor/execScan.c
TupleTableSlot *
ExecScan(ScanState *node,
         ExecScanAccessMtd accessMtd,
         ExecScanRecheckMtd recheckMtd)
{
    EPQState   *epqstate = node->ps.state->es_epq_active;
    ExprState  *qual     = node->ps.qual;
    ProjectionInfo *projInfo = node->ps.ps_ProjInfo;

    return ExecScanExtended(node, accessMtd, recheckMtd,
                            epqstate, qual, projInfo);
}

ExecScanExtended 내부의 공유 루프는 accessMtd를 호출해 다음 원시 튜플을 얻고, qual을 적용하고(NULL이 아닌 경우), 프로젝션을 수행하고 (NULL이 아닌 경우), EPQ 재평가를 처리한다. 이 로직은 어떤 스캔 노드도 중복하지 않는다.

SeqScan — 테이블 AM을 통한 풀 테이블 스캔

SeqScan은 가장 단순한 노드다. SeqNext는 첫 번째 호출 시 table_beginscan으로 TableScanDesc를 열고, estate->es_direction에 따른 방향으로 table_scan_getnextslot을 호출한다.

// SeqNext — src/backend/executor/nodeSeqscan.c
static TupleTableSlot *
SeqNext(SeqScanState *node)
{
    TableScanDesc scandesc = node->ss.ss_currentScanDesc;
    EState       *estate   = node->ss.ps.state;
    ScanDirection direction = estate->es_direction;
    TupleTableSlot *slot   = node->ss.ss_ScanTupleSlot;

    if (scandesc == NULL)
    {
        scandesc = table_beginscan(node->ss.ss_currentRelation,
                                   estate->es_snapshot, 0, NULL);
        node->ss.ss_currentScanDesc = scandesc;
    }
    if (table_scan_getnextslot(scandesc, direction, slot))
        return slot;
    return NULL;
}

재검사 함수인 SeqRecheck는 항상 true를 반환한다. 순차 스캔은 인덱스 키를 전혀 사용하지 않으므로 재검사할 것이 없기 때문이다.

ExecInitSeqScan은 qual, 프로젝션, EPQ 유무에 따라 다섯 특화 변형 중 하나를 ExecProcNode로 선택한다.

// ExecInitSeqScan (발췌) — src/backend/executor/nodeSeqscan.c
if (scanstate->ss.ps.state->es_epq_active != NULL)
    scanstate->ss.ps.ExecProcNode = ExecSeqScanEPQ;
else if (scanstate->ss.ps.qual == NULL)
{
    if (scanstate->ss.ps.ps_ProjInfo == NULL)
        scanstate->ss.ps.ExecProcNode = ExecSeqScan;
    else
        scanstate->ss.ps.ExecProcNode = ExecSeqScanWithProject;
}
else
{
    if (scanstate->ss.ps.ps_ProjInfo == NULL)
        scanstate->ss.ps.ExecProcNode = ExecSeqScanWithQual;
    else
        scanstate->ss.ps.ExecProcNode = ExecSeqScanWithQualProject;
}

각 변형은 없는 컴포넌트에 NULL을 전달한다. 예를 들어 ExecSeqScan은 epqstate, qual, projInfo 자리에 NULL, NULL, NULL을 넘겨, 컴파일러가 ExecScanExtended 안의 해당 분기를 제거하게 한다.

병렬 지원은 표준 네 함수 프로토콜을 따른다. ExecSeqScanEstimate는 table_parallelscan_estimate로 DSM 영역 크기를 산정하고, ExecSeqScanInitializeDSM은 공유 디스크립터를 할당하고 table_parallelscan_initialize를 호출한다. ExecSeqScanInitializeWorker는 table_beginscan_parallel로 공유 디스크립터에 붙는다.

IndexScan — 인덱스 구동 힙 페치

IndexNext는 첫 호출 시 index_beginscan으로 IndexScanDesc를 열고 (지연 초기화), 런타임 스캔 키를 적용한 뒤 index_getnext_slot 루프를 돈다. index_getnext_slot은 인덱스가 손실 있는 경우 xs_recheck를 설정한다.

// IndexNext (발췌) — src/backend/executor/nodeIndexscan.c
while (index_getnext_slot(scandesc, direction, slot))
{
    CHECK_FOR_INTERRUPTS();
    if (scandesc->xs_recheck)
    {
        econtext->ecxt_scantuple = slot;
        if (!ExecQualAndReset(node->indexqualorig, econtext))
        {
            InstrCountFiltered2(node, 1);
            continue;
        }
    }
    return slot;
}
node->iss_ReachedEnd = true;
return ExecClearTuple(slot);

index_getnext_slot은 인덱스 AM이 반환한 TID로 힙 튜플을 가져온다. 가시성 검사는 힙 AM 안에서 쿼리 스냅샷(estate->es_snapshot)을 사용해 수행된다. xs_recheck 플래그는 손실 있는 인덱스 AM(GIN, GiST 중 튜플 수준 정밀도를 저장하지 않는 경우)이 설정하며, 이때 가져온 힙 튜플에 원래 인덱스 조건(indexqualorig)을 재평가한다.

IndexNextWithReorder는 쿼리에 인덱스 연산자에 대한 ORDER BY 표현식이 포함된 경우를 처리한다. 튜플을 페어링 힙 재정렬 큐(iss_ReorderQueue)에 넣어 두고, 근사 순서로 반환된 값을 거리 값 재검사 후 순서대로 방출한다.

ExecIndexBuildScanKeys(1158번 줄)는 플래너의 IndexScan.indexqual 목록을 인덱스 AM이 기대하는 ScanKey 배열로 변환한다. 실행 시점에 평가해야 하는 조건(예: WHERE col = $1 같은 런타임 키)은 iss_RuntimeKeys로 분리되어 첫 번째 index_rescan 전에 ExecIndexEvalRuntimeKeys로 평가된다.

IndexOnlyScan — 가시성 맵을 통한 힙 우회

IndexOnlyScan은 IndexScan에 구조적 추가 사항이 하나 더 있다. ioss_ScanDesc->xs_want_itup = true로 설정하여 인덱스 AM이 힙을 가져오는 대신 인덱스 튜플을 반환하도록 지시한다. 튜플을 반환하기 전에 IndexOnlyNext는 가시성 맵(visibility map) 을 참조해 힙 페치가 여전히 필요한지 판단한다.

// IndexOnlyNext (발췌) — src/backend/executor/nodeIndexonlyscan.c
while ((tid = index_getnext_tid(scandesc, direction)) != NULL)
{
    bool tuple_from_heap = false;
    CHECK_FOR_INTERRUPTS();

    if (!VM_ALL_VISIBLE(scandesc->heapRelation,
                        ItemPointerGetBlockNumber(tid),
                        &node->ioss_VMBuffer))
    {
        /* 가시성 확인을 위해 힙을 방문해야 함 */
        InstrCountTuples2(node, 1);
        if (!index_fetch_heap(scandesc, node->ioss_TableSlot))
            continue;   /* 가시 튜플 없음 */
        ExecClearTuple(node->ioss_TableSlot);
        tuple_from_heap = true;
    }

    /* 인덱스 튜플로 슬롯 채우기 (xs_hitup 우선) */
    if (scandesc->xs_hitup)
        ExecForceStoreHeapTuple(scandesc->xs_hitup, slot, false);
    else if (scandesc->xs_itup)
        StoreIndexTuple(node, slot, scandesc->xs_itup, scandesc->xs_itupdesc);
    else
        elog(ERROR, "no data returned for index-only scan");
    ...
}

TID가 가리키는 힙 페이지에 VM_ALL_VISIBLE이 설정되어 있으면 힙 페치를 완전히 건너뛴다. 설정되어 있지 않으면 index_fetch_heap을 호출해 힙 튜플을 가져오지만, 그 목적은 가시성 확인뿐이다. 컬럼 데이터는 여전히 인덱스 튜플에서 가져온다. ioss_VMBuffer 핀은 호출 간에 유지되어 같은 페이지에 대한 반복적인 가시성 맵 조회 비용을 줄인다.

StoreIndexTuple은 인덱스 튜플을 스캔 슬롯의 속성 배열로 언팩한다. name 타입 컬럼이 있는 인덱스라면 NAMEDATALEN까지 패딩해야 하며, ioss_NameCStringAttNums가 해당 컬럼 번호를 추적한다.

BitmapHeapScan — 두 단계 비트맵 구동 힙 스캔

BitmapHeapScan은 MultiExecProcNode로 협력하는 두 플랜 노드로 실행된다. 외부 서브플랜인 BitmapIndexScan(또는 BitmapAnd/BitmapOr 트리)은 표준 튜플 인터페이스를 거치지 않고 TIDBitmap을 반환한다. BitmapHeapScan은 첫 번째 BitmapHeapNext 호출 시 BitmapTableScanSetup으로 미루어 MultiExecProcNode를 정확히 한 번 호출해 비트맵을 구성한 뒤, 힙 AM에 넘겨 페이지 순서 이터레이션을 맡긴다.

// BitmapTableScanSetup (발췌) — src/backend/executor/nodeBitmapHeapscan.c
static void
BitmapTableScanSetup(BitmapHeapScanState *node)
{
    /* 직렬 경로: 서브플랜으로 TIDBitmap 구성 */
    node->tbm = (TIDBitmap *) MultiExecProcNode(outerPlanState(node));
    if (!node->tbm || !IsA(node->tbm, TIDBitmap))
        elog(ERROR, "unrecognized result from subplan");

    tbmiterator = tbm_begin_iterate(node->tbm, dsa, InvalidDsaPointer);

    /* 비트맵 구동 접근을 위한 힙 스캔 디스크립터 열기 */
    if (!node->ss.ss_currentScanDesc)
        node->ss.ss_currentScanDesc =
            table_beginscan_bm(node->ss.ss_currentRelation,
                               node->ss.ps.state->es_snapshot, 0, NULL);

    node->ss.ss_currentScanDesc->st.rs_tbmiterator = tbmiterator;
    node->initialized = true;
}

BitmapHeapNext는 table_scan_bitmap_next_tuple을 루프로 호출한다. 힙 AM은 비트맵을 블록 순서로 순회한다. 비트맵에 손실 있는 페이지 항목(TIDBitmap이 work_mem을 초과하여 페이지 수준 단위로 저하된 경우)이 있으면 node->recheck가 true가 되고, BitmapHeapNext는 그 페이지의 모든 튜플에 bitmapqualorig를 재평가한다.

// BitmapHeapNext (발췌) — src/backend/executor/nodeBitmapHeapscan.c
while (table_scan_bitmap_next_tuple(node->ss.ss_currentScanDesc,
                                    slot, &node->recheck, ...))
{
    CHECK_FOR_INTERRUPTS();
    if (node->recheck)
    {
        econtext->ecxt_scantuple = slot;
        if (!ExecQualAndReset(node->bitmapqualorig, econtext))
        {
            InstrCountFiltered2(node, 1);
            ExecClearTuple(slot);
            continue;
        }
    }
    return slot;
}
return ExecClearTuple(slot);

병렬 비트맵 스캔의 경우, 리더가 tbm_prepare_shared_iterate로 이터레이터 DSA 포인터를 pstate->tbmiterator에 게시하고, 워커들은 그 포인터로 tbm_begin_iterate를 호출해 붙는다. BitmapShouldInitializeSharedState / BitmapDoneInitializingSharedState 쌍이 스핀락 + 조건 변수로 리더만 비트맵을 구성하게 보장한다.

두 단계 구조가 중요한 이유는 BitmapHeapScan과 IndexScan 사이의 가장 중요한 아키텍처 차이가 여기 있기 때문이다. IndexScan에서는 인덱스 탐색과 힙 페치가 튜플 단위로 교차한다. TID 하나를 가져오고, 그 힙 튜플을 가져오고, 반환하고, 반복한다. 각 힙 페치가 임의의 블록에 떨어질 수 있으므로, 선택도가 낮은 조건에서는 힙 접근 패턴이 사실상 무작위다. BitmapHeapScan은 인덱스 패스와 힙 패스 사이에 구체화 장벽인 TIDBitmap을 삽입함으로써 이 교차를 끊는다. 1단계에서 BitmapIndexScan 서브플랜을 MultiExecProcNode 단일 호출로 완전히 소진하여 일치하는 모든 TID를 비트맵에 누적한다. 비트맵이 완성된 다음에야 2단계가 시작되어 힙을 블록 번호 오름차순으로 순회한다. 이것이 I/O 병합의 이점이다. IndexScan이 무작위 순서로 방문했을 힙 블록 집합을 이제 순차적으로 방문하고, 같은 블록에 일치 튜플이 여럿 있어도 블록은 한 번만 읽는다.

flowchart TD
  subgraph EXECSCAN["ExecScan / ExecScanExtended — 공유 외부 루프"]
    ESLOOP["accessMtd → qual → project → EPQ"]
  end

  subgraph FAMILY["스캔 노드 계열 — 각각 하나의 accessMtd"]
    SS["SeqNext<br/>table_scan_getnextslot"]
    IS["IndexNext<br/>index_getnext_slot + 힙 페치"]
    IOS["IndexOnlyNext<br/>index_getnext_tid + VM_ALL_VISIBLE 게이트"]
    TS["TidNext<br/>table_tuple_fetch_row_version"]
    TRS["TidRangeNext<br/>table_scan_getnextslot_tidrange"]
    BHN["BitmapHeapNext<br/>table_scan_bitmap_next_tuple"]
  end

  ESLOOP --> SS
  ESLOOP --> IS
  ESLOOP --> IOS
  ESLOOP --> TS
  ESLOOP --> TRS
  ESLOOP --> BHN

  subgraph PHASE1["비트맵 1단계 — 구성 (지연, 한 번만 실행)"]
    INIT{"node->initialized?"}
    SETUP["BitmapTableScanSetup"]
    MEPN["MultiExecProcNode<br/>(BitmapIndexScan / BitmapAnd / BitmapOr)"]
    TBM["TIDBitmap<br/>정확: 1비트/TID — 손실: 1비트/페이지"]
    SHARED["pstate? → tbm_prepare_shared_iterate<br/>+ BitmapDoneInitializingSharedState"]
    ITER["tbm_begin_iterate<br/>table_beginscan_bm → rs_tbmiterator"]
  end

  subgraph PHASE2["비트맵 2단계 — 힙 페치 (튜플 단위, 블록 순서)"]
    NEXT["table_scan_bitmap_next_tuple"]
    RECHK{"node->recheck?<br/>(손실 페이지)"}
    QUAL["ExecQualAndReset<br/>bitmapqualorig"]
    EMIT["return slot"]
    DROP["InstrCountFiltered2<br/>ExecClearTuple → 루프"]
  end

  BHN --> INIT
  INIT -- no --> SETUP
  INIT -- yes --> NEXT
  SETUP --> MEPN --> TBM --> SHARED --> ITER --> NEXT
  NEXT --> RECHK
  RECHK -- no --> EMIT
  RECHK -- yes --> QUAL
  QUAL -- pass --> EMIT
  QUAL -- fail --> DROP --> NEXT

그림 2 — 모든 리프 스캔 노드는 단일 accessMtd를 공유 ExecScan/ExecScanExtended 루프에 연결한다. BitmapHeapNext가 특별한 점은 그 accessMtd 자체가 두 단계로 구성된다는 것이다. 지연 일회성 구성(BitmapTableScanSetup → MultiExecProcNode → TIDBitmap) 다음에 블록 순서 힙 순회(table_scan_bitmap_next_tuple)가 오고, 손실 있는 페이지에서는 bitmapqualorig를 튜플 단위로 재검사한다.

node->initialized 가드가 중요한 이유는 BitmapTableScanSetup이 ExecInitBitmapHeapScan 시점이 아니라 첫 BitmapHeapNext 호출 시 지연 실행되기 때문이다. 이는 다른 모든 노드의 지연 스캔 디스크립터 패턴과 같은 맥락이다. 중첩 루프가 다시 구동하는 내부 비트맵 힙 스캔은 실제로 풀될 때만 비트맵 구성 비용을 치른다. 재검사 분기(node->recheck)는 table_scan_bitmap_next_tuple이 페이지 단위로 설정한다. 힙 AM은 현재 페이지가 손실 있는 비트맵 항목에서 왔을 때 이 플래그를 올린다. 손실 있는 항목은 “이 페이지의 어떤 튜플이 일치했다”만 기록할 뿐 어느 것인지 알 수 없기 때문이다. 정확 항목은 TID 수준 정밀도를 가지므로 재검사가 불필요하다. 재검사 비용은 work_mem이 소진되어 손실 모드로 떨어진 페이지에만 발생한다. 스레드를 통과하는 두 계측 카운터 node->stats.lossy_pages와 node->stats.exact_pages가 바로 EXPLAIN (ANALYZE)에서 “Heap Blocks: exact=N lossy=M”으로 나타나는 값이다. SQL 수준에서 정확/손실 분할을 직접 확인할 수 있다.

TidScan — ctid 점 조회

TidScan은 WHERE ctid = '(0,1)' 또는 WHERE ctid = ANY(배열_표현식), WHERE CURRENT OF 커서 형태의 쿼리를 처리한다. TidExprListCreate는 ExecInitTidScan 시점에 TidScan.tidquals 표현식 목록을 파싱하여, 일반 표현식은 ExprState 객체로 컴파일하고 CURRENT OF 커서 참조를 기록한다. TidListEval은 런타임에 그 표현식들을 평가해 tss_TidList에 ItemPointer 목록을 저장한다.

// TidNext (발췌) — src/backend/executor/nodeTidscan.c
static TupleTableSlot *
TidNext(TidScanState *node)
{
    /* 첫 호출 시 tid 표현식 평가 */
    if (node->tss_TidList == NULL)
        TidListEval(node);

    while (node->tss_TidPtr < node->tss_NumTids)
    {
        ItemPointerData tid = node->tss_TidList[node->tss_TidPtr++];
        /* ... CURRENT OF 커서 해석 ... */
        if (!table_tuple_fetch_row_version(heapRelation, &tid,
                                           estate->es_snapshot, slot))
            continue;
        return slot;
    }
    return ExecClearTuple(slot);
}

TidListEval은 TID 목록을 중복 제거하고 정렬하여 table_tuple_fetch_row_version 호출이 물리적 순서로 진행되도록 한다. 목록이 클 때 무작위 I/O를 줄이는 효과가 있다. CURRENT OF 해석은 GetCurrentCID / table_tuple_tid_valid를 호출해 커서의 현재 위치를 확인한다.

TidRangeScan — 연속 ctid 범위 스캔

TidRangeScan은 WHERE ctid >= '(10,0)' AND ctid < '(20,0)' 형태의 쿼리를 위해 PG14에서 추가된 노드다. 플래너는 ctid에 대한 범위 비교를 인식하고 TidRangeScan 플랜 노드를 생성한다. MakeTidOpExpr (ExecInitTidRangeScan에서 호출)은 비교 연산자와 방향을 파싱한다.

// MakeTidOpExpr (발췌) — src/backend/executor/nodeTidrangescan.c
switch (expr->opno)
{
    case TIDLessEqOperator:
        tidopexpr->exprtype = TIDEXPR_UPPER_BOUND;
        tidopexpr->inclusive = true;   break;
    case TIDLessOperator:
        tidopexpr->exprtype = TIDEXPR_UPPER_BOUND;
        tidopexpr->inclusive = false;  break;
    /* ... TIDGreater*, 피연산자 순서가 반전된 경우 invert ... */
}

TidRangeNext는 (첫 호출 시 지연) table_beginscan_tidrange를 호출한 뒤 table_scan_getnextslot_tidrange로 범위 내 튜플을 가져온다. 힙 AM은 TID 범위를 이용해 읽을 블록 범위를 제한하므로, ctid 조건으로 걸러 내는 순차 스캔보다 효율적이다.

소스 코드 가이드

execScan.c — 공유 외부 루프

심벌	역할
ExecScan	얇은 래퍼. 노드에서 epqstate, qual, projInfo를 읽어 ExecScanExtended에 위임한다.
ExecScanExtended	공유 외부 루프. accessMtd 호출, qual 적용, 프로젝션, EPQ 처리. execScan.h에 인라인으로 정의.
ExecScanReScan	스캔 튜플 슬롯 초기화. ForeignScan·CustomScan의 EPQ relsubs_done 재설정 처리.
ExecAssignScanProjectionInfo	대상 목록이 스캔 튜플 디스크립터와 정확히 일치하면 ps_ProjInfo를 NULL로 설정(프로젝션 생략).

nodeSeqscan.c — 순차 스캔

심벌	역할
SeqNext	접근 함수. 지연 table_beginscan, 이후 table_scan_getnextslot.
SeqRecheck	항상 true. 인덱스 키가 없어 재검사 불필요.
ExecSeqScan	빠른 경로: qual 없음, 프로젝션 없음, EPQ 없음.
ExecSeqScanWithQual	빠른 경로: qual 있음, 프로젝션 없음.
ExecSeqScanWithProject	빠른 경로: 프로젝션 있음, qual 없음.
ExecSeqScanWithQualProject	전체 경로: qual + 프로젝션.
ExecSeqScanEPQ	EPQ 활성 경로(ExecScanExtended 아닌 ExecScan 사용).
ExecInitSeqScan	SeqScanState 할당, 릴레이션 열기, 슬롯 초기화, 특화 ExecProcNode 선택.
ExecEndSeqScan	디스크립터가 열려 있으면 table_endscan 호출.
ExecReScanSeqScan	table_rescan 후 ExecScanReScan.
ExecSeqScanEstimate	table_parallelscan_estimate → shm_toc_estimate_chunk.
ExecSeqScanInitializeDSM	table_parallelscan_initialize; table_beginscan_parallel.
ExecSeqScanInitializeWorker	shm_toc_lookup → table_beginscan_parallel.

nodeIndexscan.c — 인덱스 구동 힙 페치

심벌	역할
IndexNext	접근 함수. 지연 index_beginscan; xs_recheck 재검사를 포함한 index_getnext_slot 루프.
IndexNextWithReorder	변형. 근사 ORDER BY를 위해 iss_ReorderQueue(페어링 힙)에 튜플을 넣어 재정렬.
ExecIndexScan	IndexNext/IndexRecheck를 ExecScan에 전달하는 ExecProcNode 래퍼.
ExecInitIndexScan	IndexScanState 할당, 힙·인덱스 릴레이션 열기, ExecIndexBuildScanKeys 호출.
ExecIndexBuildScanKeys	플래너의 indexqual 목록을 ScanKey[]로 변환. 상수 키와 런타임 키 분리.
ExecReScanIndexScan	파라미터 변경 시 런타임 키 재평가; index_rescan 호출.
ExecEndIndexScan	index_endscan; 필요시 인덱스·힙 릴레이션 닫기.

nodeIndexonlyscan.c — 인덱스 전용 (all-visible 페이지는 힙 불필요)

심벌	역할
IndexOnlyNext	index_getnext_tid → VM_ALL_VISIBLE 확인 → 필요시 index_fetch_heap → StoreIndexTuple.
StoreIndexTuple	IndexTuple을 TupleTableSlot 속성 배열로 언팩. name 타입 컬럼 패딩 처리.
ExecIndexOnlyScan	xs_recheck 시 recheckqual 확인하는 ExecProcNode 래퍼.
ExecInitIndexOnlyScan	IndexOnlyScanState 할당; xs_want_itup = true 설정; ioss_VMBuffer = InvalidBuffer 초기화.
ExecEndIndexOnlyScan	index_endscan; 핀이 있으면 ioss_VMBuffer 해제.

nodeBitmapHeapscan.c — 두 단계 비트맵 스캔

심벌	역할
BitmapTableScanSetup	MultiExecProcNode로 TIDBitmap 구성; table_beginscan_bm 열기; 병렬 공유 상태 초기화.
BitmapHeapNext	table_scan_bitmap_next_tuple 루프; 손실 있는 페이지에서 bitmapqualorig 재검사.
ExecBitmapHeapScan	BitmapHeapNext/BitmapHeapRecheck를 ExecScan에 전달하는 ExecProcNode 래퍼.
ExecInitBitmapHeapScan	BitmapHeapScanState 할당; 외부(비트맵 인덱스) 서브플랜 초기화.
BitmapDoneInitializingSharedState	리더가 비트맵 구성 후 대기 중인 워커를 깨우는 스핀락 + ConditionVariableBroadcast.

nodeTidscan.c / nodeTidrangescan.c — ctid 대상 스캔

심벌	역할
TidExprListCreate	TidScan.tidquals 파싱; ExprState[]로 컴파일; CURRENT OF 플래그 설정.
TidListEval	TID 표현식 평가; 중복 제거 + 정렬; CURRENT OF 커서 해석.
TidNext	tss_TidList 순회; TID당 table_tuple_fetch_row_version 호출.
ExecInitTidScan	TidScanState 할당; TidExprListCreate 호출.
MakeTidOpExpr	ctid 범위 연산자를 TidOpExpr(상한/하한, 포함 여부)로 파싱.
TidRangeNext	지연 table_beginscan_tidrange; table_scan_getnextslot_tidrange 루프.
ExecInitTidRangeScan	TidRangeScanState 할당; 플랜 조건에서 TidOpExpr 목록 구성.

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

심벌	파일	줄
ExecScan	src/backend/executor/execScan.c	47
ExecScanReScan	src/backend/executor/execScan.c	108
ExecAssignScanProjectionInfo	src/backend/executor/execScan.c	81
SeqNext	src/backend/executor/nodeSeqscan.c	51
ExecSeqScan	src/backend/executor/nodeSeqscan.c	110
ExecInitSeqScan	src/backend/executor/nodeSeqscan.c	207
ExecEndSeqScan	src/backend/executor/nodeSeqscan.c	289
ExecReScanSeqScan	src/backend/executor/nodeSeqscan.c	317
ExecSeqScanEstimate	src/backend/executor/nodeSeqscan.c	343
ExecSeqScanInitializeDSM	src/backend/executor/nodeSeqscan.c	361
ExecSeqScanInitializeWorker	src/backend/executor/nodeSeqscan.c	399
IndexNext	src/backend/executor/nodeIndexscan.c	80
IndexNextWithReorder	src/backend/executor/nodeIndexscan.c	169
ExecInitIndexScan	src/backend/executor/nodeIndexscan.c	909
ExecIndexBuildScanKeys	src/backend/executor/nodeIndexscan.c	1158
ExecIndexScan	src/backend/executor/nodeIndexscan.c	521
IndexOnlyNext	src/backend/executor/nodeIndexonlyscan.c	61
ExecInitIndexOnlyScan	src/backend/executor/nodeIndexonlyscan.c	528
BitmapTableScanSetup	src/backend/executor/nodeBitmapHeapscan.c	63
BitmapHeapNext	src/backend/executor/nodeBitmapHeapscan.c	126
BitmapDoneInitializingSharedState	src/backend/executor/nodeBitmapHeapscan.c	181
BitmapHeapRecheck	src/backend/executor/nodeBitmapHeapscan.c	193
ExecBitmapHeapScan	src/backend/executor/nodeBitmapHeapscan.c	212
ExecInitBitmapHeapScan	src/backend/executor/nodeBitmapHeapscan.c	333
BitmapShouldInitializeSharedState	src/backend/executor/nodeBitmapHeapscan.c	420
StoreIndexTuple	src/backend/executor/nodeIndexonlyscan.c	269
ExecIndexOnlyScan	src/backend/executor/nodeIndexonlyscan.c	337
ExecEndIndexOnlyScan	src/backend/executor/nodeIndexonlyscan.c	399
table_scan_bitmap_next_tuple	src/include/access/tableam.h	1932
TidExprListCreate	src/backend/executor/nodeTidscan.c	70
TidListEval	src/backend/executor/nodeTidscan.c	134
TidNext	src/backend/executor/nodeTidscan.c	312
ExecInitTidScan	src/backend/executor/nodeTidscan.c	499
MakeTidOpExpr	src/backend/executor/nodeTidrangescan.c	56
TidRangeNext	src/backend/executor/nodeTidrangescan.c	222
ExecInitTidRangeScan	src/backend/executor/nodeTidrangescan.c	359
ScanState	src/include/nodes/execnodes.h	1609
SeqScanState	src/include/nodes/execnodes.h	1621
IndexScanState	src/include/nodes/execnodes.h	1698
IndexOnlyScanState	src/include/nodes/execnodes.h	1750

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

REL_18_STABLE, 커밋 273fe94 기준으로 검증.

확인됨:

• ExecSeqScan의 다섯 변형 특화(ExecSeqScan, ExecSeqScanWithQual, ExecSeqScanWithProject, ExecSeqScanWithQualProject, ExecSeqScanEPQ)가 nodeSeqscan.c에 설명대로 존재한다. 이 최적화는 PG16/PG17 시대에 도입되었고 REL_18에 포함되어 있다.
• ExecScanExtended는 src/include/executor/execScan.h에 static inline 함수로 선언되어 있다(execScan.c가 아님). ExecScan 59번 줄의 호출로 확인된다.
• IndexOnlyNext의 VM_ALL_VISIBLE 매크로 사용(161번 줄)과 IndexOnlyScanState의 ioss_VMBuffer 필드가 존재한다.
• BitmapTableScanSetup(이전의 튜플 단위 설정 방식에서 리네임됨)과 nodeBitmapHeapscan.c 115번 줄의 rs_tbmiterator 필드 할당이 REL_18에 확인된다.
• TidRangeScan 노드 유형과 table_beginscan_tidrange / table_scan_getnextslot_tidrange AM 진입점이 REL_18에 존재한다.

미해결 / 향후 드리프트 위험:

• ExecScanExtended는 헤더 파일의 인라인이다. 코드 발췌 위에서는 그 내부(qual 평가 + 프로젝션 루프)를 직접 보여 주지 않았지만, 다섯 SeqScan 변형 설명에서 참조한다. 위치 힌트 표는 .c 파일만 다루므로 ExecScanExtended의 줄 번호(execScan.h 138~165번 줄 부근)는 포함하지 않는다.
• IndexOnlyScanState의 ioss_NameCStringAttNums / ioss_NameCStringCount 필드는 REL_18 추가 사항(인덱스 전용 스캔용 name 타입 컬럼 패딩)이다. execnodes.h에 존재하지만 StoreIndexTuple의 전체 로직은 끝까지 추적하지 않았다.
• 병렬 비트맵 스캔 공유 상태 생명주기(BitmapShouldInitializeSharedState, pstate->tbmiterator DSA 포인터)는 존재가 확인되었으나, dsa_area 할당을 통한 전체 병렬 경로는 끝까지 추적하지 않았다.

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

Oracle과 DB2: 실행과 접근 경로의 분리

Oracle의 실행 엔진은 PostgreSQL보다 접근 경로와 필터를 더 적극적으로 분리한다. Oracle의 많은 플랜에서 TABLE ACCESS FULL 노드 하나가 스토리지 레이어 읽기와 필터 조건을 모두 담는다. 그 위에 별도의 Filter 노드가 없다. 이는 PostgreSQL이 ExecScan으로 qual을 밀어 넣는 방식과 같지만, Oracle은 여기서 한 발 더 나아가 버퍼 캐시 수준에서 스토리지 인덱스(SI) 필터링을 수행한다. 블록 수준 조건이 거짓이면 그 블록을 아예 로드하지 않는다. PostgreSQL에는 이에 상당하는 블록 수준 필터가 없다. 가시성 맵은 all-visible 여부만 다루고, 조건 필터링은 다루지 않는다.

MySQL/InnoDB: 클러스터드 인덱스가 힙 페치 비용 모델을 바꾸는 방식

InnoDB는 데이터를 클러스터드 인덱스(기본 키 B-트리가 전체 튜플을 저장)에 저장한다. 따라서 보조 인덱스 스캔은 항상 두 단계다. 보조 인덱스 조회 → 클러스터드 인덱스 페치(PostgreSQL의 IndexScan 힙 페치에 해당). 그러나 클러스터드 인덱스가 기본 키 순서로 정렬되어 있어, 기본 키 범위 순차 스캔은 항상 완전 순차 읽기다. PostgreSQL은 클러스터드 인덱스가 없다. CLUSTER TABLE ... USING index는 일회성 물리 정렬이지, 유지 관리되는 구조가 아니다. 이 점이 커버링 인덱스 워크로드에서 PostgreSQL의 가시성 맵 기반 인덱스 전용 스캔을 특히 중요하게 만드는 이유다.

엔진별 커버링 인덱스와 인덱스 전용 스캔

PostgreSQL의 IndexOnlyScan이 가시성 맵을 게이트로 쓰는 것은 설계 특유의 트레이드오프다. Oracle은 인덱스 페이지 안에 SCN 기반 행 디렉터리를 쓰고, SQL Server는 행 버전 스토어에 행 버전을 인덱스 페이지에 저장한다. PostgreSQL은 가시성 상태를 페이지 단위로 가시성 맵에 저장한다. 장점은 VACUUM이 가시성 맵을 관리하는 비용이 이후 그 페이지들에 대한 모든 인덱스 전용 스캔에 분산된다는 점이다. 단점은 방금 삽입되거나 최근에 갱신된 페이지는 VACUUM이 실행되어 all-visible 비트를 설정하기 전까지 힙 페치가 필요하다는 점이다.

연구 프론티어: 지연 구체화와 컬럼 단위 프로젝션

교과서의 “프로젝션 푸시다운” 원칙은 컬럼 스토어에서 지연 구체화 (late materialization) 로 확장된다(Abadi et al., VLDB 2007). 스캔 레이어에서 튜플의 모든 컬럼을 가져오는 대신, 컬럼 식별자만 위로 올리고 필터 조건이 행 집합을 줄인 뒤에야 전체 튜플을 재구성한다는 개념이다. PostgreSQL의 힙 AM은 행 스토어이므로 ExecScan은 각 단계에서 완전한 TupleTableSlot을 반환해야 한다. TupleTableSlot의 가상 튜플 메커니즘 (tts_values[] + tts_isnull[])은 컬럼 구체화를 힙 페치에서 부분적으로 분리하지만, 완전한 지연 구체화는 컬럼 AM이 필요하다. table_am API (postgres-table-am.md)가 커스텀 스캔 인터페이스로 자체 스캔 노드 변형을 제공하려는 컬럼 엔진의 확장 지점이다.

비트맵 스캔과 I/O 병합

두 단계 비트맵 스캔은 Database Internals(Petrov, 7장)가 설명하는 I/O 병합(I/O coalescing) 과 정확히 일치한다. 무작위 조회 집합을 정렬된 순차 패스로 변환하는 기법이다. PostgreSQL의 TIDBitmap은 정확 모드(TID당 1비트, 저렴한 재검사)와 손실 모드(페이지당 1비트, 필수 재검사)를 구현하며, work_mem이 소진되면 자동으로 저하된다. Blink-tree 인덱스나 ARIES-IM 같은 연구 시스템은 이를 동시 쿼리 간에 공유되는 버퍼 관리 비트맵으로 확장했다. PostgreSQL의 비트맵은 쿼리별이며 연산자 메모리에 산다.

출처

인-트리 소스 파일 (커밋 273fe94, REL_18_STABLE):

• src/backend/executor/execScan.c — 공유 외부 스캔 루프
• src/backend/executor/nodeSeqscan.c — 순차 스캔
• src/backend/executor/nodeIndexscan.c — 인덱스 스캔 + 스캔 키 구성
• src/backend/executor/nodeIndexonlyscan.c — 인덱스 전용 스캔
• src/backend/executor/nodeBitmapHeapscan.c — 비트맵 힙 스캔
• src/backend/executor/nodeBitmapIndexscan.c — 비트맵 인덱스 스캔(서브플랜)
• src/backend/executor/nodeTidscan.c — ctid 점 스캔
• src/backend/executor/nodeTidrangescan.c — ctid 범위 스캔
• src/include/nodes/execnodes.h — ScanState, SeqScanState, IndexScanState, IndexOnlyScanState, BitmapHeapScanState, TidScanState, TidRangeScanState
• src/include/executor/execScan.h — ExecScanExtended 인라인, ExecScanAccessMtd, ExecScanRecheckMtd

상호 참조 (지식 베이스):

• postgres-executor.md — Volcano 이터레이터 모델, TupleTableSlot, ExecProcNode 디스패치
• postgres-table-am.md — table_beginscan, table_scan_getnextslot, table_tuple_fetch_row_version, table_beginscan_tidrange
• postgres-nbtree.md — index_beginscan, index_getnext_slot, 스캔 키 의미론
• postgres-heap-am.md — table_beginscan_bm, table_scan_bitmap_next_tuple
• postgres-mvcc-snapshots.md — 가시성 검사, 스냅샷 의미론
• postgres-buffer-manager.md — 버퍼 핀과 가시성 맵 버퍼 관리
• postgres-path-generation.md — 이 플랜 노드들을 생성하는 플래너 경로 유형

교과서 참고:

• Database System Concepts, Silberschatz, 7판, §12.3(파일 스캔), §15.3(인덱스 스캔), §15.3.3(비트맵 스캔)
• Database Internals, Petrov, 7장(I/O 병합, 읽기 증폭)