木を低くすると、読む回数が減る

Docker の postgres:17-alpine(PostgreSQL 17.11, aarch64-unknown-linux-musl)で、bigint 1列のテーブルに索引を作りました。まずページサイズです。

$ docker exec g2pg psql -U postgres -tAc "show block_size"
8192

公式文書の “usually 8 kB” が実機で 8192 と確認できました。次に行数を変えて高さを取ります。

idx    | i1 (1,000 rows)       root | 3     level | 1
idx    | i2 (100,000 rows)     root | 3     level | 1
idx    | i3 (10,000,000 rows)  root | 290   level | 2
 
relname |   bytes   | pages
---------+-----------+-------
i1      |     40960 |     5
i2      |   2260992 |   276
i3      | 224641024 | 27422

取り違えやすいのが level です。 1,000万行の索引は level = 2 ですが段数ではありません。ページを種別で数えると根・中間・葉の3種類が出るので、段数は 3 段です。nbtree.h は btpo_level を zero for leaf pages と書くので、根の level = 2 は 0・1・2 の3段です。

その集計が扇出しの実物です(索引 i3 の全 27,421 ページ)。

 type | pages | min_items | avg_items | max_items
------+-------+-----------+-----------+-----------
i    |    97 |        59 |       283 |       285
l    | 27323 |       148 |       367 |       367
r    |     1 |        97 |        97 |        97
 
   what     | type | live_items | dead_items | avg_item_size | page_size | free_size
--------------+------+------------+------------+---------------+-----------+-----------
i3 root page | r    |         97 |          0 |            15 |      8192 |      6216
i3 leaf page | l    |        367 |          0 |            16 |      8192 |       808

根が 97 項目、中間ページが平均 283 項目、葉が平均 367 項目。 これを掛けます。

97 × 283 × 367 = 10,074,517

投入した行数は 10,000,000。差は 0.75%。 扇出しを掛け合わせる素朴な算数が、実測を再現しています。

概算式も確かめます。葉の項目は平均16バイトなので 8192 ÷ 16 = 512。実測は 367、約 72%。この差の理由は公式文書にあります。

The first 24 bytes of each page consists of a page header (PageHeaderData).

The final section is the "special section" which can contain anything the access method wishes to store. For example, b-tree indexes store links to the page's left and right siblings, as well as some other data relevant to the index structure.

ただし主因は別です。同じ文書は、項目ごとに行ポインタが要ると書いています。

Array of item identifiers pointing to the actual items. Each entry is an (offset,length) pair. 4 bytes per item.

さらに CREATE INDEX の文書は B-trees use a default fillfactor of 90 と書き、作成時の葉は約90%までです。b-tree の special section(16バイト)も入れると (8192 − 24 − 16 − 8192×0.10) ÷ (16 + 4) ≈ 366.6 で、実測とほぼ合います。512 は上限の見積もりで、分岐数そのものではありません。 中間の283も、作成時は約70%で打ち切った値です(nbtree.h の BTREE_NONLEAF_FILLFACTOR 70。(8152 − 8192×0.30) ÷ 20 ≈ 284.7)。

底が大きいことの帰結が、実測にもうひとつ出ています。

行数            索引のページ数   level   段数
1,000                    5        1      2
100,000                276        1      2
10,000,000          27,422        2      3

1,000行と10万行で段数が同じです。 さらに100倍で、ようやく1段増えました。段数は階段状にしか増えず、その幅が扇出しの分だけ広い。「データが10倍に増えたので索引が深くなったはずだ」という推論は、その10倍が階段をまたいでいなければ成り立ちません。

ページを大きくすればどうか。MySQL の用語集は、5.5 までの固定値だった16KBについてこう書いています。

large enough to hold the data for most rows, yet small enough to minimize the performance overhead of transferring unneeded data to memory.

1回で多く取れるが、要らないデータも運ぶ。 扇出しを上げることには対価があると公式が書いています。ただし本教材は MySQL では高さを実測していません。3段は PostgreSQL 17.11 の数字です。