Real MySQL 8.0 8장 인덱스

Table of Contents

1. 디스크 읽기 방식

랜덤 I/O, 순차 I/O 두 가지 디스크 읽기 방식을 간단히 살펴 보자.

3개의 페이지를 디스크에 기록하기 위해, 랜덤 I/O와 순차 I/O는 몇 번의 시스템 콜을 요청할까? 순차 I/O는 시스템 콜을 한 번만 요청해도 되지만 랜덤 I/O는 총 3번 요청해야 한다. 순차 I/O는 디스크 헤드를 한 번 움직이지만, 랜덤 I/O는 3번 움직인다. 데이터를 읽거나 쓰는 성능은 디스크 헤드를 얼마나 적게 움직이느냐가 결정하게 된다.

여러 번의 랜덤 I/O 요청이 부하를 일으키기 때문에, MySQL은 이런 요청들을 모아 한 번에 처리하여 디스크 부하를 줄이는 그룹 커밋, 바이너리 로그 버퍼, InnoDB 로그 버퍼 등의 기능을 가지고 있다.

쿼리를 튜닝해서 랜덤 I/O를 순차 I/O로 바꾸는 것은 쉽지 않고, 랜덤 I/O를 최대한 줄이는 것이 쿼리 튜닝의 목표가 된다.

2. 인덱스란?

책을 사서 뒷부분을 펼쳐 보면 ‘찾아보기’ 라는 부분이 있다. 단어와 해당 단어가 나오는 페이지가 key-value pair를 이루고 있다. 그리고 단어가 정렬되어 있다. 책을 처음부터 읽으면서 해당 단어가 나오는 부분을 찾는 것 보다 훨씬 빠르게 찾을 수 있다.

DBMS도 비슷하다. 칼럼의 값과 해당 레코드가 저장된 주소를 key-value pair를 이루도록 하고, 칼럼의 값을 정렬해서 보관해 둔다.

즉, 인덱스는 SortedList이다. 데이터가 삽입되면, 정렬을 해야 하기 때문에 ArrayList보다 삽입 속도가 느리지만, 데이터를 찾는 속도는 훨씬 빠르다. 따라서 인덱스가 많은 테이블은 INSERT, UPDATE, DELETE가 느려진다. 대신 SELECT는 훨씬 빠르게 처리할 수 있다.

인덱스를 추가할지 말지는 “저장 속도를 얼마나 희생할 수 있는지, 읽기 속도를 얼마나 빠르게 만들어야 하는지” 에 따라 결정해야 한다. WHERE 절에 사용되는 칼럼이라고 전부 인덱스를 걸어 버리면 저장 속도가 현저히 떨어질 것이다.

인덱스는 알고리즘, 중복 값 허용 여부 등 여러 가지 기준으로 나눌 수 있다. 지금부터 Key == Index 라고 생각하자.

우선 역할별로 구분해 보면 Primary Key 그리고 Secondary Key로 구분할 수 있다. PK는 해당 레코드를 대표하는 값으로 중복을 허용하지 않고, NULL도 허용하지 않는다. PK를 제외한 나머지 인덱스는 보조 키이다.

알고리즘별로 나눌 경우 대표적으로 두 가지 인덱스가 있다. B-Tree 인덱스, 그리고 Hash 인덱스이다. B-Tree 인덱스는 칼럼의 원래 값을 이용해 인덱싱하고, Hash 인덱스는 칼럼의 값에 해시 연산을 수행하여 인덱싱한다. 때문에 Hash 인덱스는 부분 일치나 범위 검색을 처리할 수 없다.

데이터의 중복 여부로 나누면 Unique 인덱스, Non-Unique 인덱스로 나눌 수 있다. Unique 하다는 사실은 쿼리를 실행할 때 아주 중요한 사실이다. Equal 조건으로 검색했을 때 하나의 결과를 찾으면 더 이상 찾지 않아도 되기 때문이다.

전문 검색 인덱스, 공간 검색 인덱스 등등 여러 종류의 인덱스가 존재한다.

3. B-Tree 인덱스

B-Tree는 가장 중요하고, 가장 일반적으로 사용되는 인덱스이다. B-Tree의 ‘B’는 “Balanced”이다. 인덱스로 설정한 원본 값을 변형시키지 않고, 정렬된 상태를 유지한다.

여러가지 변형이 존재한다.

InnoDB는 B+Tree 방식을 사용한다. 리프 노드에만 데이터가 저장된다. 책에서는 B-Tree 라고 묶어서 부르고 있다.

구조 및 특성

B-Tree는 루트 노드 - 브랜치 노드 - 리프 노드의 구조를 가지고 있다. 반드시 최상위에 하나의 루트 노드를 가지고 있다. 최하위의 리프 노드들은 실제 데이터 레코드를 찾아가기 위한 주소를 가지고 있다. 다른 노드들은 하위 노드들의 주소를 가지고 있다(B+Tree).

인덱스는 테이블의 키 칼럼만 가지고 있기 때문에 나머지 칼럼을 읽으러면 실제 레코드를 찾아서 읽어야 한다. InnoDB 스토리지 엔진을 사용하는 경우, PK를 주소처럼 활용한다. 세컨더리 인덱스를 통해 레코드를 찾는 경우, 리프 노드에 적혀 있는 PK를 얻고, PK 인덱스의 리프 페이지에 저장된 레코드를 읽는 방식이다. 실제 물리적인 주소 대신 PK를 사용하는 것은 장단점이 존재한다. 클러스터링 인덱스를 다룰 때 알아보도록 하자.

B-Tree 인덱스 키 추가 및 삭제

B+Tree Visualization

삽입

새로운 키 값이 트리에 추가될 때, 키 값을 이용해 트리에서 저장될 위치를 찾아야 한다. 저장될 위치가 결정되면 키 값과 레코드의 주소 정보를 트리의 리프 노드에 저장한다. 이 때 리프 노드가 꽉 차서 공간이 부족한 경우, 노드를 반으로 나눈다. 분할 시 중간값이 부모 노드로 복사된다.

인덱스 추가로 인해 INSERT, UPDATE 문장이 어떤 영향을 받을 지 예측하는 방법이 있다. 테이블에 레코드를 추가하는 비용을 1이라고 했을 때, 인덱스 하나당 1.5의 비용이 추가로 든다고 예측하는 것이다. 인덱스가 3개 걸려 있는 테이블에 레코드를 추가하는 데 드는 비용은 $1 + (1.5 \times 3) = 5.5$가 될 것이다.

이 비용의 대부분은 디스크 I/O이다.

삭제

삭제할 키가 있는 리프 노드를 찾고, 해당 키를 삭제한다. 이 때 리프 노드에 존재하는 키 개수가 $M/2 - 1$개가 되면, 형제 노드에서 키를 빌려 오거나 합쳐서 트리의 특성을 만족시킨다.

InnoDB는 실제로 데이터를 즉시 삭제하지 않고, 해당 공간을 재활용할 수 있도록 삭제되었다는 표시만 한다(Lazy Deletion).

변경

단순히 노드에 있는 값을 변경만 하면 트리 구조가 깨진다. 먼저 키 값을 삭제한 후, 다시 새로운 키 값을 추가하는 형태로 처리할 수 있다.

검색

UPDATE나 DELETE를 위해 키를 검색해야 한다. 이 때 트리를 탐색하며 키를 찾는다. 100% 일치, 전방 일치, 부등호 연산에 인덱스가 사용된다. 함수 연산 등으로 값이 변경되면 인덱스를 이용할 수 없다.

InnoDB 테이블에서 지원하는 레코드 락, 넥스트 키 락이 검색을 수행한 인덱스를 잠근 후 테이블의 레코드를 잠그는 방식으로 구현되어 있다. 인덱스가 적절히 설정되어 있지 않다면, UPDATE, DELETE를 수행할 때 테이블 전체가 잠기는 참사가 일어날 수 있으니 조심해야 한다.

B-Tree 인덱스 사용에 영향을 미치는 요소

인덱스 키 값의 크기

InnoDB 스토리지 엔진은 디스크에 데이터를 저장하는 기본 단위를 페이지(Page) 라고 한다. 디스크의 모든 읽기 쓰기 작업의 최소 단위가 된다. 인덱스도 결국은 페이지 단위로 관리된다.

일반적으로 DBMS의 B-Tree의 자식 노드 개수는 가변적이다. 자식 노드 개수는 인덱스의 페이지 크기, 그리고 키 값의 크기에 따라 결정된다.

InnoDB 페이지 사이즈는 기본적으로 16KB이다. 인덱스 키 값이 16바이트, 자식 노드 주소를 나타내는 공간이 12바이트라고 하면, 페이지 하나 당 $16 \times 1024 / (16 + 12) = 585$ 개의 키를 저장할 수 있다. 인덱스 키 값이 16바이트가 아닌 32바이트가 된다면, 페이지당 저장할 수 있는 인덱스 키가 줄어들 것이다.

이렇게 되면 디스크에 더 여러 번 접근해야 한다.

B-Tree 깊이

인덱스 키 값이 16바이트, B-Tree 깊이가 3인 경우 $585^{3} = 200,201,625$개의 키 값을 담을 수 있지만, 32바이트로 늘어나면 약 5천만개정도로 줄어든다.

인덱스 키 값의 크기는 가능하면 작은 게 좋다.

실제로 B-Tree의 깊이가 5단계 이상이 되는 경우는 거의 없다.

기수성

Cardinality는 키 값 중 고유한 값의 수를 의미한다. Cardinality가 높을수록 인덱스 검색 성능이 좋아진다.

읽어야 하는 레코드의 수

전체 100만 건의 레코드 중 50만 건을 읽어와야 하는 상황이라면 인덱스를 통해 50만건을 검색하는 것 보다 테이블을 모두 읽어서 필요한 레코드만 가려내는 방식으로 처리하는 것이 좋을 것이다. 일반적인 DBMS의 옵티마이저는 테이블에서 레코드 1건을 읽는 것보다 인덱스를 통해 레코드를 읽는 것을 4~5배 비싼 작업으로 예측한다.

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

인덱스 레인지 스캔

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

라는 쿼리가 있다고 해보자. 인덱스 레인지 스캔은 검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식이다. 루트 노드부터 비교하며 필요한 레코드의 시작 지점을 찾고, 거기서부터 순서대로 읽고, 스캔을 멈춰야 할 위치에 다다르면 지금까지 읽은 레코드를 반환하면 된다.

레코드의 주소가 적혀 있고, 실제 데이터 파일의 레코드를 가져 와야 할 때는 랜덤 I/O가 발생한다. 그래서 대량의 데이터를 읽을 때는 인덱스를 통해 읽는 것 보다 테이블의 데이터를 직접 읽는 것이 효율적이다.

인덱스 풀 스캔

인덱스의 처음부터 끝까지 모두 읽는 방식을 인덱스 풀 스캔이라고 한다. 대표적으로 쿼리 조건절에 사용된 칼럼이 인덱스의 첫 번째 칼럼이 아닌 경우 인덱스 풀 스캔을 하게 된다. 즉, 인덱스가 (A, B, C) 순서로 만들어져 있는데, WHERE 절이 (B, C)로 검색하는 경우이다.

일반적으로 인덱스의 크기는 테이블의 크기보다 작다. 테이블 전체를 읽는 것 보다는 효율적이다.

테이블 전체를 읽거나 인덱스 풀 스캔을 하는 경우 보통 ‘인덱스를 사용하지 못한다’, ‘인덱스를 효율적으로 사용하지 못한다’ 라고 한다.

루스 인덱스 스캔

루스 인덱스 스캔은 레인지 스캔과 비슷하지만 중간에 필요하지 않은 키 값은 무시하고 다음으로 넘어간다. 일반적으로 GROUP BY 또는 MAX(), MIN() 함수에 대해 최적화를 하는 경우 사용된다.

인덱스 스킵 스캔

인덱스가 (A, B, C) 순서로 만들어져 있는데, WHERE 절이 (B, C)로 검색하는 경우, MySQL 8.0 버전부터 옵티마이저가 최적화를 해서 A 칼럼을 건너뛴다. 루스 인덱스 스캔은 GROUP BY 절을 처리하기 위해서만 사용됐지만 인덱스 스킵 스캔은 WHERE 절도 처리 가능하도록 용도가 넓어졌다.

다중 칼럼 인덱스

인덱스가 (A, B) 순서로 만들어져 있다면, 두 번째 칼럼 B는 첫 번째 칼럼 A에 의존해 정렬되어 있다.

(1, 1) -> (1, 2) -> (1, 3) -> (2, 1) -> (2, 2) -> (2, 3) -> (3, 1) -> (3, 2) -> (3, 3)

때문에 인덱스 내에서 각 칼럼의 순서가 상당히 중요하다.

B-Tree 인덱스의 정렬 및 스캔 방향

인덱스의 키 값은 오름차순이거나 내림차순으로 정렬되어 저장된다. 하지만 항상 그 방향으로만 읽을 수 있는 것은 아니다. 어느 방향으로 읽을지는 옵티마이저가 만들어 내는 실행 계획이 결정한다.

인덱스 스캔 방향

SELECT * FROM employees WHERE first_name >= 'Anneke'
ORDER BY first_name ASC LIMIT 4;

SELECT * FROM employees
ORDER BY first_name DESC LIMIT 5;

첫 번째 쿼리는 first_name 칼럼에 정의된 인덱스로 ‘Anneke’레코드를 찾고, 정순으로 4개를 가져온다. 두 번째 쿼리는 역순으로 읽으면서 5개를 가져온다.

쿼리의 ORDER BY, MIN, MAX 함수 등 최적화가 필요하면 옵티마이저가 알아서 읽기 방향을 전환한다.

내림차순 인덱스

페이지 잠금이 인덱스 정순 스캔에 유리한 구조이고, 페이지 내에서 인덱스 레코드가 단방향으로만 연결되어 있기 때문에 역순으로 스캔하는 경우는 조금 느리다.

역순 스캔 쿼리가 많은 경우, 내림차순 인덱스를 만드는 것이 좋은 선택이 될 수 있다.

B-Tree 인덱스의 가용성과 효율성

쿼리의 WHERE, GROUP BY, ORDER BY절이 어떤 경우에 인덱스를 타는지 식별할 수 있어야 한다.

비교 조건의 종류와 효율성

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

인덱스 순서가 (dept_no, emp_no) 인 경우, ‘d002’를 찾고, ‘10114’를 찾고 쭉 읽기만 하면 된다. 하지만 인덱스 순서가 (emp_no, dept_no) 인 경우는 emp_no >= 10114, dept_no = ‘d002’인 레코드를 찾고, 그 이후 모든 레코드에 대해 dept_no를 비교해야 한다.

첫 번째 경우의는 작업 범위 결정 조건, 두 번째 경우는 필터링 조건이 된다. 작업 범위를 결정하는 조건이 많을 수록 쿼리 성능이 높아진다. 하지만 필터링 조건은 많아져도 성능이 높아지지 않는다. 오히려 느리게 만들 때가 많다.

인덱스의 가용성

B-Tree 인덱스의 특징은 왼쪽 값에 기준해서 오른쪽 값이 정렬돼 있다는 것이다. 인덱스 키 하나의 정렬도 그렇고, 다중 칼럼에서도 왼쪽 칼럼의 값을 모르면 인덱스 레인지 스캔을 할 수 없다.

SELECT * FROM employees WHERE first_name LIKE '%mer';

정렬 우선순위가 낮은 뒷부분의 값만으로는 B-Tree 인덱스의 효과를 얻을 수 없다.

SELECT * FROM dept_emp WHERE emp_no>=10144;

인덱스가 (dept_no, emp_no)로 생성되어 있다면, dept_no 조건 없이는 레인지 스캔을 할 수 없게 된다.

4. 클러스터링 인덱스

클러스터링 인덱스란?

MySQL 서버에서 클러스터링은 테이블의 레코드를 PK를 기준으로 비슷한 것끼리 묶어서 저장하는 형태로 구현된다. InnoDB 스토리지 엔진에서만 지원한다.

중요한 것은 PK값에 의해 레코드의 저장 위치가 결정된다는 것이다. 즉, PK값이 변경되면 그 레코드의 물리적인 저장 위치가 바뀌어야 한다. 때문에 PK에 대한 의존도가 높다. PK를 신중하게 설정해야 한다.

사실 인덱스 알고리즘이라기 보다는 테이블 레코드의 저장 방식이다. InnoDB처럼 항상 클러스터링 인덱스로 저장되는 테이블은 PK 기반의 검색이 매우 빠른 대신 레코드의 저장이나 PK의 변경이 상대적으로 느리다.

클러스터링 인덱스의 장단점

• 장점
  • PK로 검색할 때 처리 성능이 매우 빠르다.
  • 테이블의 모든 세컨더리 인덱스가 PK를 가지고 있기 때문에 인덱스만으로 처리될 수 있는 경우가 많음 (커버링 인덱스)
• 단점
  • 테이블의 모든 세컨더리 인덱스가 PK를 가지고 있기 때문에 PK 값이 클 경우 전체적으로 인덱스의 크기가 커진다.
  • 세컨더리 인덱스를 통해 검색할 때 PK로 다시 한 번 검색해야 하므로 처리 성능이 느리다.
  • PK에 의해 레코드의 물리적 저장 위치가 결정되기 때문에 INSERT 처리 성능이 느리다
  • PK를 변경할 때 레코드를 DELETE하고 INSERT하는 작업이 필요하기 때문에 처리 성능이 느리다

일반적으로 웹 서비스와 같은 OLTP(On-Line Transaction Processing)에서는 쓰기와 읽기의 비율이 2:8 정도 되기 때문에 조금 느린 쓰기를 감수하고 읽기를 빠르게 유지하는 것이 중요하다.