MySQL B-Tree 인덱스 [2/2]

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

---

 

◎ 인덱스 레인지 스캔

---

• 인덱스 접근 방법 중 가장 대표적인 방법으로 가장 빠른 방법
• 인덱스를 통해 레코드를 한 건만 읽는 경우와 한 건 이상을 읽는 경우를 각각 다른 이름으로 구분하지만 모두 "인덱스 레인지 스캔"이라 표현인덱스 레인지 스캔은 검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식이다.

 

인덱스를 이용한 레인지 스캔

 

 

• 검색하려는 값의 수나 검색 결과 레코드 건수와 관계없이 레인지 스캔이라고 표현한다.
• 위 그림에서 알 수 있듯 루트 노드에서부터 비교를 시작해 브랜치 노드를 거치고 최종적으로 리프 노드까지 찾아 들어가야만 비로소 필요한 레코드의 시작 지점을 찾을 수 있다.
• 일단 시작해야 할 위치를 찾으면 그때부터는 리프 노드의 레코드만 순서대로 읽으면 된다.
• 만약 스캔하다가 리프 노드의 끝까지 읽으면 리프 노드 간의 링크를 이용해 다음 리프 노드를 찾아서 다시 스캔한다. 그리고 최종적으로 스캔을 멈춰야 할 위치에 다다르면 지금까지 읽은 레코드를 사용자에게 반환하고 쿼리를 끝낸다.

 

인덱스 레인지 스캔을 통한 데이터 레코드 읽기

 

• B-Tree 인덱스에서 루트와 브랜치 노드를 이용해 스캔 시작 위치를 검색하고, 그 지점부터 필요한 방향(오름차순 또는 내림차순)으로 인덱스를 읽어나가는 과정을 위 그림에서 볼 수 있다.
• 중요한 것은 어떤 방식으로 스캔하든 관계없이, 해당 인덱스를 구성하는 칼럼의 정순 또는 역순으로 정렬된 상태로 레코드를 가져온다는 것이다.
• 또 한 가지 중요한 것은 인덱스의 리프 노드에서 검색 조건에 일치하는 건들은 데이터 파일에서 레코드를 읽어오는 과정이 필요하다는 것이다. 이 때 리프 노드에 저장된 레코드 주소로 데이터 파일의 레코드를 읽어오는데, 레코드 한 건 한 건 단위로 랜덤 I/O가 한 번씩 일어난다.
• 위 그림처럼 3건의 레코드가 검색 조건에 일치했다고 가정하면, 데이터 레코드를 읽기 위해 랜덤 I/O가 최대 3번 필요한 것이다. 그래서 인덱스를 통해 데이터 레코드를 읽는 작업은 비용이 많이 드는 작업으로 분류된다.

 

 

인덱스 레인지 스캔은 다음과 같이 크게 3간계를 거친다는 점을 살펴봤다.

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

쿼리가 필요로 하는 데이터에 따라 3번 과정은 필요하지 않을 수도 있는데, 이를 커버링 인덱스라고 한다. 커버링 인덱스로 처리되는 쿼리는 디스크의 레코드를 읽지 않아도 되기 때문에 랜덤 읽기가 상당히 줄어들고 성능은 그만큼 빨라진다.

 

 

 

 

 

 

◎ 인덱스 풀 스캔

---

• 인덱스 레인지 스캔과 마찬가지로 인덱스를 사용하지만 인덱스 레인지 스캔과는 달리 인덱스의 처음부터 끝까지 모두 읽는 방식을 인덱스 풀 스캔이라고 한다.
• 대표적으로 쿼리의 조건절에 사용된 칼럼이 인덱스의 첫 번째 칼럼이 아닌 경우 인덱스 풀 스캔 방식이 사용된다. 예를 들어, 인덱스는 (A, B, C) 칼럼의 순서로 만들어져 있지만 쿼리의 조건절은 B 칼럼이나 C 칼럼으로 검색하는 경우다.
• 일반적으로 인덱스의 크기는 테이블의 크기보다 작으므로 직접 테이블을 처음부터 끝까지 읽는 것보다는 인덱스만 읽는 것이 효율적이다. 쿼리가 인덱스에 명시된 칼럼만으로 조건을 처리할 수 있는 경우 주로 이 방식이 사용된다.
• 인덱스 뿐만 아니라 데이터 레코드까지 모두 읽어야 한다면 절대 이 방식으로 처리되지 않는다.

 

인덱스 풀 스캔

 

• 인덱스 리프 노드의 제일 앞 또는 제일 뒤로 이동한 후, 인덱스의 리프 노드를 연결하는 링크드 리스트를 따라서 처음부터 끝까지 스캔하는 방식을 인덱스 풀 스캔이라고 한다. 이 방식은 인덱스 레인지 스캔보다는 빠르지 않지만 테이블 풀 스캔보다는 효율적이다.
• 인덱스에 포함된 칼럼만으로 쿼리를 처리할 수 있는 경우 테이블의 레코드를 읽을 필요가 없기 때문이다. 인덱스의 전체 크기는 테이블 자체의 크기보다는 훨씬 작으므로 인덱스 풀 스캔은 테이블 전체를 읽는 것보다는 적은 디스크 I/O로 쿼리를 처리할 수 있다.

 

 

 

 

◎ 루스 인덱스 스캔

---

MySQL 5.7 버전까지는 MySQL의 루스 인덱스 스캔 기능이 많이 제한적이었지만, NySQL 8.0 버전부터는 다른 상용 DBMS에서 지원하는 인덱스 스킵 스캔과 같은 최적화를 조금씩 지원하기 시작했다. 앞에서 소개한 두 가지 접근 방법은 "루스 인덱스 스캔"과는 상반된 의미에서 "타이트(Tight) 인덱스 스캔"으로 분류한다.

 

루스 인덱스 스캔이란 말 그대로 느슨하게 또는 듬성듬성하게 인덱스를 읽는 것을 의미한다.

 

 

 

• 루스 인덱스 스캔은 인덱스 레인지 스캔과 비슷하게 작동하지만 중간에 필요치 않은 인덱스 키 값은 무시(SKIP)하고 다음으로 넘어가는 형태로 처리한다. 
• 일반적으로 GROUP BY 또는 집합 함수 가운데 MAX() 또는 MIN() 함수에 대해 최적화를 하는 경우에 사용된다.

 

mysql> SELECT dept_no, MIN(emp_no)
       FROM dept_emp
       WHERE dep_no BETWEEN 'd002' AND 'd004'
       GROUP BY dept_no;

 

 

 

 

 

◎ 인덱스 스킵 스캔

---

지금까지 위에서 본 인덱스는 모두 1개의 칼럼만 포함되었다. 하지만 실제 서비스용 데이터베이스에서는 2개 이상의 칼럼을 포함하는 인덱스가 더 많이 사용된다. 두 개 이상의 칼럼으로 구성된 인덱스를 다중 칼럼 인덱스(또는 복합 칼럼 인덱스)라고 하며, 또한 2개 이상의 칼럼이 연결됐다고 해서 "Concatenated Index"라고도 한다.

 

 

 

다중 칼럼 인덱스

 

 

• 위는 브랜치 노드와 리프 노드지만 브랜치 노드는 없을 수도 있으며 루트 노드와 리프 노드는 항상 존재한다.
• 위 그림은 다중 칼럼 인덱스 일 때 각 인덱스를 구성하는 칼럼의 값이 어떻게 정렬되어 저장되는지 설명해준다. 이 그림에서 중요한 것은 인덱스의 두 번째 칼럼은 첫 번째 칼럼에 의존해서 정렬돼 있다는 것이다.
• 즉, 두 번째 칼럼의 정렬은 첫 번째 칼럼이 똑같은 레코드에서만 의미가 있다는 것

 

 

 

 

 

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

---

인덱스를 생성할 때 설정한 정렬 규칙에 따라서 인덱스의 키 값은 항상 오름차순이거나 내림차순으로 정렬되어 저장한다.

인덱스를 어느 방향으로 읽을지는 쿼리에 따라 옵티마이저가 실시간으로 만들어내는 실행 계획에 따라 결정된다.

 

 

 

 

◎ 인덱스 스캔 방향

---

first_name 칼럼에 대한 인덱스가 포함된 employees 테이블에 대해 다음 쿼리를 실행하는 과정을 한 번 살펴보자.

MySQL은 이 쿼리를 실행하기 위해 인덱스를 처음부터 오름차순으로 끝까지 읽어 first_name이 가장 큰 값 하나를 가져오는 것일까?

 

mysql> SELECT *
       FROM employees
       ORDER BY first_name DESC
       LIMIT 1;

 

그렇지 않다. 인덱스는 항상 오름차순으로만 정렬돼 있지만 인덱스를 최솟값부터 읽으면 오름차순으로 값을 가져올 수 있고, 최대값부터 거꾸로 읽으면 내림차순으로 값을 가져올 수 있다는 것을 MySQL 옵티마이저는 이미 알고 있다.

 

인덱스의 오름차순(ASC)과 내림차순(DESC) 읽기

 

즉, 인덱스 생성 시점에 오름차순 또는 내림차순으로 정렬이 결정되지만 쿼리가 그 인덱스를 사용하는 시점에 인덱스를 읽는 방향에 따라 오름차순 또는 내림차순 정렬 효과를 얻을 수 있다. 오름차순으로 생성된 인덱스를 정순으로 읽으면 출력되는 결과 레코드는 자동으로 오름차순으로 정렬된 결과가 되고, 역순으로 읽으면 그 결과는 내림차순으로 정렬된 상태가 되는 것이다.

 

 

 

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

mysql> SELECT * FROM employees
       ORDER BY first_name LIMIT 5;

 

 

위의 첫 번째 쿼리는 first_name 칼럼에 정의된 인덱스를 이용해 "Anneke"라는 레코드를 찾은 후, 정순으로 해당 인덱스를 읽으면서 4개의 레코드만 가져오면 아무런 비용을 들이지 않고도 원하는 정렬 효과를 얻을 수 있다.

 

두 번째 쿼리는 이와 반대로 employees 테이블의 first_name 칼럼에 정의된 인덱스를 역순으로 읽으면서 처음 다섯 개의 레코드만 가져오면 된다.

 

 

 

 

 

 

◎ 내림차순 인덱스

---

MySQL 서버에서 두 쿼리는 실제 내림차순인지 오름차순인지와 관계없이 인덱스를 읽는 순서만 변경해서 해결할 수 있다는 것을 살펴봤다.

 

 

mysql> CREATE INDEX ix_firstname_asc ON employees (first_name ASC);
mysql> CREATE INDEX ix_firstname_desc ON employees (first_name DESC);

 

first_name 칼럼을 역순으로 정렬하는 요건만 있다면 다음 2개 인덱스 중에서 어떤 값을 선택하는 것이 좋을까?

이 궁금증에 대한 답을 찾기 위해 MySQL 8.0부터 지원되는 내림차순 인덱스에 대해 조금 깊이 있게 이해해야 한다.

 

 

 

인덱스 정순(포워드) 스캔과 인덱스 역순(백워드) 스캔

 

• 오름차순 인덱스(Ascending index) : 작은 값의 인덱스 키가 B-Tree의 왼쪽으로 정렬된 인덱스
• 내림차순 인덱스(Descending index) : 큰 값으 인덱스 키가 B-Tree의 왼쪽으로 정렬된 인덱스
• 인덱스 정순 스캔(Forward index scan) : 인덱스 키의 크고 작음에 관계없이 인덱스 리프 노드의 왼쪽 페이지부터 오른쪽으로 스캔
• 인덱스 역순 스캔(Backward index scan) : 인덱스 키의 크고 작음에 관계없이 인덱스 리프 노드의 오른쪽 페이지부터 왼쪽으로 스캔

역순 또는 정순으로 테이블을 풀 스캔하면서 레코드 1건을 반환하는 쿼리문을 작성하여 비율로 비교하면 역순 정렬 쿼리가 28.9% 더 시간이 걸리는 것을 확인할 수 있다. 

 

MySQL 서버의 InnoDB 스토리지 엔진에서 정순 스캔가 역순 스캔은 페이지(블록) 간의 양방향 연결 고리(Double linked list)를 통해 전진(Forward)하느냐 후진(Backward)하느냐의 차이만 있지만, 실제 내부적으로는 InnoDB에서 인덱스 역순 스캔이 인덱스 정순 스캔에 비해 느릴 수 밖에 없는 두 가지 이유가 있다.

 

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

위 그림을 보면 InnoDB 페이지 내부에서 레코드들이 정렬 순서대로 저장돼 있는 것처럼 표시돼 있지만 실제로 InnoDB 페이지는 힙(Heap)처럼 사용되기 때문에 물리적으로 저장이 순서대로 배치되지는 않는다.

그리고 각 데이터 페이지(InnoDB 스토리지 엔진에서 데이터 파일은 프라이머리 키 인덱스 자체라는 것에 주의)나 인덱스 페이지의 엔트리(데이터 레코드 또는 인덱스 키)는 키 값과 데이터를 자주 가지는데, 인덱스(프라이머리 키 인덱스와 세컨더리 인덱스 모두)의 루트 노드 또는 브랜치 노드라면 자식 노드의 주소를 가진다.

 

프라이머리 키에서 리프 노드의 "데이터"는 실제 레코드의 칼럼 값들이며, 세컨더리 인덱스 페이지에서는 프라이머리 키 값을 가진다.