Ascending index vs Descending index

 

 

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

Descending index 지원

- Mysql 8.0 에서 부터 지원한다.

- MariaDB 는 10.11 에서 부터 지원하는 듯?  https://mariadb.com/kb/en/descending-indexes/

Descending index , Ascending index 성능차이 Test

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

INSERT INTO t1 SELECT NULL, TABLE_NAME, COLUMN_NAME, ORDINAL_POSITION FROM information_schema.COLUMNS;
INSERT INTO t1 SELECT NULL, TABLE_NAME, COLUMN_NAME, ORDINAL_POSITION FROM t1; 

select count(1) from testdb.t1; 
14,995,200



SELECT * FROM t1 ORDER BY tid ASC  LIMIT 14994199, 1;  ##Forward scan
SELECT * FROM t1 ORDER BY tid desc  LIMIT 14994199, 1;  ##Backward scan

## 하지만 limit ~ offset 쿼리로 인해서 테이블의 모든 레코드를 full scan 해야한다.

동일하게 6번 수행 결과

 - Ascending Index 평균 3.6 sec

 - Descending Index 평균 5.3 sec

 

Backward index scan이 느린 이유 2가지

1. 페이지 잠금이 Forward index scan에 적합한 구조

 

- InnoDB 스토리지 엔진에서는 페이지 잠금 과정에서 데드락을 방지하기 위해서 B-Tree의 왼쪽에서 오른쪽 순서(Forward)로만 잠금을 획득하도록 하고 있다. 그래서 Forward index scan에서는 다음 페이지 잠금 획득이 매우 간단하지만, Backward index scan에서 이전 페이지 잠금을 획득하는 과정은 상당히 복잡한 과정을 거치게 된다.

 

2. 페이지 내에서 인덱스 레코드는 단방향으로만 연결된 구조 (Forwarded single linked link)

 

Ascending vs Descending index의 선택 기준

일반적으로 인덱스를 ORDER BY ... DESC하는 쿼리가 소량의 레코드를 드물게 실행되는 경우라면, Descending index를 굳이 고려할 필요는 없어 보인다.

또한 많은 쿼리가 인덱스의 앞쪽만 또는 뒤쪽만 집중적으로 읽어서 인덱스의 특정 페이지 잠금이 병목 지점이 될 것으로 예상된다면, 적절히 Descending index를 생성하는 것이 경합 감소에 도움이 될 것으로 보인다.

 

 

 

 

 

 

 

 

출처:

https://tech.kakao.com/2018/06/19/mysql-ascending-index-vs-descending-index/