はじめに
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 以降は結果が同じになるはずだからです。
