(KO) CUBRID Overflow File — Heap big-record 와 B+Tree overflow-OID 페이지 사슬

학술적 배경
DBMS 공통 설계 패턴
CUBRID의 구현
소스 코드 가이드
소스 검증 노트
미해결 질문
출처

학술적 배경

슬롯 페이지 (cubrid-heap-manager.md §슬롯 페이지) 는 “고정 크기 페이지 안에 가변 길이 레코드를 어떻게 담을 것인가” 라는 문 제를 페이지 안쪽 에서 푼다. 그런데 레코드 자체가 한 페이지 의 용량을 넘기는 순간, 또는 비-unique 인덱스의 한 키에 매달린 OID 리스트가 한 리프 레코드의 크기를 넘기는 순간, 슬롯 레이아웃 은 더 이상 할 말이 없다. Database Internals (Petrov) 3장 §File Formats, §Variable-Size Records 가 이 지점에서 가능 한 세 가지 고전적 전략을 정리한다.

In-line growth + tombstone. 레코드를 home 페이지에 그대 로 두되, 슬롯을 넘쳐서 자라면 페이지 안에서 옮기고 옛 자리 에 tombstone 을 남긴다. 작은 성장에만 통한다. Garcia-Molina / Ullman / Widom Database Systems: The Complete Book, §13.7 “Variable-Length Data and Records” 참고.
In-line forwarding. 새 이미지를 같은 힙의 다른 페이지로 옮기고, 원래 슬롯에는 forwarding pointer 를 남긴다. 인덱스 는 그대로 원래 OID 를 가리키고, 읽기는 그 포인터를 따라가느 라 페이지 fix 를 한 번 더 한다. CUBRID 의 REC_RELOCATION
- REC_NEWHOME 조합이 정확히 이 형태다 (cubrid-heap-manager.md §레코드 타입 어휘).
Out-of-line overflow. 레코드가 어떤 힙 페이지에도 들어 갈 수 없을 만큼 크다면, 본체를 별도 파일 (overflow file) 로 밀어 넣고 home 슬롯에는 작은 참조만 남긴다. 그 참조가 원 래 OID 의 영구 식별자고, overflow 사슬은 그 OID 에만 사적 이다. Comer (1979) 와 IBM System R 노트가 long fields 를 위해 이 형태를 처음 기술했다. PostgreSQL 이 TOAST (The Oversized-Attribute Storage Technique) 라는 이름으로 정형 화했다.

같은 문제가 한 단계 위인 B+Tree 비-unique 인덱스 에서도 나 타난다. 리프 레코드는 key || OID_list 를 들고 있다. 한 키에 매달린 중복 OID 가 너무 많아지면 OID 리스트가 리프 페이지 용량 을 넘기는데, 교재의 해법 (Bayer, Lehman / Yao, 그 후속들) 은 모양이 같다. 잉여를 키별 overflow 사슬로 밀어낸다. 힙의 overflow file 과는 별개의 사슬이지만, 같은 디스크 파일 substrate 위에서 동작한다.

CUBRID 에는 심볼 수준에서 단 하나의 overflow-file 모듈 (src/storage/overflow_file.{h,c}) 이 있다. 그 모듈이 두 종류 의 spillover 수요를 함께 떠받친다. 그리고 그 위에 두 종류의 호 출자가 서로 다른 방식으로 감싸 둔다.

Heap big-record 경로 — heap_file.c 의 heap_ovf_*.
B+Tree overflow-OID-list 경로 — btree.c 의 btree_*overflow* 들. 단, 이 경로는 overflow_file.c 를 overflow key 를 위해서만 쓴다. OID-list overflow 사슬 은 완전히 다른 페이지 형식이다 — 슬롯 B+Tree 페이지 위에 직접 쌓아 올린 형태이고, “한 논리 레코드가 소유하는 페이지 연결 리스트” 라는 모델만 같은 substrate 에서 빌려 올 뿐이다.

이 문서는 cubrid-heap-manager.md 와 cubrid-btree.md 가 둘 다 overflow_file.c 를 보라 며 비워 둔 자리를 메우려는 목적 으로 쓰였다.

DBMS 공통 설계 패턴

가변 길이 레코드와 비-unique 인덱스를 가진 모든 row-store 는 어떤 형태로든 out-of-line spillover 를 가져다 쓴다. 그 공통 재 료들이 다음과 같다.

컨테이너별로 한 개의 overflow file

할당 단위는 파일 이다 (CUBRID 의 VFID, PostgreSQL 의 toast relation, InnoDB 의 off-page page chain 이 같은 자 리다). overflow file 하나는 하나의 힙, 또는 하나의 B+Tree, 또 는 하나의 컬럼에 묶인다. 그 파일에서 할당된 페이지는 같은 소유 자만 다시 쓸 수 있다. cross-tenant 공유는 없다.

한 논리 레코드당 단방향 페이지 사슬

본문 데이터는 페이지의 사슬에 산다. 각 페이지는 작은 헤더에 “다 음 페이지” 포인터를 들고 있다. 긴 레코드 중간으로의 random access 가 필요하면 머리 페이지부터 걸어 들어간다. 호출자가 이 미 알고 있는 offset 만큼은 페이지를 건너뛸 수도 있다. 단방향 만으로도 충분하다. 모든 호출자가 머리 페이지를 알고 있기 때문 이다 (home 레코드의 참조가 가리키는 자리가 그것이다).

원래 자리의 참조 레코드

원래 자리에는 작은 고정 크기 레코드가 남는다. overflow 사슬을 찾기에 충분한 만큼만 들고 있다 — 페이지 식별자, 그리고 경우에 따라 길이. 인덱스와 다른 reader 들은 여전히 원래 자리를 가리킨 다. overflow lookup 은 그들에게 투명하다.

첫 페이지에만 있는 길이 필드

논리 레코드의 총 바이트 길이는 첫 페이지에만 들어 있다. 머 리 페이지를 fix 하면 사슬을 걷지 않고도 길이를 알 수 있다. 나 머지 페이지는 다음-페이지 링크만 들고 있다.

페이지 단위 락 없음

각 사슬이 한 논리 레코드에만 사적이고, 그 레코드의 정체성이 이 미 보호되어 있기 때문이다 (힙은 row lock 으로, 인덱스 OID 리스 트는 key range lock 으로). overflow 페이지 자체는 lock manager 의 독립 엔트리를 요구하지 않는다. WAL 규율과 머리 페이지의 latch 만으로 충분하다.

참고가 되는 다른 엔진의 설계

PostgreSQL TOAST — 사용자 테이블별로 별도의 pg_toast_<oid> relation 을 두고, 어떤 컬럼의 행이 TOAST_TUPLE_THRESHOLD (8 KB 페이지에서 약 2 KB) 를 넘기는 순간 자동으로 만든다. 큰 attribute 마다 LZ 계열 압축을 적용 한 뒤, 1996 바이트 조각으로 잘라 toast relation 의 평범한 튜 플로 저장한다. (chunk_id, chunk_seq) 가 키다. 사용자 행은 18 바이트 toast pointer (varatt_external) 만 들고 있다 — toast OID, 원본 크기, 압축 후 크기. Reader 는 lazy 하게 de-toast 한다. 해당 컬럼을 건드리지 않는 selective read 는 chunk 를 가져오지 않는다.
InnoDB DYNAMIC / COMPRESSED 행 포맷 — 한 행이 페이지의 절반을 넘기면 BLOB / TEXT / VARCHAR 컬럼이 off-page 로 저 장된다. clustered index 와 같은 tablespace 에서 할당된 blob page 사슬에 들어간다. clustered-index 레코드는 off-page 컬 럼당 20 바이트 포인터 (space, page no, offset, length) 를 들고 있다. DYNAMIC 은 인덱스 페이지에 포인터만 둔다. COMPRESSED 는 거기에 더해 리프 페이지를 압축한다.
Oracle row chaining / migration — Oracle 은 두 경우를 다른 말로 부른다. chained rows (한 블록보다 큰 레코드 → 여러 블록에 분할되어 ROWID 로 연결됨), 그리고 migrated rows (UPDATE 가 레코드를 원래 블록에 안 들어갈 만큼 키워서 다른 블록으로 옮긴 경우 — 원래 자리에 forwarding ROWID 스텁이 남 는다). 관리자에게는 V$SYSSTAT.table fetch continued row 와 DBA_TABLES 의 chained_rows 로 보인다. ANALYZE TABLE ... LIST CHAINED ROWS 로 분석한다.
MySQL MyISAM dynamic format — 레코드를 가변 길이 조각으 로 쪼개고 (offset, length) 헤더로 inline 연결한다 (데이터 파 일 안에서 끝낸다). 별도의 overflow file 이 없다.

CUBRID 는 PostgreSQL 계열 에 가깝다. 힙별로 별도 파일을 두 어 big record 를 흘려 보내고, 트리별로 별도 파일을 두어 B+Tree overflow key 를 흘려 보낸다. 그러나 TOAST 와 달리 attribute 단 위로 나누지 않는다 — 전체 레코드 가 한 덩어리로 spill 된 다. 압축도 하지 않는다. B+Tree OID-list overflow 는 자기만 의 설계점에 산다 (트리별 파일 안의 OID-정렬 슬롯 페이지). file substrate 만 공유할 뿐 힙 경로와는 무관하다.

이론 ↔ CUBRID 명칭 매핑

이론적 개념	CUBRID 명칭
힙 big-record overflow file	`FILE_MULTIPAGE_OBJECT_HEAP` (`file_manager.h`), VFID 는 `HEAP_HDR_STATS.ovf_vfid`
힙 참조 레코드 (forwarding)	`REC_BIGONE` (cubrid-heap-manager.md §레코드 타입)
B+Tree overflow-key 파일	`FILE_BTREE_OVERFLOW_KEY`, VFID 는 `BTID_INT::ovfid`
B+Tree overflow-key 참조	leaf 는 `LEAF_REC.ovfl`, non-leaf 는 `NON_LEAF_REC + ovfl`
B+Tree overflow-OID-list 페이지 사슬	`BTID_INT::ovfid` 에서 할당되는 슬롯 B+Tree 페이지, 머리는 `BTREE_OVERFLOW_HEADER`
첫 페이지 헤더 (heap big-rec / ovfkey)	`OVERFLOW_FIRST_PART { next_vpid; length; data[] }` (`overflow_file.h`)
나머지 페이지 헤더 (heap big-rec / ovfkey)	`OVERFLOW_REST_PART { next_vpid; data[] }` (`overflow_file.h`)
Overflow OID 페이지 헤더 (B+Tree)	`BTREE_OVERFLOW_HEADER { next_vpid }` (`btree_load.h:244`, slot 0/HEADER)
Insert / update / delete API	`overflow_insert` / `overflow_update` / `overflow_delete` (`overflow_file.c`)
힙 wrapper	`heap_ovf_insert` / `heap_ovf_update` / `heap_ovf_delete`
B+Tree key wrapper	`btree_store_overflow_key` / `btree_load_overflow_key` / `btree_delete_overflow_key`
B+Tree OID-list 연산	`btree_start_overflow_page` / `btree_modify_overflow_link` / `btree_find_oid_from_ovfl`
Find-or-create overflow file	`heap_ovf_find_vfid` (heap), `btree_create_overflow_key_file` (btree)
WAL 레코드	`RVOVF_NEWPAGE_INSERT`, `RVOVF_NEWPAGE_LINK`, `RVOVF_PAGE_UPDATE`, `RVOVF_CHANGE_LINK` (`recovery.h:100-103`)
첫 overflow 페이지 마커 (heap MVCC)	`LOG_DUMMY_OVF_RECORD` (vacuum / replication 이 어떤 페이지가 머리인지 인식하기 위한 표시)
Overflow 의 MVCC 헤더	`heap_get_mvcc_rec_header_from_overflow` / `heap_set_mvcc_rec_header_on_overflow` (`heap_file.c`)

CUBRID의 구현

이 모듈은 두 가지 호출자 (heap big-record, B+Tree overflow key) 의 substrate 로 동작한다. 그리고 세 번째 케이스 (B+Tree overflow-OID list — linked-pages 규율은 빌려 오되 자기만의 슬 롯 페이지 형식을 새로 짠 경우) 의 template 으로도 동작한 다. 다섯 가지 성질이 모든 코드 경로의 모양을 결정한다.

하나의 generic API, 세 종류의 파일. overflow_insert / overflow_update / overflow_delete 는 FILE_TYPE discriminator 를 받는다. overflow_file.c:102 의 assert 가 허용하는 값은 단 셋이다 — FILE_TEMP (sort run), FILE_BTREE_OVERFLOW_KEY, 그리고 FILE_MULTIPAGE_OBJECT_HEAP. 그 밖의 값은 assert 에 걸린 다.
OVERFLOW_FIRST_PART ≠ OVERFLOW_REST_PART. 어떤 사슬 의 첫 페이지든 length 필드가 추가로 들어가서 총 레코드 바 이트 크기를 들고 있다. 나머지 페이지에는 그 필드가 없다. 두 헤더의 크기가 다르므로 페이지당 페이로드 용량도 sizeof (int) 만큼 차이가 난다.
페이지 단위 락 없음. overflow_file.c:77 의 헤더 주석 이 명시한다 — “Overflow pages are not locked in any mode since they are not shared by other pieces of data and its address is only know by accessing the relocation overflow record data which has been appropriately locked.” home 참 조에 걸린 락이 사슬 전체의 access-control 게이트다.
_insert / _update / _delete 마다 system operation 한 개. 다중 페이지 할당이 log_sysop_start / log_sysop_attach_to_outer (commit) 또는 log_sysop_abort (실패) 로 묶여 있다. 외부 트랜잭션 입장에 서 spill 이 atomic 한 한 단계로 보이게 만든다. abort 된 sysop 에서 부분 사슬이 빠져나가는 일은 절대 없다.
MVCC 헤더는 머리 페이지에만 산다 (heap 경로). 첫 overflow 페이지의 레코드 첫 24 바이트 (OR_MVCC_MAX_HEADER_SIZE) 가 가시성 술어가 참조하는 mvcc_rec_header 다. 힙 home 페이지의 REC_BIGONE 슬롯에 는 그것이 없다. big record 의 heap_delete 가 힙 페이지 대신 overflow 페이지를 편집하는 이유가 이것이다 (heap_file.c:21459–21498).

Heap-overflow 경로 — 전체 레이아웃

flowchart LR
  subgraph HEAP["힙 파일 (FILE_HEAP)"]
    HP["힙 페이지\n슬롯 k = REC_BIGONE\n→ {ovf_vpid: VPID, ovf_oid.slotid = NULL_SLOTID}"]
  end
  subgraph OVF["Overflow 파일 (FILE_MULTIPAGE_OBJECT_HEAP)\nVFID = HEAP_HDR_STATS.ovf_vfid"]
    P0["첫 페이지\nOVERFLOW_FIRST_PART {\n  next_vpid → P1,\n  length = 총 바이트,\n  data[ MVCC 헤더 | row body 0..N ]\n}"]
    P1["나머지 페이지\nOVERFLOW_REST_PART {\n  next_vpid → P2,\n  data[ row body N+1..M ]\n}"]
    P2["나머지 페이지\nOVERFLOW_REST_PART {\n  next_vpid = NULL,\n  data[ row body M+1..end ]\n}"]
    P0 --> P1 --> P2
  end
  HP -- "ovf_vpid 가 P0 를 가리킴" --> P0

힙 페이지의 슬롯은 타입 REC_BIGONE 이고, 본문은 OID 다. pageid / volid 가 첫 overflow 페이지 를 가리키고, slotid 는 NULL_SLOTID 다 (heap_file.c:6582 — “slotid = NULL_SLOTID; / Irrelevant /”). overflow 레코드 자 신은 슬롯 디렉토리를 갖지 않는다. 페이지는 VPID 로 주소가 매겨 지고, 레코드 본문은 각 페이지의 data[] 영역을 이어 붙인 연속 byte stream 이다.

Walk: 힙 insert 가 overflow 경로로 떨어지는 흐름

sequenceDiagram
  participant CTX as HEAP_OPERATION_CONTEXT
  participant HI as heap_insert_logical
  participant OVF as heap_ovf_insert
  participant OFI as overflow_insert
  participant FM as file_manager
  participant LM as log_manager

  CTX->>HI: 어떤 힙 페이지에도 안 들어가는 큰 레코드
  HI->>OVF: heap_ovf_insert(hfid, &ovf_oid, recdes)
  OVF->>OVF: heap_ovf_find_vfid(... docreate=true ...)
  alt overflow 파일이 아직 없다면
    OVF->>FM: file_create_with_npages(FILE_MULTIPAGE_OBJECT_HEAP, 1, ...)
    OVF->>LM: log_append_undo/redo RVHF_STATS (heap-header 변경)
    OVF->>OVF: heap_hdr->ovf_vfid := 새 VFID
  end
  OVF->>OFI: overflow_insert(ovf_vfid, &ovf_vpid, recdes, FILE_MULTIPAGE_OBJECT_HEAP)
  OFI->>OFI: npages = ceil((len - first_payload) / rest_payload) + 1
  OFI->>LM: log_sysop_start
  OFI->>FM: file_alloc_multiple(npages, vpids[])
  loop 페이지 i in 0..npages-1
    OFI->>OFI: pgbuf_fix(vpids[i], OLD_PAGE, LATCH_WRITE)
    OFI->>OFI: OVERFLOW_FIRST_PART/REST_PART 헤더 + payload 기록
    alt i == 0 (첫 페이지)
      OFI->>LM: log_append_empty_record(LOG_DUMMY_OVF_RECORD)
    end
    OFI->>LM: log_append_redo_data(RVOVF_NEWPAGE_INSERT, page bytes)
    OFI->>OFI: pgbuf_set_dirty_and_free
  end
  OFI->>LM: log_sysop_attach_to_outer
  OFI-->>OVF: NO_ERROR, ovf_vpid = vpids[0]
  OVF-->>HI: ovf_oid = (vpids[0].volid, vpids[0].pageid, NULL_SLOTID)
  HI->>HI: home 힙 페이지에 ovf_oid 를 들고 있는 REC_BIGONE 레코드 기록

머리에 새겨 둘 두 가지 설계점.

페이지 개수는 사전에 계산된다 (overflow_file.c:112-121). 추정이 아니라 정확한 수다. 산술이 잘못되어 있다면 루프 끝의 assert (length == 0) 가 디버그 빌드에서 발사된다. 공식은 다음과 같다.

// overflow_insert — overflow_file.c (condensed)
length = recdes->length - (DB_PAGESIZE - (int) offsetof (OVERFLOW_FIRST_PART, data));
if (length > 0)
  {
    i = DB_PAGESIZE - offsetof (OVERFLOW_REST_PART, data);
    npages = 1 + CEIL_PTVDIV (length, i);
  }
else
  {
    npages = 1;
  }

루프 안에서 file_alloc 을 부르는 게 아니라 file_alloc_multiple + 페이지별 fix 루프 다. 모든 페이지는 한 개의 log_sysop_start 아래에서 할당된다. 어느 한 페이지 에서 실패하면 sysop 이 abort 되고, 이미 끝난 모든 할당이 함 께 rollback 된다. 호출자가 절반만 만들어진 사슬을 절대 보지 않는 이유가 이것이다.

Walk: big record 의 힙 update

heap_ovf_update (heap_file.c:6597) 가 overflow_update 로 들어가는 특수 케이스 경로다. 흥미로운 동작은 새 이미지가 옛 것 보다 짧거나 길 때 일어난다.

// overflow_update — overflow_file.c (sketch)
log_sysop_start (thread_p);
while (length > 0)
  {
    addr.pgptr = pgbuf_fix (next_vpid, OLD_PAGE, LATCH_WRITE);
    /* compute new copy_length for this page; log undo image */
    log_append_undo_data (RVOVF_PAGE_UPDATE, before-image);
    memcpy (page->data, source, copy_length);
    log_append_redo_data (RVOVF_PAGE_UPDATE, after-image);
    if (length > 0 && VPID_ISNULL (&next_vpid))
      {
        /* extend chain: allocate a new rest-page */
        file_alloc (ovf_vfid, ..., &next_vpid);
        log_append_undoredo_data (RVOVF_NEWPAGE_LINK, ...);
        first_part->next_vpid = next_vpid;   /* or rest_parts->next_vpid */
      }
  }
/* truncate any tail pages no longer needed */
while (!VPID_ISNULL (&next_vpid))
  {
    /* unfix tmp_vpid, file_dealloc it */
  }
log_sysop_attach_to_outer (thread_p);

세 가지 미묘한 지점.

Update 는 FILE_MULTIPAGE_OBJECT_HEAP 에만 허용된다 — 함수 머리에서 (overflow_file.c:398). B+Tree overflow key 는 교체 된다 (delete + insert). update 가 아니다. 따라서 이 경로는 heap big-record 에만 동작한다.
로깅은 분리되어 있다. before-image 에 대한 undo, after-image 에 대한 redo, 그리고 사슬이 늘어날 때마다 RVOVF_NEWPAGE_LINK 의 undo / redo 한 쌍. 사슬이 줄어들 때는 RVOVF_CHANGE_LINK undo / redo 가 발행된다 — 머리의 next_vpid 가 NULL 로 바뀌고 꼬리 페이지들이 차례대로 dealloc 된다.
LOG_DUMMY_OVF_RECORD 가 첫 페이지에서 다시 발행된다 (overflow_file.c:461). HA 복제와 vacuum 이 update 이후에 도 이 사슬이 어떤 페이지에서 시작하는지 다시 식별할 수 있게 하기 위해서다. payload 가 없는 dummy 로그 레코드가 LSN 만 anchor 한다. 복제본은 그 LSN 으로 머리를 찾는다.

Walk: big record 의 힙 delete (MVCC vs non-MVCC)

REC_BIGONE 슬롯에 대한 heap_delete_logical 은 MVCC 모드에 서 overflow_delete 를 직접 부르지 않는다. 대신 첫 overflow 페이지의 MVCC 헤더를 편집한다 (mvcc_del_id 가 그곳 에 살지, 힙 home 페이지에 사는 게 아니다).

// excerpt — heap_file.c around 21459-21498
heap_get_mvcc_rec_header_from_overflow (overflow_page, &overflow_header, NULL);
heap_mvcc_log_delete (thread_p, &log_addr, RVHF_MVCC_DELETE_OVERFLOW);
heap_delete_adjust_header (&overflow_header, mvcc_id, /*is_insid=*/false);
heap_set_mvcc_rec_header_on_overflow (overflow_page, &overflow_header);
pgbuf_set_dirty (overflow_page, DONT_FREE);
heap_mvcc_log_home_no_change (...);   /* 힙 home: 변경 없음, 그러나 vacuum 이 보아야 함 */

home 힙 페이지의 REC_BIGONE 슬롯은 MVCC delete 도중 변경되 지 않는다. vacuum (또는 non-MVCC class delete) 이 이 행 을 실제로 회수하는 시점에 와서야 heap_ovf_delete → overflow_delete → overflow_traverse(OVERFLOW_DO_DELETE) 가 사슬을 걷고 페이지마다 file_dealloc 한다. 그 시점에 힙 home 슬롯이 REC_MARKDELETED / REC_DELETED_WILL_REUSE 로 표시된 다.

Walk: big record 의 힙 read

home 힙 페이지의 REC_BIGONE 슬롯은 작은 forwarding pointer 다 (OID 모양의 12 바이트 payload). 실제 행을 읽으려면 heap_get_visible_version 이 그 포인터를 따라간다.

// heap_get_visible_version — REC_BIGONE branch (sketch)
case REC_BIGONE:
  /* Read forward_oid from the REC_BIGONE slot. */
  /* Apply MVCC visibility against the overflow page's MVCC header. */
  pgptr_ovf = pgbuf_fix (forward_oid, OLD_PAGE, LATCH_READ, ...);
  heap_get_mvcc_rec_header_from_overflow (pgptr_ovf, &mvcc_header, &peek_recdes);
  if (mvcc_satisfies_snapshot(...) != SNAPSHOT_SATISFIED)
    return S_DOESNT_EXIST_OR_WALK_PREV_VERSION_LSA;
  scan = heap_ovf_get (...);  /* 사슬을 호출자의 recdes 로 합쳐 옮긴다 */

heap_ovf_get 은 overflow_get → overflow_get_nbytes (start_offset=0, max_nbytes=-1) 을 호출 자의 MVCC 스냅샷과 함께 호출한다. 가시성 검사는 호출 자리가 아 니라 overflow_get_nbytes 안쪽 에서 일어난다 (overflow_file.c:769-780).

// overflow_get_nbytes — visibility (overflow_file.c:769-780)
if (mvcc_snapshot != NULL)
  {
    MVCC_REC_HEADER mvcc_header;
    heap_get_mvcc_rec_header_from_overflow (pgptr, &mvcc_header, NULL);
    if (mvcc_snapshot->snapshot_fnc (thread_p, &mvcc_header, mvcc_snapshot) == TOO_OLD_FOR_SNAPSHOT)
      {
        pgbuf_unfix_and_init (thread_p, pgptr);
        return S_SNAPSHOT_NOT_SATISFIED;
      }
  }

비대칭에 주목할 가치가 있다 — TOO_OLD_FOR_SNAPSHOT 만 read 를 중단시킨다. TOO_NEW_FOR_SNAPSHOT 레코드는 그대로 반환된 다. 소스의 주석이 그 이유를 설명한다 — “TOO_NEW_FOR_SNAPSHOT records should be accepted, e.g. a recently updated record, locked at select”. 이것이 중요한 이유는, SELECT ... FOR UPDATE 가 미커밋 트랜잭션이 방금 update 한 big record 를 lock 을 걸려면 그 후보 행을 어쨌든 보아야 하기 때문이다.

B+Tree overflow 경로 — 두 개의 다른 모양

B+Tree 모듈은 overflow file 을 두 가지 무관한 용도로 쓴다.

Overflow key — 단일 키가 leaf 또는 non-leaf 레코드의 inline 자리에 다 안 들어갈 만큼 큰 경우 (예 — 긴 문자열 PK). 이 경로는 overflow_file.c 를 사용한다 — 파일 타 입은 FILE_BTREE_OVERFLOW_KEY. 사슬은 키의 직렬화된 DB_VALUE 를 저장한다. heap big-record 가 행 본문을 저장하 는 것과 같은 방식이다.
Overflow OID list — 비-unique 키에 매달린 OID 가 leaf 레코드 inline 자리에 다 들어갈 수 없을 만큼 많은 경우. 이 경로는 overflow_file.c 를 쓰지 않는다. 같은 트리별 파 일 BTID_INT::ovfid 에서 할당된 슬롯 B+Tree 페이지 위에 자 기만의 페이지 형식을 짠다.

둘 다 BTID_INT::ovfid 를 파일 VFID 로 공유한다. B+Tree 마다 한 번 btree_create_overflow_key_file (btree.c:1975) 가 만 든다.

// btree_create_overflow_key_file — btree.c:1975 (condensed)
des.btree_key_overflow.btid = *btid->sys_btid;
des.btree_key_overflow.class_oid = btid->topclass_oid;
file_create_with_npages (thread_p, FILE_BTREE_OVERFLOW_KEY, 3, &des, &btid->ovfid);
heap_get_class_tde_algorithm (&btid->topclass_oid, &tde_algo);
file_apply_tde_algorithm (&btid->ovfid, tde_algo);   /* TDE for at-rest encryption */

파일은 최소 3 페이지 가 미리 할당된 채 만들어지고, 인덱스 의 클래스 단위 TDE 설정을 그대로 물려받는다. overflow-key 사슬 과 overflow-OID-list 사슬이 같은 파일에 거주한다.

Walk: B+Tree overflow OID list

flowchart LR
  subgraph LEAF["Leaf 페이지"]
    LR0["Leaf 레코드:\n[ first_oid (8B) | (cross-class unique 라면 class_oid 8B) |\n  ins_mvccid | del_mvccid | KEY bytes |\n  oid_2 | oid_3 | ... ] |\nLEAF_REC.ovfl → V0"]
  end
  subgraph OVF["키별 overflow 사슬 (BTID_INT::ovfid 안)"]
    V0["Overflow 페이지 V0 (PAGE_BTREE)\n슬롯 0 / HEADER = BTREE_OVERFLOW_HEADER {\n  next_vpid → V1\n}\n슬롯 1 = OID 정렬 레코드:\n[ oid_k | ins_mvccid | del_mvccid | oid_{k+1} | ... ]"]
    V1["Overflow 페이지 V1\n슬롯 0 / HEADER = next_vpid → V2\n슬롯 1 = 더 많은 정렬된 OID"]
    V2["Overflow 페이지 V2\n슬롯 0 / HEADER = next_vpid = NULL\n슬롯 1 = 남은 정렬된 OID"]
    V0 --> V1 --> V2
  end
  LR0 -- "leaf_rec_info.ovfl 가 V0 를 가리킴" --> V0

OID-list overflow 사슬의 성질들.

각 overflow 페이지는 PAGE_BTREE 타입의 슬롯 페이지다 — PAGE_OVERFLOW 가 아니다. btree.c:11606 의 pgbuf_check_page_ptype 가 그것을 확인한다. 이 검사가 OID-list overflow 페이지 (오버플로 레벨에 있을 뿐 여전히 B+Tree 페이지) 를 heap big-record 페이지 (별도의 페이지 타 입) 와 구분해 준다.
슬롯 0 가 BTREE_OVERFLOW_HEADER 를 들고 있다. btree_load.h:244 에서 단일 필드 struct 로 정의되어 있다 (VPID next_vpid). 슬롯 1 이 OID payload 를 들고 있고, binary search 를 위해 OID 로 정렬되어 있다.
MVCC 정보는 OID 마다 항상 OR_MVCC_MAX_HEADER_SIZE 크기 다. Leaf 레코드의 inline OID 는 mvcc_ins_id / mvcc_del_id 가 의미 없을 때 그 필드를 생략할 수 있다. 그러 나 overflow 페이지 안에서는 모든 object 가 두 필드를 모두 들 고 있다. 호출 자리의 assert (btree.c:3994 — “BTREE_MVCC_INFO_HAS_INSID && HAS_DELID”) 가 그것을 강제한 다. 이유는 — OID 단위 binary search 가 고정 크기 레코드를 요 구한다. 공간보다 예측 가능성이 더 가치 있다는 결정이다.
spage_max_space_for_new_record 가 새 OID 가 어디로 갈지 를 결정한다 (btree.c:11609). 사슬을 걷는 btree_find_free_overflow_oids_page 가 BTREE_OBJECT_FIXED_SIZE 바이트만큼 자유 공간이 있는 첫 페 이지에서 멈춘다. 어떤 페이지에도 자리가 없다면 btree_start_overflow_page 가 새 페이지를 할당하고 사슬의 머리에 끼워 넣는다 (새 페이지의 next_vpid 가 옛 첫 overflow 페이지가 되고, LEAF_REC.ovfl 이 새 페이지로 rewrite 된다). append 의 반대다. 새 페이지가 앞으로 가는 이 유는 꼬리까지 걷지 않아도 되기 때문이다.

Walk: overflow 사슬에 OID insert

// excerpt — btree.c around 11340-11423
log_sysop_start (...);
btree_start_overflow_page (btid_int, object_info, first_ovfl_vpid /* old first */,
                           pgbuf_get_vpid_ptr (leaf_page), &ovfl_vpid /* new */, &ovfl_page);
/* btree_start_overflow_page:
 *   - btree_get_new_page → pgbuf_fix(NEW_PAGE)
 *   - ovf_header_info.next_vpid := first_ovfl_vpid (link new page to old chain)
 *   - btree_init_overflow_header → spage_insert_at(HEADER, &ovf_header_info)
 *   - btree_record_append_object → write [oid|ins_mvccid|del_mvccid] into rec
 *   - spage_insert_at(slot 1, &rec)
 *   - log_append_redo_data(RVBT_RECORD_MODIFY_NO_UNDO, full page replay)
 */

LOG_RV_RECORD_SET_MODIFY_MODE (&insert_helper->leaf_addr, LOG_RV_RECORD_UPDATE_PARTIAL);
btree_leaf_record_change_overflow_link (..., &ovfl_vpid, &rv_undo_data_ptr,
                                        &insert_helper->rv_redo_data_ptr);
spage_update (leaf_page, search_key->slotid, leaf_rec);
log_append_undoredo_data (RVBT_RECORD_MODIFY_UNDOREDO, ...);  /* leaf record undo + redo */
log_sysop_end (...);

system-op 괄호가 결정적인 역할을 한다. “새 overflow 페이지 할 당됨 과 leaf 레코드가 그것을 가리킴” 사이에서 서버가 crash 하면, sysop 로그 replay 가 orphan 페이지를 dealloc 한다 (또는 괄호가 log_sysop_end_logical_undo 라면 다시 merge — OID-list 경로는 단순한 commit-on-success / abort-on-failure 를 쓴다). btree.c 의 머리 주석이 이 위험을 지적한다 — “Note that this page may be leaked if server crashes before changing the link in leaf page”. 그래서 새 페이지 할당과 leaf link rewrite 는 같은 sysop 안에 있어야 한다.

Walk: overflow 사슬에서 delete

btree_overflow_remove_object (btree.c:1622) 가 페이지에서 OID 를 지운다. 그것이 페이지를 비우면 사슬을 다시 link 해 주어 야 한다. 두 가지 경우가 있다.

첫 overflow 페이지 — leaf 레코드의 LEAF_REC.ovfl 이 다음 overflow 페이지를 가리키도록 rewrite 되어야 한다 (또 는 사슬이 비면 NULL_VPID). leaf 쪽은 btree_modify_overflow_link 가, overflow 쪽은 btree_overflow_remove_object 가 처리한다.
첫 overflow 가 아닌 페이지 — 이전 overflow 페이지의 BTREE_OVERFLOW_HEADER.next_vpid 가 rewrite 되어야 한다. 이 전 페이지가 제거 대상 페이지와 동시에 fix 되어 있어야 한다. btree_find_oid_and_its_page (btree.c:11646-11772) 가 *found_page 와 *prev_page 를 둘 다 반환해서 이를 가능하 게 한다.

// btree_modify_overflow_link — btree.c:10054 (condensed)
spage_get_record (ovfl_page, HEADER, &overflow_header_record, COPY);   /* undo image */
ovf_header_info.next_vpid := next_ovfl_vpid;
spage_update (ovfl_page, HEADER, &overflow_header_record);             /* new image */
log_append_undoredo_data (RVBT_RECORD_MODIFY_UNDOREDO,
                          ovf_addr,
                          undo (old header), redo (new header));
pgbuf_set_dirty (ovfl_page, DONT_FREE);

RVBT_RECORD_MODIFY_UNDOREDO 는 B+Tree 노드 변경에 쓰이는 통 합 물리 undo / redo 레코드다 — inline leaf insert / delete 에 쓰이는 바로 그것이다. 슬롯 ID 와 modify-mode 플래그 (LOG_RV_RECORD_UPDATE_ALL vs LOG_RV_RECORD_UPDATE_PARTIAL vs LOG_RV_RECORD_INSERT vs LOG_RV_RECORD_DELETE) 로 분기 한다. B+Tree overflow 사슬은 별도의 overflow 전용 레코드 타입 을 만드는 대신 같은 레코드 family 를 다시 쓴다.

Walk: B+Tree overflow key

키 자신이 inline 으로 저장되기에 너무 길 때 또 다른 경로가 적 용된다 — btree_store_overflow_key (btree.c:2020). 키를 pr_type->index_writeval 로 RECDES 에 직렬화한다. 그 RECDES 가 파일 타입 FILE_BTREE_OVERFLOW_KEY 와 함께 overflow_insert 의 입력이 된다.

// btree_store_overflow_key — btree.c:2020 (condensed)
overflow_file_vfid = btid->ovfid;     /* shared with OID-list overflow */
rec.area_size = size;
rec.data = db_private_alloc (size);
or_init (&buf, rec.data, rec.area_size);
pr_type->index_writeval (&buf, key_ptr);
rec.length = (int) (buf.ptr - buf.buffer);

overflow_insert (&overflow_file_vfid, first_overflow_page_vpid, &rec, FILE_BTREE_OVERFLOW_KEY);

leaf 레코드는 이제 키 바이트를 inline 으로 들고 있는 대신 첫 overflow 페이지의 VPID 를 들고 있다. 플래그 (BTREE_LEAF_RECORD_OVERFLOW_KEY) 가 reader 에게 overflow 사 슬을 참조하라고 알린다. btree_load_overflow_key (btree.c:2131) 가 read 경로다.

// btree_load_overflow_key — btree.c:2131 (condensed)
rec.area_size = overflow_get_length (thread_p, first_overflow_page_vpid);
rec.data = db_private_alloc (rec.area_size);
overflow_get (thread_p, first_overflow_page_vpid, &rec, NULL);    /* mvcc_snapshot=NULL */
or_init (&buf, rec.data, rec.length);
pr_type->index_readval (&buf, key, btid->key_type, -1, /*copy=*/true, NULL, 0);

두 가지 설계점.

overflow_get 호출의 mvcc_snapshot=NULL — overflow key 는 MVCC 정보를 들고 있지 않다. 그 키에 매달린 OID 의 가시성 이 키가 보일지 말지를 결정한다. 키 바이트 자체는 leaf 엔트리 가 존재하는 동안 MVCC-invariant 다.
키는 overflow 레코드에서 항상 복사 되어 나온다 (copy=true). inline key 는 leaf latch 아래에서 zero-copy peek 이 가능하지만, overflow key 는 index_readval 이 반환 되기 전에 페이지가 unfix 되기 때문에 DB_VALUE 로 일단 materializing 해야 한다.

btree_delete_overflow_key (btree.c:2202) 는 leaf 레코드를 읽어 첫 overflow VPID 를 추출하고 overflow_delete 를 부른다. leaf 레코드의 슬롯은 지우지 않는다 — 그것은 호출자의 일이다.

Crash recovery — 네 종류의 로그 레코드

overflow file 은 네 종류의 레코드를 발행한다. 모두 recovery.h:100-103 에 정의되어 있다.

코드	발행 시점	Redo 핸들러
`RVOVF_NEWPAGE_INSERT`	`overflow_insert` 동안 페이지마다 — 전체 페이지 redo 이미지	`overflow_rv_newpage_insert_redo` → `log_rv_copy_char`
`RVOVF_NEWPAGE_LINK`	`overflow_update` 가 사슬을 연장할 때	Undo: `overflow_rv_newpage_link_undo` (next_vpid := NULL); Redo: `overflow_rv_link` (next_vpid := )
`RVOVF_PAGE_UPDATE`	`overflow_update` 동안 페이지마다 — undo + redo 이미지	Redo: `overflow_rv_page_update_redo` (ptype 설정, byte 복사); undo는 페이지 byte image
`RVOVF_CHANGE_LINK`	`overflow_update` 가 사슬을 줄일 때	`RVOVF_NEWPAGE_LINK` 와 같은 핸들러

LOG_DUMMY_OVF_RECORD 는 RV* family 에 속하지 않는다 — zero-length 로그 레코드로, 단 하나의 목적은 LSN 을 anchor 해서 HA 복제와 vacuum_master 가 이 페이지가 사슬의 머리다 라고 인식할 수 있게 하는 것이다. 첫 페이지에서만 발행된다 (insert 시 overflow_file.c:202, update 시 :461). redo / undo 함수 가 없다. 이 LSN 을 관찰한 복제본은 page-LSN 을 다시 조회해 머 리 페이지를 식별한다.

flowchart TB
  subgraph INSERT["overflow_insert"]
    II1["log_sysop_start"]
    II2["file_alloc_multiple\n(npages)"]
    II3["페이지 i 마다:\ni==0 에서 LOG_DUMMY_OVF_RECORD\n매 페이지에서 RVOVF_NEWPAGE_INSERT"]
    II4["log_sysop_attach_to_outer\n(commit / 실패 → abort)"]
    II1 --> II2 --> II3 --> II4
  end
  subgraph UPDATE["overflow_update"]
    UU1["log_sysop_start"]
    UU2["손댄 페이지마다:\nRVOVF_PAGE_UPDATE undo+redo\n연장이면 RVOVF_NEWPAGE_LINK\n첫 페이지에 LOG_DUMMY_OVF_RECORD"]
    UU3["축소 시:\nRVOVF_CHANGE_LINK undoredo\n그 다음 꼬리 페이지 file_dealloc"]
    UU4["log_sysop_attach_to_outer\n(commit / 실패 → abort)"]
    UU1 --> UU2 --> UU3 --> UU4
  end
  subgraph DELETE["overflow_delete"]
    DD1["overflow_traverse(OVERFLOW_DO_DELETE)"]
    DD2["페이지마다:\npgbuf_unfix\nfile_dealloc(vpid) — 페이지별 로그 레코드 없음\n(file manager가 dealloc 자체를 logging)"]
    DD1 --> DD2
  end

비대칭에 주목하자 — insert 와 update 는 RVOVF_* 레코드를 발 행하고, delete 는 발행하지 않는다. 삭제가 페이지마다 file_dealloc 로 구현되어 있고, file manager 가 자기 RV*_FILE_* 레코드 family 로 페이지 dealloc 자체를 logging 하기 때문이다. overflow_file.c 가 file_dealloc 이 이미 하는 것 위에 무엇을 더 logging 할 필요가 없다.

Vacuum 과의 상호작용

Heap big-record 의 경우, vacuum 이 vacuum_heap_page 안 에서 home 힙 페이지 사슬을 방문한다. 가시성이 “모두에게 delete-visible” 인 REC_BIGONE 슬롯 (즉, overflow 페이지의 mvcc_del_id 가 가장 오래된 활성 스냅샷보다 더 오래된 경우) 을 만나면 heap_ovf_delete 를 부른다. 그 호출이 overflow 사슬 을 free 한다. home 슬롯은 REC_MARKDELETED / REC_DELETED_WILL_REUSE 로 전환된다.

B+Tree overflow OID list 의 경우, vacuum 이 B+Tree 리프를 방문해서 mvcc_del_id 가 충분히 오래된 OID 마다 btree_overflow_remove_object (또는 그 in-leaf 형제) 를 부른 다. 그것이 overflow 페이지를 비우면 페이지가 unlink 되고, btree_modify_overflow_link 와 file-manager 호출로 file_dealloc 된다. overflow 파일의 페이지는 같은 B+Tree 의 이후 insert 가 다시 쓴다 — 트리를 가로질러서는 절대 다시 쓰지 않는다.

B+Tree overflow key 의 경우, vacuum 은 특별한 역할이 없다. 키 사슬은 그것을 들고 있는 leaf 레코드가 지워질 때만 free 된 다 — btree_delete_overflow_key → overflow_delete 경로다. leaf 레코드는 DDL (key-type 변경, drop-index) 또는 row-delete

collapse-merge 로 지워진다. 따라서 MVCC 지연이 없다.

`OVERFLOW_FIRST_PART::length` 가 중요한 이유

머리 페이지에만 사는 length 필드를 두 호출자가 의지한다.

overflow_get_length (overflow_file.c:692) — O(1) 질 의다. 머리 fix, 필드 read, unfix 로 끝난다. btree_load_overflow_key 가 첫 read 이전에 목적지 버퍼 크기를 잡으려고 이 질의를 쓴다.
overflow_get_capacity (overflow_file.c:935) — 총 byte, 페이지 수, 헤더 overhead, 마지막 페이지의 자유 공간을 보고한다. 진단 dump 와 capacity planning 에 쓰인다. 이 walker 는 length 를 써서 몇 개 페이지를 traverse 할지 결 정한다. NULL next_vpid 까지 걸어가라 가 아니다. 그래서 사슬이 corrupt 되어 있다면 (예 — length 바이트가 다 소비 되기 전에 NULL link 가 나타남) 명시적인 에러로 끊어진다. silent truncation 이 일어나지 않는다.

trade-off 는 overflow_update 가 resize 동안 length 를 정확 히 유지해야 한다는 것이다. 새 길이가 더 짧은 경우까지 포함한다 (overflow_file.c:563-588 의 update 후 truncation 루프가 그것 을 잡아낸다). 새 길이가 한 페이지보다 작아도 첫 OVERFLOW_FIRST_PART 페이지는 항상 유지된다 — 사슬은 1 페이지 아래로 줄지 않는다. 머리를 지우면 힙 home 레코드의 REC_BIGONE 참조가 무효화되기 때문이다.

페이지 타입 규율

overflow file 은 호출자에 따라 두 가지 다른 페이지 타입을 쓴 다.

Heap big-record 와 B+Tree overflow key 는 PAGE_OVERFLOW 타입의 페이지를 할당한다. overflow_insert 가 새 페이지를 file_init_page_type (또는 FILE_TEMP 의 경 우 file_init_temp_page_type) 으로 초기화하고 ptype = PAGE_OVERFLOW 를 설정한다. read 는 pgbuf_check_page_ptype (..., PAGE_OVERFLOW) 로 검증한다. 이 페이지 타입이 buffer pool 레이어에 “이 페이지는 보통 의미 의 슬롯 페이지가 아니다 — 본문이 raw OVERFLOW_FIRST_PART / OVERFLOW_REST_PART 헤더 + 연속 데이터지, 슬롯 디렉토리 + 레코드가 아니다” 라고 알리는 신호다.
B+Tree overflow OID list 는 PAGE_BTREE 타입을 할당한다 — leaf 와 non-leaf 페이지와 같은 타입이다. 슬롯 페이지 다 (슬롯 0 = BTREE_OVERFLOW_HEADER, 슬롯 1 = OID 레코드). 표 준 슬롯 페이지 invariant 가 그대로 적용된다.

이 차이가 두 B+Tree overflow 경로가 무관함을 보여 주는 가장 깨 끗한 신호다 — OID-list overflow 사슬은 “depth N+1 에 있는 더 많은 B+Tree 페이지” 일 뿐이고, overflow-key 사슬은 디스크상 레 이아웃을 heap big-record 와 공유한다.

소스 코드 가이드

anchor 는 심볼명 이다. 라인은 흘러 간다. 현재 위치를 잡 으려면 git grep -n '<symbol>' src/storage/ 를 쓴다. 아래 위치 힌트 표는 이 개정 시점에 관찰된 라인이다.

타입 정의

struct overflow_first_part (overflow_file.h) — 머리 페이 지 형식: next_vpid + length + data[1].
struct overflow_rest_part (overflow_file.h) — 나머지 페 이지 형식: next_vpid + data[1].
enum OVERFLOW_DO_FUNC { OVERFLOW_DO_DELETE, OVERFLOW_DO_FLUSH } (overflow_file.c) — 공유 traversal worker 의 discriminator.
BTREE_OVERFLOW_HEADER (btree_load.h:244) — 단일 next_vpid 필드. B+Tree OID-overflow 페이지의 슬롯 0 에 산 다.
파일 타입 상수 FILE_TEMP, FILE_BTREE_OVERFLOW_KEY, FILE_MULTIPAGE_OBJECT_HEAP (file_manager.h) — overflow_insert 가 받는 세 가지 파일 타입.
페이지 타입 상수 PAGE_OVERFLOW, PAGE_BTREE (page_buffer.h) — heap-big-record / overflow-key 페이지를 B+Tree OID-list 페이지와 구분한다.
WAL 코드 RVOVF_NEWPAGE_INSERT, RVOVF_NEWPAGE_LINK, RVOVF_PAGE_UPDATE, RVOVF_CHANGE_LINK (recovery.h:100-103).

Public API (`src/storage/overflow_file.c`)

overflow_insert — 다중 페이지 할당 + 페이지별 write + 페이 지별 redo 로그 한 sysop 안. 페이지 수 사전 계산.
overflow_update — 사슬 연장 / 축소 / 덮어쓰기. FILE_MULTIPAGE_OBJECT_HEAP 을 assert (heap 전용 경로).
overflow_delete — overflow_traverse(OVERFLOW_DO_DELETE) wrapper.
overflow_flush — overflow_traverse(OVERFLOW_DO_FLUSH) wrapper.
overflow_get — overflow_get_nbytes(0, -1, ...) 의 편의 wrapper.
overflow_get_nbytes — start offset 과 max length 가 있는 부분 read. 머리 페이지에서 MVCC 가시성 적용.
overflow_get_length — O(1) 총 바이트 질의 (머리 페이지 만).
overflow_get_capacity — 사슬 전체 walk. 크기, 페이지 수, overhead, 자유 공간 보고.
overflow_get_first_page_data — 첫 페이지의 data[] 영역에 대한 포인터 (heap_get_mvcc_rec_header_from_overflow 가 사 용).

내부 helper (`src/storage/overflow_file.c`)

overflow_next_vpid — 다음 페이지 link read. 타입 인지 (head vs rest).
overflow_traverse — walk-and-call-callback worker. delete 와 flush 가 공유.
overflow_delete_internal — 페이지 단위 dealloc (file_dealloc).
overflow_flush_internal — 페이지 단위 WAL flush (pgbuf_flush_with_wal).

Recovery (`src/storage/overflow_file.c`)

overflow_rv_newpage_insert_redo — log_rv_copy_char 로 전 체 페이지 redo.
overflow_rv_newpage_link_undo — 연결 대상 페이지의 next_vpid 를 NULL 로 — 사슬 연장의 undo.
overflow_rv_link — next_vpid := <data> 설정. RVOVF_NEWPAGE_LINK (연장) 와 RVOVF_CHANGE_LINK (축소) 둘 다의 redo 로 동작.
overflow_rv_link_dump — next_vpid 로그 레코드 진단 dump.
overflow_rv_page_update_redo — 페이지 타입 (PAGE_OVERFLOW) 설정 + log_rv_copy_char 로 byte 복사.
overflow_rv_page_dump — RVOVF_PAGE_UPDATE 레코드의 진단 dump.

Heap 쪽 wrapper (`src/storage/heap_file.c`)

heap_ovf_find_vfid — HEAP_HDR_STATS.ovf_vfid 에서 힙의 overflow 파일 VFID 를 가져온다 / 만든다. docreate=true 면 sysop 안에서 FILE_MULTIPAGE_OBJECT_HEAP 을 만들고, 클래스 메타데이터에서 TDE 알고리즘을 적용하고, 힙 헤더 변경을 RVHF_STATS undo / redo 를 logging.
heap_ovf_insert — overflow_insert(..., FILE_MULTIPAGE_OBJECT_HEAP) 을 wrap. 반환된 VPID 를 slotid = NULL_SLOTID 인 OID 로 변환해 home 페이지의 REC_BIGONE 본문에 넣는다.
heap_ovf_update — overflow_update(..., FILE_MULTIPAGE_OBJECT_HEAP) wrap.
heap_ovf_delete — overflow_delete wrap. ovf_vfid_p 가 NULL 이면 heap_ovf_find_vfid 로 lookup.
heap_ovf_flush / heap_ovf_get_length / heap_ovf_get / heap_ovf_get_capacity — 대응하는 overflow_* 함수의 직접 wrapper.
heap_get_mvcc_rec_header_from_overflow — 머리 페이지의 data[] 에서 MVCC 헤더 peek (overflow_get_first_page_data 사용).
heap_set_mvcc_rec_header_on_overflow — MVCC 헤더 write back. 모든 플래그가 아직 세팅되지 않은 레코드에서도 항상 OR_MVCC_MAX_HEADER_SIZE 를 강제한다 — 빠진 INSID 자리에 MVCCID_ALL_VISIBLE 을 채우고, 빠진 DELID 자리에 MVCCID_NULL 을 채운다. 이 forced-max-size invariant 가 mvcc_header_size_lookup 으로 in-place update 비용을 예측 가능하게 만든다.
heap_get_bigone_content — big record 를 RECDES 로 읽는 다. scan_cache 기반 버퍼 재사용을 옵션으로 지원.

B+Tree 쪽 overflow-key wrapper (`src/storage/btree.c`)

btree_create_overflow_key_file — FILE_BTREE_OVERFLOW_KEY 를 만들고 VFID 를 BTID_INT::ovfid 에 저장. ≥ 3 페이지 미리 할당, TDE 적용.
btree_store_overflow_key — DB_VALUE 키를 RECDES 로 직 렬화. overflow_insert(... FILE_BTREE_OVERFLOW_KEY) 호출. 머리 VPID 반환.
btree_load_overflow_key — 머리의 length 를 read, 할당, overflow_get(... NULL) 호출, DB_VALUE 로 deserialize.
btree_delete_overflow_key — leaf / non-leaf 레코드에 박혀 있는 머리 VPID 를 찾아 overflow_delete 호출.

B+Tree 쪽 overflow-OID-list helper (`src/storage/btree.c`)

btree_start_overflow_page — 새 B+Tree 페이지 (PAGE_BTREE) 할당, BTREE_OVERFLOW_HEADER 초기화, 슬롯 1 에 새 object append, 사슬 머리에 새 페이지 link (new → old-first).
btree_modify_overflow_link — overflow 페이지 헤더의 next_vpid rewrite. RVBT_RECORD_MODIFY_UNDOREDO 발행.
btree_find_free_overflow_oids_page — 사슬을 walk, 자리 있 는 첫 페이지를 반환. 없으면 NULL.
btree_find_oid_and_its_page — 주어진 (key, OID) 쌍을 들 고 있는 페이지 (leaf 또는 overflow) 를 찾는다. 호출자가 직전 페이지의 link 를 rewrite 할 수 있도록 옵션으로 이전 페이지도 반환.
btree_find_oid_from_ovfl — 한 overflow 페이지의 슬롯 1 레 코드에서 OID 를 binary search (OID 로 정렬되어 있음).
btree_overflow_remove_object — overflow 페이지에서 OID 를 물리적으로 제거. 페이지가 비면 dealloc 후 re-link.
btree_overflow_record_replace_object — 한 OID 를 다른 OID 로 교체 (unique 제약 유지와 FK 가 사용).
btree_get_next_overflow_vpid (btree_load.c) — fix 된 페 이지에서 BTREE_OVERFLOW_HEADER.next_vpid 를 read.
btree_get_overflow_header (btree_load.c) — overflow 페이 지의 HEADER 슬롯 peek.
btree_init_overflow_header (btree_load.c) — btree_start_overflow_page 동안 overflow 페이지의 HEADER 슬롯에 write.

이 개정 시점의 위치 힌트

이 라인 번호들은 문서가 마지막으로 updated: 된 시점에 관찰된 값이다. 심볼이 권위를 갖는다. 라인은 흘러 간다.

심볼	파일	라인
`struct overflow_first_part`	`overflow_file.h`	38
`struct overflow_rest_part`	`overflow_file.h`	46
`enum OVERFLOW_DO_FUNC`	`overflow_file.c`	45
`overflow_insert`	`overflow_file.c`	81
`overflow_next_vpid`	`overflow_file.c`	275
`overflow_traverse`	`overflow_file.c`	296
`overflow_update`	`overflow_file.c`	373
`overflow_delete_internal`	`overflow_file.c`	613
`overflow_delete`	`overflow_file.c`	644
`overflow_flush_internal`	`overflow_file.c`	655
`overflow_flush`	`overflow_file.c`	677
`overflow_get_length`	`overflow_file.c`	691
`overflow_get_nbytes`	`overflow_file.c`	738
`overflow_get`	`overflow_file.c`	916
`overflow_get_capacity`	`overflow_file.c`	934
`overflow_rv_newpage_insert_redo`	`overflow_file.c`	1112
`overflow_rv_newpage_link_undo`	`overflow_file.c`	1124
`overflow_rv_link`	`overflow_file.c`	1144
`overflow_rv_page_update_redo`	`overflow_file.c`	1178
`overflow_get_first_page_data`	`overflow_file.c`	1217
`RVOVF_NEWPAGE_INSERT` 등	`recovery.h`	100
`BTREE_OVERFLOW_HEADER`	`btree_load.h`	244
`btree_get_overflow_header`	`btree_load.c`	339
`btree_init_overflow_header`	`btree_load.c`	575
`btree_get_next_overflow_vpid`	`btree_load.c`	674
`btree_create_overflow_key_file`	`btree.c`	1975
`btree_store_overflow_key`	`btree.c`	2020
`btree_load_overflow_key`	`btree.c`	2131
`btree_delete_overflow_key`	`btree.c`	2202
`btree_start_overflow_page`	`btree.c`	3973
`btree_modify_overflow_link`	`btree.c`	10054
`btree_find_free_overflow_oids_page`	`btree.c`	11579
`btree_find_oid_and_its_page`	`btree.c`	11646
`btree_find_oid_from_ovfl`	`btree.c`	12037
`heap_ovf_find_vfid`	`heap_file.c`	6462
`heap_ovf_insert`	`heap_file.c`	6568
`heap_ovf_update`	`heap_file.c`	6597
`heap_ovf_delete`	`heap_file.c`	6632
`heap_get_mvcc_rec_header_from_overflow`	`heap_file.c`	19541
`heap_set_mvcc_rec_header_on_overflow`	`heap_file.c`	19567
`heap_get_bigone_content`	`heap_file.c`	19610

소스 검증 노트

overflow_update 는 heap 전용이다. overflow_file.c:398 의 assert (file_type == FILE_MULTIPAGE_OBJECT_HEAP) 가 다 른 파일 타입 (FILE_BTREE_OVERFLOW_KEY 포함) 을 거부한다. B+Tree overflow key 는 in-place update 가 안 된다. 호출자는 옛 사슬을 overflow_delete 한 뒤 새 사슬을 overflow_insert 해야 한다 — 작은 편집이라도 그렇다. heap 경로가 특권을 갖는 이유는, 행 본문의 MVCC update 흐름이 이미 “기존 사슬을 연장 하거나 축소하면서 in-place 로 편집한다” 를 함의하고, 데이터 를 두 번 (delete + insert) 두는 것은 WAL 비용이 두 배가 되기 때문이다.
B+Tree OID-list overflow 페이지는 PAGE_OVERFLOW 가 아니 라 PAGE_BTREE 다. btree.c:11606 의 pgbuf_check_page_ptype 이 OID-list 경로가 overflow_file.c 를 사용하지 않는다 는 점을 가장 쉽게 확인하는 자리다. overflow-key 경로는 그것을 쓰고, overflow_insert 안의 file_init_page_type 에서 PAGE_OVERFLOW 페이지를 받는다.
OVERFLOW_FIRST_PART::length 는 overflow-file 레이어가 계 산하고 유지한다. 호출자가 아니다. 호출자는 들어오는 recdes->length 와 나가는 recdes->length 만 본다 — 내부 필드는 사적이다.
LOG_DUMMY_OVF_RECORD 에는 payload 가 없다. 사슬의 머리 페이지를 식별하기 위해 HA 복제와 vacuum 이 사용하는 LSN anchor 일 뿐이다. 이걸 제거해도 복구 자체는 깨지지 않는다 (사슬은 자기 redo 가 완전하다). 그러나 LSN 으로 자기 위치를 잡는 복제 측이 깨진다.
Heap big-record 의 MVCC delete 는 힙 home 페이지가 아니라 overflow 페이지를 편집한다. home 의 REC_BIGONE 슬롯은 vacuum / non-MVCC class delete 시점에만 변경된다. REC_HOME 레코드와의 구조적 차이가 이것이다 — REC_HOME 은 MVCC 헤더 가 힙 슬롯 안에 inline 으로 산다.
페이지 단위 락 부재는 의도된 최적화다. overflow_file.c:77-79 의 주석 블록이 invariant 를 문서화한 다 — 각 사슬이 한 논리 레코드에만 사적이고, 그 레코드의 상위 락 (행 락 또는 키 range 락) 이 사슬 전체를 보호한다. 그래서 lock manager 를 거치지 않고 overflow 페이지에 pgbuf_fix(PGBUF_LATCH_WRITE) 를 걸 수 있다.

미해결 질문

overflow_update 가 사슬의 split 을 유발할 수 있는가? 사슬은 단방향이라, 레코드를 키우는 update 는 꼬리에 페이지 를 덧붙이거나 in-place 로 늘리는 것뿐이어야 할 것이다. 그러 나 overflow_file.c:511-541 의 코드에는 next_vpid 가 NULL 인데 아직 남은 byte 가 있는 경우에 사슬 중간에 새 페이 지를 할당하는 듯한 분기가 있다. 추적 경로 — 결과 사슬이 항 상 꼬리-연장인지, 아니면 mid-chain 삽입이 가능한지 trace 해 볼 것.
overflow_delete_internal 이 왜 file_dealloc 에 FILE_UNKNOWN_TYPE 을 넘기는가? overflow_file.c:621 의 TODO 주석이 이를 명확히 해야 할 사항으로 표시한다. file manager 가 디스크의 file descriptor 에서 실제 타입을 lookup 하는 것 같지만, 그것을 검증하고 TODO 를 제거하는 것이 작은 cleanup 이 될 것이다. 추적 경로 — file_dealloc 시그니처와 FILE_UNKNOWN_TYPE 동작.
overflow_insert 의 FILE_TEMP 사용 케이스. overflow_file.c:102 의 valid-types assert 가 FILE_TEMP (sort files 설명) 를 받는다. CUBRID 어디에서 외부 sort 가 overflow_insert 로 다중 페이지 레코드를 쓰는가? 이 경로가 btree_load.c 의 sort phase 에도, query_executor.c 에도 보이지 않는다. 추적 경로 — FILE_TEMP 인자를 가진 overflow_insert 호출자를 grep.
B+Tree OID-list overflow 페이지에 대한 TDE 적용 여부. TDE 알고리즘은 btree_create_overflow_key_file 시점에 BTID_INT::ovfid 에 한 번 적용된다. overflow-key 와 OID-list 페이지가 모두 이 파일에 산다. OID-list 페이지가 실 제로 at-rest 암호화되는가, 아니면 암호화 hook 이 PAGE_OVERFLOW 만 keying 하기 때문에 PAGE_BTREE 인 OID-list 페이지를 건너뛰는가? 추적 경로 — pgbuf_dealloc_page / disk_page_write 의 TDE 경로와 PAGE_* discriminator.
heap_ovf_update 와 동시 reader 간 동시성. reader 는 머리 페이지를 먼저 fix 해 length 를 read 한 뒤 사슬을 walk 한다 — 그러나 각 rest-page fix 는 독립적이다. heap_ovf_update 가 reader 의 페이지 N fix 와 페이지 N+1 fix 사이에 사슬을 줄인다면, reader 가 dealloc 된 페이지를 fix 할 수도 있을까? reader 가 들고 있는 행 단위 락이 그것 을 막는가, 아니면 page-buffer 의 pin-count 가 dealloc 을 막 는가? 추적 경로 — X 행 락 또는 SELECT FOR UPDATE 아래에서 동시에 file_dealloc 되는 페이지에 pgbuf_fix 를 trace.
B+Tree overflow-key 의 MVCC. 코드는 overflow key 를 read 할 때 mvcc_snapshot=NULL 을 넘긴다 — 키가 leaf 엔트 리의 수명 동안 MVCC-invariant 라는 가정 위에서다. 그러나 leaf 엔트리 자체는 OID 마다 자기 MVCC 정보를 들고 있다. 한 키의 모든 OID 가 vacuum 되면 leaf 엔트리가 제거되고 overflow-key 사슬이 free 된다. 스냅샷 reader 가 동시에 free 되고 있는 overflow-key 사슬을 가진 leaf 엔트리를 관찰하는 window 가 있을까? 추적 경로 — vacuum 의 leaf-purge 경로와 btree_delete_overflow_key 와의 ordering.

출처

이 문서는 Code-only (sources: []) 다. 모든 자료는 아래의 CUBRID 소스 트리에서 distill 되었다. 슬라이드 데크, 원본 분석 PDF, 외부 write-up 은 사용하지 않았다.

CUBRID 소스 (`/data/hgryoo/references/cubrid/`)

src/storage/overflow_file.h
src/storage/overflow_file.c
src/storage/heap_file.c (heap_ovf_*, heap_get_mvcc_rec_header_from_overflow, heap_set_mvcc_rec_header_on_overflow, REC_BIGONE 처리는 7527–7873 행과 21420–21504 행 부근)
src/storage/btree.c (btree_create_overflow_key_file, btree_store_overflow_key, btree_load_overflow_key, btree_delete_overflow_key, btree_start_overflow_page, btree_modify_overflow_link, btree_find_free_overflow_oids_page, btree_find_oid_and_its_page, btree_find_oid_from_ovfl)
src/storage/btree_load.h (BTREE_OVERFLOW_HEADER)
src/storage/btree_load.c (btree_get_overflow_header, btree_init_overflow_header, btree_get_next_overflow_vpid)
src/storage/file_manager.h (FILE_MULTIPAGE_OBJECT_HEAP, FILE_BTREE_OVERFLOW_KEY, FILE_TEMP)
src/transaction/recovery.h (RVOVF_NEWPAGE_INSERT, RVOVF_NEWPAGE_LINK, RVOVF_PAGE_UPDATE, RVOVF_CHANGE_LINK)

이 지식 베이스의 형제 문서

knowledge/code-analysis/cubrid/cubrid-heap-manager.md — 슬롯 페이지 substrate, REC_BIGONE 레코드 타입, HEAP_HDR_STATS::ovf_vfid 의 위치.
knowledge/code-analysis/cubrid/cubrid-btree.md — 세 종류 레코드 레이아웃 (NON_LEAF_REC, LEAF_REC, overflow), BTID_INT::ovfid, 그리고 unique 강제의 일꾼인 btree_find_oid_and_its_page.
knowledge/code-analysis/cubrid/cubrid-mvcc.md — mvcc_rec_header 레이아웃과 overflow_get_nbytes 가 부르는 가시성 술어.
knowledge/code-analysis/cubrid/cubrid-page-buffer-manager.md — pgbuf_fix 규율과 PAGE_OVERFLOW / PAGE_BTREE 페이지 타입 검사.
knowledge/code-analysis/cubrid/cubrid-log-manager.md — log_sysop_start / log_sysop_attach_to_outer / log_sysop_abort 의 system-op semantics, RVOVF_* 레코드 family 와 WAL 의 상호작용, 그리고 LOG_DUMMY_OVF_RECORD 가 HA 복제에서 하는 역할.

교재 챕터 (`knowledge/research/dbms-general/`)

Database Internals (Petrov), 3장 §File Formats, §Variable-Size Records — 슬롯 페이지, forwarding, 그리고 out-of-line overflow 라는 세 가지 고전적 전략.
Database Systems: The Complete Book (Garcia-Molina, Ullman, Widom), §13.7 “Variable-Length Data and Records” — in-line forwarding 과 out-of-line overflow 의 trade-off.
Comer (1979), The Ubiquitous B-Tree (ACM CSUR) — 키별 OID 리스트와 overflow chain 의 아이디어가 B+Tree 보다 앞선다.