DB - 인덱스 스캔 방식과 클러스터링 인덱스
데이터베이스 스터디 3주차에서 학습하고 정리한 내용입니다.
1. B-Tree 인덱스의 스캔 방식
1) 인덱스 레인지 스캔(Index Range Scan)
인덱스 접근 방법 가운데 가장 대표적인 방식이다. 검색해야 할 인덱스 범위가 결정됐을 때 사용한다.
1
SELECT * FROM employees WHERE first_name BETWEEN 'Ebbe' AND 'Gad';
위의 그림은 다음과 같은 과정을 거친다.
- 루트 노드와 브랜치 노드를 거쳐 리프 노드의 범위 시작 지점으로 이동한다.
- 연결 리스트 형태로 리프 노드가 이어져 있어 순차 접근으로 범위 끝까지 스캔한다.
- 범위 끝으로 도착하면 지금까지 스캔한 레코드를 “하나씩” 조회한 후 반환하고 쿼리를 끝낸다.
1개를 읽든 여러 개를 읽든 범위가 결정되었다면 똑같은 과정을 거친다.
레코드 가져오기
실제 데이터를 가져오는 과정을 자세히 살펴보자.
ORDER BY로 정렬 방향을 따로 명시하지 않더라도 인덱스 범위의 처음부터 끝까지 스캔하므로 인덱스가 정렬된 순서로 레코드를 가져온다. 또한 스캔 과정에서 데이터 한 건 단위로 랜덤 I/O가 한 번씩 일어나므로 레코드 1건을 조회할 때 인덱스를 활용한 방식이 전체 테이블 스캔에서 1건 조회하는 과정보다 많은 비용이 드는 이유이다.
커버링 인덱스(Covering Index)
만약에 인덱스가 쿼리가 필요로 하는 데이터를 모두 포함하고 있다면 어떻게 될까? 아래와 같은 쿼리의 인덱스 레인지 스캔 과정을 살펴보자.
1
SELECT first_name FROM employees WHERE first_name BETWEEN 'Ebbe' AND 'Gad';
first_name의 값은 이미 first_name 인덱스가 가지고 있다. 이 경우 인덱스는 쿼리가 필요한 first_name 정보를 모두 가지고 있다. 따라서 이 쿼리를 실행할 때는 랜덤 I/O를 통해 실제 데이터를 가져오는 과정이 생략되어 기존보다 빠른 성능을 보인다.
2) 인덱스 풀 스캔(Index Full Scan)
인덱스의 처음부터 끝까지 읽는 방식이다. 예를 들어 (first_name, last_name) 인덱스가 존재하는데 다음과 같은 쿼리를 실행한다.
1
SELECT first_name, last_name FROM employees WHERE last_name BETWEEN 'Johnson' AND 'Smith';
이 인덱스는 다중 컬럼 인덱스이므로 first_name을 기준으로 먼저 정렬되고 이후 last_name으로 정렬된다. 따라서 first_name 없이 last_name 만으로는 인덱스에서 적절한 범위를 설정할 수 없으므로 인덱스 레인지 스캔을 활용할 수 없다.
이 경우, 인덱스를 효과적으로 사용할 수 없기 때문에 MySQL은 인덱스 풀 스캔을 고려할 수 있다. 인덱스 풀 스캔은 인덱스의 처음부터 끝까지 모든 엔트리를 읽는 방식으로, 테이블의 모든 데이터를 스캔하는 테이블 풀 스캔과 유사하다. 그러나 인덱스의 크기는 일반적으로 테이블의 크기보다 작기 때문에, 인덱스 풀 스캔을 사용하는 것이 테이블 풀 스캔보다 더 효율적일 수 있다.
또한, 현재 쿼리는 실제 테이블을 조회할 필요가 없는 커버링 인덱스를 사용하기 때문에, MySQL은 인덱스만을 스캔하여 필요한 데이터를 모두 얻을 수 있다. 하지만 실제 테이블의 데이터를 조회하는 경우 조회할 때마다 랜덤 I/O가 발생하므로 이 경우 인덱스 풀 스캔이 테이블 풀 스캔보다 오히려 성능이 떨어지므로 이 때는 인덱스 풀 스캔을 활용하지 않는다.
랜덤 I/O가 발생하지 않는다면 인덱스 풀 스캔은 테이블 풀 스캔 방식보다는 효율적이지만 인덱스 레인지 스캔보다는 느리다.
3) 루스 인덱스 스캔(Loose Index Scan)/인덱스 스킵 스캔(Index Skip Scan)
인덱스 레인지 스캔과 비슷하게 작동하지만 두 방식 모두 중간에 필요하지 않은 인덱스 키 값은 무시하고 다음으로 넘어가는 방식이다. DBMS마다 실행 과정이 조금씩 다르므로 MySQL을 기준으로 설명한다.
3-1) 루스 인덱스 스캔
일반적으로 GROUP BY 또는 집합 함수 중 MIN(), MAX() 최적화 시 활용한다. dept_emp 테이블에서 (dept_no, emp_no) 인덱스가 있다고 가정하자.
1
2
3
4
SELECT dept_no, MIN(emp_no)
FROM dept_emp
WHERE dep_no BETWEEN 'd002' AND 'd004'
GROUP BY dept_no;
위 그림과 같이 dept_no를 기준으로 먼저 정렬한 후 emp_no를 기준으로 정렬되어 있음을 확인할 수 있다. 이 경우 emp_no도 정렬되어 있으므로 첫 번째로 조회한 emp_no가 최소값임이 보장된다. 다음 emp_no는 더이상 조회할 필요가 없다. 이 경우 옵티마이저는 조회할 필요가 없는 레코드는 무시하고 다음 레코드로 이동한다.
3-2) 인덱스 스킵 스캔
인덱스 스킵 스캔은 인덱스 선두 컬럼이 조건에 포함되지 않을 때도 인덱스를 사용할 수 있도록 하는 최적화 기법이다. employees 테이블에 (gender, birth_date) 인덱스가 있다고 가정하자.
1
SELECT gender, birth_date FROM employees WHERE birth_date >= '1965-02-01';
첫 번째 인덱스인 gender를 포함하지 않고 전체 테이블을 조회하기 때문에 인덱스 스킵 스캔이 없다면 이 쿼리는 인덱스 풀 스캔으로 처리된다. MySQL 8.0에서는 gender와 같이 기수성이 작은 경우 인덱스 스킵 스캔을 활성화하면 인덱스 스킵 스캔으로 이를 효율적으로 처리할 수 있다.
MySQL 옵티마이저는 gender 컬럼에서 유니크한 값을 모두 조회한 후 조건을 추가한다.
1
2
SELECT gender, birth_date FROM employees WHERE gender='M' AND birth_date >= '1965-02-01';
SELECT gender, birth_date FROM employees WHERE gender='F' AND birth_date >= '1965-02-01';
이 경우 두 번의 인덱스 범위 스캔으로 데이터를 조회할 수 있으므로 전체 인덱스 테이블을 조회하지 않기 때문에 최적화를 할 수 있다. 하지만 gender와 같이 기수성이 적은 경우에만 활용할 수 있고 유니크한 값의 개수가 많다면 오히려 쿼리의 성능이 떨어지기 때문에 이를 잘 고려하여 최적화를 해야 한다. 또한 인덱스 테이블 내에서 모든 데이터를 조회할 수 없는 경우에도 MySQL 옵티마이저는 인덱스 스킵 스캔을 사용하지 않고 풀 테이블 스캔을 활용한다.
2. 다중 컬럼 인덱스
다중 컬럼 인덱스는 여러 컬럼을 하나의 인덱스로 저장하는 방법이다. 이 때 인덱스 내 컬럼의 순서는 아주 중요하다. employees 테이블 내에서 (dept_no, emp_no)로 저장했다면 리프 노드에서는 아래와 같이 저장된다. dept_no 순으로 먼저 정렬한 후 동일한 dept_no 내에서 emp_no를 정렬한다. 따라서 emp_no는 dept_no에 ‘의존’한다.
| dept_no | emp_no | 데이터 주소 |
|---|---|---|
| D001 | 10023 | |
| D001 | 10047 | |
| D002 | 10011 | |
| D002 | 10035 | |
| D003 | 10007 | |
| D003 | 10048 | |
| D003 | 10063 |
1
2
3
4
5
6
//1.
SELECT dept_no, emp_no FROM employees WHERE dept_no >= 'D002';
SELECT dept_no, emp_no FROM employees WHERE dept_no >= 'DOO3' AND emp_no >= 10040;
SELECT dept_no, emp_no FROM employees WHERE emp_no >= 10040;
- 3번째 레코드 ~ 4번째 레코드이다. dept_no를 기준으로 정렬되어 있으므로 인덱스 레인지 스캔을 활용할 수 있다.
- 6번째 레코드 ~ 7번째 레코드이다. dept_no와 emp_no를 기준으로 정렬되어 있고 AND 조건이므로 인덱스 레인지 스캔을 활용할 수 있다.
- 2, 6번째 레코드이다. emp_no는 dept_no에 의존하므로 emp_no 컬럼 만으로는 정렬되어 있지 않다. 따라서 인덱스 레인지 스캔을 활용할 수 없다.
위 예시처럼 활용하고자 하는 컬럼이 인덱스의 prefix일 때만 인덱스가 효과적으로 활용된다.
3. 클러스터링 인덱스
클러스터링 인덱스는 기본키 값이 비슷한 레코드끼리 묶어서 저장하는 구조이다. 비슷한 값들을 동시에 조회하는 경우가 많을 때 클러스터링 인덱스는 유용하게 사용할 수 있다. MySQL에서는 InnoDB만 클러스터링 인덱스를 지원한다.
기본키 값이 비슷한 레코드끼리 묶어서 저장하므로 기본키 값이 변경된다면 이 레코드의 물리적인 저장 위치는 변경된다. 따라서 클러스터링 인덱스가 적용된 테이블은 기본키 값에 대한 의존도가 상당히 크기 때문에 신중히 기본키를 결정해야 한다.
기본키 값을 기반으로 저장 위치가 결정되기 때문에 위와 같은 예시에서 100007번 기본키가 100002로 변경된다면 이 데이터의 위치도 페이지 2번으로 옮겨진다.
기본키가 없는 데이터
기본키가 없는 테이블은 다음과 같은 우선순위로 기본키를 대체할 컬럼을 선택한다.
- 기본키가 있으면 기본키를 클러스터링 키로 선택
- NOT NULL 옵션의 유니크 인덱스 중에서 첫 번째 인덱스를 클러스터링 키로 선택
- 자동으로 유니크한 값을 가지도록 증가되는 컬럼을 내부적으로 추가한 후 클러스터링 키로 선택
세컨더리 인덱스에 미치는 영향
MyISAM의 경우 세컨더리 인덱스의 리프 노드가 실제로 저장되어 있는 레코드의 주소를 가르킨다. 하지만 InnoDB의 경우 세컨더리 인덱스의 리프 노드가 기본키 값을 저장하고 있다.
클러스터링 인덱스를 사용하는 InnoDB에서 세컨더리 인덱스가 실제 레코드가 저장된 주소를 가지고 있다면 기본키 값이 변경될 때마다 데이터 레코드의 주소가 변경될 것이다. 이 경우 해당 테이블의 모든 인덱스에 저장된 주소값을 변경해야 한다. 이러한 문제점을 해결하기 위해 InnoDB의 모든 세컨더리 인덱스는 기본키 값을 저장하도록 구현되어 있다.
클러스터링 인덱스의 장점, 단점
장점
- 기본키로 검색할 때 처리 성능이 아주 빠르다.
- 모든 세컨더리 인덱스가 기본키를 가지고 있기 떄문에 인덱스만으로 처리될 수 있는 경우가 많다.
단점
- 모든 세컨더리 인덱스는 클러스터링 키를 가지기 때문에 클러스터링 키 값이 커지면 전체 인덱스 크기도 커진다.
- INSERT할 때 기본키에 의해 저장 위치가 결정되기 때문에 처리 성능이 느리다.
- 기본키를 변경할 때 저장 위치를 변경해야 하므로 많은 비용이 든다.
MyISAM 같은 경우 기본키의 순서와 저장 순서가 일치하지 않기 때문에 기본키로 특정 범위의 데이터를 조회할 때 랜덤I/O가 발생할 수 있다. 하지만 InnoDB는 기본키의 순서와 저장 순서가 일치하므로 기본키로 특정 범위의 데이터를 조회할 때 순차I/O를 이용하여 조회할 수 있다.
따라서 기본키를 활용한 조회가 빈번한 경우 클러스터링 인덱스가 유리한 면을 가진다.
클러스터링 인덱스 고려 사항
클러스터링 인덱스의 크기
모든 기본키는 세컨더리 인덱스의 레퍼런스로 포함이 된다. 따라서 기본키의 크기가 커진다면 모든 세컨더리 인덱스의 크기도 함께 커지게 되므로 기본 키는 신중하게 선택해야 한다.
기본키는 업무적인 컬럼으로 생성하기
업무적으로 연관되어 있는 컬럼을 기본키로 설정한다면 인접한 기본키를 조회할 가능성이 높아지므로 매우 빠르게 처리할 수 있게 된다. 하지만 AUTO_INCREMENT를 사용하게 된다면 업무적으로 연관되어 있는 것이 아닌 저장된 시간 순으로 기본키가 저장이 된다. 따라서 인접한 기본키를 조회할 가능성이 낮아지므로 클러스터링 인덱스의 이점을 활용하기 힘들다.
기본키는 반드시 명시할 것
기본키를 명시하지 않아도 InnoDB 스토리지 엔진은 내부적으로 AUTO_INCREMENT 컬럼을 추가한다. 문제는 이 경우 사용자가 이 컬럼을 조회할 수 없다. 기본키를 명시하지 않으면 용량은 똑같이 차지하고 사용자가 조회할 수 없는 상황이 되는 것이다. 따라서 기본키는 반드시 명시하는 것이 좋다.
조회보다 INSERT 위주인 경우 AUTO_INCREMENT 활용하기
여러 개의 컬럼이 복합으로 기본 키를 만드는 경우 기본키의 크기가 길어지게 된다. 세컨더리 인덱스를 만들지 않는다면 이대로 기본키를 사용해도 되지만 아니라면 AUTO_INCREMENT를 기본키로 하자. 그리고 로깅 테이블과 같이 조회보다 삽입이 빈번한 테이블들은 AUTO_INCREMENT 기본키를 설정하는 것이 성능 향상에 도움이 된다.
Reference
백은빈, 이성욱 편저, Real MySQL 8.0, 위키북스
모든 이미지 출처: 백은빈, 이성욱 편저, Real MySQL 8.0, 위키북스