1. 왜 비트맵이 만들어졌을까?
2. 왜 비트 인덱스라고 안하고 비트맵 인덱스라고 했을까?
3. 비트맵 인덱스 생성절차 까다롭지 않나?
4. 비트맵 인덱스를 쓰면 왜 빠른 결과를 나타내는데 왜?
5. 한 테이블에 여러개의 비트맵 인덱스를 구성할수 있을까? 그렇게 될 때 SQL문에서 조건절 처리할 때 어떻게 비트맵 인덱스를 사용할까?
문제 풀이 문1)
배경1) B-Tree인덱스의 문제점
B-TREE인덱스에서는 실제 컬럼 값을 인덱스에도 보관하고 있어야 한다는 점이 대용량 데이 터를 관리할 때 부담이 된다.
B-TREE인덱스 컬럼값의 분포도가 좋아야 한다는 점
결합인덱스에서 조건을 사용하지 않는 컬럼이나 ‘=‘조건이 아닌 컬럼이 결합인덱스 중간에 있 으면 액세스효율성이 떨어진다는 점
다양한 액세스패턴을 수용하기 위해 많은 인덱스가 필요할 수 있다는 점
NOT이나 NULL을 사용하거나 복잡한 OR조건에서는 인덱스의 성능을 보장받지 못한다는 점
배경2) 저장공간의 낭비
B-Tree Index는 테이블 Column값과 집합 내에서 해당정보의 rowid를 정렬된 형태로 가지 는 구조이므로 동일 값에 대해서 물리적 주소가 다른 경우 동일 값을 중복해서 가지고 있어야 함으로 저장공간의 낭비가 발생하게 된다.
또한 테이블 Column값의 길이가 큰 경우 Index의 원시 값을 그대로 가짐으로써 Index의 크기가 증가하게 된다.
배경3) 유연성(Flexibility)의 부족
B-Tree Index에서는 동일한 테이블에 대한 Access시에 두 개 이상의 Index를 병행해서 사 용하는 데에 많은 제약사항이 따른다. 그러나 실제 업무 환경에서는 사용자의 요구 사항은 매 우 다양하다. 이러한 요구사항을 만족하기 위해서는 테이블의 모든 컬럼의 조합만큼의 B-tree Index를 만들어야 하며, 이렇게 한다고 하면 테이블의 크기보다 오히려 Index의 크기가 더 커지는 기현상을 초래할 수 있다. 또한, 각각의 인덱스를 관리하는 비용이 테이블 자체를 관 리하는 비용보다 커질 수 있을 것이다. 따라서 실제 업무에는 거의 적용하기 불가능한 경우라 고 할 수 있겠다.
분포도가 좋은 두개의 B-Tree Index가 있을 경우 두개 이상의 인덱스를 동시에 사용하는데 하나만 사용되고 체크조건으로 사용되는 등 두개의 인덱스를 효과적으로 사용하기 위한 제약 사항이 있다
문2) 문제풀이
비트 단위로 맵핑 테이블을 만들어 해당 속성 값에 속하면 ‘1’, 속하지 않으면 ‘0’으로 비트맵 을 구성함
-> 여기서 생각해야 봐야 할 것은 테이블 row 만큼 비트맵을 만들면 길이가 엄청 길어질 수
있습니다. 그래서 나온 것은 비트맵 엔트리에 Range 값 넣어서 start Rowid~ end RowID 값이 존재합니다.
아래 그림 Gender 성별을 비트맵 인덱스를 만들려고 하면 유형이 남성,여성 두가지 만약에 null값도 튜플에 포함되어 있으면 3가지 key value값을 가지고 거기에 해당한 비트맵을 구성 해야 함.
따라서 비트라는 속성을 가지고 맵을 구성하기 때문에 비트맵 인덱스라고 합니다. 비트맵 인 덱스 중요한 그림은 테이블에서 비트맵 뽑아내는 아래 그림을 참조.
비트맵 만들기 그림1)
통합본 예제로 나온 비트맵 테이블 그림2)
다른 형태 그림3)
비트맵 인덱스 구성하기 그림3)
문제 3) 비트맵 구조 및 생성 절차 1. 비트맵인덱스의 구조
B-tree의 leaf block은 Index key value + Rowid 로 구성이 되어 있지만, Bitmap Index는
Index key value + Start Rowid + End Rowid + Bitmap 엔트리로 구성되어 있다. 1개의 index값이
테이블상의 여러 개의 record를 표현하기 때문에 DML문을 사용할 경우 row level locking을 지원할 수 없다 Start Rowid 와 End Rowid 의 Range사이에 있는 모든 row수만큼 Bitmap이 표현되어야 하지만, 오라클에서는 내부적인 압축 알고리즘을 사용하여 Bitmap을 생성하기 때문에 모두 표현되지 않는 경우도 있다
2. 비트맵인덱스 생성 절차
1). 인덱스를 생성하고자 하는 컬럼의 값들을 찾기 위해 테이블 스캔을 한 후
- bitmap generator에 의해 컬럼값, start rowid, end rowid , bitmap을 갖는 인덱스 엔 트리를 생성한다.
- 2단계에서 생성된 Bitmap들을 B-tree구조에 넣기 쉽도록 key값과 start rowid 순으로 정렬한다.
4). 마지막 단계에서는 정렬된 인덱스 엔트리들을 단순히 B-tree구조로 삽입한다.
문제 4,5) Bitmap INDEX 액세스
Bitmap 인덱스를 실제로 액세스하여 결과값을 가져오는 부분에 대해서 살펴보자.
비트맵이 2개 size와 color DB 조건절이 존재하면 size비트맵 과 Color 비트맵을 비트 연산 을 통해 둘다 참인 경우 row Id 만 뽑으면 끝
위의 그림과 같이 조건에 맞는 비트값을 추출하고 이 내용을 ROWID로 전환한다.
실제로 좀 더 복잡한 SQL문에서 비트 연산을 살펴보자 아래 쿼리의 실행계획을 들여다보자.
SQL에 맞는 조건으로 비트맵 연산 예제)
B tree 인덱스와 차이점을 명확히 알아보기 위한 쿼리와 그에 따른 실행계획을 살펴보자.
1) NOT을 사용한 부분부터 살펴보면 col1에서 123에 해당하는 검색된 내용에서 col2 가 ABC인 것을 Bitmap MINUS를 통해 제거한다.
2) col2가 NULL값인 것 역시 제거를 하게 되는데, 조건에 사용된 모든 컬럼은 NULL값일 수 없기 때문이다.
3) col3에 대해 범위 스캔이 발생한 결과값은 Bitmap MERGE를 통한 통합과정을 거치고, Bitmap OR를 거치고
4)마지막으로 이 결과값을 Bitmap Conversion을 통한 ROWID로 전환한다.
위의 과정을 B tree 인덱스에서 수행할 경우 OR를 기준으로 두 개의 단위 액세스가 별도 수 행, 추후 결합하는 방식으로 처리된다.
<> 의 경우 체크조건으로만 이용되기 때문에 실제 액세스하는 데이터 양을 감소시키지는 못 한다. 이렇게 감소시키지 못하는 양이 적다고 생각할 수 있지만 많은 양의 데이터가 해당될
경우 무시할 수 없다.
Bitmap 인덱스의 경우 아직까지는 제한사항이 존재하지만 적합한 곳에 제대로 사용할 경우 탁월한 효과를 얻을 수 있겠다.
부록 1)
1. Bitmap 인덱스의 구조
통상적으로 B tree 인덱스를 많이 사용하긴 하나 단점이 없는 것은 아니다. 예를들어 보자면 인덱스에 실제 컬럼의 값을 가지기 때문에 데이터의 중복이 일어나거나, 컬럼값의 분포도가 좁아야만 효율을 보장(컬럼의 결합생성으로 대체), NULL or NOT 과 같은 부정형 조건이나 복잡한 조건을 포함하는 경우 인덱스로서의 가치를 발휘할 수 없다는 점 등을 들 수 있겠다. 위에서 나열한 B tree 인덱스의 단점에 대한 대안을 Bitmap 인덱스는 제시할 수 있다. 그럼 Bitmap 인덱스의 구조에 대해서 먼저 알아보도록 하겠다.
1. 비트맵 조인인덱스
테이블에 하나의 bitmap index가 존재할 때 optimizer는 b-tree index를 사용하여 bitmap access path를 사용할지를 고려한다.
이때 생성되는 access path는 b-tree와 bitmap을 결합한 형태가 될 수 있으며, bitmap을
전혀 포함하지 않을 수는 없다.
2. 비트맵인덱스 사용 시 실행계획 오퍼레이션
Oracle9i부터는 하나의 테이블에 대한 비트맵 인덱스뿐만 아니라 비트맵 조인 인덱스(BJI : Bitmap Join Index)도 지원한다.
3. 비트맵 조인 인덱스의 특징
비트맵 조인인덱스는 많은 수의 Dimension 테이블을 가지는 Star Schema일 경우에 유용할 수 있다.
비트맵 조인인덱스를 사용할 경우 일반적인 비트맵 인덱스만을 사용할 때 발생하는 Bitwise 연산을 하지 않아도 된다.
4. 비트맵 조인 인덱스의 장점
비트맵 조인 인덱스는 두 개 이상의 테이블의 조인 결과에 대해 비트맵 인덱스를 생성할 수 있게 해준다
비트맵 조인 인덱스는 조인되어야 하는 데이타의 양을 미리 제한 하여 디스크 공간을 효율적 으로 사용할 수 있다?
비트맵 조인 인덱스의 경우 Fact 테이블의 Rowid를 압축하여 유지하므로 훨씬 적은 양의 디
스크 공간을 사용한다.
많은 수의 Dimension 테이블을 가지는 Star Schema일 경우에 유용하다. 즉, 비트맵 조인 인덱스를 사용할 경우 일반적인 비트맵 인덱스만을 사용할 때 발생하는 Bitwise 연산을 하지
않아도 된다.
5. 비트맵 조인 인덱스의 단점
다양한 질의를 처리하기 위해서는 많은 수의 비트맵 조인 인덱스를 생성하여야 한다. 즉, 각 Dimension 테이블마다 인덱스를 생성하는 것이 아니라 각 Dimension 테이블의 각 열마다 비트맵 조인 인덱스를 생성하여야 한다.
하나의 테이블(Fact 테이블)에 많은 수의 인덱스를 생성하여야 하기 때문에 관리 비용이 많이
든다. 특히, Fact 테이블에 대한 변경 작업이 발생할 경우 더 많은 관리 비용이 든다. 인덱스를 재생성할 경우 조인 작업을 동반하기 때문에 인덱스 생성 비용이 크다
'08.Algorithm' 카테고리의 다른 글
삽입정렬 (Insert Sort) (0) | 2020.06.02 |
---|---|
선택정렬 (Select Sort) (0) | 2020.06.02 |
R-Tree (0) | 2020.06.02 |
큐 (Queue) (0) | 2020.06.02 |
휴리스틱 함수, 휴리스틱 이론 (0) | 2020.06.02 |