ハッシュ結合(hash join)とは

複数のテーブルを結合するSQLを実行すると、ORACLEはネステッドループ、ハッシュ、マージの3種類のいずれかの結合方法を選択して実行計画を立てます。
本ページではハッシュ結合の特徴やパフォーマンスについて記載します。
関連:ハッシュ結合をヒント句で制御する方法


ハッシュ結合の特徴

ハッシュ結合は以下のような順序で結合を行います。

①オプティマイザが小さいと見積もった表(以下、小規模表)の結合対象となる行を全件読み込み、結合キーをハッシュ関数にかけた結果をハッシュ表と呼ばれるメモリ(UGA)上の領域に格納する
②もう片方の表(以下、大規模表)に対して結合対象となる行を読み込み、結合キーをハッシュ関数にかけて①で作成したハッシュ表に結合可能なデータがあるか確認していく

ハッシュ結合には以下のような特徴があります。

・CBOのみ選択可能
ハッシュ結合はCBOのみ選択可能な結合方法でRBOで実行計画を立てる場合は選択されません。 これは、表のサイズや各列の平均長、予測結合対象行数等の統計を利用した見積もりが出せなければサイズが大きい場合はDISK書き出しが発生する可能性もあるハッシュ表を作成する ハッシュ結合を選択することが早いのかが判断できないためだと思われます

・等価結合のみ可能
ハッシュ関数にかけた結果から結合可能な行を探すロジックのため非等価結合や範囲条件による結合はできません

・少なくとも片方の表に対して結合対象の表に対して読み込みが終わらなければ結果を返すことができない
最初に小規模表のハッシュ表を作成した後に大規模表と比較するため少なくとも小規模表に対して全結合対象行を読み込んだ後でないと結果を戻すことができません。 したがって、ネステッドループと比較して最初の一件を戻すまでの時間は遅くなります。

・外部結合でも結合順序が固定されない
8i等古いバージョンではネステッドループのように結合順序が固定されていましたが新しいバージョンにおいては外部結合でも結合順序が固定されず、 外部結合される側が小規模表として選択された場合はhash join right outerと表示される実行計画が選択されます。 なお、今現在のバージョン(12.1)では右側外部結合を明示的に指定するヒントは公開されていませんがこちらの方法で実行計画を固定化させることが可能です。

SQL > select * from tab1 a,tab2 b where a.col2=b.col2(+);

実行計画
----------------------------------------------------------
Plan hash value: 3953873357

--------------------------------------------------------------------------------------
| Id  | Operation             | Name | Rows  | Bytes |TempSpc| Cost (%CPU)| Time     |
--------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT      |      |   400K|  7812K|       |  1011   (2)| 00:00:10 |
|*  1 |  HASH JOIN RIGHT OUTER|      |   400K|  7812K|  2152K|  1011   (2)| 00:00:10 |
|   2 |   TABLE ACCESS FULL   | TAB2 |   100K|   976K|       |    79   (2)| 00:00:01 |
|   3 |   TABLE ACCESS FULL   | TAB1 |   400K|  3906K|       |   280   (2)| 00:00:03 |
--------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   1 - access("A"."COL2"="B"."COL2"(+))

・結合条件式から内部表の索引スキャンは不可能
ハッシュ結合はネステッドループのように外部表1行に対して毎回内部表にアクセスするようなロジックではないため 結合条件列からの索引アクセスはできません。以下のように小規模表、大規模表に閉じた索引アクセスは可能です。
SQL %gt; select /*+ leading(a b) USE_HASH(b) */ * from tab1 a,tab2 b where a.col1=b.col1 and a.col2 = 1 and b.col2=1;


実行計画
----------------------------------------------------------
Plan hash value: 2097176171

---------------------------------------------------------------------------------------
| Id  | Operation                    | Name   | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |        |     1 |    20 |     7  (15)| 00:00:01 |
|*  1 |  HASH JOIN                   |        |     1 |    20 |     7  (15)| 00:00:01 |
|   2 |   TABLE ACCESS BY INDEX ROWID| TAB1   |     1 |    10 |     4   (0)| 00:00:01 |
|*  3 |    INDEX RANGE SCAN          | I_TAB1 |     1 |       |     3   (0)| 00:00:01 |
|   4 |   TABLE ACCESS BY INDEX ROWID| TAB2   |     1 |    10 |     2   (0)| 00:00:01 |
|*  5 |    INDEX RANGE SCAN          | I_TAB2 |     1 |       |     1   (0)| 00:00:01 |
---------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   1 - access("A"."COL1"="B"."COL1")
   3 - access("A"."COL2"=1)
   5 - access("B"."COL2"=1)

・結合データが大きくなると一時領域への書き出しが発生する場合がある
上述のようにメモリ上にハッシュ表を作成しようとしますがメモリには限りがあるので結合データが多くPGAにハッシュ表が入りきらなくなった場合は 一時表へのDISK書き出しが発生し、DISK書き出しが発生した途端パフォーマンスが悪化する傾向にあります。
SQL > select * from tab1 a,tab2 b where a.col2=b.col2(+);

実行計画
----------------------------------------------------------
Plan hash value: 3953873357

--------------------------------------------------------------------------------------
| Id  | Operation             | Name | Rows  | Bytes |TempSpc| Cost (%CPU)| Time     |
--------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT      |      |   400K|  7812K|       |  1011   (2)| 00:00:10 |
|*  1 |  HASH JOIN RIGHT OUTER|      |   400K|  7812K|  2152K|  1011   (2)| 00:00:10 |2152Kの一時表利用が見積もられている
|   2 |   TABLE ACCESS FULL   | TAB2 |   100K|   976K|       |    79   (2)| 00:00:01 |
|   3 |   TABLE ACCESS FULL   | TAB1 |   400K|  3906K|       |   280   (2)| 00:00:03 |
--------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   1 - access("A"."COL2"="B"."COL2"(+))

・多段HASH結合時の注意
実行計画上複数のHASH結合が存在している場合、それぞれHASH表を作成することになるため必要なメモリが大きくなることになります。
以下の実行計画ではB,C,D,Eの全件がそれぞれハッシュ表としてメモリ上にロードされます。(B+C+D+Eのサイズ分メモリが確保されないと一時表領域あふれになる)
TEST@ORCL112SJIS > select * from a,b,c,d,e where a.col1=b.col1 and a.col1=c.col1 and a.col1=d.col1 and a.col1=e.col1;

実行計画
----------------------------------------------------------
Plan hash value: 3383475176

------------------------------------------------------------------------------
| Id  | Operation             | Name | Rows  | Bytes | Cost (%CPU)| Time     |
------------------------------------------------------------------------------
|   0 | SELECT STATEMENT      |      |     1 |    65 |    12  (17)| 00:00:01 |
|*  1 |  HASH JOIN            |      |     1 |    65 |    12  (17)| 00:00:01 |
|   2 |   TABLE ACCESS FULL   | E    |     1 |    13 |     2   (0)| 00:00:01 |
|*  3 |   HASH JOIN           |      |     1 |    52 |    10  (20)| 00:00:01 |
|   4 |    TABLE ACCESS FULL  | D    |     1 |    13 |     2   (0)| 00:00:01 |
|*  5 |    HASH JOIN          |      |     1 |    39 |     7  (15)| 00:00:01 |
|   6 |     TABLE ACCESS FULL | C    |     1 |    13 |     2   (0)| 00:00:01 |
|*  7 |     HASH JOIN         |      |     1 |    26 |     5  (20)| 00:00:01 |
|   8 |      TABLE ACCESS FULL| B    |     1 |    13 |     2   (0)| 00:00:01 |
|   9 |      TABLE ACCESS FULL| A    |     1 |    13 |     2   (0)| 00:00:01 |
------------------------------------------------------------------------------

以下の例では処理が進むにつれ段階的にハッシュ表のサイズが変わります。結合が進むにつれ結果セットが大きくなるようなデータだと一時表領域あふれが発生することになります。
①A表の全件
②A表->B表の順に結合した結果
③A表->B表->C表の順に結合した結果
④A表->B表->C表->D表の順に結合した結果
TEST@ORCL112SJIS > select /*+ leading(a b c d e) use_hash(b c d e ) no_swap_join_inputs(b) no_swap_join_inputs(c) no_swap_join_inputs(d) no_swap_join_inputs(e)*/
  2   * from a,b,c,d,e where a.col1=b.col1 and a.col1=c.col1 and a.col1=d.col1 and a.col1=e.col1;

レコードが選択されませんでした。


実行計画
----------------------------------------------------------
Plan hash value: 2132132732

------------------------------------------------------------------------------
| Id  | Operation             | Name | Rows  | Bytes | Cost (%CPU)| Time     |
------------------------------------------------------------------------------
|   0 | SELECT STATEMENT      |      |     1 |    65 |    12  (17)| 00:00:01 |
|*  1 |  HASH JOIN            |      |     1 |    65 |    12  (17)| 00:00:01 |
|*  2 |   HASH JOIN           |      |     1 |    52 |    10  (20)| 00:00:01 |
|*  3 |    HASH JOIN          |      |     1 |    39 |     7  (15)| 00:00:01 |
|*  4 |     HASH JOIN         |      |     1 |    26 |     5  (20)| 00:00:01 |
|   5 |      TABLE ACCESS FULL| A    |     1 |    13 |     2   (0)| 00:00:01 |
|   6 |      TABLE ACCESS FULL| B    |     1 |    13 |     2   (0)| 00:00:01 |
|   7 |     TABLE ACCESS FULL | C    |     1 |    13 |     2   (0)| 00:00:01 |
|   8 |    TABLE ACCESS FULL  | D    |     1 |    13 |     2   (0)| 00:00:01 |
|   9 |   TABLE ACCESS FULL   | E    |     1 |    13 |     2   (0)| 00:00:01 |
------------------------------------------------------------------------------

ハッシュ結合のパフォーマンス

ハッシュ結合のcostや処理時間は基本的には以下のように考えられます。

小規模表のアクセス時間+大規模表のアクセス時間+ハッシュ表の作成時間

上記には大規模表の行からハッシュ表に結合できる行がないかを探す時間が含まれていませんが、 ハッシュ関数をかけた結果からハッシュ表内に結合可能な行があるかどうかは瞬時に判断できる仕組みのため ほぼ無視することができます。

ネステッドループと比較して、ハッシュ結合が早くなるのは以下のようなSQLとなります。

・結合対象行が多く十分なメモリ(UGA)が確保できる(ハッシュ表を一時表へ書き出す必要ない、または少ない)
・結合条件の索引がなくテーブルのフルスキャンが必要

マニュアル

概要
パフォーマンス・チューニングガイド
カスタム検索

★ORACLE案件承ります
▼ORACLE掲示板