PostgreSQLの見積もりについて調べてみた

# はじめに

PostgreSQLの見積もりは、テーブル、インデックスの他にも、WALファイル、アーカイブログ等の様々なファイルを含めて実施する必要があります。
とは言え、容量の大部分を占めるのはテーブルとインデックスであることは他のRDBと変わりはありません。
今回はテーブル・インデックスの見積もりについて調べてみました。
（間違いがあったら教えてください)


# PostgreSQLの見積もりの基本（だと思うこと）

PostgreSQLの見積もりについて基本と思われることを書いてみます。

## ページ

PostgreSQLでは、実ファイル中のデータはページという単位で分かれています。
1ページは8192bytesでその中にテーブル・インデックスのデータが格納されます。

ページに含まれるデータは下表のアイテムで構成されます。
（引用：- [PostgreSQL 11.5文書　68.6. データベースページのレイアウト](https://www.postgresql.jp/document/11/html/storage-page-layout.html)）

| アイテム       | 説明                                                                                                               |
|----------------|--------------------------------------------------------------------------------------------------------------------|
| PageHeaderData | 長さは24バイト。空き領域ポインタを含む、ページについての一般情報です。                                             |
| ItemIdData     | 実際のアイテムを指すアイテム識別子の配列です。各項目は（オフセットと長さの）ペアです。1アイテムにつき4バイトです。 |
| 空き領域       | 割り当てられていない空間です。新規のアイテム識別子はこの領域の先頭から、新規のアイテムは最後から割り当てられます。 |
| アイテム       | 実際のアイテムそのものです。                                                                                       |
| 特別な空間     | インデックスアクセスメソッド特有のデータです。異なるメソッドは異なるデータを格納します。通常のテーブルでは空です。 |



# テーブルの見積もり

テーブルは前述の表の「特別な空間」以外のデータが含まれます。
pgbenchツールで生成されたpgbench_accountsテーブルを例に見積もりを行ってみます。


まず、1ページに入るタプル数をカウントするため、テーブルの行長を確認します。

```sql
testdb=# select tablename, attname, avg_width from pg_stats where tablename = 'pgbench_accounts';
    tablename     | attname  | avg_width 
------------------+----------+-----------
 pgbench_accounts | bid      |         4
 pgbench_accounts | abalance |         4
 pgbench_accounts | filler   |        85
 pgbench_accounts | aid      |         4
```

上のSQLの結果から、1タプルは(4+4+85+4)=97bytesであることが分かります。
また、1タプル毎に24bytesのヘッダーが付与されるため、実際には97+24=121bytesとなります。

そのため、1ページに入るタプル数は以下のように計算されます。

1ページに入るタプル数
= (8192 - PageHeaderData ) / ( 1タプルのサイズ + ItemIdData )
= (8192 - 24) / ( 121 + 7 + 4 )
= 61.878
= 61タプル

途中で7bytesを加えて1タプルを128bytesにしています。これは1タプルが8バイトでアラインされているからです。
(floorを使って表現した方が分かりやすいことに後から気づいたけど修正していない）

100000行の場合は、

- 100000 / 61 = 1639.34 = 1640ページ

になります。



[追記]計算式が見つからないと思っていましたが、見逃していただけで[ここ](https://lets.postgresql.jp/documents/tutorial/gihyo_rensai/5)に以下のように書いていました。

- 8KB × ceil(行数 / floor(floor(8KB × fillfactor - 24) / (28 + 行データ長)))
※floorで8の倍数に切り上げているようです。



実際にSQLでpg_classからページ数を検索すると1640ページとなり、サイジング結果と一致していることが分かります。

```sql
testdb=# select reltuples, relpages from pg_class where relname = 'pgbench_accounts';
-[ RECORD 1 ]-----
reltuples | 100000
relpages  | 1640
```

実際にサイズは1640ページ * 8192 bytes = 13434880 bytes = 13120 KB　となります。
SQLで実際のサイズを検索した結果とも以下のように一致します。

```sql
testdb=# select pg_relation_size('pgbench_accounts');
 pg_relation_size 
------------------
         13434880
```



# FILLFACTORの考慮

FILLFACTORはページ内の空き容量の割合を示します。デフォルトは100%で空き容量はありません。更新が発生するテーブルでは90%程度にすることが多いようです。

FILLFACTORを90%にした場合、ページ内の空き容量は以下のようになります。

- 8192bytes * ( 1 - 0.9 ) = 819 bytes
 
1ページに入るタプル数は以下のようになります。

1ページに入るタプル数
= (8192 - PageHeaderData - 空き容量) / ( 1タプルのサイズ + ItemIdData )
= (8192 - 24 - 819) / ( 121 + 7 + 4 )
= 55.67
= 55タプル



# インデックスの見積もり

インデックスは前述の表の「特別な空間」のデータも含まれることがテーブルと異なります。
pgbenchツールで生成されたpgbench_accountsテーブルの主キーpgbench_accounts_pkeyを例に見積もりを行ってみます。


まず、1ページに入るタプル数をカウントするため、カラムの平均キー長を確認します。
当然ですが、テーブルの時と同じ調べ方になります。

```sql
testdb=# select tablename, attname, avg_width from pg_stats where tablename = 'pgbench_accounts';
    tablename     | attname  | avg_width 
------------------+----------+-----------
 pgbench_accounts | bid      |         4
 pgbench_accounts | abalance |         4
 pgbench_accounts | filler   |        85
 pgbench_accounts | aid      |         4
```

pgbench_accounts_pkeyの定義を確認します。aid列のB-treeで構成されていることが分かります。

```
testdb=#  select * from pg_indexes where indexname = 'pgbench_accounts_pkey';
-[ RECORD 1 ]--------------------------------------------------------------------------------------
schemaname | public
tablename  | pgbench_accounts
indexname  | pgbench_accounts_pkey
tablespace | 
indexdef   | CREATE UNIQUE INDEX pgbench_accounts_pkey ON public.pgbench_accounts USING btree (aid)

```

先ほどのSQLではaid列は平均キー長が4bytesであることが分かっています。
また、インデックス1レコード毎に12bytesのヘッダーが付与されるため、実際には4+12=16bytesとなります。

そのため、1ページに入るインデックス数は以下のように計算されます。

1ページに入るインデックス数
= (8192 - PageHeaderData - (8192bytes * ( 1 - 0.9 ))) / ( 1インデックスのサイズ + ItemIdData )
= (8192 - 24 - 819) / ( floor(4 + 12, 8) + 4 )
= (7349) / ( 16 + 4 )
= 367.45
= 367タプル

100000行の場合は、

- 100000 / 367 = 272.47 = 273ページ

になります。

実際にSQLでpg_classからページ数を検索するとleaf_pagesは274ページであり、サイジング結果とほぼ一致していることが分かります。

```sql
testdb=# select * from pgstatindex('pgbench_accounts_pkey');
-[ RECORD 1 ]------+--------
version            | 3
tree_level         | 1
index_size         | 2260992
root_block_no      | 3
internal_pages     | 1
leaf_pages         | 274
empty_pages        | 0
deleted_pages      | 0
avg_leaf_density   | 89.83
leaf_fragmentation | 0

```

実際のサイズは上のように2260992 bytes = 2208 KB であり、これは276ページに相当します。すこしずれがありますが、B-Treeのmetaデータページとブランチノード(internal_pages)分です。

[2020/2/15追記]
metaデータページとブランチノード(internal_pages)分の見積もり方を追記。

metaデータページは1ページで固定。
インターナルページは以下の計算式になります。FILLFACTORは70%で固定です。

・1インターナルページ当たりのエントリー数

floor( (ブロックサイズ * FILLFACTOR - 24bytes - 16bytes) / インデックス長 )
= floor( (8192 * 0.7 - 24 - 16) / 20 ) = 5694 bytes / 20 bytes
= 284.7 ページ = 285 ページ

・必要なインターナルページ数

リーフページ数 / 1インターナルページ当たりのエントリー数
= ceil(274 / 285)
= 1 ページ
※1ページだから計算しても面白くないですが


# 最後に

- dead tuplesが発生することを考えると、見積もりした結果を1.2倍程度にした方が良いかも（ケースバイケース）。
- インデックスの場合は、インデックスの分割やデータ削除の関係でページ数が増えるので、余裕を持った見積もりとしたほうが良い。動く環境があれば実際に動かしてチューニングしながら見積もった方が良い。
- そもそも、机上よりも実際にデータを入れてサイジングした方が楽。皆はどうしているのだろう。
- （TODO）TOASTについても調べる。


# 参考

- [PostgreSQL 11.5文書　68.6. データベースページのレイアウト](https://www.postgresql.jp/document/11/html/storage-page-layout.html)
- [pg_filedump](https://git.postgresql.org/gitweb/?p=pg_filedump.git;a=summary)
- [Let's Postgres　第5回　PostgreSQL でのデータベース構築の際に必要となる物理設計のポイント](https://lets.postgresql.jp/documents/tutorial/gihyo_rensai/5)