#13. 인덱스와 정렬
정렬 비용 없이 ORDER BY 처리하기
# 인덱스와 정렬 — 정렬 비용 없이 ORDER BY 처리하기
> 📘 **학습자료 14편 / 15편** | 연결 퀴즈: [**인덱스 고급1 풀러가기**](quiz.html?set=G)
> `ORDER BY`가 들어간 쿼리의 성능을 가르는 결정적 요소는 **"정렬을 따로 하느냐, 인덱스를 그대로 읽느냐"** 입니다.
> 인덱스가 이미 정렬된 자료구조라는 사실이, 정렬 쿼리 최적화의 출발점입니다.
> 그리고 MySQL 8.0+의 **내림차순 인덱스**까지 알면 정렬 최적화의 완성입니다.
> 📚 **이전 편**: [13편 - 인덱스 스킵 스캔]
> 9편의 복합 인덱스 설계 3단계 중 2단계가 "범위 조건 또는 ORDER BY 컬럼"이었습니다.
> 이번 편에서 그 "ORDER BY 컬럼" 부분을 본격적으로 다룹니다.
## 이 자료를 다 읽으면 알게 되는 것
- 인덱스가 ORDER BY를 **공짜로 처리**할 수 있는 이유
- ASC뿐 아니라 DESC도 인덱스로 처리하는 **역순 스캔(Backward index scan)**
- 정순 스캔이 역순 스캔보다 **빠른 두 가지 이유**
- MySQL 8.0+의 **내림차순 인덱스**가 등장한 배경
---
## 📑 목차
- [1. 인덱스는 이미 정렬된 자료구조](#1-인덱스는-이미-정렬된-자료구조)
- [⭐ 2. ORDER BY ASC: 인덱스를 그대로 읽기](#2-order-by-asc-인덱스를-그대로-읽기)
- [3. ORDER BY DESC: 역순 스캔](#3-order-by-desc-역순-스캔)
- [4. 정렬 조건이 인덱스 컬럼이 아닐 때](#4-정렬-조건이-인덱스-컬럼이-아닐-때)
- [⭐ 5. 정순 스캔이 역순 스캔보다 빠르다](#5-정순-스캔이-역순-스캔보다-빠르다)
- [6. MySQL 8.0+ 내림차순 인덱스](#6-mysql-80-내림차순-인덱스)
- [핵심 요약](#핵심-요약)
---
## 1. 인덱스는 이미 정렬된 자료구조
2편(B+Tree 인덱스)에서 이미 본 사실 한 가지를 다시 꺼냅니다.
> **InnoDB의 일반 인덱스는 값들이 오름차순으로 정렬된 B-Tree 구조다.**
이 한 문장이 ORDER BY 최적화의 출발점입니다. 인덱스 리프 노드의 값들이 **이미 정렬되어 있으니**, ORDER BY를 위해 따로 정렬할 필요가 없습니다.
10편의 사전 비유를 다시 가져오면:
- 사전은 가나다순으로 이미 정렬되어 있다
- "가나다순으로 단어 목록을 보여달라"는 요청이 오면 → 사전을 그냥 처음부터 펼쳐 읽으면 끝
별도의 정렬 작업이 필요 없죠. SQL에서도 똑같습니다.
> 💡 **정렬 비용을 따로 안 들이는 게 왜 중요한가**
> ORDER BY가 들어간 쿼리에서 인덱스를 못 쓰면, MySQL은 결과를 **임시 공간에 쌓아 정렬**(filesort)합니다.
> 메모리에 안 들어가는 양이면 디스크까지 쓰게 되고, 행 수가 많을수록 비용이 폭발합니다.
> 인덱스를 정렬에 활용한다는 건 이 비용을 **0으로 만드는** 일입니다.
---
## 2. ORDER BY ASC: 인덱스를 그대로 읽기
> ⭐ **이 섹션이 인덱스 정렬의 가장 기본 패턴입니다.**
다음 상황을 봅시다.
```sql
-- ix_firstname (first_name) 인덱스 존재
SELECT first_name
FROM employees
ORDER BY first_name ASC
LIMIT 4;
```
`ix_firstname`은 `first_name` 기준으로 오름차순 정렬된 인덱스 테이블입니다. 그러니 그냥 인덱스를 **앞에서부터 4개만 읽으면** 끝입니다.
EXPLAIN 결과:
| id | type | key | rows | Extra |
|---|---|---|---|---|
| 1 | index | ix_firstname | 4 | (없음) |
`type: index`는 인덱스를 순차 스캔했다는 뜻입니다. `Extra`에 `Using filesort`가 없는 게 핵심 — **별도 정렬 작업이 일어나지 않았다**는 신호입니다.
> ⚠️ **type: index를 type: ALL과 헷갈리지 말 것**
> - `type: index` = 인덱스 테이블을 순차 스캔 (인덱스 활용 O)
> - `type: ALL` = 데이터 테이블을 풀 스캔 (인덱스 활용 X)
>
> 둘 다 "전체를 다 읽는다"는 점은 같지만, 무엇을 읽느냐가 다릅니다.
> 인덱스 테이블이 데이터 테이블보다 훨씬 가볍기 때문에 `type: index`가 더 빠릅니다.
---
## 3. ORDER BY DESC: 역순 스캔
ASC만 인덱스를 활용할 수 있는 게 아닙니다. DESC도 가능합니다.
```sql
SELECT first_name
FROM employees
ORDER BY first_name DESC
LIMIT 5;
```
오름차순으로 정렬된 인덱스를 **뒤에서부터** 읽으면 그게 곧 내림차순 결과입니다. 이걸 **역순 스캔(Backward index scan)** 이라고 부릅니다.
EXPLAIN 결과:
| id | type | key | rows | Extra |
|---|---|---|---|---|
| 1 | index | ix_firstname | 5 | **Backward index scan** |
`Extra`에 `Backward index scan`이 찍힙니다. 인덱스를 거꾸로 읽었다는 명시적 신호입니다.
> 💡 **MySQL 5.7 이전에는 어땠나**
> 5.7 이전에도 역순 스캔은 가능했지만, EXPLAIN 출력에 명시되지 않았습니다.
> 8.0부터 `Backward index scan`이라는 키워드로 표시되어 진단이 쉬워졌습니다.
---
## 4. 정렬 조건이 인덱스 컬럼이 아닐 때
여기서 한 가지 함정. **정렬한다고 무조건 인덱스를 활용하는 건 아닙니다.**
```sql
-- ix_firstname (first_name) 인덱스 존재
-- PK는 emp_no
SELECT first_name
FROM employees
ORDER BY emp_no DESC -- ← first_name이 아닌 emp_no로 정렬
LIMIT 4;
```
`ix_firstname`은 `first_name` 기준 정렬이지 `emp_no` 기준이 아닙니다. 그러니 이 쿼리에서는 `ix_firstname`의 정렬 성질을 활용할 수 없습니다.
대신 옵티마이저는 **클러스터링 인덱스(PK)** 를 봅니다. PK인 `emp_no`도 그 자체가 정렬된 자료구조니까요.
EXPLAIN 결과:
| id | type | key | rows | Extra |
|---|---|---|---|---|
| 1 | index | **PRIMARY** | 4 | Backward index scan |
`key: PRIMARY` — `ix_firstname`이 아니라 PK를 활용했다는 뜻입니다.
### 한 줄 정리
> **인덱스의 정렬 성질을 ORDER BY에 활용하려면, ORDER BY 컬럼이 그 인덱스의 정렬 기준 컬럼이어야 한다.**
이게 컴포지트 인덱스 설계 3단계(9편)에서 "ORDER BY 컬럼을 두 번째로"라고 했던 이유입니다.
---
## 5. 정순 스캔이 역순 스캔보다 빠르다
> ⭐ **이 섹션이 14편의 가장 중요한 포인트입니다.**
3장에서 "DESC도 역순 스캔으로 처리된다"고 했습니다. 그럼 ASC와 DESC가 성능적으로 똑같을까요? **그렇지 않습니다.** 같은 인덱스로 정순/역순을 비교하면 정순이 더 빠릅니다.
실측 예시:
```text
SELECT * FROM t1 ORDER BY tid ASC LIMIT 60030975, 1 -- 9.8초
SELECT * FROM t1 ORDER BY tid DESC LIMIT 60030975, 1 -- 10.8초
```
같은 데이터, 같은 인덱스인데 약 1초 차이가 납니다. 왜 그럴까요?
### 이유 1: 페이지 잠금이 정순에 최적화
InnoDB는 동시성 제어를 위해 페이지에 잠금을 거는데, **데드락 방지를 위해 한 방향으로만 잠금을 획득**하도록 설계되어 있습니다. 그 방향이 왼쪽 → 오른쪽, 즉 정순 방향이죠.
- 정순 스캔: 다음 페이지 잠금 획득이 단순
- 역순 스캔: 이전 페이지 잠금을 획득하기 위해 추가 작업 필요
많은 페이지를 스캔할수록 이 차이가 누적됩니다.
### 이유 2: 페이지 내부 레코드는 단방향 연결
InnoDB의 B-Tree 리프 페이지들 자체는 양방향(double linked list)으로 연결되어 있습니다. 그래서 페이지 단위 이동에는 큰 차이가 없습니다.
문제는 **페이지 내부**입니다. 한 페이지 안에는 보통 수백 개의 레코드가 들어 있는데, 이 레코드들은 **단방향(다음 레코드만 가리킴)** 으로 연결되어 있습니다.
- 정순 스캔: 다음 레코드 포인터를 그대로 따라가면 됨
- 역순 스캔: "이전 레코드"를 직접 가리키는 포인터가 없어서, 페이지 디렉토리(대표키 모음)를 거쳐 우회 탐색
이 우회 비용이 레코드 수만큼 누적됩니다.
### 정리
> 🎯 정순 스캔이 빠른 이유는 두 가지:
> ① 페이지 잠금이 한 방향(정순)에 최적화
> ② 페이지 내부 레코드가 단방향 연결이라 역순은 우회 비용 발생
이 사실이 다음 섹션의 **내림차순 인덱스**가 등장한 배경이 됩니다.
---
## 6. MySQL 8.0+ 내림차순 인덱스
5장의 결론은 이렇습니다:
- **내림차순 쿼리가 자주 일어나는 경우**, 오름차순 인덱스의 역순 스캔보다 **내림차순 인덱스의 정순 스캔**이 더 빠르다.
MySQL 8.0부터는 인덱스 자체를 내림차순으로 만들 수 있습니다.
```sql
-- 오름차순 인덱스 (기존)
CREATE INDEX column_idx_asc ON t1(column_name);
-- 내림차순 인덱스 (MySQL 8.0+)
CREATE INDEX column_name_desc ON t1(column_name DESC);
```
내림차순 인덱스는 **큰 값이 B-Tree의 왼쪽**에 위치하는 인덱스입니다. 즉 `ORDER BY column_name DESC` 쿼리에 대해서는 이 인덱스를 정순 스캔하면 됩니다.
### 실측 비교
같은 `ORDER BY column_name DESC` 쿼리에 대해:
| 사용한 인덱스 | 스캔 방향 | 실행 시간 |
|---|---|---|
| 오름차순 인덱스 (`column_idx_asc`) | 역순 스캔 | 1.91초 |
| 내림차순 인덱스 (`column_name_desc`) | 정순 스캔 | 1.27초 |
약 33% 빨라집니다. 내림차순 쿼리가 자주 실행되는 시스템(예: "최신 게시글 N개" 쿼리)에서는 의미 있는 차이입니다.
> 💡 **언제 내림차순 인덱스를 만들까**
> "최신 N개", "최근 1주일", "랭킹 상위 N명" 같이 **DESC 정렬이 비즈니스 로직의 기본**인 쿼리에서 효과가 큽니다.
> 단, 모든 인덱스를 내림차순으로 만들면 ASC 쿼리가 손해를 봅니다. **자주 쓰는 정렬 방향에 맞춰** 결정해야 합니다.
---
## 핵심 요약
이번 편에서 꼭 가져가야 할 한 가지:
> 🎯 **인덱스는 정렬된 자료구조이므로, ORDER BY가 인덱스 정렬과 일치하면 정렬 비용이 0이 된다**
> ASC는 정순 스캔, DESC는 역순 스캔으로 처리. 정순이 역순보다 빠르므로, DESC가 잦으면 8.0+의 내림차순 인덱스 고려.
체크리스트:
- [x] 인덱스가 ORDER BY를 공짜로 처리할 수 있는 이유를 설명할 수 있다
- [x] EXPLAIN의 `Backward index scan`이 무엇을 의미하는지 안다
- [ ] ORDER BY 컬럼이 인덱스 정렬 기준이 아니면 인덱스 정렬을 활용 못 한다는 걸 안다
- [ ] 정순 스캔이 역순 스캔보다 빠른 두 가지 이유를 안다
- [ ] MySQL 8.0+의 내림차순 인덱스가 어떤 상황에서 유리한지 판단할 수 있다
> 📝 체크리스트를 다 채울 자신이 있다면? [**인덱스 고급1 퀴즈 도전하기**](quiz.html?set=G)
---
## 이제 퀴즈에 도전하기
고급1 퀴즈의 전반부(인덱스 정렬)를 다뤘습니다.
- 인덱스는 이미 정렬된 자료구조 (14편)
- ASC는 정순 스캔, DESC는 역순 스캔(`Backward index scan`) (14편)
- ORDER BY 컬럼이 인덱스 정렬 기준이 아니면 인덱스 정렬 활용 불가 (14편)
- 정순이 역순보다 빠른 이유 + 8.0+ 내림차순 인덱스 (14편)
후반부(Index Condition Pushdown)는 15편에서 다룹니다.
> 🎯 [**인덱스 고급1 퀴즈 풀어보기**](quiz.html?set=G)
> 막히는 문제가 있다면 해당 섹션으로 돌아와 다시 읽어보세요.
> 이번 편의 핵심은 **EXPLAIN의 `Extra` 컬럼을 정렬 관점에서 다시 읽는 것** 입니다.
> `Backward index scan`이 보이면 정상, `Using filesort`가 보이면 인덱스 정렬을 못 쓰고 있다는 신호입니다.
---
## 다음 학습자료
고급1의 후반부, **Index Condition Pushdown(ICP)** 을 다룹니다. MySQL 5.6부터 도입된 최적화로, 인덱스로는 직접 탐색할 수 없는 조건도 스토리지 엔진이 인덱스 안에서 미리 걸러주는 기법입니다.
---
## Reference
- MySQL 공식 문서: [ORDER BY Optimization](https://dev.mysql.com/doc/refman/8.4/en/order-by-optimization.html)
- MySQL 공식 문서: [Descending Indexes](https://dev.mysql.com/doc/refman/8.4/en/descending-indexes.html)
- 카카오 기술 블로그: [InnoDB의 Backward Index Scan](https://tech.kakao.com/posts/351)