비용기반의 오라클 원리 (2009년)
비트맵인덱스 - 비트맵 결합 0 0 31,821

by 구루비스터디 비트맵 인덱스 bitmap index 비트맵 결합 [2023.09.23]


II 비트맵 결합


select
	small_vc
from
	t1
where
	n1	= 2	-- one in 20
and	n3	= 2	-- one in 25
;
--------------------------------------------------------------------------------------
| Id  | Operation                    | Name  | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |       |    20 |   340 |    13   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID | T1    |    20 |   340 |    13   (0)| 00:00:01 |
|   2 |   BITMAP CONVERSION TO ROWIDS|       |       |       |            |          |
|   3 |    BITMAP AND                |       |       |       |            |          |
|*  4 |     BITMAP INDEX SINGLE VALUE| T1_I3 |       |       |            |          |
|*  5 |     BITMAP INDEX SINGLE VALUE| T1_I1 |       |       |            |          |
--------------------------------------------------------------------------------------


  • 인덱스 스켄비용 : ceiling(60/20) + ceiling(63/25) = 6, 비트맵 비율 1.1에 의해 6.6
  • 실행계획의 카디널리티 20
  • 80/20 추정을 사용 : 20개의 로우중 4개는 넓게 흩어져 있으며, 나머지 16개는 모여있을 것이다.
  • 평균적으로 블록당 9개의 로우가 존재하므로 16개 로우에 대해서 2개의 블록이 필요, 총 6개 블록이 필요하다.
  • 총 비용 : round(6.6 + 6) = 13
  • 10053 트레이스 파일의 경우 best cost가 12.87로 예상과 매우 비슷하게 나왔다.


  • bitmap and를 사용하는 실행계획을 확인할 때 주목해야 할 세부항목은 인덱스의 선택도 순서대로 정렬되는 듯하므로, 선택도가 제일 좋은(로우를 가장 많이 제거하는) 인덱스가 먼저 처리되어야 한다.



select
	small_vc
from
	t1
where
	n2	= 2	-- one in 20
and	n4	= 2	-- one in 25
;
--------------------------------------------------------------------------------------
| Id  | Operation                    | Name  | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |       |    20 |   340 |     9   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID | T1    |    20 |   340 |     9   (0)| 00:00:01 |
|   2 |   BITMAP CONVERSION TO ROWIDS|       |       |       |            |          |
|   3 |    BITMAP AND                |       |       |       |            |          |
|*  4 |     BITMAP INDEX SINGLE VALUE| T1_I4 |       |       |            |          |
|*  5 |     BITMAP INDEX SINGLE VALUE| T1_I2 |       |       |            |          |
--------------------------------------------------------------------------------------
--> 책과 다름


  • 여기서 사용한 80/20 추정은 대용량 운영환경으로 갈수록 어긋나기 시작한다.
  • 예를 들어, 데이터 크기가 증가하고 사용된 인덱스의 개수가 많아질수록 결과가 달라진다.


낮은 카디널리티

  • 테이블에 여러 비트맵 인덱스가 존재한다면, 오라클은 쿼리가 효율적으로 실행되는 데 필요한 만큼 인덱스를 최대한 많이 사용한다.
  • 비트맵 인덱스의 리프 블록 세트를 하나 더 스켄하는 비용이 조회해야 할 테이블 블록 개수의 감소량 보다 클 때 사용한다.


ex) 3천6백만 로우, 800M(107,543블록), 6가지의 속성 및 비트맵 인덱스를 가지는 테이블

  • 성별 : 2가지
  • 눈의 색 : 3가지
  • 머리카락 색 : 7가지
  • 거주지 : 31가지
  • 연령대 : 47가지
  • 직업분류 : 79가지



	sex	= 1
and	eyes	= 1
and	hair	= 1
and	town	= 15
and	age	= 25
and	work	= 40


  • 인덱스 통계정보는 책 참조 (p.235 표 8-4)
  • town, age, work를 지정하여 식별한 로우의 평군 개수를 산출하면, 옵티마이저가 이들 세 컬럼만으로 테이블 방문을 36,000,000/(31*47*79) = 313 로우로 제한하기에 충분하다고 결정할 것이다. 최악의 경우도 313개 테이블 블록을 방문하는 정도이다.
  • 차선책에 해당하는 hair 인덱스가 테이블 방문 횟수를 0으로 감소시킬지라도 672개의 인덱스 블록을 방문해야 하므로 인덱스 사용의 별 가치가 없다.
  • 위의 조건의 경우 실제로, 정밀도가 높은 세개의 인덱스 만을 사용한다. 쿼리의 총 비용은 314로 보고되었다.
  • 그러나 이들 인덱스에 대해서(blevel + leaf_blocks*유효 인덱스 선택도)의 합계를 보면, 352(164+_114+74)가 된다.
  • 이 합계는 1.1의 배율을 곱해서 테이블 방문 비용을 더하기 전의 값이다.
  • 최종적으로 보고된 비용은 두 인덱스의 통계정보를 무시하고 가장 비용이 낮은 인덱스의 값을 세 번 사용하는 것으로 생각한다.



추측비용 (목표치는 314) =
   74 * 1.1 * 3        + (가장 비용이 낮은 인덱스를 1.1배 증가시켜서 세 번 사용)
   0.8 * 313 / 355     + (로우의 80%는 블록 당 335개씩 모여있음)
   0.2 * 313           = (로우의 20%는 개별 블록에 흩어져 있음)
   244.2 + 62.6 + 0.75 = 307.55 (에러율 2.1%)


  • hair 컬럼을 정렬하여 테스트 사례를 재생성한 후 다시 실행해 보면 4개의 인덱스를 선택한다. (비용 336)


  • 옵티마이저는 언제나 비용이 가장 낮은 실행계획을 선택해야 한다. 위의 결과에서는 비용이 더 높은 경우(314 -> 336)에도 비트맵 인덱스를 사용하였다.
  • 비트맵 인덱스 비용을 계산하는 코드에 약간의 문제가 있는 것이 분명하다. (p.237 ~238 참고)


NULL 컬럼

  • 오라클에게 데이터에 대해서 가능한 많은 정보를 알려주는 것은 언제나 중요하다. NOT NULL 컬럼은 특히 중요한데, 이것은 옵티마이저에게 허용되는 여러 가능성에 큰 차이를 만들 수 있다.



alter table t1 modify n1 not null;
select
	small_vc
from
	t1
where
	n1	!= 2	-- one in 20, scattered
and	n3	= 3	-- one in 25, scattered
;
--------------------------------------------------------------------------------------
| Id  | Operation                    | Name  | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |       |   380 |  6460 |   130   (0)| 00:00:02 |
|   1 |  TABLE ACCESS BY INDEX ROWID | T1    |   380 |  6460 |   130   (0)| 00:00:02 |
|   2 |   BITMAP CONVERSION TO ROWIDS|       |       |       |            |          |
|   3 |    BITMAP MINUS              |       |       |       |            |          |
|*  4 |     BITMAP INDEX SINGLE VALUE| T1_I3 |       |       |            |          |
|*  5 |     BITMAP INDEX SINGLE VALUE| T1_I1 |       |       |            |          |
--------------------------------------------------------------------------------------

alter table t1 modify n1 null;
select
	small_vc
from
	t1
where
	n1	!= 2	-- one in 20, scattered
and	n3	= 3	-- one in 25, scattered
;
---------------------------------------------------------------------------------------
| Id  | Operation                     | Name  | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT              |       |   380 |  6460 |   127   (0)| 00:00:02 |
|   1 |  TABLE ACCESS BY INDEX ROWID  | T1    |   380 |  6460 |   127   (0)| 00:00:02 |
|   2 |   BITMAP CONVERSION TO ROWIDS |       |       |       |            |          |
|   3 |    BITMAP MINUS               |       |       |       |            |          |
|   4 |     BITMAP MINUS              |       |       |       |            |          |
|*  5 |      BITMAP INDEX SINGLE VALUE| T1_I3 |       |       |            |          |
|*  6 |      BITMAP INDEX SINGLE VALUE| T1_I1 |       |       |            |          |
|*  7 |     BITMAP INDEX SINGLE VALUE | T1_I1 |       |       |            |          |
---------------------------------------------------------------------------------------


  • 두 번째 실행계획에 bitmap minus 연산이 두번 나타났음을 주목하라.
  • 비트맵 인덱스는 모든 키가 NULL인 엔트리를 포함하기 때문에, 두 번의 minus 연산이 나타난다.
  • 해당 컬럼이 절대 NULL이 되지 않음을 알고 있다면, 이런 이유에서라도 테이블 정의에 사소한 정보를 더 포함해야 한다.
  • 8i는 첫번째 실행계획이 두번째 실행 계획보다 비용이 낮은것으로 계산 되지만, 9i, 10g에서는 추가적인 bitmap minus 단계를 수행함으로써 쿼리의 비용을 낮출 수 있다고 생각하는 듯 하다.
  • 이것은 합리적인 가정일 수 있지만 NULL값을 가진로우가 없다면 비트맵 비용계산에 대한 알고리즘이 완전히 정확하지 않은 상황도 존재하는 것 같다.


BITMAP MINUS

  • 오라클은 bitmap minus를 수행할 때, 먼저 두 번째 비트맵을 취해서 1은 0으로, 0은 1로 각각 바꾼다.
  • 그리고 이렇게 뒤바뀐 bitmap을 사용하여 bitmap and를 수행함으로써 bitmap minus 연산을 처리한다.


  • 비트맵 or

create table t1
as
with generator as (
   select  --+ materialize
           rownum  id
   from    all_objects
   where   rownum <= 3000
)
select
   /*+ ordered use_nl(v2) */
   decode(
           mod(rownum-1,1000),
                   0, rownum - 1,
                      null
   )                       n1,
   decode(
           mod(rownum-1,1000),
                   0, rownum - 1,
                      null
   )                       n2,
   lpad(rownum-1,10,'0')   small_vc
from
   generator       v1,
   generator       v2
where
   rownum <= 1000000
;

create bitmap index t1_i1 on t1(n1);
create bitmap index t1_i2 on t1(n2);

begin
   dbms_stats.gather_table_stats(
           user,
           't1',
           cascade => true,
           estimate_percent => null,
           method_opt => 'for all columns size 1'
   );
end;
/

select
	small_vc
from
	t1
where
	n1 = 50000
;
--------------------------------------------------------------------------------------
| Id  | Operation                    | Name  | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |       |     1 |    13 |     1   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID | T1    |     1 |    13 |     1   (0)| 00:00:01 |
|   2 |   BITMAP CONVERSION TO ROWIDS|       |       |       |            |          |
|*  3 |    BITMAP INDEX SINGLE VALUE | T1_I1 |       |       |            |          |
--------------------------------------------------------------------------------------


  • n1 컬럼이 NOT NULL인 로우는 정확히 1,000개, 1,000개의 distinct 값, density는 1/1,000이므로 옵티마이저는 카디널리티가 1이라고 결정할 것이다. n1을 n2로 변경해도 마찬가지.



select
	small_vc
from
	t1
where
	n1 = 50000
or	n2 = 50000
;
--------------------------------------------------------------------------------------
| Id  | Operation                    | Name  | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |       |  1999 | 25987 |     2   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID | T1    |  1999 | 25987 |     2   (0)| 00:00:01 |
|   2 |   BITMAP CONVERSION TO ROWIDS|       |       |       |            |          |
|   3 |    BITMAP OR                 |       |       |       |            |          |
|*  4 |     BITMAP INDEX SINGLE VALUE| T1_I1 |       |       |            |          |
|*  5 |     BITMAP INDEX SINGLE VALUE| T1_I2 |       |       |            |          |
--------------------------------------------------------------------------------------


  • 카디널리티 1,999 : 오라클은 NULL을 고려하지 않고 테이블 내 전체 로우의 개수에 density를 적용한 것으로 보인다.
  • 이것은 두 조건의 and 연산에 대한 표준공식을 사용하여 n1 조건에 의한 1,000개(1,000,000 * 1/1,000)의 로우에 n2 조건에 의한 1,000개의 로우를 더한 후, 서로 겹치는 한 개의 로우를 뺀 값이다.



select
	small_vc
from
	t1
where
	n1 = 50000
or	(n2 = 50000 and n2 is not null)
;
--------------------------------------------------------------------------------------
| Id  | Operation                    | Name  | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |       |  1000 | 13000 |     2   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID | T1    |  1000 | 13000 |     2   (0)| 00:00:01 |
|   2 |   BITMAP CONVERSION TO ROWIDS|       |       |       |            |          |
|   3 |    BITMAP OR                 |       |       |       |            |          |
|*  4 |     BITMAP INDEX SINGLE VALUE| T1_I1 |       |       |            |          |
|*  5 |     BITMAP INDEX SINGLE VALUE| T1_I2 |       |       |            |          |
--------------------------------------------------------------------------------------


  • is not null 조건을 하나 추가하면, 계산된 카디널리티가 1,000으로 떨어진다.



select
	small_vc
from
	t1
where
	(n1 = 50000 and n1 is not null)
or	(n2 = 50000 and n2 is not null)
;
--------------------------------------------------------------------------------------
| Id  | Operation                    | Name  | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |       |     1 |    13 |     2   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID | T1    |     1 |    13 |     2   (0)| 00:00:01 |
|   2 |   BITMAP CONVERSION TO ROWIDS|       |       |       |            |          |
|   3 |    BITMAP OR                 |       |       |       |            |          |
|*  4 |     BITMAP INDEX SINGLE VALUE| T1_I1 |       |       |            |          |
|*  5 |     BITMAP INDEX SINGLE VALUE| T1_I2 |       |       |            |          |
--------------------------------------------------------------------------------------


  • is not null 조건을 하나 더 추가하면, 카디널리티가 정확히 1까지 떨어진다.


"코어 오라클 데이터베이스 스터디모임" 에서 2009년에 "비용기반의 오라클 원리 " 도서를 스터디하면서 정리한 내용 입니다.

- 강좌 URL : http://www.gurubee.net/lecture/4418

- 구루비 강좌는 개인의 학습용으로만 사용 할 수 있으며, 다른 웹 페이지에 게재할 경우에는 출처를 꼭 밝혀 주시면 고맙겠습니다.~^^

- 구루비 강좌는 서비스 제공을 위한 목적이나, 학원 홍보, 수익을 얻기 위한 용도로 사용 할 수 없습니다.

댓글등록
SQL문을 포맷에 맞게(깔끔하게) 등록하려면 code() 버튼을 클릭하여 작성 하시면 됩니다.
로그인 사용자만 댓글을 작성 할 수 있습니다. 로그인, 회원가입