B-Tree Index (3)

들어가며

지난 글 B-Tree Index(2)에서는 인덱스 사용에 영향을 주는 요소들을 살펴보았다.

네 가지 요소가 영향을 줄 수 있음을 알게 되었고, 요소들은 아래에 정리되어 있다.

 

(1) 키 값의 크기

(2) B-Tree 의 깊이

(3) 기수성과 선택도

(4) 읽어야 하는 레코드 건수

 

이 요소들이 인덱스 사용에 미치는 영향을 알았으니,

이번 글에서는 B-Tree Index를 통해 데이터를 읽는 방법에 대해 살펴보자.

 

그 전에

데이터를 읽는 방법에 대해 알아보기 전에 먼저 스캔에 대해 알아보자.

 

스캔

스캔은 인덱스를 차례대로 읽는 것을 말한다.

위에서부터 아래, 즉 정방향으로 읽거나 아래에서부터 위, 즉 역방향으로 읽는 것 모두 스캔이라고 한다.

 

방법

MySQL B-Tree Index를 사용해 데이터를 읽는 방법에는 네 가지 방법이 있다.

 

(1) 인덱스 레인지 스캔

(2) 인덱스 풀 스캔

(3) 루즈 인덱스 스캔

(4) 인덱스 스킵 스캔

 

네 가지 방법을 Tight Index Scan / Loose Index Scan 으로 분류하기도 하는데, 자세한 내용은 하나씩 정리하며 알아보자.

이 글에서는 (1) 인덱스 레인지 스캔을 다룬다.

 

인덱스 레인지 스캔

언제 사용할까?

Index Range Scan이라는 이름에서 짐작할 수 있겠는가?

인덱스 레인지 스캔은 검색해야 할 인덱스 범위가 정해져 있을 때 사용한다.

 

과정

(1) 인덱스를 탐색하며 범위를 만족하는 값을 찾는다.

(2) 필요한만큼 인덱스를 스캔한다.

(3) 필요하다면 랜덤 I/O 작업을 수행하면서 디스크에서 레코드를 읽어온다. (선택)

 

과정 (3)이 선택으로 표시되어 있는 이유는, 커버링 인덱스로만 처리되는 경우가 있기 때문이다.

커버링 인덱스로 처리할 수 없는 경우 랜덤 I/O 작업(3)이 수행되어야 한다.

 

아마 여기서 궁금한 점 두 가지가 생겼을 것이다.

1) 커버링 인덱스

2) 랜덤 I/O

 

궁금증 해결을 위해 먼저 커버링 인덱스에 대해 간단히 알아보고,

커버링 인덱스가 적용되지 않을 때 왜 랜덤 I/O가 일어날 수밖에 없는지 설명하겠다.

 

커버링 인덱스

리프노드에 있는 데이터만 읽어도 쿼리에서 요구하는 데이터를 모두 읽을 수 있도록 인덱스가 등록되어 있을 때,

즉 쿼리에서 인덱스를 구성하는 컬럼 데이터만 요구하는 경우, 커버링 인덱스로 처리된다고 한다.

 

예시를 통해 더 알아보자.

 

예시

다음과 같은 컬럼과 인덱스를 가진 테이블이 있다고 가정하자.

- user : id, age, first_name, last_name, department, creator_id, modifier_id, created_at, modified_at

- index :  age, first_name 컬럼으로 구성됨

 

다음 쿼리가 요청되었다.

SELECT age, first_name
FROM user
WHERE age = 20 AND first_name BETWEEN 'Byun' AND 'Han'

 

이 쿼리에서는 age, first_name 컬럼의 데이터를 요구하고 있는데,

마침 user 테이블에는 age, first_name으로 구성된 인덱스가 등록되어 있다.

이것은 인덱스의 리프노드에 id와 name에 대한 데이터가 있다는 의미이므로,

만약 이 Leaf Node 페이지가 버퍼 풀에 있다면 디스크 I/O 작업을 거치지 않더라도 쿼리를 수행할 수 있다.

 

이렇게 인덱스 스캔만으로도 쿼리를 수행할 수 있을 때 커버링 인덱스로 처리된다고 한다.

그림을 보며 다시 짚어보자.

 

설명

아래 그림은 user 테이블의 Index가 있는 B-Tree를 그린 것이다.

Root Node, Branch Node, Leaf Node로 구성되어 있으며 인덱스가 다음 그림처럼 들어가 있다.

WHERE 절에 있는 조건으로 인덱스를 탐색하며 범위를 만족하는 값을 찾는 과정을 회색 화살표로 표시했다.

 

 

조건이 age = 20 AND first_name BETWEEN 'Byun' AND 'Han'이므로,

인덱스를 탐색하며 age가 20이고 first_name이 범위 안에 있는 노드를 찾는다.

(20, Ahn)으로부터 시작해 (20, Byun), (20, Bong) ... (20, Han)까지, 조건을 만족하는만큼 인덱스를 스캔한다.

 

쿼리를 통해 과정을 이해해보자.

SELECT age, first_name
FROM user
WHERE age = 20 AND first_name BETWEEN 'Byun' AND 'Han'

 

이 쿼리에서 요구하는 데이터는 age와 first_name 컬럼값이다.

위 그림 속 B-Tree Leaf Node의 인덱스 구조를 보면,

인덱스를 구성하는 컬럼인 age와 first_name 외에도 해당 레코드의 PK를 저장하고 있는 것을 볼 수 있다.

 

위의 쿼리에서는 age와 first_name 컬럼값을 요구하고 있기 때문에 인덱스 스캔만으로도 쿼리를 처리할 수 있다. (커버링 인덱스)

만약 인덱스를 구성하는 컬럼이 아닌 last_name을 요구하는 쿼리였다면 어떨까?

 

조금 변경된 쿼리를 보자.

last_name 값을 요구하도록 변경된 쿼리이다.

SELECT age, first_name, last_name
FROM user
WHERE age = 20 AND first_name BETWEEN 'Byun' AND 'Han'

 

이 쿼리처럼 커버링 인덱스로 처리될 수 없고 레코드가 저장된 페이지가 버퍼 풀에 존재하지 않는 경우,

디스크에서 원하는 레코드를 읽어와야 한다. 이 때 랜덤 I/O가 수행된다.

 

(참고)

인덱스를 사용해 레코드를 읽는 방법에 대해 지난 글인 B-Tree Index(1)에서 설명한 적이 있다.

스토리지 엔진의 종류에 따라 과정이 달랐는데, 아래 두 경우 모두 디스크에서 레코드를 읽어올 때에는 랜덤 I/O 작업이 수행된다.

MyISAM 스토리지 엔진 인덱스의 Leaf Node에서 물리 주소값인 ROWID를 저장하는 것과 달리,
InnoDB 스토리지 엔진 인덱스의 경우 PK 값을 저장하고 있기 때문에 데이터를 읽어오기 위해서는 PK를 통해 한 번 더 검색해야 한다.

 

I/O 방식에는 크게 순차 I/O와 랜덤 I/O가 있는데, 인덱스 레인지 스캔의 마지막 단계에서 일어나는 랜덤 I/O에 대해 알아보겠다.

 

랜덤 I/O

왜

왜 랜덤 I/O인지 묻는다면, 연속된 데이터를 읽는 것이 아니기 때문이라고 답하겠다.

이해를 돕기 위해 다시 한번 알아보자.

 

설명

지금까지 정리한 과정을 다시 생각해보자.

 

(1) 인덱스를 탐색하고

(2) 필요한만큼 스캔한다.

(3) 인덱스를 구성하는 컬럼이 아닌 값을 요청할 경우 디스크에서 레코드를 읽어와야 한다.

 

여기까지 설명했다.

 

위에서 봤던 그림을 다시 보며 이 질문에 답해보기를 바란다.

(3)단계에서 읽어올 레코드들은 디스크에 연속적으로 저장되어 있을까?

답은 '알 수 없다' 이다.

 

디스크에 어떻게 저장되어 있는지 알 수 없다는 의미인데,

INSERT 순서대로 저장된다고 생각할 수도 있지만 중간에 DELETE 등의 변경이 가해지면서 순서는 얼마든지 달라질 수 있다.

(클러스터링 인덱스도 INSERT 순서대로 저장되지 않는 이유 중 하나다.)

 

쿼리를 다시 가져왔다.

SELECT *
FROM user
WHERE age = 20 AND first_name BETWEEN 'Byun' AND 'Han'

 

이 쿼리의 조건으로 읽어들인 인덱스 값들은 다음과 같다. (20, Byun, 19251), (20, Bong, 32942), ... , (20, Han, 4)

쿼리를 보니 user 테이블의 전체 컬럼값을 읽어와야 한다. (실제로 와일드카드는 운영환경에서 쓰지 않아야 하지만, 예시를 위해 작성했다.)

그렇다면 이제부터 해야 할 것은 PK(또는 ROWID)를 통해 디스크에서 레코드를 읽어오는 작업일 것이다.

 

여기서 다시 한번 질문하겠다.

읽어올 레코드들은 디스크에 연속적으로 저장되어 있을까?

위에서 답을 공개했으니 아니라는 것을 알 수 있을 것이다.

그래서 랜덤 I/O가 수행된다. 연속적으로 데이터를 읽어오는 작업이 아니기 때문이다.

 

속도

인덱스 레인지 스캔은 다른 스캔방법과 비교했을 때 빠른 속도를 갖고 있다.

그도 그럴 것이, 범위 안에서 차례대로 필요한 만큼 읽기 때문에 그렇다.

 

(3)단계에서 수행될 수 있는 랜덤 I/O는 인덱스 레인지 스캔에서만 일어나는 것이 아니고

PK 등을 이용해 레코드를 읽어올 때 항상 일어나는 작업이다.

따라서 인덱스를 통해 데이터를 읽는 방법 네 가지의 속도를 비교할 때 고려되는 대상이 아니기 때문에, 헷갈리지 않기를 바란다.

 

분류

이 글을 시작할 때, 스캔 방법을 두 가지로 분류할 수 있다고 했다.

Tight Index Scan, Loose Index Scan인데

Index Range Scan은 Tight Index Scan으로 분류된다.

왜 그런 것인지는 Loose Index Scan을 이해하면 자연히 알게 될 것이므로,

이것에 대한 얘기는 스캔방법을 모두 설명하고나서 다시 알아보자.

 

마치며

이 글에서는 Index Range Scan에 대해 알아봤다.

 

(1) 어떨 때 일어나는지

(2) 어떤 과정을 거치는지

 

(2)에서 다른 많은 개념들이 나와서 설명이 조금 길어지기는 했지만, 앞으로도 쓰일 내용이므로 여기에서 한꺼번에 다루었다.

다음 글에서는 Index Full Scan에 대해 알아보겠다.