Oracleのマニュアルで Bushy Join Tree と説明されてる図、Zigzag Join Treeだよね？、いわゆる、Bushy Join Tree は無いのか？ いいえ、あります！ Tweet
久々の技術ネタの投稿です。
昨年末のエントリーに軽くスルーしていた面白いネタが隠れていたのですが、気付いた方はどれぐいたでしょうか？ 多分、ぼぼ居ないだろうとは思いますがw
ということで、本日のお題は、軽くスルーしていた面白いネタとして、
Oracleでも、一般的に Bushy Join って言われているJoin Treeを生成することもできるのだ!
。。。というお話をしたいと思います。
Oracleのマニュアル( SQL Tuning Guide / Join - Oracle Database 23c )では、一応、Bushy Join Tree という記述をされているのですが、実際には、Zigzag Join Tree なんですよね。結合ツリーの図も実際の実行計画も。
一方、PostgreSQLでは、見間違えようながない Bushy Join Tree が生成されているのがわかります。
帰ってきた！ 標準はあるにはあるが癖の多いSQL #6 - Hash Joinの結合ツリーにも癖がでる
Oracleさんのマニュアルのリンク貼っても、リンク切れしちゃうので、いずれリンク切れしちゃう想定でマニュアルの図を手書きでw （といっても、 Pagesで書いたのですが）を貼っておきますね。
なお、本エントリーの後半に参考になりそうなリンクを貼っておきました。（Oracleさんのマニュアルリンクよりはリンク切れし難いと信じてw）
Oracleでは Zigzag も Bushy Join Tree のように扱われてるかのうように見えちゃいますが、実は、Bushy Join Tree に分類される結合ツリーは別に存在していたりします。
最近のOracleだとあまり目にする機会は無いように思いますが。。。特に、11g以降は見た記憶はないです。。。初期のOracleだと比較的目にしていたような気もしますが。（思い出せない！ それぐらい昔ではないかと。。。）
では、さっそく、冒頭で紹介した帰ってきた！ 標準はあるにはあるが癖の多いSQL #6 - Hash Joinの結合ツリーにも癖がでるの該当部分を再掲して確認してみましょう！
再掲
Oracle Database
SCOTT@orclpdb1> @ora_sql_hj.sql
1 SELECT
2 /*+
3 MONITOR
4 USE_HASH(t1 t2 t3 t4)
5 */
6 t1.id
7 , t1.t1_c1
8 , t2.s_id
9 , t2.t2_c1
10 , t3.b_id
11 , t3.t3_c1
12 , t4.a_id
13 , t4.c_id
14 , t4.t4_c1
15 FROM
16 t1
17 INNER JOIN t2
18 ON
19 t1.id = t2.id
20 INNER JOIN t3
21 ON
22 t1.id = t3.id
23 INNER JOIN t4
24 ON
25* t1.id = t4.id
...略...
SQL Plan Monitoring Details (Plan Hash Value=122725940)
===================================================================================================================================================
| Id | Operation | Name | Rows | Cost | Time | Start | Execs | Rows | Read | Read | Mem | Activity | Activity Detail |
| | | | (Estim) | | Active(s) | Active | | (Actual) | Reqs | Bytes | (Max) | (%) | (# samples) |
===================================================================================================================================================
| 0 | SELECT STATEMENT | | | | 1 | +0 | 1 | 25000 | | | . | | |
| 1 | HASH JOIN | | 25000 | 12 | 1 | +0 | 1 | 25000 | | | 1MB | | |
| 2 | TABLE ACCESS FULL | T4 | 500 | 3 | 1 | +0 | 1 | 500 | 2 | 49152 | . | | |
| 3 | HASH JOIN | | 500 | 9 | 1 | +0 | 1 | 500 | | | 1MB | | |
| 4 | HASH JOIN | | 50 | 6 | 1 | +0 | 1 | 50 | | | 1MB | | |
| 5 | TABLE ACCESS FULL | T1 | 10 | 3 | 1 | +0 | 1 | 10 | 2 | 49152 | . | | |
| 6 | TABLE ACCESS FULL | T2 | 50 | 3 | 1 | +0 | 1 | 50 | 2 | 49152 | . | | |
| 7 | TABLE ACCESS FULL | T3 | 100 | 3 | 1 | +0 | 1 | 100 | 2 | 49152 | . | | |
===================================================================================================================================================
ご覧のとおり、T1からT3までの結合はLeft Deep Join で、T4をRight Deep Joinで結合している、Zigzag Join Treeになっています（Oracleのマニュアルだと、Bushy Join Treeと記載されている結合ツリー）
では、PostgreSQLの Bushy Join Tree を再確認してみましょう。
PostgreSQL
perftestdb=> \! cat pg_sql_hj.sql
explain (analyze)
SELECT
/*+
HashJoin(t1 t2 t3 t4)
*/
t1.id
, t1.t1_c1
, t2.s_id
, t2.t2_c1
, t3.b_id
, t3.t3_c1
, t4.a_id
, t4.c_id
, t4.t4_c1
FROM
t1
INNER JOIN t2
ON
t1.id = t2.id
INNER JOIN t3
ON
t1.id = t3.id
INNER JOIN t4
ON
t1.id = t4.id
;
perftestdb=> \i pg_sql_hj.sql
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------
Id=1 Hash Join (cost=17.48..309.84 rows=25000 width=36) (actual time=3.405..10.466 rows=25000 loops=1)
Hash Cond: (t1.id = t2.id)
Id=2 -> Hash Join (cost=1.23..11.09 rows=500 width=24) (actual time=1.696..1.989 rows=500 loops=1)
Hash Cond: (t4.id = t1.id)
Id=3 -> Seq Scan on t4 (cost=0.00..8.00 rows=500 width=16) (actual time=0.907..0.993 rows=500 loops=1)
Id=4 -> Hash (cost=1.10..1.10 rows=10 width=8) (actual time=0.721..0.722 rows=10 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 9kB
Id=5 -> Seq Scan on t1 (cost=0.00..1.10 rows=10 width=8) (actual time=0.705..0.707 rows=10 loops=1)
Id=6 -> Hash (cost=10.00..10.00 rows=500 width=24) (actual time=1.687..1.687 rows=500 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 36kB
Id=7 -> Hash Join (cost=2.12..10.00 rows=500 width=24) (actual time=1.400..1.554 rows=500 loops=1)
Hash Cond: (t3.id = t2.id))
Id=8 -> Seq Scan on t3 (cost=0.00..2.00 rows=100 width=12) (actual time=0.701..0.712 rows=100 loops=1)
Id=9 -> Hash (cost=1.50..1.50 rows=50 width=12) (actual time=0.679..0.680 rows=50 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 11kB
Id=10 -> Seq Scan on t2 (cost=0.00..1.50 rows=50 width=12) (actual time=0.648..0.656 rows=50 loops=1)
上記はどちらも、HASH JOINをヒントで強制しているだけですが、それでも、オプティマイザの癖というか特徴は現れています。
ZigzagとBushyの違いと一口に言っちゃうと、簡単過ぎますが。
以下、SQL文の結合条件部分を抜粋してみました。赤字部分を注意深く見てください。
FROM
t1
INNER JOIN t2
ON
t1.id = t2.id
INNER JOIN t3
ON
t1.id = t3.id
INNER JOIN t4
ON
t1.id = t4.id
PostgreSQLのActual Planに見やすいよう、Idを振ってみました。
Id=7でINNER JOINしていますが、何が気づきませんか？ 特に、PostgreSQLの Bushy Join Tree で起きている変化に。。。（前述したSQLの赤字部分に注目）
私が実行したSQL文の結合条件と異なっている部分があります！ (内部でオプティマイザというかプランナが最適化のために書き換えた部分です)
結合条件を書き換え t1とt3ではなく、t2とt3を結合し、Bushy Join Tree で Hash Join されていますよね！！！！！(同意なのが自明なので書き換えているわけです。 Bushy Join Tree にするために)
一方、OracleもPostgreSQLとおなじタイプの Bushy Join Tree になることもあるのですが、このような書き換えは起こらなかったはず。。。
念の為、Oracleの結合条件が変化していないことをこの時点で確認しておきましょう。
PostgreSQL同様に、赤字部分に注目してください。SQLに記述されている結合条件のまま。
1 EXPLAIN PLAN FOR
2 SELECT
3 /*+
4 MONITOR
5 USE_HASH(t1 t2 t3 t4)
6 */
7 t1.id
8 , t1.t1_c1
9 , t2.s_id
10 , t2.t2_c1
11 , t3.b_id
12 , t3.t3_c1
13 , t4.a_id
14 , t4.c_id
15 , t4.t4_c1
16 FROM
17 t1
18 INNER JOIN t2
19 ON
20 t1.id = t2.id
21 INNER JOIN t3
22 ON
23 t1.id = t3.id
24 INNER JOIN t4
25 ON
26* t1.id = t4.id
解析されました。
経過: 00:00:00.02
PLAN_TABLE_OUTPUT
-----------------------------------------------------------------------------
Plan hash value: 122725940
-----------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
-----------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 25000 | 878K| 12 (0)| 00:00:01 |
|* 1 | HASH JOIN | | 25000 | 878K| 12 (0)| 00:00:01 |
| 2 | TABLE ACCESS FULL | T4 | 500 | 6000 | 3 (0)| 00:00:01 |
|* 3 | HASH JOIN | | 500 | 12000 | 9 (0)| 00:00:01 |
|* 4 | HASH JOIN | | 50 | 750 | 6 (0)| 00:00:01 |
| 5 | TABLE ACCESS FULL| T1 | 10 | 60 | 3 (0)| 00:00:01 |
| 6 | TABLE ACCESS FULL| T2 | 50 | 450 | 3 (0)| 00:00:01 |
| 7 | TABLE ACCESS FULL | T3 | 100 | 900 | 3 (0)| 00:00:01 |
-----------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
1 - access("T1"."ID"="T4"."ID")
3 - access("T1"."ID"="T3"."ID")
4 - access("T1"."ID"="T2"."ID")
では、Oracleには、PostgreSQLで見られる Bushy Join Tree は存在しないのか？
冒頭でも書きましたが、存在します！
BUSHY_JOINヒントまでありますw
ほぼ、お目にかかることは無くなった気がしますが。。。最近は。。
PostgreSQLとおなじ実行計画になるように、ゴニョゴニョしてみましたw （何が起こるでしょう。。。w）
なお、LEADINGヒントで、オプティマイザが内部的に生成する Bushy Join 向けのインラインビュー（ VW_BUSHY_0C91E486 ）を指定していますが、このインラインビュー名は事前に確認することはできないので、一度、インラインビューを生成させインラインビュー名を確認した後に指定しています。
（内部的に生成されるインラインビュー名称なので、手順としてはそれしかありません！）
BUSHY_JOINヒント、なんとなく、pg_hint_plan で使うような構文に似てますよねw Oracleで ZigZag Join Tree (Oracleのマニュアルだと Zigzag な Tree だけど、Bushy Join となっているので注意)になっている状態を BUSHY_JOINヒントで あえて、Bushy Join に書き換えることは無いと思いますが、使い方を理解していると、何かの役になる、、、かも。（なるとは言ってないw）
SCOTT@orclpdb1> @ora_sql_hj_bushy_join
1 SELECT
2 /*+
3 MONITOR
4 LEADING(VW_BUSHY_0C91E486)
5 USE_HASH(t2 t3)
6 USE_HASH(t1 t4)
7 BUSHY_JOIN((t2 t3) (t1 t4))
8 */
9 t1.id
10 , t1.t1_c1
11 , t2.s_id
12 , t2.t2_c1
13 , t3.b_id
14 , t3.t3_c1
15 , t4.a_id
16 , t4.c_id
17 , t4.t4_c1
18 FROM
19 t1
20 INNER JOIN t2
21 ON
22 t1.id = t2.id
23 INNER JOIN t3
24 ON
25 t1.id = t3.id
26 INNER JOIN t4
27 ON
28* t1.id = t4.id
DBMS_SQLTUNE.REPORT_SQL_MONITOR(SQL_ID=>'',TYPE=>'TEXT')
-------------------------------------------------------------------------------------
SQL Monitoring Report
...略...
SQL Plan Monitoring Details (Plan Hash Value=3887185)
===================================================================================================================================================
| Id | Operation | Name | Rows | Cost | Time | Start | Execs | Rows | Mem | Activity | Activity Detail |
| | | | (Estim) | | Active(s) | Active | | (Actual) | (Max) | (%) | (# samples) |
===================================================================================================================================================
| 0 | SELECT STATEMENT | | | | 3 | +0 | 1 | 25000 | . | | |
| 1 | HASH JOIN | | 250K | 80 | 3 | +0 | 1 | 25000 | 2MB | | |
| 2 | VIEW | VW_BUSHY_0C91E486 | 5000 | 72 | 1 | +0 | 1 | 5000 | . | | |
| 3 | MERGE JOIN CARTESIAN | | 5000 | 72 | 1 | +0 | 1 | 5000 | . | | |
| 4 | TABLE ACCESS FULL | T2 | 50 | 3 | 1 | +0 | 1 | 50 | . | | |
| 5 | BUFFER SORT | | 100 | 69 | 1 | +0 | 50 | 5000 | 6144 | | |
| 6 | TABLE ACCESS FULL | T3 | 100 | 1 | 1 | +0 | 1 | 100 | . | | |
| 7 | VIEW | VW_BUSHY_CF941F82 | 500 | 6 | 3 | +0 | 1 | 500 | . | | |
| 8 | HASH JOIN | | 500 | 6 | 3 | +0 | 1 | 500 | 1MB | | |
| 9 | TABLE ACCESS FULL | T1 | 10 | 3 | 1 | +0 | 1 | 10 | . | | |
| 10 | TABLE ACCESS FULL | T4 | 500 | 3 | 3 | +0 | 1 | 500 | . | | |
===================================================================================================================================================
PostgreSQLのように結合条件を書き換えてくれるまでは行わないようですね。Oracleのオプティマイザでは。
MERGE JOIN CARTESIAN となって、直積が発生してしまいました。PostgreSQLのように結合条件を書き換えていない結果として、結合条件の無い結合の強制となってしまった結果、直積が発生したわけです。
であれば、オリジナルの結合条件を書き換えて、それっぽくなるようにしてみましょう！
PostgreSQLのプランナのように結合条件を書き換えて再実行！！。
おお！
思い通りの実行計画になりました！
このような箇所でもオプティマイザの特徴は現れるので注意したいですね。Oracleでこの形にしたくなることは無いとは思いますけども。
ちなみに、Oracleのオプティマイザが内部的に、インラインビューを作る場合、どうやらネーミングルールがあるようで（マニュアルには記載されていないですけどもw）
VW_BUSHY_xxxxxxx となっている場合は、Bushy Join を行うためのインラインビュー名であるということは知られています
（知らない方もおおいかもしれませんが。Internal Views / Oracle Scratchpad by Jonathan Lewisあたりでそこそこまとめられていますが、Bushy Joinのためのはリストされてないですが、知らなくても困らないとは思います。OracleのBusy Join自体が現状はかなりレアな存在なので）
1 SELECT
2 /*+
3 MONITOR
4 LEADING(VW_BUSHY_0C91E486)
5 USE_HASH(t2 t3)
6 USE_HASH(t1 t4)
7 BUSHY_JOIN((t2 t3) (t1 t4))
8 */
9 t1.id
10 , t1.t1_c1
11 , t2.s_id
12 , t2.t2_c1
13 , t3.b_id
14 , t3.t3_c1
15 , t4.a_id
16 , t4.c_id
17 , t4.t4_c1
18 FROM
19 t1
20 INNER JOIN t2
21 ON
22 t1.id = t2.id
23 INNER JOIN t3
24 ON
25 t2.id = t3.id
26 INNER JOIN t4
27 ON
28* t1.id = t4.id
DBMS_SQLTUNE.REPORT_SQL_MONITOR(SQL_ID=>'',TYPE=>'TEXT')
----------------------------------------------------------------------------------------------------
SQL Monitoring Report
SQL Text
...略...
SQL Plan Monitoring Details (Plan Hash Value=400336061)
=================================================================================================================================================
| Id | Operation | Name | Rows | Cost | Time | Start | Execs | Rows | Mem | Activity | Activity Detail |
| | | | (Estim) | | Active(s) | Active | | (Actual) | (Max) | (%) | (# samples) |
=================================================================================================================================================
| 0 | SELECT STATEMENT | | | | 3 | +0 | 1 | 25000 | . | | |
| 1 | HASH JOIN | | 25000 | 12 | 3 | +0 | 1 | 25000 | 1MB | | |
| 2 | VIEW | VW_BUSHY_0C91E486 | 500 | 6 | 1 | +0 | 1 | 500 | . | | |
| 3 | HASH JOIN | | 500 | 6 | 1 | +0 | 1 | 500 | 1MB | | |
| 4 | TABLE ACCESS FULL | T2 | 50 | 3 | 1 | +0 | 1 | 50 | . | | |
| 5 | TABLE ACCESS FULL | T3 | 100 | 3 | 1 | +0 | 1 | 100 | . | | |
| 6 | VIEW | VW_BUSHY_CF941F82 | 500 | 6 | 3 | +0 | 1 | 500 | . | | |
| 7 | HASH JOIN | | 500 | 6 | 3 | +0 | 1 | 500 | 1MB | | |
| 8 | TABLE ACCESS FULL | T1 | 10 | 3 | 1 | +0 | 1 | 10 | . | | |
| 9 | TABLE ACCESS FULL | T4 | 500 | 3 | 3 | +0 | 1 | 500 | . | | |
=================================================================================================================================================
Oracleでも、一般的に言われている Bushy Join Tree へ持っていくことはできるよ。あえて使わないけど、というかこれに持っていきたい時って想像できないわけですけどもね。Zigzag Join Treeで対応しちゃうだろうから。。。
ということで、Oracleでかなり久々に見た（無理やりですけどもw）、Bushy Join Tree もあるんだよ！ の巻。完。。
今回使ったスクリプト
Oracle(PostgreSQLと同じ実行計画になるよう結合条件を書き換え,内部生成されるインラインビュー名称を確認した上で、LEADINGで結合順を聖書したもの)
SCOTT@orclpdb1> ! cat ora_sql_hj_bushy_join.sql
SELECT
/*+
MONITOR
LEADING(VW_BUSHY_0C91E486)
USE_HASH(t2 t3)
USE_HASH(t1 t4)
BUSHY_JOIN((t2 t3) (t1 t4))
*/
t1.id
, t1.t1_c1
, t2.s_id
, t2.t2_c1
, t3.b_id
, t3.t3_c1
, t4.a_id
, t4.c_id
, t4.t4_c1
FROM
t1
INNER JOIN t2
ON
t1.id = t2.id
INNER JOIN t3
ON
t2.id = t3.id
INNER JOIN t4
ON
t1.id = t4.id
.
l
set tab off
set termout off
/
set termout on
@show_realtime_sql
PostgreSQL
perftestdb=> \! cat pg_sql_hj.sql
explain (analyze)
SELECT
/*+
HashJoin(t1 t2 t3 t4)
*/
t1.id
, t1.t1_c1
, t2.s_id
, t2.t2_c1
, t3.b_id
, t3.t3_c1
, t4.a_id
, t4.c_id
, t4.t4_c1
FROM
t1
INNER JOIN t2
ON
t1.id = t2.id
INNER JOIN t3
ON
t1.id = t3.id
INNER JOIN t4
ON
t1.id = t4.id
;
なお、テーブル、索引、登録したデータなどは、過去のエントリーを参照ください。
帰ってきた！ 標準はあるにはあるが癖の多いSQL #6 - Hash Joinの結合ツリーにも癖がでる
参考) 
Trees
https://resources.mpi-inf.mpg.de/departments/d5/teaching/ss09/queryoptimization/lecture4.pdf
Classification of Join Ordering Problems
https://resources.mpi-inf.mpg.de/departments/d5/teaching/ss09/queryoptimization/lecture5.pdf
Specialized Course "Query Optimization"
https://resources.mpi-inf.mpg.de/departments/d5/teaching/ss09/queryoptimization/
では、また、面白そうなネタを見つけたら書こうと思います。:)
| 固定リンク | 0
コメント