OceanBaseデータベースの現行バージョンでは、Nested Loop Join、Hash Join、Merge Joinという3種類の異なる接合アルゴリズムがサポートされています。
Hash JoinとMerge Joinは等値の接合条件にのみ適用可能ですが、Nested Loop Joinは任意の接合条件に使用できます。
ネステッドループ結合（Nested Loop Join）
ネステッドループ結合の原理は、あるテーブル（外部テーブル）をスキャンし、そのテーブルから1件のレコードが読み取られるたびに、もう一方のテーブル（内部テーブル）を「スキャン」して条件を満たすデータを見つけることです。
ここでの「スキャン」とは、インデックスを利用した高速な位置特定スキャンである場合もあれば、フルテーブルスキャンである場合もあります。一般的に、フルテーブルスキャンのパフォーマンスは非常に低いため、結合条件の列にインデックスがない場合、オプティマイザーは通常ネステッドループ結合を選択しません。OceanBaseデータベースでは、実行計画においてインデックスを利用した高速な位置特定スキャンが可能かどうかが示されます。
以下の例のように、最初の計画では内部テーブルのスキャンがフルテーブルスキャンとなっています。これは、結合条件が t1.c = t2.c であり、t2 テーブルに c 列のインデックスがないためです。2番目の計画では、内部テーブルのスキャンでインデックスを利用してマッチする行を迅速に見つけることができます。主な理由は、結合条件が t1.b = t2.b であり、かつ t2 テーブルが b 列に作成されたインデックス k1 をアクセスパスとして選択しているためです。このように、t1 テーブルの各行の各 b 値に対して、t2 テーブルはインデックスを利用して条件を満たすマッチする行を迅速に見つけることができます。
obclient> CREATE TABLE t1(a INT PRIMARY KEY, b INT, c INT, KEY k1(b));
Query OK, 0 rows affected
obclient> CREATE TABLE t2(a INT PRIMARY KEY, b INT, c INT, KEY k1(b));
Query OK, 0 rows affected
obclient> EXPLAIN EXTENDED_NOADDR SELECT/*+USE_NL(t1, t2)*/ * FROM t1, t2
WHERE t1.c = t2.c;
+-----------------------------------------------------------------+
| Query Plan |
+-----------------------------------------------------------------+
| ===========================================
|ID|OPERATOR |NAME|EST. ROWS|COST |
-------------------------------------------
|0 |NESTED-LOOP JOIN| |1980 |623742|
|1 | TABLE SCAN |t1 |1000 |455 |
|2 | TABLE SCAN |t2 |2 |622 |
===========================================
Outputs & filters:
-------------------------------------
0 - output([t1.a], [t1.b], [t1.c], [t2.a], [t2.b], [t2.c]), filter(nil),
conds(nil), nl_params_([t1.c])
1 - output([t1.c], [t1.a], [t1.b]), filter(nil),
access([t1.c], [t1.a], [t1.b]), partitions(p0),
is_index_back=false,
range_key([t1.a]), range(MIN ; MAX)always true
2 - output([t2.c], [t2.a], [t2.b]), filter([? = t2.c]),
access([t2.c], [t2.a], [t2.b]), partitions(p0),
is_index_back=false, filter_before_indexback[false],
range_key([t2.a]), range(MIN ; MAX)
obclient> EXPLAIN EXTENDED_NOADDR SELECT/*+USE_NL(t1, t2)*/ * FROM t1, t2
WHERE t1.b = t2.b;
+-----------------------------------------------------------------+
| Query Plan |
+-----------------------------------------------------------------+
| ============================================
|ID|OPERATOR |NAME |EST. ROWS|COST |
--------------------------------------------
|0 |NESTED-LOOP JOIN| |1980 |94876|
|1 | TABLE SCAN |t1 |1000 |455 |
|2 | TABLE SCAN |t2(k1)|2 |94 |
============================================
Outputs & filters:
-------------------------------------
0 - output([t1.a], [t1.b], [t1.c], [t2.a], [t2.b], [t2.c]), filter(nil),
conds(nil), nl_params_([t1.b])
1 - output([t1.b], [t1.a], [t1.c]), filter(nil),
access([t1.b], [t1.a], [t1.c]), partitions(p0),
is_index_back=false,
range_key([t1.a]), range(MIN ; MAX)always true
2 - output([t2.b], [t2.a], [t2.c]), filter(nil),
access([t2.b], [t2.a], [t2.c]), partitions(p0),
is_index_back=true,
range_key([t2.b], [t2.a]), range(MIN ; MAX),
range_cond([? = t2.b])
ネステッドループ結合では、内部テーブルに対して複数回のフルテーブルスキャンを行う可能性があります。これは、各スキャンごとにストレージ層から再イテレーションする必要があるため、コストが比較的高くなるからです。そのため、OceanBaseデータベースでは内部テーブルに対して一度のスキャンを行い、その結果をメモリ内にマテリアライズすることをサポートしています。これにより、次回のスキャン実行時にはストレージ層から複数回スキャンする必要なく、メモリ内で関連データを直接スキャンできます。ただし、メモリ内へのマテリアライズにはコストが伴うため、OceanBaseデータベースのオプティマイザーはコストに基づいて内部テーブルをマテリアライズするかどうかを判断します。
ネステッドループ結合の最適化バリエーションの一つに、ブロックネステッドループ結合（Blocked Nested Loop Join）があります。これは、外部テーブルから1ブロック分の行を一度に読み取り、その後内部テーブルをスキャンして条件を満たすデータを見つける方法です。これにより、内部テーブルの読み取り回数を削減できます。
ネステッドループ結合は通常、外部テーブルの行数が比較的少なく、かつ内部テーブルの結合条件の列にインデックスがある場合に使用されます。これは、内部テーブルの各行がインデックスを利用して対応するマッチするデータを迅速に特定できるためです。
同時に、OceanBaseデータベースは、複数テーブル結合時にネステッドループ結合アルゴリズムを選択するためのヒントメカニズムとして /*+ USE_NL(table_name_list) */ も提供しています。例えば、以下のシナリオで結合アルゴリズムがハッシュ結合（Hash Join）を選択している場合でも、ユーザーがネステッドループ結合を使用したい場合は、上記のヒントを使用して制御できます。
obclient> CREATE TABLE t1(c1 INT, c2 INT);
Query OK, 0 rows affected
obclient> CREATE TABLE t2(c1 INT, c2 INT);
Query OK, 0 rows affected
obclient> EXPLAIN SELECT * FROM t1,t2 WHERE t1.c1 = t2.c1;
+-----------------------------------------------------------------+
| Query Plan |
+-----------------------------------------------------------------+
| ========================================
|ID|OPERATOR |NAME|EST. ROWS|COST |
----------------------------------------
|0 |HASH JOIN | |98010000 |66774608|
|1 | TABLE SCAN|T1 |100000 |68478 |
|2 | TABLE SCAN|T2 |100000 |68478 |
========================================
Outputs & filters:
-------------------------------------
0 - output([T1.C1], [T1.C2], [T2.C1], [T2.C2]), filter(nil),
equal_conds([T1.C1 = T2.C1]), other_conds(nil)
1 - output([T1.C1], [T1.C2]), filter(nil),
access([T1.C1], [T1.C2]), partitions(p0)
2 - output([T2.C1], [T2.C2]), filter(nil),
access([T2.C1], [T2.C2]), partitions(p0)
obclient> EXPLAIN SELECT /*+USE_NL(t1, t2)*/* FROM t1, t2 WHERE t1.c1 = t2.c1;
+-----------------------------------------------------------------+
| Query Plan |
+-----------------------------------------------------------------+
| ===============================================
|ID|OPERATOR |NAME|EST. ROWS|COST |
-----------------------------------------------
|0 |NESTED-LOOP JOIN| |98010000 |4595346207|
|1 | TABLE SCAN |T1 |100000 |68478 |
|2 | MATERIAL | |100000 |243044 |
|3 | TABLE SCAN |T2 |100000 |68478 |
===============================================
Outputs & filters:
-------------------------------------
0 - output([T1.C1], [T1.C2], [T2.C1], [T2.C2]), filter(nil),
conds([T1.C1 = T2.C1]), nl_params_(nil)
1 - output([T1.C1], [T1.C2]), filter(nil),
access([T1.C1], [T1.C2]), partitions(p0)
2 - output([T2.C1], [T2.C2]), filter(nil)
3 - output([T2.C1], [T2.C2]), filter(nil),
access([T2.C1], [T2.C2]), partitions(p0)
ネステッドループ結合には、以下の2種類の実装アルゴリズムもあります：
ブロックネステッドループ結合（Blocked Nested Loop Join）
OceanBaseデータベースにおけるブロックネステッドループ結合の実装方法はバッチネステッドループ結合（Batch Nested Loop Join）です。これは、外部テーブルからデータ行を一括で読み取り（デフォルトは1000行）、その後内部テーブルをスキャンして条件を満たすデータを見つけるというものです。このようにして、一括データと内部テーブルのデータをマッチングさせることで、内部テーブルの読み取り回数と内部ループの回数を削減します。
以下の例では、
batch_join=trueフィールドは今回のクエリでバッチネステッドループ結合が使用されたことを示しています。obclient>CREATE TABLE t1(c1 INT PRIMARY KEY); Query OK, 0 rows affected obclient>CREATE TABLE t2(c1 INT PRIMARY KEY); Query OK, 0 rows affected obclient>EXPLAIN EXTENDED_NOADDR SELECT /*+USE_NL(t1,t2)*/* FROM t1,t2 WHERE t1.c1=t2.c1\G *************************** 1. row *************************** Query Plan: ============================================ |ID|OPERATOR |NAME|EST. ROWS|COST | -------------------------------------------- |0 |NESTED-LOOP JOIN| |100001 |3728786| |1 | TABLE SCAN |t1 |100000 |59654 | |2 | TABLE GET |t2 |1 |36 | ============================================ Outputs & filters: ------------------------------------- 0 - output([t1.c1], [t2.c1]), filter(nil), conds(nil), nl_params_([t1.c1]), inner_get=false, self_join=false, batch_join=true 1 - output([t1.c1]), filter(nil), access([t1.c1]), partitions(p0), is_index_back=false, range_key([t1.c1]), range(MIN ; MAX)always true 2 - output([t2.c1]), filter(nil), access([t2.c1]), partitions(p0), is_index_back=false, range_key([t2.c1]), range(MIN ; MAX), range_cond([? = t2.c1])インデックスネステッドループ結合（Index Nested Loop Join）
インデックスネステッドループ結合は、インデックスに基づいて結合を行うアルゴリズムです。外部テーブルのマッチング条件を直接内部テーブルのインデックスと照合することで、内部テーブルの各レコードとの比較を回避し、内部テーブルへのマッチング回数を削減します。
以下の例では、結合条件として
t1.c1 = t2.c1が存在します。この場合、t2テーブルのc1列またはt1テーブルのc1列にインデックスがある場合、インデックスネステッドループ結合アルゴリズムが使用されます。obclient> CREATE TABLE t1(c1 INT PRIMARY KEY); Query OK, 0 rows affected obclient> CREATE TABLE t2(c1 INT ,c2 INT); Query OK, 0 rows affected obclient> EXPLAIN SELECT /*+ORDERED USE_NL(t2,t1)*/ * FROM t2, (SELECT /*+NO_MERGE*/ * FROM t1)t1 WHERE t1.c1 = t2.c1 AND t2.c2 = 1\G *************************** 1. row *************************** Query Plan: =========================================== |ID|OPERATOR |NAME|EST. ROWS|COST | ------------------------------------------- |0 |NESTED-LOOP JOIN| |981 |117272| |1 | TABLE SCAN |t2 |990 |80811 | |2 | SUBPLAN SCAN |t1 |1 |37 | |3 | TABLE GET |t1 |1 |36 | =========================================== Outputs & filters: ------------------------------------- 0 - output([t2.c1], [t2.c2], [t1.c1]), filter(nil), conds(nil), nl_params_([t2.c1]) 1 - output([t2.c1], [t2.c2]), filter([t2.c2 = 1]), access([t2.c1], [t2.c2]), partitions(p0) 2 - output([t1.c1]), filter(nil), access([t1.c1]) 3 - output([t1.c1]), filter(nil), access([t1.c1]), partitions(p0)outputs & filtersの出力結果において、パラメータ[t2.c1]が現れる場合、条件プッシュダウンの最適化が実行されたことを意味します。詳細については、JOINを参照してください。一般的に、クエリの最適化を行う際、OceanBaseデータベースのオプティマイザーはまずインデックスネステッドループ結合を優先的に選択し、次にバッチネステッドループ結合を使用できるかどうかを確認します。これら2つの最適化手法は併用可能であり、最終的にネステッドループ結合が選択されることはありません。
DAS Group Rescan
OceanBaseデータベースV4.1.0バージョンでは、DAS Group Rescanは単一レベルのNested Loop Joinの実行に適用されます。この最適化は、NLJ（Nested Loop Join）の左側の部分でバッチ処理を行い、右側の部分へのスキャン回数を削減します。この最適化はデフォルトで有効になっており、内部システム変数_NLJ_BATCHING_ENABLED（Oracleモードではこの変数を設定する際にはダブルクォーテーションマークで囲む必要があります）を使用して無効にすることができます。構文は以下のとおりです：
/* MySQLモード */
SET _NLJ_BATCHING_ENABLED=false;
/* Oracleモード */
SET "_NLJ_BATCHING_ENABLED"=false;
Nested Loop Joinの実行計画結果では、実行計画の4番目の演算子（4 - output）にあるuse_batch=trueのマークを確認できます。これは、そのNested Loop Join（NLJ）演算子でDAS Group Rescan最適化が有効になっていることを意味します。例：
obclient> CREATE TABLE t1 (a INT, b INT, c INT, PRIMARY KEY(a, b));
obclient> CREATE TABLE t2 (a INT, b INT, c INT, PRIMARY KEY(a, b));
obclient> CREATE TABLE t3 (a INT, b INT , c INT, PRIMARY KEY(b, c));
obclient> EXPLAIN EXTENDED_NOADDR select /*+no_rewrite leading(t1 v) use_nl(t1 v)*/ count(*), sum(t1.a+t1.b+t1.c+v.a+v.b+v.c) FROM t1, (select /*+no_rewrite leading(t2 t3) use_nl(t2 t3)*/ t2.a, t2.b, t3.c from t2, t3 where t2.c = t3.b) v WHERE t1.a = v.c AND t1.c = v.a;
+-----------------------------------------------------------------------------------------------------------+
| Query Plan |
+-----------------------------------------------------------------------------------------------------------+
| ==================================================================== |
| |ID|OPERATOR |NAME|EST.ROWS|EST.TIME(us)| |
| -------------------------------------------------------------------- |
| |0 |SCALAR GROUP BY | |1 |44 | |
| |1 |└─NESTED-LOOP JOIN | |1 |44 | |
| |2 | ├─TABLE FULL SCAN |t1 |1 |4 | |
| |3 | └─SUBPLAN SCAN |v |1 |39 | |
| |4 | └─NESTED-LOOP JOIN | |1 |39 | |
| |5 | ├─DISTRIBUTED TABLE RANGE SCAN|t2 |1 |21 | |
| |6 | └─DISTRIBUTED TABLE GET |t3 |1 |18 | |
| ==================================================================== |
| Outputs & filters: |
| ------------------------------------- |
| 0 - output([T_FUN_COUNT(*)], [T_FUN_SUM(t1.a + t1.b + t1.c + v.a + v.b + v.c)]), filter(nil), rowset=16 |
| group(nil), agg_func([T_FUN_COUNT(*)], [T_FUN_SUM(t1.a + t1.b + t1.c + v.a + v.b + v.c)]) |
| 1 - output([t1.a], [t1.c], [t1.b], [v.c], [v.a], [v.b]), filter(nil), rowset=16 |
| conds(nil), nl_params_([t1.a(:1)], [t1.c(:2)]), use_batch=false |
| 2 - output([t1.a], [t1.b], [t1.c]), filter(nil), rowset=16 |
| access([t1.a], [t1.b], [t1.c]), partitions(p0) |
| is_index_back=false, is_global_index=false, |
| range_key([t1.a], [t1.b]), range(MIN,MIN ; MAX,MAX)always true |
| 3 - output([v.c], [v.a], [v.b]), filter(nil), rowset=16 |
| access([v.c], [v.a], [v.b]) |
| 4 - output([t2.a], [t2.b], [t3.c]), filter(nil), rowset=16 |
| conds(nil), nl_params_([t2.c(:3)]), use_batch=true |
| 5 - output([t2.a], [t2.b], [t2.c]), filter(nil), rowset=16 |
| access([t2.a], [t2.b], [t2.c]), partitions(p0) |
| is_index_back=false, is_global_index=false, |
| range_key([t2.a], [t2.b]), range(MIN,MIN ; MAX,MAX)always true, |
| range_cond([:2 = t2.a]) |
| 6 - output([t3.c]), filter(nil), rowset=16 |
| access([GROUP_ID], [t3.c]), partitions(p0) |
| is_index_back=false, is_global_index=false, |
| range_key([t3.b], [t3.c]), range(MIN ; MAX), |
| range_cond([:1 = t3.c], [:3 = t3.b]) |
| Used Hint: |
| ------------------------------------- |
| /*+ |
| |
| LEADING(("t1" "v")) |
| USE_NL("v") |
| LEADING(("t2" "t3")) |
| USE_NL("t3") |
| NO_REWRITE |
| NO_REWRITE |
| */ |
| Qb name trace: |
| ------------------------------------- |
| stmt_id:0, stmt_type:T_EXPLAIN |
| stmt_id:1, SEL$1 |
| stmt_id:2, SEL$2 |
| Outline Data: |
| ------------------------------------- |
| /*+ |
| BEGIN_OUTLINE_DATA |
| LEADING(@"SEL$1" ("test"."t1"@"SEL$1" "v"@"SEL$1")) |
| USE_NL(@"SEL$1" "v"@"SEL$1") |
| FULL(@"SEL$1" "test"."t1"@"SEL$1") |
| LEADING(@"SEL$2" ("test"."t2"@"SEL$2" "test"."t3"@"SEL$2")) |
| USE_NL(@"SEL$2" "test"."t3"@"SEL$2") |
| FULL(@"SEL$2" "test"."t2"@"SEL$2") |
| USE_DAS(@"SEL$2" "test"."t2"@"SEL$2") |
| FULL(@"SEL$2" "test"."t3"@"SEL$2") |
| USE_DAS(@"SEL$2" "test"."t3"@"SEL$2") |
| OPTIMIZER_FEATURES_ENABLE('4.2.1.0') |
| END_OUTLINE_DATA |
| */ |
| Optimization Info: |
| ------------------------------------- |
| t1: |
| table_rows:1 |
| physical_range_rows:1 |
| logical_range_rows:1 |
| index_back_rows:0 |
| output_rows:1 |
| table_dop:1 |
| dop_method:Table DOP |
| avaiable_index_name:[t1] |
| stats version:0 |
| dynamic sampling level:1 |
| t2: |
| table_rows:1 |
| physical_range_rows:1 |
| logical_range_rows:1 |
| index_back_rows:0 |
| output_rows:1 |
| table_dop:1 |
| dop_method:DAS DOP |
| avaiable_index_name:[t2] |
| stats version:0 |
| dynamic sampling level:1 |
| t3: |
| table_rows:1 |
| physical_range_rows:1 |
| logical_range_rows:1 |
| index_back_rows:0 |
| output_rows:1 |
| table_dop:1 |
| dop_method:DAS DOP |
| avaiable_index_name:[t3] |
| stats version:0 |
| dynamic sampling level:1 |
| Plan Type: |
| LOCAL |
| Note: |
| Degree of Parallelisim is 1 because of table property |
+-----------------------------------------------------------------------------------------------------------+
106 rows in set
Merge Join
Merge Joinの原理は、まず結合するフィールドに基づいて2つのテーブルをソートし（メモリ容量が不足している場合は外部スキャンが必要）、その後2つのテーブルをスキャンして結合を開始することです。
結合処理では、各テーブルから1件ずつレコードを取り出してマッチングを開始します。関連条件に合致する場合は結果セットに追加されます。そうでない場合は、関連フィールドの値が小さいレコードを破棄し、そのレコードが対応するテーブルから次のレコードを取得してマッチングを続け、このループ全体が終了するまで繰り返します。
複数対複数の2つのテーブル間で結合を行う際には、通常一時的な領域を使用して操作を行います。例えば、AとBの結合にMerge Joinを使用する場合、関連フィールドの特定の値に対して、AとBの両方に複数のレコード（A1、A2…AnおよびB1、B2…Bn）が存在する場合、Aの各レコード（A1、A2…An）について、Bのすべての等しいレコード（B1、B2…Bn）と一度ずつマッチングを行う必要があります。このため、ポインターはB1からBnへ何度も移動し、そのたびに対応するB1〜Bnのレコードを読み込む必要があります。B1〜Bnのレコードを事前に読み込んでメモリ上の一時テーブルに格納する方が、元のデータページやディスクから読み込むよりも高速です。一部のシナリオでは、結合フィールドに利用可能なインデックスがあり、かつソートが一致している場合、ソート処理を直接スキップできます。
一般的に、Merge Joinは入力テーブルが既に順序付けられている場合に適しており、そうでない場合はHash Joinの方が適しています。以下の例は、2つのMerge Joinの計画を示しています。最初の計画ではソートが必要ですが、2番目の計画ではソートは不要です（2つのテーブルともにk1という2つのインデックスアクセスパスを選択しており、これらのインデックス自体がb列に基づいてソートされているためです）。
obclient> CREATE TABLE t1(a INT PRIMARY KEY, b INT, c INT, KEY k1(b));
Query OK, 0 rows affected
obclient> CREATE TABLE t2(a INT PRIMARY KEY, b INT, c INT, KEY k1(b));
Query OK, 0 rows affected
obclient> EXPLAIN SELECT/*+USE_MERGE(t1, t2)*/ * FROM t1, t2 WHERE t1.c = t2.c;
*************************** 1. row ***************************
Query Plan:
| =====================================
|ID|OPERATOR |NAME|EST. ROWS|COST|
-------------------------------------
|0 |MERGE JOIN | |1980 |6011|
|1 | SORT | |1000 |2198|
|2 | TABLE SCAN|t1 |1000 |455 |
|3 | SORT | |1000 |2198|
|4 | TABLE SCAN|t2 |1000 |455 |
=====================================
Outputs & filters:
-------------------------------------
0 - output([t1.a], [t1.b], [t1.c], [t2.a], [t2.b], [t2.c]), filter(nil),
equal_conds([t1.c = t2.c]), other_conds(nil)
1 - output([t1.a], [t1.b], [t1.c]), filter(nil), sort_keys([t1.c, ASC])
2 - output([t1.c], [t1.a], [t1.b]), filter(nil),
access([t1.c], [t1.a], [t1.b]), partitions(p0)
3 - output([t2.a], [t2.b], [t2.c]), filter(nil), sort_keys([t2.c, ASC])
4 - output([t2.c], [t2.a], [t2.b]), filter(nil),
access([t2.c], [t2.a], [t2.b]), partitions(p0)
obclient> EXPLAIN SELECT/*+USE_MERGE(t1, t2),INDEX(t1 k1),INDEX(t2 k1)*/ *
FROM t1, t2 WHERE t1.b = t2.b;
*************************** 1. row ***************************
Query Plan:
| =======================================
|ID|OPERATOR |NAME |EST. ROWS|COST |
---------------------------------------
|0 |MERGE JOIN | |1980 |12748|
|1 | TABLE SCAN|t1(k1)|1000 |5566 |
|2 | TABLE SCAN|t2(k1)|1000 |5566 |
=======================================
Outputs & filters:
-------------------------------------
0 - output([t1.a], [t1.b], [t1.c], [t2.a], [t2.b], [t2.c]), filter(nil),
equal_conds([t1.b = t2.b]), other_conds(nil)
1 - output([t1.b], [t1.a], [t1.c]), filter(nil),
access([t1.b], [t1.a], [t1.c]), partitions(p0)
2 - output([t2.b], [t2.a], [t2.c]), filter(nil),
access([t2.b], [t2.a], [t2.c]), partitions(p0)
同時に、OceanBaseデータベースは、複数テーブル結合時にMerge Join結合アルゴリズムを選択するためのHintメカニズム/*+ USE_MERGE(table_name_list) */も提供しています。例えば、以下のシナリオでは結合アルゴリズムとしてHash Joinが選択されていますが、ユーザーがMerge Joinを使用したい場合は、上記のHintを使用して制御できます。
obclient> CREATE TABLE t1(c1 INT, c2 INT);
Query OK, 0 rows affected
obclient> CREATE TABLE t2(c1 INT, c2 INT);
Query OK, 0 rows affected
obclient> EXPLAIN SELECT * FROM t1,t2 WHERE t1.c1 = t2.c1;
*************************** 1. row ***************************
Query Plan:
| ========================================
|ID|OPERATOR |NAME|EST. ROWS|COST |
----------------------------------------
|0 |HASH JOIN | |98010000 |66774608|
|1 | TABLE SCAN|T1 |100000 |68478 |
|2 | TABLE SCAN|T2 |100000 |68478 |
========================================
Outputs & filters:
-------------------------------------
0 - output([T1.C1], [T1.C2], [T2.C1], [T2.C2]), filter(nil),
equal_conds([T1.C1 = T2.C1]), other_conds(nil)
1 - output([T1.C1], [T1.C2]), filter(nil),
access([T1.C1], [T1.C2]), partitions(p0)
2 - output([T2.C1], [T2.C2]), filter(nil),
access([T2.C1], [T2.C2]), partitions(p0)
obclient> EXPLAIN SELECT /*+USE_MERGE(t1,t2)*/* FROM t1, t2 WHERE t1.c1 = t2.c1;
*************************** 1. row ***************************
Query Plan:
| =========================================
|ID|OPERATOR |NAME|EST. ROWS|COST |
-----------------------------------------
|0 |MERGE JOIN | |98010000 |67488837|
|1 | SORT | |100000 |563680 |
|2 | TABLE SCAN|T1 |100000 |68478 |
|3 | SORT | |100000 |563680 |
|4 | TABLE SCAN|T2 |100000 |68478 |
=========================================
Outputs & filters:
-------------------------------------
0 - output([T1.C1], [T1.C2], [T2.C1], [T2.C2]), filter(nil),
equal_conds([T1.C1 = T2.C1]), other_conds(nil)
1 - output([T1.C1], [T1.C2]), filter(nil), sort_keys([T1.C1, ASC])
2 - output([T1.C1], [T1.C2]), filter(nil),
access([T1.C1], [T1.C2]), partitions(p0)
3 - output([T2.C1], [T2.C2]), filter(nil), sort_keys([T2.C1, ASC])
4 - output([T2.C1], [T2.C2]), filter(nil),
access([T2.C1], [T2.C2]), partitions(p0)
Hash Join
Hash Joinの原理は、2つのテーブルのうち比較的小さい方のテーブル（通常Build Tableと呼ばれる）を基に結合条件に基づいてHash Tableを作成し、次に大きい方のテーブル（通常Probe Tableと呼ばれる）を行ごとにスキャンしながら、Hash Tableを探索してマッチする行を見つけることです。もしBuild Tableが非常に大きく、構築されたHash Tableをメモリ内で収容できない場合、OceanBaseデータベースはそれぞれのBuild TableとProbe Tableを結合条件に基づいて複数のパーティション(Partition)に分割します。各パーティションには独立したペアのBuild TableとProbe Tableが含まれており、これにより1つの大きなHash Joinが複数の独立した、互いに影響しないHash Joinに分割されます。各パーティションのHash Joinはメモリ内で完了可能です。ほとんどの場合、Hash Joinは他の結合方式よりも効率が高いです。
以下はHash Join計画の例です。
obclient> CREATE TABLE t1(a INT PRIMARY KEY, b INT, c INT, KEY k1(b));
Query OK, 0 rows affected
obclient>CREATE TABLE t2(a INT PRIMARY KEY, b INT, c INT, KEY k1(b));
Query OK, 0 rows affected
obclient> EXPLAIN SELECT/*+USE_HASH(t1, t2)*/ * FROM t1, t2 WHERE t1.c = t2.c;
*************************** 1. row ***************************
Query Plan:
| ====================================
|ID|OPERATOR |NAME|EST. ROWS|COST|
------------------------------------
|0 |HASH JOIN | |1980 |4093|
|1 | TABLE SCAN|t1 |1000 |455 |
|2 | TABLE SCAN|t2 |1000 |455 |
====================================
Outputs & filters:
-------------------------------------
0 - output([t1.a], [t1.b], [t1.c], [t2.a], [t2.b], [t2.c]), filter(nil),
equal_conds([t1.c = t2.c]), other_conds(nil)
1 - output([t1.c], [t1.a], [t1.b]), filter(nil),
access([t1.c], [t1.a], [t1.b]), partitions(p0)
2 - output([t2.c], [t2.a], [t2.b]), filter(nil),
access([t2.c], [t2.a], [t2.b]), partitions(p0)
同時に、OceanBaseデータベースでは、複数テーブル結合時にHash Join結合アルゴリズムを選択するためのHintメカニズム/*+ USE_HASH(table_name_list) */も提供しています。例えば、以下のシナリオでは結合アルゴリズムとしてMerge Joinが選択されていますが、ユーザーがHash Joinを使用したい場合は、上記のHintを使用して制御できます。
obclient> CREATE TABLE t1(c1 INT, c2 INT, PRIMARY KEY(c1));
Query OK, 0 rows affected
obclient> CREATE TABLE t2(c1 INT, c2 INT, PRIMARY KEY(c1));
Query OK, 0 rows affected
obclient> EXPLAIN SELECT * FROM t1, t2 WHERE t1.c1 = t2.c1;
*************************** 1. row ***************************
Query Plan:
| ======================================
|ID|OPERATOR |NAME|EST. ROWS|COST |
--------------------------------------
|0 |MERGE JOIN | |100001 |219005|
|1 | TABLE SCAN|T1 |100000 |61860 |
|2 | TABLE SCAN|T2 |100000 |61860 |
======================================
Outputs & filters:
-------------------------------------
0 - output([T1.C1], [T1.C2], [T2.C1], [T2.C2]), filter(nil),
equal_conds([T1.C1 = T2.C1]), other_conds(nil)
1 - output([T1.C1], [T1.C2]), filter(nil),
access([T1.C1], [T1.C2]), partitions(p0)
2 - output([T2.C1], [T2.C2]), filter(nil),
access([T2.C1], [T2.C2]), partitions(p0)
obclient> EXPLAIN SELECT /*+USE_HASH(t1, t2)*/ * FROM t1, t2 WHERE t1.c1 = t2.c1;
*************************** 1. row ***************************
Query Plan:
| ======================================
|ID|OPERATOR |NAME|EST. ROWS|COST |
--------------------------------------
|0 |HASH JOIN | |100001 |495180|
|1 | TABLE SCAN|T1 |100000 |61860 |
|2 | TABLE SCAN|T2 |100000 |61860 |
======================================
Outputs & filters:
-------------------------------------
0 - output([T1.C1], [T1.C2], [T2.C1], [T2.C2]), filter(nil),
equal_conds([T1.C1 = T2.C1]), other_conds(nil)
1 - output([T1.C1], [T1.C2]), filter(nil),
access([T1.C1], [T1.C2]), partitions(p0)
2 - output([T2.C1], [T2.C2]), filter(nil),
access([T2.C1], [T2.C2]), partitions(p0)
特に、OceanBaseデータベースではHash JoinにRuntime Filer最適化を採用しています。詳細については、Runtime Filterを参照してください。