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

4. 단순 B-tree 액세스

4. 단순 B-tree 액세스

B-Tree 인덱스를 사용하여 단일 테이블을 액세스하는 비용을 계산할 때 옵티마이저가 사용하는 계산식에 알아보자.

기본적인 인덱스 비용 계산식

인덱스를 이용한 전형적인 액세스 경로

조건식에 사용된 일부 컬럼에 인덱스가 정의되어 있다.
인덱스 루트(Root)블록을 찾아간다.
인덱스 브랜치(Branch) 레벨을 경유해 리프(Leaf)블록을 찾아 내려가는데, 이때 찾아진 블록은 검색조건에 부합하는 첫 번째 엔트리(시작 키 값)가 있는 유일한 장소이다.
리프 블록 간 연결고리(Chain)를 따라 진행하닥 검색 조건에 부합하는 마지막 엔트리(종료 키 값)를 지나치는 지점에서 멈춘다.
각 인덱스 엔트리에 대해 테이블 블록을 방문할지 여부를 결정한다.

SKIP SCAN

인덱스 리프 블록 간에는 양방향으로 포인터를 통해 연결돼 있으므로 인덱스 사용을 위한 기본적인 Range Scan 매커니즘은, 스캔을 시작할 블록을 찾기 위해 한 번만 브랜치 레벨을 통해 아래로 내려가야 한다.
Skip Scan 매커니즘에서는 브랜치 레벨을 따라 위아래로 이동해야 한다. 따라서 공식이 다를 뿐 아니라 버퍼를 PIN하는 전략 또한 달라 지며, 리프 블록을 스캔하는 동안 루트에서 현재 읽는 리프 블록까지의 경로 상에 있는 모든 블록을 PIN하는 것 같다. 곧바로 다시 액세스할 브랜치 블록인데 다른 프로세스가 해당 버퍼 블록을 Split 하면 안 되기 때문에 그렇게 하는 것이다.

인덱스 비용 계산

비용 = blevel + ceiling(리프 블록 수 * 유효 인덱스 선택도) + ceiling(클러스터링 팩터 * 유효 테이블 선택도)

blevel 은 인덱스 구조를 따라 내려가면서 읽어야 하는 블록 방문 횟수를 의미
Ceiling(리프 블록 수 * 유효 인덱스 선택도 ) : 주어진 입력값 집합과 매칭되는 ROWID를 모두 얻고자 스캔해야할 리프 블록 개수를 나타낸다. 유효 인덱스 선택도(effective index selectivity)는 10053 트레이스 파일에서 ix_sel이라고 표시된 엔트리에 해당된다.
Ceiling(클러스터링 팩터 * 유효 테이블 선택도) : 선택된 인덱스를 경유해서 최종적으로 테이블 로우를 읽고자 방문해야 할 테이블 블록 수를 나타낸다. 유효 테이블 선택도(Effective table selectivity)는 10053트레이스 파일에서 tb_sel이라고 표시된 엔트리에 해당한다. 참고로 10g 트레이스 파일에서는 (더 정확한 의미를 담아) ix_sel_with_filters라고 표기하기 시작했다. 대개, 이 라인이 전체 비용 중에서 가장 큰 비중을 차지하는 부분이고, B-tree 이덱스를 사용할 때의 비용 계산 시 가장 큰 오차를 일으키기도 한다.

인덱스 높이

Sequence-based 의 인덱스인 경우 맨 우측 노드에 추가적인 계층을 양산한다는 공방이 이어지고 있다. 하지만, 이런 일은 실제 발생하지 않는다. 리프 블록이 분할될 때 트리 구조에 변화가 필요하면 그 영향은 위쪽으로 향하며 절대 아래쪽으로 진행하지 않는다. 다시 말하지만, 균형(balanced) B-tree의 모든 리프 블록은 루트로부터 같은 거리를 유지한다.

테스트 시나리오


create table t1 nologging
as
select
trunc(dbms_random.value(0,25)) n1, rpad('x',40) ind_pad, trunc(dbms_random.value(0,20)) n2, lpad(rownum,10,'0') small_vc, rpad('x',200) padding
fromall_obj
ectswhererownum <= 10000 ;

create index t1_i1 on t1(n1, ind_pad, n2)
nologging pctfree 91

-- 코드 설명* 처음 생성될 브랜치에 PCTFREE가 적용되지 않고, IND_PAD가 모든 로웨 같은 값을 가지므로 
-- 전체 통계와 분산도에는 영향을 미치지 않으면서 오라클이 각 브랜치 블록에 적은 수의 로우만을 갖도록 하였음이로 인해 
-- 인덱스 높이를 증가시켜 blevel 2로 만들었다.

인덱스에서의 PCTFREE

인덱스에서의 PCTFREE는 단지 인덱스를 생성 및 재생성 할 대, 또는 병합(coalesced)하는 작업에만 관련 있고, 그것은 리프 블록에만 적용된다. 테이블에 대한 PCTFREE 스토리지 파라미터는 오라클에게 해당 블록에 더 이상의 새로운 로우 삽입을 멈춰야 하는 시점을 알려주며, 그렇게 약간의 공간을 확보해 두고 각 블록 안에 있는 로우를 갱신 할 때 사용한다. 그러나 인덱스에 저장된 엔트리는 절대 수정되지 않는다. 인덱스 엔트리를 변경하면 이 엔트리는(대개는) 인덱스 내 다른 어딘가로 옮겨지며, 업데이트할 때 실제로는 Delete & Insert 방식으로 이루어진다. 따라서 인덱스에 대해서는 업데이트를 위한 공간을 예약해 두는 게 아니라 새로운 로우 삽입을 위한 공간을 예약하는 것이다.

통계 정보


TABLE_NAME BLOCKS NUM_ROWS
-------------------- ---------- ----------
T1 371 10000
NUM_ROWS DISTINCT_KEYS BLEVEL LEAF_BLOCKS CLUSTERING_FACTOR AVG_LEAF_BLOCKS_PER_KEY AVG_DATA_BLOCKS_PER_KEY
---------- ------------- ---------- ----------- ----------------- ----------------------- -----------------------
10000 500 2 1111 9745 2 19
COLUMN_NAM NUM_NULLS NUM_DISTINCT DENSITY
---------- ---------- ------------ ----------
IND_PAD 0 1 1 N1 0 25 .04 N2 0 20 .05

select small_vc
fromt1
wheren1 = 2
and ind_pad = rpad('x',40)
and n2 = 3 ;
---------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost |
---------------------------------------------------------------------
| 0 |SELECTSTATEMENT | | 20 | 1160 | 25 |
| 1 | TABLE ACCESSBYINDEX ROWID| T1 | 20 | 1160 | 25 |
|* 2 | INDEX RANGE SCAN | T1_I1 | 20 | | 5 |
---------------------------------------------------------------------

비용 계산 방법은 ?

첫 번째 부분은 인덱스를 방문하는 라인 2(Cost=5) 에 나타나 있다.
그 중 2 만큼은 브랜치 레벨을 따라 리프 블록까지 내려가는 데 대한 비요일 것이다. (belvel이 2 였음).
'3'만큼의 비용은 옵티마이저가 필요한 20개의 rowid를 얻기 위해 스캔해야 할 리프 블록 수가 3개일 것이라고 짐작 할 수 있음
테이블 방문 비용이은 '20'이다. 대략 20개 로우를 뽑아 오는데, 로우들이 테이블 전체에 고르게 흩어져 있음을 이미 알고 있으므로 테이블 라인에서 비용이 20만큼 증가 했다는 사실과 20개의 다른 로우를 얻고자 20개의 다른 블록을 방문해야 한다는 사실을 짐작 할 수 있다.

유효 인덱스 선택도

선택도

제공된 조건절에 기초해서 옵티마이저가 현재의 데이터 집합에서 선택할 것으로 에상하는 로우 비율을 의미 한다.
N1=(constant)(Target : 25개당 1개 로우 = 로우의 4% = 0.04 * 로우 수)
Ind_pad=(constant)(Target : 모든 로우 = 로우의 100% = 1*로우 수)
N2 = (constant)( target : 20개당 1개 로우 = 로우의 5% = 0.05 * 로우 수)
선택도 (X and Y and Z) =
선택도((X and Y) and Z) =
선택도(X and Y) * 선택도(Z) = 선택도(X) * 선택도(Y) * 선택도(Z)

=> 0.04 * 1 * 0.05 = 0.002 ( 이는 3개의 조건절로 쿼리했을 때 전체 인덱스 엔트리 중에서 0.2% 만큼을 방문하게 될 것임을 의미)

인덱스 리프 블록들이 정렬된 순서로 서로 모여 있으므로전체 인덱스 로우 중 X%를 조사할 것으로 계산했다는 것은 리프 블록의 X%를 스캔할 것이라는 의미이다.그래서 비용계산식 구성요소에 리프 블록수 \유효 인덱스 선택도가* 포함된 것이다.

대개 옵티마이저는 실제로 개별 선택도를 곱해서 전체 선택도를 계산하며, 결합 인덱스 선택도를 조회하지는 않는다.
데이터 분포가 고르지 않은 상황에서는 인덱스의 distinct값의 개수를 이용하는 방법은 신뢰하기 어려우므로, 적절한 히스토그램이 존재한다면 개별 컬럼 선택도를 곱하는 전략이 전략이 일반적인 해결책일 것

유효 테이블 선택도


select
	small_vc
from
	t1
where
	n1	= 2
and	ind_pad	= rpad('x',40)
and	n2	= 3
and     small_vc = '0000000001'

- 위에 처럼 조건절을 하나 더 추가(and     small_vc = '0000000001' 추가)할 경우를 보면, 옵티마이저가 현재 생성해 둔 인덱스를 경유해 테이블을 방문하기로 했다면 테이블을 액세스하기 전까지는 마지막에 추가된 이 조건을 체크할 수 없다.
- 이 조건은 테이블을 방문해야 할 데이터 비율에는 미치지 않으며, 최종적으로 턴하는 데이터 비율에만 영향을 미친다.
- 이 사례에서는 테이블에 대한 조건절 모두 인덱스 액세스 단계에서 체크가 가능하므로 유효 테이블 선택도 역시 0.04 * 1* 0.05 = 0.002이다.

클러스터링 팩터

클러스터링 팩터는 인덱스 정렬 상태와 테이블의 무질서하게 흩어진 정도를 비교하는 측정 방법이다.
옵티마이저는 인덱스의 정렬된 순서대로 테이블 블록들을 찾아가는데, 한 블록에서 다른 블록으로 얼마나 여러 번 점프했는지를 계속 추적함으로써 클러스터링 팩터를 계산한다. (실제로는 클러스터링 팩터를 계산하는 코드는 인덱스만을 스캔하면서 거기서 읽은 rowid로부터 테이블 블록 주소를 추출해 낸다)
한번 점프할 때 마다 카운터 변수를 1씩 증가시키고, 그렇게 계산된 카운터의 최종 값이 클러스터링 팩터이다.
클러스러링 팩터는 통계 정보 수집 시 그것이 가질 수 있는 가장 작은 값은 총 테이블 블록 수와 같고, 가장 큰 값은 총 테이블 로우 수와 같아야 한다

인덱스와 클러스터링 팩터

좋은 인덱스는 낮은 클러스터링 팩터를 갖고, 안 좋은 인덱스는 높은 클러스터링 팩터를 갖는다는 상식이 매우 일반화 되었다. 이런 설명은 클러스터링 팩터가 갖는 의미적인 측면에서 분명히 어느정도 진실성이 있다. 하지만,오라클에 대해 얘기할 때 '낮은', '높은', '작은', '큰'과 같은 말, 그리고 '0에 가까운'과 같은 표현에 항상 반감이 생긴다. 10,000이란 수치는 클러스터링 팩터가 과연 낮은 것인가 높은 것인가? 테이블 10,000개 블록을 가졌다면 낮은 것이고, 100개 블록만을 가졌다면 높은 것이다. 그래서 user_tables와 user_indexes를 조인하는 두 개의 작은 스크립트(그리고 파티션 테이블 등을 위한 또 다른 스크립트)를 작성해서 중요한 수치를 비교하기를 원할 수 있다.

인덱스 액세스 비용에 대한 종합적입 검토

비용 = blevel + Ceiling(리프 블록 수 *유효 인덱스 선택도) + Ceiling(클러스터링 팩터 *유효 테이블 선택도)

브랜치 레벨 (bleve) = 2
유효 인덱스 선택도 = 0.002
리프 블록 수 (leaf_blocks)=1,111
유효 테이블 선택도 = 0.002
클러스터링 팩터(clustering_factor) = 9745

테이블 총 로우수 = 10000
2+ceiling(1, 111 * 0.002) + ceiling(9745 * 0.002)
= 2+ceiling(2.222) + ceiling(19.49)
= 2 + 3 + 20
= 5+20 = 25

B-tree 인덱스를 사용하는 일반적인 환경은 다음과 같다.

일반적으로 blevel은 3이하(대개는 2)이고, 특별한 경우에만 4임
인덱스는 밀도있게 채워지는 경향이 잇음
인덱스 엔트리는 테이블 로우보다 그 폭이 더 작기 때문에 대개 인덱스 리프 블록이 테이블 블록보다 훨씬 더 많은 엔트리를 유지함
인덱스 내의 리프 블록 수는 테이블 내의 블록 수와 비교할 때 일반적으로 더 적음

인덱스 재생성

인덱스를 재생성했을 때, 종종 인덱스의 리프 블록 수가 감소하거나 아주 가끔 브랜치 레벨이 감소할 수는 있지만 클러스터링 팩터에는 영향을 주지 않는다.
인덱스를 재생성 했을 때 인덱스 크기가 감소하는 효과 때문에 옵티마이저가 그 인덱스를 더 선호하게 하는 결과를 가져올 수 있다.
그런데 그 효과가 긍정적일 수 있지만 부정적일 수도 있다.
긍정적 측면에서 보면, 인덱스 재생성이 쿼리 시점에 그 인덱스가 캐싱되어 있을 가능성을 크게 하는 이점을 가져 올 수 있다.
반대로 인덱스 크기가 감소해서 생기는 부정적 효과로는, DML 작업시 경합에 의한 불이익을 당할 가능성이 커진다는 점과 인덱스의 균형 상태를 유지하기 위한 '시도'때문에 LEAF BLOCKS SPLITS 증가와 REDO 증가를 불러올 수 있다는 점을 들 수 있다.
모순되는 얘기 같지만, 정기적으로 인덱스를 재생성해 주어야 그 인덱스는 더 이상 인덱스 재생성을 필로 하지 않는다.
옵티마이저가 제대로 작동하길를 원한다면 인덱스가 빈틈없이 압축되도록 만들려고 노력하는 것보다
CLUSTERING_FACTOR가 실제의 데이터 흩어짐 정도를 제대로 표현하는지 여부를 확인하고 그것에 대한 어떤 조치를 취하는 것이 더 중요하다.

인덱스 액세스 비용에 대한 종합적입 검토

범위 기반 검색조건의 비용계산


select
	small_vc
from
	t1
where
	n1	= 2
and	ind_pad	= rpad('x',40)
and	n2	between 1 and 3
;
----------------------------------------------------------
| Id  | Operation         | Name | Rows  | Bytes | Cost  |
----------------------------------------------------------
|   0 | SELECT STATEMENT  |      |    82 |  4756 |    37 |
|*  1 |  TABLE ACCESS FULL| T1   |    82 |  4756 |    37 |
----------------------------------------------------------

select
	/*+ index(t1) */
	small_vc
from
	t1
where
	n1	= 2
and	ind_pad	= rpad('x',40)
and	n2	between 1 and 3
;
---------------------------------------------------------------------
| Id  | Operation                   | Name  | Rows  | Bytes | Cost  |
---------------------------------------------------------------------
|   0 | SELECT STATEMENT            |       |    82 |  4756 |    93 |
|   1 |  TABLE ACCESS BY INDEX ROWID| T1    |    82 |  4756 |    93 |
|*  2 |   INDEX RANGE SCAN          | T1_I1 |    82 |       |    12 |
---------------------------------------------------------------------

선택도(n2 between 1 and 3) =

요청한 범위 / 전체 범위 + 1 / num_distinct +1/num_distinct = (3 - 1) / (19 - 0) + 1/20 + 1/20 = 0.205263

유효 인덱스 선택도 = 1 * 0.04 * 0.205263 = 0.0082105


유효 테이블 선택도 = 1 * 0.04 * 0.025263 = 0.0082105
Cost = 2 + ceiling (1,111 * 0.0082105 ) + ----10
            Ceiling (9745 * 0.0082105 ) + ----81
	= 12 (실행 계획 인덱스 라인) + 81 = 93

8i와 9i 실행계획의 변경

8i는 카디널리티 구할 때 소수점 이하를 항상 정수 값으로 올려 버리지만(ceiling) 9i와 10g 는 가장 가까운 점수 갓으로 올리거나 내린다(round함수 사용)

범위기반 검색 조건에 대한 추가사항


alter session set "_optimizer_skip_scan_enabled"=false;
select
	/*+ index(t1) */
	small_vc
from
	t1
where
	n1	between 1 and 3
and	ind_pad	= rpad('x',40)
and	n2	= 2
;
-------------------------------------------------------------------------------------
| Id  | Operation                   | Name  | Rows  | Bytes | Cost (%CPU)| Time     |
-------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT            |       |    82 |  4756 |   264   (0)| 00:00:04 |
|   1 |  TABLE ACCESS BY INDEX ROWID| T1    |    82 |  4756 |   264   (0)| 00:00:04 |
|*  2 |   INDEX RANGE SCAN          | T1_I1 |    82 |       |   184   (0)| 00:00:03 |
-------------------------------------------------------------------------------------

컬럼 n1의 서택도는 (3-1)/(24-0) + 2/25 = 0.1633333
컬럼 ind_pad의 선택도는 여전히 1이다.
컬럼 n2의 선택도는 여전히 0.05이다.

결합 선택도를 구하면 1*0.1633333*0.05 = 0.0081667
비용 = 2 + --blevel
ceiling(0.0081667 * 1111) + ---10
ceiling(0.0081667 * 9745)
= 92 -->잘못된 값. 답은 264 이어야 한다

이 경우에 유효 인덱스 선택도는 n1 컬럼에 대한 조건절로부터만 계산되어야 한다.
N1에 대한 체크조건이 range-based 이기 때문에 index_pad와 n2에 대한 조건은 스캔해야 할 인덱스 리프 블록 수를 줄여주지못한다.
물론, 인덱스 리프 로우를 체크하는 시점에는 세 조건 모두를 사용해서 테이블로 가야 하는지 여부를 판단할 수 있다.
그래서 유효테이블 선택도 만큼은 세 개의 개별 컬럼 조건 모두를 포함한다.

결과 적으로, 유효 인덱스 선택도는 0.1633333 이고 최종 비용 공식은


비용 = 2+ -belevel
       Ceiling(0.1633333 * 11111) + -- 182
       Ceiling(0.0081667 * 9745 )  + -- 80
= 184 + 80 = 264

확장된 실행계획 정보

9i는 explain plan 문에서 사용하는 plan_table에 아주 중요한 두 개의 컬럼을 도입했다.
Filter_predicates와 access_predicates가 그것이고, 이는 where 절을 구성하는 조건절들을 옵티마이저가 어디에 어떻게 사용하려는지에 대한 정확한 정보를 제공한다.
인덱스가 효과적으로 사용되지 않는 경우, 실행계획에서 인덱스 라인은 문제점을 아주 분명하게 부각시켜 줄 것이다.
Acess_predicates 컬럼은 인덱스의 스캔 범위를 결정하는 데 사용되는 조건절 목록을 보여 줄 것이다.
반면 filter_predicates 컬럼은 리프 블록에 도달한 후에 필터 조건으로 상요될 수 있는 조건절 목록(다시 말해, 유효 인덱스 선택도 계산에 사용될 수 없는 컬럼들)을 나열할 것이다.

Index Full Scan시 비용 계산


alter session set "_optimizer_skip_scan_enabled"=false;
select
	/*+ index(t1) */
	small_vc
from
	t1
where	n2	= 2
order by n1
;


---------------------------------------------------------------------
| Id  | Operation                   | Name  | Rows  | Bytes | Cost  |
---------------------------------------------------------------------
|   0 | SELECT STATEMENT            |       |   500 |  8500 |  1601 |
|   1 |  TABLE ACCESS BY INDEX ROWID| T1    |   500 |  8500 |  1601 |
|*  2 |   INDEX FULL SCAN           | T1_I1 |   500 |       |  1113 |
---------------------------------------------------------------------

리프 블록에 도달하기 전까지는 인덱스에 어떤 체크 조건도 없으므로 유효 인덱스 선택도는 1.00(100%)임을 알 수 잇다.
리프 블록을 스캔하는 단계에서는 0.05의 선택도를 가진 단일 조건절 where n2=2를 검사할 수 있고, 따라서 이를 유효 테이블 선택도라고 생각할 수 있다.


Cost =
	2+(1*1111) + (0.05 * 9745) =
        2+1111 + 487.25 =       --round() or ceil() ?
        1113 + 488 = 1601 - ceil 적용

h5.  인덱스만 읽고 처리하는 쿼리
{code:sql}
select
	/*+ index(t1) */
	n2
from
	t1
where	n1	between 6 and 9
order by n1
;


----------------------------------------------------------
| Id  | Operation        | Name  | Rows  | Bytes | Cost  |
----------------------------------------------------------
|   0 | SELECT STATEMENT |       |  2050 | 12300 |   230 |
|*  1 |  INDEX RANGE SCAN| T1_I1 |  2050 | 12300 |   230 |
----------------------------------------------------------

범위 조건절 : (9-6)/(24-0) + 2/25 = 3/24 + 2/25 = 0.205
비용 = 2+0.205 * 1111 =
2+227.755 = 230



\\

h5.  끝으로
* 내부적으로 round()와 ceil()을 사용할 때 오라클 버전 사이에 다양성이 존재 한다.
* 기본 공식과 실제 결과가 다르게 나타는 경우가 있다.
** Unique 인덱스 이거나, Unique 또는 Primary Key 제약을 지원하는 Nonunique (인덱스 : uniqueness 체크를 위해 Nonunique인덱스 사용) 인 경우 옵티마이저는 기본 공식을 사용한 후에 거기서 1을 뺀다. 그러나 Unique 또는 Primary Key 제약을 지원하는 Nonunique 인덱스이더라도 제약에 defferable 옵션을 사용할 때는 이런 조정이 일어나지 않는다. 그래서 주의가 필요한데, 만일에 대비하기 위해 모든 제약에 deferrable옵션을 주고 싶은 유혹이 들 수 있고, 이 때문에 실행계획이 변하는 약간의 부작용이 새길 수 있다.
** 인덱스 blevel이 1로 설정(즉, 루트 블록에서 리프  블록으로 직접 연결)된 경우, 모든 인덱스 컬럼이 '=' 조건으로 사용된다면 옵티마이저는 blevel을 사실상 무시한다. 그런데 (테이블에 있는 한 로우가 업데이트되는 순간 갑자기) 루트 블록 분할(split)dl 발생해서 인덱스 비용이 2만큼 증가하면 액세스 경로가 바뀔수 있기 때문에 관심을 갖고 살펴 볼만한 사례이다

\\

{info:title=작은 테이블에 생성한 인덱스}
작은 테이블에 생성한 인덱스와 통계 정보를 다루는 전략은 매우 중요한 문제이다. 일부 작은 인덱스들은 주기적인 재성성이 필요한 것처럼 보이게 할 수 있기 때문이다. Blevel이 1에서 2로 전환되기 직전 상태에 놓인 인덱스에 통계 정보를 계속해서 수집하다 보면 하나의 추가적인 로우 삽입으로 인해 어느 순간 blevel이 1에서 2로 바뀔수 있다. 데이터 사이즈 또는 인덱스 블록 수에는 그다지 큰 변화가 없지만 비용 계산 결과가 갑자기 높아지는 원인이 된다.
이런 비정상적인 상태에 놓인 인덱스들이 있을 때 선택할 수 있는 첫 번째 옵션은, 통게 정보 수집을 멈추는 것이다. 두 번째, 통계 정보를 수집한 후에 수작업으로 blevel을 설정해 주는 것이다. 세번째는, 통계 정보를 수집하기 전에 매번 인덱스를 재생성하는 것이다.
{info}

\\

* B-tree 인덱스를 사용할 때 비용은 다음 세 가지 구성요소로 이루어 진다.
** 인덱스 깊이 : blevel에 기초해서 계산
** 스캔해야 할 인덱스 리프 블록수 : leaf_blocks에 기초해서 계산
** 테이블 블록 방문 횟수 : clustering_factor에 기초해서 계산