인덱스, 아는 만큼 보인다!
DBMS 개발자가 전하는 인덱스 활용 노하우

 

고성능 서비스를 구축하기 위한 DB 쿼리 튜닝의 핵심은 인덱스를 얼마나 잘 활용하는가에 달려 있다. 지난 3년 동안 CUBRID를 NHN 내/외부 서비스에 적용하면서 의외로 많은 개발자들이 DB 인덱스에 대해 “잘” 알지 못하고 “잘” 활용하지 못한다는 것을 발견하였다. 본 기고문에서는 6월 30일에 출시된 CUBRID 2008 R4.0에 적용된 다양한 인덱스 기법을 중심으로 인덱스 구조와 인덱스 활용 노하우를 쉽게 설명하고자 한다. 단, MySQL, MS-SQL, Oracle 등 다른 DBMS에서도 이와 동일/유사한 인덱스 기법이 적용되어 있으므로 본 기고문에서 소개할 인덱스 활용 노하우가 CUBRID에 국한되지 않는다는 점을 강조하고 싶다.

 

* 본 게시글은 월간 마이크로소프트웨어 8월호에 게재된 내용의 원작입니다.

   월간 마이크로소프트웨어에서는 약간 내용이 줄어서 게재된 관계로 본 게시글과 차이가 있을 수 있습니다.

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
강동완  | NHN Business Platform 서비스 플랫폼 개발 센터 내 DBMS 개발랩 소속이다. CUBRID 차기 버전(코드명: Apricot)에 오라클의 Index Skip Scan 기법 (MySQL에서는 Loose Index Scan이라고 함)과 Function Index, MS-SQL Server의 Include Index 등 다양한 인덱스 활용 최적화 기법을 적용하기 위하여 개발에 몰두하고 있다. 
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------

 

 

인덱스 구조와 스캔 방식을 이해하기


 

CUBRID의 인덱스는 B+-Tree 를 이용하여 인덱스를 구현한다. B+-Tree 는 B-Tree 의 한 종류로 일반적인 B-Tree 와는 달리 데이터 포인터들을 리프(Leaf) 노드에만 저장한다. 리프 노드의 상위 레벨인 넌리프(Non-Leaf) 노드는 전형적인 B-Tree 로 구성되는데, 리프 노드를 빠르게 찾기 위한 인덱스 역할을 한다. 리프 노드에는 키와 키에 대응하는 데이터의 포인터가 저장되어 있다. 리프 노드는 링크드 리스트로 연결되어 있기 때문에 범위 검색과 같은 순차 처리를 편하게 해준다. 그림 1 은 B+-Tree 의 전형적인 구조를 보여준다.

 

pic1.jpg


그림 1 B+-Tree 구조


B+-Tree 의 리프 노드는 서로 연결되어 있어 순차 처리가 가능하기 때문에 범위를 검색하는데 유리하다. 테이블은 처음부터 끝까지 모든 레코드를 읽어야 완전한 결과 집합을 얻을 수 있지만, 인덱스는 키 컬럼 순으로 정렬되어 있기 때문에 특정 위치에서 검색을 시작해서 검색 조건이 일치하지 않는 값을 만나는 순간 멈출 수 있다. 이것을 인덱스 범위 스캔(Index Range Scan)이라고 부른다. CUBRID는 범위 스캔을 B+-Tree 검색의 기본 연산으로 제공한다. 범위 스캔을 위해서는 두 개의 키가 필요한데, 범위의 양 끝을 표현하는 하위 키와 상위 키가 그것이다.

인덱스 범위 스캔은 두 단계로 진행된다. 첫 번째 단계에서는 루트에서부터 트리를 순회하여 리프 노드에서 하위 키를 찾아낸다. 두 번째 단계에서는 첫 번째 단계에서 찾은 키에서부터 상위 키까지 순차적으로 레코드를 읽어 처리한다. 상위 키가 현재 노드에서 발견되지 않으면 다음 노드를 읽어 상위 키를 가진 노드까지 검색을 계속해 나간다. 상위 키까지 순차 검색이 끝나면 전체 범위 검색이 완료된다.
두 번째 단계에서 상위 키까지 찾아가는 과정은 레코드에서 키를 읽어와 상위 키와 비교하는 과정의 연속이다. 상위 키가 최대 키이면 현재 노드의 키부터 마지막 노드까지 모두 검색 결과에 포함되기 때문에 비교 연산을 할 필요가 없어져 검색의 성능이 좋아진다. 이를 위해 옵티마이저는 입력된 쿼리를 재작성(rewrite)하며, CUBRID는 특정 키를 찾는 검색도 범위 검색으로 변환하여 수행한다. 이런 경우에는 하위 키와 상위 키 모두를 찾고자 하는 키로 동일하게 설정한다.

 

인덱스 스캔을 통한 질의 처리 과정을 이해하기


CREATE TABLE tbl (a INT NOT NULL, b STRING, c BIGINT);
CREATE INDEX idx ON tbl (a, b);

그림 2는 CUBRID에서 위의 구문으로 테이블과 인덱스를 생성하고 데이터를 입력한 경우, 인덱스 리프 노드와 테이블 데이터의 관계를 나타낸 그림이다. 왼쪽 인덱스 리프 노드에는 인덱스 키와 키에 대응되는 OID(레코드의 물리적 주소 값)가 저장되어 있다. 

 

pic2.jpg  
그림 2 인덱스 리프 노드와 테이블 데이터의 관계

 

SELECT * FROM tbl WHERE a > 1 AND a < 5 AND b < ‘K’ AND c > 10000 ORDER BY b;

 

위와 같은 SELECT질의가 주어졌을 때 WHERE 절에 있는 검색 조건은 아래의 3가지로 나눌 수 있다. 
 Key Range: 인덱스 스캔 범위로 활용되는 조건이다. (a>1 and a < 5)
 Key Filter: Key Range에 포함될 수 없지만 인덱스 키로 처리 가능한 조건이다. (b < ‘K’)
 Data Filter: 인덱스를 사용할 수 없는 조건이다. 테이블 데이터를 검색하는데 적용된다. (c > 10000)
CUBRID의 질의 처리 과정은 다음과 같다. 
1) 인덱스 스캔인 경우 먼저 Key Range와 Key Filter를 적용하여 조건에 부합하는 OID 리스트를 만들어 낸다. 이 과정은 Key Range의 시작부터 끝까지 계속된다. 
2) OID를 이용해 데이터 페이지에서 해당 레코드를 읽어 Data Filter를 적용하거나 SELECT 리스트에 기술된 컬럼 값을 읽어와 결과를 저장하는 임시 페이지에 기록한다. 
3) ORDER BY나 GROUP BY 절이 있으면 임시 페이지에 저장된 레코드들을 정렬하여 최종 결과를 생성한다. 그림 3은 위의 SELECT 질의가 처리되는 1), 2), 3) 과정을 보여 준다.

 

 

pic3.jpg


 그림 3 인덱스 및 테이블 데이터 검색을 통한 질의 처리 과정

 

인덱스 사용 시 이런 점을 주의하자


옵티마이저가 인덱스를 사용하도록 하기 위해서는 WHERE 절에 Range 조건이 있어야 한다. Range 조건은 값의 비교조건, 즉 크다, 작다, 크거나 같다, 작거나 같다, 같다와 같은 비교문으로 기술된다. 만약 Range 조건이 없다면 옵티마이저는 테이블 순차 스캔을 시도할 것이다. 
또한, WHERE 절에 인덱스 키의 첫 번째 컬럼이 사용되어야만 인덱스 스캔을 수행한다. 인덱스가 여러 컬럼으로 조합되어 있는 경우 많은 사람들이 이중 한가지 컬럼만을 사용하더라도 비교가 가능하다고 생각하는 경우가 있는데, 그것은 잘못된 생각이다. 첫 번째가 없는 상태에서는 두 번째가 정렬된 상태라고 할 수 없기 때문에 범위를 정의할 수 없다. 따라서 반드시 첫 번째 컬럼이 조건에 있어야 하며, 뒤의 컬럼들은 없어도 상관없다. 
인덱스는 값의 대소 비교를 통해 트리가 구성되어 있다. 따라서 값의 대소 비교가 아닌 것은 B+-Tree를 사용해서 값을 찾을 수 없다. <>, != 와 같이 부정형 조건이나 NULL 비교는 인덱스를 사용할 수 없다. 인덱스의 첫 번째 컬럼을 조건절에서 가공하는 경우도 인덱스를 사용할 수 없다. 다음은 인덱스를 사용하지 못하는 질의문의 예이다.

 

SELECT * FROM student WHERE grade <> 'A'; 
SELECT name, email_addr FROM student WHERE email_addr IS NOT NULL; 
SELECT student_id FROM record WHERE substring(yymm, 1, 4) = ‘1997’;

 

인덱스 활용 최적화: 디스크 I/O를 최소화하는 것이 튜닝의 핵심이다!


B+-Tree는 특성상 어떤 리프 페이지든 접근하는데 거의 동일한 비용이 든다. B+-Tree를 사용하는데 가장 큰 비용이 드는 부분은 Key Range의 시작부터 끝까지 인덱스 리프 노드들을 따라 스캔하는 것과 이와 대응되는 테이블 데이터를 스캔하는 것이다.


CUBRID의 I/O는 페이지 단위로 이루어진다. 이것은 하나의 레코드에서 하나의 컬럼만 읽으려 해도 레코드가 속한 페이지 전체를 디스크로부터 읽어온다는 것을 뜻한다. 따라서, 질의 성능을 좌우하는 가장 중요한 성능 지표는 I/O를 수행하는 페이지 개수이며, 이는 옵티마이저의 판단에 가장 큰 영향을 미친다. 옵티마이저가 인덱스를 읽을지, 테이블을 읽을지 결정하는데 있어 가장 중요한 판단 기준은 읽어야 할 레코드가 아니라 읽어야 할 페이지 개수인 것이다.


디스크 I/O는 메모리 액세스에 비해서 비용이 아주 크다. 질의 수행에 필요한 모든 데이터 페이지와 인덱스 페이지를 DB 버퍼에 올려놓고 처리할 수 있다면 좋겠지만 그러기에는 한계가 있다. 결국 디스크 I/O를 최소화 하고 대부분의 연산을 DB 버퍼에서 처리할 수 있도록 질의 처리 과정에서 액세스하는 페이지 수를 최소화시키는 것이 튜닝의 핵심이다. 액세스하는 페이지 수가 적으면 자연스럽게 물리적으로 디스크에서 읽어야 할 페이지 수도 줄어들기 때문에 DB 버퍼 히트율(DB buffer hit ratio)이 높아져서 데이터베이스의 전체적인 성능이 높아지게 된다. 그럼 지금부터 인덱스 스캔 과정에서 액세스해야 할 페이지 수를 줄일 수 있는 기법들에 대해 알아보자.

 

최적화 기법 1. Key Filter 활용


앞서 설명한 바와 같이 Key Filter는 Key Range에는 포함될 수 없지만 인덱스 키로 처리 가능한 조건이다. 이러한 Key Filter가 WHERE 조건절에 포함되면 인덱스 스캔 중에 데이터 페이지에 접근하는 횟수를 줄일 수 있다. 데이터 페이지를 읽는 것은 랜덤 액세스 이기 때문에 인덱스 페이지를 스캔하는 것보다 많은 비용이 든다. 따라서 WHERE절에 Key Filter를 주는 것이 성능에 유리하다.  또한, Data Filter가 Key Filter로 적용될 수 있도록 인덱스에 컬럼을 추가하는 것도 방법이 될 수 있다. 예를 들어 user 테이블에 (groupid, name)으로 구성된 인덱스 idx_1이 있는 상태에서 아래 질의를 수행한다고 가정해 보자.

 

SELECT * FROM user WHERE groupid = 10 AND age > 40;


groupid=10인 조건을 만족하는 레코드가 100건이고 그 중 age>40인 레코드가 10건이라고 하면, 인덱스 스캔으로 100건의 OID를 가져온 후, 최악의 경우 데이터 페이지로 100회의 액세스를 수행할 것이다. 그러나, idx_1 인덱스에 age 컬럼을 추가하여 (groupid, name, age)로 만들면 age > 40 조건이 Key Filter 조건으로 처리되어 인덱스 스캔으로 10건의 OID만 추출할 수 있다.

 

최적화 기법 2. 커버링 인덱스


만약 사용되는 인덱스 내에서 SELECT 질의에 대한 결과를 모두 얻을 수 있는 상황이라면 데이터 페이지에 저장되어 있는 레코드를 읽어오지 않아도 인덱스 키의 값으로만 결과를 만들어 낼 수 있다. MS-SQL Server 에서는 이와 같이 인덱스가 하나의 질의를 모두 “커버”한 경우에 대해서 “커버링 인덱스”라고 한다. CUBRID 2008 R4.0에도 커버링 인덱스가 도입되었다.

 

SELECT a, b FROM tbl WHERE a > 1 AND a < 5 AND b < ‘K’ ORDER BY b;

 

위의 질의는 커버링 인덱스가 적용될 수 있다. 질의에 사용된 컬럼은 a, b 뿐이고 모두 인덱스 컬럼이기 때문이다. 그림 4를 통해 커버링 인덱스에 의해 질의가 처리되어 테이블 데이터 페이지를 액세스 하는 부분이 없는 것을 확인할 수 있다. 대신 인덱스 스캔 결과로 인덱스 키 값을 그대로 Key Buffer에 저장한 후 이 값을 읽어 최종 결과를 만들어 낸다.


pic4.jpg  
그림 4 커버링 인덱스를 활용한 질의 처리 과정

 

커버링 인덱스는 데이터 페이지를 읽지 않는다는 점, 그리고 해당 질의를 자주 사용하게 되면 인덱스가 DB 버퍼에 캐시되어 있을 가능성이 높다는 점에서 디스크 I/O를 줄이는데 큰 역할을 한다. 따라서 레코드 크기에 비해 인덱스 키의 크기가 작고, 커버링 인덱스를 이용하는 질의가 자주 수행되는 것이 확실하다면, 커버링 인덱스를 사용하여 SELECT 질의 성능을 크게 향상시킬 수 있다.

 

최적화 기법 3. Sort 연산 대체


인덱스 스캔을 통해 생성된 결과 집합은 인덱스 컬럼 순으로 정렬된 상태이므로 ORDER BY, GROUP BY절에 의한 정렬 연산을 생략하도록 질의를 작성할 수 있다. 이를 위해서는 인덱스 컬럼의 순서대로 ORDER BY나 GROUP BY 절에 컬럼이 지정되어야 한다. 단 인덱스 컬럼이 조건절에서 ‘=’ 연산자로 동등 비교되는 경우에는, 해당 컬럼이 ORDER BY나 GROUP BY 절에서 중간에 생략되어도 된다. 그림 5는 인덱스 스캔에 의해 GROUP BY 정렬이 생략되는 질의 처리 과정을 보여 준다.

 

SELECT COUNT(*) FROM tbl WHERE a > 1 AND a < 5 AND b < ‘K’ AND c > 10000 GROUP BY a;



 

pic5.jpg 
그림 5 GROUP BY 정렬 최적화된 질의 처리 과정


앞에서 인덱스 스캔을 하기 위해서는 조건절에 인덱스 첫 번째 컬럼이 명시되어야 한다고 설명했다. 하지만 인덱스 컬럼에 NOT NULL 제약 조건이 설정되어 있다면 옵티마이저는 조건절에 인덱스 첫 번째 컬럼이 없더라도 최소 키값과 최대 키값으로 Key Range를 자동으로 추가하여 인덱스 스캔이 가능하도록 최적화한다. 즉, 인덱스 리프 노드의 처음부터 끝까지 스캔하게 되는데, 이를 오라클에서는 인덱스 전체 범위 스캔(Index Full Range Scan) 이라고 부른다.

 

SELECT * FROM tbl WHERE b < ‘K’ ORDER BY a;


이 질의는 옵티마이저에 의해 인덱스 전체 범위 스캔이 수행되는 예이다. CUBRID Manager라는 질의 실행 도구로 해당 질의문의 실행 계획을 확인하면, 그림 6에서처럼 Key Range가 자동으로 추가되어 ORDER BY 정렬 연산이 생략되는 것을 알 수 있다.

 

pic6.jpg 
그림 6 옵티마이저에 의해 정렬 최적화된 질의의 실행 계획

 

최적화 기법 4. LIMIT 최적화


LIMIT 절은 질의의 최종 결과 개수를 제한한다. Data Filter가 없는 질의에 LIMIT 절이 있으면 Key Range에 해당하는 키 값 전부를 스캔할 필요 없이 LIMIT 절에 기술된 개수만큼의 결과를 확보하자 마자 스캔을 중단할 수 있다. 이는 Range의 끝까지 스캔하고 나서 결국은 버리게 되는 페이지를 액세스하지 않기 때문에 불필요한 I/O를 제거할 수 있다.

SELECT * FROM tbl WHERE a = 2 AND b < ‘K’ ORDER BY b LIMIT 3;
이 질의는 LIMIT 최적화에 의해 필요한 결과를 얻은 후 인덱스 스캔이 중단되는 예이다. 만약 a = 2인 인덱스 키가 10페이지에 걸쳐 저장되어 있더라도 LIMIT 절에 명시한 3개의 키 값만 스캔하므로 1개의 페이지만 읽게 된다. 
 

pic7.jpg 
그림 7 LIMIT 최적화된 질의 처리 과정

 

한편, IN 절을 사용한 질의에 대해서도 LIMIT 최적화를 적용할 수 있다. CUBRID는 인덱스 컬럼이 IN 절에 사용되면 Key Range를 IN에 사용된 개수만큼 생성하고, 각각에 대해 인덱스 스캔을 수행한다. 다만, 아래 질의처럼 LIMIT 절에 결과 개수가 명시된 경우, 3번의 인덱스 스캔에 대해 각각 3건의 결과만 획득하고 인덱스 스캔을 중단한다. 즉, 각각의 인덱스 스캔에 대해서 LIMIT 최적화가 적용되는 것이다.

 

SELECT * FROM tbl WHERE a IN (2, 4, 5) AND b < ‘K’ ORDER BY b LIMIT 3;


ORDER BY절은 전체 결과에 대한 정렬을 의미하기 때문에 Key Range가 여러 개이면 각각의 인덱스 스캔 결과를 모아서 다시 정렬을 해야 한다. 하지만 인덱스 스캔의 결과로 정렬을 대체할 수 있는 경우에는 스캔 과정에서 바로 병합(merge)할 수 있다.  CUBRID는 이 과정을 In-Place Sorting 이라고 부른다.
그림 8을 보면서 자세한 설명을 하면, 먼저 첫 번째 range(a = 2 AND b < ‘K’)에 대한 스캔을 통해 3건의 OID를 확보한다. 그 다음 두 번째 range(a = 4 AND b < ‘K’)에 대한 스캔을 시도하는데, 이 range의 첫 번째 키인 (4, ‘DAA’)는 첫 번째 range의 마지막 스캔 키인 (2, ‘CCC’) 보다 b 컬럼의 값이 크기 때문에 바로 스캔을 중단한다. 마찬가지로 다음 세 번째 range인 a = 5 AND b < ‘K’에 대한 스캔에서도 두 번째 키를 읽은 후 바로 스캔을 중단한다. 이처럼 In-Place Sorting 기법은 인덱스 스캔 범위를 더욱 축소하고, 최종 결과에 대한 별도의 정렬을 수행하지 않기 때문에 성능 향상에 많은 도움을 준다.

 

 

 pic8.jpg 
그림 8 In-Place Sorting 기법에 의해 최적화된 질의 처리 과정

 

요약 정리


인덱스가 좋다고 해서 인덱스를 많이 만드는 것이 능사가 아니다. 오히려 인덱스 관리 비용이 증가하고 INSERT, UPDATE, DELETE 성능 저하의 원인이 될 수 있다. 
DB 튜닝의 핵심은 적절한 수의 인덱스를 생성하고 질의가 이 인덱스들을 활용할 수 있도록 질의를 최적화하는 것이다. 이를 위해서는 DBMS에 구현된 인덱스 구조와 다양한 활용 기법들을 이해하고, 질의 패턴과 사용 빈도, I/O 비용, 저장 공간에 대한 비용을 전체적으로 고려하여야 한다.