[47번] 내림차순 인덱스

#47

문제

다음 t1 데이터 테이블이 있다.

CREATE TABLE t1
(
    tid              INT NOT NULL AUTO_INCREMENT,
    TABLE_NAME       VARCHAR(64),
    COLUMN_NAME      VARCHAR(64),
    ORDINAL_POSITION INT,
    PRIMARY KEY (tid)
)ENGINE=InnoDB;

 

다음과 같이 내림차순으로 tid와 COLUMN_NAME을 탐색하는 쿼리가 있다.

SELECT tid, column_name FROM t1 ORDER BY COLUMN_NAME DESC LIMIT 11862915, 1

 

오름차순 인덱스와 내림차순 인덱스가 있을 때 각 인덱스 활용 시나리오의 효율을 비교하시오.

CREATE INDEX column_name_asc on t1(column_name ASC);
CREATE INDEX column_name_desc on t1(column_name DESC);

선지

A. 오름차순 인덱스(column_name_asc)를 활용하는 것이 더 빠르다

B. 내림차순 인덱스(column_name_desc)를 활용하는 것이 더 빠르다

C. 두 인덱스 활용 속도에 큰 차이가 없다.

정답

A. 오름차순 인덱스(column_name_asc)를 활용하는 것이 더 빠르다

B. 내림차순 인덱스(column_name_desc)를 활용하는 것이 더 빠르다

C. 두 인덱스 활용 속도에 큰 차이가 없다.

 

핵심 해설

 

MySQL 인덱스는 다음 2가지 이유로 인해 정순 스캔에 최적화되어 있습니다.

이유1) 페이지 잠금이 인덱스 정순 스캔에 더 적합한 구조입니다.

이유2) 페이지 내의 인덱스 레코드는 단방향으로만 연결된 구조입니다.

 

그렇기에 내림차순 쿼리에 대해서는 정순 스캔으로 인덱스 탐색이 가능한 내림차순 인덱스의 탐색 속도가 훨씬 빠릅니다.

MySQL은 8.0버전부터 내림차순 인덱스 생성을 지원해주고 있습니다.

 

상세 해설

용어 정리

먼저 공식 용어가 아닌 만큼 몇가지 용어를 집고 넘어가겠습니다.

 

오름차순 인덱스 : 작은 값의 인덱스 키가 B-Tree 왼쪽으로 정렬된 인덱스

내림차순 인덱스 : 큰값의 인덱스 키가 B-Tree 왼쪽으로 정렬된 인덱스

정순 인덱스 스캔 : 인덱스 리프노드의 왼쪽 페이지 부터 오른쪽으로 스캔하는 것

역순 인덱스 스캔 : 인덱스 리프노드의 오른쪽 페이지

부터 왼쪽으로 스캔하는 것

 

MySQL은 정순스캔이 역순스캔보다 빠르다

 

이유1) 페이지 잠금이 정순스캔에 최적화된 구조이기 때문

• InnoDB는 페이지 잠금 과정에서 데드락 방지를 위해 왼쪽 > 오른쪽으로만 잠금 획득
• 역순 스캔은 이전 페이지를 거슬러 올라가 잠금을 획득해야하므로 그 과정이 상대적으로 복잡

이유2) 페이지 내의 인덱스 레코드는 단방향만으로 연결

• InnoDB는 탐색하는 레코드가 포함된 페이지를 특정하기 위해 순차정렬된 레코드 4-8개 정도를 묶어 대표키를 선정
• 페이지 디렉토리(대표키만 모아놓은 리스트)를 통해 이분탐색으로 검색 대상 키가 포함된 대표키를 검색
• B-Tree 리프페이지는 양방향이지만 내부 레코드는 단방향으로 연결되어 있음

그렇기 때문에 내림차순 쿼리에서는 인덱스 정순 스캔을 할 수 있는 내림차순 인덱스가 훨씬 효율적입니다.

 

실습으로 알아보기

실제로 각 인덱스 활용 시나리오에 있어 실행시간을 EXPLAIN ANALYZE를 통해 실습해보겠습니다.

 

오름차순 인덱스 활용 쿼리 : 1s 912ms

EXPLAIN ANALYZE  SELECT tid, column_name FROM t1 ORDER BY COLUMN_NAME DESC LIMIT 11862915, 1
1 row retrieved starting from 1 in 2 s 123 ms (execution: 1 s 912 ms, fetching: 211 ms)

-> Limit/Offset: 1/11862915 row(s)  (cost=304004 rows=0) (actual time=1903..1903 rows=1 loops=1)
    -> Covering index scan on t1 using column_idx_asc (reverse)  (cost=304004 rows=2.52e+6) (actual time=0.625..1695 rows=11.9e+6 loops=1)

 

 

내림 차순 인덱스 활용쿼리 : 1s 267ms

EXPLAIN ANALYZE  SELECT tid, column_name FROM t1 ORDER BY COLUMN_NAME DESC LIMIT 11862915, 1
1 row retrieved starting from 1 in 1 s 434 ms (execution: 1 s 267 ms, fetching: 167 ms)

-> Limit/Offset: 1/11862915 row(s)  (cost=304004 rows=0) (actual time=1258..1258 rows=1 loops=1)
    -> Covering index scan on t1 using column_name_desc  (cost=304004 rows=2.52e+6) (actual time=0.0771..1050 rows=11.9e+6 loops=1)

 

내림차순 쿼리에 대하여 오름차순 인덱스보다 내림차순 인덱스를 활용한 정순 스캔하는 것이 훨씬 효율적임을 알 수 있습니다.