[MySQL] InnoDB의 B-Tree Index

Real MySQL 8.0 1권

Real MySQL 8.0 읽으면서 배웠던 부분들을 정리한 글입니다.

 

디스크 읽기 방식

---

컴퓨터에서 CPU나 메모리 같은 전자식 장치와 달리 기계적 장치인 디스크는 상대적으로 속도가 느리다. 따라서 디스크 I/O 감소가 데이터베이스 성능 튜닝에 많은 영향을 주게 된다.

 

HDD와 SSD의 차이점

이러한 기계식 하드디스크 드라이브를 대체하기 위해 전자식 저장 매체인 SSD가 많이 출시되고 있다. 또한 SSD도 하드 디스크 드라이브와 같은 인터페이스(SATA, SAS)를 지원하므로 내장 디스크나 DAS 또는 SAN에 그대로 사용할 수 있다. 원판을 기계적으로 회전시키는 하드디스크와 달리 SSD는 플래시 메모리를 사용하므로 상대적으로 데이터를 빨리 읽고 쓸 수 있다.

디스크의 헤더를 움직이지 않고 한 번에 많은 데이터를 읽는 순차 I/O에선 플래시 메모리와 하드디스크가 비슷한 성능을 내기도 한다. 하지만 랜덤 I/O에선 확연한 성능 차이를 보이게 된다. 웹 서비스의 데이터베이스에선 랜덤 I/O를 통해 작은 데이터를 읽고 쓰는 작업이 대부분 이므로 SSD는 DBMS용 스토리지에 최적이다.

 

랜덤 I/O와 순차I/O의 차이점

디스크 헤더를 움직이는 과정에서 순차 I/O에 비해 랜덤 I/O의 속도가 떨어지게 된다. 랜덤 I/O를 순차 I/O로 바꿔서 실행할 방법은 그다지 많지 않기 때문에 일반적으로 꼭 필요한 데이터만 읽는 방식으로 쿼리를 튜닝한다.

인덱스 레인지 스캔은 주로 랜덤 I/O를 사용하며, 풀 테이블 스캔은 순차 I/O를 사용한다. 이로인해 대부분의 데이터를 읽어야 하는 작업에선 인덱스를 사용하지 않고 풀 테이블 스캔을 유도하는 경우도 있다. 이러한 형태는 OLTP(Online Transaction Processing) 성격의 웹서비스보단 데이터 웨어하우스나 통계 작업에서 사용된다.

 

 

 

인덱스란?

---

데이터베이스 테이블의 모든 데이터를 검색해서 원하는 결과를 가져오려면 시간이 많이 소요되기 때문에, 컬럼의 값과 저장된 주소를 정렬된 key-value 쌍의 데이터를 메모리에 만들어 둔다. 책의 "찾아보기"와 같은 기능을 하는 것이다.

데이터가 저장될 때마다 항상 값을 정렬해야 하므로 저장하는 과정은 느리지만, 이렇게 정렬된 데이터를 조회하는 과정은 매우 빠르다. 따라서 인덱스가 많은 테이블은 INSERT, UPDATE, DELETE 문장의 처리가 느려지므로 주의해야 한다.

 

 

 

B-Tree 인덱스

---

B+-Tree 또는 B*-Tree가 사용된다. 컬럼의 원래 값을 변형시키지 않고 인덱스 구조체 내에서 항상 정렬된 상태를 유지한다. ( B-Tree의 종류는 자식 노드의 개수와 연결 형태 등에 따라 나뉜다. )

 

구조 및 특성

트리 구조의 최상위에 하나의 루트 노드가 존재하고 그 하위에 자식 노드가 붙어있는 형태. 인덱스의 리프 노드는 실제 데이터 레코드를 찾아가기 위한 주솟값을 가지고 있다.

InnoDB에서 레코드는 클러스터되어 저장되므로 기본적으로 프라이머리 키 순서로 정렬되어 저장된다. MyISAM 테이블은 세컨더리 인덱스가 물리적인 주소를 가지고, InnoDB 테이블은 논리적인 주소인 프라이머리 키를 가지고있다. 때문에 프라이머리 키를 저장하고 있는 B-Tree를 다시 검색해야 한다.

• 프라이머리 키: 레코드를 대표하는 컬럼의 값으로 만들어진 인덱스
• 세컨더리 인덱스: 프라이머리 키를 제외한 모든 인덱스

 

 

인덱스 키 관리 특징

인덱스 키 추가

인덱스를 추가할 때, 리프노드가 꽉 차서 저장할 수 없을 때는 리프노드가 분리 되어야 한다. 이는 상위 브랜치 노드까지 처리 범위가 넓어지기 때문에 B-Tree는 상대적으로 쓰기 작업에 비용이 많이 든다. 하지만 MyISAM이나 MEMORY 스토리지 엔진을 사용하는 테이블은 즉시 새로운 키 값을 B-Tree에 추가하는 반면 InnoDB는 필요하다면 지연시켜 나중에 처리할 수 있다.

 

인덱스 키 삭제

인덱스 추가와 마찬가지로 InnoDB에선 이 작업 또한 버퍼링되어 지연 처리될 수 있다.

 

인덱스 키 변경

B-Tree의 키 값 변경 작업은 먼저 키 값을 삭제한 후, 다시 새로운 키 값을 추가하는 형태로 처리된다.

 

인덱스 키 검색

인덱스의 트리 탐색은 SELECT 뿐만 아니라 UPDATE나 DELETE를 처리하기 위해 검색할 경우에도 사용된다.

검색은 100%일치 또는 값의 앞부분만 일치하는 경우 사용할 수 있다.  ( e.g LIKE '%something' ) 또한 인덱스의 키 값에 변형이 가해진 경우는 B-Tree에 존재하는 값이 아니므로 B-Tree를 사용할 수 없으니 주의해야 한다. ( e.g. something_index+1 > 100 )

 

 

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

인덱스 키 값의 크기

InnoDB 스토리지 엔진에서 디스크에 데이터를 저장하는 가장 기본 단위를 페이지 또는 블록이라고 한다. 이는 디스크의 모든 읽기 및 쓰기 작업의 최소 작업 단위가 되기도 하며 버퍼 풀에서 데이터를 버퍼링하는 기본 단위이기도 하다.

B-Tree의 자식 노드 개수는 인덱스의 페이지 크기와 키값의 크기에 따라 결정된다. innodb_page_size 시스템 변수를 이용하여 값을 선택할 수 있지만 기본 값은 16KB이다. 인덱스의 크기가 커지면, 한 페이지에 저장할 수 있는 인덱스의 개수가 줄어들고 더 많은 메모리를 소요해야 하므로 인덱스 키 값의 길이를 가능한 작게 설정해야 한다.

 

선택도(Selectivity) 기수성(Cardinality)

모든 인덱스 키 값 가운데 유니크한 값의 수. 선택도가 높을 수록 검색 대상이 줄어들기 때문에 더 빠르게 처리된다.

 

읽어야 하는 레코드의 개수

인덱스를 통해 테이블의 레코드를 읽는 것은 인덱스를 거치지 않고 바로 레코드를 읽는 것보다 높은 비용이 드는 작업이다. 따라서 전체 테이블을 모두 읽어 필요없는 데이터를 버리는 것이 효율적일지, 인덱스를 통해 필요한 데이터 개수만 읽어 오는 것이 효율적일지 판단해야 한다. 일반적인 DBMS 옵티마이저는 인덱스를 통해 레코드를 읽는 작업을 4~5배 더 많이 비용이 드는 작업으로 예측한다. 따라서 전체 테이블 레코드의 20~25%를 넘어서면 인덱스를 사용하지 않고 모두 직접 읽어 필터링하는 방식으로 처리한다.

 

 

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

인덱스 레인지 스캔

검색해야 할 인덱스 범위가 결정되었을 때 사용하는 방식. 시작해야 할 위치를 찾으면 그때부터는 리프 노드의 레코드만 순서대로 읽으면 된다. 최종적으로 스캔을 멈춰야 할 위치에 다다르면 지금까지 읽은 레코드를 사용자에게 반환하고 쿼리를 끝낸다.

1. 인덱스에서 조건을 만족하는 값이 저장된 위치를 찾는다. (인덱스 탐색)
2. 1번에서 탐색된 위치부터 필요한 만큼 인덱스를 차례대로 읽는다. (인덱스 스캔)
3. 2번에서 읽어 들인 인덱스 키와 레코드 주소를 이용해 레코드가 저장된 페이지를 가져오고, 최종 레코드를 읽어 온다.

커버링 인덱스로 처리되는 쿼리는 3번 과정인 디스크의 레코드를 읽지 않아도 되기 때문에, 성능이 더 빨라진다. SHOW STATUS LIKE 'Handler_%'명령어를 통해 1,2번 단계의 작업이 얼마나 수행되었는지 확인 할 수 있다.

 

인덱스 풀 스캔

인덱스의 처음부터 끝까지 모두 읽는 방식. 쿼리의 조건절에 사용된 컬럼이 인덱스의 첫 번째 컬럼이 아닌 경우. 일반적으로 인덱스의 크기는 테이블의 크기보다 작기 때문에 테이블을 읽는 것보다 인덱스를 읽는 것이 효율적이다. 인덱스 레인지 스캔보다 빠르진 않지만 테이블 풀 스캔보다 효율적이다.

 

루스 인덱스 스캔

인덱스를 부분적으로 읽는 것을 의미한다. 이와 상반된 의미에서 인덱스 레인지 스캔과 인덱스 풀 스캔을 타이트 인덱스 스캔으로 분류한다.

중간에 필요하지 않은 인덱스 키 값을 무시하고 다음으로 넘어가는 형태로 처리한다. 일반적으로 GROUP BY 또는 MAX, MIN 함수에 대해 최적화를 하는 경우 사용한다.

 

인덱스 스킵 스캔

MySQL 8.0에서 새롭게 도입된 기능으로 GROUP BY 작업을 위한 루스 인덱스 스캔과는 달리 WHERE 조건 절의 검색을 위한 스캔이다. 앞 순서의 인덱스의 컬럼을 사용하는 쿼리가 아닌 경우 앞 순서 인덱스 조건을 추가하여 부분적으로 인덱스 스캔을 한다. 따라서 선행 컬럼이 선택도가 높을 경우 오히려 성능이 느릴 수 있다. 따라서 다음과 같은 단점을 가진다.

• WHERE 조건절에 조건이 없는 인덱스 선행 컬럼의 선택도가 낮아야 한다.
• 쿼리가 인덱스에 존재하는 컬럼만으로 처리 가능해야 한다. (커버링 인덱스)

 

 

다중 컬럼 인덱스

두 개 이상의 컬럼으로 구성된 인덱스. 다중 컬럼 인덱스의 정렬은 선행 컬럼에 의존해서 정렬된다. 따라서 인덱스 내에서 컬럼의 순서가 상당히 중요하다.

 

 

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

인덱스의 정렬

인덱스를 생성하는 시점에 각 컬럼의 정렬을 내림차순 또는 오름차순으로 설정할 수 있다.

• 오름차순 인덱스: 작은 값의 인덱스 키가 B-Tree의 왼쪽으로 정렬된 인덱스
• 내림차순 인덱스: 큰 값의 인덱스 키가 B-Tree의 왼쪽으로 정렬된 인덱스
• 인덱스 정순 스캔: 인덱스 리프 노드의 왼쪽 페이지부터 오른쪽으로 스캔
• 인덱스 역순 스캔: 인덱스 리프 노드의 오른쪽 페이지부터 왼쪽으로 스캔

 

인덱스 정순 스캔이 역순 스캔보다 빠른 이유

• 페이지 잠금이 인덱스 정순 스캔에 적합한 구조
• 페이지 내에서 인덱스 레코드가 단방향으로만 연결된 구조

 

 

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

비교 조건의 종류와 효율성

• 작업 범위 결정 조건: 작업의 범위를 결정하는 조건
• 필터링 조건/체크 조건: 비교 작업의 범위를 줄이지 못하고 필터링 역할만 하는 조건

 

인덱스의 가용성

다중 컬럼 인덱스에서 LIKE '%word'와 같이 컬럼의 왼쪽 값을 모르면 인덱스 레인지 스캔을 사용할 수 없다.

다른 DBMS와 달리 MySQL에서는 NULL 값도 인덱스에 저장된다.

 

가용성과 효율성 판단

B-Tree 인덱스의 작업 범위 결정 조건으로 사용할 수 없는 경우

• NOT-EQUAL 비교
• LIKE '%??'와 같이 뒷부분 일치 문자열 패턴 비교
• 스토어드 함수나 연산자로 인덱스 컬럼이 변형된 후 비교
• NOT_DETERMINISTIC 속성의 스토어드 함수가 비교조건에 사용
• 데이터 타입이 서로 다른 비교
• 문자열 데이터 타입의 collation이 다른 경우

 

 

 

클러스터링 인덱스

---

비슷한 값들을 동시에 조회하는 경우가 많다는 점에 착안하여 테이블의 레코드를 비슷한 것들끼리 묶어서 저장하는 형태로 구현하는 것을 클러스터링이라고 한다. InnoDB 스토리지 엔진에서만 지원한다.

 

테이블의 프라이머리 키에 대해서만 적용된다. 즉 프라이머리 키값이 비슷한 레코드끼리 묶어서 저장하는 것을 클러스터링 인덱스라고 표현한다. 이는 프라이머리 키 값에 의해 물리적인 저장 위치가 바뀌어야 한다는 것을 의미한다. 따라서 인덱스 알고리즘이라기 보다 테이블 레코드의 저장 방식이라고 볼 수 있다. 클러스터링 인덱스는 프라이머리 키 기반의 검색이 매우 빠르며, 레코드 저장이나 프라이머리 키 변경이 상대적으로 느리다.

 

InnoDB 스토리지 엔진의 프라이머리 키 대체 컬럼 선택 과정

• 프라이머리 키가 있으면 프라이머리 키를 선택
• NOT NULL 옵션의 유니크 인덱스 중 첫번째 인덱스를 선택
• 자동으로 유니크한 값을 가지도록 증가되는 컬럼을 내부적으로 추가한 후 선택

 

세컨더리 인덱스에 미치는 영향

InnoDB는 클러스터링된 테이블을 사용하기 때문에 세컨더리 인덱스에 실제 레코드가 저장된 주소를 가지고 있다면 클러스터링 키 값이 변경될 때마다 레코드의 주소가 변경되어 모든 인덱스에 저장된 주소 값을 변경해야 할 것이다. 따라서 이러한 오버헤드를 줄이기 위해 세컨더리 인덱스에 실제 레코드의 주소가 아닌 프라이머리 키 값을 저장하도록 구현되어 있다.

 

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

장점

• 프라이머리 키로 검색할 때 처리 성능이 매우 빠름
• 세컨더리 인덱스가 프라이머리 키를 가지고 있기 때문에 인덱스만으로 처리될 수 있는 경우가 많음(커버링 인덱스)

단점

• 모든 세컨더리 인덱스가 클러스터링 키를 갖기 때문에 클러스터링 키 값이 크기가 클 경우 인덱스의 크기가 커짐
• 세컨더리 인덱스를 통해 검색할 때 프라이머리 키로 한번 더 검색해야 하므로 처리 성능이 느림
• INSERT할 때 프라이머리 키에 의해 레코드 저장 위치가 결정되기 때문에 처리 성능이 느림
• 프라이머리 키를 변경할 때 레코드를 DELETE하고 INSERT하는 작업이 필요하기 때문에 처리 성능이 느림

클러스터링 인덱스의 장점은 빠른 읽기(SELECT)이며, 단점은 느린 쓰기(INSERT, UPDATE, DELETE)라는 것을 알 수 있다. 일반적으로 웹 서비스와 같은 온라인 트랜잭션 환경에서는 쓰기와 읽기 비율이 2:8, 1:9 정도이기 때문에 빠른 읽기를 유지하는 것이 중요하다.

 

 

 

유니크 인덱스

---

디스크 읽기가 아닌 CPU에서의 컬럼 값 비교 작업이기 때문에 일반 세컨더리 인덱스와 성능 차이가 거의 없다.

유니크 인덱스의 키 값을 쓸 때는 중복된 값이 있는지 없는지 체크하는 과정이 한 단계 더 필요하기 때문에 일반 세컨더리 인덱스의 쓰기보다 느리다. 중복된 값을 체크할 때는 읽기 잠금을, 쓰기를 할 때는 쓰기 잠금을 사용한다. 일반 인덱스와 달리 중복 체크를 해야 하므로 일반 인덱스와 달리 버퍼링을 하지 못한다.