ぱと隊長日誌

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

PostgreSQL の join_collapse_limit がプランナに与える影響

はじめに

PostgreSQL の join_collapse_limit の説明をマニュアルから引用します。

join_collapse_limit (integer)
最終的にリストがこの項目数以下になる時、プランナは、明示的なJOIN構文(FULL JOINを除く)をFROM項目のリストに直します。 この値を小さくすれば計画作成時間は減少しますが、劣った問い合わせ計画が作成される可能性があります。

20.7. 問い合わせ計画

ですが、この記述からは join_collapse_limit がプランナに与える影響をイメージできませんでした。そこで、実験から推測を行いました。

PostgreSQL 14.5 をベースに調査しました。
また、src/backend/optimizer/README を参考にしました。

平坦化

SELECT * FROM A, B, C; の結合関係を {A B C} のように表現するとします。この時、A と B を結合してから C と結合しても、B と C を結合してから A を結合しても、論理的には同じです。

明示的な JOIN 句があると「平坦化」という処理が行われます。これについて明確な説明はありませんが、マニュアルの「14.3. 明示的なJOIN句でプランナを制御する」を参考に推測すると、以下の処理を行うようです。

SELECT * FROM A CROSS JOIN B CROSS JOIN C;
 ↓
SELECT * FROM A, B, C;

このように平坦化したうえでプランナーが最適な結合順を判断します。

join_collapse_limit

PostgreSQL は明示的な JOIN 句の全てを平坦化するわけではありません。ここで join_collapse_limit が効いてきます。

以下のクエリで考えます。

SELECT * FROM A CROSS JOIN B CROSS JOIN C CROSS JOIN D CROSS JOIN E WHERE ...;

join_collapse_limit = 8(デフォルト)であれば {A B C D E} は5個なので、JOIN 句は全て平坦化されます。

ですが、join_collapse_limit = 3 に設定すると、JOIN 句は3個までしか平坦化できません。その結果として結合関係が {A B C},{C D E} のように分割されます。結合関係は分割されましたが、この例は C で結合されていることに注意してください。そして、プランナーはそれぞれの結合関係で最適な結合順を判断します。

結合関係が分割される、ということは src/backend/optimizer/README の "Join Tree Construction" の記述から解釈しました。

以下のテストデータで実際の挙動を確認します。

CREATE TABLE tab1 (id integer);
CREATE TABLE tab2 (id integer);
CREATE TABLE tab3 (id integer);
CREATE TABLE tab4 (id integer);
CREATE TABLE tab5 (id integer);

INSERT INTO tab1 SELECT generate_series(1, 1*1000);
INSERT INTO tab2 SELECT generate_series(1, 2*1000);
INSERT INTO tab3 SELECT generate_series(1, 3*1000);
INSERT INTO tab4 SELECT generate_series(1, 4*1000);
INSERT INTO tab5 SELECT generate_series(1, 5*1000);

VACUUM ANALYZE;

単純な CROSS JOIN

テーブルを CROSS JOIN で結合し、結合条件は指定しません。join_collapse_limit と結合順の関係を確認します。

SET join_collapse_limit = 8;

EXPLAIN SELECT * FROM tab5 CROSS JOIN tab4 CROSS JOIN tab3 CROSS JOIN tab2 CROSS JOIN tab1;
                                      QUERY PLAN
--------------------------------------------------------------------------------------
 Nested Loop  (cost=0.00..1500300075025251.50 rows=120000000000000000 width=20)
   ->  Nested Loop  (cost=0.00..300075025166.00 rows=24000000000000 width=16)
         ->  Nested Loop  (cost=0.00..75025098.00 rows=6000000000 width=12)
               ->  Nested Loop  (cost=0.00..25046.50 rows=2000000 width=8)
                     ->  Seq Scan on tab2  (cost=0.00..29.00 rows=2000 width=4)
                     ->  Materialize  (cost=0.00..20.00 rows=1000 width=4)
                           ->  Seq Scan on tab1  (cost=0.00..15.00 rows=1000 width=4)
               ->  Materialize  (cost=0.00..59.00 rows=3000 width=4)
                     ->  Seq Scan on tab3  (cost=0.00..44.00 rows=3000 width=4)
         ->  Materialize  (cost=0.00..78.00 rows=4000 width=4)
               ->  Seq Scan on tab4  (cost=0.00..58.00 rows=4000 width=4)
   ->  Materialize  (cost=0.00..98.00 rows=5000 width=4)
         ->  Seq Scan on tab5  (cost=0.00..73.00 rows=5000 width=4)
(13 rows)

結果を下表に示します。

join_collapse_limit 結合順
1 tab4, tab5, tab3, tab2, tab1
2 tab4, tab5, tab3, tab2, tab1
3 tab3, tab4, tab5, tab1, tab2
4 tab2, tab3, tab4, tab5, tab1
5 tab1, tab2, tab3, tab4, tab5
8 tab1, tab2, tab3, tab4, tab5

join_collapse_limit = 8 の結果から、結合順は tab1, tab2, tab3, tab4, tab5 が最適であるとわかります。

join_collapse_limit = 3 の結果に至った理由を推察します。この時、結合関係は {tab5 tab4 tab3}, {tab3 tab2 tab1} となっていたと思われます。そして、各結合関係で最適な結合順に並び替えると(join_collapse_limit = 8 の結果を参考にできます)、{tab3 tab4 tab5}, {tab1 tab2 tab3} となります。各結合順を踏まえて最終的に {tab3 tab4 tab5 tab1 tab2} になったと考えられます。

join_collapse_limit = 4 の結果についても推察します。この時、結合関係は {tab5 tab4 tab3 tab2}, {tab4 tab3 tab2 tab1} になっていたと思われます。各結合関係で最適な結合順に並び替えると {tab2 tab3 tab4 tab5}, {tab1 tab2 tab3 tab4} となり、最終的に {tab2 tab3 tab4 tab5 tab1} になりました。

WHERE 句で結合条件を指定する

テーブルを CROSS JOIN で結合し、結合条件を指定します。join_collapse_limit と結合順の関係を確認します。

SET join_collapse_limit = 3;

EXPLAIN SELECT * FROM tab5 CROSS JOIN tab4 CROSS JOIN tab3 CROSS JOIN tab2 CROSS JOIN tab1 WHERE tab5.id = tab4.id AND tab4.id = tab3.id AND tab3.id = tab2.id AND tab2.id = tab1.id;

                                            QUERY PLAN
--------------------------------------------------------------------------------------------------
 Hash Join  (cost=385.05..423.47 rows=192 width=20)
   Hash Cond: (tab2.id = tab5.id)
   ->  Seq Scan on tab2  (cost=0.00..29.00 rows=2000 width=4)
   ->  Hash  (cost=379.05..379.05 rows=480 width=16)
         ->  Hash Join  (cost=268.25..379.05 rows=480 width=16)
               Hash Cond: (tab5.id = tab1.id)
               ->  Hash Join  (cost=240.75..337.75 rows=2400 width=12)
                     Hash Cond: (tab4.id = tab5.id)
                     ->  Seq Scan on tab4  (cost=0.00..58.00 rows=4000 width=4)
                     ->  Hash  (cost=203.25..203.25 rows=3000 width=8)
                           ->  Hash Join  (cost=81.50..203.25 rows=3000 width=8)
                                 Hash Cond: (tab5.id = tab3.id)
                                 ->  Seq Scan on tab5  (cost=0.00..73.00 rows=5000 width=4)
                                 ->  Hash  (cost=44.00..44.00 rows=3000 width=4)
                                       ->  Seq Scan on tab3  (cost=0.00..44.00 rows=3000 width=4)
               ->  Hash  (cost=15.00..15.00 rows=1000 width=4)
                     ->  Seq Scan on tab1  (cost=0.00..15.00 rows=1000 width=4)
(17 rows)

この時の結合順は tab3, tab5, tab4, tab1, tab2 でした。これが先の考え方で説明できるかを確認します。

結合関係は {tab5 tab4 tab3}, {tab5 tab2 tab1} となっていたと思われます。それぞれで最適な結合順を実行計画で確認します。結合条件は先の実行計画を参考にしました。

SET join_collapse_limit = 8;

-- {tab5 tab4 tab3} の結合順
EXPLAIN SELECT * FROM tab5, tab4, tab3 WHERE tab5.id = tab3.id AND tab4.id = tab5.id;
                                   QUERY PLAN
--------------------------------------------------------------------------------
 Hash Join  (cost=240.75..337.75 rows=2400 width=12)
   Hash Cond: (tab4.id = tab5.id)
   ->  Seq Scan on tab4  (cost=0.00..58.00 rows=4000 width=4)
   ->  Hash  (cost=203.25..203.25 rows=3000 width=8)
         ->  Hash Join  (cost=81.50..203.25 rows=3000 width=8)
               Hash Cond: (tab5.id = tab3.id)
               ->  Seq Scan on tab5  (cost=0.00..73.00 rows=5000 width=4)
               ->  Hash  (cost=44.00..44.00 rows=3000 width=4)
                     ->  Seq Scan on tab3  (cost=0.00..44.00 rows=3000 width=4)
(9 rows)

-- {tab5 tab2 tab1} の結合順
EXPLAIN SELECT * FROM tab5, tab2, tab1 WHERE tab5.id = tab1.id AND tab2.id = tab5.id;
                                   QUERY PLAN
--------------------------------------------------------------------------------
 Hash Join  (cost=141.75..182.25 rows=400 width=12)
   Hash Cond: (tab2.id = tab5.id)
   ->  Seq Scan on tab2  (cost=0.00..29.00 rows=2000 width=4)
   ->  Hash  (cost=129.25..129.25 rows=1000 width=8)
         ->  Hash Join  (cost=27.50..129.25 rows=1000 width=8)
               Hash Cond: (tab5.id = tab1.id)
               ->  Seq Scan on tab5  (cost=0.00..73.00 rows=5000 width=4)
               ->  Hash  (cost=15.00..15.00 rows=1000 width=4)
                     ->  Seq Scan on tab1  (cost=0.00..15.00 rows=1000 width=4)
(9 rows)

EXPLAIN の結果から、各結合関係で最適な結合順に並び替えると、{tab3 tab5 tab4}, {tab1 tab5 tab2} となりました。各結合順を踏まえつつ全体を結合すると、最終的に {tab3 tab5 tab4 tab1 tab2} となり、先の EXPLAIN 結果と一致しました。

同じテーブルを指定する

同じテーブルを別名で指定した時、結合順の判定でどのように扱われるのかを確認しました。

SET join_collapse_limit = 8;

EXPLAIN SELECT * FROM tab3 AS tab3a CROSS JOIN tab3 AS tab3b CROSS JOIN tab2 AS tab2a CROSS JOIN tab2 AS tab2b CROSS JOIN tab1 as tab1a CROSS JOIN tab1 as tab1b;
                                            QUERY PLAN
--------------------------------------------------------------------------------------------------
 Nested Loop  (cost=0.00..450150050025012736.00 rows=36000000000000000000 width=24)
   ->  Nested Loop  (cost=0.00..150050025012652.00 rows=12000000000000000 width=20)
         ->  Nested Loop  (cost=0.00..50025012600.50 rows=4000000000000 width=16)
               ->  Nested Loop  (cost=0.00..25012566.50 rows=2000000000 width=12)
                     ->  Nested Loop  (cost=0.00..12532.50 rows=1000000 width=8)
                           ->  Seq Scan on tab1 tab1a  (cost=0.00..15.00 rows=1000 width=4)
                           ->  Materialize  (cost=0.00..20.00 rows=1000 width=4)
                                 ->  Seq Scan on tab1 tab1b  (cost=0.00..15.00 rows=1000 width=4)
                     ->  Materialize  (cost=0.00..39.00 rows=2000 width=4)
                           ->  Seq Scan on tab2 tab2a  (cost=0.00..29.00 rows=2000 width=4)
               ->  Materialize  (cost=0.00..39.00 rows=2000 width=4)
                     ->  Seq Scan on tab2 tab2b  (cost=0.00..29.00 rows=2000 width=4)
         ->  Materialize  (cost=0.00..59.00 rows=3000 width=4)
               ->  Seq Scan on tab3 tab3a  (cost=0.00..44.00 rows=3000 width=4)
   ->  Materialize  (cost=0.00..59.00 rows=3000 width=4)
         ->  Seq Scan on tab3 tab3b  (cost=0.00..44.00 rows=3000 width=4)
(16 rows)
join_collapse_limit 結合順
1 tab3b, tab3a, tab2a, tab2b, tab1a, tab1b
2 tab3b, tab3a, tab2a, tab2b, tab1a, tab1b
3 tab2a, tab3a, tab3b, tab1a, tab2b, tab1b
4 tab2b, tab2a, tab3a, tab3b, tab1a, tab1b
5 tab1a, tab2a, tab2b, tab3a, tab3b, tab1b
6 tab1b, tab1a, tab2a, tab2b, tab3a, tab3b
8 tab1b, tab1a, tab2a, tab2b, tab3a, tab3b

同じテーブルを別名で指定した時、それらは別々のテーブルとして結合順が判定されるようです。もし同じテーブルを重複してカウントしないとすれば、join_collapse_limit = 3 以降は結果が同じになるはずだからです。

まとめ

ソースコードと実際の挙動をトレースしたわけではないため、実験結果からの推測にずれがあるかもしれません。ですが、join_collapse_limit がどのような働きをしているかを概念的につかむことができたのではないでしょうか。

join_collapse_limit の使い方として、postgresql.conf ではデフォルトを指定し、JOIN 句の結合順序を明示的に指定したい場合のみ都度 SET join_collapse_limit = 1; とする、というのが良いと思われます。