인덱스 Index - (4) :B-Tree 인덱스를 통한 데이터 읽기

1. 인덱스 레인지 스캔

인덱스를 통해 레코드를 한 건만 읽는 경우와 한 건 이상을 읽는 경우는 각각 다른 이름으로 구분하지만, 여기서는 '인덱스 레인지 스캔'으로 통일한다. 자세한 내용은 '실행 계획'에서 다루도록 하겠다. 

-- SELECT (1)
SELECT first_name
  FROM employees
 WHERE first_name BETWEEN 'Ebbe' AND 'Gad';

그림(1) first_name 컬럼의 인덱스를 이용한 레인지 스캔

인덱스 레인지 스캔은 검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식이다. 그림(1) 화살표에서도 알 수 있듯이 루트 노드에서부터 비교를 시작해 브랜치 노드를 거쳐 최종적으로 리프 노드까지 찾아 들어가야만 비로소 필요한 레코드의 시작 지점 (리프 노드 페이지 (5) 인덱스 키 Ebbe)을 찾을 수 있다. 일단 시작지점을 찾으면 그때부터는 리프 노드의 레코드만 순서대로 읽으면 된다. 이처럼 차례대로 쭉 읽는 것을 스캔이라고 표현한다. 만약 스캔하다가 리프 노드(페이지)의 끝까지 읽으면 리프 노드(페이지)간의 링크를 이용해 다음 리프 노드(페이지)를 찾아서 다시 스캔을 시작한다. 그리고 최종적으로 스캔을 멈춰야 할 위치에 다다르면 지금까지 읽은 레코드를 사용자에게 반환하고 쿼리를 종료한다.

 

-- SELECT (2)
SELECT *
  FROM employees
 WHERE first_name BETWEEN 'Ebbe' AND 'Gad';

그림(2) 인덱스 레인지 스캔을 통한 데이터 레코드 읽기

그림(1)은 실제 인덱스만을 읽는 경우를 보여주지만 그림(2)는 실제 데이터 파일의 레코드를 읽어 와야 하는 경우를 나타낸다. 리프 노드에서 저장된 레코드 주소로 데이터 파일의 레코드를 읽어오는데 레코드 한 건 마다 랜덤 I/O가 한 번씩 일어난다. 만약 3건의 레코드가 검색 조건에 일치했다면 랜덤 I/O가 최대 3번 필요하게 된다. 그래서 인덱스를 통해 데이터 레코드를 읽는 작업은 비용이 많이 드는 작업으로 분류된다. 그래서 읽어야 할 데이터 레코드가 20~25%를 넘어가면 인덱스를 통해 데이터를 읽으면 랜덤 I/O가 많이 발생하니 테이블의 데이터를 직접 읽어서 순차 I/O로 처리하는 것이 효율적이다.

인덱스 레인지 스캔은 3단계로 처리된다. 

1.  인덱스에서 조건을 만족하는 값이 저장된 시작점을 찾는다. 이 과정을 인덱스 탐색(Index Seek)이라고 한다. 
2.  1번에서 탐색된 시작점부터 필요한 만큼 인덱스를 차례대로 읽는다. 이 과정을 인덱스 스캔(Index Scan)이라고 한다.
3.  2번에서 읽어 들인 인덱스 키와 레코드 주소를 이용해 레코드가 저장된 페이지를 가져오고, 최종 레코드를 읽어온다. 

쿼리가 필요로 하는 데이터에 따라 3번 과정은 생략될 수 있는데 이를 커버링 인덱스라고 한다. 위 SELECT(1)이 이에 해당한다. 커버링 인덱스는 디스크의 레코드를 읽지 않아도 되기 때문에 성능은 그만큼 빨라진다.

 

2. 인덱스 풀 스캔

인덱스의 처음부터 끝까지 모두 읽는 방식을 인덱스 풀 스캔이라고 한다. 대표적으로 쿼리의 조건절에 사용된 컬럼과 표시 컬럼이 인덱스에 포함된 컬럼이지만 인덱스의 첫 번째 컬럼이 아닌 경우 인덱스 풀 스캔 방식이 사용된다. 예를 들어, 인덱스는 (A, B, C)컬럼의 순서로 만들어져 있지만 쿼리의 조건절은 B 혹은 C 컬럼으로 검색하는 경우이다. 일반적으로 인덱스의 크기는 테이블의 크기보다 작으므로 직접 테이블을 처음부터 끝까지 읽는 것보다는 인덱스만 읽는 것이 효율적이다. 커버링 인덱스로만 처리할 경우 이 방식이 사용될 수 있지만 데이터 레코드(인덱스에 포함되어 있지 않은 컬럼의 데이터를 가져와야 하는 경우)까지 모두 읽어야 한다면 옵티마이저에 의해 절대 이 방식으로 처리되지 않는다.

 

3. 루스 인덱스 스캔

느슨하게 또는 듬성듬성하게 인덱스를 읽는 것을 의미한다. 인덱스 레인지 스캔과 비슷하게 작동하지만 중간에 필요치 않은 인덱스 키 값은 무시(SKIP)하고 다음으로 넘어가는 형태로 처리한다. GROUP BY, DISTINCT 작업을 처리하는 경우에만 적용된다. 실행계획 Extra에 "Using index for group-by"로 표시된다.

SELECT dept_no, MIN(emp_no)
  FROM dept_emp
 WHERE dept_no BETWEEN 'd002' AND 'd004'
 GROUP BY dept_no;

그림(3) 루스 인덱스 스캔을 통한 데이터 읽기

이 쿼리에서 사용된 dept_emp 테이블은 (dept_no, emp_no) 컬럼으로 구성된 인덱스가 생성되어 있다. 인덱스는 정렬까지 되어 있기 때문에 그림(3)과 같이 dept_no 그룹별로 첫 번째 레코드의 emp_no 값만 읽으면 된다. 인덱스에서 WHERE 조건에 만족하는 범위 전체를 모두 인덱스 스캔할 필요가 없다는 것을 옵티마이저가 알고 있기 때문에 무시하고 다음 페이지로 이동한 다음 첫 번째 레코드만 읽는 것을 볼 수 있다.

위 이미지는 마치 페이지 마다 dept_no가 모두 분리가 되어 있는 이상적인 모습을 보이고 있고 그러면 페이지 이동으로 해결이 되지만 실제로는 한 페이지에 다른 dept_no가 있을 수 있다. 그래서 다음 dept_no를 찾는 것은 인덱스 탐색(Index Seek)으로 찾아내고 정렬이 되어 있기 때문에 처음 만나는 row의 emp_no가 min값이기 때문에 min값을 얻은 후 바로 다음 dept_no를 찾는 인덱스 탐색으로 다음 dept_no를 찾는다.

 

4. 인덱스 스킵 스캔 

인덱스의 핵심은 값이 정렬돼 있다는 것이며 인덱스를 구성하는 칼럼의 순서가 매우 중요하다. 예를 들어 employees 테이블에 다음과 같은 인덱스를 생성해보자. 

ALTER TABLE employees
  ADD INDEX ix_gender_birthdate (gender, birth_date);

ix_gender_birthdate 인덱스를 이용하려면 WHERE 조건절에 gender 컬럼에 대한 비교 조건이 필수이다.

-- SELECT(1) 인덱스를 사용하지 못하는 쿼리
SELECT *
  FROM employees
 WHERE birth_date >= '1965-02-01';
 
 
 -- SELECT(2) 인덱스를 사용할 수 있는 쿼리
 SELECT *
  FROM employees
 WHERE gender = 'M'
   AND birth_date >= '1965-02-01';

SELECT(2)는 인덱스를 효율적으로 사용할 수 있지만 SELECT(1)은 인덱스를 사용할 수 없다. 이런 경우 birth_date 칼럼의 인덱스 혹은 birth_date 컬럼으로 시작하는 인덱스를 새로 생성해야만 한다. 

MySQL 8.0 버전부터는 옵티마이저가 SELECT(1) 상황에서도 인덱스 검색이 가능하게 해주는 인덱스 스킵 스캔 (Index Skip Scan) 최적화 기능이 도입되었다. 이와 비슷한 최적화를 수행하는 루스 인덱스 스캔이라는 기능이 있지만 GROUP BY 작업 때만 적용할 수 있지만 인덱스 스킵 스캔은 WHERE 조건절의 검색을 위해 사용 가능하도록 용도가 훨씬 넓어졌다.

SET optimizer_switch='skip_scan=off'; -- 인덱스 스킵 스캔 비활성화

EXPLAIN 
 SELECT gender, birth_date
   FROM employees 
  WHERE birth_date >= '1965-02-01';

우선 인덱스 스킵 스캔 기능을 비활성하고 실행 계획을 보자. type컬럼의 값이 'index'이면 풀 인덱스 스캔을 의미하므로 인덱스를 비효율적으로 사용한 것이다. 

 

SET optimizer_switch='skip_scan=on'; -- 인덱스 스킵 스캔 활성화

EXPLAIN
 SELECT gender, birth_date
   FROM employees 
  WHERE birth_date >= '1965-02-01';

인덱스 스킵 스캔 기능을 활성화하고 실행 계획을 보자. type컬럼의 값이 'range'이면 인덱스에서 필요한 부분만 읽었다는 것을 의미한다. 그리고 Extra 컬럼에 'Using index for skip scan'이라는 문구가 표시되는데 이는 인덱스 스킵 스캔을 활용해 데이터를 조회했다는 것을 의미한다.

 

그림(4) 인덱스 스킵 스캔을 통한 데이터 읽기

그림(4)를 보면 MySQL 옵티마이저는 우선 gender 칼럼에서 유니크한 값을 모두 조회해서 주어진 쿼리에 gender 컬럼의 조건을 추가해서 쿼리를 다시 실행하는 형태로 처리한다. 즉 아래 2개의 쿼리를 실행하는 것과 비슷한 형태의 최적화를 실행하게 된다. 

SELECT gender, birth_date
  FROM employees
 WHERE gender = 'F'
   AND birth_date >= '1965-02-01';

SELECT gender, birth_date
  FROM employees
 WHERE gender = 'M'
   AND birth_date >= '1965-02-01';