Height-Balanced Histogram

Bucket 에 하나 이상의 값이 보관될 수 있어 정확한 빈도를 알 수는 없지만 분포가 잘 계산 된 경우에는 어느 정도 합리적인 계산이 가능하다.

Value Type	Cardinality 계산법
Popular Value	Base Cardinality * (bucket count / bucket size)
Non Popular Value	Base Cardinality * Density
Bind 변수 - Predicate	Base Cardinality * Density - Non Popular 와 동일
Bind 변수 - Range Predicate	5% rule
존재하지 않는 값	최대/최소값을 기준으로 선형적으로 감소하는 방식으로 계산

최대/최소 값을 기준으로 선형적으로 감소하는 방식

C2 컬럼을 예로 들었을 때
- 최대-최소구간 : (1~300)
- 위 구간의 Frequency : total Row Count * Density = 11111 * 0.00036 = 4 (책에서는 4515)
- {-300~0}, {301~600} 구간의 Frequency 는 선형적으로 감소한다고 가정
- 이런 경우 감소 크기는 Frequency / 300 = 4 / 300 = 0.0133
- 305 의 경우 최대값 300을 초과한 5 * 0.0133 만큼 감소
- (-300~0) (301~600) 구간을 벗어나는 값은 동일하게 Cardinality 1로 사용.
  => 책과 다른 Density 가 나와서 감소 수치가 현저히 작게 나타남....

Height-Balanced Histogram이 생성되면 Density가 1/NDV와는 전혀다른 값을 지닐수 있다. 그러므로 *예상치 못한 실행계획의 변화가 생길수 있다.

예제



TABLE_NAME                    : T1
COLUMN_NAME                   : C2
NUM_DISTINCT                  : 300
NUM_NULLS                     : 0
DENSITY                       : .00036320911154317
LOW_VALUE                     : C102
HIGH_VALUE                    : C204
HISTOGRAM                     : HEIGHT BALANCED

컬럼 C2에 대한 Histogram 정보 - Hight balanced Histogram

{code:SQL}
C2 CNT

--

--
1 5008
2 5008
3 8
4 8
5 8
6 6
7 6
8 6
9 6
10 6
.
.
.
{code}

{code:SQL}
TABLE_NAME COLUMN_NAME ENDPOINT_NUMBER ENDPOINT_VALUE

---

T1 C2 113 1()
T1 C2 228 2()
T1 C2 229 3()
T1 C2 230 10()
T1 C2 231 17()
T1 C2 232 24()
T1 C2 233 32()
T1 C2 234 39()
T1 C2 235 46()
T1 C2 236 55()
T1 C2 237 66()
T1 C2 238 77()
T1 C2 239 88()
T1 C2 240 98()
T1 C2 241 112()
T1 C2 242 126()
T1 C2 243 141()
T1 C2 244 155()
T1 C2 245 170()
T1 C2 246 184()
T1 C2 247 199()
T1 C2 248 213()
T1 C2 249 228()
T1 C2 250 242()
T1 C2 251 257()
T1 C2 252 271()
T1 C2 253 286()
T1 C2 254 300()
{code}

Literal-Popular Value(c2=1)


SQL> explain plan for
  2  select * from t1
  3  where c2 = 1;

해석되었습니다.

SQL> @plan

PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
Plan hash value: 3617692013

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

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

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

   1 - filter("C2"=1)

- Cardinality : 4943 (Base Cardinality * (bucket Count / bucket Size) = 11111*113/254 = 4943)

Literal-Non Popular Value(c2=10)


SQL> explain plan for
  2  select * from t1
  3  where c2 = 10;

해석되었습니다.

SQL> @plan

PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
Plan hash value: 3617692013

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

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

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

   1 - filter("C2"=10)

- Cardinality : 4 ( Base Cardinality * Density = 11111*0.00036 = 4 )

Bind 변수(c2=:b1)


SQL> explain plan for
  2  select * from t1
  3  where c2 = :b1;

해석되었습니다.

SQL> @plan

PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
Plan hash value: 3617692013

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

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

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

   1 - filter("C2"=TO_NUMBER(:B1))

- Cardinality : 37 (책과 다름.. 책에선 Bind 변수도 Non Popular Value의 Rule 과 동일한 공식, but..)

Bind 변수-Range Predicate (c2>:b1)


SQL> explain plan for
  2  select * from t1
  3  where c2 > :b1;

해석되었습니다.

SQL> @plan

PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
Plan hash value: 3617692013

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

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

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

   1 - filter("C2">TO_NUMBER(:B1))

- Cardinality : 556 ( 5% Rule = 11111*0.05=556)

Bind 변수-Between Predicate (c2 between :b1 and :b2)


SQL> explain plan for
  2  select * from t1
  3  where c2 between :b1 and :b2;

해석되었습니다.

SQL> @plan

PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
Plan hash value: 3332582666

---------------------------------------------------------------------------
| Id  | Operation          | Name | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |      |    28 |   168 |     7  (15)| 00:00:01 |
|*  1 |  FILTER            |      |       |       |            |          |
|*  2 |   TABLE ACCESS FULL| T1   |    28 |   168 |     7  (15)| 00:00:01 |
---------------------------------------------------------------------------

Predicate Information (identified by operation id):

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

   1 - filter(TO_NUMBER(:B1)<=TO_NUMBER(:B2))
   2 - filter("C2">=TO_NUMBER(:B1) AND "C2"<=TO_NUMBER(:B2))

- Cardinality : 28 ( 5% Rule = 11111*0.05*0.05=28)

존재하지 않는 값(c2=400)


SQL> explain plan for
  2  select * from t1
  3  where c2 = 400;

해석되었습니다.

SQL> @plan

PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
Plan hash value: 3617692013

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

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

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

   1 - filter("C2"=400)

- Cardinality : 3 ( 존재하지 않는 값에 대하여 최대/최소 값을 기준으로 선형적으로 감소하는 방식으로 계산)

Height-Balanced Histogram (by jkno) [2011.05.19]

Height-Balanced Histogram

최대/최소 값을 기준으로 선형적으로 감소하는 방식

예제