콘텐츠로 이동
hgryoo · Docs

(KO) PostgreSQL GIN — 일반화 역색인, 포스팅 트리, Fast-Update 목록

목차

학술적 배경

섹션 제목: “학술적 배경”

교과서적 의미의 보조 인덱스는 하나의 색인 값을 그 값을 가진 행 집합으로 매핑한다. int 컬럼이라면 B-트리 리프 항목 하나가 키와 소수의 행 포인터를 담으면 충분하고, 접근 방법(AM, Access Method)은 컬럼 값을 불투명하게 취급해 단일 비교 연산자로 정렬한다. 그런데 색인 대상 컬럼이 복합 구조일 때 이 모델은 무너진다. 배열 {4, 7, 12}, 수백 개 어휘소를 담은 tsvector, 수십 개 경로를 가진 jsonb 문서가 그런 예다. 이런 컬럼에서 가속하고 싶은 쿼리는 “배열이 {4,7,12}와 같은 행”이 아니라 “배열이 7을 포함하는 행”, “문서가 전문 쿼리 fox & quick에 매칭되는 행”이다. 값 전체가 아니라 값 안의 원소가 쿼리가 탐색하는 단위다.

이 형태에 맞는 자료구조가 **역색인(inverted index)**이다. 정보 검색의 핵심 도구다. Database System Concepts (Silberschatz 7판, 21장 “정보 검색”)는 이렇게 정의한다: “역색인은 각 단어마다 그 단어가 등장하는 모든 문서 식별자 목록을 저장한다.” 각 고유 항(term) — 단어, 어휘소, 배열 원소, 통칭 키(key) — 은 **포스팅 목록(posting list)**으로 매핑된다. 포스팅 목록은 해당 키를 담은 문서 식별자(여기서는 힙 튜플 ID)의 정렬된 집합이다. 결합 쿼리 fox & quick은 fox와 quick의 포스팅 목록을 교집합해 답한다. 선언적 쿼리는 두 목록의 합집합이다. 색인이 자연스러운 문서-to-항 관계를 항-to-문서로 역전하기 때문에 “역색인”이라 부른다. 검색 엔진이 웹 코퍼스 위에 구축하는 바로 그 구조이며, 관계형 엔진이 배열·문서·텍스트 컬럼을 색인하기 위해 차용한다.

실제 코퍼스의 두 가지 특성이 역색인을 해시 테이블의 목록보다 훨씬 복잡한 엔지니어링 문제로 만든다.

  1. 편중(Skew). 항 빈도는 Zipf 분포를 따른다. 소수의 키(the, and)는 거의 모든 문서에 등장하고, 대부분의 키는 드물다. 포스팅 목록은 TID 하나짜리부터 수백만 짜리까지 범위가 넓다. “키 옆에 목록을 인라인으로 저장”하는 단일 고정 컨테이너는 양쪽 모두 잘못 맞는다. 드문 키에는 공간 낭비, 흔한 키에는 오버플로우다. 좋은 역색인은 목록이 짧을 때 소형이고, 길어질 때 페이지 구조로 자연스럽게 전환하는 적응형 컨테이너가 필요하다.

  2. 삽입 시 쓰기 증폭. 키가 k개인 문서 하나를 삽입하면 k개의 포스팅 목록, 즉 키 공간 전반에 산재한 k개의 위치를 손봐야 한다. 각 작업은 B-트리 하강과 페이지 재작성이다. 문서 스트림을 이렇게 소매(retail) 방식으로 색인하면 같은 핫 키가 반복해서 재작성되어 극도로 느리다. 고전적인 IR 해법은 일괄 처리다. 포스팅을 메모리(또는 보조 구조)에 쌓고 키 순서로 정렬한 뒤 메인 인덱스에 일괄 병합하면, 핫 키의 목록이 문서마다 한 번씩이 아니라 배치당 한 번만 재작성된다.

세 번째 특성은 일반성이다. 관계형 엔진은 “이건 텍스트”를 하드코딩할 수 없다. 같은 기계가 integer[], text[], tsvector, jsonb, hstore, 트라이그램 인덱스, 사용자 정의 타입을 모두 처리해야 한다. 따라서 인덱스는 데이터 타입별로 제공되는 소수의 전략 함수로 매개변수화되어야 한다. 저장 값에서 키를 추출하는 함수, 쿼리에서 키를 추출하는 함수(검색 모드 포함: must-match-all, match-any, everything), 그리고 후보 행에 쿼리 키가 몇 개 존재했는지를 받아 행이 실제로 연산자를 만족하는지 판정하는 consistent 함수가 그것이다. “인덱스는 자신이 가속하는 연산자를 모른다”는 GiST와 같은 철학을, 역색인에 맞게 표현한 것이다. GIN README는 이렇게 말한다: “Generalized는 인덱스가 어떤 연산을 가속하는지 알지 못한다는 뜻이다. 대신 특정 데이터 타입에 정의된 커스텀 전략으로 동작한다.”

DBMS 공통 설계 패턴

섹션 제목: “DBMS 공통 설계 패턴”

검색 엔진(Lucene/Elasticsearch, Solr)과 관계형 엔진에 추가된 전문 검색 기능(Oracle Text, SQL Server Full-Text, MySQL FULLTEXT)은 모두 역색인 골격 위에 구축되며, 공통적인 설계 결정으로 수렴한다.

  • 사전 + 포스팅 분리. 항 사전(term dictionary) — 주로 B-트리, 정렬 배열, Lucene의 FST — 이 각 키를 포스팅 목록 위치로 매핑한다. 포스팅은 별도로 보관한다. 키와 포스팅의 크기 분포가 너무 다르기 때문이다. Lucene은 사전을 .tim/.tip 파일에, 포스팅을 .doc 파일에 저장한다. 관계형 엔진은 보통 리프가 포스팅 저장소를 가리키는 B-트리로 사전을 구현한다.

  • 포스팅의 델타 + 가변 바이트 압축. 포스팅 목록은 단조 증가 문서 ID의 정렬된 목록이다. 따라서 ID 자체가 아니라 연속 ID 간 *차이(gap)*를 저장하고, 작은 gap을 가변 길이 정수 방식(varbyte, Simple-9, PForDelta, 밀집 목록용 Roaring bitmap)으로 인코딩한다. 정렬 gap + varbyte는 표준 기준선이며 밀집 포스팅 목록을 수 배 압축한다.

  • 세그먼트 / 배치 구조와 백그라운드 병합. Lucene이 원형이다. 쓰기는 작은 인메모리 세그먼트로 들어가고, 불변 온디스크 세그먼트로 플러시된다. 백그라운드 병합 정책이 작은 세그먼트를 큰 것으로 주기적으로 합친다. 삭제는 병합 시점에 적용되는 툼스톤이며, 제자리 삭제가 아니다. 이렇게 하면 수집이 추가-전용(append-mostly)이 되고 비싼 정렬 병합이 쓰기 경로 밖으로 밀려난다. “포스팅 목록을 제자리 수정하지 않고 일괄 재구성”하는 본능은 보편적이다.

  • 사전 항의 인플레이스 삭제 없음. 어휘는 천천히 변한다. 코퍼스가 어느 임계점을 넘으면 고유 단어 집합이 거의 안정된다. 엔진은 이를 활용해 포스팅 목록이 비더라도 사전에서 항을 제거하지 않는다. 빈 항 하나의 비용은 사전 삭제에 필요한 동시성 제어 기계 비용보다 훨씬 싸다.

  • 쿼리 = 다중 스트림 병합 + 판정 함수. 여러 항에 걸친 불리언 쿼리는 항당 하나의 포스팅 커서를 열고, 문서 ID 순서로 진행하며, 각 후보 문서에서 불리언 표현식(AND/OR/NOT, 경우에 따라 근접성·점수 포함)을 평가한다. “X 이상인 문서로 건너뛰기” 기본 연산으로 커서를 전진시켜, 드문 항과 흔한 항이 교집합될 때 흔한 항의 목록 대부분을 건너뛴다. 포스팅 내부의 스킵 목록이 이를 저렴하게 만든다.

flowchart TD
  doc["색인 항목<br/>array / tsvector / jsonb"] -->|키 추출| keys["키: k1, k2, k3 ..."]
  keys --> dict["항 사전<br/>(키의 B-트리)"]
  dict -->|키별| pl["포스팅 목록<br/>정렬됨, delta+varbyte 압축<br/>문서 ID / 힙 TID"]
  q["쿼리 연산자<br/>예: arr @> '{7}'"] -->|쿼리 키 추출 + searchMode| qkeys["쿼리 키 + 일치 조건"]
  qkeys --> cursors["키별 포스팅 커서"]
  cursors -->|문서 ID 순 병합| cand["후보 문서"]
  cand -->|consistent / 불리언 판정 함수| match{"일치?"}
  match -->|yes| out["문서 ID 방출"]
  match -->|no| cursors

엔진들이 갈리는 지점은 얼마나 공격적으로 일괄 처리하는가와 레이턴시가 어디에 놓이는가다. 전용 검색 엔진은 결과적 일관성을 수용한다. 새로 색인된 문서는 refresh/commit 이후에야 검색된다. 컬럼을 색인하는 관계형 엔진은 인덱스를 힙과 트랜잭션상 일관성 있게 유지해야 한다. 트랜잭션 내 삽입된 행은 같은 트랜잭션의 후속 스캔에서 보여야 한다. 이 제약이 일괄 처리를 쓰기 경로 밖으로 얼마나 밀어낼 수 있는지를 제한한다. GIN의 타협안은 스캔도 읽는 내구성 있는 보조 구조에 일괄 처리하는 것이다.

PostgreSQL의 구현

섹션 제목: “PostgreSQL의 구현”

GIN — Generalized Inverted index, README가 “술이 아니라 지니(genie)로 생각해야 한다”고 못을 박는 — 은 PostgreSQL의 역색인 AM이다. Teodor Sigaev와 Oleg Bartunov가 원저자다. pg_am 카탈로그의 일반 항목이고 IndexAmRoutine 테이블로 디스패치된다(postgres-index-am.md 참조). ginhandler(ginutil.c)가 그 테이블을 채운다. GIN의 성격을 규정하는 두 필드는 amgettuple = NULL과 amgetbitmap = gingetbitmap이다.

// ginhandler — src/backend/access/gin/ginutil.c
amroutine->amoptionalkey = true;
amroutine->amcanreturn = NULL;
// ... condensed ...
amroutine->amgettuple = NULL;          /* GIN은 튜플 단위 반환 불가 */
amroutine->amgetbitmap = gingetbitmap; /* 비트맵 스캔만 가능 */

GIN은 비트맵 스캔만 지원하며 amgettuple을 구현하지 않는다. README가 심층 이유를 설명한다. 펜딩 목록(아래 참조) 때문에 한 스캔 중 동일 힙 TID를 두 번 방문할 수 있어, amgettuple이 요구하는 중복 없는 순서 있는 재개 가능 스트림을 보장할 수 없다. 대신 같은 비트를 TIDBitmap에 반복 설정하는데, 이는 멱등(idempotent)이다. GIN 쿼리의 EXPLAIN이 항상 Bitmap Index Scan을 보여주는 이유가 여기 있다.

GIN의 구조는 네 종류의 페이지로 구성되며, 모두 표준 PageHeader에 GIN 전용 불투명 풋터(GinPageOpaque, rightlink와 flags 보유)를 공유한다.

  1. 메타페이지 (블록 0) — GinMetaPageData: 펜딩 목록의 head/tail, 페이지·튜플 수, 통계.
  2. 엔트리 트리 — Lehman-Yao B-트리(right-link, left-link 없음: GIN은 역방향 스캔 없음). 키는 추출된 키 데이터이고, 리프 튜플은 인라인 포스팅 목록 또는 포스팅 트리 다운링크를 담는다.
  3. 포스팅 트리 — ItemPointer를 키로 하는 보조 B-트리. 한 키의 포스팅 목록이 엔트리 트리 페이지를 넘칠 때 생성된다.
  4. 펜딩 목록 페이지 — fast-update 보조 구조.
flowchart TD
  meta["메타페이지 (blk 0)<br/>펜딩 목록 head/tail<br/>nPendingPages, stats"]
  meta -.->|GinGetUseFastUpdate| pl0["펜딩 페이지<br/>(미정렬, 항목당 TID 1개)"]
  pl0 -->|rightlink| pl1["펜딩 페이지"]
  pl1 -->|rightlink| pl2["펜딩 꼬리 페이지"]
  meta --> root["엔트리 트리 루트<br/>(키의 L&Y B-트리)"]
  root --> e1["엔트리 리프: 키 'fox'<br/>인라인 포스팅 목록 (압축 TID)"]
  root --> e2["엔트리 리프: 키 'the'<br/>GinIsPostingTree -> 다운링크"]
  e2 --> pt["포스팅 트리 루트<br/>(ItemPointer 키 B-트리)"]
  pt --> ptl1["포스팅 리프<br/>압축 TID 세그먼트"]
  pt --> ptl2["포스팅 리프<br/>압축 TID 세그먼트"]

항목이 아닌 키 저장. GIN은 색인 값 전체를 저장하지 않는다. 삽입 시 opclass extractValueFn을 호출해 값을 정렬·중복 제거된 키 배열로 분해하며, 각 키는 null 범주를 갖는다. ginExtractEntries(ginutil.c)가 이를 래핑하고, 키가 없는 경우(NULL 값, 빈 배열)에 플레이스홀더 키를 합성한다. 이 플레이스홀더가 없으면 전체 인덱스 스캔과 IS NULL 쿼리가 해당 행을 조용히 놓친다.

// ginExtractEntries — src/backend/access/gin/ginutil.c
if (isNull)                       /* NULL 항목 -> 플레이스홀더 */
{
    *nentries = 1;
    (*categories)[0] = GIN_CAT_NULL_ITEM;
    return entries;
}
entries = DatumGetPointer(FunctionCall3Coll(&ginstate->extractValueFn[attnum - 1],
                                            ginstate->supportCollation[attnum - 1],
                                            value, PointerGetDatum(nentries),
                                            PointerGetDatum(&nullFlags)));
if (entries == NULL || *nentries <= 0)   /* 빈 배열 등 -> 플레이스홀더 */
{
    *nentries = 1;
    (*categories)[0] = GIN_CAT_EMPTY_ITEM;
    return entries;
}
/* 키가 둘 이상이면 정렬 및 중복 제거 */

세 null 범주 — GIN_CAT_NORM_KEY(일반 키), GIN_CAT_NULL_KEY(항목 내부의 진짜 NULL 원소), GIN_CAT_EMPTY_ITEM/GIN_CAT_NULL_ITEM(키 없는/null 항목용 플레이스홀더) — 는 엔트리 트리 비교자가 실제 키처럼 취급하므로 일반 키와 동일하게 정렬·병합된다.

포스팅 목록 → 포스팅 트리, 적응형 컨테이너. 리프 항목의 TID 목록은 GinMaxItemSize(페이지 약 1/3) 범위 내에 맞는 동안 인덱스 튜플에 인라인으로 저장된다. TID는 압축된다. README가 설명하는 방식은 이렇다. 각 (block, offset)을 43비트 정수로 합치고, 직전 TID 대비 델타 인코딩한 뒤 gap을 varbyte로 인코딩한다. 병합 후 인라인 목록이 크기 제한을 넘으면 GIN은 항목을 포스팅 트리로 변환한다. ItemPointer를 키로 하는 별도 B-트리이며, 리프는 압축 포스팅 목록 세그먼트를 담는다. 리프 항목은 이제 포스팅 트리 루트 블록 번호만 저장하며, 매직 오프셋 GIN_TREE_POSTING(0xffff)으로 플래그된다. GinIsPostingTree(itup)이 튜플 헤더를 읽어 두 경우를 구분한다. 이것이 Zipf 편중에 대한 GIN의 답이다. 드문 키는 인라인 튜플 하나, the 같은 단어는 전용 B-트리를 가진다.

Fast-update: 쓰기를 일괄 처리. 힙 행 하나를 소매 삽입하면 추출된 키당 하나씩, 각각 전체 엔트리 트리 하강이 발생한다. 이론 절에서 설명한 쓰기 증폭 문제 그대로다. GIN의 opt-in 해법(fastupdate, 기본 on)이 펜딩 목록이다. gininsert는 새 항목을 미정렬 상태로 메타페이지에 앵커된 단방향 링크드 리스트 페이지에 추가하고 반환한다. 엔트리 트리로의 비싼 병합은 ginInsertCleanup으로 미뤄진다. 클린업은 목록이 gin_pending_list_limit을 넘거나, 다음 VACUUM 때, 또는 명시적인 gin_clean_pending_list() 호출 시 실행된다. 이익은 IR의 일괄 처리 이익과 정확히 같다. 수천 개의 새 항목이 한 번 정렬되어 각 핫 키의 목록에 한 번씩 병합된다. 비용은 모든 스캔이 펜딩 목록을 먼저 선형 읽어야 한다는 것이므로 목록을 작게 유지해야 한다. fastupdate=off이면 gininsert는 키당 ginHeapTupleInsert → ginEntryInsert를 직접 호출한다.

flowchart TD
  ins["gininsert(row)"] --> fu{"GinGetUseFastUpdate?"}
  fu -->|yes| collect["ginHeapTupleFastCollect<br/>키 추출 -> collector"]
  collect --> fast["ginHeapTupleFastInsert<br/>펜딩 목록에 추가 (메타페이지)"]
  fast --> chk{"펜딩 목록 ><br/>gin_pending_list_limit?"}
  chk -->|yes| clean["ginInsertCleanup<br/>(엔트리 트리로 병합)"]
  chk -->|no| done1["return"]
  fu -->|no| retail["키별: ginHeapTupleInsert<br/>-> ginEntryInsert (하강 + 병합)"]
  retail --> done2["return"]
  clean --> done1

스캔 = 펜딩 목록, 그 다음 메인 인덱스, consistent()를 통한 병합. GIN 스캔(gingetbitmap)은 먼저 scanPendingInsert로 펜딩 목록을 스캔하고, 이어 scanGetItem/keyGetItem으로 메인 인덱스를 탐색하며, 둘 다 같은 TIDBitmap에 결과를 넣는다. 쿼리는 extractQueryFn이 qual당 하나의 GinScanKey, 쿼리 키당 하나의 GinScanEntry로 분해한다. 각 항목은 자신의 키 TID에 대한 커서다. keyGetItem은 커서를 TID 순서로 병합하고, 각 후보 TID에서 opclass consistent 함수를 어떤 항목이 존재했는지 불리언 벡터와 함께 호출한다. consistent 함수는 연산자 의미론을 인코딩한다(@>는 모든 쿼리 키 필요, &&는 임의 키 하나). 항목은 required와 additional로 분류되어 required 항목이 하나라도 있어야 하므로 병합이 TID를 저렴하게 건너뛸 수 있다.

소스 코드 가이드

섹션 제목: “소스 코드 가이드”

GIN 코드는 이 문서가 목표로 하는 네 파일을 따라 깔끔하게 나뉜다. gininsert.c(삽입 + 빌드), ginfast.c(펜딩 목록과 클린업), ginbtree.c(엔트리 트리와 포스팅 트리 양쪽에 공용되는 트리 탐색 엔진), ginget.c(스캔). ginvacuum.c가 라이프사이클을 완성한다. 호출 흐름을 따라간다.

소매 삽입: gininsert → ginEntryInsert → 적응형 컨테이너

섹션 제목: “소매 삽입: gininsert → ginEntryInsert → 적응형 컨테이너”

gininsert는 AM 진입점이다. fast-update 대 소매라는 단일 분기가 전부다.

// gininsert — src/backend/access/gin/gininsert.c
if (GinGetUseFastUpdate(index))
{
    GinTupleCollector collector;
    memset(&collector, 0, sizeof(GinTupleCollector));
    for (i = 0; i < ginstate->origTupdesc->natts; i++)
        ginHeapTupleFastCollect(ginstate, &collector,
                                (OffsetNumber) (i + 1),
                                values[i], isnull[i], ht_ctid);
    ginHeapTupleFastInsert(ginstate, &collector);   /* -> 펜딩 목록 */
}
else
{
    for (i = 0; i < ginstate->origTupdesc->natts; i++)
        ginHeapTupleInsert(ginstate, (OffsetNumber) (i + 1),
                           values[i], isnull[i], ht_ctid);  /* -> 엔트리 트리 */
}

소매 경로는 GIN 포스팅 목록-또는-트리 로직의 핵심인 ginEntryInsert로 향한다. 엔트리 트리를 ginFindLeafPage로 하강한 뒤, 키에서 발견한 것에 따라 세 가지 중 하나를 취한다.

// ginEntryInsert — src/backend/access/gin/gininsert.c
stack = ginFindLeafPage(&btree, false, false);
page = BufferGetPage(stack->buffer);


if (btree.findItem(&btree, stack))           /* 키가 이미 존재 */
{
    itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, stack->off));
    if (GinIsPostingTree(itup))              /* (1) 이미 포스팅 트리 */
    {
        BlockNumber rootPostingTree = GinGetPostingTree(itup);
        LockBuffer(stack->buffer, GIN_UNLOCK);
        freeGinBtreeStack(stack);
        ginInsertItemPointers(ginstate->index, rootPostingTree,
                              items, nitem, buildStats);   /* 포스팅 트리로 삽입 */
        return;
    }
    CheckForSerializableConflictIn(ginstate->index, NULL,
                                   BufferGetBlockNumber(stack->buffer));
    itup = addItemPointersToLeafTuple(ginstate, itup,    /* (2) 인라인 목록 확장 */
                                      items, nitem, buildStats, stack->buffer);
    insertdata.isDelete = true;
}
else
{
    CheckForSerializableConflictIn(ginstate->index, NULL,
                                   BufferGetBlockNumber(stack->buffer));
    itup = buildFreshLeafTuple(ginstate, attnum, key, category,  /* (3) 새 키 */
                               items, nitem, buildStats, stack->buffer);
    if (buildStats)
        buildStats->nEntries++;
}
insertdata.entry = itup;
ginInsertValue(&btree, stack, &insertdata, buildStats);

(2)번 addItemPointersToLeafTuple에서 컨테이너 전환이 일어난다. 기존 TID 목록과 새 TID 목록을 ginMergeItemPointers로 병합하고 재압축한 뒤 인라인 튜플 재형성을 시도한다. 압축 목록이 GinMaxItemSize 한계를 넘으면(ginCompressPostingList에서 compressedList == NULL 반환) 포스팅 트리로 승격한다.

// addItemPointersToLeafTuple — src/backend/access/gin/gininsert.c
newItems = ginMergeItemPointers(items, nitem, oldItems, oldNPosting, &newNPosting);
compressedList = ginCompressPostingList(newItems, newNPosting, GinMaxItemSize, NULL);
if (compressedList)
    res = GinFormTuple(ginstate, attnum, key, category,
                       (char *) compressedList,
                       SizeOfGinPostingList(compressedList), newNPosting, false);
if (!res)
{
    /* 포스팅 목록이 너무 커짐, 포스팅 트리로 변환 */
    BlockNumber postingRoot;
    postingRoot = createPostingTree(ginstate->index, oldItems, oldNPosting,
                                    buildStats, buffer);
    ginInsertItemPointers(ginstate->index, postingRoot, items, nitem, buildStats);
    res = GinFormTuple(ginstate, attnum, key, category, NULL, 0, 0, true);
    GinSetPostingTree(res, postingRoot);   /* 리프 튜플은 이제 다운링크 보유 */
}

buildFreshLeafTuple(3번)도 같은 로직이다. 새 키는 먼저 인라인을 시도하고, 초기 목록이 이미 너무 크면 새 포스팅 트리를 생성한다.

공용 B-트리 엔진: ginbtree.c

섹션 제목: “공용 B-트리 엔진: ginbtree.c”

엔트리 트리와 모든 포스팅 트리는 GinBtreeData vtable(findChildPage, isMoveRight, beginPlaceToPage, execPlaceToPage, prepareDownlink, fillRoot)로 매개변수화된 하나의 범용 엔진으로 구동된다. ginFindLeafPage가 하강 함수다. 페이지를 하나씩 래치 연결(latch-couple)하며, 하강 중 두 가지 L&Y 조건을 처리한다. 마주치는 미완료 분할을 완료하고, 동시 분할로 키 공간이 이동했을 때 오른쪽으로 이동한다.

// ginFindLeafPage — src/backend/access/gin/ginbtree.c
access = ginTraverseLock(stack->buffer, searchMode);
/* 트리를 수정하는 경우, 마주치는 미완료 분할을 완료 */
if (!searchMode && GinPageIsIncompleteSplit(page))
    ginFinishOldSplit(btree, stack, NULL, access);
/* 루트는 right-link가 없으므로 소규모 최적화 가능 */
while (btree->fullScan == false && stack->blkno != btree->rootBlkno &&
       btree->isMoveRight(btree, page))
{
    BlockNumber rightlink = GinPageGetOpaque(page)->rightlink;
    if (rightlink == InvalidBlockNumber)
        break;                              /* 가장 오른쪽 페이지 */
    stack->buffer = ginStepRight(stack->buffer, btree->index, access);
    stack->blkno = rightlink;
    page = BufferGetPage(stack->buffer);
}

ginStepRight는 L&Y의 “오른쪽으로 이동” 기본 연산이며, GIN의 동시성-대-VACUUM 인터락의 핵심이다. 현재 페이지를 해제하기 전에 다음 페이지를 잠근다. 덕분에 동시 페이지 삭제가 right-link를 따라가려는 독자 아래에서 페이지를 제거하지 못한다.

// ginStepRight — src/backend/access/gin/ginbtree.c
nextbuffer = ReadBuffer(index, blkno);
LockBuffer(nextbuffer, lockmode);
UnlockReleaseBuffer(buffer);            /* 다음 잠금 획득 후에만 해제 */
page = BufferGetPage(nextbuffer);
if (isLeaf != GinPageIsLeaf(page) || isData != GinPageIsData(page))
    elog(ERROR, "right sibling of GIN page is of different type");

ginPlaceToPage는 실제 삽입 또는 분할을 수행한다. 세 가지 상태 프로토콜 — GPTP_NO_WORK / GPTP_INSERT / GPTP_SPLIT — 은 nbtree의 원자적 분할 설계를 반영한다. 내부 페이지 삽입이 다운링크 게시를 완료하면 자식의 GIN_INCOMPLETE_SPLIT 플래그를 같은 WAL 액션에서 지운다. 분할 중 충돌이 발생해도 right-link가 독자를 안내하므로 트리는 계속 검색 가능하며, 다음 쓰기가 분할을 지연 완료한다.

// ginPlaceToPage — src/backend/access/gin/ginbtree.c
rc = btree->beginPlaceToPage(btree, stack->buffer, stack, insertdata,
                             updateblkno, &ptp_workspace, &newlpage, &newrpage);
if (rc == GPTP_INSERT)
{
    START_CRIT_SECTION();
    btree->execPlaceToPage(btree, stack->buffer, stack, insertdata,
                           updateblkno, ptp_workspace);
    if (BufferIsValid(childbuf))   /* 다운링크 삽입이 자식 분할 완료 */
    {
        GinPageGetOpaque(childpage)->flags &= ~GIN_INCOMPLETE_SPLIT;
        MarkBufferDirty(childbuf);
    }
    /* ... WAL ... */
}

Fast-update: ginfast.c

섹션 제목: “Fast-update: ginfast.c”

ginHeapTupleFastCollect는 수집 절반이다. 키를 추출하고(소매와 동일한 ginExtractEntries) 펜딩 형식 튜플을 구성한다. 펜딩 형식 튜플은 포스팅 목록이 없다. 단일 힙 TID가 t_tid에 직접 들어간다.

// ginHeapTupleFastCollect — src/backend/access/gin/ginfast.c
entries = ginExtractEntries(ginstate, attnum, value, isNull, &nentries, &categories);
for (i = 0; i < nentries; i++)
{
    IndexTuple itup = GinFormTuple(ginstate, attnum, entries[i], categories[i],
                                   NULL, 0, 0, true);
    itup->t_tid = *ht_ctid;          /* 펜딩 항목당 TID 1개 */
    collector->tuples[collector->ntuples++] = itup;
    collector->sumsize += IndexTupleSize(itup);
}

ginHeapTupleFastInsert는 수집된 튜플을 메타페이지에 앵커된 목록에 추가한다. 배치가 페이지 하나보다 크거나 꼬리 페이지 공간이 부족하면 별도 서브리스트를 만들어 꼬리에 접합한다. 그렇지 않으면 꼬리 페이지에 추가한다. GIN_LIST_FULLROW 플래그 비트는 페이지가 완전한 힙 튜플 행을 담는지 단편(fragment)인지를 기록하며, 스캔 측이 이를 활용한다. 메타페이지 잠금 처리는 동시성을 높이기 위해 서브리스트 구성 중 잠금을 해제했다가 재획득하는 방식이다.

// ginHeapTupleFastInsert — src/backend/access/gin/ginfast.c
if (collector->sumsize + collector->ntuples * sizeof(ItemIdData) > GinListPageSize)
    separateList = true;
else
{
    LockBuffer(metabuffer, GIN_EXCLUSIVE);
    metadata = GinPageGetMeta(metapage);
    if (metadata->head == InvalidBlockNumber ||
        collector->sumsize + collector->ntuples * sizeof(ItemIdData) > metadata->tailFreeSize)
    {
        separateList = true;
        LockBuffer(metabuffer, GIN_UNLOCK);   /* 동시성 유지를 위해 잠금 해제 */
    }
}

ginInsertCleanup은 병합 절반이다. 지연된 쓰기 비용을 갚는 함수다. 메타페이지에 LockPage(heavyweight 페이지 잠금, 버퍼 잠금과 다름)로 동시 클린업을 방지한다. 동시 삽입은 여전히 허용된다. 그런 다음 펜딩 페이지를 걷고, BuildAccumulator(키 (attnum, key) 기반의 레드-블랙 트리)에 항목을 쌓으며, 메모리가 찰 때 또는 목록 끝에 도달했을 때 ginEntryInsert로 엔트리 트리에 플러시한다.

// ginInsertCleanup — src/backend/access/gin/ginfast.c
if (forceCleanup)                        /* VACUUM / gin_clean_pending_list에서 */
    LockPage(index, GIN_METAPAGE_BLKNO, ExclusiveLock);   /* 경쟁자 대기 */
else if (!ConditionalLockPage(index, GIN_METAPAGE_BLKNO, ExclusiveLock))
    return;                              /* 경쟁자가 이미 클린업 중, 탈출 */
/* ... */
processPendingPage(&accum, &datums, page, FirstOffsetNumber);
/* 메모리가 찼거나 목록 끝에 도달하면: */
ginBeginBAScan(&accum);
while ((list = ginGetBAEntry(&accum, &attnum, &key, &category, &nlist)) != NULL)
    ginEntryInsert(ginstate, attnum, key, category, list, nlist, NULL);
shiftList(index, metabuffer, blkno, fill_fsm, stats);   /* 병합된 페이지 연결 해제 */

BuildAccumulator가 일괄 처리의 핵심 보상이다. 같은 키의 모든 펜딩 항목이 단일 ginEntryInsert 전에 모이므로, 핫 키의 포스팅 목록은 행당 한 번이 아니라 클린업당 한 번 재작성된다. shiftList는 병합된 head 페이지들을 메타페이지 목록에서 일괄(GIN_NDELETE_AT_ONCE) 해제하고 FSM에 반환한다.

스캔: ginget.c

섹션 제목: “스캔: ginget.c”

gingetbitmap이 AM 스캔 진입점이다. 순서가 중요하다. 펜딩 목록을 먼저 읽고 메인 인덱스를 읽는다. 코드 주석이 TID가 두 번 방문될 수 있는 이유(그리고 비트맵에는 무해하지만 amgettuple에는 치명적인 이유)를 설명한다.

// gingetbitmap — src/backend/access/gin/ginget.c
ginNewScanKey(scan);            /* extractQuery -> GinScanKey/GinScanEntry */
if (GinIsVoidRes(scan)) return 0;
scanPendingInsert(scan, tbm, &ntids);   /* 펜딩 목록 먼저 */
startScan(scan);
ItemPointerSetMin(&iptr);
for (;;)
{
    if (!scanGetItem(scan, iptr, &iptr, &recheck))
        break;
    if (ItemPointerIsLossyPage(&iptr))
        tbm_add_page(tbm, ItemPointerGetBlockNumber(&iptr));   /* 전체 페이지 */
    else
        tbm_add_tuples(tbm, &iptr, 1, recheck);
    ntids++;
}

scanGetItem은 모든 스캔 키를 동시에 전진시켜 모든 키를 만족하는 다음 TID를 찾는다. “이보다 작은 것은 일치 없음, 앞으로 건너뛰기” 최적화로 도약한다. 키별로 keyGetItem이 requiredEntries 중 advancePast보다 큰 최소 TID를 찾고, 해당 TID의 additionalEntries를 로드한 뒤 consistent 함수를 호출한다.

// keyGetItem — src/backend/access/gin/ginget.c
ItemPointerSetMax(&minItem);
for (i = 0; i < key->nrequired; i++)
{
    entry = key->requiredEntries[i];
    if (entry->isFinished) continue;
    if (ginCompareItemPointers(&entry->curItem, &advancePast) <= 0)
    {
        entryGetItem(ginstate, entry, advancePast);   /* 이 커서 전진 */
        if (entry->isFinished) continue;
    }
    allFinished = false;
    if (ginCompareItemPointers(&entry->curItem, &minItem) < 0)
        minItem = entry->curItem;       /* 가장 작은 required TID = 다음 후보 */
}

각 항목의 커서는 entryGetItem이 공급한다. 인라인 포스팅 목록이나 포스팅 트리(페이지 단위 전진), 또는 부분 일치·전체 스캔 항목을 위한 미리 수집된 matchBitmap에서 TID를 꺼낸다.

부분 일치와 전체 스캔: collectMatchBitmap. 부분 일치 항목(예: pg_trgm이 가속하는 LIKE 'foo%', 또는 범위)은 단일 키를 가리킬 수 없다. 엔트리 트리의 범위를 스캔해 모든 포스팅 목록을 하나의 비트맵으로 합쳐야 한다. collectMatchBitmap은 moveRightIfItNeeded로 엔트리 트리 리프를 좌→우 방향으로 걷고, opclass comparePartialFn을 호출해 범위 끝을 판단하며, 일치하는 항목의 TID(인라인 또는 scanPostingTree)를 scanEntry->matchBitmap에 접는다.

// collectMatchBitmap — src/backend/access/gin/ginget.c
if (scanEntry->isPartialMatch)
{
    if (icategory != GIN_CAT_NORM_KEY)   /* 부분 일치는 null과 절대 일치 없음 */
        return true;
    cmp = DatumGetInt32(FunctionCall4Coll(&btree->ginstate->comparePartialFn[attnum - 1],
                                          btree->ginstate->supportCollation[attnum - 1],
                                          scanEntry->queryKey, idatum,
                                          UInt16GetDatum(scanEntry->strategy),
                                          PointerGetDatum(scanEntry->extra_data)));
    if (cmp > 0)        return true;     /* 범위 지남: 중단 */
    else if (cmp < 0) { stack->off++; continue; }   /* 범위 전: 건너뜀 */
    /* cmp == 0: 이 항목은 범위 내 -> TID를 matchBitmap에 접음 */
}

moveRightIfItNeeded는 밟는 각 엔트리 리프에 **서술자 잠금(predicate lock)**을 획득하기도 한다. GIN이 직렬화 가능 격리를 지원하는 방식이다. README의 서술자 잠금 설명에서는 리프 “갭”을 잠그고, 트리 기반 키의 동등 비교를 위해 포스팅 트리 루트를 잠그고, 펜딩 목록과 인터락하기 위해 항상 메타페이지를 잠근다고 서술한다. SSI 세부 사항은 postgres-ssi-predicate-locking.md에 있다.

펜딩 목록 스캔: scanPendingInsert. 메인 인덱스 전에 GIN은 펜딩 목록을 행 단위로 스캔한다. 펜딩 항목은 미정렬이고 한 행의 항목이 여러 페이지에 걸칠 수 있어, 한 힙 행의 항목 전체를 읽고(collectMatchesForHeapRow), entryRes/hasMatchKey 배열을 채우고, 각 키의 boolConsistentFn을 직접 호출한다.

// scanPendingInsert — src/backend/access/gin/ginget.c
PredicateLockPage(scan->indexRelation, GIN_METAPAGE_BLKNO, scan->xs_snapshot);
LockBuffer(metabuffer, GIN_SHARE);
blkno = GinPageGetMeta(page)->head;
/* ... */
while (scanGetCandidate(scan, &pos))     /* 힙 행 단위 */
{
    if (!collectMatchesForHeapRow(scan, &pos)) continue;
    match = true;
    for (i = 0; i < so->nkeys; i++)
    {
        GinScanKey key = so->keys + i;
        if (!key->boolConsistentFn(key)) { match = false; break; }
        recheck |= key->recheckCurItem;
    }
    if (match) { tbm_add_tuples(tbm, &pos.item, 1, recheck); (*ntids)++; }
}

빌드: ginbuild

섹션 제목: “빌드: ginbuild”

ginbuild는 메타페이지와 리프 루트를 초기화한 뒤 힙을 스캔한다. 행마다 소매 삽입하는 대신 maintenance_work_mem 내 BuildAccumulator에 포스팅을 쌓고 ginEntryInsert로 배치 플러시한다. ginInsertCleanup이 사용하는 것과 동일한 벌크-병합 메커니즘이다. README가 벌크 삽입을 “소매 삽입보다 훨씬 빠르다”고 부르는 이유가 여기 있다. PG 18은 병렬 워커로 빌드를 구동할 수도 있다(_gin_begin_parallel). 워커들이 GinTuple을 추출해 tuplesort하고 리더가 정렬 스트림을 병합한다.

// ginbuild — src/backend/access/gin/gininsert.c
MetaBuffer = GinNewBuffer(index);
RootBuffer = GinNewBuffer(index);
GinInitMetabuffer(MetaBuffer);
GinInitBuffer(RootBuffer, GIN_LEAF);
/* ... */
buildstate.accum.ginstate = &buildstate.ginstate;
ginInitBA(&buildstate.accum);
if (indexInfo->ii_ParallelWorkers > 0)
    _gin_begin_parallel(state, heap, index, indexInfo->ii_Concurrent,
                        indexInfo->ii_ParallelWorkers);

VACUUM: ginvacuum.c

섹션 제목: “VACUUM: ginvacuum.c”

GIN의 amvacuumcleanup/ambulkdelete는 각각 ginvacuumcleanup과 ginbulkdelete다. README의 규칙은 “VACUUM은 엔트리 트리에서 튜플이나 페이지를 삭제하지 않는다”는 것이다. 키 어휘는 안정적이라고 가정한다. 따라서 ginbulkdelete는 먼저 펜딩 목록을 플러시(ginInsertCleanup, forceCleanup)하고, 엔트리 트리 리프를 right-link로 좌→우 탐색하며 각 리프의 인라인 포스팅 목록에서 죽은 TID를 제거(ginVacuumEntryPage)하고, 각 포스팅 트리로 재귀한다.

// ginbulkdelete — src/backend/access/gin/ginvacuum.c
if (stats == NULL)
{
    stats = (IndexBulkDeleteResult *) palloc0(sizeof(IndexBulkDeleteResult));
    ginInsertCleanup(&gvs.ginstate, !AmAutoVacuumWorkerProcess(),
                     false, true, stats);   /* 먼저 펜딩 목록 비움 */
}
/* ... right-link로 엔트리 리프 탐색 ... */
resPage = ginVacuumEntryPage(&gvs, buffer, rootOfPostingTree, &nRoot);
blkno = GinPageGetOpaque(page)->rightlink;
/* ... */
for (i = 0; i < nRoot; i++)
    ginVacuumPostingTree(&gvs, rootOfPostingTree[i]);   /* 포스팅 트리로 재귀 */

포스팅 트리는 축소된다. ginVacuumPostingTree는 두 단계로 실행된다. 1단계 ginVacuumPostingTreeLeaves가 모든 리프에서 죽은 TID를 제거하고 빈 리프가 있는지 기록한다. 빈 리프가 발견된 경우에만 포스팅 트리 루트에 클린업 잠금(LockBufferForCleanup, 모든 핀 보유자, 즉 진행 중인 독자를 대기)을 걸고 ginScanToDelete를 실행해 빈 페이지를 물리적으로 해제한다.

// ginVacuumPostingTree — src/backend/access/gin/ginvacuum.c
if (ginVacuumPostingTreeLeaves(gvs, rootBlkno))   /* 1단계: TID 제거 */
{
    /* 2단계: 빈 페이지가 하나 이상 -> 재스캔 후 빈 것 삭제 */
    buffer = ReadBufferExtended(gvs->index, MAIN_FORKNUM, rootBlkno, RBM_NORMAL,
                                gvs->strategy);
    LockBufferForCleanup(buffer);      /* 동시 삽입·독자 차단 */
    /* ... */
    ginScanToDelete(gvs, rootBlkno, true, &root, InvalidOffsetNumber);
}

ginScanToDelete는 조사 중인 경로 페이지들의 왼쪽 형제에 독점 잠금을 유지한다. 페이지 제거 시 다운링크와 right-link를 고치는 동안 오른쪽→왼쪽 잠금 순서를 절대 취하지 않기 위해서다. 그 순서는 동시 ginStepRight와 교착 상태를 일으킬 수 있다. 삭제된 페이지에는 “방문할 수도 있는 가장 최신 xid”가 표시되어, 해당 포인터를 이미 읽었을 수 있는 모든 독자가 완료될 때까지 재활용하지 않는다. nbtree와 동일한 지연 반환 규칙이다. ginvacuumcleanup은 마지막으로 비어진 포스팅 트리 페이지를 FSM에 반환하고 메타페이지 통계를 갱신한다.

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

섹션 제목: “위치 힌트 (2026-06-05 기준, REL_18 273fe94)”
심볼파일줄
ginhandlersrc/backend/access/gin/ginutil.c38
ginExtractEntriessrc/backend/access/gin/ginutil.c488
gininsertsrc/backend/access/gin/gininsert.c851
ginEntryInsertsrc/backend/access/gin/gininsert.c341
addItemPointersToLeafTuplesrc/backend/access/gin/gininsert.c211
buildFreshLeafTuplesrc/backend/access/gin/gininsert.c291
ginbuildsrc/backend/access/gin/gininsert.c608
_gin_begin_parallelsrc/backend/access/gin/gininsert.c922
ginHeapTupleFastCollectsrc/backend/access/gin/ginfast.c483
ginHeapTupleFastInsertsrc/backend/access/gin/ginfast.c219
ginInsertCleanupsrc/backend/access/gin/ginfast.c780
shiftListsrc/backend/access/gin/ginfast.c554
ginFindLeafPagesrc/backend/access/gin/ginbtree.c83
ginStepRightsrc/backend/access/gin/ginbtree.c177
ginTraverseLocksrc/backend/access/gin/ginbtree.c39
ginPlaceToPagesrc/backend/access/gin/ginbtree.c337
gingetbitmapsrc/backend/access/gin/ginget.c1931
scanGetItemsrc/backend/access/gin/ginget.c1300
keyGetItemsrc/backend/access/gin/ginget.c1005
entryGetItemsrc/backend/access/gin/ginget.c812
collectMatchBitmapsrc/backend/access/gin/ginget.c121
moveRightIfItNeededsrc/backend/access/gin/ginget.c43
scanPostingTreesrc/backend/access/gin/ginget.c69
scanPendingInsertsrc/backend/access/gin/ginget.c1837
ginbulkdeletesrc/backend/access/gin/ginvacuum.c564
ginvacuumcleanupsrc/backend/access/gin/ginvacuum.c687
ginVacuumPostingTreesrc/backend/access/gin/ginvacuum.c408
ginVacuumPostingTreeLeavessrc/backend/access/gin/ginvacuum.c345
ginScanToDeletesrc/backend/access/gin/ginvacuum.c246
GinIsPostingTree / GIN_TREE_POSTINGsrc/include/access/ginblock.h232 / 231
GinPageIsIncompleteSplitsrc/include/access/ginblock.h128
GinScanKeyDatasrc/include/access/gin_private.h269
GinScanEntryDatasrc/include/access/gin_private.h337
GinBtreeDatasrc/include/access/gin_private.h151

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

섹션 제목: “소스 검증 (2026-06-05 기준)”

검증은 /data/hgryoo/references/postgres, REL_18_STABLE, 커밋 273fe94852b(“Fix off-by-one with NFC recomposition for Hangul U+11A7 (TBASE)“)를 기준으로 한다. 위의 모든 코드 발췌는 선행 // symbol — path 주석에 명시된 파일에서 직접 복사하고 줄 생략(/* ... */)만 적용했다. 로직을 바꿔 쓴 부분은 없다. 다음 사실들을 직접 확인했다.

  • AM 표면. ginhandler(ginutil.c)가 amgettuple = NULL, amgetbitmap = gingetbitmap으로 설정하는 것을 grep "amget" ginutil.c로 확인했다. GIN은 비트맵 전용이다.
  • 포스팅 트리 구분자. ginblock.h가 GIN_TREE_POSTING ((OffsetNumber)0xffff)와 GinIsPostingTree(itup) (GinGetNPosting(itup) == GIN_TREE_POSTING)을 정의하며, GinGetNPosting이 t_tid의 오프셋 필드를 읽는 것을 확인했다. README가 설명하는 헤더 필드 유용 방식이 맞다.
  • Fast-update 토글. gininsert가 GinGetUseFastUpdate(index)로 분기한다. fastupdate는 기본 on이다(GinOptions / ginutil.c reloptions). 펜딩 목록이 GinMetaPageData(head, tail, tailFreeSize, nPendingPages)에 앵커링된 것을 ginblock.h에서 확인했다.
  • 클린업 인터락. ginInsertCleanup이 GIN_METAPAGE_BLKNO에 LockPage / ConditionalLockPage(heavyweight 페이지 잠금, storage/lmgr)를 사용한다. 버퍼 콘텐츠 잠금과 별개임을 두 잠금 호출과 주석을 읽어 확인했다.
  • VACUUM 비대칭. ginbulkdelete가 엔트리 리프 탐색 전에 ginInsertCleanup(..., forceCleanup = true)를 호출한다. 엔트리 트리 페이지 삭제는 없다(ginDeletePage는 ginScanToDelete에서 포스팅 트리에만 호출된다). grep -n ginDeletePage ginvacuum.c로 확인했다.
  • 포스팅 트리 삭제를 위한 클린업 잠금. ginVacuumPostingTree가 1단계에서 빈 페이지를 보고한 경우에만 포스팅 트리 루트에 LockBufferForCleanup(buffer)를 호출한다. README의 “트리 루트에 full cleanup lock”과 일치한다.
  • 서술자 잠금. collectMatchBitmap/moveRightIfItNeeded와 scanPendingInsert가 각각 엔트리 리프, 포스팅 트리 루트, 메타페이지에 PredicateLockPage를 호출한다. README의 서술자 잠금 섹션이 열거하는 세 잠금 대상과 일치한다.

주목할 한 가지 미묘한 점이 있다. README의 동시성 그림은 하강 및 step-right 중 핀/잠금 *결합(coupling)*을 묘사하지만, 탐색 모드(searchMode = true)의 ginFindLeafPage는 부모 핀을 유지하지 않는다. ReleaseAndReadBuffer를 사용하고 “리프로의 경로를 잊을 수 있다”. 삽입 모드는 핀을 유지한다. ginFindLeafPage 상단의 코드 주석이 권위 있는 참조다. README의 “Insert” 그림은 삽입 모드 경우다.

GIN이 scan->kill_prior_tuple/ignore_killed_tuples를 무시하고(nbtree 같은 LP_DEAD 힌팅 없음), equality나 부분 일치 범위 메커니즘으로만 항목을 일치시킬 수 있다는 점(일반적인 부등호 검색 없음)도 README와 코드에서 확인했다.

포스팅 목록 인코딩 주장 최종 확인. README의 “Posting List Compression” 절과 ginpostinglist.c는 포스팅 목록이 — 엔트리 트리 리프의 인라인 목록과 포스팅 트리 리프 페이지 모두 — 원시 ItemPointerData 배열이 아니라 델타 인코딩 + varbyte로 저장됨에 동의한다.

// ginCompressPostingList — src/backend/access/gin/ginpostinglist.c
// 포인터는 정렬된 순서로 도착; 이전 것과의 *차이*를 저장
result->first = ipd[0];                       /* 첫 TID는 그대로 저장 */
prev = itemptr_to_uint64(&result->first);
for (totalpacked = 1; totalpacked < nipd; totalpacked++)
{
    uint64  val = itemptr_to_uint64(&ipd[totalpacked]);
    uint64  delta = val - prev;
    Assert(val > prev);
    /* ... 경계 검사 생략 ... */
    encode_varbyte(delta, &ptr);              /* 작은 델타 => 더 적은 바이트 */
    prev = val;
}

encode_varbyte는 바이트당 7 페이로드 비트를 내보내고 최상위 비트를 연속 플래그로 사용한다. 직전 TID에서 한 블록 떨어진 TID는 6바이트가 아니라 1~2바이트가 된다. 핫 키의 수백만 TID 포스팅 목록이 압축 상태를 유지하는 온디스크 이유다. GinItupIsCompressed(itup)이 존재하는 이유도 여기 있다. 엔트리 리프는 압축 형식과 (하위 호환성을 위한) 원시 배열 양쪽을 담을 수 있어, 독자가 플래그로 분기한다.

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

섹션 제목: “PostgreSQL 너머 — 비교 설계와 연구 프론티어”

  • Lucene / 고전 IR 역색인. GIN의 엔트리 트리 + 포스팅 목록 형태는 Lucene 세그먼트의 관계형 엔진 반영이다. 항 사전(Lucene의 FST; GIN의 엔트리 B-트리)이 각 키를 포스팅 스트림(Lucene의 .doc/.pos 파일; GIN의 인라인 목록 또는 포스팅 트리)으로 매핑한다. varbyte 델타 인코딩은 Lucene의 PForDelta/FOR 블록 코덱과 같은 계열이다. 둘 다 정렬된 doc-ID와 작은 gap을 활용한다. 가장 날카로운 차이는 fast-update 펜딩 목록이다. Lucene은 세그먼트 불변이고 세그먼트 전체를 병합한다. GIN은 메인 인덱스를 제자리 수정하고 메타페이지에 앵커된 사이드 로그를 유지한다. GIN의 ginInsertCleanup을 Lucene의 세그먼트 병합 정책과 대조하면 인플레이스-대-불변 트레이드오프가 명확해진다.

  • 비트맵 및 변형 인덱스 (O’Neil & Quass 1997). GIN이 겨냥하는 “한 키 값이 많은 행에 존재” 워크로드는 비트맵 인덱스가 구축된 저-카디널리티 경우 그대로다. GIN의 consistent 함수 결합은 비트맵 인덱스가 두 비트맵을 AND하는 것에 해당하는 포스팅 목록 교집합이다. Variant Indexes 논문(dbms-papers/variant-index.md) — bit-sliced 및 projection 인덱스, 비트맵 대 목록 공간 교차점 — 이 GIN이 긴 목록을 비트맵으로 구체화하지 않고 varbyte 런으로 압축하는 이유를 보는 적절한 렌즈다. GIN의 TID 공간은 희소하고 무한히 증가할 수 있어(힙이 커질 수 있음), 키가 거의 보편적이 되기 전까지는 gap 코딩 목록이 밀집 비트맵을 이긴다.

  • RUM (GIN 후속 확장). rum 접근 방법(서드파티 확장, 코어 외부, 예시로만 명시)은 GIN의 포스팅 항목을 추가 속성 — 어휘소 위치, 타임스탬프, 거리 — 을 담도록 확장해 순서 연산자(tsvector <=> tsquery, 랭킹)를 힙 페치 없이 인덱스에서 답할 수 있게 한다. GIN은 포스팅에 TID만 저장한다. RUM의 더 풍부한 포스팅 설계와 GIN의 TID-only 목록을 비교하면, GIN의 비트맵 전용 amgetbitmap 인터페이스가 순서·점수 결과를 반환할 수 있는 인덱스와 비교해 무엇을 포기하는지 정량화된다.

  • 펜딩 목록 / LSM 유추. GIN의 fast-update 경로 — 비순서 삽입을 사이드 로그에 버퍼링하다 나중에 일괄 병합 — 는 구조적으로 1-레벨 로그 구조 병합과 같다. 펜딩 목록이 인플레이스 “L0”이고 ginInsertCleanup이 정렬된 메인 인덱스로의 압축이다. 실제 LSM과 달리 GIN은 병합 대상이 정확히 하나이고 모든 스캔에서 펜딩 목록을 선형 읽으므로, 클린업이 뒤처지면 무한한 읽기 세금을 낸다(gin_pending_list_limit / autovacuum 트리거가 이를 제한한다). GIN을 RocksDB 스타일 다중 레벨 LSM과 비교하면 GIN이 계층화된 정렬 런 대신 단일 미정렬 버퍼를 유지하는 이유가 명확해진다.

  • 부분 일치와 접두사 검색 대 트라이그램·접미사 구조. GIN의 extractQuery 부분 일치 모드(collectMatchBitmap이 엔트리 키 범위를 탐색)는 엔트리 트리가 정렬되어 있어 접두사·범위 일치를 사실상 무료로 제공한다. pg_trgm과 LIKE 가속 opclass가 GIN 위에 올라타는 방식이다. 전용 접미사 배열·FM 인덱스 텍스트 구조와의 비교는 GIN의 범용 정렬 엔트리 트리가 배열, jsonb, tsvector를 하나의 메커니즘으로 처리하면서 무엇을 포기하는지 프레임을 제공한다.

  • 동시성: 페이지 삭제 없는 L&Y 엔트리 트리. GIN의 엔트리 트리는 Lehman-Yao B-트리(right-link, step-right 복구)이지만 — nbtree와 달리 — 엔트리 페이지를 삭제하지 않는다. 키 어휘가 안정적이라고 가정하기 때문이다(postgres-nbtree.md가 완전한 L&Y 삭제 프로토콜을 담당한다). 이것이 제기하는 연구 질문은 팽창(bloat)이다. 키 집합이 변동하는 컬럼(키가 나타났다가 영구히 사라지는)의 GIN 인덱스는 전체 REINDEX만이 회수할 수 있는 죽은 엔트리 리프를 쌓는다. nbtree의 _bt_pagedel half-dead/unlink 메커니즘과 비교하면 GIN의 “어휘는 영원하다” 가정의 비용이 분리된다.

출처

섹션 제목: “출처”

트리 내 README 및 소스 파일 (REL_18_STABLE, 커밋 273fe94)

섹션 제목: “트리 내 README 및 소스 파일 (REL_18_STABLE, 커밋 273fe94)”
  • src/backend/access/gin/README — 설계 문서: 역색인 기초, 범용 전략 함수 계약, 엔트리 트리 대 포스팅 목록 대 포스팅 트리 레이아웃, fast-update 펜딩 목록과 클린업, 포스팅 목록(varbyte) 압축, 동시성과 서술자 잠금, “엔트리 페이지 삭제 없음” 제한.
  • src/include/access/ginblock.h — GinMetaPageData(펜딩 목록 앵커: head, tail, tailFreeSize, nPendingPages), GinPageOpaqueData, GIN_TREE_POSTING 센티넬과 GinIsPostingTree / GinGetNPosting 헤더 필드 접근자, GinItupIsCompressed.
  • src/include/access/gin_private.h — GinState, GinBtreeData, 스캔 키 및 스캔 항목 구조체(GinScanKey, GinScanEntry), GinBtreeStack.
  • src/backend/access/gin/ginutil.c — ginhandler(AM 표면: amgetbitmap = gingetbitmap, amgettuple = NULL), reloptions(fastupdate, gin_pending_list_limit), GinInitMetabuffer.
  • src/backend/access/gin/gininsert.c — gininsert, ginEntryInsert, ginBuildCallback, 빌드 시간 accumulator, GinGetUseFastUpdate의 fast-update 분기.
  • src/backend/access/gin/ginget.c — gingetbitmap, startScan, collectMatchBitmap, keyGetItem, entryGetItem, scanPendingInsert, consistent 함수 드라이버.
  • src/backend/access/gin/ginfast.c — ginHeapTupleFastInsert, ginInsertCleanup, makeSublist, shiftList, writeListPage, 메타페이지 LockPage / ConditionalLockPage 인터락.
  • src/backend/access/gin/ginbtree.c — ginFindLeafPage, ginStepRight, ginFinishSplit, ginInsertValue — 엔트리 트리와 포스팅 트리 양쪽에 공용되는 L&Y 하강/step-right.
  • src/backend/access/gin/ginvacuum.c — ginbulkdelete, ginVacuumPostingTree, ginVacuumEntryPage, ginScanToDelete / ginDeletePage(클린업 잠금 아래 포스팅 트리 페이지 회수).
  • src/backend/access/gin/ginpostinglist.c — ginCompressPostingList, encode_varbyte / decode_varbyte, 델타+varbyte 포스팅 코덱.

논문 및 교과서 챕터

섹션 제목: “논문 및 교과서 챕터”
  • Database System Concepts (Silberschatz, Korth, Sudarshan, 7판), 21장 “Information Retrieval” — GIN이 구현하는 역색인 / 포스팅 목록 모델과 결합 쿼리 교집합(knowledge/research/dbms-general/database-system-concepts.md).
  • O’Neil, P. & Quass, D. (1997). “Improved Query Performance with Variant Indexes.” SIGMOD 1997. 비트맵 / bit-sliced / projection 인덱스와 비트맵 대 목록 공간 트레이드오프(dbms-papers/variant-index.md).
  • Lehman, P. & Yao, S. B. (1981). “Efficient Locking for Concurrent Operations on B-Trees.” ACM TODS 6(4) — GIN의 엔트리 트리와 포스팅 트리가 재사용하는 right-link/step-right 알고리즘(텍스트는 dbms-papers/btree.md; 완전한 편차 분석은 postgres-nbtree.md).
  • Database Internals (Petrov 2019), 2~6장 — B-트리 동시성, 페이지 레이아웃, WAL 배경(knowledge/research/dbms-general/).

형제 문서 (교차 참조 — 메커니즘은 해당 문서 소유, 여기서 중복 없음)

섹션 제목: “형제 문서 (교차 참조 — 메커니즘은 해당 문서 소유, 여기서 중복 없음)”
  • postgres-index-am.md — ginhandler가 채우는 IndexAmRoutine 디스패치 계약(빌드, 삽입, amgetbitmap, bulkdelete, vacuum).
  • postgres-nbtree.md — 표준 Lehman-Yao B-트리: 하강, step-right 복구, GIN 엔트리 트리가 의도적으로 생략하는 페이지 삭제 프로토콜.
  • postgres-full-text-search.md — GIN이 구동하는 tsvector / tsquery opclass와 extractValue / extractQuery / consistent 전략 함수. 텍스트 검색 의미론은 해당 문서에 있다.
  • postgres-buffer-manager.md — GIN의 페이지 잠금과 메타페이지 LockPage 인터락 아래의 버퍼 핀 및 콘텐츠 잠금(LWLock) 래칭.
  • postgres-ssi-predicate-locking.md — collectMatchBitmap / scanPendingInsert가 PredicateLockPage로 공급하는 서술자 잠금 기계.
  • postgres-vacuum.md / postgres-autovacuum.md — ginbulkdelete를 호출하는 VACUUM 드라이버와 펜딩 목록 클린업을 강제하는 autovacuum 트리거.