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

비트맵 인덱스의 탄생 배경

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


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


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,>,<,>=,<= 등의 사용시 분리
  • 저장시 선분형태로 저장되기 때문에 빈번한 수정이 발생되는 컬럼에서는 블록레벨 잠금등으로 많은 부하가 유발될수 있음

비트연산의 실행계획
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 이상부터는 비트맵조인인덱스도 지원한다.

'Database > Oracle' 카테고리의 다른 글

Architecture  (0) 2010.05.04
도메인 인덱스(Domain Index)  (0) 2010.04.28
함수기반 (Function Based) 인덱스의 활용  (0) 2010.04.28
비-트리 인덱스(B-Tree Index)  (0) 2010.04.27
Db file sequential read  (0) 2010.04.26
1. 컬럼의 중간 부분의 검색

    create index from_loc_idx on orders (substr(ship_id,5,3));
    create index repair_loc_idx on orders (substr(ship_id,3,2), ord_date);


2. 조인 연결고리 컬럼이 대응하지 않는 경우의 해결


  ......

    from  item_group x, items y
    where x.class1||x.class2||x.class3 = y.group_cd ......
   
    ......
    from  item_gropu x, items y
    where x.class1 = substr(y.group_cd,1,2)
    and   x.class2 = substr(y.group_cd,3,2)
    and   x.class3 = substr(y.group_cd,5,3)
    ......
 
    create index group_cd_idx_ on item_group (class1||class2||class3);


3. 일자 컬럼이 분할된 경우의 해결

    where sal_yyyy >= '2005' and sal_mm >= '12' and sal_dd >= '10'    (x)
    where sal_yyyy||sal_mm||sal_dd >= '20051210'                           (o)  문제점 : Index 사용불가

    create index sal_date_idx on sales (sal_yyyy||sal_mm||sal_dd);
 

4. 데이타 타입이 상이한 조인 컬럼

    create index deptno_idx on emp(to_number(deptno));


5. 조인 컬럼이 경우에 따라 달라지는 경우

    .......
    from  sales s, department d
    where d.deptno = (case when sal_type = 1 then sal_dept else agent_no end)
    and   d.location = 'BUSAN'
    .......
 
    create index deptno_idx on sales
           (case when sal_type = 1 then sal_dept else agent_no end);
          
     
6. 대/소문자나 공백이 혼재된 컬럼의 검색

    create index ename_upper_ix on employees (upper(ename));
 
    create index ename_upper_ix on employees (upper(replace(ename,' '));


7. NULL 값을 치환하여 검색

    .....
    where  :input_date between start_date and nvl(end_date, '99991231');
    .....
   
    create index end_date_idx on account_history (nvl(end_date, '99991231'), start_date);


8. 복잡한 계산 결과의 검색

    create index order_amount_idx on order_items
        (item_cd, (order_price - nvl(order_discount,0)) * order_count));
       
    select /*+ index_desc(x order_amount_idx) */ *
    from   order_items x
    where  item_cd = :b1
    and    rownum <= 100;


9. 기간, 컬럼 길이 검색

    create index item_idx on activities (expire_date - start_date);
   
    create index source_length_idx on print_media (text_length(source_text));


10. 배타적 관계의 유일성 보장

    create unique index official_id_idx on customers
          (case when cust_type = 1 then resident_id else business_id end);
      
    select * from customers
    where (case when cust_type = 1 then resident_id else business_id end) = :b1;


함수기반 인덱스는 버전에 따라 제약사항에 차이가 있으므로 관련 메뉴얼을 참조하세요.


<참조> 새로쓴 대용량 데이타베이스 솔루션

'Database > Oracle' 카테고리의 다른 글

도메인 인덱스(Domain Index)  (0) 2010.04.28
비트맵 인덱스(Bitmap Index)  (0) 2010.04.28
비-트리 인덱스(B-Tree Index)  (0) 2010.04.27
Db file sequential read  (0) 2010.04.26
USER_CONS_COLUMNS  (0) 2010.04.22
2.1 B-tree 인덱스
* B-tree 인덱스에 대한 개괄
- 데이터베이스에서 가장 많이 쓰이는 인덱스이다.
- 오라클의 경우 CREATE INDEX 명령어를 사용하여 생성된다.
- B-tree의 B는 Balanced의 약자로 트리의 맆노드의 깊이가 같다는 균형을 의미한다.  
- 검색시 걸리는 시간은 모든 데이터가 트리의 깊이 만큼 시간이 걸린다.

[참고] CREATE INDEX 문에 의하여 생성되는 인덱스
- Default - B-tree 인덱스
- 비트맵 인덱스
- Partitioned 인덱스
- 함수-기반 인덱스
- 도메인 인덱스

* B-tree의 성능
- B-tree의 검색 속도는 트리의 깊이 d에 의하여 좌우된다.
- 트리의 깊이 d는 데이터가 많아지면 깊어지지만 값이 크지 않아 큰 영향을 주지 않는다.
- 트리의 깊이 d를 줄이려면 브랜치블록 노드에 저장하는 key 값의 수 k를 늘린다.
- 키의값개수  k를 결정은 블록노드의 크기에 관계있으나 블록노드의 크기는 시스템의 디스크 블록의 크기와 관계가 있다.
  (즉 무한정 많이 저장할수는 없다)
- 깊이가 d인 B-tree에 저장되는 데이터 키 값의 전체 개수는 약 kd-1이다.
- 예를 들어 브랜치블록이 200개이고 깊이가 3인 B-tree에 저장할 수 있는 키값은 800만개이다.
  (무척 많이 저장할 수 있다. 실제 오라클에서 어느 정도 저장하는지?)
- 오라클의 경우 B-tree인덱스는 CREATE INDEX 명령어를 사용하여 생성된다.
- B-tree의 B는 Balanced의 약자로 트리의 맆노드의 깊이가 같다는 균형을 의미한다.  
- 검색시 걸리는 시간은 모든 데이터가 트리의 깊이만큼 시간이 걸린다.

2.1.1 B-tree 인덱스의 구조
- B-tree는 루트(root)블록, 브랜치(branch)블록, 리프(leaf)블록으로 구성된다.
- 인덱스 부분은 루트블록과 브랜치블록으로 같은 구조이다.
- 브랜치블록(이하 루트블록 포함)은 k개 이하의 키값을 저장한다.
- 브랜치블록은 k+1개의 자식 노드를 갖는다.
- 유일스캔 데이터검색은 루트노드부터 시작하여 검색키값과 브랜치블록 노드에 저장된 킷값을 비교하여 분기를하여 리프블록을 찾을 때까지 계속 내려간다.
- 범위검색은 먼저 시작하는 값을 유일스캔하여 해당 리프블록을 찾은 다음 리프블록만을 따라가며 검색한다.
* 튜플의 ROWID 길이 : 실험결과 책과달리 18자리임?, 예) AAAM3lAABAAAPCiAAA

<!--StartFragment-->

2.1.2 B-tree 인덱스의 조작
- B-tree 인덱스의 가장 큰 당면 문제는 데이터 삽입, 삭제 관리이다.

가) 인덱스 생성
- 비어있는 테이블에서 인덱스 생성은 간단히 루트블록만 생성하면된다.
- 그러나 사용중인 테이블에서의 인덱스를 생성할 경우?
  [그림 1-2-4 참조]
   (알고리즘)
   1. 데이터를 모두 정렬한다
   2. 데이터를 리프블록에 순서대로 저장을 시작한다.
   3. 리프블록이 2개 이상으로 늘어나기 시작하면 브랜치블록을 생성한다.
- 브랜치블록에 저장되는 킷값의 개수는 DB_BLOCK_SIZE가 클수록 PCTFREE 값이 작을수록 유리하며, 키값의 길이가 짧은 것이 유리하다.
- 키값의 길이를 줄이는 방법은 키값을 압축하는 방법이다.
  SQL문의 예)  CREATE INDEX ord_customer_idx
                      ON orders(customer_id, sales_id) COMPRESS 1;

나) 인덱스블록의 분할(데이터 삽입)
- 데이터의 삽입이 될 때 인덱스블록의 분할이 발생한다.
- 데이터가 삽입될때
  case 1 : 데이터블록이 여유가 있다(PCTFREE 값보다 작다)
    => 바로 저장(문제없음)
  case 2 : 데이터블록이 여유가 없다.
       case 21 : 데이터가 마지막 값이면[그림 1-2-5의 아래부분]
             => 새로운 블록을 생성하여 여기에 삽입된 데이터를 저장하고 상위 브랜치블록에 이 값을 전달
       case 22 : 데이터가 중간 값이면[그림 1-2-5의 위부분]
             => 블록을 2개로 균등 분할(새로들어간 데이터를 포함하여)하여 브랜치블록에 중간 키 값을 전달
        * case 21, 22에서 분할된 키값을 상위 브랜치블록에 전달했을 경우 만약 브랜치블록 또한
                   PCTFREE 값을 초과했을 경우에는 브랜치블록을 다시 분할하며 상위 브랜치블록에 다시 전달하며
                   이 과정이 루트블록에 도달항 때까지까지 진행된다.  
- 데이터의 삽입과 삭제가 빈번하다보면 저장공간의 활용의 효율성이 떨어질 수 있다
  이 경우는 인덱스를 재생성(rebuild) 한다.
  SQL 사용예) ALTER INDEX emp_index REBUILD ONLINE;

다) 데이터의 삭제및 갱신
- 데이터를 삭제할 경우는 삭제된 데이터의 위치에 삭제를 표시하는 flag로 해결한다.
- 데이터블록에 저장된 데이터가 모두 삭제될 경우는 상위 브랜치블록의 해당로우에 삭제 표시를 한다.
- 데이터의 삽입과 삭제가 빈번한 테이블은 정기적으로 인덱스를 재생성한다.
라) 인덱스를 경유한 검색
- B-tree 인덱스를 이용한 검색은 루트블록에서 시작한다.
- [그림 1-2-6의 예] col1+col2의 복합인덱스에서 col1=B and col2=ACC를 검색
  1. 루트블록을 검색한다. col1=B와 같거나 큰 브랜치블록 21를 찾았다.
  2. 21번 브랜치블록에서 col2=ACC에 해당하는 20번 데이터블록을 찾았다.
  3. 20번 데이터블록에서 Rowid 값을 찾는다.  
- 범위 검색일 경우는 위 과정에서 찾은 Rowid를 이용하여 데이터블록을 검색한다.

2.1.3 리버스 키 인덱스

- 데이터가 비슷한 킷값을 가지고 지속적으로 발생하는 경우 B-tree 인덱스에서 비슷한 영역에 계속 저장되게 된다.
  이렇게 되면 인덱스 구조가 비효율적일 수 있다.
- 이 문제를 해결하려면 키값을 역전(reverse) 시킨 다음에 인덱스에 저장하는 방법이 리버스키인덱스 방법이다.
- 동등(=) 검색이 아닌 LIKE, BETWEEN을 사용해야하는 경우는 불가능하다.
- 데이터 검색시 같은 브랜치블록에 접근이 몰리는 것을 피할 수 있다.  
- 인덱스를 생성할 때 NOSORT 옵션을 사용할 수없으며, 비트맵인덱스, 일체형인덱스에서는 사용할 수없는 단점이 있고, 실제 적용 사례는 많지 않다.

'Database > Oracle' 카테고리의 다른 글

비트맵 인덱스(Bitmap Index)  (0) 2010.04.28
함수기반 (Function Based) 인덱스의 활용  (0) 2010.04.28
Db file sequential read  (0) 2010.04.26
USER_CONS_COLUMNS  (0) 2010.04.22
DBA_USERS  (0) 2010.04.22

오라클은 사용자가 요청한 데이터가 SGA의 버퍼 캐쉬에 존재하지 않을 경우 서버 프로세스가 데이터 파일로부터 해당 데이터 블록을 버퍼 캐쉬로 로드한다. 이를 Conventional Path I/O라 한다. Conventional Path I/O는 멀티 블록 I/O 방식과 싱글 블록 I/O 방식으로 나뉘어지게 된다. 멀티블록 I/O 방식은 한 번에 여러 개의 연속된 블록을 읽어 들이는 작업을 수행하는 I/O이며, 싱글블록 I/O 방식은 한 번에 하나의 블록만 읽어 들이는 작업을 수행하는 I/O 이다.

오라클에서는 Conventional Path I/O가 발생하게 되면 두 가지의 대기 이벤트를 통해 멀티 블록 I/O가 발생하였는지 싱글 블록 I/O가 발생하였는지를 알 수 있도록 하였다. 이 두 가지 대기 이벤트가 db file sequential read / db file scattered read 이벤트이다. 해당 이벤트들은 오라클에서 가장 보편적으로 발생하는 대기 이벤트이다. 데이터 파일에서 블록을 읽으려면 멀티 블록 I/O나 싱글 블록 I/O를 수행할 수 밖에 없기 때문이다.

db file sequential read 이벤트는 싱글블록 I/O와 함께 발생하는 대기 이벤트이다. 한 번의 싱글블록 I/O가 발생할 때마다 한 번의 db file sequential read 이벤트 대기가 발생한다. 싱글 블록 I/O는 파일로부터 하나의 블록을 읽는 모든 작업들에서 발생 가능하다. 보통 인덱스 스캔, ROWID에 의한 테이블 스캔, 컨트롤 파일(Control file), 파일 헤더(File header)를 읽을 때 발생한다.


http://wiki.ex-em.com/index.php/Db_file_sequential_read

'Database > Oracle' 카테고리의 다른 글

함수기반 (Function Based) 인덱스의 활용  (0) 2010.04.28
비-트리 인덱스(B-Tree Index)  (0) 2010.04.27
USER_CONS_COLUMNS  (0) 2010.04.22
DBA_USERS  (0) 2010.04.22
DBA_TABLESPACES  (0) 2010.04.22

+ Recent posts