CREATE INDEX はなぜ速いのか(PostgreSQLで確認)
PostgreSQL に大量データを投入する際、INDEX 作成を後回しにして高速化するというテクニックがPostgreSQL ドキュメント: 14.4. データベースへのデータ投入で紹介されている。
試してみると確かに速いのだが、この速さの理由が気になったので調べた。
(2023/04/04 追記事項あり)
投入時間の確認
以下のようなテーブル定義とデータ投入スクリプトを使用した。
-- Table 定義
CREATE TABLE foo
(
id INTEGER NOT NULL,
code VARCHAR(6) NOT NULL
);
-- INDEX 定義
CREATE INDEX ON foo (code);
-- データの投入
INSERT INTO foo
SELECT i AS id,
('C' || lpad(CAST((random() * 10000)::integer AS text), 5, '0')) AS code
FROM generate_series(1, 100000000) AS s(i);
- 投入するデータは
generate_seriesを使って 1 億件生成 - INDEX 対象の
codeカラムに格納する値はrandomを使ってランダムに生成
INDEX 作成した状態で投入するのにかかった時間と、INDEX なしで投入した後に INDEX を作成した時間は以下。
| 投入方法 | 時間 | 補足 |
|---|---|---|
| INDEX なし | 2 m 38 s | INSERT と CREATE INDEX にかかった時間の合計 |
| INDEX あり | 6 m 41 s | CREATE INDEX は事前に実施しているので INSERT のみにかかった時間 |
※ローカル環境でそれぞれ 2 回実行した結果の平均値
→確かに INDEX 作成を後回しにするとかなり高速化できる
この時点での高速化理由の考察
B-Tree インデックスへの値の挿入は、①挿入箇所を特定、②データを挿入、③必要があればリーフからルートにかけてノードのスプリットを実施、というステップで実施される。
『詳説 データベース』の 「4章 Bツリーの実装」には、
ソート済みのデータをバルクロードするか、あるいは、たとえばデフラグのためにツリーを再構築する場合...(略)...ツリーの作成に必要なデータはすでにソートしてあるので、バルクロード中に行う必要があるのは、ツリーの右端の位置にアイテムを追加することだけです。この場合には、スプリットとマージを完全に避けて、ツリーをボトムアップ方式で構築できます。つまり、1 レベルごとに書き出したり、すでに書き込み済みの下位レベルのノードへのポイン タを十分に確保できたら、すぐに上位レベルのノードを書き出したりすることができます。
とあるものの、今回のケースでは INDEX 対象の code カラムの値はランダムであるため、特に工夫をしなければ INDEX を後からまとめて構築する場合でも INDEX のデータが格納されているストレージへのランダムなアクセスが発生して、あまり優位性が出ないはず。
ということを社内の Slack でつぶやいたところ同僚から「ソートしてからバルクロードしているから速いのでは？」というコメントをもらった。
確かに、外部ソートのために要するストレージアクセス数の方が、ランダムな値を挿入する際に発生するランダムアクセス数よりもかなり少なくなりそうではある。
PostgreSQL の CREATE INDEX の処理のソースを確認
上記はあくまで想像なので、実際にどうなっているのか確認するため PostgreSQL のソースを眺めたところ nbtsort.c というファイルを見つけた。
以下ファイルの Notes の抜粋(DeepL にて翻訳)
tuplesort.cを使用して、与えられたインデックスタプルを順番に並べ替え、インデックスタプルを順番にスキャンし、各レベルのbtreeページを構築
ということで、始めにソートするのは正解だった。
(2023/04/04 追記): また、『詳説 データベース』に記載されていた1レベルごとに B-Tree を構築する方法も実施されていそう
ページを完全に満杯にするのは賢明ではありません。そうすると、どんな挿入でも分割を引き起こすからです（そして、葉のページだけでなく、分割の必要性はツリーの右上に連鎖します）。 btreesの定常状態の負荷率は、通常70%と見積もられています。 私たちは、リーフページをユーザーが制御可能な充填率（デフォルトでは90%）まで詰め込み、上位ページは常に70%まで詰め込むことにしています。 これにより、初期挿入時に多くのカスケード分割のリスクを負うことなく、適度な密度（キーが適度な大きさであれば、上位ページはそれほど多くない）を得ることができます。
ノードの充填率は(右側限定の追加により)スプリットのオーバーヘッドを発生させずに制御できる。
(2023/04/04 追記): ここで充填率を制御しているのは、インデックス作成が終わった後に新たにレコードを追加する際に、即スプリットが発生することを防ぐためだと考えられる
以前は、構築されるインデックスページは共有バッファに保持されていましたが、これは何の価値もなく（他のバックエンドがまだそれに対して興味を持っていないため）、上位ページが長期間排他ロックされていたため、CHECKPOINTのロック問題が発生しました。 今、私たちはただローカルメモリにページを構築し、それを終えるときにsmgrwriteまたはsmgrextendします。 構築終了後の最初の使用時には、共有バッファに再読み込みする必要があります。
ソート以外にもこういったバッファの扱いについての工夫がされているとのこと。
結論
- 大量データを投入する際に INDEX 作成を後回しにすると速いのは、ソート済のデータ投入で利用できる高速化手法を使えるから
- ソート以外にもメモリ効率を上げるなどの工夫もされている
(認識間違いなどがあればコメントください)
(2023/04/04 追記): 統計情報の調査
今回投入したデータ量ではインデックスのデータはメモリに乗り切ってしまい、ストレージアクセスはあまり発生していない可能性があるため、PostgreSQL の統計情報を確認してみた。
統計情報
- データ投入前に取得した情報からの増分を表にまとめた
-
blk_read_time,blk_write_time,wal_write_timeの情報はデフォルトでは収集されないので conf でtrack_io_timing,track_wal_io_timingを on にした
-
- 「INDEXなし」はデータ投入後とINDEX作成後それぞれの実行時点での情報を記載
- 右端の「割合」列は、「INDEXあり」と「INDEXなし」の数値の割合をとったもの
- 「INDEXなし」の数値はINDEX作成後のものを使用
-
wal_write,wal_write_timeはデータ投入や INDEX 作成コマンドが完了してからも少しの間増加していた- 表にまとめた数値は一定時間置いて、増加が止まったあとのもの
- 少しの間増加し続けるのは、wal の書き込みが walwriter によって非同期で実施されているためだと思われる
統計情報確認結果の考察
- 「INDEXあり」の方が blks_read の回数が少なく、 blk の read, write にかかった時間も少なかった
- B-Tree 構築中にバッファプールが溢れてメモリからストレージに書き出されることはあまり発生していなさそう
- INDEX を後から作成する場合、投入したデータをメモリに読み出す必要があるので、その分ストレージアクセスが増えていそう
-
wal_recordsについては「INDEXあり」の方が多く、約2倍となっている
統計情報だけを見ていると「INDEXなし」の方が速い理由があまり読み取れなかった。blk_read, blk_write_time あたりは「INDEXあり」の方が少ないため、当初想定した「INDEX のデータが格納されているストレージへのランダムなアクセスが発生」は見当違いだった模様。
wal_records については「INDEXあり」の方が多く、これが性能に影響している可能性はある。PostgreSQL ドキュメント: 30.5. WALの設定には
チェックポイント処理は、全てのダーティデータページをディスクへフラッシュするため、大きなI/O負荷を発生させます。 チェックポイント処理においては、I/Oはチェックポイント開始時に始まり、次のチェックポイントが開始する前に完了するように調節されます。 これは、チェックポイント処理中の性能劣化を極力抑える効果があります。
サーバのチェックポインタプロセスは、自動的にチェックポイントを時々実行します。 checkpoint_timeout秒が経過するか、またはmax_wal_sizeに達するか、どちらかの条件が最初に満たされるとチェックポイントが開始されます。 デフォルトの設定では、それぞれ5分と1GBとなっています。
とあるため、wal_records の増加によってチェックポイント頻度が増えているといったことがあるのかもしれない。(ただディスクへのフラッシュが起こると blK_write_time などの指標に計上されるはずではある)
Discussion