메뉴 건너뛰기

bysql.net

2.2. 비트맵(Bitmap) 인덱스

2010.10.04 03:58

실천하자 조회 수:20924

2.2. 비트맵(Bitmap) 인덱스

  • Bit 값으로 컬럼 저장, ROWID 자동 생성
  • 저장공간 ↓, Bit 별 연산수행
  • 생성 / 유지 비용 ↑
  • 검색 시 장점 多


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


  • B-Tree 인덱스에서 실제 컬럼 값을 인덱스에도 보관  ☞  결합 인덱스 증가 시 부담 ↑
  • B-Tree 인덱스의 주요소로 분포도가 좁아야 함  ☞  분포도가 넓을 시 Table Full Scan 보다 불리 할 수 있음
  • 결합인덱스는 조건 없는 컬럼, '=' 조건이 아닌 경우가 중간에 있을 시 효율 ↓
  • 데이터 웨어하우스처럼 카디널리티가 아주 낮은 다수의 디맨전들이 사용자 요구에 따라 다양한 구조로 결합 경우 발생 
  • B-Tree 에서 'NULL' 값, 'NOT' 부정형 조건, 복잡한 'OR' 조건 포함 시 인덱스로서의 효율 ↓ (체크 조건 역할만 함)
  • 체크 조건 역할은 테이블에서 액세스 범위를 줄이는데 기여하는 점이 없음 (효율성 ↓)


     ※ 비트맵 인덱스는 독립적 구성으로 필요 시 조합 가능 (유연성 ↑)



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


■ 구조

    • 루트 블록이나 브랜치 블록은 B-Tree 인덱스와 같은 구조
    • 리프 블록은 Bitmap 으로 구성

bitmap.jpg


(교재 p.75 Yellow, Green, Red, Null 순으로 표현)


CREATE BITMAP INDEX prod_color ON prod(color);


  • Entry Header :  컬럼 수와 Lock 정보 저장
  • Key Value :  각 키 컬럼의 길이와 값의 쌍을 저장
  • Start RowID :  시작 RowID 지정
  • End RowID :  종료 RowID 지정
  • Bitmap :  Bit문자(0,1)로 2차원 배열 구성, 해당하는 키값일 시 1, 아니면 0

bitmap_struc.jpg


■ 장점

    • 저장 공간 절약
      • 비트 저장 시 선분형태(Start RodID ~ End RowID)로 저장
      • 키 압축
      • 컬럼 값 직접 대신 유효값 '1' Bit 저장

    • 저장 방법에 의해 해당 비트 액세스로 RowID 전환 가능   ☞   각 로우마다 RowID를 가지지 않아도 됨

(단, 카디널리티가 높지 않고 동일 값의 반복 정도가 많을 시 절약 ↑)


■ 단점

    • '=' 아닌 범위기반 검색 ( Like, Between, >, <, >=, <= ) 사용 시 추출할 비트가 명확하지가 앟고, 대량이 나타날 수 있음
    • 선분 형태로 저장되기 때문에 빈번한 수정이 발생하는 컬럼
      • 인덱스 크기가 크게 증가
      • 블록레벨 잠금으로 인해 많은 부하 유발 가능
    • 카디널리티가 높은 컬럼에 대해 장점 활용 X



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


2_2_3_1.jpg


Execution Plan

-----------------------------------------------------------------------------------------------------------------

0     SELECT STATEMENT

1  0    SORT  (AGGREGATE)

2  1       TABLE ACCESS  (BY INDEX ROWID) OF    'PARTS'

3  2           BITMAP CONVERSION  (TO ROWIDS)

4  3              BITMAP AND

5  4                 BITMAP INDEX  (SINGLE VALUES) OF    'COLOR_BIX'

6  4                 BITMAP INDEX  (SINGLE VALUES) OF    'SIZE_BIX'


 Option 

 Det.Option 

 설               명 

 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

 - 

 한 테이블에서 얻은 각각의 로우들을 특정 비트맵 인덱스에 대해   

 연속해서 탐침하여 해당하는 비트맵들을 찾는 것.

 뒤에 비트맵 머지가 수행되어 하나의 비트맵으로 합쳐지며, 

 스타 변형조인에서 나타나는 형태.



       ■ NOT을 사용한 쿼리


2_2_3_2.jpg


    1. COL1 인덱스에서 123 비트맵 액세스, COL2 인덱스에서 ABC 비트맵 액세스 후 감산 연산 수행
    2. COL2 가 Null 인 비트맵 액세스 하여 다시 감산 연산 수행 ( <> 연산에서는 Null도 모두 제거 )
    3. COL3 < 100 범위 스캔은 해당 범위의 비트맵을 읽어 머지 수행
    4. 각 조건 수행 결과에 대해 OR 연산 수행하여 최종 결과 비트맵으로 만든 후, ROWID로 변형하여 테이블 액세스