Oracleの統計情報（ヒストグラム編）

今回はOracleの統計情報のうち、ヒストグラムについて調査しました。

Oracleの統計情報 - 忘れかけのIT備忘録で少しだけ触れましたが、ヒストグラムは表の列データの分布状況です。
セレクティビティ(行の選択率)のコストを見積もるために使用される統計情報です。
通常の統計情報に比べ、より最適な実行計画を作成/選択するのが目的です。
ヒストグラムには、頻度分布ヒストグラム、高さ調整ヒストグラム、上位頻度ヒストグラム、ハイブリッドヒストグラムがあります。
XXX_TAB_STATISTICSのHISTOGRAMで使用しているヒストグラムを確認できます。
XXX_HISTOGRAMS(XXX_TAB_HISTOGRAMS)でヒストグラムの詳細を確認できます。
※セレクティビティ：行が選択される割合。全表スキャンか索引スキャンかの判断指標になる
※上位頻度ヒストグラム、ハイブリッドヒストグラムは12c以降の機能

ヒストグラムがないと・・・
Oracleはデフォルトでヒストグラムを収集しますが、ヒストグラムが収集されていない場合、オプティマイザはデータが均等に分布されていると推測してしまいます。
実際のテーブルのデータの分布とオプティマイザが把握しているデータの分布に誤差が発生するため、最適な実行計画を作成/選択できません。
たとえば下記の図の場合、「D」のデータへアクセスする際、オプティマイザは「NDV=4」、「データは均等に分布されている」と見積もって全表スキャンの方が効率的と判断してしまう可能性があります。

【検証手順】
1. 検証テーブル作成、検証データ挿入
2. 統計情報取得(ヒストグラム収集なし)
3. ヒストグラムが存在しない状態でレコード取得、実行計画確認
4. 統計情報取得(ヒストグラム収集あり)
5. ヒストグラムが存在する状態でレコード取得、実行計画確認

【作業ログ】

1. 検証テーブル作成、検証データ挿入
SQL> CREATE TABLE TEST_TABLE1
2 (COL1 NUMBER(7) CONSTRAINT PK_TEST_TABLE1 PRIMARY KEY,
3 COL2 VARCHAR2(4));

表が作成されました。

SQL> CREATE INDEX IDX1_TEST_TABLE1 ON TEST_TABLE1(COL2);

索引が作成されました。

SQL> INSERT INTO TEST_TABLE1 SELECT LEVEL, 'A' FROM DUAL CONNECT BY LEVEL <= 1000;

1000行が作成されました。

SQL> INSERT INTO TEST_TABLE1 SELECT LEVEL + 1000, 'B' FROM DUAL CONNECT BY LEVEL <= 1000;

1000行が作成されました。

SQL> INSERT INTO TEST_TABLE1 SELECT LEVEL + 2000, 'C' FROM DUAL CONNECT BY LEVEL <= 1000;

1000行が作成されました。

SQL> INSERT INTO TEST_TABLE1 VALUES(3001, 'D');

1行が作成されました。

SQL> COMMIT;

コミットが完了しました。

SQL> SELECT COL2, COUNT(*) FROM TEST_TABLE1 GROUP BY COL2 ORDER BY 1;

COL2 COUNT(*)
------------ ----------
A 1000
B 1000
C 1000
D 1

2. 統計情報取得(ヒストグラム収集なし)
SQL> BEGIN
2 DBMS_STATS.GATHER_TABLE_STATS(ownname => 'SYS',
3 tabname => 'TEST_TABLE1',
4 method_opt => 'FOR ALL COLUMNS SIZE 1',
5 cascade => FALSE);
6 END;
7 /

PL/SQLプロシージャが正常に完了しました。
★'FOR ALL COLUMNS SIZE 1'はヒストグラムを収集しないように明示的に指定している

SQL> SELECT OWNER, TABLE_NAME, COLUMN_NAME, NUM_DISTINCT, NUM_BUCKETS, LAST_ANALYZED, HISTOGRAM FROM ALL_TAB_COL_STATISTICS WHERE OWNER = 'SYS' AND TABLE_NAME = 'TEST_TABLE1' AND COLUMN_NAME = 'COL2';

3. ヒストグラムが存在しない状態でレコード取得、実行計画確認
SQL> SELECT /* TEST1_1 */ * FROM TEST_TABLE1 WHERE COL2 = 'D';

COL1 COL2
---------- ------------
3001 D

SQL> SELECT * FROM TABLE(DBMS_XPLAN.DISPLAY_CURSOR('3nazjkcxu3x77'));

PLAN_TABLE_OUTPUT
-----------------
SQL_ID 3nazjkcxu3x77, child number 0
-------------------------------------
SELECT /* TEST1_1 */ * FROM TEST_TABLE1 WHERE COL2 = 'D'

Plan hash value: 3636527845

--------------------------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
--------------------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | | | 1 (100)| |
| 1 | TABLE ACCESS BY INDEX ROWID BATCHED| TEST_TABLE1 | 750 | 4500 | 1 (0)| 00:00:01 |
|* 2 | INDEX RANGE SCAN | IDX1_TEST_TABLE1 | 1 | | 1 (0)| 00:00:01 |
--------------------------------------------------------------------------------------------------------

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

2 - access("COL2"='D')
★インデックスを範囲検索して1行ヒットしたがオプティマイザは750行のテーブルアクセス(マルチブロックリードorパラレルリード)が発生すると見積もった

4. 統計情報取得(ヒストグラム収集あり)
SQL> BEGIN
2 DBMS_STATS.GATHER_TABLE_STATS(ownname => 'SYS',
3 tabname => 'TEST_TABLE1',
4 estimate_percent => 100,
5 method_opt => 'FOR COLUMNS COL2 SIZE AUTO',
6 cascade => TRUE);
7 END;
8 /

PL/SQLプロシージャが正常に完了しました。

5. ヒストグラムが存在する状態でレコード取得、実行計画確認
SQL> SELECT /* TEST1_2 */ * FROM TEST_TABLE1 WHERE COL2 = 'D';

COL1 COL2
---------- ------------
3001 D

SQL> SELECT * FROM TABLE(DBMS_XPLAN.DISPLAY_CURSOR('dm1pa05nmvdd7'));

PLAN_TABLE_OUTPUT
-----------------
SQL_ID dm1pa05nmvdd7, child number 0
-------------------------------------
SELECT /* TEST1_2 */ * FROM TEST_TABLE1 WHERE COL2 = 'D'

Plan hash value: 3636527845

--------------------------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
--------------------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | | | 2 (100)| |
| 1 | TABLE ACCESS BY INDEX ROWID BATCHED| TEST_TABLE1 | 1 | 6 | 2 (0)| 00:00:01 |
|* 2 | INDEX RANGE SCAN | IDX1_TEST_TABLE1 | 1 | | 1 (0)| 00:00:01 |
--------------------------------------------------------------------------------------------------------

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

2 - access("COL2"='D')
★インデックスを範囲検索して1行ヒットしてオプティマイザは1行のテーブルアクセスが発生すると見積もった

頻度分布ヒストグラム（Frequency）
列内の個別値がバケット数以下の場合、それぞれの値が何行あるのか正確に把握します(データの分布を列値の累計行数の差分から正確に計算して把握します)
個別値の数が指定されたバケット数以下の場合、頻度分布ヒストグラムを生成します。
「NDV <= バケット数」の場合、頻度分布ヒストグラムが採用されます。
※バケット：分布データ(個別値)の格納領域

メリット
・NDVが少ない中、他の個別値よりも極端に累計行数が少ない個別値を検索する場合、索引アクセスが選択される可能性が高くなる
・個別値の累計行数の差分を算出するため、正確な分布データが得られる(それぞれの個別値が何行あるか正確に把握できる)
デメリット
・NDVに比例してデータ量が多くなるため、ヒストグラム格納用のディクショナリが肥大化しやすい
・最大2048種類の値までしかヒストグラムが作成できない(11gは最大254種類まで)

【検証手順】
前提として下記のようなデータがあるとします
SQL> select * from emp;

EMPNO ENAME JOB MGR HIREDATE SAL COMM DEPTNO
---------- --------------- --------------- ---------- ------------------- ---------- ---------- ----------
7369 SMITH CLERK 7902 1980-12-17 00:00:00 800 10
7499 ALLEN SALESMAN 7698 1981-02-20 00:00:00 1600 300 10
7521 WARD SALESMAN 7698 1981-02-22 00:00:00 1250 500 10
7566 JONES MANAGER 7839 1981-04-02 00:00:00 2975 10
7654 MARTIN SALESMAN 7698 1981-09-28 00:00:00 1250 1400 10
7698 BLAKE MANAGER 7839 1981-05-01 00:00:00 2850 10
7782 CLARK MANAGER 7839 1981-06-09 00:00:00 2450 10
7839 KING PRESIDENT 1981-11-17 00:00:00 5000 10
7844 TURNER SALESMAN 7698 1981-09-08 00:00:00 1500 0 20
7900 JAMES CLERK 7698 1981-12-03 00:00:00 950 20
7902 FORD ANALYST 7566 1981-12-03 00:00:00 3000 30
7934 MILLER CLERK 7782 1982-01-23 00:00:00 1300 40

SQL> select * from dept;

DEPTNO DNAME LOC
---------- --------------- ---------------
10 ACCOUNTING NEW YORK
20 RESEARCH DALLAS
30 SALES CHICAGO
40 OPERATIONS BOSTON

1. 統計情報取得(ヒストグラム収集なし)
2. 統計情報取得(ヒストグラム収集あり)

【作業ログ】

1. 統計情報取得(ヒストグラム収集なし)
SQL> BEGIN
2 DBMS_STATS.GATHER_TABLE_STATS(ownname => 'SCOTT',
3 tabname => 'EMP',
4 method_opt => 'FOR ALL COLUMNS SIZE 1',
5 cascade => FALSE);
6 END;
7 /

PL/SQLプロシージャが正常に完了しました。

SQL> SELECT OWNER, TABLE_NAME, COLUMN_NAME, NUM_DISTINCT, NUM_BUCKETS, LAST_ANALYZED, HISTOGRAM FROM ALL_TAB_COL_STATISTICS WHERE OWNER = 'SCOTT' AND TABLE_NAME = 'EMP' AND COLUMN_NAME = 'DEPTNO';

SQL> SELECT TABLE_NAME, COLUMN_NAME, ENDPOINT_VALUE, ENDPOINT_NUMBER FROM ALL_HISTOGRAMS WHERE OWNER = 'SCOTT' AND TABLE_NAME = 'EMP' AND COLUMN_NAME = 'DEPTNO' ORDER BY ENDPOINT_VALUE;

TABLE_NAME COLUMN_NAME ENDPOINT_VALUE ENDPOINT_NUMBER
--------------- --------------- -------------- ---------------
EMP DEPTNO 10 0
EMP DEPTNO 40 1
★ヒストグラムが存在しない場合、2バケット(列データの最小値・最大値)があるように見える

2. 統計情報取得(ヒストグラム収集あり)
SQL> BEGIN
2 DBMS_STATS.GATHER_TABLE_STATS(ownname => 'SCOTT',
3 tabname => 'EMP',
4 estimate_percent => 100,
5 method_opt => 'FOR COLUMNS DEPTNO SIZE 2048',
6 cascade => TRUE);
7 END;
8 /

PL/SQLプロシージャが正常に完了しました。

SQL> SELECT OWNER, TABLE_NAME, COLUMN_NAME, NUM_DISTINCT, NUM_BUCKETS, LAST_ANALYZED, HISTOGRAM FROM ALL_TAB_COL_STATISTICS WHERE OWNER = 'SCOTT' AND TABLE_NAME = 'EMP' AND COLUMN_NAME = 'DEPTNO';

OWNER TABLE_NAME COLUMN_NAME NUM_DISTINCT NUM_BUCKETS LAST_ANALYZED HISTOGRAM
--------------- --------------- --------------- ------------ ----------- ------------------- --------------------
SCOTT EMP DEPTNO 4 4 2023-02-17 10:05:40 FREQUENCY
★頻度分布ヒストグラムが取得された
★NDV=4に対して'FOR COLUMNS DEPTNO SIZE 2048'を指定してもバケット数(NUM_BUCKETS)は4になった。NDVより大きい値を指定してもバケット数はNDVと同じになるようです

SQL> SELECT TABLE_NAME, COLUMN_NAME, ENDPOINT_VALUE, ENDPOINT_NUMBER FROM ALL_HISTOGRAMS WHERE OWNER = 'SCOTT' AND TABLE_NAME = 'EMP' AND COLUMN_NAME = 'DEPTNO' ORDER BY ENDPOINT_VALUE;

TABLE_NAME COLUMN_NAME ENDPOINT_VALUE ENDPOINT_NUMBER
--------------- --------------- -------------- ---------------
EMP DEPTNO 10 8
EMP DEPTNO 20 10
EMP DEPTNO 30 11
EMP DEPTNO 40 12
※ENDPOINT_VALUE：バケットに格納する分布データ(個別値)
※ENDPOINT_NUMBER：バケットに格納する分布データ(個別値)の累計行数。累計行数と1つ前のエントリの累計行数の差分が列値の行数となる(オフセットみたいなイメージ)

高さ調整ヒストグラム（Height Balanced）
列内の個別値がバケット数より多い場合、指定バケット内にソートしたデータ(個別値)を順番・均等に配置して、それぞれのバケットの最大値を記録し、その値によってデータの偏りを把握します。
複数のバケットのうち、連続したバケットの最大値(ENDPOINT_VALUE)が同じ場合、その値が他の値より多く存在しているということになります。
複数のバケットの最大値を記録し、最も頻出度が高いものをポピュラ値と呼びます。
「NDV > バケット数」の場合、高さ調整ヒストグラムが採用されます。

メリット
・厳密な統計がなくても正しい実行計画が選択できる
・NDVが多い場合でもヒストグラムを使用できる
・ポピュラ値以外の個別値は省略できるため、頻度分布ヒストグラムより領域節約できる可能性がある
デメリット
・ポピュラ値でデータの偏りを見るため、等価条件では偏りを見つけられない(たとえばDEPTNOが全部「10」の場合、ポピュラ値は10となるため、データの偏りを把握できないということだと思います)
・頻度分布ヒストグラムより正確ではない

【検証手順】
1. 統計情報取得(ヒストグラム収集なし)
2. 統計情報取得(ヒストグラム収集あり)

【作業ログ】

PL/SQLプロシージャが正常に完了しました。

SQL> SELECT OWNER, TABLE_NAME, COLUMN_NAME, NUM_DISTINCT, NUM_BUCKETS, LAST_ANALYZED, HISTOGRAM FROM ALL_TAB_COL_STATISTICS WHERE OWNER = 'SCOTT' AND TABLE_NAME = 'EMP' AND COLUMN_NAME = 'DEPTNO';

SQL> SELECT TABLE_NAME, COLUMN_NAME, ENDPOINT_VALUE, ENDPOINT_NUMBER FROM ALL_HISTOGRAMS WHERE OWNER = 'SCOTT' AND TABLE_NAME = 'EMP' AND COLUMN_NAME = 'DEPTNO' ORDER BY ENDPOINT_VALUE;

TABLE_NAME COLUMN_NAME ENDPOINT_VALUE ENDPOINT_NUMBER
--------------- --------------- -------------- ---------------
EMP DEPTNO 10 0
EMP DEPTNO 40 1

PL/SQLプロシージャが正常に完了しました。

SQL> SELECT OWNER, TABLE_NAME, COLUMN_NAME, NUM_DISTINCT, NUM_BUCKETS, LAST_ANALYZED, HISTOGRAM FROM ALL_TAB_COL_STATISTICS WHERE OWNER = 'SCOTT' AND TABLE_NAME = 'EMP' AND COLUMN_NAME = 'DEPTNO';

SQL> SELECT TABLE_NAME, COLUMN_NAME, ENDPOINT_VALUE, ENDPOINT_NUMBER FROM ALL_HISTOGRAMS WHERE OWNER = 'SCOTT' AND TABLE_NAME = 'EMP' AND COLUMN_NAME = 'DEPTNO' ORDER BY ENDPOINT_VALUE;

TABLE_NAME COLUMN_NAME ENDPOINT_VALUE ENDPOINT_NUMBER
--------------- --------------- -------------- ---------------
EMP DEPTNO 10 2
EMP DEPTNO 40 3
※ENDPOINT_VALUE：バケットに格納する分布データ(分布データの最大値)
※ENDPOINT_NUMBER：格納する分布データを格納するバケット番号

上位頻度ヒストグラム(12c～)　※未検証
頻度分布ヒストグラムから派生したヒストグラムで個別値の中で特に割合の多い個別値だけを対象としたヒストグラムです。
上位N個の個別値がデータの大半を占めている場合、上位頻度ヒストグラムが作成されます。
上位N個についてはオプティマイザが正確に行数を見積もることができます。

ハイブリッドヒストグラム(12c～)　※未検証
高さ調整ヒストグラムと頻度分布ヒストグラムを組み合わせたヒストグラムです。
高さ調整ヒストグラムの場合、ほぼポピュラな値について正確ではない見積りが作成される場合があります。
たとえば1つのバケットのエンドポイント値(最大値)として出現しますが、2つのバケットをほぼ占めているエンドポイント値(最大値)はポピュラ値とはみなされません。(ポピュラ値が見つからない)
この問題を解決するため、複数のバケットを占めるエンドポイント値(最大値)がないように個別値が配分され、エンドポイント繰返しカウント値が格納されます。
エンドポイント繰返しカウント値はヒストグラム内の各エンドポイント(バケット)について、エンドポイント値(最大値)が繰り返された回数です。
繰返しカウントを使用することで、オプティマイザはほぼポピュラな値について正確な見積りができます。

下記の手順でヒストグラムを作成します。

1. 高さ調整ヒストグラムのように各バケットに同数ずつ個別値を格納する
2. 頻度分布ヒストグラムのように同じ個別値が複数のバケットに格納されないよう調整する

各バケットの最後の個別値が何行あるのか記録していき、頻出する個別値に対して正確な見積もりができます。

※図を作成しようとしましたがそもそも仕組みがイメージできませんでした。。

オプティマイザの勘違い
【検証手順】
1. 検証テーブル作成、検証データ挿入
2. 統計情報取得(ヒストグラム収集なし)
3. ヒストグラムが存在しない状態でレコード取得、実行計画確認
4. 統計情報取得(ヒストグラム収集あり)
5. ヒストグラムが存在する状態でレコード取得、実行計画確認

【作業ログ】

1. 検証テーブル作成、検証データ挿入
SQL> CREATE TABLE TEST_TABLE1
2 (COL1 NUMBER(7) CONSTRAINT PK_TEST_TABLE1 PRIMARY KEY,
3 COL2 VARCHAR2(4));

表が作成されました。

SQL> CREATE INDEX IDX1_TEST_TABLE1 ON TEST_TABLE1(COL2);

索引が作成されました。

SQL> INSERT INTO TEST_TABLE1 SELECT LEVEL, 'A' FROM DUAL CONNECT BY LEVEL <= 1000;

1000行が作成されました。

SQL> INSERT INTO TEST_TABLE1 SELECT LEVEL + 1000, 'B' FROM DUAL CONNECT BY LEVEL <= 1000;

1000行が作成されました。

SQL> INSERT INTO TEST_TABLE1 SELECT LEVEL + 2000, 'C' FROM DUAL CONNECT BY LEVEL <= 1000;

1000行が作成されました。

SQL> INSERT INTO TEST_TABLE1 VALUES(100000, 'D');

1行が作成されました。

SQL> COMMIT;

コミットが完了しました。

SQL> SELECT COL2, COUNT(*) FROM TEST_TABLE1 GROUP BY COL2 ORDER BY 1;

COL2 COUNT(*)
------------ ----------
A 1000
B 1000
C 1000
D 1

PL/SQLプロシージャが正常に完了しました。

3. ヒストグラムが存在しない状態でレコード取得、実行計画確認
SQL> SELECT /* TEST2_1 */ * FROM TEST_TABLE2 WHERE COL1 >= 50000;

COL1 COL2
---------- ------------
100000 D

SQL> SELECT * FROM TABLE(DBMS_XPLAN.DISPLAY_CURSOR('1xp5hx4tqgd68'));

PLAN_TABLE_OUTPUT
-----------------
SQL_ID 1xp5hx4tqgd68, child number 0
-------------------------------------
SELECT /* TEST2_1 */ * FROM TEST_TABLE2 WHERE COL1 >= 50000

Plan hash value: 775196657

---------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
---------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | | | 3 (100)| |
|* 1 | TABLE ACCESS FULL| TEST_TABLE2 | 1502 | 9012 | 3 (0)| 00:00:01 |
---------------------------------------------------------------------------------

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

1 - filter("COL1">=50000)
★COL1にはインデックスを作成しているが全表スキャンの方が効率的と判断された

4. 統計情報取得(ヒストグラム収集あり)
SQL> BEGIN
2 DBMS_STATS.GATHER_TABLE_STATS(OWNNAME => 'SYS',
3 TABNAME => 'TEST_TABLE2',
4 ESTIMATE_PERCENT => 100,
5 METHOD_OPT => 'FOR COLUMNS COL1 SIZE AUTO',
6 CASCADE => TRUE);
7 END;
8 /

PL/SQLプロシージャが正常に完了しました。

5. ヒストグラムが存在する状態でレコード取得、実行計画確認
SQL> SELECT /* TEST2_2 */ * FROM TEST_TABLE2 WHERE COL1 >= 50000;

COL1 COL2
---------- ------------
100000 D

SQL> SELECT * FROM TABLE(DBMS_XPLAN.DISPLAY_CURSOR('5b1sk5jbpx7gx'));

PLAN_TABLE_OUTPUT
-----------------
SQL_ID 5b1sk5jbpx7gx, child number 0
-------------------------------------
SELECT /* TEST2_2 */ * FROM TEST_TABLE2 WHERE COL1 >= 50000

Plan hash value: 3003225609

------------------------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
------------------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | | | 3 (100)| |
| 1 | TABLE ACCESS BY INDEX ROWID BATCHED| TEST_TABLE2 | 6 | 36 | 3 (0)| 00:00:01 |
|* 2 | INDEX RANGE SCAN | PK_TEST_TABLE2 | 6 | | 2 (0)| 00:00:01 |
------------------------------------------------------------------------------------------------------

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

2 - access("COL1">=50000)
★索引スキャンが採用された

実データは合計3001行ですが「D」のEMPNOを「100000」にしたことでオプティマイザは合計100000行存在すると見積もってしまい、ヒストグラム収集前のSQL(TEST2_1)で全体の50%以上にアクセスするなら全表スキャンの方が効率的と判断してしまったようです

■参考資料
DBMS_STATS
ヒストグラム
https://www.oracle.com/technetwork/jp/ondemand/branch/120328-cbo-1593994-ja.pdf
移行前に知っておきたい、Oracle Database 12c新機能のオモテとウラ Vol.6 | アシスト
パフォーマンス改善と事前対策に役立つ Oracle SQLチューニング本気で学ぶ実践的な考え方とテクニック
新・門外不出のOracle現場ワザエキスパートが明かす運用・管理の極意

■おわりに
「上位頻度ヒストグラム」、「ハイブリッドヒストグラム」はどちらも未検証ですが、上位頻度ヒストグラムについてはヒストグラムの作成方法は頻度分布ヒストグラムと似ていますが、上位N個にフォーカスすることで頻度分布ヒストグラムより領域節約できる印象でした。
ハイブリッドヒストグラムについては「最初から頻度分布ヒストグラムで良いのでは？」と思いましたが、NDVが最大数(12cは2048)を超えた場合、頻度分布ヒストグラムで対応できないため、いったん高さ調整ヒストグラムでヒストグラムを作成して最終的に頻度分布ヒストグラムを作成している印象でした。
なお、どのヒストグラムが作成されるかは参考資料(ヒストグラム)の「図11-1 ヒストグラム作成のディシジョン・ツリー」のフローで決まります。