PostgreSQL 내부구조 (6) ㅡ Index

1편에서 본 ctid, 4편에서 본 Visibility Map. 이 둘이 인덱스에서 어떻게 쓰이는지 알아보자. 인덱스는 별도의 자료구조처럼 생각하지만, 실제로는 1편의 힙 페이지 구조 위에 얹혀 동작한다.

 

이 글에서 다루는 것:

• 인덱스가 저장하는 것 — 키와 ctid, 그리고 저장하지 않는 것
• 모든 인덱스가 보조 인덱스(secondary index)라는 의미
• 인덱스 스캔의 비용 — 힙 random I/O
• 인덱스 종류 (B-tree · GiST · SP-GiST · GIN · BRIN · Hash)와 각각의 사용처
• B-tree가 정렬을 제공한다는 것, 멀티컬럼 인덱스
• Index Only Scan과 Visibility Map의 관계
• 인덱스 유지 비용 — 쓰기 증폭과 비대화

---

인덱스가 저장하는 데이터

인덱스가 한 항목에 저장하는 것은 두 가지다.

저장하는 것	내용
키 값	인덱스를 만든 컬럼(들)의 값
ctid	그 값을 가진 행의 물리적 위치

ctid는 (페이지 번호, 라인 포인터 번호) 형태의 행 물리 주소다. 자세한 구조는 1편 ctid — 행의 물리적 주소에서 다뤘다.

인덱스는 "이 키 값을 가진 행은 저기 있다"는 포인터만 갖고 있다. 행의 나머지 컬럼 데이터는 안 갖고 있다.

그래서 인덱스로 행을 찾으면, 실제 데이터를 읽기 위해 ctid가 가리키는 힙 페이지로 한 번 더 가야 한다. 이게 인덱스 스캔이 기본적으로 "인덱스 → 힙" 2단계인 이유다.

 

더 중요한 것이 하나 더 있다. 인덱스에는 가시성 정보(t_xmin, t_xmax)가 없다.

t_xmin/t_xmax는 어떤 튜플이 어떤 트랜잭션에 보이는지를 결정하는 값으로, 튜플 헤더에 들어 있다. 자세한 동작은 2편에서 다뤘다. 핵심은 이 값들이 튜플 헤더에만 있고 인덱스 항목에는 없다는 점이다.

 

그래서 인덱스만 봐서는 "이 행이 지금 나에게 보이는가"를 알 수 없다. 인덱스가 ctid를 찾아줘도, 그 행이 살아 있는지 확인하려면 결국 힙의 튜플 헤더를 읽어야 한다.

이 두 가지 사실이 다음에 다룰 Index Only Scan과 인덱스 비대화와 연관 있다.
1. 인덱스에 실제 데이터가 없다는 것
2. 인덱스에 가시성 정보가 없다는 것

---

PostgreSQL의 모든 인덱스 — 보조 인덱스

PostgreSQL에는 힙 데이터가 정렬되는 clustered index가 없다. 모든 인덱스는 보조 인덱스(secondary index)다.

PK에 걸린 인덱스도 일반 인덱스와 구조가 같다. 키와 ctid를 저장하는 별도의 자료구조일 뿐이다.

 

이 말은 힙이 인덱스와 독립적으로 존재한다는 뜻이다. 행 데이터는 힙 페이지에 들어가고(heap-organized table), 인덱스는 그 힙을 가리키는 외부 구조다. 인덱스를 전부 지워도 힙은 그대로 남는다.

"PostgreSQL는 어떤 인덱스로 조회하든 동등하게 "인덱스에서 ctid를 찾고, 힙으로 직행한다." PK라고 더 빠를 게 없다.

항목	PostgreSQL	MySQL (InnoDB)
테이블 저장 방식	힙 (정렬 없음, Heap-organized)	PK 순으로 정렬된 B-tree (Clustered)
보조 인덱스가 가리키는 것	ctid (물리 주소 포인터)	PK 값 (논리 키)
보조 인덱스 조회 메커니즘	인덱스 리프 탐색 후 힙 페이지 직접 접근	보조 인덱스 탐색 후 PK 인덱스 재탐색 (더블 트리)

 

InnoDB는 테이블 자체가 PK로 정렬된 B-tree다. PK 조회는 그 트리만 타면 끝난다. 보조 인덱스는 ctid 같은 물리 주소가 아니라 PK 값을 저장하고, 다시 PK 인덱스를 타고 들어간다.

PostgreSQL은 그런 특별 취급이 없다. 어떤 인덱스로 조회하든 동등하게 "인덱스에서 ctid를 찾고, 힙으로 간다." PK라고 더 빠를 게 없다.

CLUSTER 명령은 클러스터형 인덱스가 아니다. CLUSTER 명령은 특정 인덱스 순서대로 힙을 한 번 물리적으로 재정렬한다. 그런데 그 순서는 유지되지 않는다. CLUSTER 명령 이후 INSERT/UPDATE가 일어나면 행은 다시 페이지 아무 데나 들어간다. 일회성 정렬일 뿐, MySQL의 InnoDB 처럼 상시 클러스터링이 아니다.

힙이 정렬되어 있지 않다는 점, 그리고 ctid라는 간접 참조를 거친다는 점은 1편에서 본 HOT update와 직접 연결된다.

HOT update는 인덱스 컬럼이 안 바뀌는 UPDATE에서 인덱스를 건드리지 않고 새 튜플 버전을 만드는 최적화다. 이게 가능한 이유가 ctid의 간접 참조 구조 덕분이다. 인덱스가 라인 포인터 번호를 가리키니, 튜플이 페이지 안에서 자리를 옮겨도 인덱스는 그대로 두고 라인 포인터만 새 위치를 가리키게 바꾸면 된다. 자세한 동작은 1편에서 다뤘다.

---

인덱스 스캔의 비용 — 힙 random I/O

인덱스 스캔은 두 단계다. 그리고 두 단계의 비용은 전혀 다르다.

단계	하는 일	I/O 특성
1. 인덱스 탐색	B-tree를 타고 내려가 ctid를 찾음	적은 페이지, 비교적 저렴
2. 힙 접근	ctid가 가리키는 힙 페이지를 읽음	행마다 흩어진 페이지 — random I/O

실제 비용이 큰 쪽은 힙 접근이다.

인덱스에서 ctid 100개를 찾았다고 해 보자. 그 100개는 힙 여기저기에 흩어져 있다. 힙 페이지 100개를 random하게 읽어야 한다. 디스크 입장에서 random I/O는 sequential I/O보다 훨씬 비싸다.

 

여기서 자주 나오는 질문이 풀린다. "인덱스가 있는데 왜 Sequential Scan을 하지?"

매칭되는 행이 테이블의 큰 비율을 차지하면, 인덱스 스캔이 유발하는 random I/O의 총합이 그냥 테이블을 처음부터 끝까지 순차로 읽는 것(Sequential Scan)보다 비싸진다. 이때는 Sequential Scan이 더 빠른 선택이다. 인덱스를 안 쓰는 게 아니라, 안 쓰는 게 더 빠른 것이다.

이 "어느 쪽이 싼가"를 판단하는 게 7편에서 다룰 Optimizer의 비용 모델이다. 인덱스 스캔의 비용 구조가 여기서 시작된다.

---

인덱스 종류

PostgreSQL은 여러 인덱스 종류를 제공한다. 종류를 고른다는 것은 결국 "이 컬럼에 어떤 연산자로 질문할 것인가"를 고르는 일이다. 같은 데이터라도 =로 찾을 때와 "겹치는가"로 찾을 때 적합한 자료구조가 다르다. 여섯 가지를 차례로 본다.

B-tree — 기본값

• CREATE INDEX에 종류를 지정하지 않으면 B-tree다. 실무에서 만드는 인덱스의 대부분이 B-tree 계열이다.
• B-tree가 답할 수 있는 건 값에 순서가 있을 때의 질문들이다. =, <, >, BETWEEN, IN, ORDER BY, 그리고 접두사 일치(LIKE 'abc%')까지 커버한다.
• 숫자, 문자열, 날짜처럼 정렬 가능한 타입이면 거의 다 B-tree를 쓴다고 보면 된다. 뒤에서 다룰 정렬 성질도 B-tree의 것이다.

GiST — 겹치고 포함되는 데이터

• GiST(Generalized Search Tree)는 R-tree 계열의 균형 트리를 일반화한 프레임워크다. B-tree가 키 하나의 대소를 따진다면, GiST는 "겹치는가 / 포함하는가 / 가까운가"를 따진다.
• 트리의 각 노드는 자식들을 감싸는 경계(bounding box)를 갖는다. 그 경계끼리는 서로 겹칠 수 있다. 이 구조 덕분에 2차원 영역이나 범위처럼 한 줄로 정렬되지 않는 데이터를 다룰 수 있다. 기하 타입, 범위 타입(range), 전문 검색, 최근접 이웃(KNN) 검색이 전부 GiST 위에서 동작한다.
• 대표 사례는 예약 시스템이다. "이 회의실의 예약 시간이 기존 예약과 겹치면 안 된다"는 규칙은 range 타입에 GiST 인덱스를 걸고 EXCLUDE 제약으로 선언적으로 막을 수 있다. 겹침 연산자(&&)를 인덱스가 처리해 준다.

SP-GiST — 공간을 겹치지 않게 분할

• SP-GiST(Space-Partitioned GiST)는 이름에 GiST가 들어가지만 트리 구조가 다르다. GiST가 영역이 겹칠 수 있는 균형 트리라면, SP-GiST는 공간을 겹치지 않게 쪼개 나가는 비균형 트리다.
• 여기 들어가는 자료구조가 쿼드트리, k-d 트리, 기수 트리(radix tree)다. 공통점은 공간을 깔끔하게 분할할 수 있는 데이터라는 점이다.
• 점 데이터, IP 주소(inet), 텍스트 접두사 검색처럼 값이 자연스럽게 구역으로 나뉘는 경우에 GiST보다 유리하다.
• GiST와 SP-GiST는 둘 다 비정형 데이터를 다루지만, 데이터가 겹치며 분포하면 GiST, 겹치지 않게 분할되면 SP-GiST 쪽이 맞다.

GIN — 한 컬럼에 값이 여러 개

• GIN(Generalized Inverted Index)은 역색인(inverted index)이다. 보통의 인덱스가 "행 → 값"이라면, GIN은 "값 → 그 값을 가진 행 목록(ctid 리스트)"으로 뒤집혀 있다.
• 한 컬럼이 값을 여러 개 담는 타입에 쓴다. 배열에서 특정 원소를 찾거나, jsonb에서 특정 키를 찾거나, 문서(tsvector)에서 특정 단어를 찾는 식이다.
• 조회는 극도로 빠른 대신 갱신(Write)이 무겁다. 하나의 행만 추가해도 그 행이 가진 여러 개의 원소(예: JSON의 여러 키)만큼 인덱스 내부 구조를 각각 갱신해야 하므로 쓰기 증폭이 발생하기 때문이다. fastupdate 옵션은 이 갱신을 버퍼에 모아두었다가 백그라운드에서 한 번에 처리하여 쓰기 비용을 분산한다.

BRIN — 거대하고 자연 정렬된 테이블

• BRIN(Block Range Index)은 접근 방식이 다르다. 행 하나하나를 인덱싱하지 않고, 페이지 범위(block range) 단위로 그 안의 min/max만 저장한다. "128페이지 묶음마다 최소·최대 timestamp" 정도만 기록하는 식이다.
  그래서 인덱스가 극도로 작다. 수십 GB 테이블의 BRIN 인덱스가 수십 KB로 끝나기도 한다.
• 대신 전제 조건이 까다롭다. 물리적 저장 순서와 값의 순서가 맞아떨어져야 한다. 시계열 로그처럼 시간 순으로 계속 append되는 테이블이 딱 맞는 경우다. 이런 테이블에서 "어제 오후 데이터"를 찾으면 관련 없는 페이지 범위를 통째로 건너뛴다.
• 값이 테이블 전체에 무작위로 흩어져 있으면 BRIN은 거의 쓸모가 없다. 범위마다 min/max가 테이블 전체 범위와 비슷해져서 아무것도 못 거른다.

Hash — 등치 비교 전용

• Hash 인덱스는 = 하나만 지원한다. 범위도 정렬도 안 된다.
• 등치 비교만 놓고 보면 B-tree와 비슷하거나 약간 빠를 수 있다. 그런데 B-tree가 어차피 =도 잘 처리하면서 범위·정렬까지 커버하기 때문에 Hash를 일부러 고를 일은 많지 않다.
• 등치 비교만 일어나는 게 확실한 큰 컬럼 정도가 후보다.

요약

종류	자료구조	답하는 쿼리	대표 사용처
B-tree	균형 트리	=, 범위, 정렬	거의 모든 일반 컬럼
GiST	겹치는 균형 트리	겹침, 포함, 근접	기하, range, 전문 검색, KNN
SP-GiST	공간 분할 트리	분할 가능한 비정형 데이터	점, IP 주소, 텍스트 접두사
GIN	역색인	포함 (다중 값)	배열, jsonb, 전문 검색
BRIN	페이지 범위 요약	범위 (정렬된 대형 테이블)	시계열 로그
Hash	해시 테이블	= 만	등치 비교 전용

실무에서 가장 자주 보는 건 B-tree다. 그다음이 jsonb·전문 검색에 쓰는 GIN이다. 나머지는 데이터 타입이 그걸 요구할 때 꺼내 쓰는 쪽에 가깝다.

---

B-tree의 정렬 성질

B-tree는 키를 정렬된 상태로 저장한다. 이 성질은 ORDER BY의 정렬 단계를 생략할 수 있게 해준다. ORDER BY created_at 쿼리가 있을 때, created_at에 B-tree 인덱스가 있으면 PostgreSQL은 인덱스를 순서대로 읽기만 하면 된다. 메모리나 디스크에 데이터를 올려놓고 퀵정렬 같은 별도의 정렬 연산(Sort 노드)을 수행할 필요가 없다.

 

⚠️ 단, 물리 데이터(힙)는 정렬되어 있지 않다는 점을 기억하자. 인덱스 가이드를 따라 힙 페이지를 방문할 때 무수한 랜덤 I/O가 발생할 수 있다. 만약 조회하려는 데이터의 양이 많다면, 옵티마이저는 CPU 정렬 비용을 아끼는 것보다 랜덤 I/O 비용이 더 크다고 판단하여 인덱스를 버리고 Sequential Scan + Sort(전체 스캔 후 직접 정렬)를 선택할 수 있다.

 

멀티컬럼 인덱스

멀티컬럼 인덱스에서는 컬럼 순서가 중요하다.

CREATE INDEX idx ON orders (customer_id, created_at);

이 인덱스는 customer_id로 먼저 정렬하고, 같은 customer_id 안에서 created_at으로 정렬한 구조다. 그래서 다음과 같이 쓰인다.

쿼리 조건	인덱스 사용
WHERE customer_id = 1	가능
WHERE customer_id = 1 AND created_at > '...'	가능 (가장 효율적)
WHERE created_at > '...'	비효율적 — 앞 컬럼을 건너뛸 수 없음

전화번호부를 성으로 정렬해 놓으면 이름만으로는 못 찾는 것과 같다. 멀티컬럼 인덱스는 앞 컬럼부터 조건에 써야 의미가 있다.

여기서 자주 나오는 질문이 하나 있다. (customer_id, created_at) 인덱스가 있는데 (customer_id) 단일 인덱스를 따로 둘 필요가 있을까?

대부분의 경우 필요 없다. 멀티컬럼 인덱스는 앞 컬럼 조건(WHERE customer_id = 1)을 이미 처리할 수 있고, 단일 인덱스보다 약간 비쌀 뿐이지 못 하는 게 아니다. 둘 다 만들면 단일 인덱스는 사실상 중복이 되고, 조회를 눈에 띄게 빠르게 해주지도 않으면서 INSERT/UPDATE마다 쓰기 비용만 하나 더 늘린다.

옵티마이저가 두 인덱스 중 어느 쪽을 고르는가, 어떤 경우에 단일 인덱스가 의미를 갖는가는 7편 인덱스 실행 계획에서 다룬다.

---

Index Only Scan

앞에서 인덱스 스캔은 "인덱스 → 힙" 2단계라고 했다. 그런데 힙 접근을 생략할 수 있는 경우가 있다. Index Only Scan이다.

힙으로 가는 이유는 두 가지다.

1. 인덱스에 없는 컬럼 데이터를 읽으려고
2. 그 행이 지금 보이는지(가시성) 확인하려고 — 인덱스에는 t_xmin/t_xmax가 없으니까

이 두 이유가 모두 사라지면 힙에 갈 필요가 없다. 조건은 두 가지다.

힙에 접근하지 않는 조건

조건 1 — 필요한 컬럼이 전부 인덱스에 있을 것

SELECT customer_id FROM orders WHERE customer_id = 1처럼, 쿼리가 읽는 컬럼이 인덱스 키에 다 들어 있으면 1번 이유가 사라진다.

 

조건 2 — 해당 페이지가 all-visible일 것

가시성 문제는 Visibility Map이 해결한다. VM은 각 페이지의 가시성 상태를 비트로 기록하는 보조 자료구조다. all-visible 비트가 켜진 페이지는 그 페이지의 모든 튜플이 모든 트랜잭션에 보인다는 뜻이다.

자세한 동작은 4편에서 다뤘다.

 

인덱스가 가리키는 ctid의 페이지가 all-visible이면, 힙의 튜플 헤더를 안 봐도 그 행이 보인다는 게 보장된다. 2번 이유가 사라진다. 두 조건이 모두 충족되면 PostgreSQL은 힙을 건너뛰고 인덱스만으로 결과를 만든다.

 

커버링 인덱스 — INCLUDE로 조건 1 만들기

조건 1 (필요한 컬럼이 전부 인덱스에 있을 것)을 Postgres에서 의도적으로 만들려면 INCLUDE를 쓴다.

-- customer_id로 검색하고 status도 같이 읽고 싶을 때
CREATE INDEX idx ON orders (customer_id) INCLUDE (status);

status는 검색 조건(키)으로는 안 쓰지만 인덱스에 같이 저장된다. 이런 인덱스를 커버링 인덱스(covering index)라고 한다.

VACUUM이 안 돌면 Index Only Scan도 효과가 없다. 조건 2는 VM이 최신이어야 성립한다. VM의 all-visible 비트는 VACUUM이 켠다. 페이지에 INSERT/UPDATE/DELETE가 일어나면 비트가 꺼지고, 다음 VACUUM이 정리하기 전까지는 꺼진 채다. autovacuum이 못 따라가면 Index Only Scan을 계획해도 결국 힙으로 떨어진다. EXPLAIN의 Heap Fetches 값이 이때 올라간다 — 이름은 Index Only Scan인데 힙을 읽고 있다는 신호다. 자세한 건 7편에서 다룬다.

---

인덱스 유지 비용

인덱스는 조회를 빠르게 하지만, 쓰기에는 비용이다.

 

쓰기 증폭

행을 INSERT하면 그 행은 힙에 한 번 들어간다. 그리고 그 테이블의 모든 인덱스에도 각각 항목이 추가된다. 인덱스가 5개면 INSERT 한 번이 인덱스 쓰기 5번을 유발한다.

UPDATE는 새 버전을 만드는 작업이라 마찬가지로 인덱스 쓰기를 일으킨다. UPDATE가 왜 새 버전을 만드는지는 2편에서 다뤘다.

1편에서 본 HOT update가 바로 이 비용을 줄이는 장치였다.

HOT update는 UPDATE 시 인덱스 컬럼이 안 바뀌고 새 버전이 같은 페이지에 들어갈 수 있으면, 인덱스를 하나도 건드리지 않고 라인 포인터로 새 튜플을 가리키게 하는 최적화다. 자세한 동작은 1편에서 다뤘다.

인덱스 5개짜리 테이블에서 UPDATE 한 번이 인덱스 쓰기 5번이냐 0번이냐의 차이다.

 

인덱스 비대화

인덱스도 dead tuple을 가리키는 항목이 쌓인다. UPDATE/DELETE로 죽은 행을 가리키던 인덱스 항목은 VACUUM이 정리한다. VACUUM이 못 따라가면 인덱스도 비대해진다.

비대해진 인덱스는 탐색할 페이지가 늘어 느려진다. 심하면 REINDEX로 인덱스를 다시 만들어야 한다.

 

인덱스 트레이드오프

조회 속도와 쓰기 비용은 맞바꾸는 관계다. 인덱스를 늘리면 조회는 빨라지지만 쓰기는 그만큼 무거워진다.

안 쓰이는 인덱스는 조회를 빠르게 해주지도 않으면서 쓰기마다 비용만 더한다.

어떤 인덱스가 실제로 쓰이는지는 pg_stat_user_indexes의 idx_scan(이 인덱스가 스캔에 쓰인 횟수)으로 확인할 수 있다.

SELECT relname, indexrelname, idx_scan
FROM pg_stat_user_indexes
ORDER BY idx_scan;

idx_scan이 0에 가까운 인덱스는 삭제 후보다.

---

정리

개념	핵심
인덱스가 저장하는 것	키 + ctid (페이지 번호, 라인 포인터 번호)
보조 인덱스	PostgreSQL의 모든 인덱스는 보조 인덱스. 클러스터형 인덱스 없음
인덱스 스캔 비용	비용의 중심은 힙 random I/O. 매칭 행이 많으면 Sequential Scan이 더 쌀 수 있다
인덱스 종류	B-tree(정렬), GiST(겹침), SP-GiST(공간 분할), GIN(다중 값 포함), BRIN(정렬된 대형 테이블), Hash(등치)
Index Only Scan	필요한 컬럼이 인덱스에 다 있고 + 페이지가 all-visible이면 힙 생략
인덱스 유지 비용	쓰기 증폭, 비대화. 안 쓰이는 인덱스는 비용일 뿐

• 인덱스가 있다고 항상 쓰이는 것도 아니고, 쓰인다고 항상 빠른 것도 아니다. Index Range Scan과 Sequential Scan 중 무엇을 쓸지, 어떤 인덱스를 탈지는 PostgreSQL이 비용을 계산해서 정한다.
• 다음 글(7편)에서는 그 판단의 주체인 Optimizer를 다룬다. Sequential / Index / Index Only / Bitmap Scan이 각각 어떻게 다르고, PostgreSQL이 통계 정보로 비용을 어떻게 추정하며, EXPLAIN을 어떻게 읽는지 알아본다.