데이터베이스 인덱스

데이터베이스 인덱스는 테이블을 처음부터 끝까지 읽지 않고도 원하는 행을 찾아 줍니다. 책 뒤의 찾아보기처럼 값과 그 값이 있는 위치를 따로 적어 둡니다. 대신 행을 넣거나 고칠 때마다 이 찾아보기도 함께 고쳐야 합니다.

상세

이 절은 인덱스가 무엇을 담고 어떻게 행을 찾아 주는지를 봅니다. 예는 회원 테이블 하나와 이메일 열에 건 인덱스 하나로 듭니다.

뒤로 가면서 인덱스가 답하는 질문과 못 하는 질문을 가릅니다. 그다음 쓰기에 붙는 비용과 걸 때와 안 걸 때를 봅니다.

인덱스가 없을 때

인덱스가 없는 테이블에서 조건에 맞는 행을 찾으려면 데이터베이스는 모든 행을 읽습니다. 행마다 조건을 견주고 맞는 것만 남깁니다. 테이블을 처음부터 끝까지 읽는 이 방식이 테이블 풀 스캔입니다.

풀 스캔은 행이 늘수록 그만큼 오래 걸립니다. 행이 열 배로 늘면 읽는 양도 열 배가 됩니다. 찾는 행이 한 줄뿐이어도 마찬가지입니다.

데이터베이스는 디스크에서 행을 한 줄씩 읽지 않습니다. 정해진 크기의 덩어리 단위로 읽습니다. 이 덩어리를 디스크 페이지, 줄여서 페이지라고 부릅니다. 페이지 한 장에는 행이 여럿 들어 있어서 찾는 비용은 몇 장을 읽었느냐로 잽니다.

인덱스가 담는 것

인덱스는 테이블과 따로 만들어 두는 목록입니다. 인덱스를 건 열의 값을 꺼내 정렬해 담습니다. 이렇게 담긴 값을 인덱스의 키라고 부릅니다.

키마다 그 행이 테이블 어디에 있는지도 함께 적습니다. 행의 위치를 가리키는 이 짧은 값이 행 식별자입니다. 몇 번 페이지의 몇 번째 행인지를 담는 식입니다.

키와 행 식별자를 한 쌍으로 묶은 것이 인덱스 항목입니다. 아래 그림은 이메일 인덱스의 항목 넷이 테이블의 행을 가리키는 모습입니다. 이메일은 앞부분만 적었습니다.

flowchart TD
    subgraph IDX["이메일 인덱스 · 키 순서로 정렬"]
        I1["choi"]
        I2["kim"]
        I3["lee"]
        I4["park"]
    end
    subgraph P7["회원 테이블 · 7번 페이지"]
        R1["kim"]
        R2["park"]
    end
    subgraph P9["회원 테이블 · 9번 페이지"]
        R3["lee"]
        R4["choi"]
    end
    I1 --> R4
    I2 --> R1
    I3 --> R3
    I4 --> R2

인덱스 쪽은 키가 알파벳 순서로 서 있습니다. 테이블 쪽은 행이 들어온 순서대로 흩어져 있습니다. 화살표 하나가 행 식별자 하나입니다. 인덱스는 순서를 맡습니다. 행의 내용은 테이블에 남겨 둡니다.

찾는 길

키를 정렬해 두면 찾을 때 전부 볼 필요가 없습니다. 종이 사전에서 낱말을 찾을 때 가운데를 펴 보고 앞뒤로 범위를 좁히는 것과 같습니다. 정렬된 목록을 반씩 잘라 가며 찾는 이 방법이 이진 탐색입니다.

데이터베이스 인덱스는 대개 이 생각을 B-tree 라는 자료구조로 구현합니다. B-tree 는 트리 모양입니다. 트리는 맨 위 칸 하나에서 아래로 칸이 갈라져 내려가는 구조입니다. 이 칸 하나가 노드입니다.

B-tree 는 정렬된 키를 여러 노드에 나눠 담습니다. 노드 하나는 페이지 한 장에 둡니다. 그래서 노드 하나에 키가 여럿 들어갑니다. 이진 탐색처럼 둘로만 갈라지지 않고 한 노드에서 여러 갈래로 갈라집니다.

맨 위 노드가 뿌리 노드, 맨 아래 노드가 잎 노드입니다. 그 사이의 노드는 가지 노드라고 부릅니다. 잎 노드에는 인덱스 항목이 들어 있습니다.

뿌리와 가지 노드에는 키 여러 개가 길잡이로 들어 있습니다. 찾을 값을 이 키와 견주어 어느 아래 노드로 내려갈지 고릅니다.

아래 그림은 lee 를 찾는 길을 굵은 선으로 그린 것입니다. 길이 잘 보이도록 노드마다 키를 한두 개만 적었습니다. 실제 노드에는 키가 훨씬 많이 들어갑니다. 키는 앞 그림처럼 이메일 앞부분만 적었습니다.

flowchart TD
    R["뿌리 노드 · kim"]
    R --> B1["가지 노드 · choi"]
    R --> B2["가지 노드 · park"]
    B1 --> L1["잎 노드 · ahn · baek"]
    B1 --> L2["잎 노드 · choi · jung"]
    B2 --> L3["잎 노드 · kim · lee"]
    B2 --> L4["잎 노드 · park · yoon"]
    L3 --> T["회원 테이블 · 9번 페이지"]
    linkStyle 1,4,6 stroke-width:3px

lee 는 뿌리의 kim 보다 뒤라서 오른쪽 가지로 갑니다. 가지의 park 보다 앞이라서 왼쪽 잎으로 갑니다. 잎에서 행 식별자를 얻은 뒤 테이블 페이지 한 장을 읽습니다. 노드 셋과 테이블 페이지 하나, 모두 네 장을 읽고 끝납니다.

복잡도

데이터가 늘 때 자료구조가 얼마나 느려지는지는 빅오 표기법으로 적습니다. 아래에서 n 은 테이블의 행 수입니다. O(n) 은 행 수에 비례해 일이 늘어난다는 뜻입니다. 행이 열 배면 일도 열 배입니다.

O(log n) 은 행 수가 곱절로 불어나도 일은 조금씩만 는다는 뜻입니다. B-tree 에서 이 일은 내려가는 층 수입니다. 노드 하나에 키를 백 개 담는다면 행이 백 배로 늘어도 층은 하나만 늘어납니다. 아래 표는 인덱스가 있을 때와 없을 때를 연산마다 견준 것입니다.

둘째 줄의 범위 조회는 「가입일이 이 날짜 이후」처럼 값이 어느 범위에 드는 행을 모두 찾는 일입니다. 시작점까지는 O(log n) 으로 내려갑니다. 거기서부터 키 순서대로 k 개를 이어 읽습니다. 그래서 O(log n + k) 입니다.

O(log n) 이 왜 그렇게 작은지는 층을 세어 보면 보입니다. 노드 하나에 키를 백 개 담는다고 해 봅니다. 한 층 내려갈 때마다 갈림길 수가 백 배가 됩니다.

flowchart TD
    subgraph F1["1층 · 뿌리"]
        A["노드 1개"]
    end
    subgraph F2["2층 · 가지"]
        B["노드 100개"]
    end
    subgraph F3["3층 · 잎"]
        C["노드 10,000개 · 키 1,000,000개"]
    end
    A -->|"갈림길 100개"| B
    B -->|"노드마다 갈림길 100개"| C

세 층이면 키 백만 개를 담습니다. 백만 행 가운데 하나를 찾는 데 노드 셋만 읽으면 됩니다. 풀 스캔이라면 백만 행이 든 페이지를 전부 읽습니다.

인덱스가 답하는 질문

키가 정렬돼 있다는 점이 인덱스로 할 수 있는 일을 정합니다. 순서를 따라가면 풀리는 질문에는 답합니다. 순서가 깨지는 질문에는 못 답합니다. 아래 표는 각 열에 인덱스가 하나씩 걸려 있다고 보고 조건마다 가른 것입니다.

마지막 두 줄은 인덱스를 걸었는데도 쿼리가 느릴 때 흔히 나오는 꼴입니다. 가운데 글자로 찾으면 앞글자가 제각각이라 정렬된 순서를 따라갈 수 없습니다. 열의 값을 소문자로 바꿔서 견주면 인덱스가 정렬해 둔 원래 값과 다른 값으로 찾는 셈이 됩니다. 두 경우 모두 데이터베이스는 결국 모든 행을 읽습니다.

여러 열에 거는 인덱스

인덱스는 열 하나에만 거는 것이 아닙니다. 여러 열을 묶어 인덱스 하나로 걸 수도 있습니다. 이것을 복합 인덱스라고 부릅니다.

복합 인덱스는 첫 열로 먼저 정렬합니다. 첫 열 값이 같은 것끼리는 둘째 열로 정렬합니다. 전화번호부가 성으로 먼저 늘어놓고 같은 성 안에서 이름으로 늘어놓는 것과 같습니다.

그래서 열을 묶은 순서가 중요합니다. 첫 열 없이 둘째 열만으로는 순서를 탈 수 없습니다. 전화번호부에서 이름만 알고 성을 모르면 처음부터 다 넘겨 봐야 합니다.

인덱스는 SQL(Structured Query Language, 구조화 질의 언어)의 CREATE INDEX 문으로 만듭니다. 아래는 팀과 나이를 묶은 인덱스를 만드는 문입니다. 조건마다 이 인덱스를 쓸 수 있는지는 줄 오른쪽에 적었습니다. 조건은 WHERE 절만 떼어 적었습니다.

CREATE INDEX idx_team_age
  ON members (team, age);

WHERE team = 3              -- 쓴다
WHERE team = 3 AND age = 30 -- 쓴다
WHERE age = 30              -- 못 쓴다

셋째 조건은 나이만 주었습니다. 첫 열인 팀이 빠져서 인덱스의 순서를 탈 수 없습니다. 나이로 자주 찾는다면 나이로 시작하는 인덱스가 따로 필요합니다.

쓰기에 붙는 비용

인덱스는 테이블 내용의 일부를 따로 들고 있습니다. 그래서 테이블이 바뀌면 인덱스도 같이 바뀌어야 합니다.

행을 하나 넣으면 인덱스마다 그 키가 들어갈 위치를 찾아 항목을 넣습니다. 행을 지우면 항목도 뺍니다. 인덱스를 건 열의 값을 고치면 옛 항목을 빼고 새 항목을 넣습니다.

인덱스를 다섯 개 걸어 둔 테이블은 행 하나를 넣을 때 인덱스 다섯 개를 더 고칩니다. 한 번의 쓰기가 여러 번의 쓰기로 불어나는 것이 쓰기 증폭입니다.

인덱스는 디스크 공간도 따로 차지합니다. 행마다 항목이 하나씩 있으니 테이블이 커지면 인덱스도 함께 커집니다.

인덱스가 있어도 풀 스캔을 고를 때

인덱스를 걸었다고 데이터베이스가 늘 그것을 쓰지는 않습니다. 이 절은 데이터베이스가 인덱스를 쓸지 말지를 어떻게 고르는지 봅니다.

쿼리를 어떤 방법으로 처리할지는 데이터베이스 안의 옵티마이저가 고릅니다. 같은 쿼리도 인덱스를 따라 찾을 수 있습니다. 테이블을 처음부터 읽을 수도 있습니다. 옵티마이저는 그중 빨라 보이는 쪽을 고릅니다.

옵티마이저가 고른 처리 방법이 실행 계획입니다. 실행 계획을 보면 쿼리가 인덱스를 썼는지 풀 스캔을 했는지 알 수 있습니다.

인덱스로 찾은 행은 테이블 여기저기에 흩어져 있습니다. 행마다 행 식별자를 따라 테이블 페이지를 따로 찾아가야 합니다. 찾을 행이 몇 줄뿐이면 이 방법이 훨씬 빠릅니다.

찾을 행이 테이블의 큰 몫이면 사정이 뒤집힙니다. 흩어진 페이지를 하나씩 찾아가느니 처음부터 이어서 다 읽는 편이 빠릅니다. 디스크는 이어진 곳을 읽을 때가 흩어진 곳을 읽을 때보다 빠르기 때문입니다.

조건이 전체 행 가운데 얼마만큼을 골라내는지를 선택도라고 부릅니다. 골라내는 행이 적을수록 인덱스가 유리합니다.

열이 가진 값의 가짓수는 카디널리티라고 부릅니다. 값이 두세 가지뿐인 열은 어느 값으로 찾아도 행이 많이 나옵니다. 이런 열에 인덱스를 걸어도 옵티마이저가 잘 고르지 않습니다.

걸 때와 안 걸 때

인덱스를 걸지는 열과 테이블을 보고 정합니다. 아래 표에 나오는 키 둘을 먼저 풉니다.

기본 키는 행 하나를 가려내는 열입니다. 기본 키에는 대개 데이터베이스가 인덱스를 저절로 만듭니다. 그래서 따로 걸 일이 거의 없습니다.

외래 키는 다른 테이블의 행을 가리키는 열입니다. 두 테이블을 이 열로 이어 읽는 일이 조인입니다.

ORM 에서 거는 인덱스

ORM(Object-Relational Mapping, 객체 관계 매핑)은 테이블을 코드의 클래스로 다루게 해 주는 도구입니다. 테이블 하나에 짝지어진 이 클래스를 모델이라고 합니다.

모델 안에서는 테이블의 열 하나를 필드 하나로 적습니다. ORM 을 쓰면 인덱스도 모델 정의에 적습니다.

마이그레이션은 테이블 구조를 바꾸는 작업을 파일로 남겨 차례로 적용하는 방식입니다. 모델에 인덱스를 적으면 마이그레이션이 그 정의를 읽어 CREATE INDEX 를 만들어 냅니다.

Django 에서는 필드에 db_index=True 를 주거나 모델의 Meta.indexes 에 인덱스를 적습니다. 외래 키 필드에는 Django 가 인덱스를 저절로 겁니다.

ORM 이 쿼리를 대신 짜 주므로 어떤 조건이 나가는지 코드에서 잘 안 보입니다. 쿼리가 느리면 ORM 이 만든 SQL 과 그 실행 계획을 함께 봅니다.

관련 항목

데이터베이스 인덱스를 이루는 구성 요소

인덱스 키 · 행 식별자 · 디스크 페이지 · 뿌리 노드 · 잎 노드

데이터베이스 인덱스를 구현하는 자료구조

B-tree · B+tree · 해시 인덱스 · LSM 트리 · 비트맵 인덱스 · 역색인 · GiST · GIN · BRIN

거는 방법에 따라 갈리는 인덱스 갈래

복합 인덱스 · 유니크 인덱스 · 커버링 인덱스 · 부분 인덱스 · 함수 기반 인덱스 · 클러스터형 인덱스 · 보조 인덱스

인덱스를 쓸지 고를 때 보는 지표와 도구

옵티마이저 · 실행 계획 · EXPLAIN · 선택도 · 카디널리티 · 통계 정보

인덱스가 바꾸는 데이터베이스 읽기 방식

테이블 풀 스캔 · 인덱스 스캔 · 인덱스 전용 스캔 · 범위 조회 · 조인 · 정렬

인덱스가 쓰기에 얹는 비용

쓰기 증폭 · WAL · 페이지 분할 · 인덱스 단편화

인덱스를 만드는 명령과 도구

CREATE INDEX · SQL · ORM · Django · 마이그레이션

인덱스와 맞물려 쓰이는 키 제약

기본 키 · 외래 키 · 유니크 제약

인덱스와 얽혀 터지는 성능 문제

슬로 쿼리 · N+1 · 인덱스는 많을수록 좋다

데이터베이스 인덱스가 딛고 선 상위 개념

자료구조 · 데이터베이스 · 관계형 데이터베이스 · 인덱스 · 이진 탐색 · 디스크