Real MySQL 8.0 Ch.8 — B-Tree 인덱스

디스크 읽기 방식

데이터 저장 매체는 컴퓨터에서 가장 느린 부분이다. 데이터베이스 서버에서는 항상 디스크 장치가 병목이 되므로, 성능 튜닝은 디스크 I/O를 어떻게 줄이느냐가 관건이다.

HDD와 SSD

CPU나 메모리는 전자식 장치지만 HDD는 기계식 장치다. SSD는 원판 플래터 대신 플래시 메모리를 장착해, 원판을 기계적으로 회전시킬 필요 없이 빠르게 읽고 쓴다. 메모리보다는 느리지만 HDD보다는 훨씬 빠르다.

랜덤 I/O와 순차 I/O

랜덤 I/O는 플래터를 돌려 읽어야 할 데이터가 저장된 위치로 디스크 헤더를 이동시킨 다음 데이터를 읽는 것이다. 이 과정 자체는 순차 I/O도 같다. 차이는 헤더를 몇 번 움직이느냐에 있다.

순차 I/O: 3개의 페이지를 디스크에 기록하기 위해 시스템 콜을 1번 요청한다. 헤더를 1번 움직인다.
랜덤 I/O: 3개의 페이지를 디스크에 기록하기 위해 시스템 콜을 3번 요청한다. 헤더를 3번 움직인다.

디스크의 성능은 헤더의 위치 이동 없이 얼마나 많은 데이터를 한 번에 기록하느냐로 결정된다. 따라서 여러 번 읽기·쓰기를 요청하는 랜덤 I/O가 부하가 훨씬 크다.

데이터베이스의 작업 대부분은 작은 데이터를 빈번히 읽고 쓴다. 그래서 MySQL에는 그룹 커밋, 바이너리 로그 버퍼, InnoDB 로그 버퍼 같은 기능이 내장돼 있다.
I/O에는 파일 동기화가 반드시 필요하다. 순차 I/O라도 동기화가 빈번하면 랜덤 I/O처럼 비효율적으로 처리될 때가 많다. 데이터베이스 서버에 흔히 쓰이는 RAID 컨트롤러의 캐시 메모리는 이런 순차 I/O를 효율적으로 처리할 수 있게 변환해 준다.

쿼리 튜닝으로 랜덤 I/O를 순차 I/O로 바꿀 방법은 많지 않다. 일반적인 쿼리 튜닝의 목적은 꼭 필요한 데이터만 읽도록 해 랜덤 I/O 자체를 줄이는 것이다.

인덱스 레인지 스캔은 주로 랜덤 I/O를, 풀 테이블 스캔은 순차 I/O를 사용한다. 그래서 큰 테이블의 레코드 대부분을 읽는 작업에서는 인덱스를 쓰지 않고 풀 테이블 스캔을 하도록 유도할 때도 있다.

인덱스란

인덱스는 컬럼의 값과 해당 레코드가 저장된 주소를 Key-Value 쌍으로 만들어 둔 것이다. 책의 찾아보기에 비유하면, 찾아보기로 알아낸 페이지 번호가 레코드의 주소에 해당한다. 그리고 찾아보기처럼 컬럼 값을 미리 정렬해서 보관한다.

자료 구조에 비유하면 인덱스는 SortedList, 데이터 파일은 ArrayList다.

인덱스는 SortedList처럼 값을 항상 정렬된 상태로 유지한다.
데이터 파일은 ArrayList처럼 별도의 정렬 없이 저장한다.

SortedList는 저장할 때마다 정렬해야 하므로 저장이 느리지만, 이미 정렬돼 있어 원하는 값을 아주 빨리 찾는다. 인덱스도 마찬가지로 INSERT, UPDATE, DELETE를 느리게 만드는 대신 SELECT를 빠르게 한다.

결국 인덱스를 하나 더 추가할지는 저장 속도를 어디까지 희생할 수 있는지, 읽기 속도를 얼마나 더 빠르게 만들어야 하는지에 따라 결정해야 한다.

인덱스의 분류

역할로 나누면 다음과 같다.

프라이머리 키: 레코드를 대표하는 컬럼의 값으로 만들어진 인덱스. NULL과 중복을 허용하지 않는다.
세컨더리 인덱스: 프라이머리 키를 제외한 모든 인덱스.

알고리즘으로 나누면 다음과 같다.

B-Tree 인덱스: 가장 일반적으로 사용된다. 컬럼의 값을 변형하지 않고 원래의 값으로 인덱싱한다.
해시 인덱스: 컬럼의 값으로 해시값을 계산해 인덱싱한다. 검색이 매우 빠르지만, 값이 변형되므로 전방 일치처럼 값의 일부만 검색하거나 범위를 검색할 때는 쓸 수 없다. 주로 메모리 기반 데이터베이스에서 사용한다.

B-Tree 인덱스

B-Tree의 B는 Binary가 아니라 Balanced다. 컬럼의 원래 값을 변형하지 않고, 인덱스 구조체 안에서 항상 정렬된 상태로 유지한다.

구조

최상위에 루트 노드가 있고, 가장 하위에 리프 노드, 그 사이에 브랜치 노드가 있다.
인덱스와 실제 데이터는 따로 보관되며, 리프 노드는 실제 데이터 레코드를 찾아가기 위한 주솟값을 가진다.
인덱스의 키 값은 모두 정렬돼 있지만, 데이터 파일의 레코드는 임의의 순서로 저장된다. DELETE로 생긴 빈 공간을 재활용하므로 INSERT된 순서와도 다르다.
단, InnoDB 테이블은 레코드가 클러스터링되어 저장되므로 기본적으로 PK 순서로 정렬된다.

InnoDB의 세컨더리 인덱스

MyISAM의 세컨더리 인덱스는 레코드의 물리적인 주소를 가진다. 반면 InnoDB는 PK를 주소처럼 사용하므로 논리적인 주소를 가진다. InnoDB에서는 PK가 ROWID 역할을 하는 셈이다.

그래서 InnoDB에서 세컨더리 인덱스로 레코드를 읽을 때는 데이터 파일을 바로 찾아가지 못한다. 인덱스에 저장된 PK 값으로 PK 인덱스를 한 번 더 검색한 뒤, PK 인덱스의 리프 페이지에 저장된 레코드를 읽는다. 느릴 것 같지만 장단점이 모두 있는 구조이며, 클러스터링 인덱스 글에서 자세히 다룬다.

키 추가, 삭제, 변경

추가: 키 값으로 B-Tree 상의 적절한 위치를 찾아, 키 값과 레코드의 주소 정보를 리프 노드에 저장한다. 리프 노드가 꽉 차면 분리(split)해야 하고, 이 작업은 상위 브랜치 노드까지 범위가 넓어진다. B-Tree의 쓰기 비용이 큰 이유다.
삭제: 해당 리프 노드를 찾아 삭제 마크만 한다. 마킹된 공간은 방치하거나 재활용한다.
변경: 키 값만 바꿀 수는 없다. 기존 키 값을 삭제한 뒤 새로운 키 값을 추가하는 형태로 처리된다.

쓰기 비용은 대략 이렇게 계산해 볼 수 있다. 테이블에 레코드를 추가하는 비용을 1이라고 하면 인덱스에 키를 추가하는 비용은 1.5 정도다. 인덱스가 3개인 테이블이라면 1.5 * 3 + 1 = 5.5가 된다. 이 비용의 대부분은 디스크에서 인덱스 페이지를 읽고 쓰는 데 걸리는 시간이다.

검색

루트 노드에서 브랜치 노드를 거쳐 리프 노드까지 이동하며 비교 작업을 수행한다.
100% 일치하거나 값의 앞부분만 일치하는 경우에 사용할 수 있다. 부등호 비교에도 쓸 수 있지만, 키 값의 뒷부분만으로 검색하는 용도로는 쓸 수 없다.
키 값에 함수나 연산을 적용해 변형한 경우에도 인덱스를 사용할 수 없다.

검색은 잠금과도 관련이 있다. InnoDB의 레코드 잠금과 넥스트 키 락은 검색에 사용한 인덱스를 잠근 뒤 테이블의 레코드를 잠그는 방식이다. 따라서 UPDATE나 DELETE를 실행할 때 적절한 인덱스가 없으면 불필요하게 많은 레코드를 잠근다.

성능에 영향을 미치는 요소

인덱스 키 값의 크기

디스크에 데이터를 저장하는 기본 단위이자 모든 읽기·쓰기의 최소 작업 단위가 페이지다. 버퍼 풀이 데이터를 버퍼링하는 단위이기도 하다. 인덱스도 페이지 단위로 관리되며, 루트·브랜치·리프 노드를 구분하는 기준이 바로 페이지다.

B-Tree는 자식 노드의 개수가 가변적인데, 그 개수는 인덱스 페이지 크기와 키 값의 크기로 결정된다.

키 값이 커지면 한 페이지에 담을 수 있는 키가 줄어든다. 레코드 500개를 읽는 SELECT가 인덱스 페이지 한 번으로 끝날 수도 있고, 두 번 이상 디스크를 읽어야 할 수도 있다.
인덱스 전체 크기도 커진다. 버퍼 풀은 제한적이므로 메모리에 캐시할 수 있는 레코드 수가 줄어 메모리 효율이 떨어진다.

B-Tree 깊이

키 값이 커질수록 한 페이지가 담는 키 개수가 줄고, 같은 레코드 건수라도 B-Tree의 깊이가 깊어져 디스크 읽기가 더 많이 필요하다. 다만 아무리 대용량 데이터베이스라도 깊이가 5단계 이상으로 깊어지는 경우는 흔치 않다.

선택도(기수성)

기수성(cardinality)은 모든 인덱스 키 값 가운데 유니크한 값의 수다. 전체 키 값이 100개이고 유니크한 값이 10개라면 기수성은 10이다. 중복된 값이 많을수록 기수성과 선택도가 낮아지고, 선택도가 높을수록 검색 대상이 줄어 빠르게 처리된다.

전체 레코드가 1만 건이고 country 컬럼에만 인덱스가 있는 테이블로 비교해 보자.

SELECT * FROM tb_test WHERE country = 'KOREA' AND city = 'SEOUL';

	country의 유니크한 값	인덱스로 읽는 건수	조건에 맞는 1건을 위해 불필요하게 읽은 건수
케이스 A	10개	평균 1,000건(10,000 / 10)	999건
케이스 B	1,000개	평균 10건(10,000 / 1,000)	9건

MySQL은 인덱스의 유니크한 값 개수를 통계 정보로 관리하므로 이 건수를 예측할 수 있다. city는 인덱스에 없으므로 그 기수성은 작업 범위에 영향을 주지 않는다. 최종 결과가 똑같이 1건이라면 케이스 A의 인덱스는 적합하지 않은 것이다.

읽어야 하는 레코드의 건수

인덱스를 통해 레코드를 읽는 것은 테이블에서 직접 읽는 것보다 비용이 크다. 레코드 1건 기준으로 4~5배 정도 더 든다.

그래서 인덱스로 읽어야 할 레코드가 전체의 20~25%를 넘으면, 인덱스를 쓰지 않고 테이블을 직접 읽어서 필터링하는 편이 효율적이다.

인덱스를 이용한 데이터 읽기

어떤 경우에 인덱스를 쓰게 유도할지, 쓰지 못하게 할지 판단하려면 MySQL이 인덱스로 레코드를 읽는 방식을 알아야 한다.

인덱스 레인지 스캔

가장 대표적인 접근 방식으로, 검색할 인덱스의 범위가 결정됐을 때 사용한다. 검색하려는 값의 수나 결과 레코드 건수와 관계없이 레인지 스캔이라고 부른다.

인덱스에서 조건을 만족하는 값이 저장된 위치를 찾는다(인덱스 탐색).
그 위치부터 필요한 만큼 리프 노드를 순서대로 읽는다(인덱스 스캔). 리프 노드의 끝에 도달하면 노드 간 링크를 따라 다음 리프 노드로 넘어간다.
읽어 들인 인덱스 키와 레코드 주소로 레코드가 저장된 페이지를 가져와 최종 레코드를 읽는다.

3번 과정에서 레코드마다 랜덤 I/O가 발생한다. 커버링 인덱스로 처리되는 쿼리는 디스크의 레코드를 읽지 않아도 되므로 이 랜덤 I/O가 없다.

인덱스 풀 스캔

인덱스를 처음부터 끝까지 모두 읽는 방식이다. 리프 노드의 제일 앞 또는 뒤로 이동한 후, 리프 노드를 연결하는 링크드 리스트를 따라 끝까지 스캔한다.

조건절에 사용된 컬럼이 인덱스의 첫 번째 컬럼이 아닐 때 사용된다. 예를 들어 인덱스가 (A, B, C)인데 WHERE 절에서 B나 C로만 검색하는 경우다.

레인지 스캔보다는 느리지만 테이블 풀 스캔보다는 효율적이다. 인덱스가 테이블보다 작고, 인덱스에 포함된 컬럼만으로 쿼리를 처리할 수 있으면 테이블의 레코드를 읽을 필요가 없기 때문이다.

루스 인덱스 스캔

인덱스를 듬성듬성 읽는 방식으로, 오라클의 인덱스 스킵 스캔과 비슷하게 동작한다. 레인지 스캔처럼 진행하되 중간에 필요하지 않은 키 값은 건너뛴다. GROUP BY나 MAX(), MIN() 함수를 최적화할 때 사용된다.

이와 대비해 레인지 스캔과 풀 스캔은 타이트 인덱스 스캔으로 분류한다.

인덱스 스킵 스캔

인덱스는 구성하는 컬럼의 순서가 매우 중요하다.

ALTER TABLE employees
  ADD INDEX ix_gender_birthdate (gender, birth_date);

-- 인덱스를 사용할 수 없는 쿼리
SELECT * FROM employees WHERE birth_date >= '1965-02-01';

-- 인덱스를 사용할 수 있는 쿼리
SELECT * FROM employees WHERE gender = 'M' AND birth_date >= '1965-02-01';

원래는 선행 컬럼인 gender 조건이 없는 첫 번째 쿼리가 이 인덱스를 사용할 수 없었다. MySQL 8.0부터는 옵티마이저가 gender 컬럼을 건너뛰고 birth_date만으로 인덱스를 검색하는 인덱스 스킵 스캔이 도입됐다. 루스 인덱스 스캔이 GROUP BY 처리에만 적용되는 것과 달리 WHERE 조건 검색에 쓰인다.

다만 조건이 있다.

WHERE 절에 조건이 없는 선행 컬럼의 유니크한 값 개수가 적어야 한다.
쿼리가 인덱스에 존재하는 컬럼만으로 처리 가능해야 한다(커버링 인덱스).

선행 컬럼의 유니크한 값이 많으면 스캔 시작 지점을 검색하는 작업이 그만큼 많이 필요해 오히려 느려진다. (emp_no, dept_no) 인덱스에서 dept_no만으로 검색한다면 사원 수만큼 레인지 스캔 시작 지점을 찾아야 한다.

다중 컬럼 인덱스

실제 서비스용 데이터베이스에서는 2개 이상의 컬럼을 포함하는 인덱스가 더 많이 사용된다.

두 번째 컬럼은 첫 번째 컬럼에 의존해서 정렬된다. 즉 두 번째 컬럼의 정렬은 첫 번째 컬럼이 같은 레코드 안에서만 의미가 있다.
따라서 인덱스 안에서 각 컬럼의 위치가 상당히 중요하다.

정렬과 스캔 방향

인덱스를 구성하는 각 컬럼의 정렬은 오름차순 또는 내림차순으로 설정할 수 있다. 인덱스를 어느 방향으로 읽을지는 쿼리에 따라 옵티마이저가 만드는 실행 계획에서 결정된다.

SELECT * FROM employees ORDER BY first_name DESC LIMIT 1;

이 쿼리는 인덱스를 처음부터 끝까지 오름차순으로 읽은 뒤 가장 큰 값을 가져오는 것이 아니다. 인덱스를 역순으로 접근해 첫 번째 레코드만 읽는다.

인덱스 자체는 정렬된 채로 고정돼 있지만, 최솟값부터 읽으면 오름차순으로, 최댓값부터 거꾸로 읽으면 내림차순으로 값을 가져올 수 있다. 즉 인덱스를 읽는 방향에 따라 정렬 효과를 얻는다.

내림차순 인덱스

오름차순과 내림차순이 혼합된 정렬은 내림차순 인덱스로만 해결할 수 있다.

CREATE INDEX ix_teamname_userscore ON employees (team_name ASC, user_score DESC);

용어를 정리하면 다음과 같다.

오름차순 인덱스: 작은 값의 키가 B-Tree의 왼쪽에 정렬된 인덱스
내림차순 인덱스: 큰 값의 키가 B-Tree의 왼쪽에 정렬된 인덱스
인덱스 정순 스캔: 리프 노드의 왼쪽 페이지부터 오른쪽으로 스캔
인덱스 역순 스캔: 리프 노드의 오른쪽 페이지부터 왼쪽으로 스캔

그렇다면 한 컬럼을 역순으로 정렬하는 요건만 있을 때, 오름차순 인덱스를 역순 스캔하는 것과 내림차순 인덱스를 정순 스캔하는 것은 차이가 없을까? 책의 테스트에서는 역순 정렬 쿼리가 정순 정렬 쿼리보다 28.9% 더 오래 걸렸다.

정순 스캔과 역순 스캔은 페이지 간의 양방향 링크를 앞으로 따라가느냐 뒤로 따라가느냐의 차이뿐인 것 같지만, 두 가지 이유로 역순이 느리다.

페이지 잠금이 인덱스 정순 스캔에 적합한 구조다.
페이지 내에서 인덱스 레코드가 단방향으로만 연결된 구조다.

많은 쿼리가 인덱스의 앞쪽만 또는 뒤쪽만 집중적으로 읽어 특정 페이지의 잠금이 병목이 될 것 같다면, 쿼리에서 자주 쓰는 정렬 순서대로 인덱스를 생성하는 것이 병목 완화에 도움이 된다.

가용성과 효율성

쿼리의 WHERE, GROUP BY, ORDER BY 절이 어떤 경우에 인덱스를 사용할 수 있고 어떤 방식으로 사용하는지 식별할 수 있어야 한다. 그래야 쿼리의 조건을 최적화하거나, 쿼리에 맞게 인덱스를 설계할 수 있다.

비교 조건의 종류와 효율성

동등 비교(=)인지 범위 조건(>, <)인지에 따라, 그리고 컬럼의 순서에 따라 인덱스의 활용 형태가 달라진다.

SELECT * FROM dept_emp WHERE dept_no = 'd002' AND emp_no >= 10144;

케이스 A: INDEX (dept_no, emp_no) dept_no = 'd002' AND emp_no >= 10144인 첫 레코드를 찾고, 이후에는 dept_no가 'd002'가 아닐 때까지 인덱스를 쭉 읽기만 하면 된다. 조건에 맞는 레코드가 5건이라면 꼭 필요한 5번의 비교만 수행한다.
케이스 B: INDEX (emp_no, dept_no) emp_no >= 10144인 첫 레코드를 찾은 뒤, 그 이후의 모든 레코드에 대해 dept_no가 'd002'인지 비교해야 한다.

케이스 A의 두 조건처럼 작업 범위를 결정하는 조건을 작업 범위 결정 조건이라 하고, 케이스 B의 dept_no 조건처럼 범위를 줄이지 못하고 거름종이 역할만 하는 조건을 **필터링 조건(체크 조건)**이라고 한다. 작업 범위 결정 조건이 많을수록 쿼리가 빨라진다.

인덱스의 가용성

B-Tree 인덱스는 왼쪽 값을 기준으로 오른쪽 값이 정렬돼 있다. 그래서 LIKE '%mer'처럼 왼쪽 부분이 고정되지 않은 조건은 인덱스 레인지 스캔을 사용할 수 없다. 다중 컬럼 인덱스에서 선행 컬럼의 조건이 없는 경우도 같은 이유로 사용할 수 없다.

참고

Real MySQL 8.0
MySQL Ascending index vs Descending index - kakao tech