調査方法・結果
以下の状況を作ります。
(1) テーブルに行を 10^5 追加する。
(2) テーブルの行を 10^5 ⇒ 10^6 まで増やす。
(3) テーブルの行を 10^6 ⇒ 10^5 まで減らす（※インデックス肥大化の発生）。
(4) テーブルを REINDEX する（※インデックス肥大化の解消）。
各状況において、以下の項目を確認します。
- インデックスの行数
- インデックスのページ数
- SELECT で 5000 行を Index Only Scan した時のコスト
testdb=# CREATE TABLE tab1(c1 INTEGER PRIMARY KEY);
CREATE TABLE
testdb=# \d tab1;
Table "public.tab1"
Column | Type | Collation | Nullable | Default
--------+---------+-----------+----------+---------
c1 | integer | | not null |
Indexes:
"tab1_pkey" PRIMARY KEY, btree (c1)(1) テーブルに行を 10^5 追加する。
testdb=# INSERT INTO tab1 SELECT generate_series(1, 1e+5);
INSERT 0 100000
testdb=# VACUUM ANALYZE;
VACUUM
testdb=# SELECT reltuples, relpages FROM pg_class WHERE relname = 'tab1_pkey';
reltuples | relpages
-----------+----------
100000 | 276
(1 row)
testdb=# EXPLAIN SELECT * FROM tab1 WHERE c1 <= 5000;
QUERY PLAN
--------------------------------------------------------------------------------
Index Only Scan using tab1_pkey on tab1 (cost=0.29..150.12 rows=5133 width=4)
Index Cond: (c1 <= 5000)
(2 rows)(2) テーブルの行を 10^5 ⇒ 10^6 まで増やす。
testdb=# INSERT INTO tab1 SELECT generate_series((1e+5)+1, 1e+6);
INSERT 0 900000
testdb=# VACUUM ANALYZE;
VACUUM
testdb=# SELECT reltuples, relpages FROM pg_class WHERE relname = 'tab1_pkey';
reltuples | relpages
-----------+----------
1e+06 | 2745
(1 row)
testdb=# EXPLAIN SELECT * FROM tab1 WHERE c1 <= 5000;
QUERY PLAN
--------------------------------------------------------------------------------
Index Only Scan using tab1_pkey on tab1 (cost=0.42..152.44 rows=5258 width=4)
Index Cond: (c1 <= 5000)
(2 rows)インデックスの行数が10倍になると、インデックスのページ数もほぼ10倍になりました。ただ、Index Only Scan のコストはほとんど変わりません。Index Only Scan が必要な範囲のインデックスのページだけ読み込むと想定すれば、これは妥当な結果といえそうです。
次にインデックスの行数を1/10にして、Index Only Scan へのコスト影響を確認します。
(3) テーブルの行を 10^6 ⇒ 10^5 まで減らす（※インデックス肥大化の発生）。
testdb=# DELETE FROM tab1 WHERE c1 > 1e+5;
DELETE 900000
testdb=# VACUUM ANALYZE;
VACUUM
testdb=# SELECT reltuples, relpages FROM pg_class WHERE relname = 'tab1_pkey';
reltuples | relpages
-----------+----------
100000 | 2745
(1 row)
testdb=# EXPLAIN SELECT * FROM tab1 WHERE c1 <= 5000;
QUERY PLAN
--------------------------------------------------------------------------------
Index Only Scan using tab1_pkey on tab1 (cost=0.42..649.14 rows=5070 width=4)
Index Cond: (c1 <= 5000)
(2 rows)インデックスの行数は1/10に変わりましたが、インデックスのページ数は変わりません。そして全体推定コストは4.3倍に増えました。
(4) テーブルを REINDEX する（※インデックス肥大化の解消）。
testdb=# REINDEX TABLE tab1;
REINDEX
testdb=# SELECT reltuples, relpages FROM pg_class WHERE relname = 'tab1_pkey';
reltuples | relpages
-----------+----------
100000 | 276
(1 row)
testdb=# EXPLAIN SELECT * FROM tab1 WHERE c1 <= 5000;
QUERY PLAN
--------------------------------------------------------------------------------
Index Only Scan using tab1_pkey on tab1 (cost=0.29..145.02 rows=5070 width=4)
Index Cond: (c1 <= 5000)
(2 rows)REINDEX でインデックスを再生成することで、インデックスのページ数は縮小しました。
全体推定コストも当初とほぼ変わらない数字になりました。
インデックスコストのモデル化
インデックスコストのモデル化を行います。状況は今回の実験例を想定します。
PostgreSQL のマニュアルに「インデックスコスト推定関数」の説明があります。
62.6. インデックスコスト推定関数
この説明ページには「典型的なコスト概算」の例が記載されています。この流れに従いつつ、差分を説明します。
インデックスのコスト計算は下記のソースコード・関数で実装されているようです。
src/backend/optimizer/path/costsize.c
cost_index(IndexPath *path, PlannerInfo *root, double loop_count, bool partial_path)
この関数の実装に「インデックスコスト推定関数」である amcostestimate を呼びだす箇所があります。amcostestimate は下記のソースコード・関数で実装されています。
src/backend/utils/adt/selfuncs.c
btcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, Cost *indexStartupCost, Cost *indexTotalCost, Selectivity *indexSelectivity, double *indexCorrelation, double *indexPages)
以降、必要に応じてソースコードを参照します。
計算で用いる変数名が対応するプランナコスト定数と異なる場合は併記しています。
プランナコスト定数は下記マニュアルに記載されています。
20.7. 問い合わせ計画
1. 与えられた制約条件に基づいて訪れられるメインテーブルの行の割合を概算して返します。
「対象の行数 / 全体の行数」が indexSelectivity になると仮定します。
対象の行数は 5000 です。
全体の行数が 10^5：
5*10^3 / 10^5 = 0.05
全体の行数が 10^6：
5*10^3 / 10^6 = 0.005
2. スキャン中に訪れられるインデックスの行数を概算します。多くのインデックス種類では、これは indexSelectivity とインデックスの中にある行数を掛けたものと等しいですが、それより多い場合もあります。
全てのケースで 5000 とします。
3. スキャン中に抽出されるインデックスページ数を概算します。これは単に indexSelectivity にページ内のインデックスのサイズを掛けたものになるでしょう。
「ページ内のインデックスのサイズ」は pg_class の relpages に等しいとします。
実装を見ると小数点以下の切り上げをしているので、計算でも切り上げします。
src/backend/utils/adt/selfuncs.c
genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, GenericCosts *costs)
numIndexPages = ceil(numIndexTuples * index->pages / index->tuples);
テーブルに行を 10^5 追加した後：
ceil(0.05 * 276) = 14
テーブルの行を 10^5 ⇒ 10^6 まで増やした後：
ceil(0.005 * 2745) = 14
テーブルの行を 10^6 ⇒ 10^5 まで減らした後：
ceil(0.05 * 2745) = 138
テーブルを REINDEX した後：
ceil(0.05 * 276) = 14
4. インデックスアクセスコストを計算します。汎用的な概算においては以下のように行うでしょう。
/*
* 一般的な仮定は、インデックスページは逐次的に読まれるので、
* random_page_cost ではなく、それぞれ seq_page_cost が掛かるというものです。
* 各インデックス行での indexquals の評価にもコストが掛かります。
* コストはすべてスキャンの間に徐々に支払われると仮定します。
*/
＜中略＞
*indexTotalCost = seq_page_cost * numIndexPages +
(cpu_index_tuple_cost + index_qual_cost.per_tuple) * numIndexTuples;
マニュアルでは seq_page_cost で計算しています。ですが、実装では random_page_cost で計算していました。
src/backend/utils/adt/selfuncs.c
genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, GenericCosts *costs)
indexTotalCost = numIndexPages * spc_random_page_cost;
indexquals の評価はほぼマニュアル通りです。
src/backend/utils/adt/selfuncs.c
genericcostestimate(PlannerInfo *root, IndexPath *path, double loop_count, GenericCosts *costs)
indexTotalCost += numIndexTuples * num_sa_scans * (cpu_index_tuple_cost + qual_op_cost);
ここまでを踏まえ、マニュアル記載の式で seq_page_cost を random_page_cost に置換して再計算します。
indexTotalCost = random_page_cost * numIndexPages + (cpu_index_tuple_cost + index_qual_cost.per_tuple) * numIndexTuples;
random_page_cost = 4.0
numIndexPages = 「スキャン中に抽出されるインデックスページ数」に等しいとします。
cpu_index_tuple_cost = 0.005
index_qual_cost.per_tuple = cpu_operator_cost = 0.0025
numIndexTuples = 「スキャン中に訪れられるインデックスの行数」に等しいとします。
テーブルに行を 10^5 追加した後：
4.0 * 14 + (0.005 + 0.0025) * 5000 = 93.5
テーブルの行を 10^5 ⇒ 10^6 まで増やした後：
4.0 * 14 + (0.005 + 0.0025) * 5000 = 93.5
テーブルの行を 10^6 ⇒ 10^5 まで減らした後：
4.0 * 138 + (0.005 + 0.0025) * 5000 = 589.5
テーブルを REINDEX した後：
4.0 * 14 + (0.005 + 0.0025) * 5000 = 93.5
さらに CPU コストが加算されます。
src/backend/optimizer/path/costsize.c
cost_index(IndexPath *path, PlannerInfo *root, double loop_count, bool partial_path)
cpu_run_cost += cpu_per_tuple * tuples_fetched;
cpu_per_tuple = cpu_tuple_cost = 0.01
tuples_fetched = 「スキャン中に訪れられるインデックスの行数」に等しいとします。
テーブルに行を 10^5 追加した後：
93.5 + 0.01 * 5000 = 143.5
テーブルの行を 10^5 ⇒ 10^6 まで増やした後：
93.5 + 0.01 * 5000 = 143.5
テーブルの行を 10^6 ⇒ 10^5 まで減らした後：
589.5 + 0.01 * 5000 = 639.5
テーブルを REINDEX した後：
93.5 + 0.01 * 5000 = 143.5
モデル化により、インデックス肥大化によるインデックスコスト増大の要因は「スキャン中に抽出されるインデックスページ数」が大きいとわかります。
また、random_page_cost もインデックスコストに大きく影響しています。マニュアルでは以下の記載があります。
例えばSSDのような、シーケンシャルアクセスに比べてランダム読み込みコストがあまり大きくない記憶装置の場合も、random_page_cost に対し1.1のようにより低い値のモデル化の方が良いでしょう。
20.7. 問い合わせ計画
この指針に従うならば、インデックス肥大化によるインデックスコスト増大を抑えることができます。結果としてより最適な実行計画を得られるかもしれません。
![[改訂新版]内部構造から学ぶPostgreSQL 設計・運用計画の鉄則 (Software Design plus)](https://m.media-amazon.com/images/I/51G-Ui96m4L._SL500_.jpg "[改訂新版]内部構造から学ぶPostgreSQL 設計・運用計画の鉄則 (Software Design plus)")
