PostgreSQL の共有メモリバッファサイズとインデックス更新の関係

概要

PostgreSQL の共有メモリバッファにはテーブルのデータだけでなく、インデックスのデータが含まれています。そこで、共有メモリバッファサイズがインデックスの更新に与える影響を検証及び考察しました。

検証環境

Windows の Hyper-V による仮想マシンを検証環境としました。

ホスト

プロセッサ	Intel Core i5-6600 CPU @ 3.30GHz
メモリ	20.0 GB
SSD	SanDisk SDSSDH3
OS	Windows 10 Pro バージョン 1909

Hyper-V

プロセッサ	4個の仮想プロセッサ
メモリ	8.0 GB
OS	CentOS Linux release 8.2.2004
DB	PostgreSQL 13.1

PostgreSQL設定 (postgresql.conf)

デフォルトの設定から変更した箇所を示します。

shared_buffers = {128MB | 2048MB}

検証方法

以下の条件を組み合わせて測定を行いました。

• shared_buffers の設定値
  • 128MB, 2048MB
• B-tree インデックスの数
  • 0～5 の範囲
• 格納値（テーブルの列に挿入する値）
  • 昇順・降順・固定値・ランダム

実行時間は EXPLAIN の Execution Time で測定しました。

バッファの使用状況は EXPLAIN の出力で INSERT ノードに出力された値を参照しました。

インデックス5個でのスクリプト例を挙げます。

CREATE TABLE tab1 (col1 INTEGER, col2 INTEGER, col3 INTEGER, col4 INTEGER, col5 INTEGER);
CREATE INDEX tab1_col1_index ON tab1 (col1);
CREATE INDEX tab1_col2_index ON tab1 (col2);
CREATE INDEX tab1_col3_index ON tab1 (col3);
CREATE INDEX tab1_col4_index ON tab1 (col4);
CREATE INDEX tab1_col5_index ON tab1 (col5);

BEGIN;

SELECT 'index = 5';

-- 以下のいずれかを実行する。
-- 昇順
EXPLAIN (ANALYZE, BUFFERS) INSERT INTO tab1 SELECT val, val, val, val, val FROM generate_series(1, 10000000) val;
-- 降順
EXPLAIN (ANALYZE, BUFFERS) INSERT INTO tab1 SELECT (10000000 - val), (10000000 - val), (10000000 - val), (10000000 - val), (10000000 - val) FROM generate_series(1, 10000000) val;
-- 固定値
EXPLAIN (ANALYZE, BUFFERS) INSERT INTO tab1 SELECT 1, 1, 1, 1, 1 FROM generate_series(1, 10000000);
-- ランダム
SELECT setseed(0);
EXPLAIN (ANALYZE, BUFFERS) INSERT INTO tab1 SELECT random.val, random.val, random.val, random.val, random.val FROM (SELECT floor(random() * 10000000) val FROM generate_series(1, 10000000)) random;

COMMIT;

DROP TABLE tab1;

検証結果

＜図1　shared_buffers = 128MB　実行時間＞

＜図2　shared_buffers = 2048MB　実行時間＞

＜図3　shared_buffers と実行時間＞

shared_buffers = 128MB での実行結果（図1）を見ると、ランダムな値を INSERT した時でインデックスが増えるに従い、実行時間が指数関数のような増加を描いています。インデックスの中身は同じであるので、shared_buffers = 2048MB での実行結果（図2）のような線形に近い増加となることを期待していました。

shared_buffers 設定値の違いは実行時間の違いとしても現れます。インデックス数 = 5・ランダム値で shared_buffers の値を変えて実行した結果が図3となります。実行時間が大きく異なっています。

この結果を考察します。

まず、インデックスのデータは共有メモリバッファに読み込まれます。

共有ブロックには、通常のテーブルとインデックスからのデータが含まれます。

EXPLAIN

また、ランダムな値でのインデックス更新は幅広い範囲のリーフページにアクセスします。

the values are not sequential at all, in fact each insert is likely to touch completely new leaf index leaf page (assuming the index is large enough).

On the impact of full-page writes - 2ndQuadrant | PostgreSQL

十分な共有メモリバッファが無いとき、更新対象となるインデックスデータの一部しか共有メモリバッファに展開できず、処理の進捗に応じてデータの入れ替えが都度発生し、パフォーマンスに影響が出ると推測されます。

検証結果で言えば shared_buffers = 128MB・ランダムのケースがそれにあたります。ランダムな値によるインデックス更新は幅広い範囲のリーフページにアクセスが必要、つまり更新対象となるインデックスデータの範囲が広い（サイズが大きい）ということになります。これに対して十分な共有メモリバッファが無いとデータの入れ替えが発生し、実行時間悪化につながったと考えられます。

共有メモリバッファの使用状況でも特徴が表れていました。

shared_buffers[MB]	index	shared hit	read	dirtied	written
128	0	10,127,370	17	63,695	102,213
128	1	38,521,264	1,557,291	1,663,475	1,705,449
128	2	61,878,755	8,150,968	8,296,359	8,293,007
128	3	83,751,346	16,229,545	16,418,695	16,317,232
128	4	105,068,771	24,863,288	25,089,897	24,692,005
128	5	126,006,686	33,876,541	34,155,565	32,979,050
2048	0	10,127,370	17	63,695	63,695
2048	1	40,078,537	18	135,356	96,107
2048	2	70,029,704	19	259,384	128,519
2048	3	99,980,871	20	537,166	160,931
2048	4	129,932,038	21	879,378	193,343
2048	5	159,883,205	22	1,189,253	225,755

＜表1　shared_buffers と共有メモリバッファ使用状況＞

特に読み取り数 (read) の値が顕著に異なります。EXPLAIN ANALYZE のマニュアルで読み取り数の明確な定義はなされていませんが、共有メモリバッファへ読み込まれたブロック数を意味していると思われます。このように考えると、共有メモリバッファのデータの入れ替えが発生し、読み取り数の違いとして現れたのではないかと推測できます。

まとめ

今回の検証から以下のことが分かりました。

• インデックス数の増加は共有メモリバッファの占有率も増加させる。
• インデックスに格納される値の傾向が共有メモリバッファの占有率に影響する。

インデックスと共有メモリバッファサイズの関係は大量のデータを追加・更新する場面で特に影響を受けます。

実際の環境での共有メモリバッファの状況は動的であり、その時々で左右されます。また、共有メモリバッファにどれだけメモリを割り当てられるかはリソースとの兼ね合いもあり、調整は難しいかもしれません。

不要なインデックスを削除することが実効的な影響緩和策といえそうです。

PostgreSQL の B-tree インデックスの数・格納値と INSERT 処理の関係

概要

データベースのインデックスは数が多くなるほどテーブルの更新処理 (INSERT / UPDATE) が遅くなるといわれています。また、B-tree インデックスの断片化が進むとキャッシュヒット効率が悪化し、性能に影響を及ぼすとも言われています。

そこで今回は B-tree インデックス（本記事内では「インデックス」と略します）の数と格納する値に着目し、INSERT 処理にどれほど影響するのかを検証しました。

今回の検証は PostgreSQL をターゲットにしており、実装の異なる他のデータベースでは結果の異なる可能性があることにご注意ください。

検証環境

Windows の Hyper-V による仮想マシンを検証環境としました。

ホスト

プロセッサ	Intel Core i5-6600 CPU @ 3.30GHz
メモリ	20.0 GB
SSD	SanDisk SDSSDH3
OS	Windows 10 Pro バージョン 1909

Hyper-V

プロセッサ	4個の仮想プロセッサ
メモリ	8.0 GB
OS	CentOS Linux release 8.2.2004
DB	PostgreSQL 13.1

PostgreSQL設定 (postgresql.conf)

デフォルトの設定から変更した箇所を示します。

shared_buffers = 2048MB
full_page_writes = {on | off}

full_page_writes は通常のケースでは on とし、一部のケースのみ off で検証しました。

検証方法

以下の条件を組み合わせて測定を行いました。

• インデックスの数
  • 0～5 の範囲
• 格納値（テーブルの列に挿入する値）
  • 昇順・降順・固定値・ランダム

格納値がランダムのケースにおいてのみ、full_page_writes を on / off の両方で測定しました。

実行時間は EXPLAIN の Execution Time で測定しました。

バッファの使用状況は EXPLAIN の出力で INSERT ノードに出力された値を参照しました。

pgstatindex でインデックスの統計情報を取得しました。

インデックス5個でのスクリプト例を挙げます。

CREATE TABLE tab1 (col1 INTEGER, col2 INTEGER, col3 INTEGER, col4 INTEGER, col5 INTEGER);
CREATE INDEX tab1_col1_index ON tab1 (col1);
CREATE INDEX tab1_col2_index ON tab1 (col2);
CREATE INDEX tab1_col3_index ON tab1 (col3);
CREATE INDEX tab1_col4_index ON tab1 (col4);
CREATE INDEX tab1_col5_index ON tab1 (col5);

BEGIN;

SELECT 'index = 5';

-- 以下のいずれかを実行する。
-- 昇順
EXPLAIN (ANALYZE, BUFFERS) INSERT INTO tab1 SELECT val, val, val, val, val FROM generate_series(1, 10000000) val;
-- 降順
EXPLAIN (ANALYZE, BUFFERS) INSERT INTO tab1 SELECT (10000000 - val), (10000000 - val), (10000000 - val), (10000000 - val), (10000000 - val) FROM generate_series(1, 10000000) val;
-- 固定値
EXPLAIN (ANALYZE, BUFFERS) INSERT INTO tab1 SELECT 1, 1, 1, 1, 1 FROM generate_series(1, 10000000);
-- ランダム
SELECT setseed(0);
EXPLAIN (ANALYZE, BUFFERS) INSERT INTO tab1 SELECT random.val, random.val, random.val, random.val, random.val FROM (SELECT floor(random() * 10000000) val FROM generate_series(1, 10000000)) random;

COMMIT;

SELECT * FROM pgstatindex('tab1_col1_index');
SELECT * FROM pgstatindex('tab1_col2_index');
SELECT * FROM pgstatindex('tab1_col3_index');
SELECT * FROM pgstatindex('tab1_col4_index');
SELECT * FROM pgstatindex('tab1_col5_index');

DROP TABLE tab1;

検証結果

＜図1　インデックス数・格納値別　実行時間＞

＜図2　インデックス数・格納値別　共有ブロックのダーティブロック数＞

格納値	version	tree_level	index_size	root_block_no	internal_pages	leaf_pages	empty_pages	deleted_pages	avg_leaf_density	leaf_fragmentation
ランダム	4	2	265,527,296	412	108	32,304	0	0	70.57	49.87
降順	4	2	403,554,304	412	241	49,020	0	0	50.34	100
昇順	4	2	224,632,832	412	97	27,323	0	0	90.09	0
固定	4	2	64,430,080	295	39	7,825	0	0	96.17	0

＜表1　インデックスの統計情報＞

図1から以下のことが分かりました。

• インデックスの数が増えるほど INSERT 処理は遅くなる。
• インデックスの更新時間は 固定 ＜ 昇順 ＜ 降順 ＜ ランダム＆FPWoff（※） ＜ ランダム となる。

（※）FPWoff は full_page_writes = off です。

格納値の種類によってインデックス有りの実行時間（≒インデックスの更新時間）が異なったのは、インデックスのページ分割が影響したと推測しています。

テーブルにデータを挿入していくと、インデックスには該当列のデータ（キー）がリーフページに挿入されていきます。インデックスのあるページがいっぱいになると、左右2つのページに分割 (SPLIT) されます。特殊なケースを除き、SPLIT が起こるとデータ量は左のページに 50%、右のページに 50% のデータ量になるように分割されます。このようにデータを分割して格納するため、断片化が起こります。
（中略）
なお、木構造の各段の一番右端ページで SPLIT が起こるケースでは、左のページにできるだけ詰めた形で分割します。このため昇順にデータが追加されるインデックスであれば、断片化の影響を避けられます。
[改訂新版]内部構造から学ぶPostgreSQL 設計・運用計画の鉄則 (Software Design plus)

表1より、昇順や固定では断片化 (leaf_fragmentation) が起きていませんが、降順やランダムでは断片化が起きたと分かります。

ランダムでの結果が悪いのは full-page write が影響していることを示唆する記事がありました。

Of course, this is due to the inherent UUID randomness. With BIGSERIAL new are sequential, and so get inserted to the same leaf pages in the btree index. As only the first modification to a page triggers the full-page write, only a tiny fraction of the WAL records are FPIs. With UUID it's completely different case, of couse – the values are not sequential at all, in fact each insert is likely to touch completely new leaf index leaf page (assuming the index is large enough).

On the impact of full-page writes - 2ndQuadrant | PostgreSQL

そこで、full-page write を off にしたところ、実行時間が短縮されました（図1）。

格納値の種類の違いによる実行時間の差異は共有ブロックのダーティブロック数と相関がありそうです（図2）。共有ブロック変更の内訳が分かれば実行時間の差異を説明できるかもしれませんが、これを調べるための手法が見つかりませんでした。

まとめ

今回の検証からは以下のことが分かりました。

• インデックスの数が増えるほど INSERT 処理は遅くなる。
• インデックスの更新時間は 固定 ＜ 昇順 ＜ 降順 ＜ ランダム＆FPWoff ＜ ランダム となる。

今回の検証では格納値の種類と実行時間の関係について、インデックスのページ分割が影響していると推測したものの、理論による裏付けを明確に示すには至りませんでした。これは今後の課題とします。

部分関数従属性と推移的関数従属性の定義

はじめに

リレーショナルデータモデルの正規化理論を理解するためには、部分関数従属性と推移的関数従属性の理解が必要となります。ですが、テキスト毎に定義のばらつきがみられました。

そこで、本記事では定義の整理とばらつきの理由について考察を行いました。

略記について

本記事内では参考にしたテキストを略記表記します。

略記	書名（著者・出版社）
RDB入門	リレーショナルデータベース入門―データモデル・SQL・管理システム・NoSQL (Information & Computing) [第3版]（増永　良文・サイエンス社）
DBSP教科書	情報処理教科書 データベーススペシャリスト 2020年版（三好　康之・翔泳社）
DBSP教本	令和02年データベーススペシャリスト合格教本（金子　則彦・技術評論社）

各書の定義

RDB入門

89ページ
[定義4.4]（完全関数従属性）関数従属性 X → Y で、X の任意の真部分集合 X' (X' ⊂ X) について X' → Y は成立しないとき、Y は X に完全関数従属しているという。

106ページ
[定義4.11]リレーション R が第2正規形であるとは次の2つの条件を満たすときをいう。
(1) R は第1正規形である。
(2) R の全ての非キー属性は R の各候補キーに完全関数従属している。

110ページ
[定義4.12]（推移的関数従属性）X, Y, Z をリレーションスキーマ R の属性集合とし、関数従属性に関して次が成立しているとする。
X → Y
Y → X が成立しない
Y → Z
ただし Y → Z は自明（な関数従属性）ではないとする（つまり、Z ⊆ Y ではない）。すると、次が成立する。
X → Z
Z → X が成立しない
このとき、X → Z を推移的関数従属性 (transitive functional dependency) といい、Z は X に推移的に関数従属する (transitively functionally dependent) という。

111ページ
[定義4.13]（第3正規形）リレーション R が第3正規形であるとは次の2つの条件を満たすときをいう。
(1) R は第2正規形である。
(2) R の全ての非キー属性は R のいかなる候補キーにも推移的に関数従属しない。

DBSP教科書

286ページ
[第2正規形の定義]
リレーション R が次の二つの条件を満たす。
(1) 第1正規形であること
(2) すべての非キー属性は、いかなる候補キーにも部分関数従属していない（完全関数従属である）こと

＜中略＞

"完全関数従属している状態" とか "完全関数従属性という性質" は、①関数従属性（候補キー：X）→（非キー属性：Y）が成立するが、②（候補キー：Xの真部分集合）→（非キー属性：Y）は成立しないときの状態及び性質のことである。逆に、①ではあるが、②が成立・存在している状態及び性質のことを "部分関数従属している" とか "部分関数従属性" という。

非キー属性：候補キーの一部にも含まれない属性

完全関数従属性の定義をDBSP教科書とRDB入門と比較すると、DBSP教科書の定義には「候補キー」や「非キー属性」が含まれており、これらに制限しています。

288ページ
[第3正規形の定義]
リレーション R が次の二つの条件を満たす。
(1) 第2正規形であること
(2) すべての非キー属性は、いかなる候補キーにも推移的関数従属していない

＜中略＞

関数従属が推移的に行われているとき、これを推移的関数従属性という。
集合 R の属性 X, Y, Z において、
① X → Y
② Y → X ではない
③ Y → Z（ただし、Z は Y の部分集合ではない）
の三つの条件が成立しているときに、"Z" は "X" に推移的に関数従属している。
このとき、次の二つが成立する。
(ⅰ) X → Z
(ⅱ) Z → X ではない

推移的関数従属の定義はDBSP教科書とRDB入門で一致しています。

DBSP教本

79ページ
完全関数従属性…非キー属性が、候補キーを構成するすべての属性に関数従属していること
部分関数従属性…非キー属性が、候補キーを構成する属性の一部に関数従属していること

完全関数従属性の定義をDBSP教本とRDB入門と比較すると、DBSP教本の定義には「候補キー」や「非キー属性」が含まれており、これらに制限しています。

完全関数従属性を「候補キー」や「非キー属性」で制限するのはDBSP教本・DBSP教科書共に共通しています。

83ページ
第 3 正規形を考える上での推移的関数従属性とは、下図のように属性 X が候補キー、属性 Y，Z が非キー属性であることを前提し、下図の①（X → Y がある）②（Y → Z がある）③（Y → X がない）のすべてが成立した関数従属性のことです。
※図は省略した。

推移的関数従属性の定義をDBSP教本とRDB入門と比較すると、DBSP教本の定義では「候補キー」や「非キー属性」を前提としています。

推移的関数従属性で「候補キー」や「非キー属性」を前提としているのはDBSP教本だけです。

定義の違いとその影響

データベーススペシャリスト試験 平成29年度午後Ⅰ問1 を参考にします。

下記の候補キーと関数従属性が与えられていました。

候補キー：
{電子会議番号，投稿番号}
{分野番号，表示順，投稿番号}

関数従属性：
① 電子会議番号 → 議題
② 分野番号 → 分野名
③ {分野番号，表示順} → 電子会議番号
④ 電子会議番号 → {分野番号，表示順}
⑤ 電子会議番号 → 作成者ユーザID
⑥ {電子会議番号，投稿番号} → 投稿本文，投稿者ユーザID
⑦ 電子会議番号 → 分野番号

(1) 部分関数従属性の検討

ここから部分関数従属性を考えるとき、DBSP教科書では『他の候補キーの一部になっている場合は、部分関数従属性ではない』とし、以下について部分関数従属性が無いと判断していました。
・④は｛分野番号，表示順｝が他の候補キーの一部になっている
・⑦は分野番号が他の候補キーの一部になっている
これはDBSP教科書の説明と一致しています。

一方、RDB入門では「部分関数従属性」の定義を与えていませんが、[定義4.4] より部分関数従属性を「関数従属性 X → Y で、X の任意の真部分集合 X' (X' ⊂ X) について X' → Y が成立するとき」とするならば、④⑦も部分関数従属性といえます。なぜなら、この定義では「他の候補キーの一部になっていないこと」という制限が含まれていないからです。

残念ながらIPAの解答例からはどちらが妥当であるかを判断できませんでした。解答例は部分関数従属性の具体例を一つ示しているのみであり、今回の妥当性の判断には使えないためです。

(2) 推移的関数従属性の検討

IPAの解答例は「電子会議番号 → 分野番号 → 分野名」となっていました。

RDB入門及びDBSP教科書の定義とは矛盾ありません。

一方、DBSP教本の定義と比較すると、"分野番号" は候補キーの一部（つまり非キー属性ではない）なので、定義内の前提とは矛盾しています。このことについてDBSP教本の解説では触れられていませんでした。

定義の違いに対する考察

定義の妥当性

私の見解になりますが、RDB入門の定義が最も妥当に思われます。弱い根拠ではありますが、以下の2点を挙げます。

(1) Wikipedia の「関数従属性」の定義

「関係の正規化」の「第2正規形」の説明を引用します。

A及びBを属性または属性の集合としたとき、「AがBに関数従属する」とは、Bの値を決めると、常にAの値が一つに定まるような性質をAが有することをいい、これをB → Aと書く。矢印の左側、つまりここでのBのことを決定項、右側、つまりここでのAのことを従属項という。属性の集合は { } で括る。（なお、A → A、{A, B} → A のように、従属項と決定項が同じか、従属項が決定項に含まれる属性だけからなる場合を自明な関数従属といい、以下の説明では関数従属から自明な関数従属を除く。）
＜中略＞
複数の属性からなる決定項のうち一部の属性にも関数従属することを部分（関数）従属（性）といい、複数の属性からなる決定項に関数従属するが部分従属はしないことを完全（関数）従属（性）という。つまり、決定項に「余分な属性」がない場合が完全従属である。

関係の正規化 - Wikipedia

このWikipediaの説明はRDB入門の定義と一致しています。

(2) 第2正規形の定義

RDB入門における第2正規形の定義を再度引用します。

[定義4.11]リレーション R が第2正規形であるとは次の2つの条件を満たすときをいう。
(1) R は第1正規形である。
(2) R の全ての非キー属性は R の各候補キーに完全関数従属している。

この定義はDBSP教科書やDBSP教本でも同様です。

ここで (2) に注目すると、もし完全関数従属の定義に候補キー・非キー属性の制限を含めているのであれば、(2) は「Rが完全関数従属であること」とするだけで済んだはずです。そうしていないということは、完全関数従属性の純粋な定義には候補キー・非キー属性の制限が無いと考えました。

定義が相違した背景の推測

DBSP教科書やDBSP教本の定義がRDB入門と相違した理由ですが、正規化理論を前提に完全関数従属性及び推移的関数従属性を定義したからではないかと推測しています。例えば、RDB入門の [定義4.4] と [定義4.11](2) を合わせれば、DBSP教科書における完全関数従属性の定義を導けます。

よって、部分関数従属性及び推移的関数従属性の定義自体には候補キー・非キー属性の制限はないが、第2正規形及び第3正規形を検討するうえでは候補キー・非キー属性を考慮する必要がある、という理解でよいのではないかと考えています。

おわりに

本件についてDBSP教科書及びDBSP教本の出版社に対し質問してみましたが、回答をいただくことができませんでした。おそらく、「記載の内容を超える」ため回答できないと判断されたと思われます。確認できなかったことは残念ですが、致し方ないことだと理解しています。

今後、新たな知見が得られれば、記事を更新します。