💡 이 글의 내용은 MySQL 8.0 이상 + InnoDB 스토리지 엔진 환경을 기준으로 작성되었습니다.
DB에서 인덱스란, 쓰기 성능과 저장 공간을 희생하는 대신 DB의 읽기 속도를 향상시키는 데이터 구조이다.
SELECT * FROM player WHERE name = 'Minsoo';
데이터가 100만건 있는 player
테이블에서 name='Minsoo'
인 를 찾는 쿼리를 실행한다 해보자.
만약, name
에 인덱스가 걸려있지 않을 경우 100만건의 데이터를 전부 찾아보는 테이블 풀 스캔을 하게 되고, 이때 시간 복잡도는 O(N)
이 된다.
하지만, name
에 B-Tree 기반 인덱스가 걸려있을 경우 시간 복잡도는 O(logN)
이 된다.
→ 인덱스는 조건을 만족하는 튜플들을 빠르게 조회, 정렬(order by), 그룹핑(group by)하기 위해 사용한다.
B-Tree는 DB에서 가장 일반적으로 사용되는 인덱스 알고리즘이다.
B-Tree는 트리 구조의 최상위에 하나의 루트 노드, 가장 하위에 있는 리프 노드, 루트 노드도 리프 노드도 아닌 중간 노드인 브랜치 노드로 구성된다.
위 그림을 기반으로 B-Tree 기반 인덱스를 이용하여 name='Fabrizio'
인 레코드를 찾는 과정을 설명하겠다.
해당 테이블에는 100만 건의 데이터가 있다고 가정한다.
우선 디스크에 들어있는 데이터 레코드들은 정렬이 되어있지 않지만, 인덱스의 키들은 정렬이 되어있다.
루트 노드부터 탐색을 시작하면 'Aamer'<'Fabrizio'<'Jaana'
이므로 브랜치 노드의 페이지 2로 가서 탐색을 진행한다.
페이지 2에서는 'Ebbe'<'Fabrizio'<'Gad'
이므로 리프 노드의 페이지 5로 가서 탐색을 진행한다.
리프 노드에는 인덱스 키에 해당하는 레코드의 주소가 있고, 디스크에서 데이터를 읽어와서 결과를 가져온다.
테이블에 레코드를 추가하는 작업의 비용이 1이라면, 인덱스에 키를 추가하는 비용은 대략 1.5이다.
InnoDB에선 필요한 경우 인덱스 키 추가 작업을 지연시킬 수 있다.
하지만 PK나 유니크 인덱스의 경우는 중복 체크가 필요하므로 지연 처리가 불가능하다.
인덱스 키 변경은 키 값에 따라 저장될 위치가 결정되므로 삭제한 뒤 새로운 값을 추가하는 형태로 처리한다.
→ 인덱스 설계가 매우 중요하다.
인덱스 키 값의 크기
키 값이 커지면 가질 수 있는 자식 노드의 수가 줄어들기 때문에 디스크 I/O가 늘어나고, 속도가 느려진다.
또한 인덱스 키 값의 크기가 커지면 전체 인덱스 크기도 커져서 메모리에 캐시할 수 있는 레코드가 줄어든다.
→ 인덱스 키의 크기가 크면 성능이 저하될 수 있다.
카디널리티
카디널리티는 데이터의 중복도를 말하며, 높을 수록 중복된 값이 적다.
인덱스는 카디널리티가 높을수록 검색 대상이 줄어들기 때문에 더 빠르게 처리된다.
→ 카디널리티가 높을 수록 읽어오는 데이터가 줄어들며 인덱스의 효율이 상승한다.
읽어야 하는 레코드의 건수
인덱스를 통해 레코드를 읽는 것은 바로 테이블의 레코드를 읽는 것 보다 비용이 높다. (약 4~5배)
만약, 인덱스를 통해 읽어야 할 레코드의 건수가 전체 테이블 레코드의 20~25%를 넘어서면 인덱스를 이용하지 않고 테이블 풀 스캔 후 필요한 레코드만 걸러내는 것이 더 효율적이다.
→ 읽어야 하는 레코드의 건수가 많을 수록 인덱스 사용이 비효율적이다.
인덱스 레인지 스캔
인덱스의 접근 방법 중 가장 대표적이고, 뒤에 나오는 다른 방식보다 빠르다.
과정은 아래와 같다.
인덱스 풀 스캔
인덱스를 사용하지만 인덱스의 처음부터 끝까지 모두 읽는 방식이다.
인덱스 크기가 테이블의 크기보다 작으므로 인덱스만으로 조건을 처리할 수 있을 때 테이블 전체를 읽는 것 보다 인덱스를 읽는 것이 더 효율적이고, 그럴 때 인덱스 풀 스캔 방식이 사용된다.
루스 인덱스 스캔
인덱스 레인지 스캔과 비슷하지만, 중간에 필요치 않은 인덱스 키 값은 무시하고 넘어가는 형태로 처리한다.
일반적으로 GROUP BY
or 집합 함수 중 MIN()
, MAX()
함수에 대해 최적화를 하는 경우에 사용한다.
인덱스 스킵 스캔
인덱스 스킵 스캔이 없다면 new_idx(A,B)
가 있을 때 아래 쿼리는 인덱스를 효율적으로 사용할 수 없다.
SELECT * FROM employees WHERE B >= '2000-11-05';
하지만, 인덱스 스킵 스캔은 아래와 같은 방식으로 처리하여 인덱스를 활용할 수 있다.
// A 컬럼이 'type1', 'type2' 두 종류의 값만 가지고 있음
SELECT * FROM employees WHERE A = 'type1' AND B >= '2000-11-05';
SELECT * FROM employees WHERE A = 'type2' AND B >= '2000-11-05';
위와 같은 처리 방식 때문에 인덱스 스킵 스캔을 사용하기 위해선 아래와 같은 조건이 필요하다.
WHERE
조건절에 조건이 없는 인덱스의 선행 컬럼(위에선 A 컬럼)의 유니크한 값의 개수가 적어야한다.테이블에 쓰기연산을 실행할 때 마다 인덱스도 변경되므로 인덱스를 적용하게 되면 쓰기 성능이 저하될 수 있다.
또한, 포인터와 인덱스의 키를 저장하기 때문에 추가적인 저장 공간을 차지한다.
또한, 아래의 경우는 인덱스를 생성하는 것 보다 테이블 풀 스캔이 더 좋을 수 있다.
그러므로 무작정 인덱스를 만들기 보다는 상황을 고려하여 신중히 만들어야 한다.
인덱스 역순 스캔은 아래의 이유들 때문에 정순 스캔에 비해 28.9% 정도 시간이 더 걸린다.
→ 자주 사용되는 정렬 순서로 인덱스를 생성하는 것이 효율적이다.
복합 인덱스란 여러 컬럼을 포함하는 인덱스를 말한다.
복합 인덱스는 선행 컬럼을 기준으로 정렬하고, 같은 값 끼리는 뒤에 있는 컬럼을 기준으로 정렬한다.
선행 컬럼의 카디널리티가 낮으면 더 많은 데이터를 확인해야 하므로 비효율적이다.
SELECT id FROM hotel WHERE region_id=3 AND category_id=2
위 쿼리를 아래 두 가지 인덱스를 사용하여 실행했을 때를 비교해보자.
category_region_idx(category_id, region_id)
category_id | region_id | PK |
---|---|---|
1 | 1 | 3 |
1 | 2 | 2 |
2 | 1 | 5 |
2 | 3 | 1 |
2 | 4 | 4 |
region_category_idx(region_id, category_id)
region_id | category_id | PK |
---|---|---|
1 | 1 | 3 |
1 | 2 | 5 |
2 | 1 | 2 |
3 | 2 | 1 |
4 | 2 | 4 |
category_region_idx
를 사용하는 경우는 category_id=2
를 만족하는 3개의 레코드 중 region_id=3
인 레코드를 찾아야 한다.
하지만, region_category_idx
는 region_id=3를 만족하는 1개의 레코드 중 category_id=2
인 레코드를 찾으면 되므로 탐색 횟수가 줄어든다.
선행 컬럼이 없는 조건의 경우에는 인덱스를 사용하기 어렵다.
복합 인덱스는 선행 컬럼을 기준으로 정렬되어 있어서 선행 컬럼이 없으면 효율적인 인덱스 사용이 어렵다.
그러므로 자주 사용하는 컬럼을 선행컬럼으로 하는 것이 좋다.
클러스터링은 테이블의 레코드를 클러스터링 인덱스가 비슷한 것들 끼리 물리적으로 묶어 저장하는 것을 말한다.
InnoDB에서는 PK를 생성할 때 자동으로 PK를 기반으로 클러스터링 인덱스를 생성한다.
만약 PK가 없다면 아래와 같은 로직으로 클러스터링 인덱스를 생성할 컬럼을 선택한다.
NOT NULL
옵션의 유니크 인덱스 중 첫 번째 인덱스를 클러스터링 키로 선택한다.
자동으로 유니크한 값을 가지도록 증가되는 컬럼을 내부적으로 추가한 후 클러스터링 키로 선택한다.
→ 위와 같이 생성된 경우는 명시적으로 나타나지 않으며 사용자가 SQL문에 사용할 수 없다.
장점
단점
테이블의 모든 세컨더리 인덱스가 클러스터링 키를 갖기 때문에 클러스터링 키 값의 크기가 클 경우 전체적인 인덱스의 크기가 커진다.
세컨더리 인덱스를 통해 검색할 때 클러스터링 인덱스로 한번 더 검색해야 하므로 성능이 느리다.
InnoDB 스토리지 엔진에서는 클러스터링 인덱스만이 물리적인 주소를 가지고, 세컨더리 인덱스는 모두 클러스터링 인덱스 키 값을 가지고 있어서 이를 이용하여 데이터 레코드를 찾는다.
그러므로 세컨더리 인덱스로 데이터를 찾기 위해서는 위와 같이 두 번의 B-Tree 탐색이 필요하다.
INSERT
할 때 PK에 의해 저장 위치가 결정되므로 처리 성능이 느리다.
PK를 변경할 때 레코드를 DELETE
하고 INSERT
하는 작업이 필요하기 때문에 처리 성능이 느리다.
커버링 인덱스란, 실제 테이블 접근 없이 인덱스에 있는 데이터만으로 쿼리를 처리할 수 있는 경우를 말한다.
이 경우 실제 테이블 접근 없이 인덱스 테이블 만으로 쿼리를 처리하므로 쿼리의 성능이 향상된다.
// category_region_idx(category_id, region_id)
SELECT id, name FROM hotel WHERE category_id=1 AND region_id=1;
위 쿼리와 같이 조건에 사용되는 컬럼과 조회하는 컬럼이 모두 인덱스에 포함되어 있으면 커버링 인덱스가 된다.
id | table | key | Extra |
---|---|---|---|
1 | hotel | category_region_idx | Using index |
이 경우, 위와 같이 EXPLAIN
의 Extra 컬럼에 Using index
라는 메시지가 나온다.
참고로 세컨더리 인덱스인 category_region_idx
에는 클러스터링 인덱스인 id
도 포함된다.
유니크 인덱스는 같은 값이 2개 이상 저장될 수 없는 인덱스를 말한다.
→ 유일성을 꼭 보장해야 하는 컬럼에는 유니크 인덱스를 생성하고, 그렇지 않다면 일반 인덱스 생성을 고려하자.
해시 테이블을 사용하여 구현한 인덱스를 말한다.
O(1)
이다.Index(a,b)
면 a
에 대한 조회에는 사용할 수 없고, 모든 컬럼에 대한 조회에만 사용 가능하다.