SQL: 인덱스

※ SQL: Index.

 

안녕하세요. 듀스트림입니다.

 

오늘 포스팅은 DBMS 옵티마이저는 '어떤 SQL에 인덱스가 필요하다고 판단하는지'와 '인덱스 최적화가 무엇인지'에 대해 정리한 이론적인 내용입니다.

 

한 번쯤 읽어두시면 도움이 될 거라고 확신합니다. (예시는 PostgreSQL이 대부분입니다.)

---

1. 왜 인덱스는 빠를까요? - 비용모형 관점

• 대부분의 RDBMS는 비용 기반 옵티마이저(CBO) 로 실행계획을 고릅니다.
• 비용은 대략 “디스크 페이지 읽기 + CPU 비교·연산 + 정렬/조인”의 합산으로 추정합니다.
• PostgreSQL은 seq_page_cost·random_page_cost 등 상수에 기반해 페이지 접근 비용을 모델링하고, MySQL은 server_cost/engine_cost 테이블로 조정 가능한 비용모형을 사용합니다.
• 인덱스 접근은 보통 O(log N) 계열로 필요한 페이지 수를 줄입니다. 그러나 무작위 페이지(random) 접근이 늘면 순차 스캔 대비 불리해질 수 있어, 옵티마이저는 선택도(selectivity) 와 랜덤/순차 비용 비율을 비교해 인덱스/시퀀셜 스캔을 고릅니다. (하드웨어·캐시 상황에 따라 비용 상수를 조정해야 하는 이유입니다.)

---

2. 옵티마이저가 필요한 인덱스를 감지하는 원리

2.1 선택도와 통계(Statistics)

• 선택도는 조건을 만족하는 행의 비율입니다. PostgreSQL은 컬럼별 MCV(최빈값), 히스토그램, NULL 비율 등을 pg_stats에 보관해 선택도를 계산합니다. 또한 다중 컬럼의 상관관계를 위해 확장 통계(의존성/다중 MCV/ndistinct) 를 생성할 수 있습니다. 
• MySQL 8.x는 히스토그램을 만들어 비인덱스 조건이나 비균등 분포의 선택도 추정 정확도를 높입니다(버킷 통계). 이는 인덱스가 없더라도 잘못된 카디널리티 추정으로 인한 나쁜 계획을 줄입니다. 
• 물리적 정렬 상관(correlation): 테이블의 물리적 배치와 컬럼 값 순서가 유사하면(±1에 근접) 랜덤 접근이 줄어 인덱스 스캔 비용 추정이 낮아집니다

---

2.2 비용모형과 접근경로 선택

• PostgreSQL 비용 계산은 “순차/랜덤 페이지 + 인덱스 튜플 처리 + 연산자 비용”의 합으로 모델링됩니다. 인덱스 사용 여부는 이 비용과 선택도, 정렬/조인 비용을 합쳐 비교합니다.
• MySQL도 유사하게 각 접근 방식(range/ref/ALL 등)의 비용을 산출해 최저 비용 계획을 선택하며, 필요 시 Optimizer Trace로 근거를 확인할 수 있습니다(이론 관점: 추정치 기반의 계획 공간 탐색).

---

2.3 여러 인덱스의 결합

• 쿼리 조건이 여러 컬럼에 흩어져 있고 단일 복합 인덱스가 없을 때, PostgreSQL은 비트맵 인덱스 스캔으로 인덱스 결과를 AND/OR 결합합니다.
• MySQL은 비슷한 개념의 Index Merge를 사용합니다(단일 테이블 내 결합). 이 메커니즘은 “단일 복합 인덱스가 더 낫다” 를 반증하진 않지만, 대체 기제로 작동합니다.

---

3. 인덱스가 필요한 SQL을 식별하는 기준

3.1 SARGability(색인 친화성)

• SARGable이란 “인덱스로 탐색 가능한 형태”를 뜻합니다.
• 컬럼에 함수를 감싸거나(예: LOWER(col)), 선두 와일드카드(%abc)를 쓰면 보통 색인 탐색성이 떨어집니다.
• 이론적으로는 표현식 인덱스나 함수 기반 인덱스(IMMUTABLE/결정적 함수)로 색인 친화성을 회복할 수 있습니다.

---

3.2 정렬·그룹과 인덱스의 순서 보존

• B-tree만이 인덱스 자체의 정렬 순서를 제공합니다. 따라서 ORDER BY/GROUP BY를 인덱스의 정렬 순서로 해결하면 별도 정렬 비용을 피합니다(정렬 회피). 이때 다중 컬럼의 열 순서·ASC/DESC와 콜레이션/operator class가 중요합니다.

---

3.3 조인과 인덱스

• 중첩 루프 조인(NLJ) 에서 내측(Inner) 테이블의 조인 키 인덱스는 탐색 비용을 급감시킵니다. 큰 양쪽 테이블의 동등 조인은 해시/머지 조인이 유리할 수 있지만, 정렬이 이미 되어 있거나(머지) 소수 매칭 키를 빠르게 찾을 수 있으면(NLJ+인덱스) 인덱스의 이득이 큽니다.

---

3.4 커버링(Index-only)과 가시성

• 커버링 인덱스는 필요한 컬럼이 전부 인덱스에 있어 테이블(힙) 접근을 생략합니다.
• PostgreSQL에서는 Visibility Map(페이지 단위 가시 비트)의 상태에 따라 힙 방문이 다시 필요할 수 있다는 점이 이론적 제약입니다.

---

4. 최적 인덱스를 설계하는 원칙

4.1 다중 컬럼(B-tree)에서의 열 순서

• 일반 법칙은 동등(=) 조건을 앞, 범위(>, BETWEEN, 접두 LIKE) 를 뒤에 둡니다. 이유는 B-tree 탐색이 선두부터 연속 일치하는 접두 조건에서 가장 강력하게 작동하기 때문입니다. MySQL은 이를 Leftmost Prefix 규칙으로 명시합니다.
• PostgreSQL도 다중 컬럼 인덱스의 순서가 선택도·정렬 회피 가능성에 직접적 영향을 줍니다.

---

4.2 복합 vs 단일+병합

• 단일 복합 인덱스는 하나의 정렬·탐색 경로에서 조건과 정렬을 동시에 만족시켜 정렬/정합 추가 비용을 없앨 수 있습니다. 반면 복수 단일 인덱스는 비트맵/Index-Merge로 결합할 수 있으나, 보통 I/O 집약적입니다(AND/OR 결합, 페이지 재방문).

---

4.3 정렬/패턴과 연산자 클래스

• 텍스트 접두 패턴(LIKE 'abc%')은 로케일 의존 비교에서 인덱스 사용이 막힐 수 있습니다.
• PostgreSQL은 text_pattern_ops 등 전용 operator class로 “문자단위 비교”를 강제해 패턴 매칭의 색인 가능성을 높입니다. (일반 비교 <, >와는 별도의 클래스 인덱스를 추가로 두어야 합니다.)

---

4.4 데이터 타입·워크로드에 맞는 인덱스 계열

B-tree

• 용도
  
  • 동등(=) 및 범위(>, <, BETWEEN) 검색
  • 정렬(ORDER BY)과 고유 제약(UNIQUE) 지원
• 내부 구조
  
  • 균형 이진트리(Balanced tree) 구조
  • 삽입·삭제 후 자동 균형 유지
  • 노드 단위로 키와 포인터 관리
• 성능 특성
  
  • 조회: O(log n)
  • 삽입/삭제: O(log n)
  • 단점: 배열/JSONB/텍스트 전체 검색에는 부적합
• 사용 사례
  
  • OLTP 대부분의 테이블 기본 인덱스
  • 외래 키, 고유 제약 지원
• 주의점
  
  • NULL 비교는 별도 처리 필요
  • 대량 텍스트 검색에는 GIN/GiST 권장

---

GIN (Generalized Inverted Index)

• 용도
  
  • 배열, JSONB, 전문 검색 등 “값들의 집합” 검색
• 내부 구조
  
  • 역색인(Inverted index) 방식
  • 항목별 posting list 저장
  • 삽입/삭제 시 posting list 재색인 필요
• 성능 특성
  
  • 검색: 매우 빠름 (특히 포함/부분 일치)
  • 삽입/삭제/업데이트: 상대적으로 비용 높음
  • 단일 값 조회: B-tree보다 느림
• 사용 사례
  
  • jsonb @> 연산
  • 배열 내 특정 값 검색
  • tsvector 기반 전문검색
• 주의점
  
  • 업데이트 비용 최적화를 위해 fastupdate 옵션 사용 가능
  • 단일 값 조회에는 비효율

---

GiST (Generalized Search Tree)

• 용도
  
  • 근사/거리/범위 기반 검색
  • 공간 데이터(PostGIS), 유사도, 트리 구조
• 내부 구조
  
  • 범용 트리 프레임워크
  • 노드에 키 요약 및 포인터 저장
  • 사용자 정의 연산자 사용 가능
• 성능 특성
  
  • 근사 검색(distance < x) 빠름
  • 동적 삽입/삭제 유리
  • 단순 동등 검색 비효율
• 사용 사례
  
  • 근접 검색, 공간/좌표 데이터
  • 범위 쿼리, 유사도 검색
• 주의점
  
  • B-tree처럼 범용 동등 검색용으로는 부적합
  • 인덱스 설계 시 연산자 클래스(operator class) 선택 필요

---

BRIN (Block Range Index)

• 용도
  
  • 초대용량, 물리적 순서와 값이 상관된 데이터
  • 시계열, 로그, 이벤트 데이터
• 내부 구조
  
  • 블록 범위(min/max 등) 요약
  • 블록 단위 메타정보만 저장 → 극소 메모리 사용
  • 정밀 검색 전 필터링 역할
• 성능 특성
  
  • 조회: 블록 단위 필터링으로 I/O 대폭 감소
  • 삽입/삭제: 매우 빠름
  • 단점: 정밀도 낮음, 무작위 분포에서는 비효율
• 사용 사례
  
  • 시계열 로그, 트랜잭션 기록
  • 데이터 웨어하우스에서 보조 색인
• 주의점
  
  • 보조 색인으로 사용
  • 무작위 값 분포 테이블에서는 성능 저하

 

인덱스	주요 용도	내부 구조	조회 성능	삽입/삭제 성능	적합 워크로드	주의점
B-tree	동등/범위/정렬	균형 이진트리	빠름 O(log n)	빠름 O(log n)	OLTP, 기본 인덱스	배열/JSONB/텍스트 검색 비효율
GIN	집합/문서 검색	역색인	매우 빠름	느림	배열, JSONB, 전문검색	단일 값 조회 비효율, 업데이트 비용 높음
GiST	근사/거리/범위	일반화 트리	빠름 (근사 검색)	동적 데이터 유리	공간 데이터, 유사도 검색	단순 동등 검색 비효율
BRIN	블록 범위 요약	블록 단위 요약	매우 빠름 (필터링)	매우 빠름	시계열, 로그, 초대용량 테이블	무작위 값 분포 비효율, 정밀도 낮음

---

4.5 부분/표현식/함수 기반 인덱스의 전제

• 부분(Partial)·표현식 인덱스는 “조건의 부분집합” 또는 “함수 결과”를 색인해 선택도를 극대화합니다. 이때 함수의 결정성(IMMUTABLE) 이 요구됩니다(인덱스의 일관성 보장 목적).
• MySQL 8.0의 functional key parts는 유사 목적을 수행합니다.

---

4.6 쓰기 비용과 유지관리 - 페이지 분할과 채움률

• B-tree는 리프가 꽉 차면 페이지 분할(page split) 이 발생하고 상위로 분할 전파가 일어나며, 이는 쓰기·공간 비용을 늘립니다. Fillfactor를 낮추면 초기 생애주기에서 분할 빈도를 완화할 수 있습니다. (정적 테이블은 높은 fillfactor가 공간 효율적입니다.)

---

5. 설계 체크리스트

1. 선택도/통계 가설
   • MCV·히스토그램·상관도(단일/확장 통계)를 통해 조건의 카디널리티가 낮은가? (낮을수록 인덱스 이득↑)
2. SARGability
   • 컬럼에 함수가 씌워져 있지 않은가? 필요하면 표현식/함수 인덱스(결정적) 로 변환 가능한가?
3. 다중 컬럼 순서
   • 동등 → 범위 → 정렬/그룹 순서로 키를 배열했는가? (MySQL은 Leftmost Prefix, PG도 순서 민감)
4. 정렬 회피
   • B-tree의 정렬 보존 특성을 활용해 ORDER BY/GROUP BY 비용을 제거할 수 있는가?
5. 조인 전략 적합성
   • 중첩 루프의 내측에 인덱스가 있는가? 큰 테이블 동등 조인은 해시/머지 전략과 비용 비교가 필요한가?
6. 대체 메커니즘
   • 단일 복합 인덱스가 없다면 비트맵/Index-Merge로 커버 가능한가(비용 비교)?
7. 데이터 타입별 특화 인덱스
   • 문서형/집합 데이터는 GIN/GiST, 시계열·대용량은 BRIN이 이론적으로 더 적합한가?
8. 유지관리 비용
   • 쓰기 폭주·페이지 분할·공간 팽창을 fillfactor/리빌드 전략으로 관리 가능한가?

---

6. DBMS별 특징

• PostgreSQL
  • 인덱스만으로 정렬을 제공하는 것은 B-tree뿐.
  • 비트맵 스캔으로 여러 인덱스 결합이 가능.
  • Index-Only는 Visibility Map 조건에 좌우.
  • 멀티컬럼 순서는 플랜·정렬에 민감.
• MySQL(InnoDB)
  • Leftmost Prefix 규칙이 강력.
  • 복수 인덱스 결합은 Index Merge.
  • 비용모형은 server_cost/engine_cost로 조정 가능.
  • 히스토그램으로 선택도 추정 보정.

---

인덱스는 테이블 위에 존재하기 때문에 구조적으로는 테이블에 종속되지만, 그 가치는 쿼리의 액세스 패턴에 의해 결정됩니다.
그래서 누군가 저에게 “인덱스란 무엇인가요?”라고 묻는다면, “쿼리 액세스 패턴 최적화 기법”이라고 답합니다.

 

오늘은 여기까지~