꿈꾸는 개발자, DBA 커뮤니티 구루비

B*Tree Inddex Combination

다음과 같은 Query 를 가정해 보자

 
SELECT *
FROM T1
WHERE C1 = 1 AND C2 = 1 ;
{code:SQL}

위의 QUERY 를 가장 효과적으로 실행하는 방법은 무엇인가 ?
COLUMN C1 과 COLUMN C2 에 모두 INDEX 가 있고, 두 개의 INDEX 를 동시에
이용할 수 있다면 가장 적은 일량으로 원하는 결과를 얻을 수 있을 것이다.
Oracle 에서 이런 것을 가능하게 해주는 것이 BITMAP INDEX 이다.

하지만 BITMAP INDEX는 심각한 DML BLOCKING 문제를 유발하기 때문에 OLTP 에서는
사용이 사실상 금지되어 있다. "DML BLOCKING 문제를 일으키지 않으면서 BITMAP INDEX의
장점을 살릴 수 있는 방법은 없을까? 라는 고민을 해결하기 위해 등장한 것이
B*TRRE INDEX COMBINATION 이다.

B*TREE INDEX COMBINATION 의 기본 동작 방식은 다음과 같다.

Index Scan 을 통해 B*Tree Index 의 Key 와 ROWID 값을 읽는다.
Key 값과 ROWID 값을 Bitmap 값으로 변환한다.
Bitmap 연산을 통해 원하는 결과(Bitmap값) 를 도출한다.
Bitmap 값을 다시 ROWID 로 변환해서 원하는 Data 를 추출한다.

원래 Index Combination 은 Bitmap Index 에 대해 쓰이는 용어이다.
즉 Bitmap Index에 대해 Bitmap 연산을 수행하는 것이 Index Combination 의 정확한 정의이다.
Oracle이 이 기능을 확장해서 B*Tree 에 대해서도 Index Combination 이 가능하게
확장한 것으로 이해 할 수 있다.

B*Tree Index Combination 은 다음과 같은 실행 계획으로 표현 된다.


---------------------------------------------------------------------------------
| Id  | Operation                                                | Name         |
---------------------------------------------------------------------------------
|  1  | SORT AGGREGATE                                           |              |
|  2  |  TABLE ACCESS BY INDEX ROWID                             | T_BC1        |
|  3  |   BITMAP CONVERSION TO ROWIDS                            |              |
|  4  |    BITMAP AND                                            |              |
|  5  |     BITMAP CONVERSION FROM ROWIDS                        |              |
|  6  |      SORT ORDER BY                                       |              |
|  7  |       INDEX RANGE SCAN                                   | T_BC1_I2     |
|  8  |     BITMAP CONVERSION FROM ROWIDS                        |              |
|  9  |      SORT ORDER BY                                       |              |
| 10  |       INDEX RANGE SCAN                                   | T_BC1_I3     |
---------------------------------------------------------------------------------

위의 실행 계획은 다음과 같이 해석할 수 있다.

Index t_bc1_i2 를 Range Scan 으로 읽는다.(7단계).
읽은 Data를 정렬(Sort Order By) 해서(6단계),
Bitmap 값으로 변환한다(5단계).
Index t_bc1_i3 를 Range Scan 으로 읽는다.(10단계).
읽은 Data를 정렬(9단계),
Bitmap 값으로 변환한다(8단계).
5번 단계와 8번 단계의 Bitmap 값을 Bitmap And 연산으로 계산하고(4단계),
그 결과를 다시 ROWID로 변환하면서(3단계),
Table 을 방문한다.(2단계)

B*Treee Index 에 대한 Index Combination 은 B*Tree Index 를 동적으로 Bitmap Index 로
변환하는 과정을 거지쳐, 이런 의미에서 다른 DBMS 에서는 동일한 기능을 Dynamic Bitmap Index
라는 이름으로 부르기도 한다.

B*Tree Index Combination 과 Bitamp 연산

 
SYS> drop table t1 purge ;
Table dropped.

SYS> create table t1 (c1 int, c2 int, c3 int);
Table created.

-- Column C1 과 Column C2 가 서로 반대의 순서가 되도록 Data 생성 
SYS>insert into t1 select mod(level,10)+1, 10-mod(level,10)-1,level from dual connect by level <= 10000 ;
10000 rows created.

SYS> create index t1_n1 on t1 (c1) ;

Index created.

SYS> create index t1_n2 on t1 (c2) ;

Index created.

SYS> create index t1_n3 on t1 (c3 ) ;

Index created.

SYS>@gather t1
PL/SQL procedure successfully completed.


-- Column c1 과 Column c2 가 모두 조건 절에 사용된 경우 다음과 같이
B*Tree Index Combination 이 선택된다. [ 안탄다 ㅡㅡ; ]

SQL> explain plan for select count(c3) from t1 where c1=1 and c2=1 ;
Explained.

SQL> @plan

PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------------
Plan hash value: 3892869488

--------------------------------------------------------------------------------------
| Id  | Operation                    | Name  | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |       |     1 |    39 |     1   (0)| 00:00:01 |
|   1 |  SORT AGGREGATE              |       |     1 |    39 |            |          |
|*  2 |   TABLE ACCESS BY INDEX ROWID| T1    |     1 |    39 |     1   (0)| 00:00:01 |
|*  3 |    INDEX RANGE SCAN          | T1_N1 |     1 |       |     1   (0)| 00:00:01 |
--------------------------------------------------------------------------------------


PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------

   2 - filter("C2"=1)
   3 - access("C1"=1)

16 rows selected.


-- 강제로 힌트를 주어두 B*Tree Index Combination 이 발생하지 않는다. 
-- 아무리 해두 B*Tree Index 에 대한 Index Combinaton 이 유도 되지 않는다. ㅜ_ㅜ
QL> select /*+ gather_plan_statistics  index_combine(t1 t1(c1) t1(c2)) */ count(c3) from t1 where c1=1 and c2=1 ;

 COUNT(C3)
----------
         0

SQL> @stat

PLAN_TABLE_OUTPUT
-----------------------------------------------------------------------------------------------------------

SQL_ID  77r0m910c76jm, child number 0
-------------------------------------
select /*+ gather_plan_statistics  index_combine(t1 t1(c1) t1(c2)) */ count(c3) from t1 where c1=1
and c2=1

Plan hash value: 3892869488

-------------------------------------------------------------------------------------------------------------
| Id  | Operation                    | Name  | Starts | E-Rows | Cost (%CPU)| A-Rows |   A-Time   | Buffers |
-------------------------------------------------------------------------------------------------------------
|   1 |  SORT AGGREGATE              |       |      1 |      1 |            |      1 |00:00:00.01 |       1 |
|*  2 |   TABLE ACCESS BY INDEX ROWID| T1    |      1 |      1 |     1   (0)|      0 |00:00:00.01 |       1 |
|*  3 |    INDEX RANGE SCAN          | T1_N1 |      1 |      1 |     1   (0)|      0 |00:00:00.01 |       1 |
-------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - filter("C2"=1)
   3 - access("C1"=1)

21 rows selected.

Bitmap 연산에 의해 Table 의 방문 회수가 줄어드는 경우에만
B*Tree Index Combination 이 유리하다.

B*Tree Index Combination 이 발생한 경우에 대한 Plan Statistics 정보에서
Memory 사용량 정보가 추가로 출력될 수 있다는 것에 유의해야 한다.
Bitmap Conversion 을 수행하기 위해 내부적으로 정렬(Sort Orderb By)과
Bitmap 연산이 발생하기 때문에 추가적인 Memory 사용이 불가피하다.

B*Tree Index Combination 의 뛰어난 결과에 고무되겠지만,
몇 가지 함정이 있다

우선 B*Tree Index Combination 은 OLTP 환경에서 Bitmap Index 가 가진 장점을 흉내내기
위해 고안된 것이라는 것을 명심하자. Bitmap Index 를 대신할 수 있는 것은 아니다.
OLAP 환경에서는 여전히 Bitmap Index 의 사용이 필수 불가결하다.
B*Tree Index Combination 이 항상 성능에 유리한 것은 아니다.
여러 개의 Index 를 사용하는 과정에서 Table 방문 회수를 상당히 줄일 수 있는
경우에만 유리하다고 할 수 있다.
B*Tree Index Combination 은 내부적으로 추가적인 연산을 수행하기 때문에 좀더 많은
Memory 사용을 필요로 한다. 같은 이유로 좀 더 많은 CPU 자원을 필요로 한다.
이것이 암시하는 것은 Logical Reads 만이 성능 개선의 판단 기준은 아니라는 것이다.
Logical Reads 는 줄지만 Memory 와 CPU 자원을 더 많이 사용한다면 판단은 좀 더 어려워진다.

Hints and Parameters

B*Tree Index Combination 은 INDEX_COMBINE Hint 를 통해서 제어한다.

 
 select /* index_combine(t1) */ c1 from t1 ;
 select /* index_combine(t1 t1_n1 t1_n2) */ c1 fro t1 ;
 select /* index_combine(t1 t1(c1) t1(c2) ) */ c1 from t1 ;

B*Tree Index Combination 의 동작 여부는 _B_TREE_BITMAP_PLANS Parameter 를
이용해 제어할 수 있다.


SQL> @check_hidden_parameter.sql
Enter value for input_parameter: _b_tree_bitmap_plans
old  15: a.ksppinm LIKE '&input_parameter'
new  15: a.ksppinm LIKE '_b_tree_bitmap_plans'

Parameter                                                    Session Value                  Instance Value
------------------------------------------------------------ ------------------------------ ------------------------------
_b_tree_bitmap_plans                                         TRUE                           TRUE

문서에 대하여

최초작성일 : 2009년 2월 14일
이 문서는 오라클클럽 코어 오라클 데이터베이스 스터디 모임에서 작성하였습니다.
{*}이 문서의 내용은 조동욱님의 'Optimizing Oracle Optimizer'을 참고하였습니다.*