BITMAPPED INDEX

제품 : ORACLE SERVER

작성날짜 : 2004-08-13


SCOPE
-----
8~10g Standard Edition 에서는 지원 하지 않습니다.

<< Bitmapped Index >>

최근에 각광받고 있는 Datawarehousing환경 과 End-User-Computing환경등
에서 필요한 RDBMS의 첨단 Indexing Access기법으로 경쟁사에서는 Bitwised
Index를 발표하고 있습니다. 이 기법은 Oracle Server V7.3에서도 Bitmapped
Index라는
이름으로 발표될 예정이므로 이에 대한 정확한 이해를 위해 다음사항을 기술해
보았습니다.

１) Bitmapped Index란 ?
２) Bitmapped Index의 장단점 ?
３) Oracle's Bitmapped Index의 특성 ?

1. Bitmapped Index란 ?
RDBMS의 Table로부터 특정 자료의 검색을 위해 기존의 일반 RDBMS에서는
검색효율의 향상을 위해 B-Tree Index를 구현하여 사용하여 왔습니다.
그외에도 B-tree Cluster Index , Hash Cluster Index등을 이용하여 대
부분의 검색효율을 보장하여 왔지만 B-Tree Access를 위한 특성으로
인해 몇가지 어려움을 안고 있었습니다.

1) B-tree Index Access 방식을 위해선 실지 조건비교되는 Column값에
대한Table의 원시값을 Index에도 보관하고 있어야 함으로 인해 Index를 위한
실지 data의 중복 저장으로 저장공간의 낭비를 감수하여야 했으며, 특히
현실 상황에서 자주 사용케 되는 여러 컬럼의 Concatenated Index (결합
인덱스) 에서 자료량이 많은 Table에 대해서는 크나큰 부담이었습니다.

2) Index설정 Column값의 분포도(Unique성)가 넓은 Column에대한 (예:성별)
조건검색시에는 Index access를 했을때 보다 오히려 Full Table Scan방식이
오히려 빠른 성능을 보장하기 때문에 RDBMS의 Cost Based Optimizer는
Random access비용이 많이드는 Index access를 포기하고 빠른속도의 순차
Table Scan을 하여 높은 Hit Ratio를 보장하려 하는 경우를 우리는 흔히
보게됩니다.

3) End-User-Computing 환경에서 흔히 예상되는 복잡한 질의조건으로 인해
Optimizer가 최적 실행계획에서 Index를 포기하게되는 경우를 초래합니
다. (예: 복잡한 OR 연산자등)

이러한 상황을 해결하기 위한 새로운 Index Access 방법으로 Bitmapped Index가
새롭게 등장하게 되었습니다.

다음 상황을 통하여 구체적 설명을 제시합니다.
예) 한국오라클(주) 에서 관리하고 있는 고객정보 Table이 다음과 같이
정의 되어있다고 가정합시다.
------------------------------------------------
고객번호 혼인여부 성별 중요등급
------------------------------------------------
1001 결혼 여 하
1002 미혼 남 상
1003 재혼 남 중
------------------------------------------------

상기 Column들의 속성을 보면
고객번호는 유일한 값들이며 B-Tree Index로 탁월한 조회성능 보장.
혼인여부(3종류),성별(2종류),중요등급(3종류) 은 30 - 50%의 넓은
분포도를 갖는 값들로서 B-Tree Index사용시 효율성이 거의 없슴.
즉, B-Tree Index에서는 자료의 값에 따라 Sort하여 이분식(Binary)
가지치기(Leaf & Node) 구조를 유지하여, 조건에 들어오는 값에따라
검색자료 범위(Access Range)를 쪼개어 나가는데 반해, 저장되어 있
는 자료가 동종(같은값)이 많다면 해야할일(Access Range)이 줄지
않고 비용이 많이드는 Random Access(Index에서 Rowid를 가지고 실
Table Data를 찾을때)만 많아지고, Scan해야할 자료가지(Leaf) 수는
쉽게 줄지않게되어 B-Tree Index방식으로는 빠른 성능을 보장하기가
어렵습니다.

그렇다면 다음과 같이 분포도가 좋지않은 중요등급 Column을 몇개의
Bit들만 가지고 정보를 저장키로 하여봅니다.

----------------------------------------------------------
중요등급 = '상' 1 0 0 0 0 0
중요등급 = '중' 0 1 0 0 1 1
중요등급 = '하' 0 0 1 1 0 0
----------------------------------------------------------
*혼인여부(3종류),성별(2종류)도 같이 적용하였다고 가정.

이런 상황에서 아래의 SQL을 실행한다고 가정하여 봅니다.

Select count(*) from 고객정보
where 결혼여부 = '미혼'
and 중요도 in ('상','중');
("미혼자 인 고객중에 중요도가 '상' 이거나 '중'인 고객은 몇 ?")
이SQL을 실행하기 위한 Optimizer가 이러한 Operation을 다음과
같이 결정한다면 훨씬 빠른속도의 성능을 낼 수 있을 것 입니다.

혼인여부 = '미혼' AND (중요도 = '상' OR 중요도 = '중')
즉, '011001' AND ( '100000' OR '010011')
다시 풀어보면 '011001' AND '110011' 이고 결과는 '010001'이다.
Optimizer는 두개 컬럼의 논리연산결과가 '010001'인 Row들을 찾아
건수를 세면 될 것 입니다.

상기와 같이 논리연산과 Bit처리 방식은 Computer에게 훨씬 쉽게
처리할 수 있는 길을 만들어주게 되면서, 몇종류 안되는 값들과의
별도의 조그만 연결표(Bitmap)와 몇Bit만의 저장공간만을 가지고
Index 구성을 가능케 함으로써 공간의 절약효과도 상당할 것이다.
특히, Data warehousing, Decision Support System 에서와 같은
방대한 정보량에서 유용할 수 있습니다.


2. Bitmapped Index의 장단점 ?

Index를 사용하는데 있어서 우리는 몇가지의 고려사항을 검토해야 합니
다. 조회성능측면, 저장공간측면, 유지관리측면 정도를 고려할 수 있습
니다. 앞으로, 이러한 측면에서의 Bitmapped Index특성을 설명하기로
하겠습니다. 우선, Bitmapped Index의 장,단점을 간추려보면 다음과 같
습니다. 장점으로는 아주적은 Index저장공간을 사용하여 좋지않은 분포
도의 값을 갖는 다량의 자료를 빠른속도로 Access할 수 있다는 것과 복
잡다양한 조건에 대해 Index Access Path를 적용할 수 있다는 점이 있는
반면, 조건 유형이 Pattern Match형태가 자주 사용될시 효용성이 극소화
되며, B-Tree Index와 같이 모든 Query에 대해 Index Path로 사용될 수
없다는 단점이 있습니다. 한예로 Insert, Update, Delete와 같은 Query
에서는 무의미 합니다.
Bitmapped Index는 다음과 같은 측면에서 각각 유용한 이점이 있습니다.

조회성능측면
- 각각의 독립적인 Column들에 대하여 여러유형 (AND,OR...)의 조건절에
대해 Index가 사용 되어지게 하는 규칙이 불필요하다.(ad hoc query)
- 분포도가 나쁜 값에 대한 Index Access가 빠름.
- Index Column으로 추가 필요시 독립적으로 추가 및 적용 가능.
- 복잡하게 길어지는 조건절에서도 모두 유효하게 작동된다.
(복잡한 질의 및 ad hoc query에서 유용)
- 특히 다량의 자료에 대한 계 질의(aggregate query)에서 탁월.
(예:COUNT operator)
- 분포도가 좋은 (Unique성:값의종류가 많다) 값에대한 Index는 불리.

저장공간측면
- Index에 가지고 있어야 될 자료값 에대한 공간 절약.
. 하지만, Bitmapped Index로 적용하게될 Column의 특성상 실제 값의
Size도 크지않다 예를들어 '남' 과 '여'값의 겨우 2Byte 이하일 것
이다. 즉, Bitmapped Index적용 Column의 후보는 대개 5가지 정도
이내의 값을 갖는 경우가 되므로 실지 값의 Size도 작게됨.
고로, 이러한 측면에서의 저장공간 절약 측면 보다는 실제 현업상
요구되는 Index구성에서 예를 들면 더나은 이해가 될 것 입니다.
예) 기존에 고객정보 검색속도를 위해 Index1을 다음과 같이 구성
하였다고 가정 하겠습니다.
B-Tree Index1 = (혼인여부,성별,중요도)
이경우는 Where절에서 혼인여부가 조건에 오지않는 경우나
조건절에 성별만 혹은 중요도만을 가지고 검색할 경우에는
Index1을 사용할 수 없기에 Index2(성별,중요도,혼인여부),
Index3(중요도,성별,혼인여부)등의 추가 Index가 있어야
만족한 성능을 낼 수 있었다면 거의 10 - 100배의 공간절약
을하며 Bitmapped Index1(혼인여부),Index2(성별),Index3
(중요도)등의 독립적인 3개의 적은공간으로 만족한 성능을
보장할 수 있슴. 이러한 측면에서의 이점이 클 것 입니다.

유지관리측면
- Bitmapped Index는 Decision Support System과 같은 조회전용 업무나
OLTP업무 비중이 작은 업무에서 적합.
- 아직 Single Bit에 대한 Lock방안이 없고, Bitmapped Index에서는
Row-Level Locking대신에 Block-Level Locking이 적용되기 때문에
OLTP전용 업무에서는 Lock Contention 및 Deadlock 가능성 많음.
- Bitmapped Index에서 Update등의 Transaction은 Block level Lock을
사용하여야 하므로 Oracle의 기본Locking 인 Row level Lock 사용할
수 없게 되며 결국 Oracle block (예:2KB)내의 한Row에 대한 변경이
필요시(Update등)에는 해당 Block전체가 Locking되므로 잦은 변경이
예상되는 OLTP업무에서는 큰부담이 되므로 Batch성 Bulk Operation
이 가미되어 운용할 수 있는 방안이 필요.
예) Data warehousing에서는 주업무가 조회이며, 자료변경 추가시는
대부분 Batch성으로 처리하는 사례에서 Batch작업시 Bitmapped
Index들을 Disable시키고 처리후 Enable하는 것이 바람직.


3.Oracle's Bitmapped Index의 특성 ?
Oracle에서의 Bitmapped Index는 다음의 이점을 제공합니다.

검증된 기술
- 이미 Oracle7의 Text Server에서 Bitmapped Technology를 적용하여
사용하여 왔으며 이러한 기술을 Oracle7 Release7.3에서 Production
으로 제공합니다.

통합기능으로 제공
- 별도의 기능옵션 추가없이 Oracle Server에 통합되어 제공됩니다.
- 기존 사용 모든 환경과 수정없이 통합 적용이 가능합니다.
(예: DB Trigger, Distributed, Parallel, Integrity constraints...)
- 각종 SQL, Tool 및 Utility, Application등에서 수정이 필요없습니다.

병렬 Index 생성 지원
- 방대한 자료에 대한 Index생성시 병렬수행으로 Bitmapped Index생성

압축기능
- 저장공간을 현저히 줄일 수 있게 구현된 압축기법을 제공합니다.

입력/수정/삭제 지원
- Oracle의 Bitmapped Index는 Insert,Update,Delete 를 지원합니다.
(은행 계정업무 와 같은 무리한 OLTP transaction이 아닌 하루업무
중에 약 10% 이내의 자료변경 업무는 그대로 사용 가능)
- 사용자로 하여금 가끔 유발되는 변경에 대해서 Bitmapped Index를
재생성이 불필요하게 투명하게 사용가능.

병렬 Index 검색 지원
- 대량의 Table에 대한 검색시 병렬로 Bitmapped Index 검색 가능.
여러컬럼에 대한 Bitmapped Index 지원
- 분포도가 나쁜 몇개의 컬럼이 항시 같이 조건에 오는 경우 B-Tree
Index에서의 Concatenated Index같이 Multicolumn Bitmapped Index
사용가능.

유연성 보장
- 하나의 Table에 B-tree Index와 Bitmapped Index를 동시
혼용가능.
(Clustered Index도 혼용 생성 가능)

Oracle에서의 테스트 예제

Oracle에서의 Bitmapped Index의 특성을 확인할 수 있는 예시
입니다.

고객정보자료는 약100만건의 자료로 구성되어 있으며 현재 고객번호는
유일한 값으로 구성되며 Primary Key로 선언되어 있습니다.
그러나, 성별 과 중요도, 혼인여부 컬럼의 값은 2가지 내지는 3가지
종류이어서 B-Tree Index로는 검색수행 속도를 보장할 수 없는
상황임.

1) Select * from 고객정보 where 성별 = '남';
본 SQL을 Optimizer는 최적의 Execution Plan으로 Parallel
Full Table Scan을 선택하게 됩니다. (전체의 50%이므로)

2) Select * from 고객정보 where 고객번호 = 1001;
본 SQL을 Optimizer는 최적의 Execution Plan으로 Unique
B-tree Index를 Access 하여 Rowid를 가지고 Table 을
1번 Scan.

3) Select * from 고객정보
where 성별 = '남' and 중요도 in ('상','중');
본 SQL을 Optimizer는 최적의 Execution Plan으로 Bitmapped Index
를 선택하게 됩니다.

4) Select * from 고객정보
where 성별 = '남' and 고객번호 = 1001;
본 SQL을 Optimizer는 최적의 Execution Plan으로 B-tree Index를
Range Scan하는 방법을 선택하게 됩니다.
(성별 Bitmapped Index 보다는 Unique한 고객번호 Index가 효율적)

상기와같이 Oracle 에서의 Bitmapped Index는 Cost Based Optimizer
에 의해 투명하고 유연성있게 수행속도를 보장하게 되며, 필요시
Oracle의 특징인 Optimizer 취사 선택기능으로 사용의도에 맞추어
사용이 가능합니다.
결론

Data Warehousing 또는 Decision Support System에서의 필요한 요소인
Oracle의 Bitmapped Index는 Release7.3 Server에 탑재되게 되었으며
기존 RDBMS에서의 조회 수행속도의 몇가지 걸림돌을 해결케 하였고, 또
한 방대한 자료량에 대한 Index의 저장공간 절약 및 End-User-computing
에 꼭 필요한 Indexing 구현기법입니다.
단, Bitmapped Index만이 지상 최대의 해법이 아니란 것도 우리는 알아
야 하며 사전에 OLTP에서의 부담감에 대한 분석이 필요하며, 과연 나쁜
분포도에서 저장공간에 대한 낭비에는 많은 관심이 없고 단지 좋은 조회
속도를 보장키 위한다면 이미 기존 Oracle7에서부터 사용해온 Clustered
Index를 검토해 보는 것이 타당하리라고 사료됩니다.


Reference Documents
-------------------
<Note:70067.1>
<Note:108653.1>