이화식 선생님의 새로쓴 대용량 데이터 베이스 1의 온라인 스터디 입니다.
매주 각 스터디 팀원들이 담당 분량을 정리해서 올리고 토론식으로 진행합니다.
스터디 포스팅은 팀원들에의해 이루어지지만 스터디 참여는 사이트 회원 모두가 가능합니다.

진행기간: 2009.07 ~ 2009.10. 종료

2.2. 비트맵(Bitmap) 인덱스

2009.07.14 20:44

휘휘 조회 수:110471

2.2. 비트맵(Bitmap)인덱스
    비트를 이용하여 컬럼값을 저장하고 이를 이용하여 rowid를 자동으로 생성하는 인덱스

2.2.1. 비트맵 인덱스의 탄생 배경

기존 인덱스들의 문제점에 대한 대안
  • B-tree 인덱스는 실제 컬럼 값을 인덱스에도 보관함으로써 중복이 생김
  • B-tree 인덱스는 컬럼의 분포도가 좁아야 최적의 성능을 발휘 하므로 분포도가 넓을 경우 분리
  • 결합인덱스는 그 조건에 맞지 않는 컬럼이나 '='조건이 아닌경우가 있으면 성능의 저하가 있음
  • b-tree 인덱스는 DW 하우스 처럼 카디널러티가 낮은 다수의 디맨전들이 다양한 요구를 할경우 엄청난 개수의 인덱스를 동원해야함
  • b-tree 인덱스는 'null','not'을 사용한 부정형 조건 복잡한 'or'등에서 제 성능을 발휘하지 못함
  • 일부의 컬럼으로 인덱스를 구성하여 'driving(처리조건 주관)'하고 나머지는 체크역할로 사용
      (적은량의 결과에 내부적으로 많은 범위를 액세스한후 조건에 맞는것을 버리는 형태로 동작할수도 있음)


2.2.2. 비트맵 인덱스의 구조와 특성


BITMAP.png


인용:
color라는  컬럼에 'yellow,green,red,null'이 들어있는경우
비트맵 인덱스를 생성
" create bitmap index prod_color_btidx on prod(color); "
하면
b-tree와 같은구조로 tree를 구성하여 최종 리프 노드에
각 값들의 bit값으로 변환하여 저장


  • 비 트 저장시 rowid를 선분형태(start rowid ~ end rowid)로 저장하여 압축의 효과를 가질수 있으묘 키 압축이 적용되어 저장공간이 절약된다. 컬럼값의 저장역시 비트형태로 '1'이라는 비트가 저장되며 rowid로 전환할때에도 해당비트를 액세서 하여 역연산을 수행하면 되어 btree처럼 각 컬럼마다 rowid를 가지지 않아도 된다
  • 비트맵 인덱스는 'AND' 와 'OR' 검색 시에 비트 연산을 적용하면 원하는 결과로 나타남
    (비트연산: 0 AND 1 = 0, 0 OR 1 = 1)
  • null 값역시 bit값을 가지기 때문에 b-tree인덱스의 null의 문제해결

단점
  • '=' 이 아닌 LIKE,BETWEEN,>,<,>=,<= 등의 사용시 분리
  • 저장시 선분형태로 저장되기 때문에 빈번한 수정이 발생되는 컬럼에서는 블록레벨 잠금등으로 많은 부하가 유발될수 있음

2.2.3. 비트맵 인덱스의 액세스

인용:
Select sum(weight)
from parts
where size='MED'
and color='RED'

--------------------------------------------------------------
color idx : 'BLUE    ' 0 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0
color idx : 'RED     ' 0 1 1 0 1 0 0 1 0 0 0 0 1 0 0 1
color idx : 'GREEN   ' 1 0 0 0 0 1 0 0 0 1 0 1 0 1 0 0

                            AND

size  idx : 'SMALL   ' 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1
size  idx : 'MED     ' 1 1 0 0 1 0 1 0 0 0 0 1 0 1 0 0
size  idx : 'LARGE   ' 0 0 0 1 0 0 0 0 1 0 1 0 1 0 1 0
--------------------------------------------------------------
                       1 2 3 4 5 6 7 8  9
--------------------------------------------------------------

TABLE
partno     color      size     weight
-----------------------------------
001        GREEN      MED      98.1
002        RED        MED      124.3
003        RED        SMALL    100.1
004        BLUE       LARGE    54.2
005        RED        MED      124.5
006        GREEN      SMALL    60.2

비트 연산으로(AND) 결과를 찾은후 ROWID를 해석하여
테이블에 엑세스 하고 결과를 리턴한다. 위의경우는 002, 005번.



비트연산의 실행계획
BITMAP CONVERSION
  • TO ROWIDS : 테이블 액세스를 위해 비트맵을 ROWID로 변환
  • FROM ROWIDS : ROWID를 비트맵으로 변환
  • COUNT : 실제값이 필요하지 않은 경우 해당 ROWID의 개수만 산출

BITMAP INDEX
  • SINGLE VALUE : 인덱스 블록 내에서 하나의 키 값에 해당하는 비트맵을 검색
  • RANGE SCAN : 하나의 키 값에 해당하는 여러 개의 비트맵을 검색
  • FULL SCAN : 시작/종료값이 제공되지 않은 경우 비트맵 전체를 스캔

BITMAP MERGE
  • 범위 스캔으로 얻은 몇 개의 비트맵을 하나로 머지

BITMAP MINUS
  • 부정형 연사이나 차집합을 구하는 작업

BITMAP OR
  • 두 개의 비트맵을 대상으로 비트 열에 대한 OR 연산을 수행

BITMAP AND
  • 두개의 비트맵을 대상으로 비트 열에 대한 AND 연산을 수행

BITMAP KEY ITERATION
  • 한 테이블에서 얻은 각각의 로우들을 특정 비트맵 인덱스에 대해 연속해서 확인하여 비트맵을 찾는것
    뒤에 비트맵 머지가 수행되어 하나의 비트맵으로 합쳐지며 스타 변형 조인에서 나타남

인용:
비트맵 인덱스는 분포도가 좁은 컬럼에서 최적의 성능을 발휘하며 인덱스 생성시 ROWID값을
선분형태( 시작 - 끝 ) 로 저장하고 각 컬럼의 값을 0,1의 비트 값으로 저장한다.
그에 따라 AND, OR 등의 복합 조건 검색시 '논리 연산' 의 결과가 찾고자 하는 자료의 결과를 의미하게
되어 효율 적인 활용이 가능하다.

그리고 각 DBMS의 버젼에 따라 지원 기능 및 범위가 조금씩 다르며 ORACLE 9i 이상부터는 비트맵조인인덱스도 지원한다.


  • 작성자: tofriend(남송휘)
  • 작성일: 2009년 07월 15일
  • 참고문헌 : 새로쓴 대용량데이터 베이스 1 - 이화식 , 기타 문서