DB 내부 구조: 쿼리 실행과 인덱스 자료 구조

SQL 문장이 실행되는 과정

DB마다 구조는 다르지만 큰 흐름은 비슷하다. 앞쪽은 무엇을 할지 정하는 단계, 뒤쪽은 실제로 데이터를 만지는 단계다. SQL이 관계대수로 바뀌는 논리적 단계와 절의 평가 순서는 관계대수와 DB 설계에 있고, 여기서는 엔진 내부의 구성 요소를 따라간다.

flowchart TB
  client["클라이언트"] -->|"SQL (TCP 위의 DB 프로토콜)"| t["[1] 전송 계층<br/>연결·인증·세션"]
  t --> parser["[2] 파서<br/>구문 분석 → 의미 분석(테이블·컬럼 존재, 권한) → 쿼리 트리"]
  parser --> opt["[3] 옵티마이저<br/>통계로 비용을 추정해 실행 계획 선택<br/>(어느 인덱스? 어떤 조인 순서·방식?)"]
  opt --> exec["[4] 실행기<br/>계획대로 연산자(스캔, 조인, 정렬, 집계)를 돌린다"]
  exec --> am["[5] 접근 방법<br/>테이블·인덱스에서 행을 꺼내는 로직 (풀 스캔, 인덱스 스캔)"]
  am -->|"읽기"| buf["[6] 버퍼 관리자<br/>메모리의 페이지 캐시(버퍼 풀)에 있으면 바로,<br/>없으면 디스크에서 읽어 올린다"]
  am -->|"쓰기"| tx["[7] 트랜잭션 관리자<br/>로그(WAL·redo)를 먼저 쓰고 버퍼의 페이지를 고친다"]
  tx --> lock["[8] 잠금 관리자<br/>동시에 같은 데이터를 고치지 못하게 잠금을 건다"]

스토리지 엔진

[5]~[8]처럼 데이터를 실제로 디스크에 어떻게 놓고, 읽고, 쓰고, 잠그고, 장애에서 되살릴지를 맡는 층을 스토리지 엔진(storage engine)이라 한다. 그 위의 SQL 층(파서·옵티마이저·실행기)은 「무엇을 원하나」를 해석하고, 엔진은 「행 하나 주세요」, 「이 행을 바꿔 주세요」 같은 요청을 처리한다.

MySQL은 이 층을 플러그인처럼 갈아 끼우는 구조라 테이블마다 엔진을 고른다(CREATE TABLE ... ENGINE=InnoDB). 기본값인 InnoDB는 트랜잭션·행 잠금·크래시 복구를 갖췄고, 옛 MyISAM은 트랜잭션이 없고 테이블 잠금만 한다. 그 밖에 MEMORY, 그리고 RocksDB를 쓰는 MyRocks가 있다. PostgreSQL은 엔진이 하나로 정해져 있다(12부터 테이블 접근 방식 API로 다른 저장 방식을 붙일 수는 있다). MongoDB의 WiredTiger처럼 NoSQL도 같은 개념의 층을 가진다.

옵티마이저: 규칙 기반과 비용 기반

지금 주요 DBMS(MySQL, PostgreSQL, Oracle, SQL Server)는 모두 비용 기반이다. Oracle의 RBO는 10g부터 지원이 끝났다. 그래서 통계를 최신으로 유지하는 것(ANALYZE TABLE, PostgreSQL의 autovacuum이 함께 돌리는 ANALYZE)이 성능 관리의 일부다. 실행 계획을 읽는 법과 풀 스캔을 고르는 이유는 인덱스 설계와 쿼리 튜닝에 있다.

엔진의 몸체: Oracle로 보는 메모리·프로세스·파일

위 흐름의 버퍼 관리자·트랜잭션 관리자가 실제로 어떤 부품인지는 엔진 하나를 뜯어 보면 잘 보인다. Oracle은 부품마다 이름이 붙어 있어 예로 쓰기 좋다. 부품이 노리는 목표는 셋이다. 디스크를 덜 읽고, 커밋을 빨리 끝내고, 죽어도 되살린다. MySQL·PostgreSQL도 같은 목표를 비슷한 부품으로 푼다.

Oracle에서 인스턴스와 데이터베이스는 다른 말이다. 인스턴스는 메모리와 백그라운드 프로세스의 묶음이라 시작할 때 생기고 종료하면 사라진다. 데이터베이스는 디스크의 파일 묶음이라 인스턴스가 꺼져도 남는다. 인스턴스가 데이터베이스를 마운트해서 연다. 보통 1:1이고, RAC(Real Application Clusters)에서는 여러 서버의 인스턴스가 한 데이터베이스를 함께 연다.

flowchart TB
  cl["클라이언트"] --> sp["서버 프로세스<br>(전용 메모리 PGA)"] --> sga
  subgraph sga["SGA: 모든 세션이 공유"]
    direction LR
    bc["버퍼 캐시"] ~~~ shp["공유 풀"] ~~~ rlb["리두 로그 버퍼"] ~~~ lp["대용량·자바 풀"]
  end
  sga -->|"DBWn"| df["데이터 파일"]
  sga -->|"LGWR"| orl["온라인 리두 로그"] -->|"ARCn"| al["아카이브 로그"]
  sga -.- bg["CKPT·SMON·PMON …"]
  cf["컨트롤 파일<br>파일 위치와 체크포인트 기록"]

메모리: SGA와 PGA

공유 풀은 문장 모양이 같은 SQL의 실행 계획을 재사용한다(소프트 파싱). 값을 문자열로 이어 붙이면 문장이 매번 달라 캐시를 못 쓰므로, Oracle에서는 바인드 변수가 인젝션 방어에 더해 성능에도 크게 듣는다(Prepared Statement).

백그라운드 프로세스

연결마다 프로세스를 두는 것은 PostgreSQL도 같고, MySQL은 연결마다 스레드를 둔다. 어느 쪽이든 연결이 비싸 앞단에 커넥션 풀을 둔다.

커밋은 리두 로그만 순차로 덧붙이고 끝낸다. 흩어진 데이터 블록을 제자리에 쓰는 무거운 일은 DBWn이 미룬다. 그 사이에 죽으면 재시작 때 리두로 커밋된 변경을 다시 적용하고(롤 포워드), 언두 세그먼트의 이전 값으로 커밋 안 된 변경을 되돌린다. 체크포인트가 잦으면 복구할 리두가 짧아지는 대신 쓰기가 는다. WAL과 재시작 복구의 일반 원리는 트랜잭션과 회복에 있다.

물리 파일

논리 저장 구조

SQL이 보는 테이블과 디스크 파일 사이에는 네 겹의 논리 단위가 있다.

flowchart TD
  ts["테이블스페이스"] ---|"1:N"| df["데이터 파일(물리)"]
  ts --> seg["세그먼트<br>테이블·인덱스·파티션 하나가 차지하는 공간"]
  seg --> ext["익스텐트<br>연속된 블록 묶음. 공간이 모자라면 하나씩 더 받는다"]
  ext --> blk["블록<br>I/O의 최소 단위. 기본 8KB(2~32KB 중 DB를 만들 때 정한다)"]

• 블록이 크면 한 번에 많이 읽어 I/O 횟수가 줄지만, 몇 행만 필요할 때 낭비가 생기고 같은 블록을 두고 다투는 일이 는다. 분석용은 크게, OLTP는 기본값 근처를 쓴다. InnoDB의 페이지(기본 16KB)가 같은 개념이다.
• 익스텐트는 블록을 연속으로 묶어 줘서 데이터가 흩어지지 않고 순차 읽기가 빨라진다.
• 세그먼트는 한 테이블스페이스 안에 있지만 그 안의 여러 데이터 파일에 걸칠 수 있다.
• 테이블스페이스는 관리 단위다. 테이블과 인덱스를 다른 디스크의 테이블스페이스에 두어 I/O를 나누거나, 오래된 데이터를 읽기 전용 테이블스페이스로 옮겨 백업 대상을 줄인다. 기본으로 SYSTEM·SYSAUX(데이터 사전), UNDO(롤백과 읽기 일관성용 이전 값), TEMP(메모리에 못 담은 정렬 중간 결과), USERS(사용자 객체 기본 위치)가 있다.

CREATE TABLESPACE ts_orders
  DATAFILE '/u01/oradata/orders01.dbf' SIZE 100M AUTOEXTEND ON NEXT 10M;
 
ALTER TABLESPACE ts_orders
  ADD DATAFILE '/u02/oradata/orders02.dbf' SIZE 100M;   -- 다른 디스크로 넓히기
 
-- 안의 객체, 걸린 참조 제약, 실제 파일까지 지운다. 되돌릴 수 없다
DROP TABLESPACE ts_orders INCLUDING CONTENTS AND DATAFILES CASCADE CONSTRAINTS;

Oracle의 스키마는 사용자 계정과 1:1이다. HR 사용자가 만든 객체는 HR 스키마에 속하고, 다른 사용자는 HR.EMPLOYEES처럼 접두어를 붙이거나 동의어를 만들어 쓴다(동의어). 테이블 저장 방식은 순서 없이 쌓는 힙 테이블이 기본이고, 기본 키 순서의 B-트리에 행을 넣는 인덱스 구조 테이블(IOT)을 고를 수도 있다(클러스터드 인덱스).

에디션은 무료이고 CPU·메모리·용량 상한이 있는 Express Edition(XE), 중소 규모용 Standard Edition 2, 모든 기능을 갖춘 Enterprise Edition으로 나뉜다. 파티셔닝은 Enterprise Edition의 별도 유료 옵션이다. 12c부터는 컨테이너 DB(CDB) 하나에 플러그형 DB(PDB) 여럿을 담는 멀티테넌트 구조를 쓴다.

인덱스 자료 구조

어떤 자료 구조가 맞는지는 데이터가 메모리에 있나 디스크에 있나, 값의 형태(숫자·문자열·좌표·문서)가 무엇인가, 쓰기가 많나 읽기가 많나에 달렸다.

왜 B+트리인가

같은 균형 트리라도 레드-블랙 트리·AVL 트리는 노드 하나에 키 하나, 자식 둘이다. 디스크에서는 노드 하나를 읽을 때마다 페이지 하나만큼 I/O가 생기므로, 트리 높이가 곧 디스크 접근 횟수다.

M차 B+트리의 노드는 최소 ⌈M/2⌉개의 자식을 가지므로, 높이 h에서 담을 수 있는 키가 (M/2)^h 이상으로 늘어난다. 차수가 수백이면 수억 건도 높이 3~4 안에 들어가고, 루트와 상위 노드는 버퍼 풀에 상주하므로 실제 디스크 읽기는 한두 번이다. 모든 리프가 같은 깊이에 있어 어떤 키든 같은 비용으로 찾는다. 키가 길면 한 페이지에 들어가는 키 수가 줄어 트리가 높아지므로 인덱스 키는 짧을수록 좋다. 인덱스를 어떻게 설계할지는 인덱스 설계와 쿼리 튜닝에 있다.

B-트리와 B+트리는 같은 계열이지만 데이터를 두는 곳이 다르다.

B+트리가 늘 낫지는 않다. 무작위 점 조회만 있는 작업에서는 위쪽에서 끝날 수 있는 B-트리가 유리할 수 있고, 내부 노드에 키를 한 번 더 저장하는 공간이 든다. 같음 조회만 필요하면 해시 인덱스가 더 빠르다. 그래도 DB는 범위 조회·정렬·순차 스캔이 흔하고 높이가 낮을수록 디스크 I/O가 줄어서 B+트리를 기본으로 쓴다. 현업에서 「B-트리 인덱스」라고 부르는 것도 실제로는 대부분 B+트리다.

공간 인덱스: R-트리와 지오해시

B+트리는 값을 한 줄로 정렬해야 쓸 수 있다. 위도·경도는 두 값이 함께 가까워야 「가까운 곳」이므로, 한쪽으로 정렬하면 다른 쪽 조건은 거르지 못한다. 그래서 공간 데이터는 따로 처리한다.

지오해시는 칸 경계 문제가 있다. 바로 옆이라도 경계 건너편이면 접두사가 전혀 다를 수 있어서, 반경 검색은 내 칸과 주변 8칸을 함께 조회한 뒤 실제 거리로 다시 거른다. 칸 길이(문자열 자릿수)는 검색 반경에 맞춰 고른다.

PostgreSQL의 인덱스 종류

PostgreSQL은 접근 방식(access method)을 골라 인덱스를 만든다(CREATE INDEX ... USING gin (...)).

확장으로 더 붙는다. pgvector는 벡터 유사도 검색용 HNSW·IVFFlat 인덱스를 더한다.

이 밖에 열 단위 저장에 쓰는 비트맵 인덱스, 「없음」을 빠르게 판정하는 블룸 필터, 벡터 유사도 검색용 HNSW 같은 그래프 인덱스도 있다.

B-트리와 LSM 트리

디스크 기반 저장 엔진의 두 갈래다.

B-트리: 제자리 갱신

flowchart LR
  root["루트 페이지"] --> inner["내부 페이지"] --> leaf["리프 페이지: 키·값<br/>해당 페이지를 찾아 고쳐 쓴다"]

LSM 트리: 추가 후 병합

flowchart TB
  w["쓰기"] --> wal["WAL(장애 대비)"]
  w --> mem["멤테이블(메모리, 정렬)"]
  mem -->|"가득 차면 flush"| l0["L0: SSTable · SSTable · SSTable"]
  l0 -->|"컴팩션(compaction): 겹치는 파일을 병합·정렬, 지운 값 제거"| l1["L1: SSTable ── SSTable"]
  l1 --> l2["L2 ..."]
  r["읽기<br/>멤테이블 → L0 → L1 … 순으로 찾는다<br/>(블룸 필터로 없는 파일은 건너뜀)"]

세 가지 증폭으로 비교하면 정리가 쉽다. 읽기 증폭(한 번 읽으려고 몇 번 디스크를 보나), 쓰기 증폭(한 번 쓴 데이터가 디스크에 몇 번 다시 쓰이나), 공간 증폭(실제 데이터 대비 디스크를 얼마나 쓰나). B-트리는 읽기 증폭이 작고, LSM 트리는 쓰기 처리량을 위해 읽기·공간 증폭을 받아들인다. 와이드 컬럼 DB에서 LSM 트리가 쓰이는 방식은 와이드 컬럼 DB와 대규모 메시지 저장에 있다.

정리

• SQL은 파싱 → 최적화 → 실행 → 버퍼·트랜잭션·잠금 관리 순으로 처리된다. 느린 쿼리는 대개 옵티마이저가 고른 계획에서 원인이 보인다.
• 쓰기는 WAL로 먼저 기록하고, 읽기는 버퍼 풀에서 끝나는 것이 보통이다.
• Oracle로 보면 인스턴스(공유 메모리 SGA + 프로세스 전용 PGA + 백그라운드 프로세스)가 파일 묶음인 데이터베이스를 연다. 커밋은 LGWR의 리두 쓰기로 끝나고 데이터 블록은 DBWn이 나중에 내린다. 저장은 테이블스페이스 → 세그먼트 → 익스텐트 → 블록이다.
• 인덱스 자료 구조는 값의 형태와 읽기·쓰기 비율로 고른다. 범위 조회는 B-트리, 전문 검색은 역색인, 공간은 R-트리다.
• B-트리는 읽기에, LSM 트리는 쓰기에 강하다.

관련 노트: 트랜잭션과 회복, 데이터베이스 확장과 성능 최적화, 와이드 컬럼 DB와 대규모 메시지 저장: Cassandra·ScyllaDB, 검색엔진의 원리: 역인덱스와 랭킹, 트리와 이진 탐색 트리, DB 커넥션 풀