ハッシュ結合

ハッシュ結合アルゴリズムは、入れ子ループ結合の、内部クエリを 実行する際にBツリー走査が大量発生してしまうという弱点に狙いを絞っています。代わりにハッシュ結合では、結合の片側のクエリの候補となるレコードを ハッシュテーブルに 読み込むことで、結合のもう片方の各行と高速に突き合わせができるようにしています。ハッシュ結合のチューニングでは、入れ子ループ結合とは全く異なる インデックスのアプローチが必要になります。さらに、より少ない列を選択することで、ハッシュ結合の パフォーマンスを上げることもできますが、これは多くのORMにとっては難しい課題です。

ハッシュ結合のインデックス戦略は全く異なると書きましたが、これは結合する列にインデックスが必要ないためです。whereの述語 それぞれに対する独立したインデックスのみが、ハッシュ結合のパフォーマンスを改善できます。

以下の例を考えてみましょう。過去6ヶ月の売上を、対応する従業員の詳細と共に選択しています。

SELECT *
  FROM sales s
  JOIN employees e ON (s.subsidiary_id = e.subsidiary_id
                  AND  s.employee_id   = e.employee_id  )
 WHERE s.sale_date > trunc(sysdate) - INTERVAL '6' MONTH

SALE_DATEが、where句の 唯一の独立したフィルタです。つまり、この句は1つのテーブルしか参照しておらず、結合の述語にはなっていないということです。

実行計画の最初のステップでは、全従業員をハッシュテーブルに読み込むためのフルスキャンが行われています(ID 2)。ハッシュテーブルは、キーとして結合述語を使っています。次のステップでは、SALESに対しての フルスキャンを行っており、SALE_DATEの条件に合致しない売上のレコードを全て捨てています(ID 3)。データベースは、残りのSALESのレコードに対応する従業員の詳細については、ハッシュ テーブルにアクセスして読み出しています。

ハッシュテーブルの唯一の目的は、EMPLOYEEテーブルに 何度もアクセスしなくてもよいようにするための、一時的なインメモリ構造としての 動きです。ハッシュテーブルへは最初の1回しかロードされないので、各レコードを 読み込むのを効率化するためのインデックスは必要ないのです。実行計画の述語 情報からも、EMPLOYEESテーブルに対してフィルタが適用されていないことが分かります(ID 2)。クエリは、このテーブルに対して独立した述語を持っていないためです。

これは、ハッシュ結合ではインデックスを使えないという意味ではありません。 独立した述語にはインデックスが使えないということです。2つのテーブルへのアクセスのうちのどちらかにしか適用できない条件というのがあり得ますが、 それが上の例のようなSALE_DATEに対するフィルタです。

CREATE INDEX sales_date ON sales (sale_date)

次の実行計画は、このインデックスを使っています。しかしそれにも 関わらず、EMPLOYEESに対する独立したwhereの 述語がないクエリのため、EMPLOYEES表にはフルスキャンが実行されています。

ハッシュ結合におけるインデックスは、入れ子ループ結合と比較して、対称的に なっています。これは、結合の順序はインデックスに関係ないという意味です。 結合順序が逆になっても、SALES_DATEインデックスはハッシュテーブルへのロードに使われます。

別の角度からハッシュ結合のパフォーマンスを最適化するには、ハッシュテーブルのサイズを小さくする方法があります。ハッシュテーブル全体が メモリに収まっていなければ、最適化されたハッシュ結合はできません。ハッシュテーブルを使う結合では、オプティマイザは小さな方のテーブルを 自動的に使います。Oracleの実行計画では、メモリ使用量の見積もりは 「Bytes」列に表示されています。上の実行計画では、EMPLOYEES テーブルは9MBを必要としているとあり、これは他のテーブルより小さくなっていることが分かります。

SQLクエリを変更することでハッシュテーブルのサイズを小さくすることも 可能です。データベースがより少ないレコードしかハッシュテーブルに読み込まずに 済むように、条件を追加してやることが考えられます。前述の例でまた考えると、 DEPARTMENTに対するフィルタを追加することで、営業スタッフのみが 選択されるようにできます。売上を持たない従業員をハッシュテーブルに保存する 必要がないので、DEPARTMENTにインデックスがない場合でも、 ハッシュ結合のパフォーマンスは改善されます。この場合、特定の部署に 所属していないけれど、SALESにレコードがある従業員がいない ことを確実にしておかねばなりません。この問題に対しては、制約を付けて対処するとよいでしょう。

ハッシュテーブルのサイズを最小化しようとする時、関係があるのは行数ではなく、メモリ使用量です。これはつまり、本当に必要な属性だけ、 つまり選択する列を減らすことでもハッシュテーブルのサイズを小さく出来るということです。

SELECT s.sale_date, s.eur_value
     , e.last_name, e.first_name
  FROM sales s
  JOIN employees e ON (s.subsidiary_id = e.subsidiary_id
                  AND  s.employee_id   = e.employee_id  )
 WHERE s.sale_date > trunc(sysdate) - INTERVAL '6' MONTH

間違った列を選択するようにしたとしても、すぐにどこかでエラーメッセージが出るで しょうから、この方法でバグを生んでしまうことはほとんどないでしょう。それなのに、大幅なハッシュテーブルサイズの削減が可能です。今回の例では、 9MBから234KBまで、97%も削減できました。

--------------------------------------------------------------
| Id | Operation                    | Name      | Bytes| Cost|
--------------------------------------------------------------
|  0 | SELECT STATEMENT             |           | 2067K| 2202|
|* 1 |  HASH JOIN                   |           | 2067K| 2202|
|  2 |   TABLE ACCESS FULL          | EMPLOYEES |  234K|  478|
|  3 |   TABLE ACCESS BY INDEX ROWID| SALES     |  913K| 1724|
|* 4 |    INDEX RANGE SCAN          | SALES_DATE|      |  133|
--------------------------------------------------------------

一見するとSQL文からいくつかの列を消すのは簡単なように思えますが、 ORMツールを使っている場合は難しい課題になります。いわゆる部分オブジェクトをサポートしているものはほとんどありません。以下の例では、いくつかの可能性を見てみましょう。