콘텐츠로 이동
hgryoo · Docs

(KO) PostgreSQL 해시 인덱스 — 선형 해싱, 버킷, 오버플로 페이지

목차

학술적 배경

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

해시 인덱스가 답하는 질문은 하나다 — “이 키를 가진 행은 어느 것인가?” B-트리와 달리 범위 스캔, 부등호, ORDER BY, 접두사 매칭에는 쓸 수 없다. 해싱이 키의 순서를 의도적으로 파괴하기 때문이다. 인접한 두 값도 임의로 떨어진 버킷에 배치된다. 그 대신 교과서가 약속하는 O(1) 등치 조회를 얻는다. Database System Concepts (Silberschatz 7판 14장 “Indexing”; research/dbms-general/ 수록)는 이 이상을 이렇게 정식화한다. 해시 함수 h(K)가 키를 B개 버킷 중 하나로 매핑하면, 조회는 h(K)를 계산해 그 버킷으로 직행하고 그 안의 소수 항목만 스캔한다. 루트-리프 하강도, log_F N 페이지 읽기도 없다. 비용 모델은 버킷 하나 접근에 버킷이 한 페이지를 초과할 때의 오버플로 체인 탐색을 더한 것이다.

디스크 해시 테이블에서 어려운 부분은 조회가 아니라 성장이다. N행에 맞게 크기를 정한 정적 해시 테이블은 10N행이 되면 처참하게 무너진다. 버킷마다 긴 오버플로 체인이 생겨 O(1) 약속이 O(체인 길이)로 붕괴한다. 단순한 해결책은 두 배 크기 테이블로 전체 재해싱인데, 메모리에서는 괜찮지만 디스크에서는 재앙이다. 인덱스 전체를 한 번에 다시 쓰면서 파일을 두 배로 늘리고 모든 동시 독자·작성자를 차단한다. 이 문제를 해결하는 분야가 동적 해싱이며, PostgreSQL이 채택한 구체적 변형이 **선형 해싱(linear hashing)**이다. Witold Litwin(1980)이 고안하고, src/backend/access/hash/README 맨 위에 직계 참조로 명시된 Margo Seltzer & Ozan Yigit, “A New Hashing Package for UNIX”, USENIX Winter 1991이 UNIX용으로 대중화했다(postgres-paper-bibliography.md 수록; 동일 계보가 PostgreSQL의 인메모리 dynahash.c에도 흐른다).

선형 해싱의 통찰은 테이블을 한 번에 버킷 하나씩 증가시키되, 어느 버킷이 실제로 넘쳤는지와 무관하게 고정된 라운드로빈 순서로 분할한다는 것이다. 두 마스크를 유지한다. lowmask는 현재 레벨 2^L개 버킷을, highmask = 2*lowmask + 1은 다음 레벨을 커버한다. 키를 주소 지정하려면 먼저 b = h(K) & highmask를 계산하고, b가 현재 존재하는 최고 버킷을 초과하면 b = h(K) & lowmask로 되돌아간다. 분할 포인터(PostgreSQL에서는 hashm_maxbucket)가 라운드로빈 확장이 어디까지 진행됐는지 표시한다. 테이블이 너무 가득 찼다고 판단되면, 분할 포인터 위치의 버킷이 분할된다. 그 버킷의 항목을 넓어진 highmask 아래서 재해싱해 기존 버킷과 새 고번호 버킷 사이에 분배한다. 분할 포인터는 하나 전진한다. 결정적으로 분할되는 버킷은 넘친 버킷이 아니다. 오버플로 페이지가 국소적 핫스팟을 흡수하는 동안, 전역 분할 포인터가 고르게 전진해 전체 레벨에 걸쳐 평균적으로 테이블이 부드럽게 두 배가 된다.

두 가지 구조적 결과가 이 문서의 나머지를 조직한다.

  1. 버킷에는 오버플로 페이지가 필요하다. 분할은 전역 부하율이 임계값을 넘을 때만 일어나고, 특정 버킷이 가득 찼을 때 일어나지 않는다. 따라서 특정 버킷은 한 페이지에 맞지 않는 튜플을 일시적으로 받을 수 있다. 그 튜플들은 primary 페이지에 체인된 오버플로 페이지로 흘러넘친다. 오버플로는 분할 일정을 라운드로빈으로 유지하게 해주는 압력 배출 밸브다.

  2. 버킷-블록 매핑은 저장이 아니라 계산으로 얻어야 한다. 단순한 구현은 버킷 번호를 디스크 블록으로 매핑하는 디렉터리 배열을 유지할 것이다. 선형 해싱은 디렉터리를 피한다. 버킷이 규율 잡힌 2의 거듭제곱 분할점 그룹으로 할당되므로, 버킷의 물리 블록을 버킷 번호와 소규모 spares[] 배열로 계산할 수 있다. 이것이 정확히 PostgreSQL의 BUCKET_TO_BLKNO 매크로가 하는 일이다.

동반하는 주제는 동시성과 충돌 안전성이다. 교과서의 해시 테이블은 단일 스레드이고 인메모리다. 프로덕션 인덱스는 많은 백엔드가 동시에 읽고 삽입하는 동안 분할과 가비지 컬렉션도 실행되어야 하고, 분할 중 충돌에서도 살아남아야 한다. PostgreSQL의 답은 버퍼 매니저의 세 가지 기본 요소 — 콘텐츠 락(content lock), 핀(pin), 클린업 락(cleanup lock)(각각 postgres-buffer-manager.md 참조) — 에 전적으로 의존하고, 모든 다중 페이지 변경을 단일 페이지 단위 원자적 WAL 액션으로 분해하는 것이다. B-트리가 사용하는(postgres-nbtree.md) 규율과 같지만, 버킷 체인 형태에 맞게 적용된다.

DBMS 공통 설계 패턴

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

디스크 해시 인덱스를 구축하는 엔지니어들은 반복되는 관행으로 수렴한다. 이 관행들을 먼저 이름 붙여 두면, PostgreSQL 심볼들이 공유 설계 공간 안에서 내린 선택으로 읽힌다.

디렉터리 해싱 대 디렉터리 없는 선형 해싱

섹션 제목: “디렉터리 해싱 대 디렉터리 없는 선형 해싱”

동적 온디스크 해싱의 두 주요 계보가 있다.

  • 확장 가능 해싱(Extendible hashing) (Fagin et al. 1979)은 명시적 디렉터리를 유지한다. 해시의 상위 d비트로 인덱싱되는 2^d 포인터 배열이다. 버킷이 넘치면 그 버킷만 분할하고, 디렉터리는 두 배가 되거나(d가 커져야 할 때) 두 슬롯을 다시 가리키기만 한다. 조회는 항상 정확히 두 번의 I/O(디렉터리 + 버킷)지만, 디렉터리 자체가 커질 수 있고 공유 가변 구조다.
  • 선형 해싱 (Litwin 1980; Seltzer-Yigit 1991)은 디렉터리를 유지하지 않는다. 버킷 주소는 해시, 두 마스크, 분할 포인터로 산술 계산한다. 성장은 온디맨드가 아니라 라운드로빈이다. 이 설계는 가끔의 추가 오버플로 체인 홉을 감수하는 대신, 그 자체가 경합과 메모리 핫스팟이 될 중앙집중식 디렉터리를 없앤다.

PostgreSQL은 디렉터리 없는 선형 해싱을 선택했다. 그래서 메타페이지에 포인터 테이블 대신 highmask, lowmask, maxbucket, spares[] 배열이 있다.

flowchart TD
  K["키 K"] --> H["h = hash(K)<br/>32비트 해시 코드"]
  H --> HM["b = h &amp; highmask"]
  HM --> CMP{"b &gt; maxbucket?"}
  CMP -->|yes| LM["b = h &amp; lowmask<br/>아직 분할 안 된 버킷"]
  CMP -->|no| USE["버킷 b 사용"]
  LM --> USE
  USE --> BLK["BUCKET_TO_BLKNO(metap, b)<br/>물리 블록 계산"]
  BLK --> PBP["primary 버킷 페이지"]
  PBP --> OVF["오버플로 페이지 체인<br/>(이중 연결)"]

버킷 체인 — primary 페이지와 오버플로

섹션 제목: “버킷 체인 — primary 페이지와 오버플로”

거의 모든 디스크 해시 인덱스는 버킷을 페이지 연결 리스트로 표현한다. 버킷의 영구 홈인 페이지 하나에 버킷 증가에 따라 추가되는 오버플로 페이지들이 이어진다. PostgreSQL은 이중 연결 체인(전방 hasho_nextblkno, 후방 hasho_prevblkno)을 사용한다. 가비지 컬렉션이 해제된 오버플로 페이지를 체인 중간에서 양쪽 이웃을 고쳐 제거할 수 있기 때문이다. 페이지 내 항목은 해시 코드 순으로 정렬되어 이진 탐색이 가능하다. 단, 버킷의 여러 페이지에 걸친 순서는 유지되지 않는다.

분할점 그룹을 통한 계산 주소 지정

섹션 제목: “분할점 그룹을 통한 계산 주소 지정”

디렉터리 없이 버킷을 증분 할당하려면, 선형 해싱 구현이 버킷 페이지를 2의 거듭제곱 그룹으로 할당한다. PostgreSQL은 각 그룹을 *분할점(splitpoint)*이라 부른다. 분할점 s는 2^(s-1)개의 새 버킷을 추가하므로 그룹당 테이블이 두 배가 된다. 한 번에 거대한 슬랩을 할당하지 않으려고 그룹 >= 10은 네 개의 동일한 *단계(phase)*로 나뉜다. 분할점별 배열(spares[])은 각 분할점의 버킷 페이지 이전에 할당된 오버플로 페이지 수를 기록한다. 이것이 버킷 번호를 블록 번호로 산술 변환하는 데 필요한 유일한 상태다.

락 매니저 대신 페이지 수준 잠금

섹션 제목: “락 매니저 대신 페이지 수준 잠금”

B-트리와 해시 인덱스는 같은 동시성 문제에 직면하고 같은 도구를 사용한다. 개별 페이지 읽기/쓰기에는 수명이 짧은 버퍼 콘텐츠 락, 인플라이트 커서 아래서 페이지가 재조직되는 것을 방지하는 장기 버퍼 핀, 페이지나 버킷을 전면 재조직하는 권한인 클린업 락(다른 누구도 페이지를 핀하지 않은 채 잡는 배타적 콘텐츠 락)을 사용한다. 이 중 어느 것도 heavyweight 락 매니저(postgres-lock-manager.md)를 건드리지 않는다. 해시 AM의 구체적 관행은 primary 버킷 페이지의 클린업 락 = 전체 버킷 재조직 권한, 스캔은 전체 생애 동안 primary 버킷 페이지 핀 보유다.

다중 페이지 변경을 원자적 WAL 액션으로 분해

섹션 제목: “다중 페이지 변경을 원자적 WAL 액션으로 분해”

분할은 메타페이지, 기존 버킷 페이지들, 새 버킷 페이지들을 건드린다. 오버플로 해제는 대상 페이지, 양쪽 이웃, 비트맵 페이지, 메타페이지를 건드린다. 단일 WAL 레코드는 무제한의 페이지를 커버할 수 없다(XLR_MAX_BLOCK_ID가 32로 제한). 공유 규율은 각 논리적 연산을 단일 레코드 원자적 단계 시퀀스로 분해하는 것이다. 각 단계는 인덱스를 유효하고 검색 가능한 상태로 남기며, 복구 규칙은 “어떤 중간 상태도 합법적”이다. 따라서 단계 사이의 충돌은 다음 삽입, 분할, VACUUM이 지연 방식으로 복구한다.

PostgreSQL의 구현

섹션 제목: “PostgreSQL의 구현”

PostgreSQL 해시 AM은 src/backend/access/hash/에 있다. hashhandler()가 IndexAmRoutine을 채운다(AM 디스패치 계약은 postgres-index-am.md 참조). 핵심 메커니즘은 다섯 파일에 있다. hashpage.c(메타페이지, 버킷 할당, 분할), hashinsert.c(삽입), hashsearch.c(스캔), hashovfl.c(오버플로 페이지 생애 주기와 압착), hashutil.c(주소 산술). 튜플이 경험하는 순서로 설계를 살펴본다. 주소 지정, 검색, 삽입, 분할, 오버플로와 가비지 컬렉션 순이다.

페이지 타입과 special space

섹션 제목: “페이지 타입과 special space”

물리 페이지 종류는 네 가지다. 모든 페이지 끝의 HashPageOpaqueData special space에 있는 hasho_flag 비트로 구분한다.

// HashPageOpaqueData — src/include/access/hash.h
typedef struct HashPageOpaqueData
{
  BlockNumber hasho_prevblkno;  /* prev page in chain, OR maxbucket-as-of-split */
  BlockNumber hasho_nextblkno;  /* next page in bucket chain */
  Bucket    hasho_bucket;    /* bucket number this page belongs to */
  uint16    hasho_flag;      /* LH_* page type + transient flag bits */
  uint16    hasho_page_id;    /* 0xFF80, identifies hash pages to pg_filedump */
} HashPageOpaqueData;


#define LH_OVERFLOW_PAGE    (1 << 0)
#define LH_BUCKET_PAGE      (1 << 1)
#define LH_BITMAP_PAGE      (1 << 2)
#define LH_META_PAGE      (1 << 3)
#define LH_BUCKET_BEING_POPULATED  (1 << 4)
#define LH_BUCKET_BEING_SPLIT    (1 << 5)
#define LH_BUCKET_NEEDS_SPLIT_CLEANUP  (1 << 6)
#define LH_PAGE_HAS_DEAD_TUPLES    (1 << 7)

하위 4비트가 페이지 타입(블록 0은 항상 LH_META_PAGE), 상위 4비트가 분할과 클린업 중 사용되는 일시적 버킷 상태 플래그다. hasho_prevblkno의 이중 의미에 주목하라. 오버플로 페이지에서는 실제 이전 블록이지만, primary 버킷 페이지에서는 해당 버킷이 마지막으로 분할된 시점의 hashm_maxbucket 값을 저장한다. 이 오버로딩이 메타페이지 캐시(아래 참조)의 핵심이다. primary 페이지의 “이전 블록”은 어차피 항상 무효이므로 비용이 없다.

메타페이지와 계산 주소 지정

섹션 제목: “메타페이지와 계산 주소 지정”

블록 0이 메타페이지다. 테이블의 live 기하학을 저장한다.

// HashMetaPageData (excerpt) — src/include/access/hash.h
typedef struct HashMetaPageData
{
  double    hashm_ntuples;    /* tuples stored, drives split decision */
  uint16    hashm_ffactor;    /* target fill factor (tuples per bucket) */
  uint32    hashm_maxbucket;  /* ID of highest live bucket (= split pointer) */
  uint32    hashm_highmask;    /* mask into the whole current table */
  uint32    hashm_lowmask;    /* mask into the lower half */
  uint32    hashm_ovflpoint;  /* current splitpoint for overflow allocation */
  uint32    hashm_firstfree;  /* lowest-numbered free overflow bit */
  uint32    hashm_nmaps;    /* number of bitmap pages */
  uint32    hashm_spares[HASH_MAX_SPLITPOINTS];  /* ovfl pages before each splitpoint */
  BlockNumber hashm_mapp[HASH_MAX_BITMAPS];    /* blocks of the bitmap pages */
} HashMetaPageData;

키의 버킷 주소는 디렉터리에서 조회하는 게 아니라 계산으로 얻는다. 두 함수가 산술을 담당한다. _hash_hashkey2bucket이 선형 해싱 마스크를 적용한다.

// _hash_hashkey2bucket — src/backend/access/hash/hashutil.c
Bucket
_hash_hashkey2bucket(uint32 hashkey, uint32 maxbucket,
           uint32 highmask, uint32 lowmask)
{
  Bucket    bucket;


  bucket = hashkey & highmask;
  if (bucket > maxbucket)
    bucket = bucket & lowmask;  /* this bucket not yet split off */


  return bucket;
}

그리고 BUCKET_TO_BLKNO가 버킷 번호를 물리 블록으로 변환한다. 해당 버킷의 분할점 그룹 앞에 있는 오버플로 페이지 수를 더한다. spares[] 항목이 디렉터리 없는 동작을 가능하게 하는 요소다.

// BUCKET_TO_BLKNO — src/include/access/hash.h
#define BUCKET_TO_BLKNO(metap,B) \
  ((BlockNumber) ((B) + ((B) ? (metap)->hashm_spares[_hash_spareindex((B)+1)-1] : 0)) + 1)

+ 1은 블록 0의 메타페이지를 보정한다. 버킷 0과 1은 항상 블록 1과 2에 있다. _hash_spareindex는 버킷 수를 전역 분할점 단계로 매핑하고, _hash_get_totalbuckets는 그 역을 수행한다. 이 둘이 README에 설명된 “그룹 < 10은 단일 단계, 그룹 >= 10은 4단계” 할당 일정을 구현한다.

// _hash_spareindex — src/backend/access/hash/hashutil.c
uint32
_hash_spareindex(uint32 num_bucket)
{
  uint32    splitpoint_group = pg_ceil_log2_32(num_bucket);


  if (splitpoint_group < HASH_SPLITPOINT_GROUPS_WITH_ONE_PHASE)
    return splitpoint_group;
  /* ... groups >= 10 are split into 4 equal phases ... */
  return splitpoint_phases;
}

메타페이지 캐싱으로 경합 회피

섹션 제목: “메타페이지 캐싱으로 경합 회피”

스캔과 삽입 모두 버킷을 찾으려면 maxbucket/highmask/lowmask가 필요하다. 매 연산마다 메타페이지를 잠그면 블록 0이 심각한 핫스팟이 된다. 그래서 각 백엔드는 _hash_getcachedmetap으로 relcache(rd_amcache)에 메타페이지 사본을 캐시한다. 위험은 오래된 캐시다. 동시 분할이 캐시가 채워진 후 대상 키를 새 버킷으로 이동했을 수 있다. 검증 트릭은 오버로드된 hasho_prevblkno를 이용한다. 후보 primary 버킷 페이지를 잠근 후 페이지에 저장된 maxbucket-as-of-last-split을 캐시된 maxbucket과 비교한다. 페이지의 값이 더 크면 캐시를 만든 후 버킷이 분할된 것이므로 락을 해제하고 캐시를 새로 고친 후 재시도한다.

// _hash_getbucketbuf_from_hashkey — src/backend/access/hash/hashpage.c
for (;;)
{
  bucket = _hash_hashkey2bucket(hashkey, metap->hashm_maxbucket,
                  metap->hashm_highmask, metap->hashm_lowmask);
  blkno = BUCKET_TO_BLKNO(metap, bucket);
  buf = _hash_getbuf(rel, blkno, access, LH_BUCKET_PAGE);
  opaque = HashPageGetOpaque(BufferGetPage(buf));


  /* If this bucket hasn't been split since our cache, we're done. */
  if (opaque->hasho_prevblkno <= metap->hashm_maxbucket)
    break;


  /* Stale: drop lock, force-refresh the cached metapage, and retry. */
  _hash_relbuf(rel, buf);
  metap = _hash_getcachedmetap(rel, &metabuf, true);
}

재시도 비용이 낮은 이유를 README가 설명한다. 어떤 버킷도 수십 번 이상 분할될 수 없지만(전체 버킷 수는 2^32로 제한), 접근은 무제한이므로 안정 상태에서는 재시도가 거의 일어나지 않는다.

버킷 스캔

섹션 제목: “버킷 스캔”

해시 스캔은 단일 컬럼 등치(HTEqualStrategyNumber)만 지원하며 전체 인덱스 스캔은 거부한다. _hash_first가 해시 키를 계산하고 primary 버킷 페이지를 찾아 스캔 전체 동안 핀으로 고정한다. 성능과 동시성의 핵심은 한 번의 페이지 읽기에서 모든 일치 튜플을 백엔드 로컬 스토리지(so->currPos.items[])에 담은 뒤, 페이지 콘텐츠 락을 해제하고 인덱스 락 없이 힙 TID를 처리한다는 것이다. 핀은 primary 버킷 페이지에만 유지된다. 이 덕분에 동시 삽입이 스캔이 재위치를 찾을 필요 없이 같은 페이지에서 진행될 수 있다.

flowchart TD
  START["_hash_first(scan, dir)"] --> HK["hashkey = hash(scankey)"]
  HK --> GBB["_hash_getbucketbuf_from_hashkey<br/>pin + lock primary 버킷 페이지"]
  GBB --> POP{"버킷이 분할에 의해<br/>채워지는 중?"}
  POP -->|yes| OLD["기존(분할) 버킷도 핀<br/>set hashso_buc_populated"]
  POP -->|no| RP["_hash_readpage"]
  OLD --> RP
  RP --> BIN["_hash_binsearch(page, hashkey)<br/>첫 번째 매칭 위치 결정"]
  BIN --> LOAD["_hash_load_qualified_items<br/>매칭 항목을 currPos.items[]에 복사"]
  LOAD --> REL["콘텐츠 락 해제<br/>(primary 버킷 핀은 유지)"]
  REL --> NEXT{"currPos에<br/>남은 항목?"}
  NEXT -->|yes| RET["xs_heaptid 반환"]
  NEXT -->|no, fwd| STEP["_hash_next: hasho_nextblkno<br/>오버플로 페이지로 전진"]
  STEP --> RP

분할에 의해 채워지는 중인 버킷에서 스캔이 시작되면, 분할된 기존 버킷도 스캔해야 하며 이미 복사된 튜플(INDEX_MOVED_BY_SPLIT 마킹)은 건너뛴다. _hash_load_qualified_items가 이 건너뛰기와 죽은 튜플 건너뛰기를 모두 처리한다.

// _hash_load_qualified_items (forward) — src/backend/access/hash/hashsearch.c
if ((so->hashso_buc_populated && !so->hashso_buc_split &&
   (itup->t_info & INDEX_MOVED_BY_SPLIT_MASK)) ||
  (scan->ignore_killed_tuples &&
   (ItemIdIsDead(PageGetItemId(page, offnum)))))
{
  offnum = OffsetNumberNext(offnum);  /* skip moved-by-split / dead */
  continue;
}
if (so->hashso_sk_hash == _hash_get_indextuple_hashkey(itup) &&
  _hash_checkqual(scan, itup))
{
  _hash_saveitem(so, itemIndex, offnum, itup);  /* qualified match */
  itemIndex++;
}
else
  break;  /* page is hash-sorted, so first miss ends the run */

항목이 페이지 내에서 해시 순으로 정렬되므로 이진 탐색이 첫 번째 가능한 매칭으로 점프하고 첫 번째 불일치에서 루프가 종료된다. 전체 페이지 스캔이 불필요하다.

튜플 삽입

섹션 제목: “튜플 삽입”

_hash_doinsert는 인덱스 튜플에서 미리 계산된 해시 키를 추출하고 primary 버킷 페이지를 찾아 쓰기 락을 건 후, 여유 공간이 있는 페이지를 찾아 버킷 체인을 탐색한다. 세 가지 주목할 만한 동작이 있다. (1) 버킷이 분할 중이면 먼저 분할을 완료하려 시도한다. 공간이 생겨 불필요한 오버플로 페이지를 피할 수 있기 때문이다. (2) 가득 찬 페이지에 죽은(LP_DEAD-힌트) 튜플이 있으면 오버플로에 의존하기 전에 그 페이지 하나를 진공한다. (3) 튜플을 배치한 후에야 메타페이지를 잠가 튜플 수를 증가시키고 분할 여부를 결정한다.

// _hash_doinsert (chain walk) — src/backend/access/hash/hashinsert.c
while (PageGetFreeSpace(page) < itemsz)
{
  BlockNumber nextblkno;


  /* try reclaiming dead tuples on this page before overflowing */
  if (H_HAS_DEAD_TUPLES(pageopaque) && IsBufferCleanupOK(buf))
  {
    _hash_vacuum_one_page(rel, heapRel, metabuf, buf);
    if (PageGetFreeSpace(page) >= itemsz)
      break;
  }


  nextblkno = pageopaque->hasho_nextblkno;
  if (BlockNumberIsValid(nextblkno))
  {
    /* step to existing overflow page (drop lock; keep pin on primary) */
    if (buf != bucket_buf)
      _hash_relbuf(rel, buf);
    else
      LockBuffer(buf, BUFFER_LOCK_UNLOCK);
    buf = _hash_getbuf(rel, nextblkno, HASH_WRITE, LH_OVERFLOW_PAGE);
  }
  else
  {
    /* end of chain: allocate and link a fresh overflow page */
    LockBuffer(buf, BUFFER_LOCK_UNLOCK);
    buf = _hash_addovflpage(rel, metabuf, buf, (buf == bucket_buf));
  }
  page = BufferGetPage(buf);
  pageopaque = HashPageGetOpaque(page);
}

실제 배치는 _hash_pgaddtup이 이진 탐색으로 삽입 위치를 찾아 해시 코드 순서를 유지한다. 카운트 증가와 분할 결정은 메타페이지 배타적 락 아래 임계 구역 내에서 이루어지며 전체가 단일 WAL 레코드다.

// _hash_doinsert (commit + split decision) — src/backend/access/hash/hashinsert.c
LockBuffer(metabuf, BUFFER_LOCK_EXCLUSIVE);
START_CRIT_SECTION();
itup_off = _hash_pgaddtup(rel, buf, itemsz, itup, sorted);
MarkBufferDirty(buf);
metap = HashPageGetMeta(metapage);
metap->hashm_ntuples += 1;
do_expand = metap->hashm_ntuples >
  (double) metap->hashm_ffactor * (metap->hashm_maxbucket + 1);
MarkBufferDirty(metabuf);
/* ... XLOG_HASH_INSERT registers buf (block 0) and metabuf (block 1) ... */
END_CRIT_SECTION();
LockBuffer(metabuf, BUFFER_LOCK_UNLOCK);
_hash_relbuf(rel, buf);
if (do_expand)
  _hash_expandtable(rel, metabuf);  /* may split one bucket */

분할 조건 ntuples > ffactor * (maxbucket + 1)은 전역 부하율이다. 현재 버킷이 아니라 전체 테이블이 너무 가득 찼을 때 발동하는 것이 선형 해싱의 라운드로빈 규율이다.

버킷 증분 분할

섹션 제목: “버킷 증분 분할”

_hash_expandtable이 성장의 핵심이다. 메타페이지를 잠그고 분할이 여전히 필요한지 재확인한 후, 선형 해싱 규칙에 따라 분할할 버킷을 선택한다. 새 버킷은 maxbucket + 1이고, 분할 원본이 되는 기존 버킷은 new_bucket & lowmask다. 기존 버킷에 조건부 클린업 락을 시도한다. 메타페이지 락을 잡은 채 차단할 수 없으므로 조건부다. 락을 얻지 못하면 그냥 포기한다. 인덱스는 가득 찬 채로 남지만 정확성은 유지되며, 다음 삽입자가 재시도한다.

// _hash_expandtable (bucket selection) — src/backend/access/hash/hashpage.c
new_bucket = metap->hashm_maxbucket + 1;
old_bucket = (new_bucket & metap->hashm_lowmask);
start_oblkno = BUCKET_TO_BLKNO(metap, old_bucket);


buf_oblkno = _hash_getbuf_with_condlock_cleanup(rel, start_oblkno, LH_BUCKET_PAGE);
if (!buf_oblkno)
  goto fail;  /* couldn't get cleanup lock; abandon split, stay overfull */

기존 버킷에 미결 분할(LH_BUCKET_BEING_SPLIT) 또는 분할 클린업 잔여 작업(LH_BUCKET_NEEDS_SPLIT_CLEANUP)이 있으면 먼저 완료하고 재시작한다. 하나의 버킷은 두 개의 분할이 동시에 진행될 수 없다. 새 분할점의 버킷 페이지 전체를 할당해야 할 수도 있다(_hash_alloc_buckets. 범위 끝에 단일 0 페이지를 기록해 파일의 논리적 EOF를 확장하고 나머지는 파일시스템 홀에 의존). 그런 다음 임계 구역 내에서 메타페이지 마스크를 업데이트하고 두 버킷을 진행 중으로 플래그한다. 모두 단일 XLOG_HASH_SPLIT_ALLOCATE_PAGE 레코드다.

// _hash_expandtable (mask + flag update) — src/backend/access/hash/hashpage.c
START_CRIT_SECTION();
metap->hashm_maxbucket = new_bucket;
if (new_bucket > metap->hashm_highmask)
{
  /* a full doubling completed: widen the masks one bit */
  metap->hashm_lowmask = metap->hashm_highmask;
  metap->hashm_highmask = new_bucket | metap->hashm_lowmask;
}
/* old bucket: mark being-split AND stamp maxbucket into hasho_prevblkno */
oopaque->hasho_flag |= LH_BUCKET_BEING_SPLIT;
oopaque->hasho_prevblkno = maxbucket;
/* new bucket: fresh primary page, marked being-populated */
nopaque->hasho_flag = LH_BUCKET_PAGE | LH_BUCKET_BEING_POPULATED;

마스크 확장은 2의 거듭제곱 경계에서만 발동한다. 경계 사이에서는 마스크가 고정된 채 분할당 버킷이 하나씩 늘어난다. 선형 해싱의 부드러운 증분 두 배 배가가 바로 이것이다. _hash_splitbucket이 기존 버킷의 체인을 탐색하며 각 튜플을 새 마스크 아래서 재계산한다. 새 버킷으로 가야 할 튜플은 복사(제자리 이동 아님)하고 INDEX_MOVED_BY_SPLIT_MASK를 찍어 새 버킷에 추가한다.

// _hash_splitbucket (partition loop) — src/backend/access/hash/hashpage.c
bucket = _hash_hashkey2bucket(_hash_get_indextuple_hashkey(itup),
                maxbucket, highmask, lowmask);
if (bucket == nbucket)
{
  new_itup = CopyIndexTuple(itup);
  new_itup->t_info |= INDEX_MOVED_BY_SPLIT_MASK;  /* scans skip in old bucket */
  /* buffer up; flush to new page (and chain overflow) when full */
  itups[nitups++] = new_itup;
}
else
  Assert(bucket == obucket);  /* stays put */

기존 버킷에 남을 튜플은 그대로 둔다. 분할 클린업 단계에서 지연 삭제된다. 체인 순회가 끝나면 두 primary 페이지를 다시 잠그고(낮은 번호 버킷 먼저 — 락 순서 준수), 진행 중 플래그를 지우고, 기존 버킷에 LH_BUCKET_NEEDS_SPLIT_CLEANUP을 설정한다. 모두 XLOG_HASH_SPLIT_COMPLETE 레코드 아래서다.

// _hash_splitbucket (completion) — src/backend/access/hash/hashpage.c
oopaque->hasho_flag &= ~LH_BUCKET_BEING_SPLIT;
nopaque->hasho_flag &= ~LH_BUCKET_BEING_POPULATED;
oopaque->hasho_flag |= LH_BUCKET_NEEDS_SPLIT_CLEANUP;  /* old copies still present */

“지금 복사하고 moved-by-split 마킹, 나중에 needs-cleanup 아래 삭제”하는 2단계 설계가 분할을 충돌에서 살아남게 하고 동시 스캔에 보이지 않게 한다. 분할 전 시작된 스캔은 기존 버킷의 원본을 본다. 분할 중 시작된 스캔은 새 버킷과 기존 버킷의 아직 이동 안 된 튜플을 본다. 분할 중간에 충돌하면 두 플래그가 모두 설정되므로 독자 알고리즘이 다음 삽입이 작업을 완료할 때까지 양쪽 절반을 투명하게 스캔한다.

flowchart TD
  INS["삽입이 ntuples ><br/>ffactor * (maxbucket+1) 초과"] --> EXP["_hash_expandtable"]
  EXP --> META["메타페이지 잠금<br/>분할 필요 재확인"]
  META --> PICK["new = maxbucket+1<br/>old = new &amp; lowmask"]
  PICK --> CL{"기존 버킷에<br/>조건부 클린업 락?"}
  CL -->|no| GIVEUP["포기<br/>가득 찬 채로, 나중에 재시도"]
  CL -->|yes| PEND{"기존 버킷에<br/>미결 분할/클린업?"}
  PEND -->|yes| FIN["완료 후 restart_expand"]
  PEND -->|no| ALLOC["새 분할점 그룹이면<br/>_hash_alloc_buckets"]
  ALLOC --> FLAG["임계 구역: 마스크 확장,<br/>old=BEING_SPLIT new=BEING_POPULATED 플래그<br/>WAL: SPLIT_ALLOCATE_PAGE"]
  FLAG --> PART["_hash_splitbucket:<br/>nbucket 튜플 복사,<br/>MOVED_BY_SPLIT 마킹<br/>WAL: SPLIT_PAGE per full page"]
  PART --> DONE["플래그 클리어,<br/>NEEDS_SPLIT_CLEANUP 설정<br/>WAL: SPLIT_COMPLETE"]
  DONE --> CLEAN["hashbucketcleanup:<br/>기존 버킷에서 이동된 원본 삭제"]

오버플로 페이지 — 할당, 해제, 여유 공간 비트맵

섹션 제목: “오버플로 페이지 — 할당, 해제, 여유 공간 비트맵”

오버플로 페이지는 비트맵 페이지로 추적한다. 전용 페이지로, 페이로드가 거대한 비트 배열이다. 오버플로 페이지 하나당 비트 하나(0 = 여유, 1 = 사용 중). _hash_addovflpage가 hashm_firstfree부터 비트맵을 검색해 재활용 가능한 페이지를 찾는다. 없으면 인덱스를 확장한다. 할당과 체인 연결이 단일 XLOG_HASH_ADD_OVFL_PAGE 레코드이므로 충돌로 절반만 연결된 페이지가 누수될 수 없다.

// _hash_addovflpage (recycle vs. extend) — src/backend/access/hash/hashovfl.c
for (; bit <= last_inpage; j++, bit += BITS_PER_MAP)
{
  if (freep[j] != ALL_SET)    /* a free bit in this bitmap word */
  {
    bit += _hash_firstfreebit(freep[j]);
    blkno = bitno_to_blkno(metap, bit + (i << BMPG_SHIFT(metap)));
    ovflbuf = _hash_getinitbuf(rel, blkno);  /* recycle this page */
    goto found;
  }
}
/* ... fell through: extend the relation for a new overflow page ... */

해제는 역과정이며 튜플을 다른 곳으로 이동하는 것과 원자적으로 결합된다. _hash_freeovflpage가 이중 연결 체인에서 대상 페이지를 제거하고(양쪽 이웃 수정), 비트맵 비트를 지우고, 적절하면 hashm_firstfree를 낮추고, 재배치된 튜플을 쓰기 페이지에 추가한다. 모두 단일 XLOG_HASH_SQUEEZE_PAGE 레코드다. README는 이동과 연결 해제를 하나의 액션으로 결합하는 것이 스탠바이에서 튜플이 잠깐 두 번 보이는 것을 막는 이유라고 명시한다.

// _hash_freeovflpage (delink) — src/backend/access/hash/hashovfl.c
if (BufferIsValid(prevbuf))
  prevopaque->hasho_nextblkno = nextblkno;  /* fore sibling skips us */
if (BufferIsValid(nextbuf))
  nextopaque->hasho_prevblkno = prevblkno;  /* aft sibling skips us */
CLRBIT(freep, bitmapbit);            /* mark page free in bitmap */
if (ovflbitno < metap->hashm_firstfree)
  metap->hashm_firstfree = ovflbitno;

VACUUM(hashbulkdelete → hashbucketcleanup)은 버킷 체인을 따라 연결된 클린업 락 아래서 죽은 튜플과 moved-by-split 튜플을 페이지 단위로 제거한다. 그런 다음 _hash_squeezebucket이 버킷을 압착한다. 체인 꼬리에서 후방으로 이동하는 읽기 포인터와 primary 페이지에서 전방으로 이동하는 쓰기 포인터가 작동한다. 빈 오버플로 페이지를 해제할 때까지 앞쪽 페이지로 튜플을 이동하고, 두 포인터가 만나면 종료한다. 비트맵 여유 풀로 오버플로 페이지를 회수하는 유일한 메커니즘이다(REINDEX 제외). 버킷 수 자체는 줄어들지 않는다.

버킷 수준 잠금과 스캔/VACUUM 상호 잠금

섹션 제목: “버킷 수준 잠금과 스캔/VACUUM 상호 잠금”

잠금 계약은 간결하지만 엄격하다. 두 버킷을 건드려야 하는 두 연산 사이의 교착 상태를 피하려고 낮은 번호 버킷을 항상 먼저 잠근다. 메타페이지는 모든 버킷 락 이후에만 잠근다. 스캔은 전체 생애 동안 primary 버킷 페이지의 핀(락이 아님)을 유지한다. VACUUM과 분할(모두 클린업 락, 즉 유일한 핀이 필요)이 스캔이 머무는 동안 해당 버킷을 재조직하지 못하게 막는다. 남은 위험 하나 — VACUUM이 버킷의 클린업 락을 해제한 후 시작했지만 아직 실행 중인 클린업을 추월해 VACUUM이 재사용하려는 TID를 잘못 죽이는 스캔 — 는 락 체이닝으로 차단한다. 클린업이 현재 페이지를 해제하기 전에 체인의 다음 페이지를 잠그므로 스캔은 클린업 프론티어를 도약할 수 없다.

소스 코드 가이드

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

해시 AM은 전적으로 src/backend/access/hash/ 아래에 있다. 심볼은 호출 흐름별로 묶었다. 끝의 위치 힌트 표는 각 심볼의 (파일, 행)을 2026-06-05 기준으로 제공한다.

AM 디스패치 표면 (hash.c)

섹션 제목: “AM 디스패치 표면 (hash.c)”
  • hashhandler — 인덱스 AM 레이어(postgres-index-am.md)에 알려지는 IndexAmRoutine을 채운다. AM이 등치만 지원하고(amsearcharray = false, 단일 전략), unique와 순서 지정을 지원하지 않음을 선언한다.
  • hashbuild — 일괄 빌드 진입점. 인덱스가 충분히 크면 먼저 해시 코드로 정렬하는 스풀을 사용한다(hashsort.c, 이 문서 범위 외).
  • hashinsert — 튜플별 공개 진입점. 인덱스 튜플을 계산하고 _hash_doinsert를 호출한다.
  • hashgettuple — 스캔 진입점. _hash_first / _hash_next를 구동하고 LP_DEAD 킬-아이템 힌팅을 관리한다.
  • hashbulkdelete / hashbucketcleanup — VACUUM의 버킷별 클린업 드라이버. 죽은 튜플과 moved-by-split 튜플을 제거하고 LH_BUCKET_NEEDS_SPLIT_CLEANUP을 지운 후 압착한다.

주소 산술 (hashutil.c)

섹션 제목: “주소 산술 (hashutil.c)”
  • _hash_datum2hashkey — opclass 해시 프로시저를 호출해 키의 32비트 해시 코드를 얻는다(캐시된 비크로스-타입 빠른 경로).
  • _hash_hashkey2bucket — highmask/lowmask/maxbucket을 적용해 해시 코드를 버킷 번호로 매핑한다.
  • _hash_spareindex — 버킷 수를 전역 분할점 단계로 매핑한다(그룹 < 10은 단일 단계, 그룹 >= 10은 4단계).
  • _hash_get_totalbuckets — 역함수. 주어진 분할점 단계까지 할당된 전체 버킷 수.
  • _hash_get_oldblock_from_newbucket / _hash_get_newblock_from_oldbucket — 분할의 두 버킷 번호 사이를 변환. 스캔과 분할 완료에서 사용.
  • BUCKET_TO_BLKNO (매크로, hash.h) — 버킷 번호를 물리 블록으로 변환.

메타페이지, 할당, 분할 (hashpage.c)

섹션 제목: “메타페이지, 할당, 분할 (hashpage.c)”
  • _hash_init / _hash_init_metabuffer — CREATE INDEX 시 메타페이지, 초기 N개 버킷 페이지, 첫 번째 비트맵 페이지를 생성한다.
  • _hash_getbuf / _hash_getnewbuf / _hash_getinitbuf / _hash_getbuf_with_condlock_cleanup — 허용된 페이지 타입 마스크를 _hash_checkpage로 검증하는 타입 안전 버퍼 접근자.
  • _hash_getcachedmetap — rd_amcache의 relcache 메타페이지 사본을 반환(필요 시 지연 새로 고침).
  • _hash_getbucketbuf_from_hashkey — 캐시 유효성 검사 조회 루프. 잠긴 primary 버킷 페이지를 반환하며 오래된 캐시 감지 시 재시도.
  • _hash_expandtable — 분할 드라이버. 버킷 선택, 클린업 락 획득, 마스크 확장, 할당, 진행 중 플래그 설정.
  • _hash_alloc_buckets — 새 분할점 그룹을 위해 범위 끝에 0 페이지 하나를 기록해 파일의 논리적 EOF를 확장.
  • _hash_splitbucket — 기존 버킷 튜플을 기존과 새 버킷 사이에 재분배. 이동 튜플에 INDEX_MOVED_BY_SPLIT 마킹.
  • _hash_finish_split — 충돌이나 클린업 락 획득 실패로 중단된 분할을 완료. 이미 이동된 튜플을 건너뛰려고 TID 해시 테이블 사용.

삽입 (hashinsert.c)

섹션 제목: “삽입 (hashinsert.c)”
  • _hash_doinsert — 버킷 찾기, 여유 공간을 위한 체인 탐색(필요 시 오버플로 추가), 튜플 배치, 메타페이지 카운트 증가, 가득 차면 분할 발동.
  • _hash_pgaddtup / _hash_pgaddmultitup — 해시 코드 순서를 유지하며 페이지에 튜플 하나/여러 개 추가(슬롯을 이진 탐색으로 찾음).
  • _hash_vacuum_one_page — 오버플로 페이지에 의존하기 전에 가득 찬 단일 페이지에서 LP_DEAD 튜플을 기회주의적으로 삭제.

스캔 (hashsearch.c)

섹션 제목: “스캔 (hashsearch.c)”
  • _hash_first — 스캔 시작. 키를 해싱하고, primary 버킷 페이지를 핀으로 고정하고, 채워지는 중인 케이스를 처리하고, 이진 탐색으로 위치 지정.
  • _hash_readpage — 한 페이지의 모든 적합 튜플을 so->currPos.items[]에 로드하고 콘텐츠 락 해제(핀은 유지).
  • _hash_load_qualified_items — 페이지별 매칭 루프. moved-by-split 튜플과 죽은 튜플 건너뜀.
  • _hash_next / _hash_readnext / _hash_readprev — 체인의 다음/이전 페이지로 전진. 스캔 시작 시 분할이 진행 중이었으면 분할 파트너 버킷으로 교차.

오버플로 생애 주기 (hashovfl.c)

섹션 제목: “오버플로 생애 주기 (hashovfl.c)”
  • _hash_addovflpage — 비트맵에서 여유 오버플로 페이지를 재활용하거나 인덱스를 확장. 버킷 꼬리에 원자적으로 체인 연결.
  • _hash_freeovflpage — 오버플로 페이지를 체인에서 제거하고, 비트맵 비트를 지우고, 튜플을 쓰기 페이지로 이동. 모두 단일 WAL 액션.
  • _hash_squeezebucket — 튜플을 앞쪽으로 이동하고 빈 오버플로 페이지를 해제해 버킷 압착.
  • _hash_initbitmapbuffer — 모든 비트를 “사용 중”으로 설정해 비트맵 페이지 초기화.
  • bitno_to_blkno / _hash_ovflblkno_to_bitno — 오버플로 페이지의 비트맵 비트 번호와 물리 블록 번호 사이 변환.

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

섹션 제목: “위치 힌트 (2026-06-05 기준, REL_18 273fe94)”
심볼파일행
hashhandlersrc/backend/access/hash/hash.c58
hashbuildsrc/backend/access/hash/hash.c122
hashinsertsrc/backend/access/hash/hash.c258
hashgettuplesrc/backend/access/hash/hash.c290
hashbulkdeletesrc/backend/access/hash/hash.c465
hashbucketcleanupsrc/backend/access/hash/hash.c690
_hash_datum2hashkeysrc/backend/access/hash/hashutil.c82
_hash_hashkey2bucketsrc/backend/access/hash/hashutil.c125
_hash_spareindexsrc/backend/access/hash/hashutil.c142
_hash_get_totalbucketssrc/backend/access/hash/hashutil.c174
_hash_get_oldblock_from_newbucketsrc/backend/access/hash/hashutil.c422
_hash_get_newblock_from_oldbucketsrc/backend/access/hash/hashutil.c461
_hash_initsrc/backend/access/hash/hashpage.c327
_hash_init_metabuffersrc/backend/access/hash/hashpage.c498
_hash_getbufsrc/backend/access/hash/hashpage.c70
_hash_getbuf_with_condlock_cleanupsrc/backend/access/hash/hashpage.c96
_hash_getnewbufsrc/backend/access/hash/hashpage.c198
_hash_expandtablesrc/backend/access/hash/hashpage.c614
_hash_alloc_bucketssrc/backend/access/hash/hashpage.c992
_hash_splitbucketsrc/backend/access/hash/hashpage.c1073
_hash_finish_splitsrc/backend/access/hash/hashpage.c1356
_hash_getcachedmetapsrc/backend/access/hash/hashpage.c1501
_hash_getbucketbuf_from_hashkeysrc/backend/access/hash/hashpage.c1559
_hash_doinsertsrc/backend/access/hash/hashinsert.c38
_hash_pgaddtupsrc/backend/access/hash/hashinsert.c274
_hash_pgaddmultitupsrc/backend/access/hash/hashinsert.c331
_hash_vacuum_one_pagesrc/backend/access/hash/hashinsert.c370
_hash_nextsrc/backend/access/hash/hashsearch.c48
_hash_readnextsrc/backend/access/hash/hashsearch.c131
_hash_readprevsrc/backend/access/hash/hashsearch.c197
_hash_firstsrc/backend/access/hash/hashsearch.c288
_hash_readpagesrc/backend/access/hash/hashsearch.c448
_hash_load_qualified_itemssrc/backend/access/hash/hashsearch.c604
bitno_to_blknosrc/backend/access/hash/hashovfl.c35
_hash_ovflblkno_to_bitnosrc/backend/access/hash/hashovfl.c62
_hash_addovflpagesrc/backend/access/hash/hashovfl.c112
_hash_freeovflpagesrc/backend/access/hash/hashovfl.c490
_hash_initbitmapbuffersrc/backend/access/hash/hashovfl.c777
_hash_squeezebucketsrc/backend/access/hash/hashovfl.c842
HashMetaPageDatasrc/include/access/hash.h244
HashPageOpaqueDatasrc/include/access/hash.h77
BUCKET_TO_BLKNOsrc/include/access/hash.h39

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

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

모든 주장은 /data/hgryoo/references/postgres의 REL_18 트리(커밋 273fe94)를 직접 검증했다.

  • 페이지 타입과 플래그. 네 가지 물리 페이지 타입(LH_OVERFLOW_PAGE, LH_BUCKET_PAGE, LH_BITMAP_PAGE, LH_META_PAGE)과 네 가지 일시적 플래그(LH_BUCKET_BEING_POPULATED, LH_BUCKET_BEING_SPLIT, LH_BUCKET_NEEDS_SPLIT_CLEANUP, LH_PAGE_HAS_DEAD_TUPLES)가 인용한 대로 hash.h 54–61행에 정의되어 있다. HASHO_PAGE_ID는 0xFF80(101행). 검증됨.
  • hasho_prevblkno 오버로드. 헤더 주석(67–72행)이 primary 버킷 페이지에서 hasho_prevblkno가 “버킷이 마지막으로 분할된 시점의 hashm_maxbucket 값 또는 버킷 생성 시점의 값”을 저장하며 캐시 검증에 쓰인다고 확인한다. _hash_initbuf가 max_bucket으로 설정하고(176행), _hash_expandtable이 분할 시 maxbucket으로 업데이트한다. 검증됨.
  • 메타페이지 캐시 검증. _hash_getbucketbuf_from_hashkey가 opaque->hasho_prevblkno <= metap->hashm_maxbucket일 때 루프를 종료하고, 그렇지 않으면 _hash_getcachedmetap(rel, &metabuf, true)로 강제 새로 고침한다. 검증됨.
  • 선형 해싱 마스크 논리. _hash_hashkey2bucket이 bucket = hashkey & highmask; if (bucket > maxbucket) bucket &= lowmask;를 그대로 계산한다. _hash_expandtable의 두 배 경계에서의 마스크 확장(lowmask = highmask; highmask = new_bucket | lowmask;)이 존재한다. 검증됨.
  • 분할 선택. new_bucket = maxbucket + 1; old_bucket = new_bucket & lowmask;가 _hash_expandtable에서 확인된다. 조건부 클린업 락(_hash_getbuf_with_condlock_cleanup)과 “실패 시 포기” 경로(goto fail)가 설명한 대로다. 검증됨.
  • moved-by-split 마킹. _hash_splitbucket이 CopyIndexTuple로 적합한 튜플을 복사하고 INDEX_MOVED_BY_SPLIT_MASK(= INDEX_AM_RESERVED_BIT, hash.h 293행)를 OR하며, _hash_load_qualified_items가 hashso_buc_populated && !hashso_buc_split일 때 그런 튜플을 건너뛴다. 검증됨.
  • 분할 결정 공식. _hash_doinsert와 _hash_expandtable 모두 ntuples > ffactor * (maxbucket + 1)을 사용하며 두 곳 모두에 명시적 “동기화 유지” 주석이 있다. 검증됨.
  • WAL 연산 코드. XLOG_HASH_INIT_META_PAGE(0x00), INIT_BITMAP_PAGE, INSERT, ADD_OVFL_PAGE, SPLIT_ALLOCATE_PAGE, SPLIT_PAGE, SPLIT_COMPLETE, MOVE_PAGE_CONTENTS, SQUEEZE_PAGE, DELETE, SPLIT_CLEANUP, UPDATE_META_PAGE, VACUUM_ONE_PAGE가 모두 hash_xlog.h 27–45행에 정의되어 있다. 각 XLogInsert(RM_HASH_ID, ...) 호출이 해당 연산과 일치한다. 검증됨.
  • 오버플로 여유 공간 비트맵. _hash_addovflpage가 hashm_firstfree부터 비트맵을 검색하고 freep[j] != ALL_SET 워드를 찾으면 재활용(없으면 확장)하며, _hash_freeovflpage가 CLRBIT(freep, bitmapbit)를 하고 hashm_firstfree를 낮춘다. XLOG_HASH_SQUEEZE_PAGE 아래 원자적 이동+연결 해제가 확인된다. 검증됨.
  • 스캔 잠금. _hash_first가 so->hashso_bucket_buf를 핀으로 유지한다. _hash_readpage가 콘텐츠 락을 해제하지만 primary 버킷 핀은 유지한다(currPos.buf == hashso_bucket_buf일 때 LockBuffer(... BUFFER_LOCK_UNLOCK)). 전체 페이지 슬러프가 currPos.items[]에 존재한다. 검증됨.
  • 전체 인덱스 스캔 거부. _hash_first가 scan->numberOfKeys < 1일 때 ERRCODE_FEATURE_NOT_SUPPORTED “hash indexes do not support whole-index scans”를 발생시킨다. 검증됨.
  • 한 가지 주의. 문서에서 VACUUM이 “비트맵 여유 풀에 공간을 돌려주지만 OS에는 돌려주지 않는다”고 했다. README(31–34행)가 해시 인덱스는 REINDEX 외에 축소되지 않으며 오버플로 페이지는 재활용되지만 파일시스템에 반환되지 않는다고 확인한다. 검증됨.

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

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

  • 확장 가능 해싱(Fagin et al. 1979) 대 PostgreSQL의 디렉터리 없는 선형 해싱. 지배적 대안은 상위 d 해시 비트로 인덱싱된 2^d 디렉터리를 유지해 탐색당 정확히 두 번의 I/O를 보장하고 넘친 버킷만 분할한다. PostgreSQL은 의도적으로 디렉터리를 거부했다. BUCKET_TO_BLKNO가 포인터 테이블 대신 spares[]로 블록을 계산한다. 가끔의 추가 오버플로 체인 홉을 감수하고 그 자체가 경합과 메모리 핫스팟이 될 공유 가변 인메모리 디렉터리를 없앴다. 각 hashm_* 메타페이지 필드를 확장 가능 해싱 유사체(디렉터리 대 마스크, 로컬 깊이 대 hasho_prevblkno-as-maxbucket)로 매핑하면 트레이드오프가 선명해진다. 논문: Fagin, Nievergelt, Pippenger & Strong, “Extendible Hashing”, ACM TODS 4(3), 1979.

  • Litwin의 원래 선형 해싱 대 Seltzer-Yigit의 UNIX 패키지. README는 Seltzer & Yigit 1991(dbms-papers/ 참고문헌)을 직계 계보로 인정하며, 이는 Litwin의 1980년 선형 해싱의 엔지니어링 개선판이다. PostgreSQL의 spares[]/분할점 단계 방식(그룹 < 10은 단일 단계, 그룹 >= 10은 4단계)은 교과서 알고리즘에 없는 디스크 할당 최적화다. 한 번에 2의 거듭제곱 전체 슬랩으로 파일을 확장하는 것을 피한다. _hash_spareindex를 Litwin의 평탄한 그룹 번호 매기기와 비교하면 논문 알고리즘이 프로덕션 스토리지 코드로 어떻게 강화되는지 자립적으로 보여주는 사례다. 논문: Litwin, “Linear Hashing: A New Tool for File and Table Addressing”, VLDB 1980.

  • 기본 등치 인덱스로서 해시 대 B-트리. PG 10에서 WAL 로깅이 도입되기 전까지 해시 인덱스는 충돌 안전하지 않았고 문서화는 적극적으로 등치에도 B-트리를 권했다. 지금도 단일 컬럼 B-트리가 O(log_F N)으로 등치를 지원하면서 완전한 충돌 안전성, 순서 지정, 고유성을 제공하므로, 해시 AM이 이기는 경우는 매우 큰 키(전체 키 저장 대신 4바이트 해시 코드 저장이 유리할 때)와 고카디널리티 등치 워크로드뿐이다. postgres-nbtree.md의 _bt_search와 _hash_first를 넓은 텍스트 등치 컬럼에서 벤치마킹하면 교차점을 정량화할 수 있다.

  • 인메모리 동적 해싱 — dynahash.c가 같은 계보를 공유. PostgreSQL의 자체 인메모리 해시 테이블(버퍼 매핑 테이블, relcache, 락 매니저의 LOCK 해시 뒤에 있는 src/backend/utils/hash/dynahash.c)이 같은 Seltzer-Yigit 패키지에서 내려왔다. 다만 디스크 분할점 대신 디렉터리 세그먼트로 확장하고 영속하지 않는다. 온디스크 hashm_spares[] 주소 지정과 dynahash의 분절 디렉터리를 비교하면 하나의 알고리즘이 디스크와 RAM 각각에 특화된 두 갈래로 나뉘는 모습을 보여준다.

  • 현대 동시/래치 프리 해시 인덱스. 연구 엔진들은 페이지 콘텐츠 락 선형 해싱을 넘어 래치 프리 분할-순서 리스트(Shalev-Shavit 2006)와 캐시 인식 확장 가능 해싱(예: 영속 메모리용 레벨 해싱, CCEH)으로 나아간다. PostgreSQL의 버킷별 클린업 락, 스캔 생애 전체 핀 프로토콜을 이런 설계들과 비교하면 디스크 지향 버퍼 공유 엔진이 충돌 안전성과 복제본 일관성을 위해 무엇을 포기하는지 드러난다. 해시 AM의 “페이지 변경당 원자적 WAL 액션 하나, 어떤 중간 상태도 검색 가능” 규율이 정확히 래치 프리 인메모리 설계가 필요 없고 쉽게 제공할 수도 없는 속성이다.

  • CUBRID에는 해시 인덱스 AM이 없다. CUBRID의 영속 인덱싱은 B+-트리 전용이다. 해싱은 쿼리 실행기(해시 조인, 해시 집계)와 인메모리 구조에 나타나며, 보조 인덱스 접근 방법으로는 없다. DBMS가 B-트리 전용 인덱스 카탈로그를 선택하는 이유(옵티마이저 비용 모델의 균일성, 유지해야 할 단일 복구 프로토콜)를 설명하는 노트가 이 파일의 자연스러운 동반자다. CUBRID 코드 분석 트리를 참고하라.

출처

섹션 제목: “출처”

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

섹션 제목: “트리 내 README 및 소스 파일 (REL_18_STABLE, 커밋 273fe94)”
  • src/backend/access/hash/README — 설계 문서. 선형 해싱 기본과 Seltzer-Yigit 계보, 분할점/spares[] 주소 지정 방식, 락 정의(페이지 콘텐츠 락, 핀, 클린업 락), hasho_prevblkno를 통한 메타페이지 캐시 검증, 증분 분할 프로토콜, 오버플로 페이지 여유 공간 비트맵, 압착/클린업 VACUUM 경로, WAL 충돌 안전성 불변식.
  • src/include/access/hash.h — HashPageOpaqueData, HashMetaPageData, LH_* 페이지 타입 및 일시적 플래그 비트, BUCKET_TO_BLKNO, INDEX_MOVED_BY_SPLIT_MASK, HASHO_PAGE_ID, 분할점/비트맵 상수.
  • src/include/access/hash_xlog.h — RM_HASH_ID가 재생하는 XLOG_HASH_* 연산 코드와 레코드별 페이로드 구조체.
  • src/backend/access/hash/hash.c — hashhandler, AM 콜백(hashinsert, hashgettuple, hashbulkdelete), hashbucketcleanup.
  • src/backend/access/hash/hashpage.c — 메타페이지 초기화, 타입 안전 버퍼 접근자, _hash_getcachedmetap, _hash_getbucketbuf_from_hashkey, _hash_expandtable, _hash_alloc_buckets, _hash_splitbucket, _hash_finish_split.
  • src/backend/access/hash/hashinsert.c — _hash_doinsert, _hash_pgaddtup, _hash_vacuum_one_page.
  • src/backend/access/hash/hashsearch.c — _hash_first, _hash_readpage, _hash_load_qualified_items, _hash_next/_hash_readnext/_hash_readprev.
  • src/backend/access/hash/hashovfl.c — _hash_addovflpage, _hash_freeovflpage, _hash_squeezebucket, 비트맵 헬퍼.
  • src/backend/access/hash/hashutil.c — _hash_hashkey2bucket, _hash_spareindex, _hash_get_totalbuckets, 기존/새 버킷 변환자.

논문 및 교과서 챕터

섹션 제목: “논문 및 교과서 챕터”
  • Seltzer, M. & Yigit, O. (1991). “A New Hashing Package for UNIX.” Proc. Winter USENIX Conf. 해시 README 맨 위에 인용된 직계 참조. 선형 해싱 코어와 spares[] 주소 지정의 출처. knowledge/research/dbms-papers/와 postgres-paper-bibliography.md 계획에 수록.
  • Litwin, W. (1980). “Linear Hashing: A New Tool for File and Table Addressing.” Proc. VLDB. Seltzer-Yigit가 개선한 원래 선형 해싱 알고리즘.
  • Fagin, R., Nievergelt, J., Pippenger, N. & Strong, H. R. (1979). “Extendible Hashing — A Fast Access Method for Dynamic Files.” ACM TODS 4(3):315-344. “DBMS 공통 설계 패턴”과 “PostgreSQL 너머” 섹션에서 대조한 디렉터리 기반 대안.
  • Database System Concepts (Silberschatz, Korth, Sudarshan, 7판), 14장 “Indexing” — 정적 해싱과 동적 해싱 기초(knowledge/research/dbms-general/).
  • Database Internals (Petrov 2019), 2–6장 — 온디스크 해시 구조의 페이지 레이아웃, 오버플로 체인, WAL 프레이밍.

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

섹션 제목: “형제 문서 (교차 참조 — 메커니즘은 해당 문서가 소유, 여기서 중복하지 않음)”
  • postgres-index-am.md — hashhandler가 채우는 IndexAmRoutine 디스패치 계약(빌드/삽입/스캔/VACUUM 콜백 표면).
  • postgres-nbtree.md — B-트리 AM. 이 AM이 비교 대상인 기본 등치 인덱스이자 “원자적 WAL 액션으로 분해” 동시성 규율의 공유 출처.
  • postgres-buffer-manager.md — 버킷 수준 잠금 프로토콜의 기반인 버퍼 핀, 콘텐츠 락(LWLock), 클린업 락.
  • postgres-lock-manager.md — SQL 수준 heavyweight 락 테이블. 해시 AM이 페이지 수준 동시성에 의도적으로 사용하지 않는 것.
  • postgres-wal-records-rmgr.md — RM_HASH_ID 리소스 매니저와 XLOG_HASH_* 레코드의 rmgr WAL 재생 프레이밍.
  • postgres-architecture-overview.md — Axis 4(플러그인 가능 접근 방법). 해시 AM이 nbtree, GiST, GIN, SP-GiST, BRIN 옆에 위치하는 곳.