[MySQL] B-Tree 인덱스 - 3

이전 글에 이어서 MySQL의 B-Tree 인덱스에 대해 알아보겠습니다.

[MySQL] B-Tree 인덱스 - 1

[MySQL] B-Tree 인덱스 - 2

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

인덱스는 인덱스의 키 값으로 항상 오름차순이나 내림차순으로 정렬되어 있습니다. 인덱스가 오름차순으로 정렬되어 있더라도 인덱스를 거꾸로 읽으면 내림차순으로 인덱스를 읽을 수 있습니다. 인덱스를 어느 방향으로 읽을지는 옵티마이저가 결정합니다.

인덱스 스캔 방향

first_name 칼럼에 대한 인덱스가 포함된 employees 테이블에 다음 쿼리를 실행한다 가정해봅시다.

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

만약 정순으로 인덱스를 읽는다면 인덱스의 처음부터 마지막까지 오름차순으로 스캔을 할 것입니다. 하지만 인덱스 스캔 방향은 역순도 가능합니다. 따라서 모든 인덱스를 읽고 마지막 인덱스의 레코드를 반환하는 것이 아닌, 역순 스캔을 통해 마지막 인덱스의 레코드를 반환합니다. 즉, 인덱스 생성 시점에 오름차순 또는 내림차순으로 정렬이 결정되지만 쿼리가 인덱스를 사용하는 시점에 인덱스를 읽는 방향에 따라 오름차순, 내림차순을 모두 이용할 수 있습니다.

내림차순 인덱스

MySQL 5.7 버전까지는 다음과 같이 칼럼 단위로 오름차순, 내림차순을 혼합하여 인덱스를 만들 수 없었습니다.

mysql> CREATE INDEX ix_teamname_userscore ON employees (team_name ASC, user_score DESC);

MySQL 8.0 버전부터는 가능하도록 변경되었습니다. 8.0 이전 버전에서는 에러 없이 동작하지만 DESC는 무시됩니다. 'parsed but ignored'

 

내림차순 인덱스가 없더라도 인덱스의 스캔 방향만 바꾸면 내림차순 인덱스가 필요 없어보입니다. 하지만 InnoDB 내부에서 인덱스 역순 스캔은 정순 스캔에 비해 느립니다. 이유는 다음과 같습니다.

 

1. 페이지 잠금이 인덱스 정순 스캔에 적합한 구조

2. 페이지 내에서 인덱스 레코드가 단방향으로만 연결된 구조

 

InnoDB의 페이지 잠금 방식은 인덱스 정순 스캔을 중심으로 구현되어 있습니다. 페이지의 잠금을 획득할 때 정순으로 페이지를 잠그고 해제합니다. 하지만 인덱스 역순 스캔은 조금 복잡한 과정을 거칩니다. 자세한 내용은 카카오 테크 블로그에 있습니다. 요약하자면 InnoDB의 B-Tree 리프 페이지는 Double Linked List로 연결되어 있지만, 데드락을 방지하기 위해 왼쪽에서 오른쪽(정순)으로만 잠금을 획득하도록 구현돼있습니다. 그래서 이전 페이지의 잠금을 획득하는 과정이 복잡합니다.

 

B-Tree 인덱스는 페이지 단위로 정렬되어 있습니다. 검색 대상 레코드가 저장된 페이지까지 검색은 할 수 있지만 그 페이지 내에도 수많은 레코드가 저장되어 있습니다. 이 레코드들은 인덱스와 달리 Single Linked List로 연결되어 있습니다. 레코드의 순서는 인덱스의 생성 시점의 정렬에 따라 다른 정렬 순서를 갖게 됩니다. 이는 인덱스의 정렬 순서와 반대되는 레코드 검색 시 성능에 악영향을 줄 수 있음을 의미합니다.

[출처]https://blog.jcole.us/2013/01/14/efficiently-traversing-innodb-btrees-with-the-page-directory/

내림 차순 인덱스를 사용했을 때의 성능을 비교해 보겠습니다. 8.0 버전과 5.7 버전에서 다음과 같은 인덱스를 생성합니다.

mysql> CREATE INDEX a_desc_b_asc (a DESC, b ASC);

8.0에서는 원하는 인덱스가 생성됐지만 5.7에서는 (a ASC, b ASC)로 인덱스가 생성됐습니다.

다음 표는 내림차순 인덱스를 지원하지 않는 5.7 버전과 반대인 8.0 버전의 쿼리를 비교한 표입니다.

[출처]https://dev.mysql.com/blog-archive/mysql-8-0-labs-descending-indexes-in-mysql/

Q1) 8.0에서 a 칼럼에 대해 내림차순 인덱스가 존재하므로 인덱스 정순 스캔과 역순 스캔의 차이만큼 성능이 개선됐습니다.

Q2) 8.0에서 인덱스 역순 스캔을 진행합니다. 역순 스캔을 진행했기 때문에 Q1보다 조금 느린걸 알 수 있습니다.(8.0 버전에서 내림차순 인덱스의 역순 스캔은 5.7 버전의 오름차순 인덱스의 정순 스캔과 비슷한 성능을 낸다고 합니다.)

Q3) 8.0에서 인덱스와 동일한 순서로 레코드를 읽기때문에 가장 빠릅니다. 5.7에서는 혼합 순서를 요청하는 쿼리인 경우 file sort에 의존하기 때문에 그 차이가 큽니다.

Q4) 8.0에서 인덱스를 역순으로 읽기 때문에 Q3보다 조금 느립니다. 5.7에서는 인덱스를 통해 만족하는 정렬을 얻을 수 없기 때문에 느립니다.

Q5, 6) 8.0에서 인덱스를 역순, 정순으로 읽어도 원하는 정렬을 얻을 수 없습니다. 그래서 file sort를 사용하기 때문에 느립니다. Q5, 6에 대해 file sort를 피하고 싶다면 (a ASC, b ASC)를 추가할 수 있습니다. 또한 역순 스캔을 피하고 싶다면 (a ASC, b DESC), (a DESC, b DESC)를 추가할 수 있습니다.

 

인덱스가 추가된 최종 비교입니다.

[출처]https://dev.mysql.com/blog-archive/mysql-8-0-labs-descending-indexes-in-mysql/

참고

 

MySQL Ascending index vs Descending index

MySQL :: MySQL 8.0 Labs - Descending Indexes in MySQL