B-Tree index의 정렬 및 스캔 방향

인덱스를 생성할 때 설정한 정렬 규칙에 의해 인덱스의 키 값은 오름차순 혹은 내림차순으로 정렬되어 저장된다.

but 어떤 인덱스가 오름차순으로 생성됐다고 해서 오름차순으로만 읽을 수 있는 의미는 아니다. 오름차순 인덱스를 반대로 읽으면 내림차순으로도 사용될 수 있다.

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

인덱스의 정렬

인덱스를 생성하는 시점에서 각 컬럼의 정렬을 오름차순/내림차순으로 설정할 수 있다. MySQL 5.7 버전까지는 컬럼 단위로 정렬 순서를 혼합(ASC, DESC)해서 생성할 수 없었다.

하지만 8.0 버전부터는 아래와 같은 형태의 정렬 순서를 혼합한 인덱스 생성도 가능해졌다.

create index ix_teamname_userscore
on employees (team_name asc, user_score desc);

인덱스 스캔 방향

select * from employees
order by first_name desc
limit 1;

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

아니다. 인덱스는 오름차순으로 정렬되어 있어도 최솟값부터 읽으면 오름차순으로 가져오고, 최댓값부터 읽으면 내림차순으로 값을 가져올 수 있다. 이는 MySQL 옵티마이저가 결정한다.

즉, 인덱스 생성 시점에 오름/내림차순으로 정렬이 결정되지만 인덱스를 어떻게 사용하는지는 쿼리에 따라 달라지며 읽는 방향에 따라서 오름차순 또는 내림차순 정렬 효과를 볼 수 있다.

select * from employees
where first_name >= 'anneke'
order by first_name asc
limit 4;

select * from employees
order by first_name desc
limit 5;

첫 번째 쿼리는 ‘annke’를 찾은 후, 정순으로 읽어서 추가 비용 없이 원하는 정렬 효과를 얻을 수 있다.

두 번째 쿼리는 인덱스 테이블이 오름차순으로 정렬되어 있지만 desc를 한다고 인덱스의 정렬 방식이 변경되지는 않는다. order by절에 내림차순으로 데이터를 요청하면 역순 스캔 방향으로 반환할 수 있다.

MySQL 옵티마이저는 인덱스의 읽기 방향을 전환해서 사용하도록 실행 계획을 만들어 낸다.

내림차순 인덱스

2개 이상의 칼럼이 내림차순, 오름차순을 동시에 사용하는 쿼리를 위해서는, 각 컬럼이 오름차순, 내림차순으로 정의된 복합 컬럼 인덱스가 필요하다.

다음과 같이 team_name은 정순으로 정렬 후, user_score 컬럼은 역순으로 정렬하는 쿼리를 보자.

select * from emplyees
order by team_name asc, user_score desc
limit 10

// 옳지 않은 튜닝
create index ~ (team_name asc, user_socre asc)

쿼리에서 정렬 작업이 인덱스를 사용하도록 튜닝하기 위해서 (team_name asc, user_socre asc)로 튜닝한다면 아무 도움이 되지 않는다. 이 경우에는 MySQL 8.0에서 도입된 내림차순 인덱스로만 튜닝 될 수 있다.

즉, 2개 이상의 컬럼으로 구성된 복합 인덱스에서, 각 컬럼이 내림차순과 오름차순이 혼합된 경우 내림차순 인덱스로만 해결할 수 있다. (해결 = 인덱스를 통한 정렬 최적화)

이해가 잘 가지 않아 다시 예시를 보겠다.

-- 전통적인 인덱스 (MySQL 8.0 이전)
CREATE INDEX idx_score ON employees (score); -- 자동으로 오름차순으로만 저장

-- 내림차순 인덱스 (MySQL 8.0 이후)
CREATE INDEX idx_score_desc ON employees (score DESC); -- 실제로 내림차순으로 저장

-- (MySQL 8.0 이후)
CREATE INDEX idx_mixed ON employees (team_name ASC, score DESC);

1. MySQL 8.0 이전

모든 인덱스는 오름차순으로만 저장되고 desc 정렬이 필요한 경우 인덱스를 거꾸로 읽어야 한다.

특히 복합 인덱스에서 일부는 asc, 일부는 desc로 정렬해야 하는 경우 성능 저하가 발생한다.

1. MySQL 8.0 이후

인덱스 생성 시 각 컬럼별로 정렬 방향을 지정할 수 있다. 실제로 지정한 방향대로 데이터가 저장된다.

복합 인덱스에서도 각 컬럼별로 다른 정렬 방향을 지정할 수 있다.

아래 그림은 인덱스 정순, 역순 스캔의 이해를 돕는다.

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

• 내림차순 인덱스: 큰 값의 인덱스 키가 B-Tree 오른쪽에 정렬된 인덱스

• 인덱스 정순(forward) 스캔: 인덱스 키 값의 크고 작고와 상관없이 리프 노드의 왼쪽 페이지부터 오른쪽으로 스캔

• 인덱스 역순(backward) 스캔: 정순과 반대로 리프 노드의 오른쪽 페이지부터 왼쪽으로 스캔

일반적으로 인덱스 역순 스캔은 정순 스캔보다 느리다.

Record1 <-> Record2 <-> Record3 <-> Record4

MySQL의 InnoDB 스토리지 엔진에서 정순 스캔과 역순 스캔은 페이지(블록) 간의 더블 링크트 리스트의 포인터를 통해 전진, 후진하느냐 차이가 존재하지만 내부적으로 InnoDB에서 인덱스 역순 스캔이 더 느릴수 밖에 없는 이유가 있다.

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

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

일반적으로 인덱스를 order by .. desc 하는 쿼리가 소량의 레코드에 드물게 실행되는 경우라면 내림차순 인덱스를 굳이 고려할 필요는 없다.

또한 많은 쿼리가 인덱스의 앞쪽 혹은 뒤쪽으로 집중적으로 읽어서 인덱스의 특정 페이지 잠금이 병목이 될 것으로 예상된다면 쿼리에서 자주 사용되는 정렬 순서대로 인덱스를 생성하는 것이 잠금 병목 현상을 완화하는 데 도움이 될 것이다.