메뉴 건너뛰기

bysql.net

9. 비트맵 인덱스

2011.03.07 08:31

휘휘 조회 수:5011


  • b*tree index테이블 레코드를 가리키는 rowid 목록을 키값과 함께 저장하는 구조이나
  • bitmap index는 키값에 중복이 없고 키값별로 하나의 비트맵 레코드를 가지며
    비트맵상의 각 비트가 하나의 테이블 레코드와 매핑된다.


(1) 비트맵 인덱스 기본구조


상품ID 1 2 3 4 5 6 7 8 9 0
상품명 KA387 RX008 SS501 WDGS CY690 K1EA PO782 TQ84 UA345 OK455
생상 GREEN GREEN RED BLUE RED GREEN BLUE   BLUE RED

BLUE 0 0 0 1 0 0 1 0 1 0
GREEN  1 1 0 0 0 1 0 0 0 0
RED 0 0 1 0 1 0 0 0 0 1
null 0 0 0 0 0 0 0 1 0 0


  • 키값 green을 보면 1,2,6번째 비트가 1로 설정되어있으며 이것은 각 순번에 상응하는 테이블의 레코드값이 green임을 의미한다




  • 구조
    • KEY, 시작 ROWID, 종료 ROWID, BITMAP 의 정보를 담고 있음


KEYSTART (ROWID)END (ROWID)BITMAP
BLUE1.1134.270001...00010000
GREEN 1.1134.270100...00100000
RED1.1134.271000...00000100
null1.1134.270010..01000000



비트맵 위치와 rowid 매핑
  • 테이블 블록은 한 익스텐트에 저장되지만 익스텐트끼리는 인접하지않고 다른데이타 파일에 흩어져 저장되게 되어
    상대적인 시작, 종료rowid로 정확한 레코드 위치를 파악 하는 방법이 필요하며 그 방법은 아래와 같다.



SQL> show parameter block_size;

NAME                                 TYPE        VALUE
------------------------------------ ----------- ------------------------------
db_block_size                        integer     8192


block이 8192바이트라면 1byte 인 ‘a’  단일 컬럼을 저장하면

이론상 1블럭당 수천개가 저장되어야하지만 실제로는 아래와 같이 730개를 넘지 못함

SQL> create table t1 (c)
 2  pctfree 0
 3  as
 4  select 'a' from dual connect by level <=100000;

Table created.

SQL> select min(count(*)),max(count(*)),avg(count(*))
 2  from t1
 3  group by dbms_rowid.rowid_block_number(rowid);

MIN(COUNT(*)) MAX(COUNT(*)) AVG(COUNT(*))
------------- ------------- -------------
         720           730    729.927007

SQL>

이로서 오라클은 한블록에 저장할수 있는 최대 래코드 개수를 제한하고 있음을 확인할수 있으며
오라클은 비트맵인덱스를 찾아갈때 이정보를 사용하여 각 익스텐트당 블록수등을 감안하여 계산이 가능하게됨

ex) 블럭당 최대수 730, 총 20개의 블럭,

      두개의 익스텐드에 각각 10개의 블록이 있을때 9500번째 비트 값을 찾을경우


floor(9500)/730 =13 14번째 블록 (두번째 익스텐트 4번째 블럭)
mod(9500,7300) = 10 10번째 레코드

730*13+10 = 9500


의 계산으로 찾아 가게된다.






키값의 수가 많을때

  • 비트맵 인덱스는 키값별로 하나의 레코드를 가지며 값이 많아질수록 인덱스 높이가 증가 하게 되어
    b*tree 인덱스보다 더많은 공간을 차지할수도 있게된다.


키값별로 로우 수가 많을때

  • 한블록으로 비트맵을 표현할수 없을 정도로 로우수가 많으면 두개이상의 블록에 나누어 저장한다.


비트맵 압축

  • 오라클은 비트맵을 저장할때 반복되는 0값을 제거하고 check sum bit를 두어 압축하여 저장하게 된다.


(2) 비트맵 인덱스 활용


  • 성별등과 같이 Distinct Value 개수가 적을 때 효율적이며
    단일 사용의 경우 테이블 Random 액세스 발생 측면에서는 B*Tree인덱스와 같기때문에 index 블록 스캔량이 줄어드는 정도의 성능 이점만 얻을수 있다.

    하지만 여러 비트맵인덱스를 동시에 사용하게 된다면 비트연산으로 검색을 수행하게 되어 이점을 가질수 있게된다.
  • 장점
    • bit연산으로 검색가능
    • null 검색 가능
    • 여러 인덱스를 동시에 활용하기때문에 다양한 조건절이 사용되는 ad-hoc query가 많은 환경에 적합
  • 단점
    • lock 에 의한 DML 부하 (레크드 변경시마다 비트맵 범위의 모든 레코드에 lock이 걸림)

계산 예


조건 :   (크기=’small’  or 크기 is null) and 생상=’green’


순번             0 1 2 3 4 5 6 7 8 9

(크기    small   0 0 0 1 0 0 1 0 1 0

or

크기)     null   0 1 0 0 0 0 0 1 0 0

and
색상     green   1 1 0 0 0 1 1 0 0 0


bit 연산을 통해 1, 6 번 선택




(3) recored_per_block


  • 오라클은 최대 레코드 개수를 제한하고 있으며 이경우 값에 따라  실제 저장되는 평균 레코드 개수이 못미쳐 낭비되는
    공간이 많이 생기게 될수도 있다.
  • 이에 오라클은 블록에 저장될수 있는 최대 레코드 개수를 사용자가 지정할수 있는 기능을 제공한다.


SQL> alter table t minimize records_per_block;


  • 명령수행하면  t 테이블을 스캔하여 블록당 최대 개수를 조사하여 그에맞게 설정하게된다.
    (교제의 경우 블록당 7개 레코드만 저장될수 있도록 변경)
  • 명령수행 후   create bitmap index를 수행하면 그 기준에 맞게 index를 할당한다.
  • 하지만 블록당 레코드 개수가 정상치 보다 낮은 상태에서 본 명령을 수행하면 추가로 데이터가 입력될때 블록마다 공간이
    많이 발생하게 되어 비트맵 인덱스가 줄어드는것 이상으로 테이블 크기가 커지게되므로 주의 하여야 한다.


  • 오라클 고도화 원리와 해법 2 (bysql.net 2011년 1차 스터디)
  • 작성자: 남송휘(휘휘)
  • 최초작성일: 2011년 3월 6일
  • 본문서는 bysql.net 스터디 결과입니다 .본 문서를 인용하실때는 출처를 밝혀주세요. http://www.bysql.net
  • 문서의 잘못된 점이나 질문사항은 본문서에 댓글로 남겨주세요. ^^