ぱと隊長日誌

ブログ運用もエンジニアとしての生き方も模索中

PostgreSQL のインデックス肥大化と実行計画のコストへの影響

データベース

お知らせ

本記事をベースに新しい記事を公開しました。
PostgreSQL インデックス肥大化とインデックスコストへの影響（再モデル化） - ぱと隊長日誌

新しい記事ではインデックスコストモデルの正確性を向上させました。
新しい記事を参照いただけますと幸いです。

概要

PostgreSQL のインデックスサイズは一度大きくなると、その後小さくなるタイミングが限られています。

「［改訂新版］内部構造から学ぶPostgreSQL-設計・運用計画の鉄則」でインデックスファイルサイズが小さくなるのは以下のタイミングとしています。

  • DROP INDEX でインデックス自体を削除した場合
  • TRUNCATE TABLE でテーブル全体を空にした場合
  • REINDEX でインデックスを再構成した場合

[改訂新版]内部構造から学ぶPostgreSQL 設計・運用計画の鉄則 (Software Design plus)

[改訂新版]内部構造から学ぶPostgreSQL 設計・運用計画の鉄則 (Software Design plus)

Amazon

テーブルのデータの追加・更新・削除を繰り返しているうちに、インデックスファイルサイズが必要以上に大きくなった状態を、本記事では「インデックスの肥大化」としました。

インデックスの肥大化した状況では実行計画のコスト計算に影響することがあります。これは適切な実行計画を選択する妨げとなるかもしれません。

本記事ではインデックスの肥大化が実行計画のコスト計算に影響を与えた例を示します。

検証環境

なお、PostgreSQL の日本語版マニュアルの最新版は現時点で 12 を対象としているため、記事の中ではこれを参照しています。

調査方法・結果

以下の状況を作ります。
(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..143.27 rows=4970 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..139.92 rows=4771 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..621.35 rows=4853 width=4)
   Index Cond: (c1 <= 5000)
(2 rows)

インデックスの行数は1/10に変わりましたが、インデックスのページ数は変わりません。そして全体推定コストは4.4倍に増えました。

(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..141.22 rows=4853 width=4)
   Index Cond: (c1 <= 5000)
(2 rows)

REINDEX でインデックスを再生成することで、インデックスのページ数は縮小しました。
全体推定コストも当初とほぼ変わらない数字になりました。

全体推定コストのモデル化

インデックスが肥大化した時の全体推定コストのモデル化にチャレンジしました。結論として今回はうまく導けなかったのですが、今後の再挑戦に向けて記録を残しておきます。

インデックスのコスト計算は下記のソースコード・関数で実装されていると目星を付けました。
src/backend/optimizer/path/costsize.c
cost_index(IndexPath *path, PlannerInfo *root, double loop_count, bool partial_path)

この関数の実装に amcostestimate 関数を呼び出す箇所があり、この実装を探し当てることはできませんでしたが（C言語の知識が無さ過ぎて辛い…）、PostgreSQL のマニュアルに「インデックスコスト推定関数」として説明されているページを見つけました。
61.6. インデックスコスト推定関数

この説明ページには「典型的なコスト概算」の例が記載されていました。インデックスのコスト計算がこれに従うと仮定し、インデックス肥大化の影響をモデル化できないか試みました。

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 に等しいと仮定します。

テーブルに行を 10^5 追加した後：
0.05 * 276 = 13.8

テーブルの行を 10^5 ⇒ 10^6 まで増やした後：
0.005 * 2745 = 13.725

テーブルの行を 10^6 ⇒ 10^5 まで減らした後：
0.05 * 2745 = 137.25

テーブルを REINDEX した後：
0.05 * 276 = 13.8

4. インデックスアクセスコストを計算します。 汎用的な概算においては以下のように行うでしょう。
＜中略＞
*indexTotalCost = seq_page_cost * numIndexPages + (cpu_index_tuple_cost + index_qual_cost.per_tuple) * numIndexTuples;

seq_page_cost = 1.0
cpu_index_tuple_cost = 0.005
index_qual_cost.per_tuple = 不明だったので cpu_operator_cost の 0.0025 と仮定します。
numIndexPages = 「スキャン中に抽出されるインデックスページ数」に等しいと仮定します。
numIndexTuples = 「スキャン中に訪れられるインデックスの行数」に等しいと仮定します。

テーブルに行を 10^5 追加した後：
1.0 * 13.8 + (0.005 + 0.0025) * 5000
=51.3

テーブルの行を 10^5 ⇒ 10^6 まで増やした後：
1.0 * 13.725 + (0.005 + 0.0025) * 5000
=51.225

テーブルの行を 10^6 ⇒ 10^5 まで減らした後：
1.0 * 137.25 + (0.005 + 0.0025) * 5000
=174.75

テーブルを REINDEX した後：
1.0 * 13.8 + (0.005 + 0.0025) * 5000
=51.3

調査で出力された全体推定コストの値とはかけ離れていますが、インデックスの肥大化でコストが大きく計算される傾向は同じでした。

モデルの妥当性の検証は不十分ですが、今後の再調査に向けた布石とはなりそうです。

まとめ

インデックスの肥大化は実行計画のコスト計算に影響を与えることがあるとわかりました。

ただ、インデックスの肥大化がコスト計算にどれほど影響を及ぼすのかについて示すことはできなかったため、今後の課題といたします。