정보과학 IT

INDEX & JOIN - 인덱스 기본 원리

물곰탱이 2012. 9. 5. 16:52

INDEX & JOIN - 인덱스 기본 원리

 

지금 당장 책장에서 아무 책이나 골라 맨 뒤쪽에 있는 인덱스(색인) 부분을 펼쳐보기 바란다. 가나다순(혹은 ABC 순)으로 정렬되었고, 키워드가 같을 땐 페이지 순으로 정렬된 것을 볼 수 있을 것이다. 인덱스를 이용하면 원하는 키워드를 포함한 페이지를 빠르게 찾을 수 있다. 인덱스가 없다면? 책 전체를 한 장씩 훑어가며 찾는 수밖에 없다. 데이터베이스에서 사용하는 인덱스도 다르지 않다. 대용량 테이블에서 우리에게 필요한 데이터를 빨리 찾으려면 인덱스의 도움이 필요하다. 인덱스가 아예 없거나, 적절한 인덱스를 찾지 못하면 테이블 전체를 읽어야 하기 때문에 시간이 오래 걸리는 것은 당연하다.

 

1. 인덱스 구조

가. 인덱스 기본

 

모든 DBMS는 나름의 다양한 인덱스를 제공하는데, 저장방식과 구조, 탐색 알고리즘이 조금씩 다르긴 해도 원하는 데이터를 빨리 찾도록 돕는다는 근본적인 목적은 같다. 여기서, 가장 일반적으로 사용되는 B*Tree 인덱스 구조부터 살펴보자. 좀 더 다양한 인덱스 구조는 뒤에서 보게 될 것이다.

 

 

[그림 Ⅲ-4-1]에 예시한 인덱스 칼럼은 양의 정수만 저장할 수 있는 데이터 타입이라고 가정하고 그린 것이다. 이름에서 알 수 있듯이 B*Tree 인덱스는 나뭇잎으로 무성한 나무를 뒤집어 놓은 듯한 모습이다. 나무를 뒤집어 놓았으므로 맨 위쪽 뿌리(Root)에서부터 가지(Branch)를 거쳐 맨 아래 나뭇잎(Leaf)까지 연결되는 구조다. 처음에는 단 하나의 루트 블록에서 시작하겠지만 데이터가 점점 쌓이면서 루트, 브랜치, 리프 노드를 모두 갖춘 풍성한 나무로 성장한다. 중간에 물론, 루트와 리프만으로 구성된 2단계 구조를 거친다. 참고로, 루트에서 리프 블록까지의 거리를 인덱스 깊이(Height)라고 부르며, 인덱스를 반복적으로 탐색할 때 성능에 영향을 미친다. 루트와 브랜치 블록은 각 하위 노드들의 데이터 값 범위를 나타내는 키 값과, 그 키 값에 해당하는 블록을 찾는 데 필요한 주소 정보를 가진다. 리프 블록은 인덱스 키 값과, 그 키 값에 해당하는 테이블 레코드를 찾아가는 데 필요한 주소 정보(ROIWD)를 가진다. 키 값이 같을 때는 ROWID 순으로 정렬된다는 사실도 기억하기 바란다. 리프 블록은 항상 인덱스 키(Key) 값 순으로 정렬돼 있기 때문에 ‘범위 스캔(Range Scan, 검색조건에 해당하는 범위만 읽다가 멈추는 것을 말함)’이 가능하고, 정방향(Ascending)과 역방향(Descending) 스캔이 둘 다 가능하도록 양방향 연결 리스트(Double linked list) 구조로 연결돼 있다. 아래는 null 값을 인덱스에 저장하는 데 있어 Oracle과 SQL Server의 차이점을 설명한 것이다.

 

 

 

  • Oracle에서 인덱스 구성 칼럼이 모두 null인 레코드는 인덱스에 저장하지 않는다. 반대로 말하면, 인덱스 구성 칼럼 중 하나라도 null 값이 아닌 레코드는 인덱스에 저장한다.
  • SQL Server는 인덱스 구성 칼럼이 모두 null인 레코드도 인덱스에 저장한다.
  • null 값을 Oracle은 맨 뒤에 저장하고, SQL Server는 맨 앞에 저장한다.

 

 

 

null 값을 처리하는 방식이 이처럼 DBMS마다 다르고, 이런 특성이 null 값 조회에 인덱스가 사용될 수 있는지를 결정하므로 인덱스를 설계하거나 SQL을 개발할 때 반드시 숙지하기 바란다.

 

나. 인덱스 탐색

 

인덱스 탐색 과정을 수직적 탐색과 수평적 탐색으로 나눠서 설명할 수 있다. 수평적 탐색은 인덱스 리프 블록에 저장된 레코드끼리 연결된 순서에 따라 좌에서 우, 또는 우에서 좌로 스캔하기 때문에 ‘수평적’이라고 표현한다. 수직적 탐색은 수평적 탐색을 위한 시작 지점을 찾는 과정이라고 할 수 있으며, 루트에서 리프 블록까지 아래쪽으로 진행하기 때문에 ‘수직적’이다. [그림 Ⅲ-4-1]에서 키 값이 53인 레코드를 찾아보자.

 

① 우선 루트 블록에서 53이 속한 키 값을 찾는다. 두 번째 레코드가 선택될 것이므로 거기서 가리키는 3번 블록으로 찾아간다. ② 3번 블록에서 다시 53이 속한 키 값을 찾는다. 여기서는 첫 번째 레코드가 선택될 것이므로 9번 블록으로 찾아간다. ③ 찾아간 9번은 리프 블록이므로 거기서 값을 찾거나 못 찾거나 둘 중 하나다. 다행히 세 번째 레코드에서 찾아지므로 함께 저장된 ROWID를 이용해 테이블 블록을 찾아간다. ROWID를 분해해 보면, 오브젝트 번호, 데이터 파일번호, 블록번호, 블록 내 위치 정보를 알 수 있다. ④ 테이블 블록에서 레코드를 찾아간다.

 

사실 ④번이 끝은 아니다. [그림 Ⅲ-4-1] 인덱스가 Unique 인덱스가 아닌 한, 값이 53인 레코드가 더 있을 수 있기 때문이다. 따라서 9번 블록에서 레코드 하나를 더 읽어 53인 레코드가 더 있는지 확인한다. 53인 레코드가 더 이상 나오지 않을 때까지 스캔하면서 ④번 테이블 액세스 단계를 반복한다. 만약 9번 블록을 다 읽었는데도 계속 53이 나오면 10번 블록으로 넘어가서 스캔을 계속한다.

 

2. 다양한 인덱스 스캔 방식

가. Index Range Scan

 

Index Range Scan은 [그림 Ⅲ-4-2]처럼 인덱스 루트 블록에서 리프 블록까지 수직적으로 탐색한 후에 리프 블록을 필요한 범위(Range)만 스캔하는 방식이다.

 

 

B*Tree 인덱스의 가장 일반적이고 정상적인 형태의 액세스 방식이라고 할 수 있고, Oracle에서의 실행계획은 다음과 같다.

 

 

 

SQL> create index emp_deptno_idx on emp(deptno); SQL> set autotrace traceonly explain SQL> select * from emp where deptno = 20; Execution Plan ------------------------------------------------------ 0 SELECT STATEMENT Optimizer=ALL_ROWS 1 0 TABLE ACCESS (BY INDEX ROWID) OF 'EMP' (TABLE) 2 1 INDEX (RANGE SCAN) OF 'EMP_DEPTNO_IDX' (INDEX)

 

 

 

SQL Server에서는 Index Seek라고 표현하며, 실행계획은 다음과 같다.

 

 

 

StmtText ------------------------------------------------------------- |--Nested Loops(Inner Join, OUTER REFERENCES:([Bmk1000])) |--Index Seek(OBJECT:([..].[dbo].[emp].[emp_deptno_idx]), SEEK:([deptno]=20) ORDERED FORWARD) |--RID Lookup(OBJECT:([..].[dbo].[emp]), SEEK:([Bmk1000]=[Bmk1000]) LOOKUP ORDERED FORWARD)

 

 

 

참고로, 2000 이전 버전의 실행계획에는 다음과 같이 표시된---------------------------------------------------- |--Bookmark Lookup(BOOKMARK:([Bmk1000]), OBJECT:([..].[dbo].[emp])) |--Index Seek(OBJECT:([..].[dbo].[emp].[emp_deptno_idx]), SEEK:([deptno] = 20) ORDERED FORWARD)

 

 

 

인덱스를 수직적으로 탐색한 후에 리프 블록에서 “필요한 범위”만 스캔한다고 했는데, 이는 범위 스캔(Range Scan)이 의미하는 바를 잘 설명해 주고 있다. 데이터베이스 프로그래밍에 경험이 많지 않은 초급 개발자는 대개 인덱스가 사용되는 실행계획을 보면 자신이 작성한 SQL문에 문제가 없다고 판단하고 일단 안심한다. 하지만 실행계획 상에 Index Range Scan이 나타난다고 해서 항상 빠른 속도를 보장하는 것은 아니다. 인덱스를 스캔하는 범위(Range)를 얼마만큼 줄일 수 있느냐, 그리고 테이블로 액세스하는 횟수를 얼마만큼 줄일 수 있느냐가 관건이며, 이는 인덱스 설계와 SQL 튜닝의 핵심 원리 중 하나이다. Index Range Scan이 가능하게 하려면 인덱스를 구성하는 선두 칼럼이 조건절에 사용되어야 한다. 그렇지 못한 상황에서 인덱스를 사용하도록 힌트로 강제한다면 바로 이어서 설명할 Index Full Scan 방식으로 처리된다. Index Range Scan 과정을 거쳐 생성된 결과집합은 인덱스 칼럼 순으로 정렬된 상태가 되기 때문에 이런 특징을 잘 이용하면 sort order by 연산을 생략하거나 min/max 값을 빠르게 추출할 수 있다.

 

나. Index Full Scan

 

Index Full Scan은 수직적 탐색없이 인덱스 리프 블록을 처음부터 끝까지 수평적으로 탐색하는 방식으로서, 대개는 데이터 검색을 위한 최적의 인덱스가 없을 때 차선으로 선택된다.

 

 

아래는 Oracle에서 Index Full Scan할 때의 실행계획이다.

 

 

 

SQL> create index emp_idx on emp (ename, sal); SQL> set autotrace traceonly exp SQL> select * from emp 2 where sal > 2000 3 order by ename; Execution Plan ---------------------------------------------------------- 0 SELECT STATEMENT Optimizer=ALL_ROWS 1 0 TABLE ACCESS (BY INDEX ROWID) OF 'EMP' (TABLE) 2 1 INDEX (FULL SCAN) OF 'EMP_IDX' (INDEX)

 

 

 

SQL Server에서는 Index Scan이라고 표현하며, 실행계획은 다음과 같다.

 

 

 

StmtText ------------------------------------------------------------- |--Filter(WHERE:([..].[dbo].[emp].[sal]>(2000.))) |--Nested Loops(Inner Join, OUTER REFERENCES:([Bmk1000])) |--Index Scan(OBJECT:([..].[dbo].[emp].[emp_idx]), ORDERED FORWARD) |--RID Lookup(OBJECT:([..].[dbo].[emp]), SEEK:([Bmk1000]=[Bmk1000]) LOOKUP ORDERED FORWARD)

 

 

 

참고로, 2000 이전 버전의 실행계획에는 다음과 같이 표시된다.

 

 

 

StmtText ------------------------------------------------------------- |--Bookmark Lookup(BOOKMARK:([Bmk1000]), OBJECT:([..].[dbo].[emp])) |--Index Scan(OBJECT:([..].[dbo].[emp].[emp_idx1]), WHERE:([sal] > 2000) ORDERED FORWARD)

 

 

 

수직적 탐색없이 인덱스 리프 블록을 처음부터 끝까지 수평적으로만 탐색한다고 했는데, 이는 개념적으로 설명하기 위한 것일 뿐 실제로는 [그림 Ⅲ-4-3]처럼 수직적 탐색이 먼저 일어난다. 루트 블록과 브랜치 블록을 거치지 않고는 가장 왼쪽에 위치한 첫 번째 리프 블록으로 찾아갈 방법이 없기 때문이다. 그래서 이 과정을 [그림 Ⅲ-4-3]에 점선으로 표시했다.

 

 

 

  • Index Full Scan의 효용성

 

 

 

위 SQL처럼 인덱스 선두 칼럼(ename)이 조건절에 없으면 옵티마이저는 우선적으로 Table Full Scan을 고려한다. 그런데 대용량 테이블이어서 Table Full Scan의 부담이 크다면 옵티마이저는 인덱스를 활용하는 방법을 다시 생각해 보지 않을 수 없다. 데이터 저장공간은 ‘가로×세로’ 즉, ‘칼럼길이×레코드수’에 의해 결정되므로 대개 인덱스가 차지하는 면적은 테이블보다 훨씬 적게 마련이다. 만약 인덱스 스캔 단계에서 대부분 레코드를 필터링하고 일부에 대해서만 테이블 액세스가 발생하는 경우라면 테이블 전체를 스캔하는 것보다 낫다. 이럴 때 옵티마이저는 Index Full Scan 방식을 선택할 수 있다. 아래는 Index Full Scan이 효과를 발휘하는 전형적인 케이스다.

 

 

 

SQL> select * from emp where sal > 5000 order by ename; Execution Plan -------------------------------------------------- 0 SELECT STATEMENT Optimizer=ALL_ROWS 1 0 TABLE ACCESS (BY INDEX ROWID) OF 'EMP' (TABLE) 2 1 INDEX (FULL SCAN) OF 'EMP_IDX' (INDEX)

 

 

 

 

[그림 Ⅲ-4-4]처럼 연봉이 5,000을 초과하는 사원이 전체 중 극히 일부라면 Table Full Scan보다는 Index Full Scan을 통한 필터링이 큰 효과를 가져다준다. 하지만 이런 방식은 적절한 인덱스가 없어 Index Range Scan의 차선책으로 선택된 것이므로, 할 수 있다면 인덱스 구성을 조정해 주는 것이 좋다.

 

 

 

  • 인덱스를 이용한 소트 연산 대체

 

 

 

Index Full Scan은 Index Range Scan과 마찬가지로 그 결과집합이 인덱스 칼럼 순으로 정렬되므로 Sort Order By 연산을 생략할 목적으로 사용될 수도 있는데, 이는 차선책으로 선택됐다기보다 옵티마이저가 전략적으로 선택한 경우에 해당한다.

 

 

 

SQL> select /*+ first_rows */ * from emp 2 where sal > 1000 3 order by ename; Execution Plan -------------------------------------------------- 0 SELECT STATEMENT Optimizer=HINT: FIRST_ROWS 1 0 TABLE ACCESS (BY INDEX ROWID) OF 'EMP' (TABLE) 2 1 INDEX (FULL SCAN) OF 'EMP_IDX' (INDEX)

 

 

 

 

[그림 Ⅲ-4-5]에서 대부분 사원의 연봉이 1,000을 초과하므로 Index Full Scan을 하면 거의 모든 레코드에 대해 테이블 액세스가 발생해 Table Full Scan 보다 오히려 불리하다. 만약 SAL이 인덱스 선두 칼럼이어서 Index Range Scan 하더라도 마찬가지다. 그럼에도 여기서 인덱스가 사용된 것은 사용자가 first_rows 힌트(SQL Server에서는 fastfirstrow 힌트)를 이용해 옵티마이저 모드를 바꾸었기 때문이다. 즉, 옵티마이저는 소트 연산을 생략함으로써 전체 집합 중 처음 일부만을 빠르게 리턴할 목적으로 Index Full Scan 방식을 선택한 것이다. 사용자가 그러나 처음 의도와 다르게 데이터 읽기를 멈추지 않고 끝까지 fetch 한다면 Full Table Scan한 것보다 훨씬 더 많은 I/O를 일으키면서 서버 자원을 낭비할 텐데, 이는 옵티마이저의 잘못이 결코 아니며 first_rows 힌트를 사용한 사용자에게 책임이 있다.

 

다. Index Unique Scan

 

Index Unique Scan은 [그림 Ⅲ-4-6]처럼 수직적 탐색만으로 데이터를 찾는 스캔 방식으로서, Unique 인덱스를 ‘=’ 조건으로 탐색하는 경우에 작동한다.

 

 

아래는 Oracle에서 Index Unique Scan할 때의 실행계획이다.

 

 

 

SQL> create unique index pk_emp on emp(empno); SQL> alter table emp add 2 constraint pk_emp primary key(empno) using index pk_emp; SQL> set autotrace traceonly explain SQL> select empno, ename from emp where empno = 7788; Execution Plan ----------------------------------------------- 0 SELECT STATEMENT Optimizer=ALL_ROWS 1 0 TABLE ACCESS (BY INDEX ROWID) OF 'EMP' 2 1 INDEX (UNIQUE SCAN) OF 'PK_EMP' (UNIQUE)

 

 

 

SQL Server 실행계획에는 Oracle의 Range Scan과 Unique Scan을 구분하지 않고 똑같이 Index Seek라고 표시한다.

 

 

 

StmtText ------------------------------------------------------------- |--Nested Loops(Inner Join, OUTER REFERENCES:([Bmk1000])) |--Index Seek(OBJECT:([..].[dbo].[emp].[pk_emp]), SEEK:([empno]=7788) ORDERED FORWARD) |--RID Lookup(OBJECT:([..].[dbo].[emp]), SEEK:([Bmk1000]=[Bmk1000]) LOOKUP ORDERED FORWARD)

 

 

 

참고로, 2000 이전 버전의 실행계획에는 다음과 같이 표시된다.

 

 

 

StmtText ------------------------------------------------------------- |--Bookmark Lookup(BOOKMARK:([Bmk1000]), OBJECT:([..].[dbo].[emp])) |--Index Seek(OBJECT:([..].[dbo].[emp].[pk_emp1]), SEEK:([empno] = 7788) ORDERED FORWARD)

 

 

 

라. Index Skip Scan

 

인덱스 선두 칼럼이 조건절로 사용되지 않으면 옵티마이저는 기본적으로 Table Full Scan을 선택한다. 또는, Table Full Scan보다 I/O를 줄일 수 있거나 정렬된 결과를 쉽게 얻을 수 있다면 Index Full Scan 방식을 사용한다고 했다. Oracle은 인덱스 선두 칼럼이 조건절에 빠졌어도 인덱스를 활용하는 새로운 스캔방식을 9i 버전에서 선보였는데, 바로 Index Skip Scan이 그것이다.([그림 Ⅲ-4-7] 참조).

 

 

예를 들어, 성별과 연봉 두 칼럼으로 구성된 결합 인덱스에서 선두 칼럼인 성별 조건이 빠진 SQL문이 Index Skip Scan 방식으로 수행될 때의 실행계획은 다음과 같다.

 

 

 

SQL> select * from 사원 where 연봉 between 2000 and 4000; Execution Plan -------------------------------------------------- 0 SELECT STATEMENT Optimizer=ALL_ROWS 1 0 TABLE ACCESS (BY INDEX ROWID) OF '사원' (TABLE) 2 1 INDEX (SKIP SCAN) OF '사원_IDX' (INDEX)

 

 

 

Index Skip Scan 내부 수행원리를 간단히 요약하면, 루트 또는 브랜치 블록에서 읽은 칼럼 값 정보를 이용해 조건에 부합하는 레코드를 포함할 “가능성이 있는” 하위 블록(브랜치 또는 리프 블록)만 골라서 액세스하는 방식이라고 할 수 있다. 이 스캔 방식은 조건절에 빠진 인덱스 선두 칼럼의 Distinct Value 개수가 적고 후행 칼럼의 Distinct Value 개수가 많을 때 유용하다.

 

 

 

Index Skip Scan에 의존하는 대신, 아래와 같이 성별 값을 In-List로 제공해 주면 어떨까? SQL> select * from 사원 2 where 연봉 between 2000 and 4000 3 and 성별 in ('남', '여') Execution Plan -------------------------------------------------- 0 SELECT STATEMENT Optimizer=ALL_ROWS 1 0 INLIST ITERATOR 2 1 TABLE ACCESS (BY INDEX ROWID) OF '사원' (TABLE) 3 2 INDEX (RANGE SCAN) OF '사원_IDX' (INDEX)

 

 

 

실행계획 1번 단계(ID=1)에 INLIST ITERATOR라고 표시된 부분은 조건절 In-List에 제공된 값의 종류만큼 인덱스 탐색을 반복 수행함을 뜻한다. 이렇게 쿼리 작성자가 직접 성별에 대한 조건식을 추가해 주면 Index Skip Scan에 의존하지 않고도 빠르게 결과집합을 얻을 수 있다. 단, 이처럼 In-List를 명시하려면 성별 값의 종류가 더 이상 늘?이 효과를 발휘하려면 In-List로 제공하는 값의 종류가 적어야 한다. In-List를 제공하는 튜닝 기법을 익히 알던 독자라면, Index Skip Scan이 옵티마이저가 내부적으로 In-List를 제공해 주는 방식이라고 생각하기 쉽지만 내부 수행 원리는 전혀 다르다.

 

마. Index Fast Full Scan

 

말 그대로 Index Fast Full Scan은 Index Full Scan보다 빠르다. Index Fast Full Scan이 Index Full Scan보다 빠른 이유는, 인덱스 트리 구조를 무시하고 인덱스 세그먼트 전체를 Multiblock Read 방식으로 스캔하기 때문이다. Index Full Scan과의 차이점을 요약하면 [표 Ⅲ-4-1]과 같다.

 

 

바. Index Range Scan Descending

 

Index Range Scan과 기본적으로 동일한 스캔 방식이다. [그림 Ⅲ-4-8]처럼 인덱스를 뒤에서부터 앞쪽으로 스캔하기 때문에 내림차순으로 정렬된 결과집합을 얻는다는 점만 다르다.

 

 

아래 처럼 emp 테이블을 empno 기준으로 내림차순 정렬하고자 할 때 empno 칼럼에 인덱스가 있으면 옵티마이저가 알아서 인덱스를 거꾸로 읽는 실행계획을 수립한다.

 

 

 

SQL> select * from emp 2 where empno is not null 3 order by empno desc Execution Plan ------------------------------------------------------------- 0 SELECT STATEMENT Optimizer=ALL_ROWS 1 0 TABLE ACCESS (BY INDEX ROWID) OF 'EMP' (TABLE) 2 1 INDEX (RANGE SCAN DESCENDING) OF 'PK_EMP' (INDEX (UNIQUE))

 

 

 

SQL Server에서의 실행계획은 다음과 같다.

 

 

 

StmtText ------------------------------------------------------------- |--Nested Loops(Inner Join, OUTER REFERENCES:([Bmk1000])) |--Index Scan(OBJECT:([..].[dbo].[emp].[pk_emp]), ORDERED BACKWARD) |--RID Lookup(OBJECT:([..].[dbo].[emp]), SEEK:([Bmk1000]=[Bmk1000]) LOOKUP ORDERED FORWARD)

 

 

 

아래 처럼 max 값을 구하고자 할 때도 해당 칼럼에 인덱스가 있으면 인덱스를 뒤에서부터 한 건만 읽고 멈추는 실행계획이 자동으로 수립된다.

 

 

 

SQL> create index emp_x02 on emp(deptno, sal); SQL> select deptno, dname, loc 2 ,(select max(sal) from emp where deptno = d.deptno) 3 from dept d Execution Plan ------------------------------------------------------------- 0 SELECT STATEMENT Optimizer=ALL_ROWS 1 0 SORT (AGGREGATE) 2 1 FIRST ROW 3 2 INDEX (RANGE SCAN (MIN/MAX)) OF 'EMP_X02' (INDEX) 4 0 TABLE ACCESS (FULL) OF 'DEPT' (TABLE)

 

 

 

3. 인덱스 종류

 

가. B*Tree 인덱스

 

모든 DBMS가 B*Tree 인덱스를 기본적으로 제공하며, 추가적으로 제공하는 인덱스 구조는 모두 B*Tree 인덱스의 단점을 보완하기 위해 개발된 것들이다. B*Tree 인덱스 구조와 다양한 스캔 방식에 대해서는 이미 설명하였다. 뒤에서 튜닝 원리를 설명할 때도 계속 B*Tree를 기준으로 설명할 것이므로 여기서는 B*Tree 인덱스 구조에서 나타날 수 있는 Index Fragmentation에 대한 개념만 잠시 살펴보기로 하자.

 

1) Unbalanced Index

 

delete 작업 때문에 인덱스가 [그림 Ⅲ-4-9]처럼 불균형(Unbalanced) 상태에 놓일 수 있다고 설명한 자료들을 볼 수 있다. 즉 다른 리프 노드에 비해 루트 블록과의 거리가 더 멀거나 가까운 리프 노드가 생길 수 있다는 것인데, B*Tree 구조에서 이런 현상은 절대 발생하지 않는다.

 

 

B*Tree 인덱스의 ‘B’는 ‘Balanced’의 약자로서, 인덱스 루트에서 리프 블록까지 어떤 값으로 탐색하더라도 읽는 블록 수가 같음을 의미한다. 즉, 루트로부터 모든 리프 블록까지의 높이(height)가 동일하다.

 

2) Index Skew

 

불균형(Unbalanced)은 생길 수 없지만 Index Fragmentation에 의한 Index Skew 또는 Sparse 현상이 생기는 경우는 종종 있고, 이는 인덱스 스캔 효율에 나쁜 영향을 미칠 수 있다. Index Skew는 인덱스 엔트리가 왼쪽 또는 오른쪽에 치우치는 현상을 말한다. 예를 들어, 아래와 같이 대량의 delete 작업을 마치고 나면 [그림 Ⅲ-4-10]처럼 인덱스 왼쪽에 있는 리프 블록들은 텅 비는 반면 오른쪽은 꽉 찬 상태가 된다.

 

 

 

SQL> create table t as select rownum no from big_table where rownum <= 1000000 ; SQL> create index t_idx on t(no) ; SQL> delete from t where no <= 500000 ; SQL> commit;

 

 

 

 

Oracle의 경우, 텅 빈 인덱스 블록은 커밋하는 순간 freelist로 반환되지만 인덱스 구조 상에는 그대로 남는다. 상위 브랜치에서 해당 리프 블록을 가리키는 엔트리가 그대로 남아 있어 인덱스 정렬 순서상 그 곳에 입력될 새로운 값이 들어오면 언제든 재사용될 수 있다. 새로운 값이 하나라도 입력되기 전 다른 노드에 인덱스 분할이 발생하면 그것을 위해서도 이들 블록이 재사용된다. 이때는 상위 브랜치에서 해당 리프 블록을 가리키는 엔트리가 제거돼 다른 쪽 브랜치의 자식 노드로 이동하고, freelist에서도 제거된다. 레코드가 모두 삭제된 블록은 이처럼 언제든 재사용 가능하지만, 문제는 다시 채워질 때까지 인덱스 스캔 효율이 낮다는 데에 있다. SQL Server에선 Index Skew 현상이 발생하지 않는다. 주기적으로 B*Tree 인덱스를 체크함으로써 지워진 레코드와 페이지를 정리해 주는 메커니즘을 갖기 때문이다. 인덱스 레코드를 지우면 리프??코드’로 마크(mark)되었다가 이를 정리해 주는 별도 쓰레드에 의해 비동기 방식으로 제거되는데, 그 과정에서 텅 빈 페이지가 발견되면 인덱스 구조에서 제거된다.

 

3) Index Sparse

 

Index Sparse는 [그림 Ⅲ-4-11]처럼 인덱스 블록 전반에 걸쳐 밀도(density)가 떨어지는 현상을 말한다.

 

 

예를 들어, 아래와 같은 형태로 delete 작업을 수행하고 나면 t_idx 블록의 밀도는 50% 정도 밖에 되질 않는다. 100만 건 중 50만 건을 지우고 나서도 스캔한 인덱스 블록 수가 똑같이 2,001개인 것을 확인하기 바란다.

 

 

 

SQL> create table t as select rownum no from big_table where rownum <= 1000000 ; SQL> create index t_idx on t(no) ; SQL> select /*+ index(t) */ count(*) from t where no > 0; COUNT(*) ---------- 1000000 Statistics ---------------------------------------------------------- 0 recursive calls 0 db block gets 2001 consistent gets … …… SQL> delete from t where mod(no, 10) < 5 ; 500000 행이 삭제되었습니다. SQL> commit; SQL> select /*+ index(t) */ count(*) from t where no > 0; COUNT(*) ---------- 500000 Statistics ---------------------------------------------------------- 0 recursive calls 0 db block gets 2001 consistent gets … ……

 

 

 

지워진 자리에 인덱스 정렬 순서에 따라 새로운 값이 입력되면 그 공간은 재사용되지만 위와 같은 대량의 delete 작업이 있고 난 후 한동안 인덱스 스캔 효율이 낮다는 데에 문제가 있다. 왼쪽, 오른쪽, 중간 어디든 Index Skew처럼 블록이 아예 텅 비면 곧바로 freelist로 반환돼 언제든 재사용되지만, Index Sparse는 지워진 자리에 새로운 값이 입력되지 않으면 영영 재사용되지 않을 수도 있다. 총 레코드 건수가 일정한데도 인덱스 공간 사용량이 계속 커지는 것은 대개 이런 현상에 기인한다.

 

4) 인덱스 재생성

 

Fragmentation 때문에 인덱스 크기가 계속 증가하고 스캔 효율이 나빠지면 인덱스를 재생성하거나 DBMS가 제공하는 명령어를 이용해 빈 공간을 제거하는 것이 유용할 수 있다. 하지만 일반적으로 인덱스 블록에는 어느 정도 공간을 남겨두는 것이 좋다. 왜냐하면, 빈 공간을 제거해 인덱스 구조를 슬림(slim)화하면 저장 효율이나 스캔 효율엔 좋겠지만 인덱스 분할이 자주 발생해 DML 성능이 나빠질 수 있기 때문이다. 인덱스 분할에 의한 경합을 줄일 목적으로, 초기부터 빈 공간을 남기도록 옵션을 주고 인덱스를 재성성할 수도 있다. 하지만 그 효과는 일시적이다. 언젠가 빈 공간이 다시 채워지기 때문이며, 결국 적당한 시점마다 재생성 작업을 반복하지 않는 한 근본적인 해결책이 되지는 못한다. 인덱스를 재생성하는 데 걸리는 시간과 부하도 무시할 수 없다. 따라서 인덱스의 주기적인 재생성 작업은 아래와 같이 예상효과가 확실할 때만 시행하는 것이 바람직하다.

 

 

 

  • 인덱스 분할에 의한 경합이 현저히 높을 때
  • 자주 사용되는 인덱스 스캔 효율을 높이고자 할 때. 특히 NL Join에서 반복 액세스되는 인덱스 높이(height)가 증가했을 때
  • 대량의 delete 작업을 수행한 이후 다시 레코드가 입력되기까지 오랜 기간이 소요될 때
  • 총 레코드 수가 일정한데도 인덱스가 계속 커질 때

 

나. 비트맵 인덱스

 

Oracle은 비트맵(Bitmap) 인덱스 구조를 제공하며, [그림 Ⅲ-4-12]를 보면 그 구조를 쉽게 이해할 수 있다. [그림 Ⅲ-4-12] 처럼 상품 테이블에 10개 레코드가 있고, 색상으로는 RED, GREEN, BLUE가 입력돼 있다고 하자. 8번 상품에는 색상이 입력되지 않았다.

 

 

[그림 Ⅲ-4-12] 아래쪽은 색상 칼럼에 생성한 비트맵 인덱스를 표현한 것인데, 키 값이 BLUE인 첫 번째 행을 보면 4번째, 7번째, 9번째 비트가 1로 설정돼 있다. 따라서 상응하는 테이블 레코드의 색상 값이 ‘BLUE’임을 뜻한다. 비트맵 인덱스는 부정형 조건에도 사용할 수 있는데, [그림 Ⅲ-4-12]에서 ‘BLUE’가 아닌 값을 찾으려면 인덱스 첫 번째 행에서 0으로 설정된 비트만 찾으면 된다. Oracle B*Tree 인덱스와 달리 비트맵 인덱스는 NULL도 저장하기 때문에 아래와 같은 조건에도 사용할 수 있다.

 

 

 

select * from 상품 where 색상 is null

 

 

 

[그림 Ⅲ-4-12]처럼 칼럼의 Distinct Value 개수가 적을 때 비트맵 인덱스를 사용하면 저장효율이 매우 좋다. B*Tree 인덱스보다 훨씬 적은 용량을 차지하므로 인덱스가 여러 개 필요한 대용량 테이블에 유용하다. 다양한 분석관점(Dimension)을 가진 팩트성 테이블이 주로 여기에 속한다. 반대로 Distinct Value가 아주 많은 칼럼이면 오히려 B*Tree 인덱스보다 많은 공간을 차지한다. Distinct Value 개수가 적은 칼럼일 때 저장효율이 좋지만 테이블 Random 액세스 발생 측면에서는 B*Tree 인덱스와 똑같기 때문에 그런 칼럼을 비트맵 인덱스로 검색하면 그다지 좋은 성능을 기대하기 어렵다. 스캔할 인덱스 블록이 줄어드는 정도의 성능 이점만 얻을 수 있고, 따라서 하나의 비트맵 인덱스 단독으로는 쓰임새가 별로 없다. 그 대신, 여러 비트맵 인덱스를 동시에 사용할 수 있는 특징 때문에 대용량 데이터 검색 성능을 향상시키는 데에 효과가 있다. 예컨대, 아래와 같은 쿼리에 여러 개 비트맵 인덱스로 Bitwise 연산을 수행한 결과, 테이블 액세스량이 크게 줄어든다면 큰 성능 개선을 기대할 수 있다.

 

 

 

select 지역, sum(판매량), sum(판매금액) from 연도별지역별상품매출 where (크기 = 'SMALL' or 크기 is null) and 색상 = 'GREEN' and 출시연도 = '2010' group by 지역

 

 

 

비트맵 인덱스는 여러 인덱스를 동시에 활용할 수 있다는 장점 때문에 다양한 조건절이 사용되는, 특히 정형화되지 않은 임의 질의(ad-hoc query)가 많은 환경에 적합하다. 다만, 비트맵 인덱스는 Lock에 의한 DML 부하가 심한 것이 단점이다. 레코드 하나만 변경되더라도 해당 비트맵 범위에 속한 모든 레코드에 Lock이 걸린다. OLTP성 환경에 비트맵 인덱스를 쓸 수 없는 이유가 여기에 있다. 지금까지 설명한 특징을 고려할 때 비트맵 인덱스는 읽기 위주의 대용량 DW(특히, OLAP) 환경에 아주 적합하다.

 

다. 함수기반 인덱스

 

Oracle이 제공하는 함수기반 인덱스(Function Based Index, FBI)는 칼럼 값 자체가 아닌, 칼럼에 특정 함수를 적용한 값으로 B*Tree 인덱스를 만든다. 주문수량이 100보다 작거나 NULL인 주문 건을 찾는 아래 쿼리를 예로 들어 보자.

 

 

select * from 주문 where nvl(주문수량, 0) < 100

 

 

주문수량 칼럼에 인덱스가 있어도 위처럼 인덱스 칼럼을 가공하면 정상적인 인덱스 사용이 불가능하다. 하지만 조건절과 똑같이 NVL 함수를 씌워 아래 처럼 인덱스를 만들면 인덱스 사용이 가능하다. 주문수량이 NULL인 레코드는 인덱스에 0으로 저장된다.

 

 

create index emp_x01 on emp( nvl(주문수량, 0) );

 

 

이 외에도 함수기반 인덱스가 유용한 가장 흔한 사례는, 대소문자를 구분해서 입력 받은 데이터를 대소문자 구분 없이 조회할 때다. upper(칼럼명) 함수를 씌워 인덱스를 생성하고 upper(칼럼명) 조건으로 검색하는 것이다. 함수기반 인덱스는 데이터 입력, 수정 시 함수를 적용해야 하기 때문에 다소 부하가 있을 수 있으며, 사용된 함수가 사용자 정의 함수일 때는 부하가 더 심하다. 따라서 남용하지 말고 꼭 필요한 때만 사용하기 바란다.

 

라. 리버스 키 인덱스

 

일련번호나 주문일시 같은 칼럼에 인덱스를 만들면, 입력되는 값이 순차적으로 증가하기 때문에 [그림 Ⅲ-4-13]처럼 가장 오른쪽 리프 블록에만 데이터가 쌓인다. 이런 현상이 발생하는 인덱스를 흔히 ‘Right Growing(또는 Right Hand) 인덱스’라고 부르며, 동시 INSERT가 심할 때 인덱스 블록 경합을 일으켜 초당 트랜잭션 처리량을 크게 감소시킨다.

 

 

그럴 때 리버스 키 인덱스(Reverse Key Index)가 유용할 수 있는데, 이것은 말 그대로 입력된 키 값을 거꾸로 변환해서 저장하는 인덱스다. 조금 전에 설명한 함수기반 인덱스를 상기하면서, 아래와 같이 reverse 함수에서 반환된 값을 저장하는 인덱스라고 생각하면 쉽다.

 

 

 

create index 주문_x01 on 주문( reverse(주문일시) );

 

 

 

순차적으로 입력되는 값을 거꾸로 변환해서 저장하면 [그림 Ⅲ-4-14]처럼 데이터가 고르게 분포한다. 따라서 리프 블록 맨 우측에만 집중되는 트랜잭션을 리프 블록 전체에 고르게 분산시키는 효과를 얻을 수 있다.

 

 

하지만, 리버스 키 인덱스는 데이터를 거꾸로 입력하기 때문에 ‘=’ 조건으로만 검색이 가능하다. 즉, 부등호나 between, like 같은 범위검색 조건에는 사용할 수 없다.

 

마. 클러스터 인덱스

 

Oracle에는 클러스터 테이블(Clustered Table)이라는 오브젝트가 있다. 클러스터 테이블에는 인덱스 클러스터와 해시 클러스터 두 가지가 있는데, 지금 설명하려는 클러스터 인덱스는 인덱스 클러스터와 관련이 있다. 인덱스 클러스터 테이블은 [그림 Ⅲ-4-15]처럼 클러스터 키(여기서는 deptno) 값이 같은 레코드가 한 블록에 모이도록 저장하는 구조를 사용한다. 한 블록에 모두 담을 수 없을 때는 새로운 블록을 할당해 클러스터 체인으로 연결한다.

 

 

심지어 여러 테이블 레코드가 물리적으로 같은 블록에 저장되도록 클러스터를 할당할 수도 있다(다중 테이블 인덱스 클러스터). 여러 테이블을 서로 조인된 상태로 저장해 두는 것인데, 일반적으로는 하나의 데이터 블록이 여러 테이블에 의해 공유될 수 없음을 상기하기 바란다. (SQL Server에서는 가능한데, 1장에서 설명한 혼합 익스텐트를 참조하라.) Oracle에서 인덱스 클러스터를 만들고, 거기에 클러스터 인덱스를 정의하는 방법은 다음과 같다.

 

 

 

SQL> create cluster c_deptno# ( deptno number(2) ) index ; SQL> create index i_deptno# on cluster c_deptno#;

 

 

 

방금 생성한 클러스터에 아래와 같이 테이블을 담기만 하면 된다.

 

 

 

SQL> create table emp 2 cluster c_deptno# (deptno) 3 as 4 select * from scott.emp;

 

 

 

클러스터 인덱스도 일반적인 B*Tree 인덱스 구조를 사용하지만, 해당 키 값을 저장하는 첫 번째 데이터 블록만 가리킨다는 점에서 다르다. 클러스터 인덱스의 키 값은 항상 Unique(중복 값이 없음)하며, [그림 Ⅲ-4-15]에서 보듯 테이블 레코드와 1:M 관계를 갖는다. 일반 테이블에 생성한 인덱스 레코드는 테이블 레코드와 1:1 대응 관계를 갖는다는 사실을 상기하기 바란다. 이런 구조적 특성 때문에 클러스터 인덱스를 스캔하면서 값을 찾을 때는 Random 액세스가 (클러스터 체인을 스캔하면서 발생하는 Random 액세스는 제외하고) 값 하나당 한 번씩만 발생한다. 클러스터에 도달해서는 Sequential 방식으로 스캔하기 때문에 넓은 범위를 검색할 때 유리하다. 새로운 값이 자주 입력(→ 새 클러스터 할당)되거나 수정이 자주 발생하는 칼럼(→ 클러스터 이동)은 클러스터 키로 선정하지 않는 것이 좋다.

 

바. 클러스터형 인덱스/IOT

 

SQL Server에서 지원되는 인덱스로는 클러스터형 인덱스(Clustered Index)와 비클러스터형 인덱스(Non-Clustered Index) 2가지가 있다. 비클러스터형 인덱스는 지금까지 설명한 B*Tree 인덱스와 100% 같으므로 따로 설명하지 않겠다.

 

1) 클러스터형 인덱스/IOT 구조

 

클러스터형 인덱스도 구조적으로는 B*Tree 인덱스와 같은 형태다. 차이가 있다면 별도의 테이블을 생성하지 않고 모든 행 데이터를 인덱스 리프 페이지에 저장한다는 점이다. [그림 Ⅲ-4-16] 우측에서 보듯, “인덱스 리프 페이지가 곧 데이터 페이지”인 셈이다.

 

 

일반적인 힙 구조 테이블에 데이터를 삽입할 때는 정해진 순서 없이 Random 방식으로 이루어진다. 반면, 클러스터형 인덱스는 정렬 상태를 유지하며 데이터를 삽입한다. 따라서 클러스터형 인덱스는 테이블마다 단 하나만 생성할 수 있다. 한 테이블이 두 개의 정렬 순서를 가질 수 없으므로 너무나 당연한 제약이다. 테이블에 클러스터형 인덱스를 생성하면 항상 정렬된 상태를 유지해야 하기 때문에 데이터 입력 시 성능이 느린 단점을 갖는다. 비클러스터형 인덱스를 생성해도 정렬을 유지해야 한다는 점은 같지만, 클러스터형 인덱스는 인덱스 키 값 외에도 많은 데이터를 리??(Split)이 자주 발생하고, 이 때문에 DML 부하가 더 심하게 발생한다. 이런 단점에도 불구하고 클러스터형 인덱스를 사용하는 이유는, 넓은 범위의 데이터를 검색할 때 유리하기 때문이다. 이런 특징은, 같은 값을 가진 레코드가 100% 정렬된 상태로 모여 있고 리프 레벨이 곧 데이터 페이지라는 데서 나온다. 즉, 정렬된 리프 페이지를 Sequential 방식으로 스캔하면서 검색 값을 모두 찾을 수 있고, 찾은 레코드에 대해서는 추가적인 테이블 Random 액세스가 필요하지 않다. 클러스터형 인덱스를 Oracle의 클러스터 인덱스와 헷갈리지 말기 바란다. 이름 때문에 ‘클러스터형 인덱스(Clustered Index)’를 Oracle의 클러스터 인덱스와 같다고 생각하기 쉽지만 클러스터형 인덱스는 오히려 Oracle IOT에 가깝다. 차이가 있다면, Oracle IOT는 PK에만 생성할 수 있다는 점이다. SQL Server 클러스터형 인덱스는 중복 값이 있는 칼럼에도 생성할 수 있기 때문에 중복된 키 값을 내부적으로 식별하기 위해 ‘uniquifier’라는 값(4바이트 크기)을 함께 저장한다.

 

2) 클러스터형 인덱스 / IOT 활용

 

클러스터형 인덱스는 아래와 같은 상황에서 유용하다.

 

 

 

  • 넓은 범위를 주로 검색하는 테이블
  • 크기가 작고 NL Join으로 반복 룩업하는 테이블
  • 칼럼 수가 적고 로우 수가 많은 테이블
  • 데이터 입력과 조회 패턴이 서로 다른 테이블

 

 

 

마지막 항목에 대해서는 보충설명이 필요할 것 같다. 어떤 회사에 100명의 영업사원이 있다고 하자. 영업사원들의 일별 실적을 집계하는 테이블이 있는데, 한 페이지에 100개 레코드가 담긴다. 그러면 매일 한 페이지씩 1년이면 365개 페이지가 생긴다. 실적등록은 이처럼 일자별로 진행되지만 실적조회는 주로 사원별로 이루어진다. 예를 들어, 일상적으로 아래 쿼리가 가장 많이 수행된다고 하자.

 

 

 

select substring(일자, 1, 6) 월도 , sum(판매금액) 총판매금액, avg(판매금액) 평균판매금액 from 영업실적 where 사번 = 'S1234' and 일자 between '20090101' and '20091231' group by substring(일자, 1, 6)

 

 

 

만약 비클러스터형 인덱스를 이용한다면 사원마다 365개 데이터 페이지를 Random 액세스 방식으로 읽어야 한다. 특정 사원의 1년치 영업실적이 365개 페이지에 흩어져 저장돼 있기 때문이다. 이처럼 데이터 입력과 조회 패턴이 서로 다를 때, 아래와 같이 사번이 첫 번째 정렬 기준이 되도록 클러스터형 인덱스를 생성해 주면, 한 페이지만 읽고 처리를 완료할 수 있다.

 

 

 

create clustered index 영업실적_idx on 영업실적(사번, 일자);

 

 

 

지금까지 설명한 클러스터형 인덱스의 특징은 Oracle IOT(Index-Organized Table)에도 똑같이 적용된다. 방금 설명한 사례로 Oracle에서 IOT를 생성하려면 아래와 같이 하면 된다.

 

 

 

create table 영업실적 ( 사번 varchar2(5), 일자 varchar2(8), ... , constraint 영업실적_PK primary key (사번, 일자) ) organization index;

 

 

 

3) 2차 인덱스로부터 클러스터형 인덱스/IOT 참조하는 방식

 

SQL Server는 클러스터형 인덱스를 가리키는 2차 인덱스를 비클러스터형 인덱스라고 부른다. Oracle에선 IOT를 가리키는 2차 인덱스를 ‘Secondary Index’라고 부른다. 2차 인덱스는 클러스터형 인덱스나 IOT를 가리키는 키 값을 내부적으로 포함하는데, 버전마다 구조가 조금씩 다르다. SQL 서버 6.5 이전에는 비클러스터형 인덱스가 클러스터형 인덱스 레코드를 직접 가리키는 rowid를 갖도록 설계하였다. 문제는, 인덱스 분할에 인해 클러스터형 인덱스 레코드 위치가 변경될 때마다 비클러스터형 인덱스(한 개 이상일 수 있음)가 갖는 rowid 정보를 모두 갱신해 주어야 한다는 데 있다. 실제로, DML 부하가 심하다고 느낀 마이크로소프트는 7.0 버전부터 비클러스터형 인덱스가 rowid 대신 클러스터형 인덱스의 키 값을 갖도록 구조를 변경하였다. 이제 클러스터형 인덱스의 키 값을 갱신하지 않는 한, 인덱스 분할 때문에 비클러스터형 인덱스를 갱신할 필요가 없어진 것이다. 그런데 DML 부하가 줄어든 대신, 비클러스터형 인덱스를 이용할 때 이전보다 더 많은 I/O가 발생하는 부작용을 안게 되었다. 비클러스터형 인덱스에서 읽히는 레코드마다 건건이 클러스터형 인덱스 수직 탐색을 반복하기 때문이다. 당연히 클러스터형 인덱스 높이(height)가 증가할수록 블록 I/O도 증가한다. Oracle은 IOT를 개발하면서 SQL 서버 6.5 이전과 7.0 이후 버전이 갖는 두 가지 액세스 방식을 모두 사용할 수 있도록 설계하였다. IOT 레코드의 위치는 영구적이지 않기 때문에 Oracle은 Secondary 인덱스로부터 IOT 레코드를 가리킬 때 물리적 주소 대신 Logical Rowid를 사용한다. Logical Rowid는 PK와 physical guess로 구성된다.

 

 

 

Logical Rowid = PK + physical guess

 

 

 

physical guess는 Secondary 인덱스를 “최초 생성하거나 재생성(Rebuild)한 시점”에 IOT 레코드가 위치했던 데이터 블록 주소(DBA)다. 인덱스 분할에 의해 IOT 레코드가 다른 블록으로 이동하더라도 Secondary 인덱스에 저장된 physical guess 값은 갱신되지 않는다. SQL 서버 6.5에서 발생한 것과 같은 DML 부하를 없애기 위함이고, 레코드 이동이 발생하면 정확한 값이 아닐 수 있기 때문에 ‘guess’란 표현을 사용한 것이다. 이처럼 두 가지 정보를 다 가짐으로써 Oracle은 상황에 따라 다른 방식으로 IOT를 액세스할 수 있게 하였다. 경우에 따라서는 두 가지 방식을 다 사용하기도 하는데, physical guess가 가리키는 블록을 찾아갔다가 찾는 레코드가 없으면 PK로 다시 탐색하는 식이다.

 

 

http://www.dbguide.net/db.db?cmd=view&boardUid=148220&boardConfigUid=9&categoryUid=216&boardIdx=140&boardStep=1