ぱと隊長日誌

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

PostgreSQL の結合テーブル数と計画時間の関係

データベース アーキテクチャ

概要

PostgreSQL のマニュアルには以下の記載があります。

結合の対象がせいぜい2、3個のテーブルなら心配するほど結合の種類は多くありません。 しかし、テーブル数が増えると可能な結合の数は指数関数的に増えていきます。 10程度以上にテーブルが増えると、すべての可能性をしらみつぶしに探索することはもはや実用的ではなくなります。 6や7個のテーブルでさえも、計画を作成する時間が無視できなくなります。

https://www.postgresql.jp/document/14/html/explicit-joins.html

これが実際どの程度なのか、PostgreSQL の結合テーブル数と計画時間の関係を調べてみました。

検証

検証環境

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

ホスト
プロセッサ Intel Core i5-6600 CPU @ 3.30GHz
メモリ 20.0 GB
SSD SanDisk SDSSDH3
OS Windows 10 Pro バージョン 21H2
Hyper-V
プロセッサ 4個の仮想プロセッサ
メモリ 8.0 GB
OS Red Hat Enterprise Linux release 8.6
DB PostgreSQL 14.5
PostgreSQL

ソースコードからインストールし、デフォルト設定のままとしました。

検証方法

計画時間には以下の項目が影響すると想定しました。

  • 結合テーブル数
  • 結合方式
  • 遺伝的問い合わせ最適化 (GEQO)

そこで、以下の条件を組み合わせて検証しました。()内は本記事内での表記です。

  • 結合テーブル数を 2 ～ 20 で変化させる
  • FROM 句の記載
    • 単純に並べる (list)
    • CROSS JOIN で結合 (cross)
  • WHERE 句の結合条件有無
    • 無し (only)
    • 有り (where)

各条件のクエリを EXPLAIN (SUMMARY) で 5 回測定し、Planning Time の中央値を採用しました。

実験に用いたスクリプトを抜粋します。

CREATE TABLE tab1 (id integer);
CREATE TABLE tab2 (id integer);
（省略）
CREATE TABLE tab20 (id integer);

INSERT INTO tab1 SELECT generate_series(1, 1*1000);
INSERT INTO tab2 SELECT generate_series(1, 2*1000);
（省略）
INSERT INTO tab20 SELECT generate_series(1, 20*1000);

VACUUM ANALYZE;

-- list_only
EXPLAIN (SUMMARY) SELECT * FROM tab1, tab2;
EXPLAIN (SUMMARY) SELECT * FROM tab1, tab2, tab3;
（省略）
EXPLAIN (SUMMARY) SELECT * FROM tab1, tab2, tab3, ... , tab20;

-- list_where
EXPLAIN (SUMMARY) SELECT * FROM tab1, tab2 WHERE tab1.id = tab2.id;
EXPLAIN (SUMMARY) SELECT * FROM tab1, tab2, tab3 WHERE tab1.id = tab2.id AND tab2.id = tab3.id;
（省略）
EXPLAIN (SUMMARY) SELECT * FROM tab1, tab2, tab3, ... , tab20 WHERE tab1.id = tab2.id AND tab2.id = tab3.id ... AND tab19.id = tab20.id;

-- cross_only
EXPLAIN (SUMMARY) SELECT * FROM tab1 CROSS JOIN tab2;
EXPLAIN (SUMMARY) SELECT * FROM tab1 CROSS JOIN tab2 CROSS JOIN tab3;
（省略）
EXPLAIN (SUMMARY) SELECT * FROM tab1 CROSS JOIN tab2 CROSS JOIN tab3 ... CROSS JOIN tab20;

-- cross_where
EXPLAIN (SUMMARY) SELECT * FROM tab1 CROSS JOIN tab2 WHERE tab1.id = tab2.id;
EXPLAIN (SUMMARY) SELECT * FROM tab1 CROSS JOIN tab2 CROSS JOIN tab3 WHERE tab1.id = tab2.id AND tab2.id = tab3.id;
（省略）
EXPLAIN (SUMMARY) SELECT * FROM tab1 CROSS JOIN tab2 CROSS JOIN tab3 ... CROSS JOIN tab20 WHERE tab1.id = tab2.id AND tab2.id = tab3.id ... AND tab19.id = tab20.id;

検証結果

テーブル数と計画時間（計画時間は対数スケール）
＜図1　テーブル数と計画時間（計画時間は対数スケール）＞

テーブル数と計画時間
＜図2　テーブル数と計画時間＞
※ list_where は計画時間が大きすぎるため、省略しています。

階乗のグラフ（片対数グラフ）
＜図3　階乗のグラフ（片対数グラフ）＞

結合テーブル数が増えるほど、計画時間は増えます。結合テーブル数を n としたとき、結合順の候補数は n! となります。よって、計画時間も n! に比例すると考えられます。図1と図3がよく似ていることからもこれを裏付けています。

テーブル数が 8 以下の時は list と cross で計画時間の差異がありません。このことから、結合の平坦化処理にかかる時間は無視できるほど小さいといえます。

テーブル数が 8 を超えると、cross の計画時間増加がいったん落ち着きます。これは結合の平坦化処理を行うテーブル数を制限する join_collapse_limit のデフォルトが 8 であることに起因していると考えられます。

以前の記事で join_collapse_limit の挙動を考察しました。
PostgreSQL の join_collapse_limit がプランナに与える影響 - ぱと隊長日誌
ここで、join_collapse_limit = 3 であれば、JOIN 句は 3 個までしか平坦化されないため、結合関係が {A B C},{C D E} のように分割される。また、プランナーはそれぞれの結合関係で最適な結合順を判断するとしました。

結合関係が分割されたことで検討すべき結合順候補数の違いとなり、計画時間の違いになったと考えています。

なお、cross の計画時間増加の変化がテーブル数 8 の次は 15 で同様に現れています。これも結合関係の分割に起因しているのではないかと推測しています。join_collapse_limit = 8 で各結合関係が 8 までしかテーブルを扱えないとすれば、下記のようになるからです。
{tab1 tab2 ... tab8} {tab8 tab9 ... tab15}

list の場合はテーブル数が 12 になると計画時間が減少しています。これは GEQO 発動のテーブル数を設定している geqo_threshold のデフォルトが 12 であることに起因していると考えられます。つまり、テーブル数が 12 以上になると GEQO に切り替わり、計画時間の減少に寄与しました。

cross の場合はテーブル数が 12 以上でも計画時間の減少は見られません。これは join_collapse_limit = 8 で結合の平坦化が 8 個までに制限されているため、各結合関係が GEQO 発動条件に合致しなかったためと考えられます。

結合条件の有無（only と where）で比較すると、計画時間は only < where となっています。only であれば単なる直積であるため、Nested Loop と Seq Scan の組み合わせだけ考えることになります。ですが、where のように結合条件が加わると、Hash Join なども検討することになり、計画に時間がかかったと推測されます。

マニュアルでも結合の計画に時間がかかることを示唆しています。

リレーショナル演算子の中で、処理と最適化が一番難しいのは結合です。 実行可能な問い合わせ計画の数は問い合わせの中に含まれる結合の数によって指数関数的に増加します。 個々の結合や、多様なインデックス（例えばPostgreSQLのB-tree、ハッシュ、GiST、GINなど）をリレーションのアクセスパスとして処理するため、様々な結合メソッド（例えばPostgreSQLのネステッドループ、ハッシュ結合、マージ結合など）を提供することが、さらなる最適化を行わなければならない腐心の原因となっています。

60.1. 複雑な最適化問題としての問い合わせ処理

まとめ

結合テーブル数が増えるほど、計画時間は増えます。ただし、その増え方は join_collapse_limit, geqo_threshold といったパラメータの影響を受けます。

今回検証に用いた比較的シンプルなクエリであっても、テーブル数が 11 の時に 300 ms を超える計画時間となりました。計画時間と生成されるプランの質のバランスを考えた時、計画時間に関わるパラメータのデフォルト値はかなり妥当な設定といえるのかもしれません。