데이터베이스 인덱스
"An index is a database structure that you can use to speed up the retrieval of rows."
— 데이터베이스 성능 모델링 교과서에 나오는 정석적인 인덱스 정의.
느려터진 쿼리를 구원하는 신의 한 수처럼 보이지만, 잘못 설계하는 순간 전체 쓰기 성능을 시궁창으로 처박아버리는 초고위험 양날의 검. 검색이 0.1초 느리다고 테이블의 모든 컬럼에 인덱스를 발라버리는 주니어 개발자를 볼 때 DBA는 조용히 이성을 잃는다
1. 개요
데이터베이스 인덱스는 데이터베이스 테이블에 대한 검색 속도를 높여주는 물리적인 자료구조다. 책으로 비유하자면 책의 맨 뒷장에 있는 '색인(찾아보기)'과 완벽히 같은 역할을 한다. 수천 페이지의 두꺼운 백과사전에서 특정 단어를 찾을 때 처음부터 끝까지 다 넘겨보는 바보짓(Full Scan) 대신, 맨 뒤의 색인을 보고 몇 페이지로 바로 갈지 건너뛰는(Index Scan) 원리다.
물리적으로 테이블과 별도로 생성된 인덱스 파일은 정렬된 상태를 유지하며 데이터가 어디에 저장되어 있는지 알려주는 포인터를 가지고 있다. 이를 통해 디스크의 무작위 읽기(Random I/O) 횟수를 획기적으로 줄여, 수천만 행이 쌓인 대용량 테이블에서도 밀리초 단위의 경이로운 검색 응답 시간을 선사한다. 단, 공짜는 없다. 인덱스를 유지하기 위해 추가적인 저장 공간이 필요하며, 데이터의 추가/수정/삭제 시마다 인덱스를 새로 정렬하는 오버헤드가 발생한다.(...)
2. B-Tree와 B+Tree: 인덱스를 떠받치는 중추
2.1. 인덱스 자료구조의 절대 표준, B-Tree 계열
데이터베이스 인덱스의 핵심은 정렬과 균형이다. 이를 위해 대다수의 관계형 데이터베이스(RDBMS)는 B-Tree (Balanced Tree) 또는 이의 변형인 B+Tree 자료구조를 기반으로 인덱스를 구현한다.
- B-Tree (균형 트리): 이진 트리와 달리 하나의 노드가 여러 개의 자식을 가질 수 있는 다원 트리다. 최악의 상황에서도 탐색 시간이 $O([log](./log.md) N)$을 보장하기 때문에 편향 트리처럼 한쪽으로 길게 뻗어나가 성능이 파멸하는 일이 없다.
- B+Tree: 현대 RDBMS가 가장 사랑하는 구조다. 오직 리프 노드(Leaf Node)에만 실제 데이터 포인터를 저장하고, 리프 노드들끼리는 양방향 링크드 리스트(Double Linked List)로 한 줄로 연결해 두었다. 이 덕분에 범위 검색(Range Scan)을 할 때 트리를 위아래로 다시 타고 올라갈 필요 없이 리프 노드만 옆으로 쭉 따라가면 되므로 성능이 폭발적으로 상승한다.1
해시 테이블(Hash Table) 역시 단 한 건을 찾는 속도는 $O(1)$로 기가 막히게 빠르지만, 정렬이 안 되기 때문에 크다/작다 같은 범위 검색이나 LIKE 조건 검색에서 아무 쓸모가 없어 메인 인덱스로 채택되지 못했다.
3. 복합 인덱스(Composite Index)와 우측의 법칙
3.1. 컬럼 순서가 다르면 타지 않는다
두 개 이상의 컬럼을 묶어서 하나의 인덱스로 만드는 것을 복합 인덱스 (Composite Index) 또는 다중 컬럼 인덱스라고 부른다. 복합 인덱스는 첫 번째 컬럼을 기준으로 먼저 정렬한 뒤, 첫 번째 컬럼의 값이 같을 때만 두 번째 컬럼으로 정렬을 수행하는 방식으로 동작한다.
여기서 주니어 개발자들이 가장 많이 범하는 실수가 '좌측 기준(Left-most Prefix) 법칙'을 무시하는 것이다. 예를 들어 (성별, 나이) 순서로 복합 인덱스를 만들어 뒀는데, 쿼리 조건문에 WHERE 나이 = 20만 덜렁 적어두면 데이터베이스는 이 인덱스를 전혀 활용하지 못하고 결국 테이블 풀 스캔을 때린다. 첫 번째 컬럼인 '성별'이 조건문에 생략되었기 때문에 정렬 구조를 써먹을 수 없기 때문이다.(...)
따라서 복합 인덱스를 설계할 때는 무조건 검색 조건에 필수적으로 많이 쓰이고, 값의 고유 분포가 좁은(카디널리티가 높은) 컬럼을 왼쪽에 배치해야 피눈물을 흘리지 않는다.2
4. Full Scan vs Index Scan의 냉정한 현실
4.1. 인덱스는 무조건 좋은가?
결론부터 말하자면 아니다. 인덱스를 통한 스캔은 기본적으로 무작위 읽기(Random I/O)를 유발한다. 반면 테이블 전체를 긁어오는 풀 스캔(Full Scan)은 디스크 헤더를 순차적으로 이동하며 읽는 순차 읽기(Sequential I/O)를 사용한다. 디스크 물리 구조상 순차 읽기가 무작위 읽기보다 훨씬 빠르다.
만약 조회하려는 데이터가 테이블 전체 데이터의 대략 10% ~ 25%를 넘어선다면, 옵티마이저(Optimizer)는 머리를 굴린 뒤 '인덱스 하나하나 무작위로 읽어오는 것보다 그냥 테이블 전체를 한 번에 순차적으로 긁는 게 더 싸게 먹힌다'라고 판단하여 일부러 풀 스캔을 때려버린다. 인덱스를 만들어 놨는데 왜 안 타냐며 징징대지 말자. 데이터베이스는 생각보다 훨씬 똑똑하다.
5. 관련 밈 및 드립
5.1. Explain을 보았으나 ALL이었다
SQL 쿼리가 느려져 원인을 찾기 위해 쿼리문 앞에 EXPLAIN을 붙여 실행 계획을 조회했을 때, select_type에 'ALL' (Full Table Scan)이 새빨갛게 찍히는 순간 개발자는 말문이 막힌다. 로컬 테스트 환경(데이터 10건)에서는 0.001초 만에 돌던 쿼리가 실운영 환경(데이터 1000만 건)에서 서비스 장애를 일으킨 주범을 마주한 개발자는, 그날 밤샘을 확정하며 조용히 DB에 사죄의 기도를 올린다.(...)
6. 여담
- 카디널리티(Cardinality)의 배신: 인덱스를 태우기에 가장 좋은 컬럼은 '이메일'이나 '주민등록번호'처럼 값의 중복도가 지극히 낮은(카디널리티가 높은) 컬럼이다. 반대로 '성별(남/여)'처럼 중복도가 극도로 높은 컬럼에 단독 인덱스를 걸면, 인덱스 타는 게 오히려 더 느려지는 참사가 발생한다.
- 함수 기반 인덱스 (FBI):
WHERE UPPER(name) = 'KIM'처럼 쿼리 조건에서 컬럼 값을 가공해 버리면 기존 인덱스는 무용지물이 된다. 굳이 이렇게 쓰려면 '함수 기반 인덱스(Function-Based Index)'라는 별난 인덱스를 걸거나 조건문 좌변을 가공하지 않도록 쿼리를 고쳐야 한다. - 인덱스도 늙고 병든다: 테이블에 수많은 INSERT, UPDATE, DELETE가 반복되면 인덱스 노드가 쪼개지고 텅 빈 공간이 생기면서 '인덱스 파편화(Fragmentation)'가 일어난다. 이때는 주기적으로
REBUILD를 쳐서 인덱스를 꾹꾹 눌러 담아 재정렬해 줘야 제 성능을 유지한다.