[DB] MySQL InnoDB의 인덱스(feat. 클러스터링 인덱스, 세컨더리 인덱스, 인덱스 스캔 종류, 다중 컬럼 인덱스)

이전에 전반적인 DB 인덱스에 대해 살펴봤었습니다.

https://ksh-coding.tistory.com/122

[DB] DB 인덱스(Index)란?

 

이번에는 MySQL의 InnoDB에서는 인덱스를 어떻게 구현했는지 살펴보도록 하겠습니다.

---

1. B-Tree 인덱스를 사용하여 구현

B-Tree는 DB 인덱싱 알고리즘 중 가장 일반적으로 사용되고, 가장 먼저 도입된 알고리즘입니다.

MySQL의 InnoDB는 B-Tree 알고리즘을 사용하여 인덱스를 구현하고 있습니다.

그렇다면 B-Tree 알고리즘이 무엇인지 살펴봅시다.

 

1-1. B-Tree의 구조 및 특성

B-Tree는 Tree 자료 구조의 하나로, 여러 가지 노드로 구성되어 있습니다.

B-Tree를 구성하는 노드들은 순서대로 다음과 같습니다.

• 루트 노드(Root Node) : 최상위 하나의 노드
• 브랜치 노드(Branch Node) : 중간 노드
• 리프 노드(Leaf Node) : 최하위의 노드

출처 : Real MySQL 8.0 1권 p221

 

최종적으로 우리가 인덱스를 통해 찾고 싶은 레코드는 맨 오른쪽의 데이터 파일에 들어있습니다.

그래서 검색하고 싶은 데이터를 찾는 과정은 다음과 같습니다.

루트 노드 → 브랜치 노드 → 리프 노드 → 데이터 파일의 찾고 싶은 레코드

 

이때, 그림에서 볼 수 있듯이 리프 노드에서 항상 실제 찾고 싶은 레코드의 주솟값을 가지고 있습니다.

 

※ 페이지란?

그림에서 공통적으로 노드 옆에 ‘페이지’ 라는 개념이 보이는데, 페이지란 무엇일까요?

결과적으로 페이지의 개념은 다음과 같습니다.

디스크와 메모리(버퍼풀)에 데이터를 읽고 쓰는 최소의 작업 단위

 

인덱스 뿐만 아니라 PK, 테이블 모두 페이지 단위로 관리됩니다.

테이블, 인덱스 생성 시에 모두 페이지에 저장이 되는 것입니다.

여기서는 인덱스 생성 시에 인덱스(노드)가 저장되는 곳이라고 보면 될 것 같습니다.

 

하나의 페이지에는 정해진 크기가 존재하고, 개별 데이터들이 페이지에 저장됩니다.

이때 페이지 하나 하나를 읽을 때마다 디스크 I/O가 추가로 발생하게 됩니다.

디스크 I/O가 많아진다는 것은 성능이 떨어지게 되는 것을 의미합니다.

따라서, DB의 성능을 개선하기 위해서는 디스크 I/O를 줄이는 것이 핵심입니다.

 

디스크 I/O를 줄이기 위해서는 페이지 하나의 개별 데이터를 줄여 최대한 담아야 합니다.

페이지 하나의 개별 데이터가 크게 되면 다음과 같은 상황이 발생하여 성능이 저하됩니다.

• 개별 데이터가 커서 페이지가 여러개 생성되므로 추가 페이지를 읽기 위해 디스크 I/O가 많아집니다.
• 메모리(버퍼풀)에 각 페이지를 캐싱하는데, 페이지 자체의 크기가 커져서 캐싱할 수 있는 페이지 수가 줄어듭니다.

 

다시 돌아와서, 그림과 함께 B-Tree의 구조를 살펴봅시다.

출처 : Real MySQL 8.0 1권 p221

 

인덱스는 페이지 단위로 저장되고, 항상 정렬된 상태를 유지합니다.

정렬된 인덱스의 키를 따라서 루트 노드 → 브랜치 노드 → 리프 노드 순으로 리프 노드에 도달하면

리프 노드에는 인덱스 키와 레코드의 PK가 Key-Value 형태로 쌍으로 저장되어 있습니다.

 

출처 : Real MySQL 8.0 1권 p222

출처 : Real MySQL 8.0 1권 p222

 

위의 그림은 MyISAM과 InnoDB의 리프노드와 찾고자 하는 테이블 데이터 레코드를 나타낸 것입니다.

 

MyISAM의 경우에는 처음 사진처럼 바로 리프 노드에서 찾고자 하는 테이블 데이터 레코드의 물리적인 주소값을 Value로 가지기 때문에 바로 찾아갈 수 있습니다.

 

하지만 InnoDB의 경우에는 리프 노드에서 레코드의 물리적인 주소값이 아닌 PK를 가지기 때문에

레코드를 접근할 때 바로 접근할 수 없습니다.

왜냐하면, PK가 기본적으로 '클러스터링 인덱스'로 관리되기 때문입니다.

따라서, PK로 접근 시 PK 인덱스를 한번 더 검색하게 되고 PK 인덱스의 리프 노드에 있는 레코드를 최종적으로 읽습니다.

 

 

1-2. 클러스터링 인덱스란?

이를 정확히 이해하기 위해서는 ‘클러스터링 인덱스’가 무엇인지 알아야겠죠?

클러스터링 인덱스는 MySQL의 InnoDB에서만 지원하고, 나머지 스토리지 엔진에서는 지원되지 않습니다.

클러스터링 인덱스는 다음과 같습니다.

PK가 비슷한 레코드끼리 묶어서 인덱스로 저장한 것

 

따라서, MySQL에서 클러스터링 인덱스는 PK에 대해서만 적용되는 내용입니다.

클러스터링 인덱스도 인덱스이므로 PK 기반의 검색이 매우 빠르지만, 레코드의 저장이나 PK 변경이 상대적으로 느립니다.

출처 : Real MySQL 8.0 1권 p272

 

위의 그림은 MySQL InnoDB의 클러스터링 인덱스를 나타낸 그림입니다.

리프 노드를 잘 살펴보면, 이전에 살펴봤던 인덱스의 리프 노드와는 달리 클러스터링 인덱스의 리프 노드에는

레코드의 모든 컬럼이 저장되어 있는 것을 알 수 있습니다.

 

 

1-3. 세컨더리 인덱스를 통한 검색

클러스터링 인덱스의 개념을 살펴보고, 다시 이전에 살펴봤던 B-Tree의 구조를 살펴봅시다.

출처 : Real MySQL 8.0 1권 p222

 

위의 그림은 ‘세컨더리 인덱스’를 통해서 찾고자 하는 레코드를 찾아가는 그림입니다.

그렇다면, 세컨더리 인덱스는 무엇일까요? 개념은 다음과 같습니다.

클러스터링 인덱스(PK 인덱스)를 제외한 모든 인덱스

 

앞에서 다음과 같이 언급했었습니다.

리프 노드에서 레코드의 물리적인 주소값이 아닌 PK를 가지기 때문에 레코드를 접근할 때 바로 접근할 수 없습니다.

 

이러한 경우는 클러스터링 인덱스(PK 인덱스)가 아닌 세컨더리 인덱스의 경우에 해당하는 말이었습니다.

 

따라서, 세컨더리 인덱스의 리프 노드에는 찾고자 하는 레코드의 물리적인 주소값이 아닌 PK를 가집니다.

그렇기 때문에 바로 레코드에 접근할 수 없고 클러스터링 인덱스 검색을 한 번 더 거쳐서

원하는 레코드에 접근하게 됩니다.

 

여기까지 잘 이해하셨다면, 다음과 같은 생각이 들 수 있습니다.

“세컨더리 인덱스를 통한 검색은 왜 클러스터링 인덱스를 한번 더 거치게 했을까? 성능이 안 좋은 거 아닌가?”

 

세컨더리 인덱스의 리프 노드에서 실제 레코드가 저장된 주소를 가지지 않고 PK를 가지는 이유는

레코드 변경 시 인덱스의 부하를 줄이기 위해서입니다.

 

예를 들어, 다음과 같은 테이블이 있다고 해봅시다.

CREATE TABLE MEMBER (
    id BIGINT NOT NULL AUTO_INCREMENT,
    name VARCHAR(20) NOT NULL,
    nickname VARCHAR(20) NOT NULL,
    address VARCHAR(20) NOT NULL,
    PRIMARY KEY (id)
)

여기서 세컨더리 인덱스의 리프 노드에서 PK가 아닌 실제 레코드가 저장된 주소를 가진다고 생각해봅시다.

이때 해당 테이블의 클러스터링 되어있는 PK id 컬럼이 변경된다고 했을 때,

해당 레코드의 물리적 주소값이 변경됩니다.

 

이때 PK가 아닌 name, nickname, address의 인덱스(세컨더리 인덱스)의 리프 노드에서

실제 레코드가 저장된 주소값을 가진다면 해당 테이블의 모든 인덱스에 저장된 물리적 주솟값을 변경해야 합니다.

 

해당 상황에서 세컨더리 인덱스의 리프 노드가 실제 레코드 주소값이 아닌 PK를 논리적으로 참조한다면 어떨까요?

레코드의 값이 변경되어도 논리적인 PK 참조는 변경되지 않기 때문에 세컨더리 인덱스의 변경이 일어나지 않게 됩니다.

이렇듯 레코드 변경 시에 오버헤드를 제거하기 위해 세컨더리의 인덱스의 리프 노드가 PK를 가지는 것을 알 수 있습니다.

 

 

1-4. MySQL InnoDB의 B-Tree 인덱스 요약

MySQL InnoDB의 B-Tree를 사용한 인덱스를 이해하기 위해서 다음과 같은 개념을 살펴봤습니다.

• B-Tree 알고리즘
• 루트 노드(페이지)
• 브랜치 노드(페이지)
• 리프 노드(페이지)
• 클러스터링 인덱스
• 세컨더리 인덱스

 

아래의 2가지 인덱스를 활용한 검색 상황을 예시로 들면서 MySQL InnoDB의 인덱스 구현을 요약해보도록 하겠습니다.

(1-3의 MEMBER 테이블로 예시를 들도록 하겠습니다.)

 

SELECT * FROM member WHERE id = 1;

해당 상황에서 검색 조건은 PK인 id 컬럼을 통해 조회를 하고 있습니다.

이때는 클러스터링 인덱스에 바로 접근하여 클러스터링 인덱스의 리프 노드에서 해당 레코드를 바로 조회합니다.

출처 : Real MySQL 8.0 1권 p272

 

SELECT * FROM member WHERE name = ‘성하’;

 

해당 상황에서 검색 조건은 PK가 아닌 name 컬럼을 통해 조회를 하고 있습니다.

이때는 세컨더리 인덱스를 사용하여 세컨더리 인덱스의 리프 노드에서 해당 레코드의 PK 값을 통해

클러스터링 인덱스의 루트 노드 → 브랜치 노드 → 리프 노드로 접근하여 찾고자 하는 레코드를 조회합니다.

(아래는 예시 테이블과는 상관없는 그림으로, 접근하는 과정만 봐주시면 될 것 같습니다!)

출처 : Real MySQL 8.0 1권 p222

 

---

2. 레코드 추가, 수정, 삭제 시 인덱스 변화

테이블의 레코드 추가, 수정, 삭제 시 인덱스에 변화가 발생합니다.

테이블의 레코드 작업이 수행될 때 인덱스가 어떻게 변화하는지를 알면 쿼리 성능 개선에 도움이 될 것입니다.

각각 어떻게 변화하는지 살펴보도록 합시다.

 

2-1. 레코드 추가

인덱스의 특징 중에 다음과 같은 특징이 존재했습니다.

항상 정렬된 상태를 유지한다.

 

따라서, 레코드가 추가되었을 때 항상 정렬된 상태를 유지하기 위해서 추가될 인덱스의 적절한 위치를 탐색한 후에 저장합니다.

이때 인덱스의 추가 비용은 레코드를 추가하는 비용의 약 1.5배입니다.

만약 인덱스가 3개 존재한다면 레코드 추가 비용 1 + 인덱스 추가 비용 1.5 * 3 = 5.5로 계산합니다.

이때의 비용은 메모리, CPU에서 처리하는 시간이 아니라 디스크 I/O 비용이기 때문에 상당히 비쌉니다.

 

InnoDB에서는 메모리에 인덱스 추가 작업을 지연시켜서 디스크 쓰기 횟수를 줄여 효율적으로 한 번에 쓰도록 할 수 있습니다.

하지만, PK나 유니크 인덱스의 경우 추가한 즉시 중복 검사가 필요하기 때문에 지연없이 작업을 수행합니다.

 

 

2-2. 레코드 삭제

레코드 삭제 시에도 마찬가지로 인덱스가 삭제되어야 합니다.

이때 인덱스 삭제 방법은 해당 레코드가 저장된 인덱스의 리프 노드에 삭제 마킹 작업을 수행하면 됩니다.

이렇게 삭제 마킹된 인덱스 키 공간은 그대로 방치하거나, 재활용할 수도 있습니다.

레코드 삭제도 마찬가지로 디스크 I/O가 필요한 작업이기 때문에 지연시켜서 효율적으로 처리할 수도 있습니다.

 

 

2-3. 레코드 수정

레코드가 수정되면 인덱스의 키 값이 변경됩니다.

인덱스의 키 값은 해당 값에 따라 저장될 리프 노드의 위치가 결정되기 때문에

인덱스의 키 값이 변경된다고 할 때 기존 인덱스의 키 값만 변경하는 것은 불가능하고, 위치를 아예 다시 결정해야한다.

따라서, 인덱스의 키 값 변경 작업은 먼저 키 값을 삭제한 후에 새로운 키 값을 추가하는 형태로 처리됩니다.

 

2-4. 레코드 검색

인덱스를 사용하여 레코드를 검색하는 상황은 앞서 살펴본 것처럼 2가지 상황이 존재합니다.

• PK로 레코드 검색 : 클러스터링 인덱스를 통해 바로 조회
• 인덱스로 레코드 검색 : 세컨더리 인덱스를 통해 PK를 찾고 PK를 통해 조회

 

PK나 인덱스를 사용하지 않는 일반 값으로 레코드를 검색하는 상황도 있지만,

결국 테이블의 모든 레코드를 조회해야하기 때문에 성능이 좋지 않습니다.

(Full Table Scan)

 

추가로 레코드 검색뿐만 아니라 레코드의 수정, 삭제 시에도 수정, 삭제 전에 해당 레코드를 찾고 수행할 때도

인덱스를 통한 검색이 사용됩니다.

---

3. 인덱스를 통한 데이터 읽기

그렇다면, MySQL InnoDB가 어떻게 인덱스를 이용해서 실제 레코드를 조회하는지 살펴보겠습니다.

예제들은 모두 Real MySQL 8.0 1권에 나온 예제들로 설명하도록 하겠습니다.

 

 

3-1. 인덱스 레인지 스캔(Index Range Scan)

인덱스 레인지 스캔은 인덱스의 접근 방법 중 가장 대표적인 접근 방법입니다.

인덱스 레인지 스캔은 검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방법입니다.

다음 쿼리를 예제로 들 수 있습니다.

SELECT * FROM employees WHERE first_name BETWEEN 'Ebbe' AND 'Gad';

출처 : Real MySQL 8.0 1권 p231

 

위의 그림은 인덱스 레인지 스캔을 나타낸 그림입니다.

루트 노드에서 시작해서 최종적으로 리프 노드까지 들어가면 찾고자 하는 레코드의 시작 위치를 찾을 수 있습니다.

그때부터는 리프 노드의 레코드를 순서대로 읽으면 됩니다.

이때 인덱스의 리프 노드를 통해 찾고자 하는 레코드를 읽어 오는데 레코드 한 건 단위로 랜덤 I/O가 발생합니다.

따라서, 데이터 레코드를 읽는 작업은 랜덤 I/O가 발생하므로 비용이 많이 드는 작업입니다.

 

인덱스 레인지 스캔의 과정을 요약하면 다음 3가지 과정으로 요약할 수 있습니다.

1. 인덱스 상에서 찾고자 하는 레코드의 시작 위치를 가리키는 인덱스 찾기 (인덱스 탐색, Index seek)
2. 해당 인덱스부터 필요한 만큼 인덱스 쭉 읽기 (인덱스 스캔, Index Scan)
3. 2번에서 읽은 인덱스 키와 레코드 주소를 통해 레코드가 저장된 페이지를 가져오고, 최종 레코드 읽기

 

3번 작업은 만약 쿼리가 커버링 인덱스로 처리된다면 수행되지 않는다.

3번 작업에서 인덱스에서 레코드를 읽을 때 랜덤 I/O가 발생하므로

커버링 인덱스로 인해서 3번 작업을 수행하지 않아도 된다면 성능이 상당히 향상될 것입니다.

 

※ 커버링 인덱스란?

커버링 인덱스는 다음과 같습니다.

쿼리를 충족시키는데 필요한 모든 데이터를 갖고 있는 인덱스

 

쉽게 말하면, 쿼리의 모든 항목이 인덱스 컬럼으로 이루어져 있을 때 커버링 인덱스를 사용했다고 말합니다.

 

쿼리 예시 2가지를 들어보도록 하겠습니다.

CREATE TABLE MEMBER (
    id BIGINT NOT NULL AUTO_INCREMENT,
    name VARCHAR(20) NOT NULL,
    nickname VARCHAR(20) NOT NULL,
    address VARCHAR(20) NOT NULL,
    PRIMARY KEY (id)
)

 

 

해당 테이블에서 name 컬럼에 인덱스를 추가했다고 해봅시다.

 

1. SELECT * FROM member WHERE name = '성하';
2. SELECT name FROM member WHERE name = '성하';

 

1번의 경우 where 조건 절에는 인덱스 컬럼이 사용되었지만

select 절의 인덱스가 설정된 id, name 이외의 nickname, address 필드까지 가져와야 하기 때문에

인덱스 정보로만 구성할 수 없고, 인덱스를 통해 해당 레코드를 읽어와야 합니다.

이 경우에는 커버링 인덱스가 사용되었다고 할 수 없습니다.

 

2번의 경우에는 where 조건 절은 1번 경우와 같이 인덱스 컬럼이 사용되고,

select 절에 인덱스가 설정된 컬럼인 name만 가져오면 됩니다.

이때는 인덱스 정보로만 모든 쿼리를 충족할 수 있기 때문에 이때 커버링 인덱스가 사용되었다고 할 수 있습니다.

 

따라서, 커버링 인덱스가 사용되었다는 것은 찾고자 하는 레코드를 읽지 않고

인덱스 상의 정보로만 쿼리를 충족했다는 것이고, 레코드 읽기 시에 발생하는 랜덤 I/O가 발생하지 않았다는 의미입니다.

그렇기 때문에 커버링 인덱스를 사용하도록 개선하면 쿼리 성능을 높일 수 있습니다.

 

 

3-2. 인덱스 풀 스캔(Index Full Scan)

인덱스 풀 스캔은 인덱스를 처음부터 끝까지 모두 읽는 방식을 말합니다.

대표적인 경우는 쿼리의 조건절에 사용된 컬럼이 여러 인덱스 컬럼 중 첫 번째 인덱스로 설정된 컬럼이 아닌 경우에

인덱스 풀 스캔 방식을 사용합니다.

 

이는 인덱스 레인지 스캔보다는 비효율적이지만 테이블을 처음부터 끝까지 읽는 테이블 풀 스캔보다는 효율적입니다.

출처 : Real MySQL 8.0 1권 p234

 

 

3-3. 루스 인덱스 스캔(Loose Index Scan)

루스 인덱스 스캔이란 느슨하게, 듬성듬성 인덱스를 읽는 것을 말합니다.

일반적으로 GROUP BY 또는 MAX(), MIN() 함수를 사용하는 쿼리를 최적화할 때 사용됩니다.

Real MySQL 8.0의 쿼리 예제를 살펴보겠습니다.

SELECT dept_no, MIN(emp_no)
FROM dept_emp
WHERE dep_no BETWEEN 'd002' AND 'd004'
GROUP BY dept_no;

 

여기서 dept_no와 emp_no라는 컬럼에 인덱스가 생성되어 있고

인덱스가 dept_no, emp_no로 정렬까지 되어 있습니다.

출처 : Real MySQL 8.0 1권 p235

 

이때 쿼리에서 WHERE을 만족하는 레코드를 모두 읽지 않고

필요한 부분(각 종류별로 하나)만 읽고 다음 레코드로 이동하는 것을 알 수 있습니다.

 

 

3-4. 인덱스 스킵 스캔(Index Skip Scan)

인덱스 스킵 스캔은 MySQL 8.0부터 추가된 기능으로, 인덱스의 뒷 컬럼만으로 검색하는 경우 옵티마이저가 자동으로 쿼리를 최적화해서 인덱스를 사용하도록 하는 읽기 방식입니다.

 

Real MySQL 8.0에서 나온 예제 기준으로 설명해보도록 하겠습니다.

 

인덱스가 (gender, birth_date) 순서로 설정되어 있을 때 다음과 같은 쿼리를 살펴봅시다.

SELECT * FROM employees WHERE birth_date >= '1965-02-01';

해당 쿼리는 birth_date 컬럼이 조건에 사용되긴 하지만 인덱스 설정 시 (gender, birth_date) 순서로 설정했기 때문에

인덱스를 사용하지 못하는 쿼리가 됩니다.

이러한 상황에서 MySQL 8.0 버전 이전에는 birth_date 컬럼부터 시작하는 인덱스를 새로 생성해야만 했습니다.

 

하지만 MySQL 8.0 버전부터는 인덱스 스캔 최적화를 통해 birth_date 컬럼만으로도 인덱스 검색이 가능하게 해주빈다.

원리는 조건 절에 없지만 인덱스로 설정된 gender 컬럼에서 유니크한 값을 모두 조회한 후에

주어진 쿼리에 gender 컬럼의 조건을 추가해서 쿼리를 다시 실행하는 형태로 처리가 됩니다.

따라서, 내부적으로 다음과 같은 쿼리가 실행됩니다.

SELECT * FROM employees WHERE gender='M' AND birth_date >= '1965-02-01';
SELECT * FROM employees WHERE gender='F' AND birth_date >= '1965-02-01';

 

해당 기능은 MySQL 8.0에 도입된 기능이기 때문에 다음과 같은 한계를 가집니다.

• 인덱스 설정이 되지 않은 컬럼의 유니크한 값을 모두 가져올 때, 해당 유니크한 값의 개수가 적어야한다.
• 커버링 인덱스로 사용될 때만 적용된다.

---

3. 다중 컬럼 인덱스(Multi-Column Index)

앞서 살펴본 인덱스들은 대부분이 모두 1개의 컬럼만 포함된 인덱스였습니다.

하지만, 인덱스가 1개가 아니라 두개 이상의 컬럼으로 구성된 인덱스면 어떻게 될까요?

출처 : Real MySQL 8.0 1권 p240

 

위의 그림은 Real MySQL 8.0에서 다중 컬럼 인덱스를 나타낸 그림입니다.

위의 예시는 dept_no, emp_no 컬럼을 인덱스로 설정했습니다.

그림에서 중요한 점은 인덱스의 두 번째 컬럼(emp_no)가 첫 번째 컬럼(dept_no)에 의존해서 정렬되어 있다는 것입니다.

맨 아래 있는 레코드를 보면, emp_no만 본다면 그림에 있는 모든 레코드 중 가장 처음으로 나와야 합니다.

하지만 dept_no가 정렬했을 때 가장 뒤이므로 맨 아래 위치하게 되는 것입니다.

 

따라서 다중 컬럼 인덱스에서는 인덱스 내에서의 각 컬럼의 위치(순서)가 상당히 중요하며,

이는 인덱스를 설정할 때 결정됩니다.

 

인덱스를 (dept_no, emp_no) 순으로 설정한 후 다음과 같은 쿼리를 실행시킬 때 어떻게 될까요?

SELECT * FROM employees WHERE emp_no=10013 AND dept_no='d003';

 

인덱스의 순서는 dept_no, emp_no 순이지만 WHERE 조건 절의 순서는 emp_no, dept_no입니다.

이때는 일반적인 인덱스 레인지 스캔이 아니라 앞서 살펴봤던 인덱스 풀 스캔을 사용하여 읽게 됩니다.

그렇기 때문에 성능이 더 느려지는 것을 확인할 수 있습니다.

 

따라서, 다중 컬럼 인덱스를 사용할 때는 어떤 방식의 조회가 자주 일어나는지, 필터링이 어떻게 될지 고민 후에

인덱스의 순서를 잘 고려하여 설정하는 것이 중요합니다.