![[MySQL] 테이블과 인덱스](/images/mysql_logo.png){kind=logo}
Table of Contents
인덱스는 데이터베이스 쿼리의 성능과 관련해서 빼놓을 수 없는 중요한 부분입니다. 인덱스에 대한 지식은 개발자나 관리자 모두에게 중요한 부분이며, 쿼리 튜닝의 기본이 됩니다.
디스크 읽기 방식
보통 컴퓨터에서 가장 큰 성능 저하는 디스크 I/O에서 발생합니다. 따라서 데이터베이스의 성능 튜닝은 어떻게 디스크 I/O을 줄이느냐가 관건일 때가 상당히 많습니다.
HDD와 SSD
데이터베이스 서버에서 순차 I/O 보다는 랜덤 I/O가 차지하는 비중이 훨씬 큽니다. 그리고 이러한 랜덤 I/O의 속도를 훨씬 높여준 장치가 바로 SSD입니다. 이러한 이유로 DBMS용 스토리지에 SSD는 최적의 장치라고 할 수 있습니다.
랜덤 I/O와 순차 I/O
랜덤 I/O은 데이터의 개수만큼 데이터의 위치를 찾아야 하고, 순차 I/O은 한 번만 데이터의 위치를 찾으면 되기 때문에 랜덤 I/O으로 인한 작업 부하가 훨씬 더 크게 발생합니다. HDD는 매번 데이터의 위치를 찾기 위해 디스크 헤드를 움직여야 하기 때문에 랜덤 I/O의 작업 부하는 훨씬 더 커지게 됩니다. SSD는 디스크 원판이 아닌 플래시 메모리를 사용하기 때문에 차이가 없을 것 같지만 마찬가지로 랜덤 I/O에서 성능이 저하됩니다.
그래서 일반적으로 쿼리 튜닝의 목적은 랜덤 I/O의 회수를 줄이는 것입니다. 여기서 랜덤 I/O을 줄인다는 것은 쿼리를 처리하는 데 꼭 필요한 데이터만 읽도록 쿼리를 개선하는 것을 의미합니다. 그리고 랜덤 I/O을 줄이기 위해 저희는 인덱스라는 것을 활용할 것입니다.
DBMS에서는 랜덤 I/O이 자주 발생하고, 쿼리의 성능을 높이기 위해서는 랜덤 I/O을 줄여야 한다.
이렇게 랜덤 I/O을 줄이기 위해 DBMS에서는 인덱스를 사용한다.
인덱스란?
보통 인덱스를 설명할 때 책 맨 끝에 있는 색인을 예시로 많이 사용합니다. 예를 들어 책에서 ‘무궁화’라는 단어를 찾고 싶다면 저희는 책 페이지에서 내용을 하나씩 찾아보기 보다는 색인에서 ‘무궁화’라는 단어가 포함된 페이지의 쪽수를 찾게 될 겁니다.
DBMS도 데이터베이스 테이블의 모든 데이터를 검색해서 원하는 레코드(Row)를 가져오려면 시간이 오래 걸릴 것입니다. 그래서 컬럼의 값과 그 값을 가지는 레코드가 저장된 주소를 매핑한 인덱스를 만들어 두는 것입니다.
책의 색인: 단어 - 책 페이지 매핑
DBMS의 인덱스: 컬럼 값 - 값을 가지는 레코드(Row)의 주소 매핑
그리고 인덱스의 중요한 특성 중 하나는 키(컬럼 값)가 정렬되어 있다는 것입니다. 예를 들어 테이블의 사람 이름을 나타내는 name이라는 컬럼으로 인덱스를 만들었다고 했을 때, name 값을 정렬하여 각각의 주소를 매핑해 인덱스를 만들게 됩니다.
아래는 인덱스 페이지의 예시로 다음과 같이 name이 알파벳 순으로 정렬되어 있습니다.
| name | 레코드 주소 |
|---|---|
| Alice | 14345342 |
| Bob | 61345549 |
| Carl | 24641345 |
| Doson | 41127651 |
이렇게 인덱스 페이지를 정렬했을 때 장단점이 있습니다.
- 장점: 정렬되어 있기 때문에 인덱스(컬럼 값)를 빠르게 찾고 결과적으로 데이터를 빠르게 읽어온다
- 단점: 컬럼 값에
INSERT,UPDATE,DELETE가 발생할 때마다 인덱스를 정렬하기 때문에 저장 속도가 느리다
결론적으로 DBMS에서 인덱스는 데이터의 저장(INSERT, UPDATE, DELETE) 성능을 희생하고 데이터의 읽기 속도를 높여주게 됩니다. 그래서 인덱스 파일을 하나 더 추가할지 말지는 데이터의 저장 속도를 얼마만큼 희생하여, 그 결과로 읽기 성능을 얼마나 더 빠르게 만들지에 따라 결정되게 됩니다.
위에서 인덱스 페이지가 정렬되어 있어 인덱스 값을 빨리 찾을 수 있다고 했습니다. 정렬되어 있다는 것의 이점은 탐색 알고리즘에서 선형 탐색이 아닌 이진 탐색과 같이 선형 탐색보다 더 빠른 탐색 알고리즘을 사용할 수 있다는 것입니다.
인덱스 파일은 이진 탐색을 지원하는 이진 트리 자료 구조와 비슷하지만 더 빠른 탐색을 가능하게 하는 Balanced Tree(B-Tree)라는 자료구조로 구현되어 있습니다.
이외에도 대표적으로 Hash Table 자료구조를 이용한 방법도 있으며 최근에는 Fractal-Tree, Merge-Tree와 같은 알고리즘을 사용하는 DBMS도 개발되고 있습니다.
B-Tree 인덱스
- Balanced Tree
- 가장 일반적으로 사용되는 인덱스 형태
- 컬럼 값을 변형하지 않고 원래의 값을 이용해 인덱싱
- B-Tree를 응용한 많은 자료구조가 등장
Hash Table 인덱스
- 컬럼 값을 해시한 결과를 인덱스로 사용
- 매우 빠른 검색 지원
- 해시값을 인덱스로 사용해 컬럼 값의 일부만 검색하거나 범위를 검색할 때는 사용 불가
- 주로 메모리 기반의 데이터베이스에서 많이 사용
B-Tree 인덱스
디스크 기반 스토리지는 하드웨어적 특성으로 I/O의 가장 작은 단위가 페이지가 됩니다. 디스크 기반 자료구조는 디스크 접근 횟수를 최소화 하기 위해 데이터의 지역성을 높여야 합니다. 이렇게 지역성을 높이는 방법은 페이지를 만들 때 비슷하게 참조되는 데이터를 페이지로 만드는 것입니다. 비슷하게 참조되는 데이터를 페이지로 만듦으로써 데이터를 조회할 때 페이지를 넘나드는 포인터를 최소화할 수 있습니다.
이렇게 만든 페이지가 B-트리에서 노드가 됩니다. 다시 말해 B-트리는 페이지 기반 자료구조입니다.
(비슷하게 참조되는 키값은 사실상 정렬했을 때 인근 키값들)
이제 키 값을 기준으로 그 키 값을 가지는 실제 파일 주소를 어떻게 찾는지 예시를 들어 설명해보겠습니다.
참고로 여기서 설명하는 B-트리는 엄밀히 B+ 트리입니다 B-트리와 B+ 트리의 차이는 B-트리는 루트 노드, 브랜치 노드, 리프 노드 모든 레벨에 값을 저장하는 것이 가능하고, B+ 트리의 경우 브랜치 노드에, 리프노드에 저장된 값을 찾는데 필요한 구분(seperator) 키만 저장합니다.
MySQL에서는 MyISAM, InnoDB 모두 B+ 트리 형태로 되어 있고, 편의상 그냥 B-트리라고 하기 때문에 B-트리라고 하더라도 마음속으로는 B+ 트리 형태를 떠올리면 되겠습니다.
참고로 이러한 B+ 트리는 리프 노드에만 값을 저장하기 때문에 Insert, Update, Delete 연산은 리프노드에만 영향을 미칩니다. 상위 레벨의 노드는 트리 균형을 위해 분할 혹은 병합이 일어날 때만 영향을 받습니다.
- 인덱스의 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주소값을 가짐
- 인덱스의 키 값은 모두 정렬돼 있지만, 데이터 파일의 레코드는 정렬돼 있지 않고 임의의 순서로 저장돼 있음 (InnoDB는 예외)
- InnoDB엔진의 데이터 파일 레코드는 클러스터되어 디스크에 저장되므로 기본적으로 프라이머리 키 순서로 정렬되어 저장됨
- 인덱스는 테이블의 키 컬럼만 가지고 있으므로 나머지 컬럼을 읽으려면 데이터 파일에서 해당 레코드를 찾아야 함
InnoDB 스토리지 엔진의 데이터 파일
InnoDB 스토리지 엔진은 인덱스 뿐만 아니라 데이터 파일도 B-Tree와 같은 형태로 데이터가 정렬되어 저장되어 있습니다. 이를 클러스터링 인덱스라고 합니다. 그래서 MySQL에서 클러스터링 인덱스는 사실 데이터 파일 자체를 의미합니다.
- InnoDB 엔진에서는 인덱스를 통해 레코드를 읽을 때 파일을 바로 찾아가지 못함
- 인덱스에 저장돼 있는 프라이머리 키 값을 이용해 프라이머리 키 인덱스를 한 번 더 검색한 후,
- 프라이머리 키 인덱스의 리프 페이지에 저장돼 있는 레코드를 읽음
- 즉 InnoDB 엔진에서는 모든 세컨더리 인덱스 검색에서 데이터 레코드를 읽기 위해서는,
- 반드시 프라이머리 키를 저장하고 있는 B-Tree를 다시 한번 검색해야 함
- InnoDB 엔진에서 데이터 파일은 프라이머리 키 인덱스 자체
- 세컨더리 인덱스의 리프 노드에 레코드 주소가 아닌 프라이머리 키를 저장하고 있으면, 데이터 삽입으로 페이지 분할이 일어나도, 세컨더리 인덱스의 리프 노드는 메모리 주소가 아니라 프라이머리 키를 가지고 있기 때문에, 세컨더리 인덱스에 값을 변경하지 않아도 된다
참고로 MyISAM 스토리지 엔진의 인덱스와 데이터 파일간의 관계는 다음과 같습니다.
한 가지 짚고 넘어갈 점은 위와 같이 인덱스 키 하나에 매칭되는 레코드 하나가 매핑되는 경우는
프라이머리 키 인덱스나 유니크 키 인덱스 같은 특별한 경우이고
보통은 인덱스 키 하나에 여러 개의 레코드가 매핑된다.
근데 인덱스를 이용해서 레코드를 찾을 때는 테이블에서 그냥 레코드를 찾는 것보다 5배 정도 더 큰 비용이 들어간다.
여기서 5배는 복합적인 요인이 합해져서 5배 정도되는 것 같다.
- 우선 인덱스 키를 가지고 해당 리프 노드를 찾아가는데 걸리는 시간
- 그 리프 노드에서 해당 키를 찾는데 걸리는 시간 (이 시간은 리프 노드의 사이즈에 따라 또 달라짐)
- 그리고 키에 매핑되는 데이터의 실제 주소를 알았을 때 데이터 파일의 해당 주소로 찾아가는데 걸리는 시간. (이 경우 한 건 한건이 모두 랜덤 I/O임)
- 그리고 조건절에 사용된 인덱스가 = 과 같은 것이 아니라 범위 조건절이면 리프 노드간 이동도 해야함
데이터의 Insert, Update, Delete시 인덱스에서의 동작
- 테이블의 레코드를 저장하거나 변경하는 경우 인덱스 키 추가나 삭제 작업이 발생
인덱스 키 추가
- B-Tree에 저장될 때는 저장될 키 값을 이용해 B-Tree상의 적절한 위치를 검색해야 함
- 위치가 결정되면 레코드의 키 값과 대상 레코드의 주소 정보를 B-Tree의 리프 노드에 저장
- 리프 노드가 꽉 차서 더 저장할 수 없을 때는 리프 노드가 분리돼야 하는데, 이는 상위 브랜치 노드까지 처리의 범위가 넓어짐
- 이러한 이유로 B-Tree는 상대적으로 쓰기 작업(새로운 키를 추가하는 작업)에 비용이 많이 들어감
인덱스 키 삭제
- 해당 키 값이 저장된 B-Tree의 리프 노드를 찾아서 그냥 삭제 마크만 하면 작업이 완료됨
- 인덱스 키 삭제로 인한 마킹 작업 또한 디스크 쓰기가 필요하므로 디스크 I/O이 필요한 작업
인덱스 키 검색
- 인덱스를 구축하는 이유는 빠른 검색
- 인덱스 트리 탐색은 SELECT문 뿐만 아니라, UPDATE나 DELETE를 처리하기 위해 레코드를 검색하는 경우에도 사용됨
- 함수나 연산을 수행한 결과로 정렬한다거나 검색하는 작업은 B-Tree의 장점을 이용할 수 없음
- InnoDB 엔진의 경우, 검색을 수행한 인덱스를 잠근 후 테이블의 레코드를 잠그는 방식으로 구현돼 있음
- 따라서 UPDATE나 DELETE문이 실행될 때 테이블에 적절히 사용할 인덱스가 없으면 불필요하게 많은 레코드를 잠금
B-Tree 인덱스 사용에 영향을 미치는 요소
- B-Tree 인덱스는 인덱스를 구성하는 컬럼의 크기와 레코드의 건수, 그리고 유니크한 인덱스 키 값의 개수 등에 의해 검색이나 변경 작업의 성능이 영향을 받음
인덱스 키 값의 크기
- InnoDB 스토리지 엔진은 디스크에 데이터를 저장하는 가장 기본 단위를 페이지라고 함
- 페이지: 디스크의 모든 읽기 및 쓰기 작업의 최소 작업 단위. 또한 InnoDB 엔진의 버퍼 풀에서 버퍼링하는 기본 단위
- 인덱스도 결국은 페이지 단위로 관리됨. 루트와 브랜치, 리프 노드를 구분하는 기준이 바로 페이지 단위
- B-Tree는 자식 노드를 몇 개까지 가질 수 있을까? -> 인덱스의 페이지 크기와 키 값의 크기에 따라 결정됨
- InnoDBB 엔진의 페이지 크기를
innodb_page_size시스템 변수를 이용해 4KB~64KB로 선택 가능 기본값은 16KB - 인덱스의 키를 16bytes, 값에 해당하는 자식 노드 주소를 12bytes라 하면, 인덱스 페이지당 16*1024/28 = 585개의 키 저장 가능
- 최종적으로 이 경우에 자식 노드를 585개 가질 수 있는 B-Tree가 됨
- 인덱스 키 값이 커지면 자식 노드의 수는 줄어듬 -> B-Tree의 탐색 횟수 증가 -> SELECT 쿼리가 느려짐
B-Tree 깊이
- 위에서 키 값의 크기가 커지면 B-Tree의 깊이가 증가함을 확인
- B-Tree의 깊이는 MySQL에서 값을 검색할 때 몇 번이나 랜덤하게 디스크를 읽어야 하는지와 직결되는 문제
- 실제로는 아무리 대용량 데이터베이스라도 B-Tree의 깊이가 5단계 이상까지 깊어지는 경우는 거의 없음
선택도(유니크한 값의 수)
- 인덱스 컬럼 값중 유니크한 값의 수
- 인덱스 컬럼이 100개의 값을 가지는데 그중에서 유니크한 값의 수가 10개라면 선택도는 10
- 인덱스는 선택도가 높을수록 검색 대상이 줄어들고 검색 성능이 빨라짐
읽어야 하는 레코드의 건수
- 인덱스를 통해 테이블의 레코드를 읽는 것은 바로 테이블의 레코드를 읽는 것보다 높은 비용이 드는 작업
- 인덱스를 이용한 읽기의 손익 분기점이 얼마인지 판단할 필요가 있음
- 일반적으로 인덱스를 통해 레코드 1건을 읽는 것이 직접 읽는 것보다 4~5배 정도 비용이 더 많이 드는 작업
- 즉 인덱스를 통해 읽어야 할 레코드의 건수가 전체 테이블 레코드의 20~25%를 넘어서면 테이블을 모두 직접 읽어 필요한 레코드만 가려내는(필터링) 방식으로 처리하는 것이 효율적
- 전체 100만 건의 레코드 가운데 50만 건을 읽어야 하는 작업은 인덱스를 이용하지 않고 직접 읽어서 처리할 것
- (ex. 유저 정보를 가지고 있는 테이블이 있을 때, ‘성별’을 인덱스로 만드는 것은 비효율적)
인덱스 적용 기준
- WHERE, JOIN, ORDER BY절에 많이 사용되는 컬럼
- 카디널리티가 높은 컬럼
- INSERT, UPDATE, DELETE가 많이 발생하지 않는 컬럼
- 테이블 규모가 큰 경우
- 잘 활용하지 않는 인덱스는 삭제하는 것이 좋음
데이터의 Select시 인덱스에서의 동작
- 스토리지 엔진이 어떻게 인덱스를 이용해 실제 레코드를 읽어내는지 알아보자
인덱스 레인지 스캔
- 인덱스 레인지 스캔은 인덱스의 접근 방법 가운데 가장 대표적인 접근 방식
- 검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식
- 루트 노드에서부터 비교를 시작해 브랜치 노드를 거치고 최종적으로 리프 노드까지 들어가야만 필요한 레코드의 시작 지점을 찾을 수 있음
- 시작해야 할 위치를 찾으면 그 때부터는 리프 노드의 레코드만 순서대로 읽으면 됨. 이렇게 쭉 읽는 것을 스캔이라고 표현
- 리프 노드 끝까지 읽으면 노드 간의 링크를 이용해 다음 리프 노드를 찾아 다시 스캔
- 루트와 브랜치 노드를 이용해 스캔 시작 위치를 검색하고, 그 지점부터 필요한 방향으로 인덱스를 읽어 나감
- 읽어 나가면서 검색 조건에 일치하는 경우 데이터 파일에서 레코드를 읽어옴
- 이때 리프 노드에 저장된 레코드 주소로 데이터 파일의 레코드를 읽어오는데 한 건 단위로 랜덤 I/O이 한 번씩 일어남
- 그래서 인덱스를 통해 데이터 레코드를 읽는 작업은 비용이 많이 드는 작업으로 분류
인덱스 풀 스캔
- 인덱스 레인지 스캔과 달리 인덱스의 처음부터 끝까지 모두 읽는 방식
- 쿼리의 조건절에 사용된 컬럼이 인덱스의 첫 번째 컬럼이 아닌 경우 인덱스 풀 스캔 방식 사용
- 예를 들어 인덱스는 (A, B, C) 컬럼의 순서로 만들어져 있지만, 쿼리의 조건절은 B컬럼이나 C컬럼으로 검색하는 경우
- 일반적으로 인덱스의 크기는 테이블의 크기보다 작으므로 직접 테이블을 읽는 것보다 인덱스만 읽는 것이 효율적
- 쿼리가 인덱스에 명시된 컬럼만으로 조건을 처리할 수 있는 경우 주로 이 방식이 사용됨
테이블 풀 스캔
- 테이블 자체의 사이즈가 굉장히 작은 경우
- 조건에 부합하는 레코드가 너무 많은 경우
- 인덱스를 사용하지 못하는 경우에 해당
- WHERE 절이나 ON 절에 인덱스를 이용할 수 있는 적절한 조건이 없는 경우
- 테이블 전체를 읽어옴
루스 인덱스 스캔
- 오라클의 인덱스 스킵 스캔과 유사한 방식. MySQL에서는 루스(Loose) 인덱스 스캔이라고 함
- 위에서 봤던 인덱스 레인지 스캔, 인덱스 풀 스캔을 타이트(Tight) 인덱스 스캔으로 분류함
- 말 그대로 느슨하게 또는 듬성듬성하게 인덱스를 읽는 것을 의미
- 인덱스 레인지 스캔과 비슷하게 동작하지만 중간에 필요치 않은 인덱스 키 값은 무시(Skip)하고 넘어가는 형태로 처리
- 일반적으로 GROUP BY 또는 집합 함수 가운데 MAX(), MIN() 함수에 대해 최적화 하는 경우에 사용
- 아래의 쿼리문이 있을 때, 인덱스가 (dept_no, emp_no) 조합으로 정렬되어 있다면, WHERE절을 만족하는 각 dept_no별로 제일 첫 번째 emp_no만 읽어오고 나머지 인덱스는 스킵할 수 있음
SELECT dept_no, MIN(emp_no) FROM dept_emp WHERE dept_no BETWEEN 'd002' AND 'd004' GROUP BY dept_no;
인덱스 스킵 스캔
- 데이터베이스에서 인덱스의 핵심은 값이 정렬돼 있다는 사실 -> 이로 인해 인덱스를 구성하는 컬럼의 순서가 매우 중요
- (A, B)라는 인덱스가 있을 때 이 인덱스를 사용해 쿼리문의 빠른 처리를 하려면 WHERE 조건절에 A에 관한 조건이 반드시 제일 앞에 등장해야 함. (WHERE A=1000, 또는 WHERE A=1000 AND B=’M’)
- 나의 쿼리문에 WHERE 조건절에 A랑 B가 있다면 (A, B)라는 인덱스를 생성해주면 쿼리 성능을 향상시킬 수 있음
CREATE INDEX <인덱스명> ON <테이블명> ( 컬럼명1, 컬럼명2, ... ); ALTER TABLE <테이블명> ADD INDEX <인덱스명> (컬럼명1, 컬럼명2, ...); CREATE TABLE <테이블명> INDEX <인덱스명> (컬럼명1, 컬럼명2, ...); - MySQL 8.0부터 WHERE B=’M’과 같이 A에 관한 조건절이 없어도 인덱스 (A, B)를 이용해 인덱스 스킵 스캔을 할 수 있도록하는 최적화 기능이 도입됨
클러스터링 인덱스
- 클러스터링: 여러 개를 하나로 묶는다는 의미
- InnoDB의 프라이머리 키가 클러스터링 키로 사용되며, 이 값에 의해 레코드의 위치가 결정됨
- 비슷한 값들을 동시에 조회하는 경우가 많다는 점에 착안한 것
- 즉 프라이머리 키 값이 비슷한 레코드끼리 묶어서 저장하는 것을 클러스터링 인덱스라고 표현
- 중요한 것은 프라이머리 키 값에 의해 레코드의 저장 위치가 결정된다는 것
- 프라이머리 키 값이 변경된다면 그 레코드의 물리적인 저장 위치가 바뀌어야 한다는 것을 의미하기도 함
- 클러스터링 인덱스로 저장되는 테이블은 프라이머리 키 기반의 검색이 매우 빠름. 대신 저장은 상대적으로 느림
- 프라이머리 키가 없는 경우 InnoDB 엔진이 다음 우선순위대로 프라이머리 키를 대체할 컬럼을 선택
- NOT NULL 옵션의 유니크 인덱스 중에서 첫 번째 인덱스
- 자동으로 유니크한 값을 가지도록 증가되는 컬럼을 내부적으로 추가한 후 클러스터링 키로 선택
- 하지만 이 방법은 프라이머리 키가 사용자에게 노출되지 않으며, 쿼리 문장에서 명시적으로 사용할 수 없음(혜택 없음)
클러스터링 인덱스의 장점과 단점
- 장점
- 프라이머리 키로 검색할 때 처리 성능이 매우 빠름
- 테이블의 모든 세컨더리 인덱스가 프라이머리 키를 가지고 있기 때문에 인덱스만으로 처리될 수 있는 경우가 많음
- 단점
- 테이블의 모든 세컨더리 인덱스가 클러스터링 키를 갖기 때문에 전체적으로 인덱스의 크기가 커짐
- 세컨더리 인덱스를 통해 검색할 때 프라이머리 키로 다시 한 번 검색해야 하므로 처리 성능이 느림
프라이머리 키 사용시 주의 사항
- 클러스터링 인덱스 키의 크기를 크게 하지 않도록 해야함
- AUTO-INCREMENT보다는 가능한 업무적인 컬럼으로 생성
- 대부분 검색에서 상당히 빈번하게 사용됨 -> 설령 그 컬럼의 크기가 크더라도 해당 레코드를 대표할 수 있다면 그 컬럼을 프라이머리 키로 사용할 것을 권장
- 프라이머리 키는 반드시 명시할 것
보조 인덱스
- 세컨더리 인덱스, 논-클러스터링 인덱스라고도 불림
- 여러 개의 인덱스를 가질 수 있음
- 리프 노드에는 레코드가 저장되어 있는 주소를 가지고 있음
- 추가적인 디스크 공간을 요구함
CREATE UNIQUE INDEX [인덱스 명]
CREATE INDEX [인덱스 명]
