2026년 4월 23일 약 20분 분량 이론/데이터베이스

데이터베이스 인덱스 ②: 스캔의 종류와 옵티마이저의 선택

Database Index PostgreSQL EXPLAIN Bitmap Scan Query Optimizer Selectivity Performance

0. 들어가며

인덱스 시리즈 2편입니다. 1편에서 EXPLAIN을 읽는 법 을 익혔다면, 이번 편은 EXPLAIN에 등장하는 스캔 노드들의 메커니즘 과 옵티마이저가 그 중 무엇을 언제 선택하는가 를 다룹니다. 같은 인덱스, 같은 데이터에서도 쿼리 모양에 따라 plan이 달라지는 이유 를 이해하는 편입니다.

핵심 메시지: 인덱스가 있다고 모든 쿼리가 같은 방식으로 그 인덱스를 쓰는 것은 아니다. PostgreSQL은 Sequential Scan / Index Scan / Index-Only Scan / Bitmap Index Scan + Bitmap Heap Scan 같은 여러 스캔 전략을 가지고 있고, 옵티마이저는 통계 기반 셀렉티비티 추정 에 따라 비용이 가장 낮은 plan 을 고릅니다. 셀렉티비티가 매우 낮으면 Index Scan, 매우 높으면 Seq Scan, 중간이면 Bitmap Scan, 이 스펙트럼이 핵심입니다.

인덱스 시리즈 2편 커버: 셀렉티비티 스펙트럼

글의 범위: 이번 편은 스캔의 종류와 선택 메커니즘 까지 다룹니다. Index-Only Scan의 진짜 IOS 조건(Visibility Map과의 관계)은 3편에서 deep dive하고, 복합 인덱스/AND/OR 동작은 4편에서 다룹니다.

1. 스캔이란 무엇인가

Scan Node: 쿼리 plan의 가장 아래

PostgreSQL의 쿼리 plan은 트리 구조 입니다. 가장 아래에 있는 노드가 Scan Node, 즉 테이블이나 인덱스에서 raw row를 가져오는 단계 입니다. 그 위에 sort, join, aggregate 같은 노드들이 쌓입니다.

이번 편에서 다룰 스캔 노드 5종:

Sequential Scan (Seq Scan): 테이블 전체를 처음부터 끝까지 읽음
Index Scan: 인덱스에서 후보를 찾고 → 힙(테이블)으로 가서 행을 가져옴
Index-Only Scan: 인덱스만으로 답이 완료, 힙으로 안 감 (3편에서 deep dive)
Bitmap Index Scan: 인덱스 스캔으로 페이지 비트맵 을 만듦
Bitmap Heap Scan: 비트맵을 사용해 페이지를 물리적 순서로 읽음

이 중 Bitmap Index Scan은 단독으로 최종 결과를 반환하지 않습니다. 보통 상위 Bitmap Heap Scan에서 소비 되며, 중간에 BitmapAnd / BitmapOr 가 끼기도 합니다. 사실상 4가지 주요 전략, 즉 Seq, Index, IOS, Bitmap이 있다고 보면 됩니다.

옵티마이저의 선택: 셀렉티비티가 결정한다

옵티마이저는 통계(pg_statistic)를 기반으로 각 plan의 cost를 추정 하고 가장 낮은 cost를 선택 합니다. 핵심 변수는 셀렉티비티(selectivity), 즉 조건이 매칭하는 행의 비율 입니다. PostgreSQL 공식 문서가 정의하듯, “WHERE 조건이 row의 얼마나 많은 부분을 통과시키는가” 가 plan 결정의 출발점입니다.

셀렉티비티 스펙트럼: 매칭 비율이 plan을 결정한다

다만 이것은 대략적 경향성 이지 고정 규칙은 아닙니다. 셀렉티비티는 출발점일 뿐이며, 실제 plan 선택은 cost 모델의 종합 계산 결과 입니다. correlation(컬럼 값과 물리적 순서의 상관성), cost 파라미터(seq_page_cost/random_page_cost/effective_cache_size), 캐시 상태, row width, parallel 가능성 등 여러 요소가 함께 작용합니다.

1장 요약: Scan Node는 plan tree의 가장 아래에서 raw row를 가져오는 단계 입니다. 옵티마이저는 셀렉티비티 에 따라 4가지 주요 전략(Seq / Index / IOS / Bitmap) 중 하나를 cost 기반으로 선택합니다.

2. Sequential Scan: 테이블 전체 순차 읽기

동작

가장 단순한 스캔입니다. 테이블의 첫 페이지부터 마지막 페이지까지 차례대로 읽으면서 WHERE 조건으로 필터링합니다.

1
EXPLAIN ANALYZE SELECT * FROM grades WHERE name = 'Z';

1
 Parallel Seq Scan on grades
2
   (cost=1000.00..125000.00 rows=10 width=20)
3
   (actual time=2845..3012 rows=8 loops=1)
4
   Filter: (name = 'Z')
5
   Rows Removed by Filter: 11000000

Rows Removed by Filter: 11000000, 1100만 행을 전부 읽고 필터로 걸러냈습니다.

언제 선택되는가

직관과 다르게, Seq Scan이 항상 나쁜 것은 아닙니다. 다음 경우 옵티마이저는 Seq Scan을 적극적으로 선택합니다:

인덱스가 없는 컬럼 조건: 다른 선택지가 없으니 Seq Scan
테이블이 매우 작음: 인덱스 메타데이터 읽는 비용이 전체 테이블 읽기 보다 클 수 있음
반환할 행이 많음: 거의 모든 행이 매칭하면 인덱스로 후보 찾기 + 힙 random IO 가 순차 IO 보다 비쌈
SELECT * + 모든 컬럼 인덱스 가정 무용: 어차피 힙으로 가야 함

Parallel Seq Scan

PostgreSQL은 큰 테이블의 Seq Scan 을 병렬 로 처리할 수 있습니다. 여러 worker 프로세스가 테이블을 분할해서 동시에 스캔 한 뒤 Gather 노드 가 결과를 합칩니다. 다만 parallel 사용 여부 는 옵티마이저가 parallel_setup_cost / parallel_tuple_cost / min_parallel_table_scan_size(기본 8MB) / max_parallel_workers_per_gather 를 종합해 결정합니다. 작은 테이블이거나 cost 이득이 없으면 parallel을 안 씁니다. 또한 모든 쿼리가 parallel 가능한 것은 아닙니다. PARALLEL UNSAFE로 표시된 함수, SERIALIZABLE 격리 수준, FOR UPDATE 같은 lock 절, cursor 사용은 parallel을 막습니다.

2장 요약: Seq Scan은 테이블 전체 순차 읽기 입니다. 인덱스 부재 / 작은 테이블 / 높은 셀렉티비티에서 선택됩니다. Parallel Seq Scan은 큰 테이블 + worker 띄울 만한 cost 이득 이 있을 때만 사용합니다.

3. Index Scan: 인덱스에서 찾고 힙으로 점프

동작

가장 직관적인 인덱스 활용 패턴:

인덱스를 스캔 해서 조건에 맞는 후보의 위치(CTID) 를 찾는다
각 후보에 대해 힙(테이블)으로 점프 해서 실제 행을 읽는다
필요한 컬럼을 반환

1
EXPLAIN ANALYZE SELECT name FROM employees WHERE id = 7;

1
 Index Scan using employees_pkey on employees
2
   (cost=0.43..8.45 rows=1 width=20)
3
   (actual time=0.012..0.045 rows=1 loops=1)
4
   Index Cond: (id = 7)

Index Cond: (id = 7)은 인덱스를 id=7로 검색해서 정확히 한 후보를 찾고, 힙으로 가서 name 컬럼 을 읽습니다.

핵심 비용: 힙으로의 random IO

Index Scan의 약점은 힙 접근의 random IO 입니다. 인덱스 자체는 정렬되어 있지만, 인덱스가 가리키는 힙 위치 는 디스크 상에서 흩어져 있을 수 있습니다. 매 행마다 서로 다른 페이지 로 점프하면, 순차 IO 대비 4배 비싼 random IO(random_page_cost=4.0 기본값)가 누적됩니다.

Index Scan vs Bitmap Scan: 같은 인덱스, 다른 IO 패턴

이 비용 때문에 반환 행이 많아지면 Index Scan이 갑자기 비효율적 이 됩니다. 정확히는 행 수가 아니라 서로 다른 페이지 접근 수 가 늘어나면서 random IO 비용이 누적됩니다 (같은 페이지에 여러 행이 모여 있거나 buffer cache hit이 있으면 실제 IO는 더 적을 수 있습니다). 그래도 행이 물리적으로 흩어져 있을수록 비용은 빠르게 폭증합니다.

언제 선택되는가

셀렉티비티가 매우 낮을 때: 한두 행, 또는 0.x% 수준
LIMIT이 작은 경우: 필요한 행이 전체 중 몇 개 라 random IO 누적 비용이 작음
점프가 physical order에 가까운 경우 (correlation 높음): 인덱스 순서와 힙 순서가 비슷하면 random IO가 순차 IO처럼 빨라짐 (pg_stats.correlation이 이를 추적). CLUSTER table_name USING idx_name 명령으로 테이블을 인덱스 순서로 물리적 재배치 해 correlation을 인위적으로 높일 수도 있습니다. 단 PostgreSQL 공식 문서가 명시하듯 CLUSTER는 one-time 작업 이고 이후 INSERT/UPDATE는 clustering을 유지하거나 보장하지 않습니다. HOT update는 같은 페이지 안 에서 새 버전을 만들 수 있어 물리적 locality 훼손을 줄일 수는 있지만 clustering 순서 보장 메커니즘은 아닙니다.

3장 요약: Index Scan은 인덱스로 후보 찾고 힙으로 점프 입니다. 약점은 힙의 random IO 누적 이라 일반적으로 매우 낮은 셀렉티비티에서 가장 효율적 이지만, 데이터 배치(correlation)나 캐시 상태에 따라 그 효율 범위는 중간 셀렉티비티까지 확장 될 수 있습니다.

4. Bitmap Index Scan + Bitmap Heap Scan: 중간 지점

왜 필요한가

Index Scan은 너무 많고 Seq Scan은 너무 적은 중간 지점 에서 옵티마이저가 선택하는 하이브리드 전략 입니다. PostgreSQL 공식 문서가 직접 “Like an index scan, it scans an index… but like a sequential scan, it takes advantage of data being easier to read in bulk” 라고 표현합니다.

동작

두 단계로 나뉩니다:

1단계: Bitmap Index Scan

인덱스를 스캔해 조건에 맞는 행들의 위치 를 찾음
결과를 행 하나하나로 반환하지 않고, 페이지 기반 비트맵 으로 만든다 (PostgreSQL의 TIDBitmap 구조)
정상적인 exact bitmap 은 페이지 단위 chunk + 그 안에서 tuple offset bitmap 까지 기억, 즉 어느 페이지의 어느 row가 매칭하는지 정확히 추적. PostgreSQL 내부 구조로는 PageTableEntry per page 에 최대 256개 tuple bitmap (8KB 페이지 기준)
work_mem이 부족 하면 일부 chunk가 lossy 모드 로 축약, 페이지 단위로만 기억하고 tuple offset은 버림 (이 경우 heap에서 페이지 전체를 읽고 재검증해야 함)

2단계: Bitmap Heap Scan

비트맵의 페이지들을 물리적 페이지 번호 순서대로 읽음 → 완전한 순차 IO는 아니지만, 페이지 접근을 정렬해 random IO를 크게 줄이는 방식 (흩어진 random 접근보다 훨씬 효율적)
lossy 페이지 에서는 페이지 내 조건을 만족하지 않는 행 을 다시 필터링 (Recheck Cond)

1
EXPLAIN ANALYZE
2
SELECT * FROM customer_records
3
WHERE state_code = 'KS' AND gender = 'F';

1
 Bitmap Heap Scan on customer_records
2
   (cost=835.78..8669.29 rows=49226 width=12)
3
   Recheck Cond: (state_code = 'KS')
4
   Filter: (gender = 'F')
5
   Heap Blocks: exact=6370
6
   ->  Bitmap Index Scan on idx_state_code
7
         (cost=0.00..823.48 rows=97567 width=0)
8
         Index Cond: (state_code = 'KS')

해석:

Bitmap Index Scan이 먼저 실행 → 인덱스에서 state_code=‘KS’ 후보 페이지 비트맵 생성
Bitmap Heap Scan이 비트맵에 표시된 페이지들을 물리적 순서로 읽음
Recheck Cond: exact 비트맵 에서는 plan에 표시만 되고 실제로 의미 있는 row 제거는 거의 발생하지 않음. 진짜로 작동하는 경우 는 (1) lossy bitmap (work_mem 부족으로 비트맵이 페이지 단위 로 축약된 경우), 페이지 내 어느 행이 매칭하는지 모르므로 전체 페이지 fetch + 행마다 재검증, (2) lossy index type (예: GiST/BRIN, 인덱스가 후보를 대략 반환하므로 정확한 매칭 재검증 필요)
Heap Blocks: exact=6370, 6,370개 페이지를 읽음

다중 인덱스 결합: BitmapAnd / BitmapOr

Bitmap Scan의 진짜 강력한 능력 은 여러 인덱스의 비트맵을 결합 할 수 있다는 점입니다:

1
EXPLAIN SELECT * FROM test
2
WHERE a = 100 AND b = 100;

1
 Bitmap Heap Scan on test
2
   ->  BitmapAnd
3
         ->  Bitmap Index Scan on idx_a
4
               Index Cond: (a = 100)
5
         ->  Bitmap Index Scan on idx_b
6
               Index Cond: (b = 100)

BitmapAnd: 두 인덱스의 비트맵을 교집합으로 결합

해석:

idx_a 비트맵 + idx_b 비트맵을 AND 연산 해 둘 다 만족하는 페이지 만 남김
그 결합된 비트맵으로 한 번만 힙 접근

OR 조건이면 BitmapOr로 합집합 비트맵을 생성합니다. 즉 단일 인덱스로는 못 풀 쿼리도 여러 인덱스 결합으로 효율적으로 처리 가능합니다.

언제 선택되는가

중간 셀렉티비티: 수~수십 %. Index Scan은 random IO가 너무 많고, Seq Scan은 너무 많이 읽음
다중 인덱스 결합 가능: 두 컬럼에 각각 인덱스가 있고 AND/OR로 묶인 쿼리
인덱스 후보가 많지만 페이지 수는 적당히 적은 경우: 비트맵의 페이지 단위 묶기가 효과적

Recheck Cond와 lossy bitmap

Recheck Cond가 plan에 표시되는 것이 항상 의미 있는 작업 은 아닙니다. 진짜로 row 제거가 일어나는 경우는 두 가지:

1. lossy bitmap (work_mem 부족)

정상적인 exact bitmap은 페이지 단위로 관리되며, 각 페이지 안에서 어떤 tuple이 매칭되는지 비트로 표시합니다. PostgreSQL 내부 구조로는 PageTableEntry per page (페이지마다 한 chunk) + 그 chunk 안에 tuple offset bitmap (8KB 페이지에 최대 256 tuples). 즉 순수한 행 단위 비트 배열이 아니라, 페이지 기반 + 페이지 안에서 tuple 위치까지 정확히 추적 하는 두 단계 구조입니다. work_mem이 부족하면 PageTableEntry 일부가 lossy로 축약 되고, 이 경우 tuple offset bitmap을 버리고 페이지 단위로만 기억하므로 heap에서 전체 페이지 fetch + 각 행 재검증 이 필요합니다. 여기서 진짜 Recheck Cond 비용이 발생합니다.

EXPLAIN 출력의 Heap Blocks: exact=N lossy=M이 결정적 신호입니다. lossy > 0이면 work_mem을 늘리는 것이 첫 처방입니다. Rows Removed by Index Recheck: N도 같이 보면 lossy로 인한 비효율을 정량화할 수 있습니다.

2. lossy index type (GiST, BRIN 등)

GiST나 BRIN 같은 인덱스는 후보를 대략적으로만 반환합니다. 예를 들어 BRIN은 블록 범위 요약 이라 값 범위가 겹치는 블록의 모든 행 을 후보로 던지고, 진짜 매칭은 heap에서 재확인해야 합니다. 이 경우 Recheck Cond가 항상 의미 있는 작업입니다.

B-tree + exact bitmap에서는 lossy bitmap에 비해 recheck 비용이 작습니다. 다만 인덱스 타입(GIN/GiST/BRIN)이나 추가 조건 에 따라 exact pages인데도 Rows Removed by Index Recheck가 나타나는 케이스가 있습니다 (PostgreSQL 메일링 리스트에 사례 보고됨). 즉 Recheck Cond의 실제 비용은 plan만으로 추정하지 말고 EXPLAIN ANALYZE의 Rows Removed by Index Recheck로 확인 해야 합니다.

Index Cond vs Filter: 미묘한 차이

EXPLAIN 출력에서 Index Cond와 Filter는 겉모양은 비슷해 보여도 의미가 다릅니다:

Index Cond: 인덱스 자체로 후보를 좁히는 조건. B-tree에서 범위를 줄이는 access predicate
Filter: 후보 행을 가져온 뒤 적용하는 조건. 인덱스로 좁히지 못해 모든 후보 행 에 대해 평가

Index Cond vs Filter: access predicate vs filter predicate

1
 Index Scan using idx_a on test
2
   Index Cond: (a = 100)
3
   Filter: (b = 100)        -- 인덱스로 못 좁힘, heap에서 행마다 재평가

여기서 b = 100은 모든 a=100 후보 행을 가져온 뒤 적용합니다. 후보가 많으면 비효율 이라 복합 인덱스로 풀어야 할 신호 입니다 (4편에서 deep dive).

4장 요약: Bitmap Scan은 Index Scan과 Seq Scan의 중간 입니다. 페이지 단위 비트맵을 물리적 순서로 읽기 하고 여러 인덱스 결합 가능합니다. Recheck Cond는 lossy bitmap 또는 lossy index 에서만 진짜 비용이 발생하며, Heap Blocks: lossy > 0이면 work_mem 부족 신호입니다. Index Cond vs Filter는 인덱스 활용 vs heap 재평가 의 차이입니다.

5. Index-Only Scan: 힙으로 안 가는 최선의 경우

동작

인덱스 안에 쿼리가 필요한 모든 컬럼 이 들어있으면, 힙으로 안 가도 답을 만들 수 있습니다. 진짜 최선의 plan 입니다.

1
EXPLAIN ANALYZE SELECT id FROM grades WHERE id = 7;

1
 Index Only Scan using grades_pkey on grades
2
   (cost=0.43..8.45 rows=1 width=4)
3
   (actual time=0.005..0.005 rows=1 loops=1)
4
   Index Cond: (id = 7)
5
   Heap Fetches: 0

Heap Fetches: 0, 힙 접근이 0번입니다. 인덱스만으로 답을 완료합니다.

진짜 IOS의 조건은 까다롭다

Index Only Scan 노드가 plan에 잡혔다고 진짜 IOS는 아닙니다. PostgreSQL의 IOS는 Visibility Map(VM)과 협업해야 진정한 효과를 봅니다. VM이 해당 페이지가 모든 트랜잭션에 visible 이라고 표시한 경우에만 힙 접근을 생략 할 수 있습니다. VM이 최신이 아니면 Heap Fetches > 0가 되어 결국 힙으로 가야 합니다.

이 메커니즘은 3편에서 deep dive 합니다 (스토리지 ③편의 Visibility Map 내용과 통합). 이번 편에서는 Heap Fetches 값이 IOS의 진짜 효율을 보여준다 는 점만 기억하면 됩니다.

Covering Index: INCLUDE로 IOS 만들기

기본적으로 인덱스에는 키 컬럼 만 들어갑니다. 추가 컬럼 까지 인덱스에 포함시키면 IOS 가능 범위가 넓어집니다. INCLUDE 절을 씁니다:

1
CREATE INDEX idx_grades_id_name
2
ON grades(id) INCLUDE (name);

이러면 SELECT id, name FROM grades WHERE id = 7도 인덱스만으로 답할 수 있습니다 (id가 검색 키, name이 비검색 데이터). 이것을 Covering Index 라 부르고, 3편에서 INCLUDE 절의 트레이드오프와 함께 deep dive 합니다.

언제 선택되는가

쿼리에 필요한 모든 컬럼이 인덱스에 있음 (covering index)
VM이 최신: VACUUM이 잘 돌고 있어 visible 표시가 정확
SELECT * 같은 패턴이 아님: 모든 컬럼 요구는 IOS 거의 불가능

5장 요약: IOS는 힙 접근 없이 인덱스만으로 답 완료 하는 최선의 plan입니다. 다만 VM 최신성 조건이 있어 Heap Fetches > 0이면 진짜 IOS가 아닙니다. 3편에서 자세히 다룹니다.

6. 옵티마이저는 어떻게 인덱스를 선택하는가

통계 기반 셀렉티비티 추정

옵티마이저의 모든 결정의 출발점 은 셀렉티비티 추정입니다. 이를 위해 PostgreSQL은 각 컬럼 에 대해 다음 통계를 유지합니다 (pg_statistic, 사용자용 뷰는 pg_stats):

reltuples / relpages: 테이블 전체 행 수, 페이지 수
n_distinct: 컬럼의 고유값 수
null_frac: NULL 비율
most_common_vals (MCV): 가장 자주 나오는 값들과 빈도
histogram_bounds: MCV에 없는 값들의 분포 (default 100 buckets)
correlation: 컬럼 값 순서와 물리적 디스크 순서 의 상관성 (-1~1)

이 통계는 ANALYZE 명령 이나 autovacuum의 자동 분석 으로 갱신됩니다. 통계가 부정확하면 plan이 망가집니다. 1편에서 봤듯 추정 vs 실측 격차 가 진단 신호입니다.

다중 인덱스: 어떤 걸 쓸까

여러 컬럼에 각각 인덱스가 있는 경우, 옵티마이저는 세 가지 시나리오를 검토합니다:

시나리오 1: 두 인덱스 모두 사용 (BitmapAnd/BitmapOr)

각각의 인덱스를 비트맵으로 만들어 결합합니다. AND 조건이고 두 인덱스 모두 적당히 셀렉티브 할 때 효과적입니다.

시나리오 2: 한 인덱스만 사용 + 추가 필터

더 셀렉티브한 인덱스 하나만 사용해 후보를 줄이고, 다른 조건은 필터 로 처리합니다.

1
 Index Scan using idx_a on test
2
   Index Cond: (a = 100)
3
   Filter: (b = 100)

Index Cond는 인덱스로 직접 필터링 하고, Filter는 힙에서 가져온 행에 대해 필터링 합니다. AND 조건에서 셀렉티브한 쪽이 인덱스로, 나머지는 필터 로 처리되는 패턴입니다.

시나리오 3: 둘 다 안 씀

두 인덱스 모두 너무 많은 행을 반환하면 그냥 Seq Scan 입니다. 통계 기반 으로 cost가 가장 낮은 plan 이 결정됩니다.

AND vs OR: 동작 차이

옵티마이저의 결정에 AND인지 OR인지 가 결정적입니다:

AND: 교집합 입니다. 한쪽만 충분히 셀렉티브 하면 그 인덱스만 사용 하고 나머지는 Filter로 처리되는 경우가 많습니다. 다만 두 조건 모두 적당히 셀렉티브 하면 BitmapAnd로 결합 하는 것이 더 효율적인 경우도 있어 옵티마이저가 cost로 결정합니다.
OR: 합집합 입니다. 어느 한쪽이라도 매칭하는 행이 모두 결과입니다. 모든 관련 인덱스를 다 봐야 함. 결과적으로 Bitmap Scan + BitmapOr 가 자연스럽거나, 아예 Seq Scan 이 더 효율적일 수도 있습니다.

4편에서 복합 인덱스 + AND/OR 를 더 자세히 다룹니다.

옵티마이저가 인덱스를 안 쓰는 이유

함수/표현식 적용: WHERE LOWER(name) = 'z', 함수 인덱스를 따로 만들어야 함
LIKE 시작 와일드카드: WHERE name LIKE '%Z%', B-tree로 해결 불가
암묵적 타입 변환: WHERE id::TEXT = '100', 인덱스가 원본 타입 에 만들어졌으므로 적용 불가
너무 많은 행 반환 예상: 통계상 Seq Scan이 더 싸다 고 판단
통계가 stale: ANALYZE 안 돌아 옵티마이저가 잘못된 가정

6장 요약: 옵티마이저는 통계 기반 셀렉티비티 추정 으로 plan을 결정합니다. 다중 인덱스는 결합 / 단일 사용 / 둘 다 무시 세 시나리오 중 cost가 낮은 것이 선택되며, AND vs OR로 동작이 크게 달라집니다. 함수/와일드카드/타입 변환 이 인덱스 사용을 막는 흔한 패턴입니다.

7. 실전: 같은 인덱스, 다른 plan

같은 테이블, 같은 인덱스에서 조건 형태에 따라 plan이 달라지는 예를 봅니다. grades 테이블에 G(grade) 에 인덱스가 있고 id 에는 PK 인덱스가 있습니다.

패턴 1: 매우 셀렉티브한 조건 → Index Scan

1
EXPLAIN SELECT name FROM grades WHERE id = 1000;

1
 Index Scan using grades_pkey on grades
2
   Index Cond: (id = 1000)

한 행입니다. Random IO 1번. Index Scan을 선택합니다.

패턴 2: 중간 셀렉티비티 → Bitmap Scan

1
EXPLAIN SELECT name FROM grades WHERE g > 95;

1
 Bitmap Heap Scan on grades
2
   Recheck Cond: (g > 95)
3
   ->  Bitmap Index Scan on idx_g
4
         Index Cond: (g > 95)

대략 5% 수준의 행이 매칭합니다. 이 정도 셀렉티비티에서 Index Scan은 random IO 부담이 크고, Seq Scan은 95%를 버려야 하는 낭비 가 있어 Bitmap이 합리적인 선택지가 됩니다 (정확한 임계값은 데이터 분포/cost 설정에 따라 달라집니다).

패턴 3: 너무 많은 행 → Seq Scan (인덱스가 있어도)

1
EXPLAIN SELECT name FROM grades WHERE id > 100;

1
 Seq Scan on grades
2
   Filter: (id > 100)

거의 모든 행이 매칭합니다. 인덱스를 무시하고 Seq Scan을 선택합니다.

패턴 4: 다중 인덱스 결합 → BitmapAnd

1
EXPLAIN SELECT * FROM grades WHERE g > 95 AND id < 10000;

1
 Bitmap Heap Scan on grades
2
   ->  BitmapAnd
3
         ->  Bitmap Index Scan on idx_g
4
               Index Cond: (g > 95)
5
         ->  Bitmap Index Scan on grades_pkey
6
               Index Cond: (id < 10000)

두 인덱스 모두 적당히 셀렉티브합니다. 결합으로 결과가 더 작아집니다.

패턴 5: 함수 적용 → 인덱스 못 씀

1
EXPLAIN SELECT name FROM grades WHERE LOWER(name) = 'z';

1
 Seq Scan on grades
2
   Filter: (lower(name) = 'z')

인덱스가 name 에 있어도 LOWER(name)에는 없습니다. 함수 인덱스가 필요하거나, 데이터를 미리 소문자로 저장해야 합니다.

7장 요약: 같은 인덱스가 있어도 조건의 셀렉티비티 + 형태 에 따라 Index / Bitmap / Seq plan이 갈립니다. 함수/표현식은 원본 인덱스를 무력화 시킵니다.

8. 정리

핵심 통찰

PostgreSQL의 4가지 주요 스캔: Sequential / Index / Index-Only / Bitmap. Bitmap은 Index Scan과 Seq Scan의 중간. Bitmap Index Scan은 단독으로 결과를 내지 않고, 보통 BitmapAnd/BitmapOr를 거쳐 Bitmap Heap Scan에서 소비 된다.
선택의 기준은 셀렉티비티: 매우 낮으면 Index Scan, 매우 높으면 Seq Scan, 중간이면 Bitmap. 정확한 임계값은 cost 모델 + 데이터 분포 + correlation + 캐시 상태 에 따라 달라진다.
Index Scan의 약점은 힙 random IO 누적: 서로 다른 페이지 접근 수 가 누적 비용을 결정. correlation 높거나 cache hit 많으면 효율 범위가 중간 셀렉티비티까지 확장될 수 있음.
Bitmap Scan의 본질은 random IO를 물리적 순서로 정렬해 크게 줄이기: 페이지 단위 비트맵을 물리적 순서로 읽기. Recheck Cond는 lossy bitmap(work_mem 부족) 또는 lossy index type 에서만 진짜 비용, Heap Blocks: lossy > 0이 신호.
다중 인덱스 결합 (BitmapAnd / BitmapOr): 단일 인덱스로 못 풀 쿼리도 여러 인덱스의 비트맵 결합 으로 효율 가능.
IOS는 진짜 IOS여야 효과: Heap Fetches: 0이어야 함. VM 최신성 조건은 3편에서.
옵티마이저의 통계 기반 결정은 한계가 있다: stale 통계, 컬럼 상관관계, 함수/와일드카드, 타입 변환이 plan을 망가뜨리는 흔한 원인.

진짜 한 줄

인덱스가 있어도 어떻게 쓰일지는 셀렉티비티가 결정한다. PostgreSQL의 스캔 전략은 Index Scan만 있는 것이 아니라 Seq / Index / IOS / Bitmap 4가지 스펙트럼이고, 옵티마이저는 그 중 가장 싼 것을 고를 뿐 이다.

통합된 답: 한 단락 정리

PostgreSQL은 Sequential Scan / Index Scan / Index-Only Scan / Bitmap Index Scan + Bitmap Heap Scan 등 여러 스캔 전략을 가지고 있고, 옵티마이저는 통계 기반 으로 cost가 가장 낮은 plan 을 고릅니다. 셀렉티비티가 가장 중요한 변수지만 유일한 변수는 아니며, correlation/cost 파라미터/캐시 상태/row width/parallel 가능성이 함께 작용합니다. Seq Scan 은 인덱스 없거나/작은 테이블/높은 셀렉티비티에서 선택되며 parallel 가능 (단 PARALLEL UNSAFE 함수, SERIALIZABLE, FOR UPDATE 등은 막음). Index Scan 은 인덱스로 후보 찾고 힙으로 random IO로 점프 하는 패턴이라 일반적으로 매우 낮은 셀렉티비티에서 가장 효율적 이지만, 정확히는 서로 다른 페이지 접근 수 가 누적 비용을 결정하므로 correlation이 높거나 cache hit이 많으면 중간 셀렉티비티(예: 5%)에서도 충분히 효율적 일 수 있습니다. correlation이 높을수록 Index Scan 효율이 올라가고 CLUSTER로 인위적으로 높일 수도 있지만 one-time 작업 이라 이후 INSERT/UPDATE는 정렬을 보장하지 않습니다. Bitmap Scan 은 Index와 Seq의 중간 지점 에서 비트맵 을 만들어 완전한 순차 IO는 아니지만 페이지 접근을 정렬해 random IO를 크게 줄이고, BitmapAnd / BitmapOr 로 여러 인덱스 결합 까지 가능합니다. exact bitmap 은 페이지 + tuple offset까지 정확히 추적하지만 work_mem 부족 하면 lossy(페이지 단위)로 축약 되어 Recheck Cond가 진짜 비용이 발생합니다. Heap Blocks: lossy > 0이 결정적 신호입니다. lossy index type(GIN/GiST/BRIN)이나 추가 조건에서도 recheck가 의미 있을 수 있어 Rows Removed by Index Recheck로 확인이 정확합니다. Bitmap Index Scan은 단독으로 결과를 내지 않고 보통 BitmapAnd/BitmapOr를 거쳐 Bitmap Heap Scan에서 소비 됩니다. Index Cond vs Filter는 인덱스 활용 범위 vs heap 재평가 의 차이라 후자가 많으면 복합 인덱스 신호 입니다. Index-Only Scan 은 인덱스만으로 답 완료 하는 최선의 plan이지만 Visibility Map 최신성 이 조건이라 Heap Fetches: 0이어야 진짜 IOS입니다 (3편 deep dive). 다중 인덱스 환경에서는 결합 / 단일 사용 / 둘 다 무시 시나리오 중 cost가 낮은 것이 선택되며, AND vs OR 로 동작이 갈립니다. AND는 한쪽만 충분히 셀렉티브 하면 단일 인덱스 + Filter, 둘 다 적당히 셀렉티브 면 BitmapAnd입니다. OR는 모든 인덱스를 봐야 함. 함수/표현식 적용, LIKE 시작 와일드카드, 암묵적 타입 변환은 원본 인덱스를 무력화 시키는 흔한 패턴입니다. EXPLAIN으로 plan 노드 종류를 확인 해 옵티마이저의 실제 선택 을 검증하는 것이 튜닝의 출발점입니다.

글의 범위와 한계

이 글은 PostgreSQL 기준 입니다. 스캔 노드의 종류와 명칭은 DBMS마다 다릅니다. MySQL의 EXPLAIN은 type 컬럼 에 ALL (Seq Scan 해당), index, range, ref, eq_ref, const 같은 값으로 표현하고, Bitmap Index Scan은 PostgreSQL 특유의 메커니즘 입니다 (MySQL InnoDB는 비슷한 효과를 Index Merge 로 처리). 다만 옵티마이저가 셀렉티비티 기반으로 plan을 결정한다 는 본질은 모든 RDBMS에 공통이고, 사고법 자체는 이식 가능합니다.

또한 이번 편은 cost 계산의 정확한 공식 은 다루지 않았습니다. seq_page_cost, random_page_cost, cpu_tuple_cost, cpu_index_tuple_cost, cpu_operator_cost 같은 cost 모델 상수의 상세한 조합 공식 은 PostgreSQL 공식 문서 Section 14.2 Statistics Used by the Planner 와 Section 19.7 Query Planning 을 참고하면 됩니다.

참고 (1차 자료 우선)

PostgreSQL Documentation — Using EXPLAIN: 스캔 노드 출력 해석
PostgreSQL Documentation — Statistics Used by the Planner: pg_statistic, pg_stats, MCV, histogram
PostgreSQL Documentation — Row Estimation Examples: 셀렉티비티 계산의 실제 예시
PostgreSQL Documentation — Planner/Optimizer: paths, plans, GEQO
PostgreSQL Documentation — CLUSTER: 테이블의 물리적 재배치, one-time 작업
Crunchy Data — Postgres Scan Types in EXPLAIN Plans: 스캔 종류별 실전 해설
Crunchy Data — Postgres’ Clever Query Planning System: 셀렉티비티와 통계
pganalyze — Bitmap Index Scan: Bitmap Scan 메커니즘 상세
pganalyze — Bitmap Heap Scan + lossy bitmap insights: exact vs lossy block 차이
pganalyze — How Postgres Chooses Which Index To Use For A Query: 옵티마이저의 인덱스 선택 과정
pgMustard — Recheck Cond: Recheck Cond는 lossy 상황에서만 의미
pgMustard — Index Cond: Index Cond와 Filter의 차이
Use The Index, Luke! — Filter Predicates: access vs filter predicate
Yugabyte — Bitmap Scans on Distributed PostgreSQL: TIDBitmap 내부 구조 (PageTableEntry / 256 tuples per page)
Postgres Pro — Queries in PostgreSQL: 4. Index scan: exact vs lossy bitmap, chunk 크기 (32 bytes per page)
Paquier — Postgres 9.4 lossy/exact pages for bitmap heap scan: lossy bitmap의 work_mem 의존성 실험
CYBERTEC — Use HOT, so CLUSTER won’t rot: CLUSTER 후 correlation 보존을 위한 HOT update
Percona — One Index, Three Different PostgreSQL Scan Types: 같은 인덱스, 다른 scan
CYBERTEC — PostgreSQL indexing: Index scan vs. Bitmap scan vs. Sequential scan: 세 스캔의 비교

작성자 @범수

오늘의 노력이 내일의 전문성을 만든다고 믿습니다.

댓글 수정/삭제는 GitHub Discussions에서 가능합니다.