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

{panel:bgColor=#FFFFCE} Q: 전체 Row 수의 5% 정도 이하일 경우에는 Index Lookup 이 유리하고, 그 이상이라면 Table Full Scan 이 유리한가요? A: 질문이 잘못 되었다. {panel}
"일반적으로 10~15% 정도를 인덱스와 전체 테이블 엑세스의 손익분기점으로 볼 수 있다." (대용량 데이터베이스 솔루션 I, 33 페이지) http://wiki.gurubee.net/pages/viewpage.action?pageId=688165
{tip:icon=true}Index Scan 과 Table Full Scan 중 유리한 쪽을 결정하는 Magic Number 는 없다, CBO 는 각각의 Cost 를 기계적으로 계산해서 Cost 가 더 낮은 Operation 을 선택한다.{tip}

Table Full Scan Cost

가정

Blocks	100
MBRC	4	db_file_multiblock_read_count
sreadtim	5	Single Block I/O 의 평균 수행 시간(ms)
mreadtim	10	Multi Block I/O 의 평균 수행 시간(ms)

Cost =

Single Block I/O Count +	0
Adjusted Multi Block I/O Count +	Multi Block I/O Count * 가중치 = (Blocks / MBRC) * (mreadtim / sreadtim) = ( 100 / 4 ) * ( 10 / 5 ) = 50
Adjusted CPU Count	<Small Value> (0.xxxx)

결론
- 이 케이스의 Cost 는 약 50 보다 조금 큰 값이 된다. (50.xxxx)
- MBRC(db_file_multiblock_read_count) 같은 요소 들을 제어 함으로서 Cost 를 제어할 수 있다.

Index Scan Cost

Index 를 통해 Row 를 읽는 과정
1. 조건을 만족하는 최초의 Index Leap Block 까지 찾아간다
2. 조건을 만족하는 Index Key 를 순서대로 Fetch 하면서 (access)
3. ROWID 를 이용해 Table Block 을 하나씩 읽으면서
4. 조건에 해당하는 Row 를 Fetch 한다. (filter)

Cost =

	Blevel	2	Root Block 에서 Leaf Block 까지 찾아가는 Cost
+	Leaf Blocks * Index Selectivity	4 * 1 / 4	조건에 맞는 Index Leaf Block 을 읽는 Cost
+	Clustering Factor * Table Selectivity	8 * 1 / 5	조건에 맞는 Table Block 을 읽는 Cost
+	Adjusted CPU Count	<Small Value> (0.xxxx)

결론
- 이 케이스의 Cost 는 약 5 보다 조금 큰 값이 된다. (5.xxxx)
- 위와 같은 요소를 통해서 Index Scan 의 Cost 가 결정 된다
- Index Scan 과 관련된 모든 I/O 는 Single Block I/O 이므로 I/O Count = I/O Cost 임
- Blevel = Index height - 1 (Leaf Block 은 별도 계산)

Index Selectivity 와 Table Selectivity 의 차이점

가정


create table t1 (c1 int, c2 int, c3 int, c4 int);

create index t1_n1 on t1(c1, c2, c3);
...

-- Selectivity 는 다음과 같다고 가정한다.
-- Selectivity (c1 = 1) = 0.1
-- Selectivity (c3 = 2) = 0.2

select * from t1 where c1 = 1 and c3 = 2;

비교

Index Selectivity	Selectivity(c1 = 1)	0.1	c1 = 1 and c3 = 2 조건은 c1 = 1 조건과 동일
Table Selectivity	Selectivity(c1 = 1) * Selectivity(c3 = 2)	0.02 (0.1 * 0.2)	c3 =2 조건은 Index 의 Filtering 조건으로는 사용될수 없지만, Table 로 나머지 Column 을 읽으러 가야 할지의 여부를 결정하는 Filtering 조건으로는 사용됨

참고
- Index Selectivity 와 Table Selectivity 가 다른 경우는 다중 Column 으로 이루어진 Index 에 대해서 Key 값의 일부만이 조건으로 사용된 경우이다.

Dirty Estimation

가정

Total Rows	100,000
Total Blocks	10,000
MBRC	10
Index Height	3 (Blevel = 2)
Leaf Blocks	100
Clustering Factor	50,000
Index Selectivity	Table Selectivity

위의 가정에서 Index Scan 의 Cost 와 Table Scan 의 Cost 가 같아지는 Magic Number 찾기

Index Lookup Cost	Table Scan Cost
Blevel + (Leaf Blocks * Selectivity) + (Clustering Factor * Selectivity)	Table Blocks / MBRC
2 + (100 * S) + (50000 * S)	10000 / 10
(50000 + 100) * S	10000 / 10 - 2
S	(10000/10 - 2) / (50000 + 100) = 0.019 (2%)

결론
- 위의 가정에서 Selectivity 2% 가 Magic Number(경계값)이 된다.
- 위의 패턴을 적용해 보면, 대부분 0% ~ 10% 사이에서 CBO 의 선택이 결정된다
확대해석
- Index Scan Cost 에서 Clustering Factor 가 차지하는 비중이 매우 높다
- Index 에 대해 넓은 범위의 Leaf Block 을 Scan 하는 경우에는 Cost 가 매우 높다. 즉 Selectivity 가 차지하는 비중이 매우 높다.
- Table Full Scan 의 Cost 는 MBRC(db_file_multiblock_read_count) 값에 크게 의존한다.

Execution Plan (좋은 Clustering Factor)
{code:sql} explain plan for select /+ good clsf / * from t_clsf where c1 between 1 and 100; {code}
{code:sql}	Id	Operation	Name	Rows	Bytes	Cost (%CPU)

0

SELECT STATEMENT

100

700

3 (0)

>> 3

1

TABLE ACCESS BY INDEX ROWID

T_CLSF

100

700

3 (0)

>> 3 - 2 = 1

2

INDEX RANGE SCAN

T_CLSF_I1

100

2 (0)

>> 2

{code}

Execution Plan (나쁜 Clustering Factor)
{code:sql} explain plan for select /+ bad clsf index(t_clsf) / * from t_clsf where c2 between 1 and 100; {code}
{code:sql}	Id	Operation	Name	Rows	Bytes	Cost (%CPU)

0	SELECT STATEMENT	100	700	97 (0)	>> 97	1	TABLE ACCESS BY INDEX ROWID	T_CLSF	100	700	97 (0)	>> 97 - 2 = 95	2	INDEX RANGE SCAN	T_CLSF_I2	100	2 (0)	>> 2 {code}
{info:icon=false}TABLE ACCESS BY INDEX ROWID(Id:1) : Index Key 값을 확인한 후 ROWID 를 이용해 Table 까지 찾아가는 Cost INDEX RANGE SCAN(Id:2) : Index 의 Root Block 에서 Leaf Block 까지 찾아가는 Cost + Index Leaf Block 을 읽는 Cost {info}
{tip:icon=true}이런 차이는 대부분 Clustering Factor 값의 차이에 의해 발생한다.{tip}

Index Scan Cost (by openlsw) [2011.03.22]