[Database] 복합 인덱스에서 컬럼 순서는 어떻게 결정해야 할까

팀 프로젝트 festabook에서 학습한 내용을 정리한 글입니다.
시스(CS 스터디)에서 발표한 내용을 정리한 글입니다.

 

💭 들어가며

본 글은 시스(CS 스터디)에서 발표한 내용을 정리한 자료로, 발표용 흐름에 맞추어 순차적으로 구성되어 있다. 개념에 대한 보다 정확한 이해가 필요하다면, 시스 유튜브에 업로드된 영상 자료를 함께 참고 바란다.

글 중간에 ❓로 표시된 부분은 흐름상 자연스럽게 떠오른 의문을 의미하며, 하단 또는 확장하기 파트에서 다룬다.

 
 

✅ 문제 상황

festabook에서는 성능 개선을 위해 복합 인덱스를 적용한 튜닝 사례가 있다. 이 과정에서 단순히 복합 인덱스가 필요하다는 판단을 넘어서, 컬럼의 순서가 실제 실행 계획과 성능에 어떤 영향을 미치는지에 대한 의문이 생겼다.
이에 따라, 복합 인덱스에서 컬럼 순서가 왜 중요한지, 그리고 어떤 기준으로 순서를 결정해야 하는지를 정리해보고자 한다.
 
 

✅ 사전 지식

▶ 단일 인덱스(Single Index)

단일 인덱스는 위 사진처럼 하나의 컬럼을 기준으로 B+Tree 인덱스를 구성한 가장 기본적인 형태의 인덱스다. 인덱스 키는 해당 컬럼의 값으로만 구성된다.
 

▶ 복합 인덱스(Composite Index)

복합 인덱스는 위 사진처럼 여러 컬럼을 하나의 B+Tree 인덱스로 구성하여 사용하는 인덱스다. 단일 인덱스와 달리, 컬럼의 순서가 인덱스 활용 여부와 성능에 직접적인 영향을 준다.
 

▶ 카디널리티(Cardinality)

카디널리티는 인덱스 키 값 중 유니크한 값의 개수를 의미한다.

• 전체 row 수가 100이고, 그중 유니크한 값이 10개: 카디널리티 = 10
• 성별 컬럼(MALE/FEMALE): 카디널리티 = 2

카디널리티가 높을수록 검색 대상이 줄어들기 때문에 성능에 유리하다. ❓
 

▶ 선택도(Selectivity)

선택도는 조건을 적용했을 때 실제로 조회 대상이 되는 row 비율을 의미한다.

선택도 = 조건에 의해 반환되는 row 수 / 전체 row 수

• 선택도 0.001: 0.1%만 남김 = 매우 좋음
• 선택도 0.5: 절반 남김 = 인덱스 의미 거의 없음
• 선택도 0.9: 거의 안 줄임 = 풀 스캔이 나음

Real MySQL에서는 Cardinality와 Selectivity를 거의 동일한 개념으로 사용한다고 설명한다.

 
 

✅ 파고 들기

▶ 과연 그럴까

MySQL InnoDB는 B+Tree 인덱스를 사용한다.

1. 탐색 단계에서는 O(log N)으로 리프 노드까지 이동
2. 이후 리프 노드에서는 순차 스캔

🔽 가정

MySQL(InnoDB)에서 리프 노드 크기는 기본적으로 16KB이다. 하나의 row가 BIGINT 컬럼 3개로 구성되어 있다고 가정하면, 실제 데이터 외에도 메타데이터가(레코드 헤더, MVCC용 시스템 컬럼, NULL 비트맵, 오프셋 정보)가 함께 저장된다. ❓ 이를 모두 고려하면, 고정 길이 row 하나당 대략 20~30B의 오버헤드가 발생한다고 한다.

• 순수 데이터 크기: BIGINT 8B × 3 = 24B
• 메타데이터 오버헤드(가정): 약 26B
• 하나의 리프 노드에 저장 가능한 row 수: 116,384B / 50B ≈ 327 rows

🔽 성별 컬럼에 인덱스를 건 경우

• 과정
  • 성별을 ENUM 컬럼이라고 가정하면, InnoDB 내부에서는 해당 값을 정수 값(예: 0, 1)으로 변환하여 인덱스를 구성한다. ❓
  • 성별 컬럼의 카디널리티: 2
• 탐색 방식
  • 성별과 같이 카디널리티가 낮은 컬럼에 인덱스를 생성하면, 동일한 키 값을 가진 row들이 여러 개의 리프노드에 걸쳐 연속적으로 저장된다.
  • 예를 들어 여자(FEMALE)에 해당하는 row가 1,000개만 존재하더라도, 하나의 리프 노드에 약 300여 개의 row가 저장된다고 가정하면 3개 이상의 리프 노드가 필요하다.
• 결과
  • 만약 실제로 찾고자 하는 row가 여자 그룹 중 가장 오른쪽 리프 노드에 존재한다면, B+Tree 탐색 이후에도 해당 값이 포함된 첫 리프 노드부터 마지막 리프 노드까지 순차 탐색을 수행하게 된다.

🔽 나이 컬럼에 인덱스를 건 경우

• 과정
  • 이번에는 카디널리티가 상대적으로 높은 컬럼을 예로 들어보자. 나이 컬럼은 값의 범위가 넓고, 각 값이 비교적 고르게 분포되어 있다고 가정할 수 있다.
  • 나이 컬럼의 카디널리티: 약 100
• 탐색 방식
  • WHERE age = 23 조건이 주어지면, B+Tree 탐색을 통해 age = 23에 해당하는 정확한 키 범위로 바로 이동하고 해당 값들은 하나의 리프 노드 안에 밀집되어 저장된다. ❓
  • 즉, 리프 노드에 도달한 이후 추가적인 순차 탐색이 발생하지 않는다.
• 결과
  • 따라서 성별과 같이 카디널리티가 낮은 컬럼에 비해, 리프 노드 스캔 비용이 줄어들며 상대적으로 효율적인 인덱스 탐색이 가능하다.

 

▶ 단일 인덱스에서는 카디널리티가 높은 컬럼이 항상 유리할까

그렇다고 볼 수 있지 않을까… 카디널리티가 높고 선택도가 극단적으로 높은 극한의 케이스가 아니라면…
 

▶ 복합 인덱스에서도 카디널리티가 높은 컬럼이 항상 유리할까

아니다! 복합 인덱스는 쿼리 패턴 중심으로 설계해야 한다. 그 이유를 다음의 원칙과 예시를 통해 습득해보자.

1️⃣ = 조건 컬럼이 가장 먼저

• 여러 개라면 카디널리티가 높은 컬럼을 선행 컬럼으로 둔다.
• = 조건은 B+Tree에서 탐색 범위를 확정시킨다.

2️⃣ 범위 조건(<, >, BETWEEN)은 뒤로

• 범위 조건이 등장하는 순간 그 뒤 컬럼은 정렬 보장 불가하다. ❓
• 따라서 범위 조건은 항상 후행 컬럼으로 둔다.

3️⃣ ORDER BY / GROUP BY

• ORDER BY
  • 앞 조건들이 = 일 때만 인덱스 정렬 활용 가능
  • 범위 조건이 먼저 나오면 filesort 발생 가능성 큼
  • ORDER BY + LIMIT 조합에서 특히 중요
• GROUP BY
  • GROUP BY는 동일한 값을 가진 row들을 그룹 단위로 집계
  • 범위 조건이 인덱스 앞에 오면 이후 컬럼의 정렬성이 깨져 GROUP BY 최적화가 어려워짐
  • GROUP BY 기준 컬럼은 범위 조건보다 앞이 유리한 경우가 많음

 

▶ 실전 예시

1️⃣ 예제

WHERE created_at BETWEEN ? AND ?
AND user_id = ?

🔽 정답

(user_id, created_at)

• user_id는 동등 조건이므로 선행 컬럼으로 배치
• created_at은 범위 조건이므로 후행 컬럼으로 배치

2️⃣ 예제

SELECT *
FROM post
WHERE category_id = ?
AND status = 'PUBLISHED'
ORDER BY created_at DESC
LIMIT 20;

🔽 정답

(category_id, status, created_at)

• 두 컬럼 모두 동등 조건이므로 인덱스 활용 가능
  • 그중 카디널리티가 더 높은 category_id를 선행 컬럼으로 배치
  • 카디널리티가 낮은 status는 그 다음 컬럼으로 배치
• ORDER BY created_at DESC를 처리하기 위해 created_at을 마지막 컬럼으로 배치

3️⃣ 예제

SELECT *
FROM orders
WHERE user_id = ?
AND created_at >= ?
ORDER BY price DESC;

🔽 정답

(user_id, created_at)

• user_id는 동등 조건이므로 선행 컬럼으로 배치
• created_at은 범위 조건이므로 후행 컬럼으로 배치
• ORDER BY price는 인덱스로 처리할 수 없으므로 filesort를 감수

4️⃣ 예제

SELECT user_id, COUNT(*)
FROM orders
WHERE status = 'DONE'
AND created_at >= ?
GROUP BY user_id;

🔽 정답

(status, user_id, created_at)

• status는 동등 조건이므로 선행 컬럼으로 배치
• user_id로 그룹핑을 하기 때문에 후행 컬럼으로 배치
• created_at은 범위 조건이므로 마지막 컬럼으로 배치

 
 

✅ 확장하기

▶ ENUM에 인덱스를 걸면 정수로 변환되는가

• ENUM 값을 인덱스를 걸게 되면 정수 인덱스 값으로 저장된다.
• 잘못된 값은 0으로 저장, 이후 정의된 순서대로 1, 2, 3 ~ 순차적으로 정수 인덱스 번호를 갖는다.

 

▶ 하나의 row에 20~30B의 메타데이터에는 실제로 무엇이 붙을까

🔽 행 포맷 종류

• 실제로 MySQL InnoDB는 4가지 행 포맷을 지원한다.
  • REDUNDANT
  • COMPACT
  • DYNAMIC
  • COMPRESSED

기본 행 포맷은 DYNAMIC이며 이를 기준으로 내부 구조를 정리한다.

🔽 DYNAMIC 기준

1. Record Header: 5 bytes
   • 다음 레코드 포인터
   • 삭제 여부
   • 레코드 타입
   • 힙 번호
2. MVCC 시스템 컬럼: 13 bytes
   • transaction ID: 6 bytes
     • 마지막으로 이 row를 변경한 트랜잭션 ID
   • roll pointer: 7 bytes
     • undo log 위치를 가리키는 포인터
3. NULL Bitmap: ceil(N/8) bytes
   • NULL 허용 컬럼이 하나라도 있으면 생성
4. 가변 길이 컬럼 길이 목록: 1~2 bytes × 컬럼 수
   • VARCHAR, VARBINARY, TEXT, BLOB 같은 가변 길이 컬럼마다 붙는 메타데이터
5. (선택) Hidden ROW_ID: 6 bytes
   • PRIMARY KEY가 없을 때 InnoDB가 내부적으로 클러스터드 인덱스를 만들기 위해 자동 추가
6. (선택) Off-page column pointer: 20 bytes × 컬럼 수
   • VARCHAR, TEXT, BLOB, JSON 등 길이가 길면 처음부터 off-page 저장

 

▶ 인덱스 쓰기 중 인터널 노드가 꽉 차서 분할(page split)될 때 과정과 분할 기준

🔽 페이지 병합(Page Merge)

• DELETE 또는 UPDATE로 인해 레코드 크기가 줄어들면 인덱스 페이지의 page-full 비율이 감소한다.
• 이 비율이 MERGE_THRESHOLD(기본값 50%) 미만으로 떨어지면, InnoDB는 해당 페이지를 인접한 페이지와 병합하려고 시도한다.
• 병합의 목적은 너무 비어 있는 페이지를 제거하여 공간 활용도를 높이는 것이다.

🔽 페이지 분할(Page Split)

• 페이지 분할은 page-full 비율을 기준으로 직접 트리거되지 않는다.
• 병합 여부와 관계없이, INSERT 시점에 인덱스 페이지에 더 이상 레코드를 저장할 공간이 없으면 InnoDB는 새 페이지를 할당하고 페이지 분할을 수행한다.
• 이 과정에서 기존 페이지의 레코드 일부가 새 페이지로 이동되며, 부모(인터널) 노드에 새로운 경계 엔트리가 추가된다.
• 부모 노드 역시 공간이 부족한 경우, 이 분할 과정은 상위 노드로 전파될 수 있다.
• 페이지 분할 비율은 MySQL 공식 문서에 명시되어 있지 않다.

 
 

📍 참고 자료

• Real MySQL 8.0
• MySQL 공식 문서 - 13.3.5 The ENUM Type
• MySQL 공식 문서 - 17.10 InnoDB Row Formats
• MySQL 공식 문서 - 17.8.11 Configuring the Merge Threshold for Index Pages