Frequency vs. Height-Balanced

• 오라클의 값 저장 개수 254개 한계로 인해 Distinct Count만큼 Bucket수가 존재하지 않는 경우가 존재하기 때문에 Frequency Histogram, Height-Balanced Histogram 두 종류의 Histogram이 존재하게 됨.

Frequency Histogram

• 빈도 Histogram
• 값(Value)의 Distinct Count와 Bucket 수가 일치하는 경우
• 1개의 Bucket 이 하나의 값을 가지게 된다. 즉 값에 해당하는 빈도를 정확하게 저장하고 있게 된다.

ex) A =100건, B =200건, C =100건 => distinct count = 3
     이때 만약  Bucket count = 3 이면   Histogram에는 \{(A, 100), (B, 200), (C, 100)} 으로 저장

Height-Balanced Histogram

• 균일 높이 Histogram
• 값(Value)의 Distinct Count가 Bucket 수보다 많은 경우 값마다 Bucket을 하나씩 할당 할 수 없으므로 값들을 적당한 Bucket으로 분배
• Bucket의 높이 : 전체 개수/Bucket 개수

Height-Balanced Histogram 이 생성되는 경우

• Distinct Count 가 254개 초과인 경우
• DBMS_STATS Package 의 METHOD_OPT Parameter 를 통해 Distinct Count 보다 적은 Bucket size 를 할당한 경우
• (ex) exec dbms_stats.gather_table_stats(user, 't1', method_opt=>'for columns c1 size 5')

예제

drop table t1 purge;
create table t1(c1 int, c2 int);

insert into t1
select 1, mod(level, 2) +1
from dual
connect by level <= 10000
union all
select 2, mod(level, 300) + 1
from dual
connect by level <= 1000
union all
select 3, mod(level, 50) + 1
from dual
connect by level <= 100
union all
select 4, mod(level, 5) + 1
from dual
connect by level <= 10
union all
select 5, mod(level, 1) + 1
from dual
connect by level <= 1
;

commit;

exec dbms_stats.gather_table_stats(user, 't1', method_opt=>'for all columns size skewonly')

TABLE_NAME                    : T1
COLUMN_NAME                   : C1
NUM_DISTINCT                  : 5
NUM_NULLS                     : 0
DENSITY                       : .0000450004500045
LOW_VALUE                     : C102
HIGH_VALUE                    : C106
HISTOGRAM                     : FREQUENCY
-----------------
TABLE_NAME                    : T1
COLUMN_NAME                   : C2
NUM_DISTINCT                  : 300
NUM_NULLS                     : 0
DENSITY                       : .00036320911154317
LOW_VALUE                     : C102
HIGH_VALUE                    : C204
HISTOGRAM                     : HEIGHT BALANCED
-----------------

컬럼 C1에 대한 Histogram 정보 - Frequency Histogram

        C1        CNT
---------- ----------
         1      10000
         2       1000
         3        100
         4         10
         5          1

TABLE_NAME           COLUMN_NAME          ENDPOINT_NUMBER ENDPOINT_VALUE
-------------------- -------------------- --------------- --------------------
T1                   C1                             10000 1()
T1                   C1                             11000 2()
T1                   C1                             11100 3()
T1                   C1                             11110 4()
T1                   C1                             11111 5()

Frequency Histogram 정보 보는 방법

• 자신의 빈도는 자신의 END_POINT_NUMBER 에서 앞선 값의 END_POINT_NUMBER 를 뺀 값

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

        C2        CNT
---------- ----------
         1       5008
         2       5008
         3          8
         4          8
         5          8
         6          6
         7          6
         8          6
         9          6
        10          6
	.
	.
	.

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()

Height Balanced Histogram 정보 보는 방법

• Height Balanced Histogram 에서 하나의 Bucket의 높이는 일정함
  • 전체 Rowcount / Bucket Count = 1 Bucket 의 높이
  • 각 값(Value)의 빈도에 따라 Bucket을 차지

• 하나의 값이 하나 혹은 그 이상의 Bucket 을 차지하는 경우 -> Popular Value
• 여러 값이 하나의 Bucket에 들어있는 경우 -> Non Popular Value

• 값 1 의 예 - Popular Value

• 즉 값 1은 1번에서 113번 Bucket 을 혼자서 사용한다는 뜻
• 이를 이용해 빈도를 계산하면

   Popular Value Frequency = Height * Bucket size
                           = (Total Row Count / Total Bucket size) * Bucket size
                           = (11111/254) * 113 = 4943

• 값 10 의 예 - Non Popular Value

• 이 때 이전 ENDPOINT_VALUE = 3,
• 즉 4 ~ 10 번 값 6개가 230번 bucket 하나를 공유하고 있음

• Popular Value 와 Non Popular Value는 Cardinality의 계산 방식에서 완전히 다른 공식을 사용