I. Cardinality Matters

1. The most common reason for poor execution plans with perceived "good" statistics is inaccurate row count estimates.
"좋은" 통계 정보를 가지고도 실행 계획이 비효율적으로 수립되는 가장 흔한 이유는 예측 Row 수가 부정확하기 때문이다.
Oracle Engineer - Andrew Holdsworth

2. If an access plan is not optimal it is because the cardinality estimate for ont or more of the row sources is grossly incorrect
만일 실행 계획이 불량하다면 Row Source(실행 계획의 각 단계)들 중 하나 이상에서 예측 Row 수가 매우 부정확하기 때문이다.
Technical Reviewer - Wolfgang Breitling

II. Cardinality 기본 개념

1. Cardinality of a set is the number of elements of the set

Cardinality는 특정 집합에 속한 원소(element)의 수를 의미한다.

2. Oracle에서는 Cardinality 의미를 다음의 4가지로 사용

Base Cardinality
- Base Cardinality란 특정 Table의 전체 Row 수를 의미한다.
- dba_tables.num_rows 값이라고 볼 수 있다.
Calculated Cardinality
- Calculated Cardinality란 Predicate, 즉 조건 절에 의해 Filtering된 Row수를 의미한다.
  가령 Table t1의 전체 Row수가 1000건이고 t1.c1 > 100 조건을 만족하는 Row 수가 100건이라고 가정한다면
  이 경우 Base Cardinality(t1) = 1000이 되고, Calculated Cardinality(t1.c1 > 100) = 100이 된다.
Estimated Cardinality
- Base Cardinality 또는 Calculated Cardinality 모두 Oracle이 실행계획을 세우는 단계에서 사용하는
  모든 Cardinality는 예측치이며 이것을 Estimated Cardinality라고 부른다.
Actual Cardinality
- Query를 수행한 후 계산된 실제 Row 수를 의미함.
- Estimated Cardinality가 실행계획을 수립하는 단계에서 계산되는 반면 Actual Cardinality는 실제 수행한 후에만 알 수 있다.
- Estimated Cardinality 값과 Actual Cardinality 값이 큰 차이를 보인다면 Oracle의 예측이 부정확했다는 것을 의미

3. 이 책에서는 Calculated Cardinality + Estimated Cardinality

III. Basic Rules

1. 기본개념

구분	설명
Distinct Count	Number of Distinct Values
Density	컬럼값의 밀도(1 / NDV)
Skewness	Data가 특정 값에 몰려있을 경우 Dkewness가 높다고 함 Historgram이 존재하는 경우 Skewness를 반영하기 위해 별도의 Density를 계산
Selectivity	특정 조건의 선택도를 의미 Density는 특정 컬럼(하나)의 고정된 값인 반면 Selectivity는 동적 컬럼의 값

2. 테스트 데이터 생성


-- create objects
DROP TABLE T1 PURGE;

CREATE TABLE T1(C1 INT, C2 INT, C3 DATE, C4 VARCHAR2(14));

-- GENERATE DATA AND GATHER STATISTICS
INSERT INTO T1
SELECT LEVEL, -- HIGHLY SELECTIVE
       MOD(ABS(DBMS_RANDOM.RANDOM), 10), -- HIGHLY UNSELECTIVE
       TO_DATE('20080301', 'YYYYMMDD') - MOD(LEVEL, 100),
       TO_CHAR(TO_DATE('20080301', 'YYYYMMDD') - MOD(LEVEL, 100), 'YYYYMMDD')
FROM   DUAL
CONNECT BY LEVEL <= 10000
;

-- gather stats "without" histogram
EXEC DBMS_STATS.GATHER_TABLE_STATS(USER, 'T1', METHOD_OPT=>'FOR ALL COLUMNS SIZE 1');

-- function
CREATE OR REPLACE FUNCTION F1(p_num IN NUMBER) RETURN NUMBER IS
    v_num NUMBER;
BEGIN
    SELECT p_num + 1
    INTO   v_num
    FROM   DUAL;
RETURN v_num;
END;

3. 통계정보 확인


-- Table
SELECT TABLE_NAME,
       NUM_ROWS,
       BLOCKS,
       SAMPLE_SIZE,
       TO_CHAR(LAST_ANALYZED, 'YYYY/MM/DD HH24:MI:SS') AS LAST_ANAL
FROM   USER_TAB_STATISTICS
WHERE  TABLE_NAME = UPPER('T1')
;

TABLE_NAME	NUM_ROWS	BLOCKS	SAMPLE_SIZE	LAST_ANAL
T1	10000	43	10000	2009-02-23 7:28:37 PM


-- Column
SELECT S.TABLE_NAME,
       S.COLUMN_NAME,
       S.NUM_DISTINCT,
       S.NUM_NULLS,
       S.DENSITY,
       S.LOW_VALUE,
       S.HIGH_VALUE,
       S.HISTOGRAM
FROM   USER_TAB_COLS S
WHERE  S.TABLE_NAME = UPPER('T1')
;

TABLE_NAME	COLUMN_NAME	NUM_DISTINCT	DENSITY	LOW_VALUE	HIGH_VALUE	HISTOGRAM
T1	C4	100	0.01	3230303731313230	3230303830333030	NONE
T1	C3	100	0.01	786B0B17010101	786C0301010101	NONE
T1	C2	10	0.1	80	C10A	NONE
T1	C1	10000	0.0001	C102	C302	NONE


-- Histogram
SELECT TABLE_NAME,
       COLUMN_NAME,
       ENDPOINT_NUMBER,
       ENDPOINT_VALUE || '(' || ENDPOINT_ACTUAL_VALUE || ')' AS ENDPOINT_VALUE
FROM   USER_TAB_HISTOGRAMS
WHERE  TABLE_NAME = UPPER('T1')
ORDER  BY COLUMN_NAME,
          ENDPOINT_NUMBER
;

TABLE_NAME	COLUMN_NAME	ENDPOINT_NUMBER	ENDPOINT_VALUE
T1	C1	0	1()
T1	C1	1	10000()
T1	C2	0	1()
T1	C2	1	9()
T1	C3	0	2454428()
T1	C3	1	2454527()
T1	C4	0	260592218620663000000000000000000000()
T1	C4	1	260592218928948000000000000000000000()

4. 테스트

1) Literal Value 테스트

① Cardinality
= Base Cardinality * Selectivity = 10000 * 0.0001 = 1


EXPLAIN PLAN FOR
SELECT  *
FROM    T1
WHERE   C1 = 1
;

select * from table(dbms_xplan.display);

--------------------------------------------------------------------------
| Id  | Operation         | Name | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |      |     1 |    23 |    13   (0)| 00:00:01 |
|*  1 |  TABLE ACCESS FULL| T1   |     1 |    23 |    13   (0)| 00:00:01 |
--------------------------------------------------------------------------

② Cardinality
= Base Cardinality * Selectivity = 10000 * 0.01 = 1000


EXPLAIN PLAN FOR
SELECT  *
FROM    T1
WHERE   C2 = 1
;

select * from table(dbms_xplan.display);

--------------------------------------------------------------------------
| Id  | Operation         | Name | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |      |  1000 | 23000 |    13   (0)| 00:00:01 |
|*  1 |  TABLE ACCESS FULL| T1   |  1000 | 23000 |    13   (0)| 00:00:01 |
--------------------------------------------------------------------------

2) Bind Value 테스트

① Equal Cardinality
= Base Cardinality * Selectivity = 10000 * 0.0001 = 1


EXPLAIN PLAN FOR
SELECT  *
FROM    T1
WHERE   C1 = :B1
;

select * from table(dbms_xplan.display);

--------------------------------------------------------------------------
| Id  | Operation         | Name | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |      |     1 |    23 |    13   (0)| 00:00:01 |
|*  1 |  TABLE ACCESS FULL| T1   |     1 |    23 |    13   (0)| 00:00:01 |
--------------------------------------------------------------------------

3) Between 테스트

① Between Predicate Cardinality
= Base Cardinality * (Selectivity(C1 BETWEEN X AND Y))
= Base Cardinality * (Selectivity(C1 = X) + Selectivity(C1 = Y) + Selectivity(X < C1 < Y))
= Base Cardinality * (Selectivity(C1 = X) + Selectivity(C1 = Y) + (Y - X)/(MAX - MIN))
= Base Cardinality * (Selectivity(C1 = 1) + Selectivity(C1 = 100) + (100 - 1)/(10000 - 1))
= 10000 * (0.0001 + 0.0001 + (99)/(9999))
= 10000 * (0.0001 + 0.0001 + 0.00990099)
= 10000 * 0.01000099
= 100


EXPLAIN PLAN FOR
SELECT  *
FROM    T1
WHERE   C1 BETWEEN 1
           AND     100
;

select * from table(dbms_xplan.display);

--------------------------------------------------------------------------
| Id  | Operation         | Name | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |      |   100 |  2300 |    13   (0)| 00:00:01 |
|*  1 |  TABLE ACCESS FULL| T1   |   100 |  2300 |    13   (0)| 00:00:01 |
--------------------------------------------------------------------------

4) 2개 이상의 Predicate

① 2개 이상의 Predicate Cardinality
= Base Cardinality * (Selectivity(C1 BETWEEN X AND Y)) * (SELECTIVITY(C2 = 1))
= 10000 * 0.01 * 0.1
= 0.001


EXPLAIN PLAN FOR
SELECT  *
FROM    T1
WHERE   C1 BETWEEN 1
           AND     100
AND     C2 = 1
;

select * from table(dbms_xplan.display);

--------------------------------------------------------------------------
| Id  | Operation         | Name | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |      |    10 |   230 |    13   (0)| 00:00:01 |
|*  1 |  TABLE ACCESS FULL| T1   |    10 |   230 |    13   (0)| 00:00:01 |
--------------------------------------------------------------------------

5) OR로 연결된 Predicate

① OR로 연결된 Predicate Cardinality
= Base Cardinality * (Selectivity(P1 OR P2))
= Base Cardinality * (Selectivity(P1) + Selectivity(P2) - Selectivity(P1 AND P2))
= Base Cardinality * (Selectivity(P1) + Selectivity(P2) - (Selectivity(P1) * Selectivity(P2)))
= 10000 * (0.01 + 0.1 - (0.01 * 0.1))
= 10000 * (0.109) = 1090


EXPLAIN PLAN FOR
SELECT  *
FROM    T1
WHERE   C1 BETWEEN 1
           AND     100
OR      C2 = 1
;

select * from table(dbms_xplan.display);

--------------------------------------------------------------------------
| Id  | Operation         | Name | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |      |  1090 | 25070 |    13   (0)| 00:00:01 |
|*  1 |  TABLE ACCESS FULL| T1   |  1090 | 25070 |    13   (0)| 00:00:01 |
--------------------------------------------------------------------------

6) Date Type

① Date Equal Cardinality
= Base Cardinality * Selectivity
= 10000 * 0.01
= 100


EXPLAIN PLAN FOR
SELECT  *
FROM    T1
WHERE   C3 = TO_DATE('20080201', 'YYYYMMDD')
;

select * from table(dbms_xplan.display);

--------------------------------------------------------------------------
| Id  | Operation         | Name | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |      |   100 |  2300 |    13   (0)| 00:00:01 |
|*  1 |  TABLE ACCESS FULL| T1   |   100 |  2300 |    13   (0)| 00:00:01 |
--------------------------------------------------------------------------

② varchar2 Equal Cardinality
= Base Cardinality * Selectivity
= 10000 * 0.01
= 100


EXPLAIN PLAN FOR
SELECT  *
FROM    T1
WHERE   C3 = '20080201'
;

select * from table(dbms_xplan.display);

--------------------------------------------------------------------------
| Id  | Operation         | Name | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |      |   100 |  2300 |    14   (8)| 00:00:01 |
|*  1 |  TABLE ACCESS FULL| T1   |   100 |  2300 |    14   (8)| 00:00:01 |
--------------------------------------------------------------------------

③ Date Between Cardinality
= Base Cardinality * (Selectivity(C3 BETWEEN P1 AND P2))
= Base Cardinality * (Selectivity(P1) + Selectivity(P2) + Selectivity(P1 < C1 < P2))
= Base Cardinality * (Selectivity(P1) + Selectivity(P2) + (P2 - P1)/(MAX - MIN))
= 10000 * (0.01 + 0.01 + (2008/01/10 - 2007/12/31) / (2008/03/01 - 2007/11/23))
= 10000 * (0.01 + 0.01 + (10)/(99))
= 10000 * 0.121010101
= 1210


EXPLAIN PLAN FOR
SELECT  *
FROM    T1
WHERE   C3 BETWEEN TO_DATE('20071231', 'YYYYMMDD')
           AND     TO_DATE('20080110', 'YYYYMMDD')
;

select * from table(dbms_xplan.display);

--------------------------------------------------------------------------
| Id  | Operation         | Name | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |      |  1210 | 27830 |    13   (0)| 00:00:01 |
|*  1 |  TABLE ACCESS FULL| T1   |  1210 | 27830 |    13   (0)| 00:00:01 |
--------------------------------------------------------------------------

④ varchar2 Between Cardinality
= Base Cardinality * (Selectivity(C4 BETWEEN P1 AND P2))
= Base Cardinality * (Selectivity(P1) + Selectivity(P2) + Selectivity(P1 < C4 < P2))
= Base Cardinality * (Selectivity(P1) + Selectivity(P2) + (P2 - P1)/(MAX - MIN))
= 10000 * (0.01 + 0.01 + (20080110 - 20071231) / (20080301 - 20071123))
= 10000 * (0.01 + 0.01 + (8879) / (9178))
= 10000 * 0.987422096
= 9874


EXPLAIN PLAN FOR
SELECT  *
FROM    T1
WHERE   C4 BETWEEN '20071231'
           AND     '20080110'
;

select * from table(dbms_xplan.display);

--------------------------------------------------------------------------
| Id  | Operation         | Name | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |      |  9874 |   221K|    13   (0)| 00:00:01 |
|*  1 |  TABLE ACCESS FULL| T1   |  9874 |   221K|    13   (0)| 00:00:01 |
--------------------------------------------------------------------------

5. 공식 정리

구분	공식
Equals	= Base Cardinality * Selectivity
Between	= Base Cardinality * (Selectivity(C1 BETWEEN P1 AND P2)) = Base Cardinality * (Selectivity(P1) + Selectivity(P2) + Selectivity(P1 < C1 < P2)) = Base Cardinality * (Selectivity(P1) + Selectivity(P2) + (P2 - P1)/(MAX - MIN))
2개 이상 AND	= Base Cardinality * Selectivity(P1) * Selectivity(P2)
2개 이상 OR	= Base Cardinality * (Selectivity(P1 OR P2)) = Base Cardinality * (Selectivity(P1) + Selectivity(P2) - Selectivity(P1 AND P2)) = Base Cardinality * (Selectivity(P1) + Selectivity(P2) - (Selectivity(P1) * Selectivity(P2)))

IV. Magic Number

1. Magic Number란?

'Magic Number'란 {*}{+}오라클이 조건값을 측정할 수 없을 경우 임의의 값을 사용하는것을 의미{+}{*}

Bind & Range = 5%
Function = 1%
Function & Range = 5%

2. 테스트

① Bind & (> OR <)
= Base Cardinality * 0.05
= 10000 * 0.05
= 500


EXPLAIN PLAN FOR
SELECT  *
FROM    T1
WHERE   C1 > :B1
;

select * from table(dbms_xplan.display);

--------------------------------------------------------------------------
| Id  | Operation         | Name | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |      |   500 | 11500 |    13   (0)| 00:00:01 |
|*  1 |  TABLE ACCESS FULL| T1   |   500 | 11500 |    13   (0)| 00:00:01 |
--------------------------------------------------------------------------

② Bind & Between
= Base Cardinality * (C1 >= :B1) * (C1 <= B2)
= 10000 * 0.05 * 0.05
= 25


EXPLAIN PLAN FOR
SELECT  *
FROM    T1
WHERE   C1 BETWEEN :B1
           AND     :B2
;

select * from table(dbms_xplan.display);

---------------------------------------------------------------------------
| Id  | Operation          | Name | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |      |    25 |   575 |    13   (0)| 00:00:01 |
|*  1 |  FILTER            |      |       |       |            |          |
|*  2 |   TABLE ACCESS FULL| T1   |    25 |   575 |    13   (0)| 00:00:01 |
---------------------------------------------------------------------------

③ Function
= Base Cardinality * 0.01
= 10000 * 0.01
= 100


EXPLAIN PLAN FOR
SELECT  *
FROM    T1
WHERE   F1(C1) = 1
;

select * from table(dbms_xplan.display);

--------------------------------------------------------------------------
| Id  | Operation         | Name | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |      |   100 |  2300 |    16  (19)| 00:00:01 |
|*  1 |  TABLE ACCESS FULL| T1   |   100 |  2300 |    16  (19)| 00:00:01 |
--------------------------------------------------------------------------

④ Function & Range
= Base Cardinality * 0.05
= 10000 * 0.05
= 500


EXPLAIN PLAN FOR
SELECT  *
FROM    T1
WHERE   F1(C1) > 1
;

select * from table(dbms_xplan.display);

--------------------------------------------------------------------------
| Id  | Operation         | Name | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |      |   500 | 11500 |    16  (19)| 00:00:01 |
|*  1 |  TABLE ACCESS FULL| T1   |   500 | 11500 |    16  (19)| 00:00:01 |
--------------------------------------------------------------------------

⑤ Function & between
= Base Cardinality * (C1 >= :B1) * (C1 <= B2)
= 10000 * 0.05 * 0.05
= 25


EXPLAIN PLAN FOR
SELECT  *
FROM    T1
WHERE   F1(C1) BETWEEN 1
               AND     100
;

select * from table(dbms_xplan.display);

--------------------------------------------------------------------------
| Id  | Operation         | Name | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |      |    25 |   575 |    16  (19)| 00:00:01 |
|*  1 |  TABLE ACCESS FULL| T1   |    25 |   575 |    16  (19)| 00:00:01 |
--------------------------------------------------------------------------

⑥ Function이 바인드 값일경우
= Dencity 적용
= Base Cardinality * Selectivity
= 10000 * 0.0001
= 1


EXPLAIN PLAN FOR
SELECT  *
FROM    T1
WHERE   C1 = F1(C1)
;

select * from table(dbms_xplan.display);

--------------------------------------------------------------------------
| Id  | Operation         | Name | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |      |     1 |    23 |    16  (19)| 00:00:01 |
|*  1 |  TABLE ACCESS FULL| T1   |     1 |    23 |    16  (19)| 00:00:01 |
--------------------------------------------------------------------------

⑦ Like & Literal
= Base Cardinality * Selectivity
= 10000 * 0.01
= 100


EXPLAIN PLAN FOR
SELECT  *
FROM    T1
WHERE   C4 LIKE '20080101'
;

select * from table(dbms_xplan.display);

--------------------------------------------------------------------------
| Id  | Operation         | Name | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |      |   100 |  2300 |    13   (0)| 00:00:01 |
|*  1 |  TABLE ACCESS FULL| T1   |   100 |  2300 |    13   (0)| 00:00:01 |
--------------------------------------------------------------------------

⑧ Like & Bind
= Base Cardinality * 0.05
= 10000 * 0.05
= 500


EXPLAIN PLAN FOR
SELECT  *
FROM    T1
WHERE   C4 LIKE :B1
;

select * from table(dbms_xplan.display);

--------------------------------------------------------------------------
| Id  | Operation         | Name | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |      |   500 | 11500 |    13   (0)| 00:00:01 |
|*  1 |  TABLE ACCESS FULL| T1   |   500 | 11500 |    13   (0)| 00:00:01 |
--------------------------------------------------------------------------

⑨ Like & Bind & OPT_PARAM 힌트
= Base Cardinality * Selectivity
= 10000 * 0.01
= 100

{*}OPT_PARAM('_LIKE_WITH_BIND_AS_EQUALITY', 'TRUE') 힌트{*}

Bind 변수에 대한 Like 조건은 '=' 조건과 동일하게 처리


EXPLAIN PLAN FOR
SELECT  /*+ OPT_PARAM('_LIKE_WITH_BIND_AS_EQUALITY', 'TRUE') */
        *
FROM    T1
WHERE   C4 LIKE :B1
;

select * from table(dbms_xplan.display);

--------------------------------------------------------------------------
| Id  | Operation         | Name | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |      |   101 |  2323 |    13   (0)| 00:00:01 |
|*  1 |  TABLE ACCESS FULL| T1   |   101 |  2323 |    13   (0)| 00:00:01 |
--------------------------------------------------------------------------

⑩ Like & Bind & '%'
= Base Cardinality * 0.05
= 10000 * 0.05
= 500


EXPLAIN PLAN FOR
SELECT  *
FROM    T1
WHERE   C4 LIKE '%2008'
;

select * from table(dbms_xplan.display);

--------------------------------------------------------------------------
| Id  | Operation         | Name | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |      |   500 | 11500 |    13   (0)| 00:00:01 |
|*  1 |  TABLE ACCESS FULL| T1   |   500 | 11500 |    13   (0)| 00:00:01 |
--------------------------------------------------------------------------

문서에 대하여

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

Cardinality 기본 개념 (by jongmali) [2009.04.30]

목차