콘텐츠로 이동
hgryoo · Docs

(KO) PostgreSQL BRIN — 블록 범위 인덱스와 범위 맵

목차

학술적 배경

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

code-analysis/postgres 트리에서 지금까지 다룬 인덱스 패밀리 — B-트리(postgres-nbtree.md), GiST, 해시 — 는 공통된 구조적 전제를 공유한다. 힙 튜플마다 인덱스 항목을 하나씩 만든다는 것이다. 그 덕분에 정확하지만(프로브 결과가 정확히 일치하는 TID만 반환), 비싸다. 수십억 행 테이블의 인덱스는 수억 개 항목을 품고 테이블 크기의 상당 부분을 차지하며, 삽입할 때마다 균형 트리에 새 항목을 끼워 넣는 비용이 발생한다.

created_at 칼럼으로 필터링하는 애널리틱 웨어하우스 팩트 테이블을 생각해 보자. 데이터가 추가 전용(append-mostly)이고 물리적으로 정렬된 상황이라면, 정밀도는 대부분 낭비다. WHERE created_at BETWEEN x AND y 쿼리에 필요한 것은 ‘어떤 행이 일치하는가’가 아니라 ‘어떤 디스크 페이지를 건너뛸 수 있는가’이다. 그 질문만 답하는 인덱스는 수천 배 작아도 된다.

이 아이디어가 블록 단위 요약 인덱스다. 문헌과 다른 엔진에서는 여러 이름으로 부른다. Netezza·Oracle Exadata의 zone map, Moerkotte의 1998년 VLDB 논문에서 나온 Small Materialized Aggregates(SMA), MinMax 인덱스, 그리고 PostgreSQL에서는 BRIN — Block Range INdex다. 이론적 토대는 Database Internals (Petrov 2019; research/dbms-general/database-internals.md)의 정밀 대 근사 보조 구조 구분과, Database System Concepts (Silberschatz 7판 14장 “Indexing”)의 선택도·클러스터링 비용 모델에서 찾을 수 있다.

BRIN의 핵심 교환 관계는 크기 대 정밀도다. BRIN은 그 교환 관계의 극단, 즉 ‘매우 작고 부정확한’ 쪽에 위치한다.

  1. 행이 아닌 페이지 범위를 인덱싱한다. 힙 블록을 고정 크기 그룹, 즉 페이지 범위로 나누고 범위당 요약 하나를 저장한다. 범위당 128 페이지(PostgreSQL 기본값)이면, 약 128 × 226 ≈ 29,000 튜플당 항목 하나다. 수 기가바이트 테이블이라도 인덱스는 킬로바이트 단위다.

  2. 요약은 값 집합이 아닌 범위 경계다. 정렬 가능한 타입은 범위 내 모든 값의 (min, max)를 저장하고, 기하 타입에는 경계 박스(bounding box)를 저장한다. 조회 조건은 경계와 대조해 검사한다. 조건이 [min, max] 안의 어떤 값으로도 만족될 수 없으면 범위 전체를 건너뛴다. 만족될 수도 있으면 재검사를 위해 범위를 반환한다. 이는 블룸 필터와 같은 단방향 논리다. 거짓 음성 없음, 거짓 양성 많음.

  3. 효과는 물리적 상관관계에 전적으로 달려 있다. 인덱스 칼럼이 힙 블록 순서와 잘 상관되어 있으면, 각 범위의 [min, max]가 좁고 이웃 범위와 겹치지 않아 선택적 조건이 거의 모든 범위를 건너뛴다. 칼럼이 뒤섞여 있으면 모든 범위의 [min, max]가 전체 도메인에 걸치고, 스캔은 순차 스캔과 다를 바 없어진다. BRIN은 따라서 범용 기본값이 아닌 전문 도구다. 선택 기준은 pg_stats.correlation이다.

두 번째 구조적 아이디어는 변환 레이어다. 페이지를 건너뛰려면, 각 페이지 범위의 요약을 트리를 내려가지 않고 O(1)에 찾아야 한다. BRIN의 답이 **범위 맵(revmap)**이다. 힙 블록 번호에 대한 단순 산술로 주소를 계산하는 평면 배열이며, 슬롯 i에 페이지 범위 i의 요약 튜플 TID를 담는다. README에 직접 나와 있다. “범위 맵 항목의 크기가 고정되어 있으므로, 주어진 힙 페이지에 대한 범위 맵 항목 주소를 단순 산술로 계산할 수 있다.” revmap은 B-트리에 없는 BRIN 고유 구성 요소이며, 이 문서의 나머지를 조직한다.

두 가지 결과가 즉각 따라온다.

  1. BRIN은 손실 비트맵만 생성할 수 있고 튜플 스트림은 생성할 수 없다. 범위 요약은 일치할 수도 있는 페이지만 식별하므로, 유일하게 정직한 출력은 “이 페이지들을 읽고 재검사하라”다. PostgreSQL AM 레이어는 이를 공식화한다. BRIN은 amgetbitmap을 지원하지만 amgettuple은 지원하지 않는다. 빌드하는 비트맵은 의도적으로 페이지 단위 손실 비트맵이다.

  2. 유지 관리는 비대칭적이고 지연된다. 삽입은 새 값이 [min, max] 밖에 있을 때만 경계를 넓힐 수 있다. 따라서 대부분의 삽입은 아무것도 건드리지 않는다. 테이블 끝에 생기는 새 범위는 미요약 상태로 두고, VACUUM이나 명시적·자동 호출이 summarize_range를 실행할 때까지 스캔에서 “모든 것과 일치할 수 있음”으로 취급해 정확성을 유지한다. 삭제는 요약을 좁히지 않는다. README에서 이는 “정확성 문제가 아니라 최적화 기회”라고 명시한다.

DBMS 공통 설계 패턴

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

블록 요약 인덱스를 구축하는 엔지니어들은 반복되는 설계 선택지로 수렴한다. 이를 먼저 이름 붙혀 두면, PostgreSQL 전용 심볼들이 공유 설계 공간에서 내린 선택으로 읽힌다.

고정 크기 페이지 범위와 계산 기반 변환 맵

섹션 제목: “고정 크기 페이지 범위와 계산 기반 변환 맵”

대부분의 zone-map 류 구조는 저장소 블록을 고정 크기 단위로 묶고 단위당 요약 하나를 유지한다. 고정 크기가 핵심 단순화다. 튜플 t를 포함하는 블록의 요약은 정수 나눗셈 t_block / blocks_per_run으로 찾는다. 검색이 없다. 가변 크기 단위(데이터 밀도에 자동 조정)는 꾸준히 제안되지만 거의 구현되지 않는다. 조회 구조를 다시 도입하기 때문이다. PostgreSQL README의 “Future improvements” 절에 다른 크기 페이지 범위가 미구현 항목으로 명시된다.

단방향 요약: 값 집합이 아닌 범위 경계

섹션 제목: “단방향 요약: 값 집합이 아닌 범위 경계”

요약은 보수적이어야 한다. 일치하지 않는데 일치할 수도 있다고 주장하는 거짓 양성은 허용된다(쓸모없는 페이지 읽기와 재검사 비용만 있다). 일치하는데 일치하지 않는다고 주장하는 거짓 음성은 허용되지 않는다(정확성 버그다). 두 가지 주요 요약 형태가 있다.

  • MinMax — 정렬 가능한 타입의 min과 max를 저장한다. 범위 조건과 동등 조건(<, <=, =, >=, >)을 처리한다.
  • 경계 박스/포함(inclusion) — 기하 또는 집합론적 봉투(box, 범위 타입, inet 등)를 저장한다. 포함 관계와 겹침 조건을 처리한다.

두 형태 모두 합집합이다. 두 범위의 요약을 합치려면 경계를 넓혀 둘 다 포함하면 되며, 이 연산은 결합법칙과 교환법칙을 만족한다. 덕분에 요약을 병렬로 만들고 합칠 수 있다.

손실, 재검사 필수 스캔

섹션 제목: “손실, 재검사 필수 스캔”

구조가 근사적이므로, 스캔 연산자는 반드시 재검사와 짝을 이뤄야 한다. 엔진은 인덱스가 지목한 모든 페이지를 읽고 원래 조건을 각 튜플에 다시 적용한다. 인덱스의 역할은 오직 읽을 페이지 집합을 줄이는 것이다. 블룸 필터 스캔이나 손실 비트맵 인덱스와 정신이 같다. 그래서 이 인덱스는 항상 비트맵 힙 스캔 류 노드에만 공급하고, 인덱스 전용 스캔이나 정렬 스캔에는 공급할 수 없다.

지연 일괄 요약화

섹션 제목: “지연 일괄 요약화”

삽입 시 행 단위 인덱스를 유지하는 것은 요약 인덱스가 피하려는 바로 그 비용이다. 그래서 요약화는 일괄 처리된다. 새로 쓰인 블록 묶음은 유지 관리 패스(VACUUM 상당, 일괄 로드 훅, 또는 백그라운드 트리거)가 묶음을 한 번 스캔해 경계를 계산할 때까지 미요약 상태로 남는다. 그 동안 묶음은 “모든 것과 일치할 수 있음”으로 취급해 쿼리 정확성을 유지한다. 미묘한 동시성 위험이 있다. 유지 관리 패스가 묶음을 스캔하는 동안 새 튜플이 추가될 수 있다. 구현은 이를 포착해야 하며, 전형적 방법은 플레이스홀더/2단계 프로토콜이다.

단일 페이지 원자적 액션을 통한 충돌 안전성

섹션 제목: “단일 페이지 원자적 액션을 통한 충돌 안전성”

디스크 인덱스라면 모든 변형 — 요약화, 제자리 갱신, 이동, 역요약화, 맵 확장 — 이 WAL 로그된 액션이어야 하며 어떤 중단 시점에서도 온디스크 구조가 유효해야 한다. 반복되는 기법은 다중 페이지 변형을 결합 상태가 원자적이어야 하는 페이지들(예: 새 요약 페이지와 그것을 가리키는 맵 슬롯)을 함께 커버하는 WAL 레코드로 분해하고, 고아가 된 중간 상태는 이후 스캔이나 VACUUM이 자가 수정하도록 만드는 것이다.

PostgreSQL의 구현

섹션 제목: “PostgreSQL의 구현”

PostgreSQL은 이 다섯 가지 관행 모두를 src/backend/access/brin/에서 구현한다. 액세스 메서드는 brinhandler가 등록하며, 핵심 기능 프로파일을 광고한다. amgettuple 없음, amgetbitmap 있음, 손실, 다중 칼럼, 요약화다.

// brinhandler — src/backend/access/brin/brin.c
amroutine->amcanorder = false;
amroutine->amcanmulticol = true;
amroutine->amoptionalkey = true;
amroutine->amsearchnulls = true;
amroutine->amstorage = true;          /* opclass picks the stored type */
amroutine->amcanparallel = false;     /* scans are not parallel ... */
amroutine->amcanbuildparallel = true; /* ... but builds are */
amroutine->amsummarizing = true;      /* inserts may trigger autosummarize */
amroutine->amgettuple = NULL;         /* no precise probe — lossy only */
amroutine->amgetbitmap = bringetbitmap;

온디스크 인덱스는 정확히 세 가지 페이지 타입을 가진다. 각 페이지의 special 영역에 태그가 붙어 pg_filedump와 pageinspect가 구분할 수 있다.

// brin_page.h — page-type tags live in the last half-word of every page
#define BRIN_PAGETYPE_META      0xF091   /* block 0 */
#define BRIN_PAGETYPE_REVMAP    0xF092   /* the range map, right after meta */
#define BRIN_PAGETYPE_REGULAR   0xF093   /* summary (and placeholder) tuples */

블록 0은 메타페이지다. revmap은 블록 1부터 연속된 블록들을 차지하며 테이블이 커짐에 따라 확장된다. 나머지는 요약 튜플을 담는 regular 페이지다. 레이아웃과 스캔/삽입 흐름을 아래에 정리했다.

flowchart TD
  subgraph IDX["BRIN index relation (main fork)"]
    META["blk 0: METAPAGE<br/>pagesPerRange, lastRevmapPage, version"]
    RM["blks 1..lastRevmapPage: REVMAP pages<br/>rm_tids[]: one ItemPointer per page range"]
    REG["blks &gt; lastRevmapPage: REGULAR pages<br/>summary tuples (min/max, null flags)"]
  end
  HEAP["Heap: page ranges of pagesPerRange blocks each<br/>range i = heap blocks [i*ppr .. i*ppr+ppr-1]"]
  RM -- "slot i -&gt; TID" --> REG
  REG -- "summarizes" --> HEAP
  HEAP -- "heapBlk / ppr -&gt; revmap slot" --> RM

범위당 요약 튜플

섹션 제목: “범위당 요약 튜플”

연산 클래스가 저장할 내용을 정의한다. 기본 minmax 연산 클래스는 인덱스 칼럼당 두 개의 저장 Datum — min과 max — 을 기여하며, BrinOpcInfo의 oi_nstored = 2로 기술된다.

// brin_minmax_opcinfo — src/backend/access/brin/brin_minmax.c
result = palloc0(MAXALIGN(SizeofBrinOpcInfo(2)) + sizeof(MinmaxOpaque));
result->oi_nstored = 2;          /* min and max */
result->oi_regular_nulls = true; /* AM handles NULL bookkeeping generically */
result->oi_typcache[0] = result->oi_typcache[1] = lookup_type_cache(typoid, 0);

메모리 상의 요약은 칼럼당 BrinValues 하나를 담는 BrinMemTuple이다. 두 범용 NULL 플래그(bv_hasnulls, bv_allnulls)와 연산 클래스 전용 bv_values[]가 전체 요약을 포착한다. 튜플 수준 플래그는 플레이스홀더 튜플과 빈 범위 튜플을 표시한다.

// brin_tuple.h — the deformed (in-memory) summary
typedef struct BrinValues {
    AttrNumber bv_attno;
    bool       bv_hasnulls;   /* any NULL in the range? */
    bool       bv_allnulls;   /* all values NULL in the range? */
    Datum     *bv_values;     /* opclass-stored values (min,max for minmax) */
    void      *bv_mem_value;
} BrinValues;


typedef struct BrinMemTuple {
    bool        bt_placeholder; /* summarization in progress */
    bool        bt_empty_range; /* range provably has no tuples */
    BlockNumber bt_blkno;       /* first heap block of the range */
    /* ... */
    BrinValues  bt_columns[FLEXIBLE_ARRAY_MEMBER];
} BrinMemTuple;

add_values_to_range는 빌드와 삽입이 공유하는 튜플당 누산기다. 칼럼마다 NULL이면 로컬에 기록하거나, 연산 클래스 BRIN_PROCNUM_ADDVALUE(예: brin_minmax_add_value)를 호출해 경계를 넓히고 요약이 변경됐는지 반환한다.

// add_values_to_range — src/backend/access/brin/brin.c (condensed)
bool modified = dtup->bt_empty_range;
for (keyno = 0; keyno < bdesc->bd_tupdesc->natts; keyno++) {
    BrinValues *bval = &dtup->bt_columns[keyno];
    if (bdesc->bd_info[keyno]->oi_regular_nulls && nulls[keyno]) {
        if (!bval->bv_hasnulls) { bval->bv_hasnulls = true; modified = true; }
        continue;
    }
    result = FunctionCall4Coll(addValue, /* BRIN_PROCNUM_ADDVALUE */
                               idxRel->rd_indcollation[keyno],
                               PointerGetDatum(bdesc), PointerGetDatum(bval),
                               values[keyno], nulls[keyno]);
    modified |= DatumGetBool(result);
}
dtup->bt_empty_range = false;
return modified;

minmax addValue는 “값 집합이 아닌 경계” 설계의 핵심이다. 이미 [min, max] 안에 있는 값은 아무것도 바꾸지 않는다(false를 반환해 페이지 쓰기가 없다). 경계 밖에 있는 값만 요약을 넓힌다.

// brin_minmax_add_value — brin_minmax.c (condensed)
if (column->bv_allnulls) {           /* first non-null seen: min = max = newval */
    column->bv_values[0] = datumCopy(newval, attr->attbyval, attr->attlen);
    column->bv_values[1] = datumCopy(newval, attr->attbyval, attr->attlen);
    column->bv_allnulls = false;
    PG_RETURN_BOOL(true);
}
cmpFn = minmax_get_strategy_procinfo(bdesc, attno, attr->atttypid, BTLessStrategyNumber);
if (DatumGetBool(FunctionCall2Coll(cmpFn, colloid, newval, column->bv_values[0]))) {
    column->bv_values[0] = datumCopy(newval, ...); updated = true;   /* new min */
}
cmpFn = minmax_get_strategy_procinfo(bdesc, attno, attr->atttypid, BTGreaterStrategyNumber);
if (DatumGetBool(FunctionCall2Coll(cmpFn, colloid, newval, column->bv_values[1]))) {
    column->bv_values[1] = datumCopy(newval, ...); updated = true;   /* new max */
}
PG_RETURN_BOOL(updated);

범위 맵(revmap)

섹션 제목: “범위 맵(revmap)”

revmap은 연속된 revmap 페이지에 걸쳐 있는 ItemPointerData 평면 배열이다. 두 매크로가 모든 주소 계산을 담당한다. 검색이 없다.

// brin_revmap.c — heap block -> (revmap page, slot) by pure arithmetic
#define HEAPBLK_TO_REVMAP_BLK(pagesPerRange, heapBlk) \
    ((heapBlk / pagesPerRange) / REVMAP_PAGE_MAXITEMS)
#define HEAPBLK_TO_REVMAP_INDEX(pagesPerRange, heapBlk) \
    ((heapBlk / pagesPerRange) % REVMAP_PAGE_MAXITEMS)

heapBlk / pagesPerRange가 범위 번호다. REVMAP_PAGE_MAXITEMS로 나누면 revmap 페이지 번호(+1로 메타페이지 건너뜀)를, 나머지가 그 안에서의 슬롯 번호를 준다. brinGetTupleForHeapBlock은 힙 블록에서 요약 BrinTuple로 변환하는 핵심 루틴이다. revmap 슬롯을 읽고, TID를 따라 regular 페이지로 가고, tup->bt_blkno == heapBlk를 검증한다. 불일치는 동시 repoint를 의미하므로 재시도한다. 자기 참조 루프가 감지되면 손상(corruption)으로 오류를 일으킨다.

// brinGetTupleForHeapBlock — brin_revmap.c (condensed)
heapBlk = (heapBlk / revmap->rm_pagesPerRange) * revmap->rm_pagesPerRange;
mapBlk = revmap_get_blkno(revmap, heapBlk);
if (mapBlk == InvalidBlockNumber) return NULL;   /* range not summarized */
for (;;) {
    /* read revmap slot under SHARE lock */
    iptr = contents->rm_tids + HEAPBLK_TO_REVMAP_INDEX(revmap->rm_pagesPerRange, heapBlk);
    if (!ItemPointerIsValid(iptr)) return NULL;   /* unsummarized */
    if (ItemPointerIsValid(&previptr) && ItemPointerEquals(&previptr, iptr))
        ereport(ERROR, (errcode(ERRCODE_INDEX_CORRUPTED), ...)); /* loop guard */
    previptr = *iptr;
    blk = ItemPointerGetBlockNumber(iptr); *off = ItemPointerGetOffsetNumber(iptr);
    /* fetch the regular page, lock in requested mode */
    if (BRIN_IS_REGULAR_PAGE(page)) {
        tup = (BrinTuple *) PageGetItem(page, lp);
        if (tup->bt_blkno == heapBlk) return tup;   /* found it */
    }
    LockBuffer(*buf, BUFFER_LOCK_UNLOCK);           /* repointed concurrently; retry */
}

슬롯 설정은 대칭적으로 단순하다. brinSetHeapBlockItemptr이 계산된 슬롯에 ItemPointerData를 쓰거나 무효화한다. WAL 재생에서도 같은 루틴을 사용하기 때문에 revmap 갱신은 재생 안전하다.

손실 비트맵 스캔

섹션 제목: “손실 비트맵 스캔”

bringetbitmap이 유일한 스캔 진입점이다. 트리를 내려가지 않는다. 힙 크기를 파악한 뒤 블록 0에서 시작해 pagesPerRange 단계로 revmap을 선형으로 걷는다. 범위마다 모든 페이지를 추가하거나(미요약, 플레이스홀더, 또는 일치) 건너뛴다(consistent 함수가 불일치 판단). 추가된 모든 페이지는 페이지 단위 손실 TIDBitmap에 들어가고, BitmapHeapScan 재검사 노드가 필터링한다.

flowchart TD
  S["bringetbitmap: nblocks = RelationGetNumberOfBlocks(heap)"] --> L{"heapBlk &lt; nblocks?"}
  L -- no --> DONE["return totalpages * 10"]
  L -- yes --> G["brinGetTupleForHeapBlock(heapBlk)"]
  G --> T{"got a summary tuple?"}
  T -- "no (unsummarized)" --> ADD["addrange = true"]
  T -- "yes" --> PH{"placeholder?"}
  PH -- yes --> ADD
  PH -- no --> CK["for each attr with keys:<br/>check null keys, then<br/>opclass consistent()"]
  CK --> M{"all keys consistent?"}
  M -- no --> SKIP["addrange = false"]
  M -- yes --> ADD
  ADD --> E["tbm_add_page for every page in range"]
  SKIP --> N["heapBlk += pagesPerRange"]
  E --> N
  N --> L

일치 판단 로직은 스캔 루프 안에 있다. check_null_keys(IS [NOT] NULL 처리와 all-nulls 단락 평가)와 연산 클래스 BRIN_PROCNUM_CONSISTENT가 핵심 호출이다.

// bringetbitmap — brin.c (condensed): per-range decision
if (!gottuple)                         addrange = true;   /* unsummarized -> keep */
else if (dtup->bt_placeholder)         addrange = true;   /* in-progress -> keep */
else {
    addrange = true;                   /* default keep; no keys => match */
    for (attno = 1; attno <= bdesc->bd_tupdesc->natts; attno++) {
        if (dtup->bt_empty_range)      { addrange = false; break; }   /* provably empty */
        if (bdesc->bd_info[attno-1]->oi_regular_nulls &&
            !check_null_keys(bval, nullkeys[attno-1], nnullkeys[attno-1]))
                                       { addrange = false; break; }
        if (bval->bv_allnulls)         { addrange = false; break; }   /* strict ops */
        add = FunctionCall3Coll(&consistentFn[attno-1], collation,
                                PointerGetDatum(bdesc), PointerGetDatum(bval),
                                PointerGetDatum(keys[attno-1][keyno]));
        addrange = DatumGetBool(add);
        if (!addrange) break;
    }
}
if (addrange)
    for (pageno = heapBlk; pageno <= Min(nblocks, heapBlk+ppr)-1; pageno++)
        tbm_add_page(tbm, pageno);     /* page-granular, lossy */

minmax consistent 함수는 addValue의 쌍이다. 스캔 키 전략을 저장된 경계에 대한 비교로 변환한다. </<=는 min을 검사하고, >/>=는 max를 검사하며, =는 min <= key <= max를 요구한다.

// brin_minmax_consistent — brin_minmax.c (condensed)
switch (key->sk_strategy) {
  case BTLessStrategyNumber: case BTLessEqualStrategyNumber:
    matches = FunctionCall2Coll(finfo, colloid, column->bv_values[0] /*min*/, value);
    break;
  case BTEqualStrategyNumber:        /* min <= key AND max >= key */
    matches = FunctionCall2Coll(/*<=*/finfo, colloid, column->bv_values[0], value);
    if (!DatumGetBool(matches)) break;
    matches = FunctionCall2Coll(/*>=*/finfo2, colloid, column->bv_values[1], value);
    break;
  case BTGreaterEqualStrategyNumber: case BTGreaterStrategyNumber:
    matches = FunctionCall2Coll(finfo, colloid, column->bv_values[1] /*max*/, value);
    break;
}
PG_RETURN_DATUM(matches);

유지 관리: 삽입은 좁히고, VACUUM이 요약화한다

섹션 제목: “유지 관리: 삽입은 좁히고, VACUUM이 요약화한다”

brininsert는 항목을 새로 만들지 않는다. 삽입된 튜플의 범위를 커버하는 요약을 찾는다. 범위가 미요약 상태면 즉시 반환한다. 그렇지 않으면 add_values_to_range로 경계를 넓혀야 하는지 확인하고, 그럴 때만 brin_doupdate를 적용한다. 새 범위는 VACUUM, brin_summarize_new_values(), 또는 autosummarize reloption이 지연 요약화한다. 연산 클래스가 정의한 union은 두 요약을 합친다. 병렬 빌드에서 작업자 빌드 범위를 리더에 통합할 때와, 동시 요약화 중 플레이스홀더를 다시 합칠 때 모두 사용된다. 다음 절에서 이 흐름들을 심볼별로 추적한다.

소스 코드 가이드

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

AM 인터페이스와 디스크립터

섹션 제목: “AM 인터페이스와 디스크립터”

brinhandler(brin.c)는 IndexAmRoutine을 채우고 범용 AM 디스패치의 진입점이다(자세한 계약은 postgres-index-am.md 참조). brin_build_desc는 BrinDesc — 인덱스별 런타임 디스크립터 — 를 구성한다. 각 칼럼의 BRIN_PROCNUM_OPCINFO를 호출해 oi_nstored와 저장 타입을 파악한다. 모든 연산 클래스가 제공해야 하는 네 가지 범용 지원 프로시저 번호는 brin_internal.h에 있다.

// brin_internal.h — generic opclass support procedure numbers
#define BRIN_PROCNUM_OPCINFO     1   /* describe the stored layout */
#define BRIN_PROCNUM_ADDVALUE    2   /* widen a summary with a heap value */
#define BRIN_PROCNUM_CONSISTENT  3   /* does a summary match a scan key? */
#define BRIN_PROCNUM_UNION       4   /* merge two summaries */
#define BRIN_PROCNUM_OPTIONS     5   /* optional */
#define BRIN_LAST_OPTIONAL_PROCNUM 15

brin_build_desc는 인덱스 튜플 디스크립터를 순회하며 bd_totalstored를 누산한다. 결과인 bdesc->bd_info[] 배열(BrinOpcInfo *)이 모든 add/consistent/union 호출에 전달된다.

Revmap: 주소 지정, 조회, 물리적 확장

섹션 제목: “Revmap: 주소 지정, 조회, 물리적 확장”

revmap 액세스 객체 BrinRevmap은 brinRevmapInitialize로 생성된다. 메타페이지에서 pagesPerRange와 lastRevmapPage를 읽어 캐시한다. revmap_get_blkno는 힙 블록을 물리적 revmap 블록으로 변환한다(해당 revmap 페이지가 아직 없으면 InvalidBlockNumber를 반환, 즉 미요약 범위).

// revmap_get_blkno — brin_revmap.c
targetblk = HEAPBLK_TO_REVMAP_BLK(revmap->rm_pagesPerRange, heapBlk) + 1; /* +1 skips meta */
if (targetblk <= revmap->rm_lastRevmapPage)
    return targetblk;
return InvalidBlockNumber;

revmap 페이지가 없는 범위에 요약을 삽입해야 할 때, revmap_extend_and_get_blkno가 루프를 돌며 revmap_physical_extend를 호출한다. 이 루틴이 revmap에서 가장 복잡한 부분이다. 메타페이지를 잠가(revmap 확장 직렬화) 다음 블록을 가져온다. 이미 존재하는 페이지면 읽고, 없으면 릴레이션을 확장한다. 해당 블록이 이미 요약 튜플을 담고 있으면 먼저 퇴거(evacuate)한다. README의 “revmap을 다른 페이지로 확장할 때, 그 페이지에 있는 기존 튜플들을 다른 곳으로 이동한다” 동작이 여기서 구현된다.

// revmap_physical_extend — brin_revmap.c (condensed)
LockBuffer(revmap->rm_metaBuf, BUFFER_LOCK_EXCLUSIVE);  /* serialize extension */
if (metadata->lastRevmapPage != revmap->rm_lastRevmapPage) {
    revmap->rm_lastRevmapPage = metadata->lastRevmapPage; /* stale cache: caller retries */
    LockBuffer(revmap->rm_metaBuf, BUFFER_LOCK_UNLOCK); return;
}
mapBlk = metadata->lastRevmapPage + 1;
/* ... obtain buffer for mapBlk (read or ExtendBufferedRel) ... */
if (brin_start_evacuating_page(irel, buf)) {            /* page holds tuples? */
    LockBuffer(revmap->rm_metaBuf, BUFFER_LOCK_UNLOCK);
    brin_evacuate_page(irel, revmap->rm_pagesPerRange, revmap, buf);
    return;                                             /* caller starts over */
}
START_CRIT_SECTION();
brin_page_init(page, BRIN_PAGETYPE_REVMAP);             /* retype as revmap */
metadata->lastRevmapPage = mapBlk;
/* set metapage pd_lower, MarkBufferDirty, WAL: XLOG_BRIN_REVMAP_EXTEND */
END_CRIT_SECTION();

brinGetTupleForHeapBlock(위 인용)이 읽기 경로이고, brinSetHeapBlockItemptr이 쓰기 경로이며 WAL 재생과 공유한다. brinRevmapDesummarizeRange는 요약화의 역이다. revmap 슬롯과 regular 페이지를 잠근 뒤, PageIndexTupleDeleteNoCompact로 요약 튜플을 삭제하고 슬롯을 무효화하며 XLOG_BRIN_DESUMMARIZE를 WAL 로그한다. regular 페이지가 그 사이에 revmap 페이지로 바뀌었으면 false(재시도)를 반환한다.

// brinRevmapDesummarizeRange — brin_revmap.c (condensed)
START_CRIT_SECTION();
ItemPointerSetInvalid(&invalidIptr);
brinSetHeapBlockItemptr(revmapBuf, revmap->rm_pagesPerRange, heapBlk, invalidIptr);
PageIndexTupleDeleteNoCompact(regPg, regOffset);   /* drop the summary tuple */
MarkBufferDirty(regBuf); MarkBufferDirty(revmapBuf);
/* WAL: xl_brin_desummarize {pagesPerRange, heapBlk, regOffset} */
END_CRIT_SECTION();

페이지 연산: 삽입, 제자리 갱신, 이동, 퇴거

섹션 제목: “페이지 연산: 삽입, 제자리 갱신, 이동, 퇴거”

brin_doinsert(brin_pageops.c)는 새 요약(또는 플레이스홀더, 빈 범위) 튜플을 배치한다. revmap이 충분히 길어지도록 한 뒤(brinRevmapExtend), 삽입 버퍼를 찾고(brin_getinsertbuffer, FSM 참조 후 필요 시 릴레이션 확장), PageAddItem으로 튜플을 쓰고, brinSetHeapBlockItemptr로 revmap 슬롯이 새 튜플을 가리키게 하고, XLOG_BRIN_INSERT를 WAL 로그한다. 이 모두가 하나의 critical section 안에서 일어나 튜플과 그것을 가리키는 슬롯이 함께 내구화된다.

brin_doupdate는 제자리 좁히기 경로다. 저렴한 같은 페이지 덮어쓰기와 비싼 이동 사이의 결정은 brin_can_do_samepage_update에 달려 있다.

// brin_can_do_samepage_update — brin_pageops.c
return ((newsz <= origsz) ||
        PageGetExactFreeSpace(BufferGetPage(buffer)) >= (newsz - origsz));

새 (넓어진) 요약이 맞으면, brin_doupdate는 PageIndexTupleOverwrite로 덮어쓰고 XLOG_BRIN_SAMEPAGE_UPDATE를 로그한다. revmap 슬롯은 바뀌지 않는다. 튜플이 같은 TID에 남기 때문이다. 맞지 않으면, 새 튜플을 다른 페이지에 쓰고 이전 것을 삭제하며 revmap 슬롯을 새 TID로 repoint한다. 이는 새 페이지 + revmap + 이전 페이지를 커버하는 XLOG_BRIN_UPDATE로 로그한다.

// brin_doupdate — brin_pageops.c (the move branch, condensed)
revmapbuf = brinLockRevmapPageForUpdate(revmap, heapBlk);
START_CRIT_SECTION();
PageIndexTupleDeleteNoCompact(oldpage, oldoff);       /* remove old summary */
newoff = PageAddItem(newpage, newtup, newsz, ...);    /* write new one */
ItemPointerSet(&newtid, newblk, newoff);
brinSetHeapBlockItemptr(revmapbuf, pagesPerRange, heapBlk, newtid); /* repoint */
MarkBufferDirty(oldbuf); MarkBufferDirty(newbuf); MarkBufferDirty(revmapbuf);
/* WAL: XLOG_BRIN_UPDATE (+ INIT_PAGE if extended) over all three buffers */
END_CRIT_SECTION();

brin_doupdate는 커밋 전에 이전 튜플이 여전히 정상 항목인지, 페이지가 여전히 regular 페이지인지, 바이트가 origtup 스냅샷과 일치하는지(brin_tuples_equal) 재확인한다. 동시 삽입자가 변경했으면 brin_doupdate가 false를 반환하고, brininsert는 루프를 재시작해 현재 요약을 다시 읽는다. 그렇게 어떤 삽입자의 값도 잃지 않는다.

퇴거 쌍이 revmap 확장을 지원한다. brin_start_evacuating_page는 WAL 비로그 BRIN_EVACUATE_PAGE 플래그를 설정해 br_page_get_freespace가 0을 반환하게 한다(새 튜플이 이 페이지에 배치되지 않는다). brin_evacuate_page는 페이지의 모든 튜플을 brin_doupdate를 재실행해 다른 곳으로 이동하고, 이후 revmap 페이지로 재분류될 수 있도록 해제한다.

스캔: bringetbitmap

섹션 제목: “스캔: bringetbitmap”

brinbeginscan은 BrinOpaque(revmap 액세스 + BrinDesc)를 만든다. bringetbitmap(앞 절)은 스캔 키를 속성별 배열로 전처리하고, IS [NOT] NULL 키(nullkeys)와 일반 키(keys)를 분리한 뒤 revmap 탐색을 실행한다. 각 속성의 BRIN_PROCNUM_CONSISTENT는 지연 조회된다. 연산 클래스가 두 가지 서명을 모두 취할 수 있다. consistentFn.fn_nargs >= 4면 AM이 모든 키를 한 번에 넘기고(FunctionCall4Coll), 그렇지 않으면 하나씩 넘긴다(FunctionCall3Coll). minmax는 3인수 형태를 사용한다. brinrescan은 새 스캔 키를 복사하고, brinendscan은 opaque를 해제한다. 반환값 totalpages * 10은 의도적으로 조잡한 행 추정치다. AM은 페이지 수만 알 뿐 튜플 수는 모른다.

빌드: 직렬, 병렬, 빈 범위

섹션 제목: “빌드: 직렬, 병렬, 빈 범위”

brinbuild는 메타페이지(brin_metapage_init, WAL XLOG_BRIN_CREATE_INDEX)와 BrinBuildState를 초기화한다. 그런 다음 병렬 작업자를 실행하거나(_brin_begin_parallel / _brin_parallel_merge), brinbuildCallback을 공급받아 table_index_build_scan으로 힙을 물리적 순서대로 직렬 스캔한다. 콜백은 실행 중인 범위에 튜플을 누산하고, 힙 블록이 다음 범위로 넘어갈 때마다 form_and_insert_tuple로 플러시한다.

// brinbuildCallback — brin.c (condensed)
while (thisblock > state->bs_currRangeStart + state->bs_pagesPerRange - 1) {
    form_and_insert_tuple(state);                 /* flush completed range */
    state->bs_currRangeStart += state->bs_pagesPerRange;
    brin_memtuple_initialize(state->bs_dtuple, state->bs_bdesc);
}
(void) add_values_to_range(index, state->bs_bdesc, state->bs_dtuple, values, isnull);

스캔 후 brinbuild는 마지막 부분 범위를 플러시하고 brin_fill_empty_ranges를 호출해 스캔이 건너뛴 후행 범위에 빈 범위 요약 튜플을 역채운다. 빈 범위는 정확성-효율성 면에서 중요하다. WHERE nonnull_col IS NULL 같은 조건은 갭을 미요약(= 항상 일치) 상태로 취급하는 대신 빈 범위를 쳐낼 수 있다. 병렬 콜백 brinbuildCallbackParallel은 대신 각 범위를 공유 tuplesort에 흘린다(form_and_spill_tuple). 리더가 작업자별 결과를 합치고 빈 범위를 직접 채운다.

요약화와 플레이스홀더 프로토콜

섹션 제목: “요약화와 플레이스홀더 프로토콜”

brinsummarize는 revmap을 스캔하고 미요약 범위(NULL 슬롯)마다 summarize_range를 호출한다. 이 루틴이 동시성 측면에서 핵심이다. 단순히 힙 범위를 스캔하고 요약을 삽입할 수 없다. 스캔 중에 동시 삽입자가 범위에 튜플을 추가하면 누락될 수 있기 때문이다. 해법이 플레이스홀더 튜플이다.

flowchart TD
  A["summarize_range(heapBlk)"] --> B["brin_form_placeholder_tuple<br/>brin_doinsert: revmap now points to placeholder"]
  B --> C["concurrent inserters update<br/>the placeholder via brininsert"]
  B --> D["table_index_build_range_scan<br/>'any visible' over the heap range"]
  D --> E["loop: brin_form_tuple from scan result"]
  E --> F{"brin_doupdate placeholder -&gt; summary?"}
  F -- success --> G["done: revmap points to real summary"]
  F -- "failed (placeholder changed)" --> H["re-read placeholder<br/>union_tuples into scan result"]
  H --> E

// summarize_range — brin.c (condensed)
phtup = brin_form_placeholder_tuple(state->bs_bdesc, heapBlk, &phsz);
offset = brin_doinsert(state->bs_irel, ppr, state->bs_rmAccess, &phbuf, heapBlk, phtup, phsz);
/* scan the heap range; 'any visible' so in-progress inserts are included */
table_index_build_range_scan(heapRel, state->bs_irel, indexInfo, false, true, false,
                             heapBlk, scanNumBlks, brinbuildCallback, state, NULL);
for (;;) {
    newtup = brin_form_tuple(state->bs_bdesc, heapBlk, state->bs_dtuple, &newsize);
    didupdate = brin_doupdate(..., phbuf, offset, phtup, phsz, newtup, newsize, samepage);
    if (didupdate) break;                         /* placeholder -> summary committed */
    /* someone updated the placeholder concurrently: merge and retry */
    phtup = brinGetTupleForHeapBlock(state->bs_rmAccess, heapBlk, &phbuf, &offset, &phsz, ...);
    union_tuples(state->bs_bdesc, state->bs_dtuple, phtup);
}

union_tuples(그리고 연산 클래스 brin_minmax_union)는 플레이스홀더의 누산 값을 스캔 결과에 합친다. 빈/all-null 경우를 처리한 뒤 칼럼당 BRIN_PROCNUM_UNION을 호출한다. SQL 진입점은 brin_summarize_range / brin_summarize_new_values(후자는 BRIN_ALL_BLOCKRANGES 전달)이며, 둘 다 ShareUpdateExclusiveLock을 취하고 복구 중에는 실행을 거부한다. autosummarize는 brininsert에서 트리거된다. 새 범위의 첫 번째 블록에 첫 번째 튜플이 들어오면, autovacuum에 이전 범위에 대한 AVW_BRINSummarizeRange 작업을 요청한다.

// brininsert — brin.c (autosummarize trigger, condensed)
if (autosummarize && heapBlk > 0 && heapBlk == origHeapBlk &&
    ItemPointerGetOffsetNumber(heaptid) == FirstOffsetNumber) {
    lastPageTuple = brinGetTupleForHeapBlock(revmap, heapBlk - 1, &buf, &off, NULL, BUFFER_LOCK_SHARE);
    if (!lastPageTuple)
        AutoVacuumRequestWork(AVW_BRINSummarizeRange, RelationGetRelid(idxRel), heapBlk - 1);
}

VACUUM과 삭제

섹션 제목: “VACUUM과 삭제”

brinbulkdelete는 사실상 no-op이다. BRIN은 튜플별 TID를 저장하지 않으므로 힙 튜플 제거에 인덱스 정리가 필요 없다(README: 삭제 후 요약 좁히기는 “정확성 문제가 아니라 최적화 기회”). brinvacuumcleanup이 실제 VACUUM 작업을 담당한다. brin_vacuum_scan이 인덱스를 물리적 순서로 걸으며 brin_page_cleanup으로 초기화되지 않은 페이지를 수리하고(확장 도중 충돌로 FSM 공간이 손실된 경우), 그런 다음 brinsummarize가 아직 미요약인 모든 범위를 요약화한다(include_partial = false이므로 부분 꼬리는 제외).

inclusion 연산 클래스(대조)

섹션 제목: “inclusion 연산 클래스(대조)”

inclusion 연산 클래스는 스칼라 [min, max]를 합집합 봉투로 일반화하고 세 값을 저장한다. 합집합, unmergeable 플래그, contains_empty 플래그다(oi_nstored = 3). box/range/inet BRIN을 뒷받침하며, 네 가지 범용 프로시저 외에 PROCNUM_MERGE(11, 필수)와 PROCNUM_MERGEABLE(12)를 추가로 사용한다. 기하 내부는 postgres-gist.md의 영역이다. 여기서 핵심은, 프레임워크 — opcinfo/addValue/consistent/union, revmap, 손실 스캔 — 가 연산 클래스에 무관하다는 것이다. 새 요약 종류는 이 다섯 가지 콜백의 새 구현일 뿐이다.

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

섹션 제목: “위치 힌트 (2026-06-05 기준, REL_18 273fe94)”
심볼파일줄
brinhandlersrc/backend/access/brin/brin.c250
brininsertsrc/backend/access/brin/brin.c344
bringetbitmapsrc/backend/access/brin/brin.c567
brinbuildCallbacksrc/backend/access/brin/brin.c995
brinbuildsrc/backend/access/brin/brin.c1105
brinbulkdeletesrc/backend/access/brin/brin.c1302
brinvacuumcleanupsrc/backend/access/brin/brin.c1317
brin_summarize_rangesrc/backend/access/brin/brin.c1381
brin_desummarize_rangesrc/backend/access/brin/brin.c1491
brin_build_descsrc/backend/access/brin/brin.c1581
summarize_rangesrc/backend/access/brin/brin.c1761
brinsummarizesrc/backend/access/brin/brin.c1887
union_tuplessrc/backend/access/brin/brin.c2031
brin_vacuum_scansrc/backend/access/brin/brin.c2172
add_values_to_rangesrc/backend/access/brin/brin.c2205
check_null_keyssrc/backend/access/brin/brin.c2298
brin_fill_empty_rangessrc/backend/access/brin/brin.c2993
brinRevmapInitializesrc/backend/access/brin/brin_revmap.c70
brinSetHeapBlockItemptrsrc/backend/access/brin/brin_revmap.c155
brinGetTupleForHeapBlocksrc/backend/access/brin/brin_revmap.c194
brinRevmapDesummarizeRangesrc/backend/access/brin/brin_revmap.c323
revmap_get_blknosrc/backend/access/brin/brin_revmap.c442
revmap_physical_extendsrc/backend/access/brin/brin_revmap.c522
HEAPBLK_TO_REVMAP_BLK / _INDEXsrc/backend/access/brin/brin_revmap.c40
brin_doupdatesrc/backend/access/brin/brin_pageops.c53
brin_can_do_samepage_updatesrc/backend/access/brin/brin_pageops.c323
brin_doinsertsrc/backend/access/brin/brin_pageops.c342
brin_metapage_initsrc/backend/access/brin/brin_pageops.c486
brin_start_evacuating_pagesrc/backend/access/brin/brin_pageops.c524
brin_evacuate_pagesrc/backend/access/brin/brin_pageops.c564
brin_getinsertbuffersrc/backend/access/brin/brin_pageops.c689
brin_minmax_opcinfosrc/backend/access/brin/brin_minmax.c34
brin_minmax_add_valuesrc/backend/access/brin/brin_minmax.c64
brin_minmax_consistentsrc/backend/access/brin/brin_minmax.c137
brin_minmax_unionsrc/backend/access/brin/brin_minmax.c208
BrinMetaPageData / RevmapContentssrc/include/access/brin_page.h64 / 78
REVMAP_PAGE_MAXITEMSsrc/include/access/brin_page.h93
BrinValues / BrinMemTuplesrc/include/access/brin_tuple.h29 / 44
BRIN_DEFAULT_PAGES_PER_RANGEsrc/include/access/brin.h39

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

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

REL_18_STABLE 체크아웃 커밋 273fe94(PG 18.x), 소스 트리 /data/hgryoo/references/postgres에서 검증했다.

  • 페이지 타입과 메타페이지 레이아웃 — brin_page.h는 정확히 세 가지 페이지 타입(BRIN_PAGETYPE_META 0xF091, _REVMAP 0xF092, _REGULAR 0xF093), BRIN_METAPAGE_BLKNO 0, BRIN_CURRENT_VERSION 1, 그리고 BrinMetaPageData { brinMagic, brinVersion, pagesPerRange, lastRevmapPage }를 정의한다. 확인됨.
  • Revmap 산술 — brin_revmap.c의 HEAPBLK_TO_REVMAP_BLK와 HEAPBLK_TO_REVMAP_INDEX는 heapBlk, pagesPerRange, REVMAP_PAGE_MAXITEMS만으로 페이지와 슬롯을 계산한다. +1로 메타페이지를 건너뛴다. revmap_get_blkno는 아직 할당되지 않은 revmap 페이지(= 미요약)에는 InvalidBlockNumber를 반환한다. 소스 그대로 확인됨.
  • amgettuple 없음 — brinhandler가 amgettuple = NULL, amgetbitmap = bringetbitmap을 설정한다. amcanparallel = false이지만 amcanbuildparallel = true, amsummarizing = true다. 확인됨.
  • 기본 단위 — brin.h의 BRIN_DEFAULT_PAGES_PER_RANGE는 128이다. 확인됨.
  • minmax 저장 레이아웃 — brin_minmax_opcinfo는 oi_nstored = 2(bv_values[0] = min, [1] = max), oi_regular_nulls = true를 설정한다. inclusion은 oi_nstored = 3이다. 확인됨.
  • 범용 procnum — brin_internal.h에서 BRIN_PROCNUM_OPCINFO=1, ADDVALUE=2, CONSISTENT=3, UNION=4. inclusion은 PROCNUM_MERGE=11, PROCNUM_MERGEABLE=12를 추가한다. 확인됨.
  • 플레이스홀더 프로토콜 — summarize_range가 brin_form_placeholder_tuple을 삽입하고, table_index_build_range_scan(any-visible 모드)으로 스캔한 뒤, 충돌 시 brin_doupdate + union_tuples를 루프한다. 확인됨.
  • WAL 레코드 종류 — XLOG_BRIN_CREATE_INDEX, _INSERT, _SAMEPAGE_UPDATE, _UPDATE, _REVMAP_EXTEND, _DESUMMARIZE가 설명된 루틴에서 발행된다. brin.c, brin_pageops.c, brin_revmap.c에서 확인됨. (WAL 재생 핸들러는 brin_xlog.c에 있으며 여기서는 다루지 않는다.)
  • 동시성 루프 감지 — brinGetTupleForHeapBlock은 반복 사이에 변경되지 않은 revmap TID를 감지하면 ERRCODE_INDEX_CORRUPTED를 발생시킨다. 확인됨.
  • 범위 제한 준수 — 범용 IndexAmRoutine 디스패치는 postgres-index-am.md에 위임됐다. inclusion 연산 클래스의 기하 내부는 postgres-gist.md에 위임됐다. 버퍼/WAL 프리미티브는 이름만 언급했고 재도출하지 않았다.
  • 주의 — 위치 힌트 표의 줄 번호는 273fe94 기준 힌트다. 심볼 이름이 지속적인 기준점이다. inclusion 연산 클래스는 대조 목적으로만 요약했고 완전히 검토하지 않았다.

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

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

  • Moerkotte의 SMA 대 BRIN — 같은 아이디어, 두 가지 세분화. 기초 논문인 Moerkotte 1998(“Small Materialized Aggregates”)은 옵티마이저가 파티션을 쳐내고 데이터를 건드리지 않고도 집계 쿼리에 답할 수 있도록 파티션당 집계(min, max, sum, count)를 유지하자고 제안했다. BRIN은 SMA의 쳐내기 절반을 특화한 것이다. 저장 블록 파티션과 고정 (min, max) 요약을 사용한다. 의도적으로 집계 답변 절반은 포함하지 않는다. BRIN 스캔은 여전히 지목된 모든 페이지를 재검사하며 요약을 쿼리 답변으로 반환하지 않는다. pg_stats 기반 계획이 대신 무엇을 복원하는지와 PostgreSQL이 sum/count를 구체화하지 않음으로써 무엇을 포기하는지 비교하면 계보가 선명해진다. 논문 기준: dbms-papers/(SMA / 데이터 웨어하우스 인덱싱).

  • Zone map과 스토리지 인덱스 (Netezza, Oracle Exadata, Amazon Redshift). 상업적 칼럼 스토어/어플라이언스 엔진들은 같은 구조를 다른 이름으로 제공한다. zone map은 스토리지 레이어가 자동으로 유지하는 존별 min/max이고, Exadata storage index는 스토리지 셀 RAM에 산다. 구조적 대조는 누가 요약을 소유하는가에 있다. 그 시스템들에서 요약은 불투명하고 사용자에게 보이지 않는 스토리지 엔진 산물이다. PostgreSQL에서 BRIN은 CREATE INDEX로 만들고 VACUUM이 유지하는 일급 릴레이션이며, pages_per_range를 조정할 수 있고 brin_summarize_*를 명시적으로 호출할 수 있다. PostgreSQL은 어플라이언스의 불가시성을 pageinspect(brin_page_items, brin_revmap_data)를 통한 검사 가능성과 DBA 제어권으로 맞바꾼다.

  • minmax/inclusion 너머의 인코어 BRIN 연산 클래스. REL_18에는 같은 프레임워크 안의 두 가지 추가 요약 종류가 있다. brin_minmax_multi(brin_minmax_multi.c, oi_nstored = 1)는 단일 [min, max] 대신 직렬화된 값 범위 집합을 저장한다. 몇 개의 이상치가 있거나 클러스터링이 약한 칼럼에서 모든 범위 요약이 전체 도메인으로 붕괴되는 것을 막는다. BRIN의 약점(낮은 상관관계)에 대한 실용적 답이다. brin_bloom(brin_bloom.c)은 범위를 블룸 필터로 요약해 정렬 타입 요구 없이 비상관 칼럼에서 동등 조건 쳐내기를 제공한다. 두 연산 클래스 모두 revmap, 손실 스캔, opcinfo/addValue/consistent/union 계약을 그대로 재사용한다. 여기서 분석한 프레임워크가 연산 클래스에 무관하다는 구체적 증거다.

  • 상관관계 절벽과 자기 조정 범위. BRIN의 효과는 pg_stats.correlation의 계단 함수다. README의 “Future improvements” 절은 다른 크기 페이지 범위를 제안한다. 요약이 느슨해질 곳에서는 세밀하게, 이미 촘촘한 곳에서는 거칠게 자동 조정하는 방식이다. 명시적으로 이를 “범위 맵 자체를 인덱스로 활용해 구현할 수 있을 것”이라고 언급한다. 미실현 연구 영역이다. revmap에 검색을 다시 도입하므로 현재 BRIN을 정의하는 O(1) 변환을 적응성과 맞바꾼다. 쳐내기 효과 대 revmap 조회 비용을 측정하는 프로토타입이 README의 추측을 직접 검증할 것이다.

  • 손실 비트맵 표현 비용. README의 두 번째 “Future improvements” 항목은 TIDBitmap의 손실 페이지 범위 표현(Bitmapset)이 BRIN에 최적이 아니라고 지적한다. BRIN은 항상 연속된 전체 페이지 범위를 내보내기 때문이다. 범위 인식 비트맵 인코딩은 독립된 최적화로, bringetbitmap과 BitmapHeapScan 재검사 사이의 간극을 줄인다. postgres-executor.md의 TIDBitmap 영역이지만 BRIN이 동기 부여 워크로드다.

  • 칼럼 임프린트와 학습된 요약. 칼럼 임프린트(Sidirourgos & Kersten, SIGMOD 2013)나 학습 기반 zone map 같은 연구 구조는 요약을 캐시 라인 단위 비트 벡터나 학습된 조건자로 밀어 넣어 BRIN의 고정 [min, max]가 수용하는 거짓 양성률을 줄인다. 이들은 BRIN이 가장 보수적으로 답하는 열린 질문을 집중 조명한다. 요약 정밀도 얼마가 얼마만큼의 인덱스 크기와 유지 관리 비용을 정당화하는가 — 1절에서 이름 붙인 크기 대 정밀도 교환 관계가 이제 단일 고정 지점이 아닌 살아있는 설계 축이다.

출처

섹션 제목: “출처”

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

섹션 제목: “인트리 README 및 소스 파일 (REL_18_STABLE, 커밋 273fe94)”
  • src/backend/access/brin/README — 설계 문서. 범위당 요약 모델, 범위 맵과 고정 산술 주소 지정, 확장 시 퇴거 규칙, 요약화와 플레이스홀더/동시 삽입 프로토콜, “삭제는 요약을 좁히지 않는다는 것은 최적화 기회일 뿐” 주석, “Future improvements” 목록(다른 크기 페이지 범위, TIDBitmap 표현).
  • src/backend/access/brin/brin.c — brinhandler, brininsert(autosummarize 트리거 포함), bringetbitmap, brinbuild / brinbuildCallback / brinbuildCallbackParallel, brin_build_desc, summarize_range / brinsummarize, union_tuples, add_values_to_range, check_null_keys, brin_fill_empty_ranges, brinbulkdelete / brinvacuumcleanup / brin_vacuum_scan, SQL 진입점 brin_summarize_range / brin_summarize_new_values / brin_desummarize_range.
  • src/backend/access/brin/brin_revmap.c — brinRevmapInitialize, HEAPBLK_TO_REVMAP_BLK / HEAPBLK_TO_REVMAP_INDEX, revmap_get_blkno, revmap_physical_extend, brinGetTupleForHeapBlock(루프 감지 읽기 경로), brinSetHeapBlockItemptr(WAL 재생과 공유), brinRevmapDesummarizeRange.
  • src/backend/access/brin/brin_pageops.c — brin_doinsert, brin_doupdate(같은 페이지 덮어쓰기 대 이동 후 repoint 분기), brin_can_do_samepage_update, brin_metapage_init, brin_start_evacuating_page / brin_evacuate_page, brin_getinsertbuffer.
  • src/backend/access/brin/brin_minmax.c — 기본 연산 클래스: brin_minmax_opcinfo(oi_nstored = 2), brin_minmax_add_value, brin_minmax_consistent, brin_minmax_union.
  • src/backend/access/brin/brin_inclusion.c — inclusion 연산 클래스(oi_nstored = 3, PROCNUM_MERGE/MERGEABLE), 대조 참조.
  • src/backend/access/brin/brin_minmax_multi.c, brin_bloom.c — 6절에서 언급한 추가 인코어 연산 클래스.
  • src/include/access/brin_page.h — BRIN_PAGETYPE_{META,REVMAP,REGULAR}, BrinMetaPageData, RevmapContents, REVMAP_PAGE_MAXITEMS, BRIN_METAPAGE_BLKNO, BRIN_CURRENT_VERSION.
  • src/include/access/brin_tuple.h — BrinValues, BrinMemTuple, BrinTuple, 플레이스홀더/빈 범위 플래그.
  • src/include/access/brin_internal.h — BrinDesc, BrinOpcInfo, 범용 BRIN_PROCNUM_* 번호.
  • src/include/access/brin.h — BrinStatsData, reloption, BRIN_DEFAULT_PAGES_PER_RANGE(128).

논문 및 교과서 장

섹션 제목: “논문 및 교과서 장”
  • Moerkotte, G. (1998). “Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing.” VLDB 1998, 476-487. BRIN의 개념적 선조. 파티션당 요약 쳐내기. knowledge/research/dbms-papers/에 기준 문서 있음.
  • Sidirourgos, L. & Kersten, M. (2013). “Column Imprints: A Secondary Index Structure.” SIGMOD 2013, 893-904. 더 세밀한 비트 벡터 요약. 같은 거짓 양성 쳐내기 계열의 연구 프론티어. 6절에서 인용.
  • Database Internals (Petrov 2019) — 정밀 대 근사 보조 구조 구분과 비트맵/재검사 프레이밍 (knowledge/research/dbms-general/database-internals.md).
  • Database System Concepts (Silberschatz, Korth, Sudarshan, 7판), 14장 “Indexing” — 페이지 건너뛰기 스캔이 B-트리 프로브보다 유리해지는 선택도·클러스터링 비용 모델 (knowledge/research/dbms-general/).

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

섹션 제목: “형제 문서 (교차 참조 — 메커니즘은 해당 문서 소유, 여기서 중복하지 않음)”
  • postgres-index-am.md — brinhandler가 채우는 범용 IndexAmRoutine 디스패치 계약(amgetbitmap, amsummarizing, 병렬 빌드 플래그).
  • postgres-gist.md — BRIN inclusion 연산 클래스가 재사용하는 inclusion 스타일 기하 연산 클래스 내부와 경계 박스 기계장치.
  • postgres-buffer-manager.md — revmap 및 regular 페이지 변형이 래치하는 버퍼 핀과 콘텐츠 락.
  • postgres-vacuum.md / postgres-autovacuum.md — brinvacuumcleanup/brinsummarize를 호출하는 VACUUM 패스, AVW_BRINSummarizeRange autosummarize 요청을 처리하는 autovacuum 작업자.
  • postgres-wal-records-rmgr.md — RM_BRIN_ID 리소스 매니저와 재생 핸들러가 brin_xlog.c에 있는 XLOG_BRIN_* 레코드 종류.
  • postgres-architecture-overview.md — Axis 4(플러그인 가능 액세스 메서드). BRIN은 요약화, 손실 비트맵 전용 인덱스 AM으로 배치된다.