[MySQL] Clusterd Index와 Non-clustered Index, B-Tree

목차

배경

이전부터 RDB와 관련된 문제와 문제 해결 방안에 대한 궁금증이 있었고, 인프런에서 흥미로워 보이는 강의 200억건의 데이터를 MySQL로 마이그레이션 할 때 고려했던 개념과 튜닝 방법를 발견하여 수강하였다. 하지만 RDB와 쿼리를 서비스 로직을 구현하는데 사용해보기만 했지 실제 동작 원리를 이해해본적은 없어 강의를 수강하는데 어려움이 있었고, 따로 시간을 내어 추가적인 기본 지식을 찾아보았다.

 

강의 내용에 대해 정리해보기에 앞서 데이터베이스 성능 최적화와 관련된 가장 기본적인 지식인 인덱스(Index)에 대해서 알아본다.

데이터베이스 인덱스

MySQL을 포함한 대부분의 RDBMS는 테이블 검색 속도를 향상하기 위해 Index를 제공하고, 이러한 Index는 성능 최적화에서 중요한 역할을 한다. 데이터베이스 성능 최적화를 위해서 Index가 사용되는데 두 가지 주요 인덱스의 유형으로 Clustered Index와 Non-Clustered Index가 있다.

클러스터드 인덱스(Clustered Index)

테이블의 데이터가 실제로 인덱스의 순서에 맞춰 정렬되어 저장된다. (e.g. 전화번호 순으로 정렬된 전화번호부를 상상하자.) 즉, 실제 데이터의 위치를 가지고 있다. 테이블이 물리적으로 클러스터드 인덱스에 따라 정렬되기 때문에 한 테이블에는 하나의 클러스터드 인덱스만 존재할 수 있다.

 

기본적으로 PK 값을 기준으로 Clustered Index가 생성되며 PK가 없다면 Unique Key를, Unique key도 없다면 6byte의 Hidden Key(Row Id)를 생성하여 활용한다. (출처 : https://gngsn.tistory.com/194)

 

물리적인 데이터를 바로 조회하므로 빠른 읽기 성능을 제공하나, 인덱스는 기본적으로 B-Tree 형태로 저장되어 있기 때문에 삽입이나 업데이트 시에는 재정렬이 필요할 수 있어 오버헤드가 발생할 수 있다.

예시

다음과 같이 ID를 key로 갖는 Employees 테이블을 생성하면 ID가 클러스터드 인덱스가 되며 ID 값에 따라 데이터가 물리적으로 정렬된다.

CREATE TABLE Employees (
    ID INT PRIMARY KEY,
    Name VARCHAR(100),
    Age INT
);

논클러스터드 인덱스(Non-Clustered Index)

실제로 데이터가 정렬되는 것이 아니라, 인덱스를 구성하는 컬럼의 값들로만 별도의 디스크 공간에 정렬된 상태로 구성된다. 이때 각 인덱스는 B-Tree 형태로 구성되는데 각 노드는 인덱스를 구성하는 컬럼 값과 실제 데이터가 저장된 위치(PK 값 혹은 RowId)를 가리킨다.

 

별도의 저장 공간에 인덱스가 저장되어 있으므로 한 테이블에 여러개의 논클러스터드 인덱스를 생성할 수 있다. 하지만 무작정 인덱스를 생성하는 경우 그만큼 디스크 공간을 차지하고 Index Dive가 발생할 수 있어 주의가 필요하다.

 

논클러스터드 인덱스를 사용할 경우, 인덱스를 먼저 찾은 후 실제 데이터로 이동해야 하기 때문에 클러스터드 인덱스에 비해 약간의 오버헤드가 있다. 이때 인덱스 설계가 잘 되어있다면 실제 데이터를 조회하지 않고 쿼리 결과를 반환하여 성능 향상을 이룰 수 있는데, 이러한 인덱스를 커버링 인덱스(Covering Index)라고 한다.

예시

다음과 같이 Employees 테이블의 Name 컬럼 값을 기반으로 idx_name라는 이름의 인덱스를 생성할 수 있다.

CREATE INDEX idx_name ON Employees (Name);

 

Index(인덱스)와 B-Tree

인덱스로 설정된 컬럼은 해당 컬럼의 값들만 따로 모아서 B-Tree 구조로 저장된다.

아래 쿼리에서 employee_id 컬럼에 대해 인덱스가 설정되어 있다면, MySQL은 이 인덱스를 사용해 정렬된 값 중에서 해당 행을 빠르게 찾아낼 수 있다.

 

즉, 인덱스를 활용하면 테이블의 모든 행을 스캔하지 않고도 원하는 데이터를 찾을 수 있다. 이처럼 실제 테이블에서 데이터를 조회하지 않고 B-Tree에 미리 저장된 인덱스에 있는 컬럼 값들만 사용하여 데이터를 가져오는 것을 Covering Index라고 한다.

SELECT * FROM employees WHERE employee_id = 1001;

 

구체적인 예시로 살펴보면 다음과 같다. 예를 들어서 sample 테이블에 있는 name 컬럼에 대해 인덱스 idx_name을 생성했다고 가정하자.

+----+-------+
| id | name  |
+----+-------+
| 1  | Alice |
| 2  | Bob   |
| 3  | Carol |
| 4  | Dave  |
| 5  | Eve   |
+----+-------+

 

인덱스 idx_name은 name 컬럼의 값들만 따로 모아서 정렬된 형태로 B-Tree 구조에 다음과 같이 정렬된 형태로 유지된다. (별도의 디스크 공간에 추가로 저장된다.)

      Bob (id: 2, name: Bob)
     /                     \\
Alice (id: 1, name: Alice)   Carol (id: 3, name: Carol)
                              /                     \\
                     Dave (id: 4, name: Dave)      Eve (id: 5, name: Eve)

 

이 때 B-Tree의 노드에는 인덱싱된 컬럼 값의 복사본과 Clusterd Index 행에 대한 포인터가 포함된다. (B-Tree는 n차 BST(이진 탐색 트리)의 형태이다. 따라서 조회 성능은 빠르지만 삽입/삭제시 성능 저하가 발생할 수 있다.) 또한 자주 사용되는 인덱스는 MySQL이 캐싱해두므로 별도의 메모리 공간을 점유한다. (스토리지 엔진 별로 MySQL이 데이터를 캐싱하는 방식으로 InnoDB Buffer Pool 혹은 MyISAM Key Cache라고 한다.)

 

이러한 원리로 인덱스를 무작정 많이 생성할 수록 결국 캐시되는 인덱스가 늘어나 메모리 공간을 많이 차지할 수 있어 주의가 필요하다.

 

예시 1) 다음과 같이 쿼리에서 name 컬럼을 조건으로 사용하거나 조회하는 경우

아래 다음과 같이 두 단계에 거쳐 row를 조회한다. 결과적으로 위와 같은 과정을 통해 full table scan을 하지 않고 검색해야 할 범위를 줄이면서 해당하는 레코드를 빠르게 찾을 수 있다. 이를 통해 쿼리 성능을 크게 향상할 수 있다.

 

1. B-Tree에서 정렬된 name 값 중 Bob만을 찾아서(시간복잡도 : O(logN)) 그에 해당하는 ROW ID를 가져온다.
2. 매핑된 ROW ID를 보고 실제 테이블의 로우를 조회한다.

SELECT * FROM sample WHERE name = 'Bob';

 

예시 2) 인덱스에 포함된 컬럼만을 조회하는 경우

인덱스에 저장된 컬럼 name만 반환하므로 테이블을 조회하는 과정을 생략할 수 있다. 따라서 불필요한 데이터 읽기를 줄일 수 있다.

SELECT name FROM sample WHERE name = 'Bob';

Cardinality(카디널리티)

전체 행에서 특정 컬럼의 중복 수치(테이블의 컬럼에 포함되는 값들의 고유성 또는 다양성을 나타낸다.) 카디널리티는 곧 특정 데이터 집합의 유니크(Unique)한 값의 개수로 볼수 있다. 인덱스의 카디널리티는 쿼리 성능에 큰 영향을 미치며, 높은 카디널리티일수록 인덱스가 더 효율적으로 작동한다.

낮은 카디널리티 (Low Cardinality)

전체 행 중 어떤 컬럼에 고유(Unique)한 값들이 적고 중복되는 값이 많은 경우 카디널리티가 낮다고 표현한다.

예를 들어 성별을 저장하는 gender 컬럼은 값을 male과 female만 갖는다. 이 경우 gender컬럼은 카디널리티가 낮다고 볼 수 있다.

 

이처럼 카디널리티가 낮은 컬럼으로 인덱스를 구성한다면 대부분 행이 동일한 값을 갖게 되므로 인덱스의 효율성이 낮아진다.

gender나 status와 같은 값이 몇 가지로 제한된 컬럼에 인덱스를 사용하더라도 결과적으로 조회해오는 행의 수가 많다. 따라서 성능상 이점이 크지 않다. 결국 인덱스로 탐색하는 행의 범위를 효율적으로 좁히는데 어려움이 있다.

 

이는 결국 full scan과 성능상 큰 차이가 없을 수 있다.

높은 카디널리티 (High Cardinality)

전체 행 중 어떤 컬럼에 고유한 값들이 많고 중복되는 값들이 적은 경우 카디널리티가 높다고 표현한다.

예를 들어 주민등록번호와 같은 식별자를 담는 id 컬럼은 값이 다양하다. 이 경우 높은 카디널리티를 갖는다. 대부분 행의 값들이 서로 다르기 때문에 인덱스가 매우 효율적으로 작동한다. id나 email 같은 고유한 값이 있는 컬럼에 인덱스를 사용하면, 특정 값을 검색할 때 빠른 성능을 기대할 수 있다.

Full scan

특정 조건을 만족하는 데이터를 찾기 위해 테이블의 모든 행을 순차적으로 읽는 방식, 인덱스를 사용하지 않고 테이블 전체를 검색한다. 대량의 데이터를 처리하는 경우 성능이 저하될 수 있다.

 

MySQL에서는 EXPLAIN 명령어로 쿼리 계획을 확인할 수 있는데, type이 ALL로 나타나면 풀스캔이 발생한 것이다.

풀 스캔이 발생하는 경우 1.  쿼리에서 사용된 조건이 인덱스에 없는 컬럼을 대상으로 하는 경우

예를 들어, age에 인덱스가 없는데 age > 30을 조건으로 검색하면, MySQL은 테이블의 모든 행을 읽으며 조건에 맞는 데이터를 찾는다.

SELECT * FROM employees WHERE age > 30;

 

풀 스캔이 발생하는 경우 2. 인덱스를 사용할 수 없을 정도로 조건이 복잡한 경우

쿼리가 여러개의 Join, 서브 쿼리 등으로 구성되어 너무 복잡한 경우 Optimizer가 어떤 인덱스를 사용할지 판단하기 어려워 풀스캔이 발생할수 있다.

 

또한 인덱스는 원본 데이터에 대해 적용되므로 함수를 사용(예: LOWER() 함수)한다면 원본 데이터와 값이 달라져 인덱스를 활용할 수 없다. 이 경우 Optimizer에 의해 풀스캔이 발생할 수 있다.

SELECT * FROM employees WHERE LOWER(name) = 'john';

 

풀 스캔이 발생하는 경우 3. 인덱스의 선택성이 낮은 경우(카디널리티가 낮은 경우)

인덱스를 타면 Row를 조회할 때 B-Tree를 탐색하여 인덱스 노드를 통해 원하는 값을 찾고, 그 후에 해당 노드에서 ROWID를 통해 실제 테이블에 있는 행을 조회한다. (두 번의 단계가 필요하다.)

하지만 카디널리티가 낮은 경우 인덱스 노드를 조회하더라도 조회하는 값이 많아. (범위를 효율적으로 줄일 수 없다.) 따라서 비용이 더 많이 들 수 있다. 이 경우 Optimizer가 풀 스캔을 선택할 수 있다. (MySQL의 Optimizer는 쿼리를 실행하기 전에 어떤 방법으로 데이터를 가져올지 결정한다.)

풀 스캔이 발생하는 경우 4. 테이블 크기가 작은 경우(Row가 적은 경우)

3번째 이유와 동일하다. 인덱스를 타면 두 번의 단계가 필요하다. 하지만 로우가 적다면 전체 테이블을 한 번에 읽어도 비용이 많이 들지 않는다. 따라서 테이블의 크기가 작다면 인덱스를 탐색하는 과정(두 번의 단계)보다 전체를 읽는 것이 훨씬 효율적일 수 있다.