[DB] MySQL 8.0 인덱스

MYSQL의 내부 동작과 그 원리에 대해 궁금해져, Real MySQL 8.0 책을 읽었는데 정리를 안하니 계속 내용이 휘발되어서 내 방식으로 정리해보고자 글을 쓴다. 

---

1. 디스크 읽기 방식

CPU나 메모리 같은 주요 장치는 대부분 전자식 장치이지만, 하드 디스크 드라이브는 기계식 장치다. 그래서 DB 서버에서는 항상 디스크 장치가 병목이 되어 어떻게 Disk I/O를 줄이느냐가 관건일 때가 많다. 

 

디스크에 데이터를 쓰고 읽는 데 걸리는 시간은 디스크 헤더를 움직여서 읽고 쓸 위치로 옮기는 단계에서 결정된다. 

디스크의 헤더를 움직이지 않고 한 번에 많은 데이터를 읽는 Sequential I/O에서는 SSD와 HDD의 성능은 비슷하다. 다만, Random I/O에서는 SSD가 훨씬 빠르다. DB I/O의 대다수가 Random I/O 통해 작은 데이터를 읽고 쓰는 작업이 대부분이기에 SSD가 DBMS용 스토리지에 최적이다. 

 

SSD(Solid State Drive)는 기존 HDD(하드 디스크 드라이브) 에서 데이터 저장용 플래터를 제거하고 그 대신 플래시 메모리를 장착하고 있다. 그래서 디스크 원판을 기계적으로 회전시킬 필요가 없어져 빨리 데이터를 읽고 쓸 수 있다. SSD의 초당 처리 횟수가 HDD보다 약 500배(100,000 vs 200)높다.

*메모리와 디스크는 약 1,000배(SSD)~10만배(HDD) 가량의 차이가 있다. 

 

2. 인덱스란? 

책의 목차나 색인으로 비유할 수 있다. 색인(인덱스)에 나오는 페이지 번호(레코드 주소)를 통해 책의 특정 부분(데이터 파일)에 빨리 접근할 수 있다. 하지만, 색인도 일정 페이지를 차지하는 것처럼 인덱스 테이블도 공간을 차지한다. 그리고 목차만 있는 것보다 색인까지 있을 때, 책의 내용이 늘어나면 목차와 색인을 업데이트하는 데에 많은 비용이 든다. 즉, 인덱스는 저장 성능을 희생하는 대신 읽기 속도를 높이는 기술이다. 그래서 인덱스 추가 유무는 저장 속도를 어디까지 희생할 수 있는지, 읽기 속도를 얼마나 더 빠르게 만드러야 하는지를 고려하고 결정하자. 

 

인덱스 종류는 다음과 같다. 

1) Primary Key (= Clustering Index)

: 해당 레코드를 대표하는 column의 값으로 만들어진 인덱스다. 이를 통해 테이블에서 해당 레코드를 식별한하기에 식별자라고도 한다. PK가 없는 경우, UNIQUE하고 NON NULL인 컬럼이 클러스터링 인덱스가 된다. 

*InnoDB 테이블에서 레코드는 클러스터되어 디스크에 저장되는데, 기본적으로 PK 순서로 (물리적)정렬되어 저장된다. 

 

2) Secondary Key (= Non-Clustering Index)

: Primary Key를 제외한 나머지 모든 인덱스는 Secondary Index로 물리적 정렬은 되지 않는다. 

 

3. B+ Tree 인덱스

MySQL에서 사용하는 인덱싱 알고리즘으로, 컬럼의 원래 값을 변형시키지 않고, 인덱스 구조체 내에서 항상 정렬된 상태로 유지된다. Secondary Index들은 모두 각자의 B+ Tree 인덱스 테이블이 있다. 하나의 루트 노드, 중간의 여러 브랜치 노드들과 가장 밑바닥에 여러 리프 노드들이 있다. 실제 데이터가 존재하는 노드는 leaf 노드로 인덱스 키와 PK로 이루어져있고, root노드와 branch 노드는 인덱스 키(인덱스 값)과 자식 노드 주소로 이루어져 있다. PK로 데이터 파일에서 해당 PK를 가진 레코드를 검색해 나머지 컬럼 값들을 확인할 수 있다. 즉, 세컨더리 인덱스 검색에서 데이터 레코드를 읽기 위해서는 반드시 프라이머리 키를 저장하고 있는 B+ Tree로 구성된 데이터 파일을 다시 한번 검색해야 한다. 

 

[왜 검색 작업에 비용이 적게 들까?]

검색 작업은 B Tree 루트 노드부터 시작해 브랜치 노드를 거쳐 최종 리프 노드까지 이동하면서 비교 작업을 수행(logm(N))한다. 수정과 삭제를 위해서 탐색 할 때에도 동일하다. 인덱스 트리에 키로 정렬되어 저장되기에 키의 전체나 앞부분을 비교조건으로 사용하여 탐색할 수 있다. 또한, 인덱스에 존재하는 값으로만 탐색이 가능하기에 연산 결과로 검색하는 작업은 B Tree의 장점을 이용할 수 없다. 

+) leaf 노드들은 linked list로 구현되어 범위 기반 조회에서 연속적인 데이터를 O(1)에 조회가 가능하다. 

 

[왜 쓰기 작업에 비용이 많이 들까?]

B Tree에 레코드를 저장할 때, 저장될 키 값을 이용해 B Tree상의 적절한 위치를 검색해야 한다. 위치가 결정되면, 레코드의 키 값과 PK 정보를 B Tree의 리프 노드에 저장한다. 리프 노드가 꽉 차면 리프 노드가 Split되고, 상위 브랜치 노드까지 처리 범위가 넓어진다. 이때 디스크로부터 인덱스 페이지를 읽고 쓰기(Random I/O)를 하는 작업에서 시간이 오래 걸린다. 

*책에서는 테이블에 레코드를 추가하는 작업 비용을 1이라 한다면, 인덱스에 키를 추가하는 작업 비용을 1.5 정도로 잡는다. 

*인덱스 키 추가 작업을 체인지 버퍼를 통해 지연시킬 수 있지만, PK나 UNIQUE 인덱스의 경우에는 중복 체크가 필요하기에 즉시 B Tree에 추가하거나 삭제한다. 

 

인덱스 키 삭제의 경우에는 해당 키 값이 저장된 B Tree의 리프 노드를 찾아서 삭제 마킹을 하면 된다. 이후, 해당 공간을 방치하거나 재사용할 수 있다. 인덱스 키 변경 시에는 제거한 후, 새로 추가해야 한다. 

 

4. 인덱스 검색과 변경 작업의 성능에 영향을 미치는 요소

1) 인덱스 값의 크기: 탐색 시간복잡도가 logm(N)라 했는데, 자식 수(m)이 늘어날수록 Tree의 depth가 낮아져 탐색 비용이 줄어든다. 이때, 자식 수에 영향을 미치는 것이 인덱스 페이지와 키 값의 크기다. 인덱스 페이지 크기는 일정한 상황에서 키 값이 작을수록 한 페이지에 여러개의 {인덱스 키와 자식노드 주소} 쌍을 담을 수 있어 자식 수를 키울 수 있다. Depth가 줄어 탐색해야 하는 페이지 수가 줄어들면 그만큼 Disk Random I/O 수가 줄어들게 된다. 전체적으로 인덱스 크기가 작아지면, 버퍼 풀에 더 많은 데이터를 캐시할 수 있는 장점도 있다. 

*페이지(블록): 디스크의 데이터 저장 기본 단위로, 모든 작업의 최소단위다. 

*InnoDB는 인덱스 페이지 크기가 기본 16KB다. 

*Depth를 줄이기 위해 'B' Tree 말 그대로 Balance를 맞추는 것이 중요하다. 

 

2) Cardinality(선택도, 기수성): 모든 인덱스 키 값 가운데 UNIQUE한 값의 수를 나타내는 카디널리티가 클수록 중복된 값이 적다는 의미이기에 검색 대상이 줄어 그만큼 빠르게 처리된다. 

 

5. B Tree 인덱스를 통한 데이터 읽기

1) 인덱스 레인지 스캔 : 검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식이다.

1. 인덱스 탐색: 인덱스에서 조건을 만족하는 값이 저장된 시작 지점을 찾는다. 

2. 인덱스 스캔: 시작 지점부터 필요한 만큼 인덱스를 차례대로 쭉 읽는다. 다음 리프 노드로는 링크를 이용해 이동한다. 

3. 조건에 일치하는 건들을 PK값을 이용해 레코드가 저장된 페이지를 가져오고(Random I/O), 최종 레코드를 읽어온다.

*인덱스에 포함된 칼럼만으로 쿼리를 처리할 수 있는 경우, 데이터 파일에 접근하지 않는다. 

인덱스 레인지 스캔은 데이터를 읽기 위해 주로 랜덤 I/O를 사용하며, 풀 데이블 스캔(인덱스 사용X)은 순차 I/O를 사용한다. 논클러스터링 인덱스는 클러스터링 인덱스와 달리 물리적 정렬이 되어 있지 않기 때문이다. 그래서 큰 데이블의 레코드 대부분을 읽는 작업에서는 인덱스를 사용하지 않고 풀 테이블 스캔을 사용하도록 유도할 때도 있다. 

 

2) 인덱스 풀 스캔 : 인덱스의 처음부터 끝까지 모두 읽는 방식이다. 쿼리의 조건절에 사용된 칼럼이 인덱스의 첫 번째 칼럼이 아닌 경우 즉, 쿼리가 인덱스에 명시된 칼럼만으로 조건을 처리할 수 없는 경우 사용된다.

인덱스 리프 노드의 제일 앞 또는 제일 뒤로 이동한 뒤, 링크드 리스트를 따라 처음부터 끝까지 스캔한다. 해당 방식은 인덱스 레인지 스캔보다는 느리지만, 테이블 풀 스캔보다는 효율적이다. 

 

3) 루스 인덱스 스캔 : 이전 두 타이트 인덱스 스캔과 상반되는 방식으로, 듬성듬성하게 인덱스를 읽는 방식이다. 즉, 중간에 필요치 않은 인덱스 키 값을 무시하고 다음으로 넘어간다. 

 

4) 인덱스 스킵 스캔 :  MySQL 8.0에 도입된 기능으로, 뒷 우선순위인 인덱스 컬럼만으로도 인덱스 검색이 가능하게 해주는 최적화 기능이다. 인덱스는 이를 구성하는 칼럼의 우선순위대로 정렬되어있는 것이 특징이기에, 인덱스를 구성하는 칼럼의 순서가 매우 중요하다. 인덱스가 (a, b, c) 순서로 구성되어 있고, 쿼리가 b, c를 조건절로 가지고 있다면, 원래 해당 복합 인덱스를 사용하지 못했다. 

 

 

5) 다중(복합) 칼럼 인덱스 : 두 개 이상의 칼럼으로 구성된 인덱스이다. B Tree 인덱스는 왼쪽 값에 의존해서 오른쪽 값이 정렬된다.즉, 두 번째 칼럼은 첫 번째 칼럼에 의존해서 정렬되어 있어 인덱스 내에서 각 칼럼의 순서가 상당히 중요하다. 그래서 왼쪽 컬럼의 값을 모르면 인덱스 레인지 스캔을 사용할 수 없다. 

 

 

6. 클러스터링 인덱스

MySQL 서버에서 클러스터링은 테이블의 레코드를 비슷한 것(pk 기준)끼리 묶어서 저장하는 형태로 구현된다. 이는 비슷한 값들을 동시에 조회하는 경우가 많다는 점에 착안한 것이다. InnoDB의 모든 테이블은 기본적으로 PK를 기준으로 클러스터링되어 물리적으로 정렬된 상태로 모든 컬럼값들과 함께 저장된다. 이것이 곧 B Tree 구조로 저장된 데이터 파일이다. 그래서 PK기반의 검색이 매우 빨라서 실행 계획에서 PK는 기본적으로 다른 보조 인덱스에 비해 비중이 높게 설정된다. 다만, 레코드의 저장이나 PK의 변경이 물리적인 페이지 재배치로 이뤄져야하는 상황으로 번지기에 상대적으로 느리다. 

*프라이머리 키의 크기가 길어도 세컨더리 인덱스가 필요치 않다면, 그대로 프라이머리 키를 사용하는 것이 좋다. 

 

7. UNIQUE 인덱스

사실 인덱스라기보다 제약 조건에 가깝다고 볼 수 있다. 다만, MySQL에서는 인덱스 없이 제약만 설정할 수가 없고, UNIQUE Index는 일반 다른 인덱스와 같은 역할을 한다. 인덱스의 구조로는 다른 Secondary Index와 동일하다. 

*Null도 unique 인덱스에 저장될 수 있는데, Null은 특정 값이 아니기에 2개 이상 저장될 수 있다. 

 

[읽기] UNIQUE하지 않은 Secondary Index는 중복된 값이 허용되므로 읽어야 하는 레코드가 많지만, UNIQUE Index는 읽어야 하는 레코드가 1개이기에 빠르다. (절대적인 1건에 대한 탐색 비용은 동일)

 

[쓰기] UNIQUE Index의 키 값을 쓸 때는 중복된 값이 있는지 없는지 체크하는 과정이 한 단계 더 필요하다. 그래서 UNIQUE하지 않은 Secondary Index의 쓰기 비해 느리다. UNIQUE Index는 중복된 값 체크할 때 S-Lock을 사용하고, 쓰기를 할 때는 X-Lock을 사용하는데, 이때 데드락이 빈번히 발생한다. 또한, 중복 체크를 해야 해서 쓰기 작업이 Change Buffer에 버퍼링되지 못하고 즉시 처리해야 하기에 변경 작업이 더 느리게 작동한다. 

 

8. 외래키

외래키 제약이 설정되면 자동으로 연관되는 테이블의 칼럼에 인덱스까지 생성된다. 즉, 부모 테이블과 자식 테이블 모두 해당 칼럼에 인덱스가 생성된다. 변경 시에는 반드시 부모 테이블이나 자식 테이블에 데이터가 있는지 체크해야 하기에 잠금이 여러 테이블로 전파되고, 이로 인해 데드락이 발생할 때가 많아 개발할 때 주의해야 한다. 

*잠금이 다른 테이블로 확장되면 그만큼 전체적으로 쿼리의 동시 처리에 영향을 미친다.