Split View: 데이터베이스 내부 구조 완전 가이드 2025: 스토리지 엔진, B-Tree, LSM-Tree, MVCC, WAL

데이터베이스 내부 구조 전체 아키텍처
============================================

  Client Query
       |
       v
  [SQL Parser] --> [Query Optimizer] --> [Execution Engine]
       |                                        |
       v                                        v
  [Buffer Pool / Cache]              [Transaction Manager]
       |                                        |
       v                                        v
  [Storage Engine]                    [Lock Manager + MVCC]
       |
       +---> [B-Tree Index]  (페이지 지향)
       +---> [LSM-Tree]      (로그 구조)
       |
       v
  [WAL (Write-Ahead Log)]
       |
       v
  [Disk (데이터 파일 + 로그 파일)]

페이지 지향 스토리지 구조
=========================

  [Page 0: File Header]
  [Page 1: B-Tree Root]
  [Page 2: B-Tree Internal]
  [Page 3: B-Tree Leaf (data)]
  [Page 4: B-Tree Leaf (data)]
  [Page 5: Free Space Map]
  ...
  [Page N: B-Tree Leaf (data)]

  각 페이지 내부 구조:
  +----------------------------------+
  | Page Header (LSN, checksum, ...) |
  | Slot Array (오프셋 포인터)        |
  |         ...free space...          |
  | Tuple 3 | Tuple 2 | Tuple 1     |
  +----------------------------------+

로그 구조 스토리지 구조
=======================

  Write Path:
  [Client Write] --> [MemTable (in-memory, sorted)]
                          |
                     (flush when full)
                          |
                          v
                    [SSTable L0] (immutable, sorted)
                    [SSTable L0]
                          |
                     (compaction)
                          |
                          v
                    [SSTable L1] (merged, sorted)
                          |
                     (compaction)
                          |
                          v
                    [SSTable L2] (larger, sorted)

B-Tree 구조 (order = 4)
========================

              [  30  |  60  ]           <-- Root Node
             /       |       \
            v        v        v
     [10|20]    [40|50]    [70|80|90]   <-- Internal Nodes
     / | \      / | \      / |  |  \
    v  v  v    v  v  v    v  v  v   v
   [1] [15] [25] [35] [45] [55] [65] [75] [85] [95]  <-- Leaf Nodes
    5   17   28   38   48   58   68   78   88   98
    8   19        39        59        79        99

노드 분할 과정 (order = 4, 키 25 삽입)
========================================

Before:
  Parent: [20 | 40]
  Child:  [21 | 23 | 24]  (full!)

Step 1: 25를 삽입하면 overflow
  Temp:  [21 | 23 | 24 | 25]

Step 2: 중간값(23)을 부모로 올림
  Parent: [20 | 23 | 40]
  Left:   [21]
  Right:  [24 | 25]

After:
         [20 | 23 | 40]
        /    |     |    \
     ...  [21]  [24|25]  ...

B+Tree 구조
============

  Internal Nodes: 키만 저장 (데이터 없음)
              [30 | 60]
             /    |    \
            v     v     v
  Leaf:  [10|20|30] --> [40|50|60] --> [70|80|90]
          data          data           data

  핵심 차이:
  - B-Tree: 모든 노드에 데이터 저장
  - B+Tree: 리프 노드에만 데이터 저장
  - B+Tree: 리프 노드가 연결 리스트로 연결 (범위 스캔 최적화)

클러스터드 인덱스 (InnoDB Primary Key)
======================================

  B+Tree 리프 = 실제 테이블 데이터
  
  [PK: 1] --> {id:1, name:'Alice', age:30}
  [PK: 2] --> {id:2, name:'Bob',   age:25}
  [PK: 3] --> {id:3, name:'Carol', age:35}

논클러스터드 인덱스 (Secondary Index)
======================================

  B+Tree 리프 = 프라이머리 키 참조
  
  [name:'Alice'] --> PK: 1  (다시 클러스터드 인덱스 조회 필요!)
  [name:'Bob']   --> PK: 2
  [name:'Carol'] --> PK: 3

LSM-Tree 전체 구조
==================

  [Write Request]
       |
       v
  [WAL (디스크)] <--- 장애 복구용 선행 기록
       |
       v
  [MemTable (메모리)]  <--- Red-Black Tree 또는 Skip List
       |
  (MemTable이 임계값 도달)
       |
       v
  [Immutable MemTable]
       |
  (디스크로 flush)
       |
       v
  [Level 0 SSTables]  <--- 키 범위 겹칠 수 있음
       |
  (Compaction)
       |
       v
  [Level 1 SSTables]  <--- 키 범위 겹치지 않음
       |
  (Compaction)
       |
       v
  [Level 2 SSTables]  <--- 더 큰 파일들
       |
       ...

// MemTable 구현 예시 (Skip List 기반)
class MemTable {
    private final ConcurrentSkipListMap<byte[], byte[]> data;
    private final AtomicLong approximateSize;
    private static final long FLUSH_THRESHOLD = 64 * 1024 * 1024; // 64MB

    public void put(byte[] key, byte[] value) {
        data.put(key, value);
        approximateSize.addAndGet(key.length + value.length);
    }

    public byte[] get(byte[] key) {
        return data.get(key);
    }

    public boolean shouldFlush() {
        return approximateSize.get() >= FLUSH_THRESHOLD;
    }

    // MemTable -> SSTable 변환
    public SSTable flush(String sstablePath) {
        SSTableBuilder builder = new SSTableBuilder(sstablePath);
        for (Map.Entry<byte[], byte[]> entry : data.entrySet()) {
            builder.add(entry.getKey(), entry.getValue());
        }
        return builder.build(); // 정렬된 상태로 디스크에 기록
    }
}

SSTable 내부 구조
=================

  +-------------------------------------------+
  | Data Block 0                               |
  |   key1:value1 | key2:value2 | key3:value3  |
  +-------------------------------------------+
  | Data Block 1                               |
  |   key4:value4 | key5:value5 | key6:value6  |
  +-------------------------------------------+
  | ...                                        |
  +-------------------------------------------+
  | Meta Block (Bloom Filter)                  |
  +-------------------------------------------+
  | Index Block                                |
  |   block0_last_key -> offset0               |
  |   block1_last_key -> offset1               |
  +-------------------------------------------+
  | Footer                                     |
  |   index_offset | meta_offset | magic_num   |
  +-------------------------------------------+

Size-Tiered Compaction
======================

  크기가 비슷한 SSTable들을 합병

  Level 0: [T1] [T2] [T3] [T4]  (각 64MB)
                   |
              (4개가 쌓이면 합병)
                   |
                   v
  Level 1: [   T1+T2+T3+T4   ]  (약 256MB)

  장점: 쓰기 증폭이 낮음
  단점: 공간 증폭이 높음 (일시적으로 2배 공간 필요)
        읽기 시 여러 SSTable 확인 필요

Leveled Compaction
==================

  각 레벨은 키 범위가 겹치지 않는 SSTable로 구성
  레벨 N+1의 크기는 레벨 N의 10배

  L0: [a-z] [a-z] [a-z]    (키 범위 겹침 허용, 각 64MB)
       |
  L1: [a-e] [f-k] [l-p] [q-z]    (키 범위 겹침 없음, 총 640MB)
       |
  L2: [a-b] [c-d] ... [y-z]      (키 범위 겹침 없음, 총 6.4GB)

  장점: 읽기 증폭 낮음, 공간 증폭 낮음
  단점: 쓰기 증폭 높음 (최대 10x per level)

# Bloom Filter 동작 원리
class BloomFilter:
    def __init__(self, size, num_hash_functions):
        self.bit_array = [0] * size
        self.size = size
        self.num_hash = num_hash_functions

    def add(self, key):
        for i in range(self.num_hash):
            index = hash(key, seed=i) % self.size
            self.bit_array[index] = 1

    def might_contain(self, key):
        """
        True  -> 키가 존재할 수 있음 (false positive 가능)
        False -> 키가 확실히 없음 (false negative 없음)
        """
        for i in range(self.num_hash):
            index = hash(key, seed=i) % self.size
            if self.bit_array[index] == 0:
                return False
        return True

# 사용 예시: SSTable 읽기 최적화
def get(key):
    # 1. MemTable 확인
    result = memtable.get(key)
    if result:
        return result

    # 2. 각 SSTable의 Bloom Filter로 빠르게 필터링
    for sstable in sorted_sstables:
        if sstable.bloom_filter.might_contain(key):
            result = sstable.search(key)  # 실제 디스크 I/O
            if result:
                return result
    return None

쓰기 증폭 분석
==============

  원본 데이터: 1 byte

  B-Tree 쓰기 증폭:
    WAL 기록(1) + 페이지 쓰기(1) = 약 2x
    (실제로는 페이지 크기만큼 쓸 수 있어 더 높을 수 있음)

  LSM-Tree 쓰기 증폭 (Leveled Compaction):
    WAL 기록(1) + MemTable flush(1) + L0->L1(10) + L1->L2(10) + ...
    = 약 10 * level_count

  예: 5개 레벨이면 약 50x 쓰기 증폭!

Buffer Pool 구조
================

  [Hash Table: page_id -> frame_id]
       |
       v
  +------+------+------+------+------+
  |Frame0|Frame1|Frame2|Frame3|Frame4|  <-- Buffer Pool (메모리)
  |Page5 |Page12|Page3 |empty |Page8 |
  |dirty |clean |dirty |      |clean |
  +------+------+------+------+------+

  [Free List]: [Frame3]
  [LRU List]:  Frame4 <-> Frame1 <-> Frame0 <-> Frame2
               (least)                           (most)

  Page Table (매핑):
    Page 5  -> Frame 0 (dirty, pin_count=2)
    Page 12 -> Frame 1 (clean, pin_count=0)
    Page 3  -> Frame 2 (dirty, pin_count=1)
    Page 8  -> Frame 4 (clean, pin_count=0)

class LRUReplacer:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = OrderedDict()

    def access(self, frame_id):
        if frame_id in self.cache:
            self.cache.move_to_end(frame_id)
        else:
            if len(self.cache) >= self.capacity:
                self.cache.popitem(last=False)  # 가장 오래된 것 제거
            self.cache[frame_id] = True

    def evict(self):
        if self.cache:
            frame_id, _ = self.cache.popitem(last=False)
            return frame_id
        return None

Clock 알고리즘
==============

  시계 바늘이 순환하며 교체할 프레임을 찾음

      [Frame0: ref=1]
     /                \
  [Frame4: ref=0]    [Frame1: ref=1]   <-- clock hand 위치
     \                /
      [Frame3: ref=1]
         |
      [Frame2: ref=0]

  교체 과정:
  1. clock hand가 가리키는 Frame1의 ref bit 확인
  2. ref=1이면 ref=0으로 설정하고 다음으로 이동
  3. ref=0인 프레임을 찾으면 교체
  4. Frame2(ref=0)를 교체 대상으로 선택

Checkpoint 과정
===============

  1. Dirty Page 목록 수집
     Frame0(Page5): dirty -> 디스크에 기록 필요
     Frame2(Page3): dirty -> 디스크에 기록 필요

  2. Fuzzy Checkpoint (InnoDB 방식)
     - 모든 dirty page를 한 번에 쓰지 않음
     - 백그라운드에서 점진적으로 기록
     - 시스템 부하 분산

  3. Checkpoint LSN 기록
     - WAL에서 이 LSN 이전의 로그는 복구 시 불필요
     - WAL 파일 재활용 가능

  Timeline:
  WAL: [LSN:100][LSN:101]...[LSN:200][LSN:201]...
                              ^
                         Checkpoint LSN=200
                         (LSN 200 이전은 안전하게 디스크에 기록됨)

WAL 기록 흐름
=============

  1. 트랜잭션 시작
     BEGIN;

  2. UPDATE users SET name='Bob' WHERE id=1;
     a) WAL에 로그 레코드 기록:
        [LSN:101, TxID:5, Table:users, PK:1, 
         old:{name:'Alice'}, new:{name:'Bob'}]
     b) Buffer Pool의 페이지 수정 (메모리에서만)

  3. COMMIT;
     a) WAL에 커밋 레코드 기록:
        [LSN:102, TxID:5, COMMIT]
     b) WAL을 디스크에 fsync (이것이 COMMIT의 내구성 보장!)
     c) 클라이언트에 성공 응답

  핵심: 데이터 페이지는 나중에 lazy하게 디스크에 기록됨
  WAL만 디스크에 있으면 장애 후 복구 가능

LSN 구조와 역할
===============

  WAL File:
  [LSN:100|INSERT|TxID:3|...][LSN:101|UPDATE|TxID:5|...][LSN:102|COMMIT|TxID:5]

  Buffer Pool Page Header:
  +------------------+
  | Page LSN: 101    |  <-- 이 페이지에 마지막으로 적용된 WAL 레코드
  | Checksum: 0xAB12 |
  | ...               |
  +------------------+

  Checkpoint LSN: 100
    -> LSN 100 이전의 변경은 모두 디스크에 반영됨
    -> 복구 시 LSN 100 이후부터 재실행(redo)

  Flushed LSN: 102
    -> WAL 파일에서 디스크에 기록된 마지막 LSN

Group Commit 최적화
===================

  개별 fsync는 비용이 매우 높음 (SSD에서도 수백 us)

  Without Group Commit:
    Tx1: write WAL -> fsync -> respond   (10ms)
    Tx2: write WAL -> fsync -> respond   (10ms)
    Tx3: write WAL -> fsync -> respond   (10ms)
    Total: 30ms, 3 fsync calls

  With Group Commit:
    Tx1: write WAL --|
    Tx2: write WAL --|--> single fsync -> respond to all
    Tx3: write WAL --|
    Total: 10ms, 1 fsync call

  효과: fsync 횟수를 대폭 줄여 처리량 크게 향상

ARIES 복구 프로토콜 (Analysis-Redo-Undo)
==========================================

  Phase 1: Analysis (분석)
    WAL을 처음부터 스캔하여:
    - 장애 시점의 활성 트랜잭션 목록 파악
    - dirty page 목록 파악

  Phase 2: Redo (재실행)
    Checkpoint LSN 이후의 모든 WAL 레코드를 재실행
    - 커밋된 트랜잭션의 변경 복원
    - 미커밋 트랜잭션의 변경도 일단 복원

  Phase 3: Undo (취소)
    미커밋 트랜잭션의 변경을 역순으로 취소

  예시:
  WAL: [Tx1:INSERT][Tx2:UPDATE][Tx1:COMMIT][Tx2:DELETE][CRASH!]
                                                         ^
  Analysis: Tx1=committed, Tx2=active(uncommitted)
  Redo:     Tx1의 INSERT 재실행, Tx2의 UPDATE/DELETE도 재실행
  Undo:     Tx2의 DELETE 취소, Tx2의 UPDATE 취소

PostgreSQL MVCC 구현
====================

  각 튜플(행)에 메타데이터 포함:

  Tuple Header:
  +----------+----------+--------+
  | xmin     | xmax     | data   |
  +----------+----------+--------+

  xmin: 이 튜플을 생성(INSERT)한 트랜잭션 ID
  xmax: 이 튜플을 삭제(DELETE/UPDATE)한 트랜잭션 ID (0이면 유효)

  예시: UPDATE users SET age=31 WHERE id=1;

  Before (xmin=100, xmax=0):
  +----------+----------+-------------------+
  | xmin=100 | xmax=0   | id=1, age=30      |  <-- 현재 버전
  +----------+----------+-------------------+

  After (Tx 200이 UPDATE 실행):
  +----------+----------+-------------------+
  | xmin=100 | xmax=200 | id=1, age=30      |  <-- 이전 버전 (soft delete)
  +----------+----------+-------------------+
  +----------+----------+-------------------+
  | xmin=200 | xmax=0   | id=1, age=31      |  <-- 새 버전
  +----------+----------+-------------------+

PostgreSQL 가시성 규칙 (Snapshot Isolation)
==========================================

  현재 트랜잭션의 snapshot: active_tx = {150, 180}
  snapshot_xmin = 150 (가장 오래된 활성 트랜잭션)

  튜플이 보이는 조건:
  1. xmin이 커밋됨 AND xmin이 snapshot 이전
  2. xmax가 0이거나, xmax가 커밋되지 않았거나, 
     xmax가 snapshot 이후

  예시:
  - (xmin=100, xmax=0): 보임 (100은 커밋됨, 삭제 안 됨)
  - (xmin=100, xmax=200): Tx200이 커밋되면 안 보임
  - (xmin=150, xmax=0): 안 보임 (150은 아직 활성)
  - (xmin=120, xmax=180): 180이 활성이므로 보임

InnoDB Read View 구조
=====================

  Read View 생성 시점의 스냅샷:
  {
    creator_trx_id: 200,     // 현재 트랜잭션 ID
    trx_ids: [150, 180],     // 생성 시점 활성 트랜잭션 목록
    up_limit_id: 150,        // trx_ids 중 최솟값
    low_limit_id: 201        // 다음 할당될 트랜잭션 ID
  }

  Undo Log를 통한 버전 체인:
  
  Current Row:  {id:1, name:'Carol', trx_id:200}
       |
       v (undo log pointer)
  Undo v1:     {id:1, name:'Bob',   trx_id:180}
       |
       v (undo log pointer)
  Undo v2:     {id:1, name:'Alice', trx_id:100}

  가시성 판단:
  - trx_id=200 (creator): 자신이 수정 -> 보임
  - trx_id가 up_limit_id(150) 미만: 커밋 확정 -> 보임
  - trx_id가 low_limit_id(201) 이상: 미래 트랜잭션 -> 안 보임
  - trx_id가 trx_ids에 포함: 활성 트랜잭션 -> 안 보임
  - 그 외: 커밋됨 -> 보임

격리 수준과 허용되는 이상 현상
===============================

  격리 수준          | Dirty Read | Non-Repeatable | Phantom Read
  ================== | ========== | ============== | ============
  READ UNCOMMITTED   |    허용    |      허용      |     허용
  READ COMMITTED     |    방지    |      허용      |     허용
  REPEATABLE READ    |    방지    |      방지      |     허용*
  SERIALIZABLE       |    방지    |      방지      |     방지

  * MySQL InnoDB의 REPEATABLE READ는 Gap Lock으로 Phantom Read도 방지

-- Dirty Read (READ UNCOMMITTED)
-- Tx1:
BEGIN;
UPDATE accounts SET balance = 500 WHERE id = 1; -- 원래 1000
-- 아직 COMMIT 안 함!

-- Tx2 (READ UNCOMMITTED):
SELECT balance FROM accounts WHERE id = 1;
-- 결과: 500 (커밋되지 않은 데이터를 읽음!)

-- Tx1:
ROLLBACK; -- 500은 무효화됨
-- Tx2는 잘못된 데이터를 기반으로 결정을 내릴 수 있음

-- Non-Repeatable Read (READ COMMITTED)
-- Tx1:
BEGIN;
SELECT balance FROM accounts WHERE id = 1;
-- 결과: 1000

-- Tx2:
BEGIN;
UPDATE accounts SET balance = 500 WHERE id = 1;
COMMIT;

-- Tx1:
SELECT balance FROM accounts WHERE id = 1;
-- 결과: 500 (같은 트랜잭션 내에서 다른 결과!)

-- Phantom Read (REPEATABLE READ, non-InnoDB)
-- Tx1:
BEGIN;
SELECT COUNT(*) FROM orders WHERE status = 'pending';
-- 결과: 5

-- Tx2:
BEGIN;
INSERT INTO orders (status) VALUES ('pending');
COMMIT;

-- Tx1:
SELECT COUNT(*) FROM orders WHERE status = 'pending';
-- 결과: 6 (새로운 행이 나타남 - phantom!)

InnoDB 락 종류
==============

  1. Record Lock (레코드 락)
     특정 인덱스 레코드를 잠금
     예: WHERE id = 5 -> id=5 레코드만 잠금

  2. Gap Lock (갭 락)
     인덱스 레코드 사이의 간격을 잠금
     예: WHERE id BETWEEN 5 AND 10
         -> (5, 10) 사이에 새로운 레코드 삽입 방지

  3. Next-Key Lock (넥스트키 락)
     Record Lock + Gap Lock
     예: WHERE id = 5 
         -> id=5 레코드 + 이전 레코드와의 갭
     InnoDB REPEATABLE READ의 기본 잠금 방식

  4. Intention Lock (인텐션 락)
     테이블 수준의 의도 표시
     - IS (Intention Shared): 행 수준 S lock을 획득할 의도
     - IX (Intention Exclusive): 행 수준 X lock을 획득할 의도

Intention Lock 호환성
=====================

           | IS    | IX    | S     | X
  ---------|-------|-------|-------|-------
  IS       | 호환  | 호환  | 호환  | 충돌
  IX       | 호환  | 호환  | 충돌  | 충돌
  S        | 호환  | 충돌  | 호환  | 충돌
  X        | 충돌  | 충돌  | 충돌  | 충돌

  예시:
  Tx1: SELECT ... FOR SHARE  -> IS(테이블) + S(행)
  Tx2: SELECT ... FOR UPDATE -> IX(테이블) + X(행)
  
  IS와 IX는 호환 -> 테이블 수준에서 블로킹 없음
  같은 행에 S와 X -> 행 수준에서 Tx2가 대기

-- 교착 상태 시나리오
-- Tx1:
BEGIN;
UPDATE accounts SET balance = balance - 100 WHERE id = 1;  -- Lock A

-- Tx2:
BEGIN;
UPDATE accounts SET balance = balance - 200 WHERE id = 2;  -- Lock B

-- Tx1:
UPDATE accounts SET balance = balance + 100 WHERE id = 2;  -- Wait for Lock B

-- Tx2:
UPDATE accounts SET balance = balance + 200 WHERE id = 1;  -- Wait for Lock A
-- DEADLOCK! Tx1 -> Lock B -> Tx2 -> Lock A -> Tx1

Deadlock 탐지: Wait-for Graph
==============================

  Tx1 ---waits for---> Tx2
   ^                    |
   |                    |
   +---waits for--------+

  사이클 발견! -> 비용이 낮은 트랜잭션을 롤백

  InnoDB 방식:
  - Wait-for graph를 주기적으로 검사
  - 사이클 발견 시 undo log가 적은 트랜잭션을 victim으로 선택
  - ERROR 1213 (40001): Deadlock found when trying to get lock

쿼리 처리 과정
==============

  SQL Query
     |
     v
  [Parser] --> AST (Abstract Syntax Tree)
     |
     v
  [Binder/Analyzer] --> 테이블/컬럼 존재 확인, 타입 검사
     |
     v
  [Query Rewriter] --> 뷰 확장, 서브쿼리 변환
     |
     v
  [Optimizer] --> 최적 실행 계획 선택
     |
     +---> [Cost Estimator] --> 각 계획의 비용 추정
     +---> [Plan Enumerator] --> 가능한 실행 계획 열거
     |
     v
  [Execution Engine] --> 실행 계획에 따라 데이터 접근

비용 추정 요소
=============

  1. I/O 비용: 디스크에서 읽어야 할 페이지 수
     - Sequential I/O: 1.0 (기본 단위)
     - Random I/O: 4.0 (SSD) ~ 40.0 (HDD)

  2. CPU 비용: 튜플 처리 비용
     - 비교 연산: 0.01
     - 해시 계산: 0.02

  3. 메모리 비용: 정렬, 해시 테이블 등

  비용 공식 예시 (간략화):
  Total Cost = (pages * seq_page_cost) + (tuples * cpu_tuple_cost)

  예: 풀 테이블 스캔
  pages = 1000, seq_page_cost = 1.0
  tuples = 100000, cpu_tuple_cost = 0.01
  Total = 1000 * 1.0 + 100000 * 0.01 = 2000

조인 알고리즘 비교
==================

  1. Nested Loop Join
     for each row r in R:        -- |R| iterations
       for each row s in S:      -- |S| iterations
         if r.key == s.key:
           emit (r, s)
     비용: O(|R| * |S|)
     적합: 작은 테이블, 인덱스가 있을 때

  2. Hash Join
     Phase 1 (Build):
       for each row r in R:
         hash_table[hash(r.key)] = r
     Phase 2 (Probe):
       for each row s in S:
         if hash_table[hash(s.key)] exists:
           emit (match, s)
     비용: O(|R| + |S|)
     적합: 대용량 테이블, 등가 조인

  3. Sort-Merge Join
     Phase 1: Sort R by key
     Phase 2: Sort S by key
     Phase 3: Merge sorted R and S
     비용: O(|R|log|R| + |S|log|S| + |R| + |S|)
     적합: 이미 정렬된 데이터, 범위 조인

-- PostgreSQL 통계 정보 확인
SELECT
    tablename,
    attname,
    n_distinct,    -- 고유값 수 (-1이면 모두 고유)
    correlation,   -- 물리적 정렬과 논리적 정렬의 상관관계
    most_common_vals,
    most_common_freqs,
    histogram_bounds
FROM pg_stats
WHERE tablename = 'users';

-- 결과 예시:
-- attname: status
-- n_distinct: 5
-- most_common_vals: {active, inactive, pending, banned, deleted}
-- most_common_freqs: {0.65, 0.20, 0.10, 0.03, 0.02}
-- correlation: 0.12 (물리적 순서와 무관)

인덱스 선택 판단 기준
====================

  쿼리: SELECT * FROM users WHERE status = 'active'

  옵션 1: Full Table Scan
    pages: 1000, selectivity: 0.65 (65%의 행이 'active')
    비용: 1000 * 1.0 = 1000

  옵션 2: Index Scan (status 인덱스)
    index_pages: 10, table_pages: 650 (random I/O)
    비용: 10 * 1.0 + 650 * 4.0 = 2610

  결론: selectivity가 높아서(65%) Full Table Scan이 더 효율적!

  일반적으로: selectivity가 5~15% 이하일 때 인덱스 사용이 유리

InnoDB 아키텍처
===============

  In-Memory:
  +-------------------------------------------------------+
  | Buffer Pool                                            |
  |  [Data Pages] [Index Pages] [Undo Pages] [Lock Info]   |
  |  [Adaptive Hash Index]                                 |
  |  [Change Buffer]                                       |
  +-------------------------------------------------------+
  | Log Buffer                                             |
  +-------------------------------------------------------+

  On-Disk:
  +----------------------------+----------------------------+
  | System Tablespace          | Redo Log Files             |
  |  (ibdata1)                 |  (ib_logfile0, ib_logfile1)|
  |  - Data Dictionary         |  - WAL records             |
  |  - Doublewrite Buffer      |                            |
  |  - Change Buffer           |                            |
  |  - Undo Logs               |                            |
  +----------------------------+----------------------------+
  | Per-Table Tablespace (.ibd files)                       |
  |  - Table Data + Index                                   |
  +--------------------------------------------------------+

Change Buffer 동작
==================

  상황: Secondary Index 페이지가 Buffer Pool에 없을 때

  Without Change Buffer:
    1. 디스크에서 페이지 읽기 (Random I/O!)
    2. 페이지 수정
    3. dirty로 표시

  With Change Buffer:
    1. 변경 사항을 Change Buffer에 기록 (메모리)
    2. 나중에 페이지가 읽힐 때 merge
    
  효과: 랜덤 I/O를 순차 I/O로 변환
  적합: 쓰기가 많고 secondary index가 많은 워크로드
  부적합: unique index (중복 확인 필요)

  설정:
  innodb_change_buffering = all  -- inserts, deletes, purges 모두
  innodb_change_buffer_max_size = 25  -- buffer pool의 25%

Adaptive Hash Index
===================

  InnoDB가 자동으로 자주 접근하는 B+Tree 페이지에 해시 인덱스를 구축

  일반 B+Tree 접근: O(log N) - 3~4번의 페이지 접근
  AHI 접근: O(1) - 해시 테이블 직접 참조

  동작 방식:
  1. 특정 인덱스 패턴의 접근 빈도 모니터링
  2. 임계값 초과 시 자동으로 해시 인덱스 생성
  3. 패턴이 변경되면 해시 인덱스 자동 재구축/삭제

  모니터링:
  SHOW ENGINE INNODB STATUS;
  -- Hash table size 34679, used cells 1234
  -- 10.52 hash searches/s, 3.48 non-hash searches/s

  주의: 워크로드에 따라 오히려 성능 저하 가능
  innodb_adaptive_hash_index = ON|OFF

Doublewrite Buffer 목적
=======================

  문제: Partial Page Write (Torn Page)
  - OS 페이지 크기(4KB)와 InnoDB 페이지 크기(16KB)가 다름
  - 장애 시 16KB 페이지의 일부만 기록될 수 있음
  - WAL로도 복구 불가 (WAL은 페이지의 변경 부분만 기록)

  해결: Doublewrite Buffer
  1. dirty page를 먼저 doublewrite buffer(연속 영역)에 기록
  2. 그 다음 실제 위치에 기록
  3. 장애 시: doublewrite buffer에서 완전한 페이지 복구

  흐름:
  [Dirty Page] --> [Doublewrite Buffer (디스크)] --> [실제 테이블 파일]
                   (순차 쓰기, 2MB 단위)              (랜덤 쓰기)

RocksDB 아키텍처
================

  Write Path:
  [Put/Delete] --> [WAL] --> [MemTable (Active)]
                                    |
                              (switch when full)
                                    |
                                    v
                            [MemTable (Immutable)]
                                    |
                              (background flush)
                                    |
                                    v
                            [L0 SST Files]
                                    |
                           (background compaction)
                                    |
                                    v
                            [L1 SST Files]
                                    |
                                   ...
                                    |
                                    v
                            [Ln SST Files]

  Read Path:
  [Get] --> [MemTable] --> [L0 SSTs] --> [L1 SSTs] --> ... --> [Ln SSTs]
             (bloom)        (bloom)       (bloom)               (bloom)

Column Families 개념
===================

  하나의 DB 인스턴스에서 논리적으로 분리된 키-값 네임스페이스

  CF "default":     user:1 -> {"name":"Alice"}
  CF "metadata":    schema_version -> "3.2"
  CF "timeseries":  ts:1710000000 -> {"temp":23.5}

  각 Column Family는 독립적인:
  - MemTable
  - SSTable 세트
  - Compaction 설정
  - Compression 설정

  사용 예:
  Options options;
  ColumnFamilyOptions cf_opts;
  cf_opts.compaction_style = kCompactionStyleLevel;
  cf_opts.write_buffer_size = 128 << 20;  // 128MB MemTable

  // Timeseries CF는 FIFO compaction (오래된 데이터 자동 삭제)
  ColumnFamilyOptions ts_opts;
  ts_opts.compaction_style = kCompactionStyleFIFO;
  ts_opts.compaction_options_fifo.max_table_files_size = 1 << 30; // 1GB

Rate Limiter 설정
=================

  목적: 컴팩션과 플러시의 I/O를 제한하여
        전면(foreground) 읽기/쓰기 성능 보호

  설정 예시:
  options.rate_limiter.reset(
      NewGenericRateLimiter(
          100 * 1024 * 1024,   // rate_bytes_per_sec: 100MB/s
          100 * 1000,          // refill_period_us: 100ms
          10,                  // fairness
          RateLimiter::Mode::kWritesOnly
      )
  );

  동작:
  - 컴팩션/플러시가 100MB/s 이상 쓰지 못하도록 제한
  - 전면 요청이 I/O 대역폭을 확보할 수 있음
  - 피크 시간에는 낮게, 오프피크에는 높게 동적 조절 가능

-- 커버링 인덱스로 이중 조회 제거
-- Before: secondary index -> clustered index (bookmark lookup)
SELECT name, email FROM users WHERE status = 'active';
-- index(status)만 있으면 name, email을 위해 테이블 접근 필요

-- After: 커버링 인덱스
CREATE INDEX idx_status_covering ON users(status) INCLUDE (name, email);
-- 인덱스만으로 쿼리 완료 (Index Only Scan)

-- 복합 인덱스 순서의 중요성 (Leftmost Prefix Rule)
CREATE INDEX idx_abc ON orders(customer_id, order_date, status);

-- 이 인덱스를 사용할 수 있는 쿼리:
SELECT * FROM orders WHERE customer_id = 100;                    -- O
SELECT * FROM orders WHERE customer_id = 100 AND order_date > '2025-01-01'; -- O
SELECT * FROM orders WHERE customer_id = 100 AND status = 'shipped';        -- O (skip scan 가능)

-- 이 인덱스를 사용할 수 없는 쿼리:
SELECT * FROM orders WHERE order_date > '2025-01-01';            -- X
SELECT * FROM orders WHERE status = 'shipped';                   -- X

# MySQL InnoDB Buffer Pool 설정
[mysqld]
# 전체 메모리의 70-80%를 Buffer Pool에 할당
innodb_buffer_pool_size = 12G

# 여러 인스턴스로 분할하여 경합 감소
innodb_buffer_pool_instances = 8

# Buffer Pool 내용을 재시작 시 보존
innodb_buffer_pool_dump_at_shutdown = ON
innodb_buffer_pool_load_at_startup = ON

# 모니터링
SHOW ENGINE INNODB STATUS;
-- Buffer pool hit rate: 999/1000 (99.9% 이상이 이상적)

# InnoDB Redo Log 설정
[mysqld]
# Redo log 크기 (너무 작으면 checkpoint 빈번, 너무 크면 복구 시간 증가)
innodb_redo_log_capacity = 4G

# fsync 전략
innodb_flush_log_at_trx_commit = 1  # 가장 안전 (기본값)
# = 0: 1초마다 fsync (최대 1초 데이터 손실 가능)
# = 1: 매 커밋마다 fsync (가장 안전, 가장 느림)
# = 2: 매 커밋마다 OS buffer에 쓰기, 1초마다 fsync