[Oracle]Index fragmentation

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 작업을 수행한 이후 다시 레코드가 입력되기까지 오랜 기간이 소요될 때
• 총 레코드 수가 일정한데도 인덱스가 계속 커질 때

 

https://dataonair.or.kr/db-tech-reference/d-guide/sql/?mod=document&uid=366