비트맵 인덱스. (by niceboyous) [2013.01.29]
비트맵 인덱스
B*Tree 와 비트맵 인덱스
B*Tree 인덱스 : 테이블 레코드를 가리키는 rowid 목ㄺ을 키 값과 함께 저장하는 구조, rowid에는 중복 값이 없지만 키에는 중복값이 있을 수 있다.
비트맵 인덱스 : 키 값에 중복이 없고, 키 값별로 하나의 비트맵 레코드를 갖는다. 비트맵 상의 각 비트가 하나의 테이블 레코드와 매핑된다.
h3.(1) 비트맵 인덱스 기본 구조
1.비트맵인덱스의 leaf구조는 Key, Start RowID ,End RowId ,BitMap으로 구성되어 있다.
(B*Tree의 경우는 RowId와 Key로 구성되어 있음)
2.비트맵인덱스의 경우에는 하나의 인덱스 Key 엔트리에 많은 로우에 대한 포인터를 갖고 있다.
(B*Tree의 경우에는 인덱스 Key와 테이블 로우가 한쌍을 이룬다.)
-위의 그림은 색상 컬럼을 생성한 비트맵 인덱스를 표현한 그림으로, 키 값이 lue인 첫번째 행을 보면 4번째 ,7번째 ,9번째 비트가 1로 설정돼 있다.
따라서 상응하느 테이블 레코드의 색상 값이 'BLUE'임을 뜻한다.
-즉,비트맵의 값이 1이면 그 키값의 색상임을 뜻하고 0이면 아니다 라고 표현하고 있다고 생각하면 된다.
-위의 그림에는 모든 비트맵의 시작 rowid와 종료 rowid를 같이 표현하였지만 이는 비트맵을 압축하지 않았을 때의 모습이며,
실제로는 여러 압축 알고리즘이 사용되어 서로 다른 rowid범위를 가지며 키 값의 수가 많다면 완전히 0으로 차는 블럭이 생기게 되는데 이러한 블럭들은
제거 된다.
비트맵 위치와 Rowid매핑
- 비트맵 인덱스의 레코드 위치를 알아내는 원리
데이터 블록은 한 익스텐트 내에서 연속된 상태로 저장되지만 익스텐트끼리는 서로 인접해 있지 않다. 그런데 어떻게 비트맵 인덱스는 레코드 위치를 찾아 낼수 있을까?
그 이유는 오라클이 한 블록에 저장할 수 있는 최대 레코드 개수를 제한하고 있기 때문이다.
- {*}오라클이 블록에 저장 개수를 제한하고 있음에 대한 예제{*}
SQL> show parameter block_size;
NAME TYPE VALUE
------------------------------------ ----------- ------------------------------
db_block_size integer 8192
- 현재 오라클 표준 블록의 크기가 8,192로 나오고 있다.
- 만약, 1 바이트 크기의 레코드라면 한 블록에 수천개를 저장할 수 있어야 하지만 앞서 말한데로 레코드 개수를 제한하기에 그러하지 못함을 아래에서 볼수있다.
SQL> create table t1 ( c )
2 pctfree 0
3 as
4 select 'a' from dual connect by level <= 100000;
테이블이 생성되었습니다.
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
-- 5Byte를 늘려서 다시 테스트
SQL> create table t2 ( c )
2 pctfree 0
3 as
4 select lpad('a', 5) from dual connect by level <= 100000;
테이블이 생성되었습니다.
SQL> select min(count(*)), max(count(*)), avg(count(*))
2 from t2
3 group by dbms_rowid.rowid_block_number(rowid);
MIN(COUNT(*)) MAX(COUNT(*)) AVG(COUNT(*))
------------- ------------- -------------
720 730 729.927007
위 와 같은 이유로
florr(9500/730) = 13 -> 14번째 블록
mod(9500,730) = 10 -> 10번째 레코드
와 같은 공식으로 14번째 블록의 10번째 레코드를 찾아가며 된다.
반대로 해당 레코드의 비트를 1로 변경하려 한다면 730 X 13 + 10 = 9,500 이와 같은 공식으로 해당 비트를 찾아간다.
키 값의 수가 많을 때
- 비트맵 인덱스는 키 값별로 하나의 레코드를 갖는데, 저장할 키 값의 수가 아주 많을 때는 한 블록에 모두 담지 못한다.
- 비트맵을 저장하기 위해 두 개 이상 블록이 필요해지면 B*Tree 인덱스 구조를 사용하며, 값의 수가 많을수록 인덱스 높이도 증가한다.
- B*Tree 인덱스 구조로 사용될정도라면 B*Tree 인덱스보다 더 많은 공간을 차지하수 있다.
h5.키 값별로 로우 수가 많을 때
- 한 블록 크기의 비트맵으로 표현할수 없을 정도로 테이블 로우 수가 많을 때도 두개 이상 블록이 필요해 진다.
h3.(1) 비트맵 인덱스 활용
- 비트맵 인덱스는 성별처럼 Distinct Value 개수가 적을 때 저장효율이 매우 좋다.(반대의 경우에는 B*Tree보다 많은 공간을 차지)
- 인덱스가 여러 개 필요한 대용량 테이브에 유용하다. 주로 다양한 분석관점을 가진 팩트성 테이블이 이에 속한다.
- Distinct Value 개수가 적은 컬럼일때 저장효율이 좋지만 테이블 Random 액세스 발생 측면에서는 B*Tree와 동일.(좋은 성능 기대 어렵다)
- 하나의 비트맵 인덱스 단독으로는 쓰임새가 별로 없지만 여러 비트맵 인덱스를 동시에 사용할 수 있다는 특징 때문에 대용량 데이터 검색 성능을 향상 시키는 데에 큰 효과를 발휘한다.
- 두 개 이상 비트맵을 이용한 Bitwise AND 연산뿐만 아니라 Bitwise OR, Bitwise Not 연산도 가능하다
- {*}Bitwise AND 연산, Bitwise OR, Bitwise Not 연산 의 예{*}
-- 상품 테이블의 '크기'와 '색상' 두 컬럼에 각각 비트맵 인덱스가 있는 상태에서 아래와 같은 쿼리를 수행
select * from 상품
where (크기 = 'SMALL' or 크기 is null)
and 색상 = 'GREEN'
- 비트맵 인덱스는 열 인덱스를 동시에 활용할 수 있다는 장점 때문에 다양한 조건절이 사용되는, 특히 정형화 되지 안흔 임의 질의가 많은 환경에 적합
- 비트맵 인덱스는 lock에 의한 DML부하가 심한것이 단점.
(설명을 덧붙이자면, 비트맵 인덱스의 경우 DML같은 작업시 B*Tree같은 경우에는 Row단위 Rock을 잡지만 비트맵 인덱스는 키단위로 Rock이 걸리게 되어 엄청난 부하가 될수 있다.) - 하여 웨어하우스 또는 ad hoc 쿼리 환경에 적합하다.
h3.(3)RECORDS_PER_BLOCK
- 앞서 말했던 것과 같이 오라클에서는 한 블럭다 레코드 개수를 제한하고 있으며, 한블럭당 최대 레코드 개수가 730이면, 키 값마다 블록 수 X 730만큼의 비트를 할당한다.
- 하지만 실제 블록ㅇ 저장되는 평균적인 레코드 개수는 여기에 한참 못미치며, 비트맵 인덱스에 낭비되는 공간이 많이 생긴다.
- 이에 오라클은 블록에 저장될 수 있는 최대 레코드 개수를 사용자가 지정할 수 있는 기능을 제공한다.
-- 100만개 레코드를 갖는 T 테이블을 생성
SQL> create table t ( x number, y char(1) ) pctfree 99 pctused 1;
테이블이 생성되었습니다.
SQL> insert into t
2 select mod(rownum,3), 'x' from dual connect by level <= 1000000;
1000000 개의 행이 만들어졌습니다.
SQL> commit;
커밋이 완료되었습니다.
-- Block당 레코드의 개수 확인
SQL> select min(count(*)), max(count(*)), avg(count(*))
2 from t
3 group by dbms_rowid.rowid_block_number(rowid);
MIN(COUNT(*)) MAX(COUNT(*)) AVG(COUNT(*))
------------- ------------- -------------
1 7 6.999958
--비트맵 인덱스 생성
SQL> create bitmap index t_idx on t(x);
인덱스가 생성되었습니다.
SQL> select extents, blocks, bytes/1024 "SIZE(KB)"
2 from user_segments
3 where segment_name = 'T_IDX';
EXTENTS BLOCKS SIZE(KB)
---------- ---------- ----------
17 256 2048
-- 인덱스를 만들고 크기를 측정하면, 총 256개 블록이 할당돼 2MB공간을 차지
-- 인덱스를 삭제 후 T 테이블을 스캔하여 블록당 최대 레코드 개수를 조사
SQL> drop index t_idx;
인덱스가 삭제되었습니다.
SQL> alter table t minimize records_per_block;
테이블이 변경되었습니다. -> 작업이 완료되면, T 테이블에는 블록당 최대 7개 레코드만 저장됨
-- 비트맵 인덱스를 만들면, 오라클은 블록당 최대 7개 레코드가 담기는 것을 기준으로 키 값마다 [블록수 * 7] 만큼의 비트를 할당
SQL> create bitmap index t_idx on t(x);
인덱스가 생성되었습니다.
SQL> select extents, blocks, bytes/1024 "SIZE(KB)"
2 from user_segments
3 where segment_name = 'T_IDX';
EXTENTS BLOCKS SIZE(KB)
---------- ---------- ----------
10 80 640