B-Tree 인덱스(2)
4. B-Tree 인덱스를 통한 데이터 읽기
어떤 경우에 인덱스를 사용하도록 유도할지, 또는 사용하지 못하게 할지 판단하려면 MySQL(더 정확히는 각 스토리지 엔진)이 어떻게 인덱스를 이용(경유)해서 실제 레코드를 읽어 내는지 알고 있어야 할 것이다. 여기서는 MySQL이 인덱스를 이용하는 대표적인 방법 3가지를 살펴보겠다.
인덱스 레인지 스캔
인덱스 레인지 스캔은 인덱스의 접근 방법 가운데 가장 대표적인 접근 방식으로, 밑에서 설명할 나머지 2가지 접근 방식보다는 빠른 방법이다. 인덱스를 통해 레코드를 한 건만 읽는 경우와 한 건 이상을 읽는 경우를 각각 다른 이름으로 구분하지만, 여기서는 모두 묶어 "인덱스 레인지 스캔"이라고 표현했다. 다음 쿼리를 예제로 살펴보자.
SELECT * FROM employees WHERE first_name BETWEEN 'Ebbe' AND 'Gad';
인덱스 레인지 스캔은 검색해야 할 인덱스의 범위가 결정됐을 때 사용하는 방식이다. 검색하려는 값의 수나 검색 결과 레코드 건수와 관계없이 레인지 스캔이라고 표현한다. 위의 그림의 화살표에서도 알 수 있듯이 루트 노드에서부터 비교를 시작해 브랜치 노드를 거치고 최종적으로 리프 노드까지 찾아 들어가야만 비로소 실제로 원하는 시작 지점을 찾을 수 있다. 일단 시작해야 할 위치를 찾으면 그때부터는 리프 노드의 레코드만 순서대로 읽으면 된다. 이처럼 차례대로 쭉 읽는 것을 스캔이라고 표현한다. 만약 스캔하다가 리프 노드의 끝까지 읽으면 리프 노드 간의 링크를 이용해 다음 리프 노드를 찾아서 다시 스캔한다. 그리고 최종적으로 스캔을 멈춰야 할 위치에 다다르면 지금까지 읽은 레코드를 사용자에게 반환하고 쿼리를 끝낸다. 위의 그림에서 두꺼운 선을 스캔해야 할 위치 검색을 위한 비교 작업을 위미하며, 바탕색이 있는 리프 노드의 레코드 구간은 실제 스캔하는 범위를 표현했다.
위의 그림은 실제로 인덱스만을 읽는 경우를 보여준다. 하지만 B-Tree 인덱스의 리프 노드를 스캔하면서 실제 데이터 파일의 레코드를 읽어 와야 하는 경우도 많은데, 이 과정을 좀 더 자세히 살펴보자.
B-Tree 인덱스에서 루트와 브랜치 노드를 이용해 특정 검색(스캔) 시작 값을 가지고 있는 리프 노드를 검색하고, 그 지점부터 필요한 방향(오름차순 또는 내림차순)으로 인덱스를 읽어 나가는 과정을 위의 그림에서 확인할 수 있다. 가장 중요한 것은 어떤 방식으로 스캔하든 관계없이, 해당 인덱스를 구성하는 칼럼의 정순 또는 역순으로 정렬된 상태로 레코드를 가져온다는 것이다. 이는 별도의 정렬 과정이 수반되는 것이 아니라 인덱스 자체의 정렬 특성 때문에 자동으로 그렇게 된다는 것이다.
또 하나 위의 그림에서 중요한 것은 인덱스의 리프 노드에서 검색 조건에 일치하는 건들은 데이터 파일에서 레코드를 읽어오는 과정이 필요하다는 것이다. 이때 리프 노드에 저장되는 레코드 주소로 데이터 파일의 레코드를 읽어오는데, 레코드 한 건 한 건 단위로 랜덤 I/O가 한 번씩 실행된다. 위의 그림에서처럼 3건의 레코드가 검색 조건에 일치했다고 가정하면 데이터 레코드를 읽기 위해 랜덤 I/O가 최대 3번이 필요한 것이다. 그래서 인덱스를 통해 데이터 레코드를 읽는 작업은 비용이 많이 드는 작업으로 분류되는 것이다. 그리고 인덱스를 통해 읽어야 할 데이터 레코드가 20~25%를 넘으면 인덱스를 통한 읽기보다 테이블의 데이터를 직접 읽는 것이 더 효율적인 처리 방식이 되는 것이다.
인덱스 풀 스캔
인덱스 레인지 스캔과 마찬가지로 인덱스를 사용하지만 인덱스 레인지 스캔과는 달리 인덱스의 처음부터 끝까지 모두 읽는 방식을 인덱스 풀 스캔이라고 한다. 대표적으로 쿼리의 조건절에 사용된 칼럼이 인덱스의 첫 번째 칼럼이 아닌 경우 인덱스 풀 스캔 방식이 사용된다. 예를 들어 인덱스는 (A, B, C) 칼럼의 순서대로 만들어져 있지만 쿼리의 조건절은 B 칼럼이나 C 칼럼으로 검색하는 경우다.
일반적으로 인덱스의 크기는 테이블의 크기보다 작으므로 직접 테이블을 처음부터 끝까지 읽는 것보다는 인덱스만 읽는 것이 효율적이다. 쿼리가 인덱스에 명시된 칼럼만으로 조건을 처리할 수 있는 경우 주로 이 방식이 사용된다. 인덱스뿐만이 아니라 데이터 레코드까지 모두 읽어야 한다면 절대 이 방식으로 처리되지 않는다. 간단하게 그림으로 인덱스 풀 스캔의 처리 방식을 살펴보자.
위의 그림에서 인덱스 풀 스캔의 예를 살펴볼 수 있다. 먼저 인덱스 리프 노드의 제일 앞 또는 제일 뒤로 이동한 후, 인덱스의 리프 노드를 연결하는 링크드 리스트(Linked list, 리프 노드 사이를 연결하는 세로로 그려진 두쌍씩의 화살표)를 따라서 처음부터 끝까지 스캔하는 방식을 인덱스 풀 스캔이라고 한다. 이 방식은 인덱스 레인지 스캔보다는 빠르지 않지만 테이블 풀 스캔보다는 효율적이다. 위에서도 언급했듯이 인덱스에 포함된 칼럼만으로 쿼리를 처리할 수 있는 경우 테이블의 레코드를 읽을 필요가 없기 때문이다. 인덱스의 전체 크기는 테이블 자체의 크기보다는 훨씬 작으므로 인덱스 풀 스캔은 테이블 전체를 읽는 것보다는 적은 디스크 I/O로 쿼리를 처리할 수 있다.
루스 인덱스 스캔
많은 사용자에게 루스(Loose) 인덱스 스캔이라는 단어는 상당히 생소할 것이다. 오라클과 같은 DBMS의 "인덱스 스킵 스캔"이라고 하는 기능과 작동 방식은 비슷하지만 MySQL에서는 이를 "루스 인덱스 스캔"이라고 한다. 하지만 MySQL의 루스 인덱스 스캔 기능은 아직은 제한적이다. 위에서 소개한 두 가지 접근 방법("인덱스 레인지 스캔"과 "인덱스 풀 스캔")은 "루스 인덱스 스캔"과는 상반된 의미에서 "타이트(Tight) 인덱스 스캔"으로도 분류한다. 루스 인덱스 스캔이란 말 그대로 느슨하게 또는 듬성듬성하게 인덱스를 읽는 것을 의미한다.
루스 인덱스 스캔은 인덱스 레인지 스캔과 비슷하게 작동하지만, 중간마다 필요치 않은 인덱스 키값은 무시(SKIP)하고 다음으로 넘어가는 형태로 처리한다. 일반적으로 GROUP BY 또는 집합 함수 가운데 MAX() 또는 MIN() 함수에 대해 최적화를 하는 경우에 사용된다.
SELECT dept_no, MIN(emp_no)
FROM dept_emp
WHERE dep_no BETWEEN 'd002' AND 'd004'
GROUP BY dept_no;이 쿼리에서 사용된 dept_emp 테이블은 dept_no와 emp_no 두 개의 칼럼으로 인덱스가 생성돼 있다. 또한 이 인덱스는 dept_no + emp_no의 값으로 정렬까지 돼 있어서 위의 그림에서와 같이 dept_no 그룹별로 제일 첫 번째 레코드의 emp_no 값만 읽으면 되는 것이다. 즉 인덱스에서 WEHRE 조건을 만족하는 범위 전체를 다 스캔할 필요가 없다는 것을 옵티마이저는 알고 있기 때문에 조건에 만족하지 않는 레코드는 무시하고 다음 레코드로 이동한다. 위의 그림을 보면 인덱스 리프 노드를 스캔하면서 불필요한 부분은 무시하고 필요한 부분만 읽었음을 알 수 있다.
5. 다중 칼럼(Multi-column) 인덱스
지금까지 살펴본 인덱스들은 모두 1개의 칼럼만 표함된 인덱스였다. 하지만 실제 서비스용 데이터베이스에서는 2개 이상의 칼럼을 포함하는 인덱스가 더 많이 사용된다. 두 개 이상의 칼럼으로 구성된 인덱스를 다중 칼럼 인덱스라고 하며, 또한 2개 이상의 칼럼이 연결됐다고 해서 "Concatenated Index"라고 도 한다. 아래 그림은 2개 이상의 칼럼을 포함하는 다중 칼럼 인덱스의 구조를 보여준다.
위의 그림에서는 편의상 루트 노드는 생략했으나 실제로 데이터 레코드 건수가 작은 경우에는 브랜치 노드가 없는 경우도 있을 수 있다. 하지만 루트 노드와 리프 노드는 항상 존재한다. 위의 그림은 다중 칼럼 인덱스일 때 각 인덱스 구성 칼럼값이 어떻게 정렬되어 저장되는지 설명하기 위해서다. 이 그림에서 중요한 것은 인덱스의 두 번째 칼럼은 첫 번재 칼럼에 의존해서 정렬돼 있다는 것이다. 즉, 두 번째 칼럼의 정렬은 첫 번째 칼럼이 똑같은 레코드에서만 의미가 있다는 것이다. 위의 그림에서는 칼럼이 2개 뿐이지만, 만약 칼럼이 4개인 인덱스를 생성한다면 세 번째 칼럼은 두 번째 칼럼에 의존해서 정렬되고 네 번째 칼럼은 다시 세 번째 칼럼에 의존해서 정렬된다는 것이다. 위의 예제에서 emp_no 값의 정렬 순서가 빠르다 하더라도 dept_no 칼럼의 정렬 순서가 늦다면 인덱스의 뒤쪽에 위치한다. 그래서 위의 그림에서 emp_no 값이 "10003"인 레코드가 인덱스 리프 노드의 제일 마지막(하단)에 위치하는 것이다. 다중 칼럼 인덱스에서는 인덱스 내에서 각 칼럼의 위치(순서)가 상당히 중요하며 또한 아주 신중히 결정해야 하는 이유가 바로 여기에 있다.
참고
- Real MySQL
