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

B-Tree 인덱스는 아래 요소들에 의해 검색이나 변경 작업 성능의 영향을 받는다.

인덱스를 구성하는 칼럼의 크기
레코드의 건수
유니크한 인덱스 키 값의 갯수 (카디널리티)

3.1 인덱스 키 값의 크기

InnoDB 스토리지 엔진은 디스크에 데이터를 Page 또는 Block 단위로 저장한다. 이들은 디스크의 모든 읽기 및 쓰기 작업과 버퍼 풀에서 데이터를 버퍼링하는 최소 작업 단위이다.
인덱스도 결국 Page 단위로 관리된다. 앞서, B-Tree의 노드를 보여줬는데, 자식 노드의 최대 갯수를 이 페이지 크기와 키 값의 크기로 결정한다. 페이지 크기의 기본값은 16KB이므로, 16KB인 상황을 상상해보자. 그리고 인덱스 키를 16 Byte라고 가정해보자. 그리고 키 외의 자식 노드 주소값의 저장 용량을 대략 6 ~ 12 Byte라고 가정하자.

그러면 산술적으로 16 * 2^10 / (16 + 12) = 585개의 데이터가 저장될 수 있다.
이제, 인덱스 키의 크기가 16 Byte에서 32 Byte가 되었다고 가정해보자. 16 * 2^10 / (32 + 12) = 372 개의 데이터가 저장된다.
그러니까, 인덱스 키의 크기와 한 페이지에 저장될 수 있는 레코드의 갯수가 반비례 하는 상황이다. 만약에 500개의 데이터를 원하는 상황이라면, 16Byte 때는 1번만에 전부 데이터를 찾을 수 있지만, 32Byte때는 2번이 걸리게 되는 것이다.

결론적으로 인덱스 키 값이 커지면 결국 디스크로 부터 읽어야 하는 횟수가 늘어나는 것이다. 이는 곧 느려진다는 것을 의미한다.

또한 키의 크기가 커지면 당연히 레코드의 크기도 커지기 때문에, 캐싱할 수 있는 레코드의 갯수가 줄어든다. 이 또한 속도를 느려지게 하는데에 영향을 준다.

3.2 B-Tree 깊이

트리 구조의 깊이는 당연히 탐색 시간에 큰 영향을 미친다. 편향 트리의 탐색 시간은 어떨까?
위 그림의 탐색을 생각해보자. 매 노드에서 어느 자식 노드로 갈지 검사하면서, 유일한 자식으로 계속 이동하는데, 모든 노드를 탐색하므로 선형 시간 O(N)이 걸린다. 그래서 밸런스를 맞추는 형태의 트리들은 Depth를 줄이는 것이 목표이다.

그러나, MySQL에서 트리 깊이를 직접 제어할 방도는 없다. 다만 인덱스 키 값이 커지게 되면 -> 하나의 인덱스 페이지가 담는 키 값의 갯수가 줄어들게 되므로 -> 노드가 늘어나고 -> Depth가 깊어진다.
따라서, 인덱스 키 값의 크기를 작게 하는 것은 매우 중요하다.

3.3 Cardinality는

기수성 - Cardinality는 선택도인 Selectivity와 거의 같은 이유로 사용된다. 모든 인덱스 키 값 가운데 유니크한 값의 수를 의미한다. 예를 들어 유저가 1억명일 때 , 예외를 제외하면 생물학적 성별은 단 2개 뿐이다. 이 때 기수성은 1억 / 2 = 5천만으로 계산할 수 있다. 반면 성별이 아닌 id 값으로 인덱싱을 걸었다고 생각해보자. 단일 Primary Key는 Unique하므로, 카디널리티는 1이다. 1억 / 1억 = 1
Cardinality는 그 값이 낮을 수록 좋다.
그 이유를 알기 위해 앞서 예시로 든 성별 인덱스 테이블을 상상해보자. 이 인덱스 테이블엔 오직 "여자들"과 "남자들"의 위치가 적혀 있을 것이다. 내가 남자이면서 id가 7인 사람을 찾고 싶을 때, 이 인덱스 테이블을 통해서 얻을 수 있는 이득은 거의 없다. 결국 남자 전체를 확인하므로, 검색 범위를 절반으로 밖에 못 줄인다. 1억명 중 남녀가 5천만명씩 있었다고 가정하면 탐색할 레코드를 겨우 5천만 밖에 못 줄이는 셈이다.
그러나, Unique한 Id 인덱스를 사용한다면, 인덱스만으로 유일한 한명을 색출해낼 수 있다. 불필요한 탐색 999,999,99을 줄이는 것이다. 그 한명을 B-Tree 검색으로 O(log_M(1억))만에 빠르게 찾아내니 얼마나 좋을까? -> 그래서 카디널리티가 높을 수록 인덱스가 그 힘을 발휘할 수 있다.

실제로 막 인덱싱 걸지 말고, DB에 적용 이후 용량을 확인해보면, 거의 인덱싱 테이블의 크기가 기존 테이블에 육박하거나 더 큰 것을 알 수 있다. 안 그래도 용량도 많이 차지하는데, 별로 효과도 없은 인덱싱을 거는 것은 너무 손해이기 때문에, 잘 고려하자. (이 논리를 쭉 갖고 있어야 다중 인덱싱 상황에서도 인덱싱 순서 판단이 용이하다)

3.4 읽어야 하는 레코드의 건수

인덱스를 거치는 것은 사실 탐색하기 전에 트리 구조를 한번 훑는 것이기 때문에, 바로 테이블을 탐색하는 것 보다 비용이 큰 작업이다. 인덱스를 거치지 않는게 나은 상황이 분명히 있고, 그 상황을 판단 해야 한다.
일반적인 DBMS 옵티마이저는 인덱스를 통해 레코드 1건을 읽는 것이, 바로 테이블을 읽는 것 보다 4~5배의 비용이 더 드는 작업으로 예측하기 때문에, 이것 보다는 이득이 있어야 한다.
옵티마이저는 인덱스를 통해 읽어야 할 데이터 건수를 예측하는데, 전체 테이블의 20 ~ 25%를 넘어서는 경우, 인덱스를 이용하지 않는 것이 이득이라고 판단하여 인덱스를 사용하지 않고, Full Table Scan을 실행한다.

4. B-Tree 인덱스를 통한 데이터 Read

일단 MySQL의 각 스토리지 엔진이 어떻게 인덱스를 이용해 레코드를 읽는지를 이해하고 있어야, B-Tree 인덱스를 사용하는 상황에 대해 제대로 고민할 수 있다.
이제 다양한 B-Tree 인덱스 읽기 방식을 알아보자.

4.1 Index Range Scan

인덱스 레인지 스캔은 검색할 인덱스의 범위가 결정됐을 떄 사용하는 가장 평범한 읽기 방식이다. 검색하려는 값의 수나 검색 결과 레코드 건수와 관계 없이 "레인지 스캔"이라고 표현하는데, 리프 노드를 필요한 범위 만큼 스캔한다.

위 그림은 실제 레코드 외에 인덱스 테이블만을 스캔하는 그림이다.
위 그림 처럼 스캔해야 할 범위의 시작점을 찾아낸 다음, 레코드를 순서대로 쭉~ 읽는다. (그래서 스캔이라고 표현한다.)

만약 스캔하다가 리프노드의 끝까지 읽으면, 리프노드간의 링크를 이용해 다음 리프 노드를 찾아 다시 스캔한다. (이 부분은 조금 헷갈린다. B-Tree에도 이런 링크가 있는걸까?)

최종적으로 데이터를 모두 찾아 스캔을 멈추면, 지금까지 읽은 레코드를 반환하고 쿼리를 종료한다.

인덱스에 의한 정렬

위 그림은 인덱스만을 탐색했다. 이번엔 실제 레코드까지 확인하는 경우도 살펴보자.

위 그림과 같이 인덱스가 정렬되어 있기 때문에, 실제 데이터가 정렬되어 있지 않아도 레코드를 정렬된 상태로 가져오게 된다! 이는 별도의 정렬 과정 없이 인덱스 자체의 특성 때문에 발생하는 정렬이다!(중요) 따라서, 마침 정렬이 필요했다면 인덱스만으로 따로 정렬하는 리소스가 줄어든다.

실제 레코드를 읽은 과정

위 그림에선 실제 레코드까지 읽는데, 이때 레코드 하나 하나마다 Random I/O가 발생한다! 그래서 인덱스를 통해 레코드를 읽는 비용이 결코 적지 않다고 설명했던 것이다.

만약에 테이블의 90%데이터를 읽어오라는 요청을 받았는데, 굳이 굳이 인덱스 테이블을 한번 거친다고 상상해보라!

이제 왜 오래 걸린다고 표현했는지 확실히 이해갈 것이다. 이러한 비용 문제 때문에, 앞에서도 언급했듯이 인덱스를 통해 읽어야 할 데이터 레코드가 20 ~ 25%를 넘으면 옵티마이저는 인덱스를 사용하지 않고 데이터를 읽어온다.

인덱스 레인지 스캔 3단계

결국 인덱스 레인지 스캔은 아래 3단계를 거친다.

Index Seek : 인덱스에서 조건을 만족하는 값이 저장된 위치를 찾아낸다. (인덱스 탐색)
Index Scan : 시작 위치를 탐색한 다음, 필요한 만큼 인덱스를 차례대로 쭉~~읽는다.
레코드 가져오기 : 읽어들인 인덱스 키와 레코드 주소를 통해 레코드가 저장된 페이지들을 가져온다! 그리고 최종 레코드들을 읽어온다.

MySQL은 이런 Seek과 Scan이 실행된 횟수나 레코드 건수를 확인할 수 있는 상태값을 제공해주는데. 아래와 같은 쿼리로 확인할 수 있다

SHOW STATUS LIKE 'Handler_%';

커버링 인덱스

만약, 인덱스만으로도 필요한 모든 정보를 파악할 수 있어, 3번 과정은 필요하지 않을 수도 있는데, 이를 커버링 인덱스라고 한다.
그냥 필요한 데이터가 모두 인덱싱 되어 있는 상황이다. 그렇다면 실제 레코드를 다녀오지 않아도 되지 않는가?

물론 필요한 컬럼이 많아 인덱스 테이블에 저장되는 컬럼이 늘어난다면, 용량은 어마어마하게 커질 수 있다. 그래서 데이터를 찾는 시간의 측면에서는 커버링 인덱스가 엄청나지만, 용량의 문제가 있기 때문에 치트키처럼 사용할 수는 없다.

4.2 Index Full Scan

인덱스를 사용하면서 인덱스의 처음 부터 끝까지 모두 읽는 방식을 Index Full Sacn이라고 부른다.

언제 인덱스를 전부 읽게 될까? 인덱스가 걸린 값의 모든 가능한 값으로 범위 검색을 하면 전부 읽게 될까?
아니다. 이 때는 풀 테이블 스캔을 하는 것이 나을 것이다.

인덱스 풀 스캔은 쿼리의 조건으로 사용된 칼럼이 인덱스의 첫 칼럼이 아닐 때 사용된다. 그러니까 인덱스가 (수업 id, 학생 id)로 걸려 있다고 가정했을 때, 학생 id로 쿼리가 날아오는 경우 풀 스캔이 사용될 수 있다. 뒤에서 배울 루스 인덱스 스캔, 스킵 스캔 등이 없을 때 풀 스캔 될 수 있다.

인덱스 풀 스캔은 인덱스 테이블만을 사용해 쿼리한다는 점에서는 나쁘지 않다. 보통 실제 테이블 보다는 당연히 크기가 작기 때문이다. 그렇다고 해서 썩 훌륭한 상황인 것도 아니다. 애초에 인덱스를 사용하는 목적은 인덱스를 통해 빠르게 데이터를 읽는 것인데, 전체를 읽고 있기 때문이다. 그래서 인덱스를 효율적으로 사용하고 있지 못한 상황이라고 할 수 있다.

4.3 Loose Index Scan

Loose Index Scan은 "느슨하게" 혹은 "듬성 듬성"하게 인덱스를 읽는 방식이다. (반대로 인덱스 레인지 스캔과 풀 스캔은 일종의 Tight Index Scan이라고 할 수 있다.)

Index Range Sacn과 비슷하게 작동하지만, 중간에 필요하지 않은 인덱스 키 값은 무시하고 다음으로 넘어간다!
일반적으로 GROUP BY나 집합 함수들에 대한 최적화를 하는 경우에 사용되는데, 실제로 사용되는 상황은 까다롭다.

예를 들어 아래 쿼리를 보자

SELECT id, MIN(student_id)
FROM lectures
WHERE id BETWEEN '10' AND '15'
GROUP BY id

위 쿼리는 강의들의 id별로 가장 숫자가 낮은 학생 id를 그룹화 하고 있다. 그리고 lectures 테이블은 (id, student_id) 조합으로 인덱싱이 있고 정렬까지 되어 있다고 가정하자. 이 때, 아래 그림을 참고해서 생각해보자.

student_id의 최솟값만 알면 되는 상황인데, 사실 id별로 가장 위의 레코드만 읽으면 되지 않겠는가? 그 student_id가 id별로 정렬된 student_id의 최소값인 것은 확실하기 때문이다.

이 경우 옵티마이저는 id별로 student_id 전체를 읽을 필요가 없다는 것을 알게되고, 첫 값만 읽고 다음 id로 향한다! 즉, "듬성 듬성" 읽게 되는 것이다!

이러한 루스 인덱스 스캔은 보다 싶이 몇몇 상황에서만 사용 가능하다. 옵티마이저는 여러 조건을 만족할 때만 이를 활용한다!

TODO : 실행 계획 공부 뒤에 루스 인덱스 스캔 제약조건 추가

4.4 인덱스 칼럼 순서의 중요성과..
- Index Skip Scan

Index Skip Scan은 MySQL 8.0에 도입된 기능으로, 다중 컬럼 인덱스에서 앞에 위치한 컬럼을 건너뛸 수 있게 해준다.

예를 들어 회원 테이블을 (gender, birth_date)로 인덱스를 생성했다고 생각해보자. 옛날에는 이 인덱스를 효율적으로 사용하려면 gender 칼럼에 대한 비교 조건이 필요했다.아래와 같은 쿼리로는 인덱스를 효율적으로 사용할 수 없었다.

SELECT *
FROM members
WHERE birth_date >= '1996-05-06';

위와 같은 쿼리는 gender에 대한 비교가 없으므로, 인덱스를 사용하지 않거나, 인덱스 풀 스캔을 유도했다.
인덱스를 효율적으로 사용하려면 아래와 같이 gender 조건이 추가 되어야 했다. (혹은 birth_date로 인덱스를 추가 생성해야 했다..)

SELECT *
FROM members
WHERE gender = 'M' AND birth_date >= '1996-05-06';

Index Skip Scan 등장

MySQL 8.0에 추가된 index Skip Scan은 gender 조건을 뛰어 넘을 수 있게 해준다. (실행조건 Extra 에서 Using Index for skip scan으로 나타남)

위 그림과 같이 진행되는데, MySQL 옵티마이저는 gender 칼럼에서 유니크한 값을 모두 쿼리에 추가하는 형태로 처리한다! 사실상 앞서 보인 birth_date만 활용한 쿼리를 호출하면, 아래와 같은 2개의 쿼리를 실행하는 것과 비슷한 효과를 낸다.

SELECT *
FROM members
WHERE gender = 'M' AND birth_date >= '1996-05-06';
 
SELECT *
FROM members
WHERE gender = 'F' AND birth_date >= '1996-05-06';

참 편리하다. 그리고 그림을 잘 보면, 인덱스는 gender가 같으면 birth_date로 정렬되어 있기 때문에 유니크한 성별별로 깔끔하게 레인지 스캔을 한다.

단점

건너뛸 칼럼의 유니크한 값의 갯수가 적어야 한다
커버링 인덱스가 아니면 선택되지 않는다. -> 인덱스에 존재하는 칼럼만으로 쿼리의 처리 가능해야 한다.

건너뛸 칼럼의 유니크한 값의 갯수가 많다면 (카디널리티가 높다면) 스캔의 시작점을 탐색하는 작업이 많이 필요해지고, 오히려 성능이 더 느려질 수 있다.

4.5 다중 칼럼 인덱스

두 개 이상의 칼럼으로 구성된 인덱스를 다중 컬럼 인덱스, 혹은 복합 칼럼 인덱스라고 부른다.

다중 칼럼 인덱스는 앞 컬럼에 의존해 정렬되어 있다. 예를 들어 (A, B, C)로 인덱스를 만들었다면, 기본적으로 A 값으로 인덱스가 정렬되어 있고, A가 같은 경우에는 그 안에서 B로 정렬되어 있다. 똑같이 B가 같은 값들에 대해 C가 정렬되어 있을 것이다.

따라서, 인덱스 순서는 매우 중요하다! 카디널리티가 낮은 값과 검색이 잘 되는 값이 앞으로 나와 있어야, 불필요한 탐색을 최대한 줄일 수가 있을 것이다. 아주 신중하게 결정해야 한다.