ハッシュ結合


Applies to
DB2Yes
MySQLNo
OracleYes
PostgreSQLYes
SQL ServerYes

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

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

Tweet this tip

ヒント

ハッシュ結合のパフォーマンスを改善したいなら、 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つのテーブルしか参照しておらず、 結合の述語にはなっていないということです。

DB2
Explain Plan
------------------------------------------------------------
ID | Operation          |                       Rows |  Cost
 1 | RETURN             |                            | 60750
 2 |  HSJOIN            |             50795 of 10000 | 60750
 3 |   TBSCAN SALES     | 50795 of 1011118 (  5.02%) | 60053
 4 |   TBSCAN EMPLOYEES |   10000 of 10000 (100.00%) |   688

Predicate Information
 2 - JOIN (Q2.SUBSIDIARY_ID = DECIMAL(Q1.SUBSIDIARY_ID, 10, 0))
     JOIN (Q2.EMPLOYEE_ID = DECIMAL(Q1.EMPLOYEE_ID, 10, 0))
 3 - SARG ((CURRENT DATE - 6 MONTHS) < Q2.SALE_DATE)

欲しい結果を取り出すためにwhere句は 次のように書き換えられています : WHERE s.sale_date > current_date - 6 MONTH

Oracle
--------------------------------------------------------------
| Id | Operation          | Name      | Rows  | Bytes | Cost |
--------------------------------------------------------------
|  0 | SELECT STATEMENT   |           | 49244 |    59M| 12049|
|* 1 |  HASH JOIN         |           | 49244 |    59M| 12049|
|  2 |   TABLE ACCESS FULL| EMPLOYEES | 10000 |     9M|   478|
|* 3 |   TABLE ACCESS FULL| SALES     | 49244 |    10M| 10521|
--------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   1 - access("S"."SUBSIDIARY_ID"="E"."SUBSIDIARY_ID"
          AND "S"."EMPLOYEE_ID"  ="E"."EMPLOYEE_ID")
   3 - filter("S"."SALE_DATE">TRUNC(SYSDATE@!)
                           -INTERVAL'+00-06' YEAR(2) TO MONTH)

実行計画の最初のステップでは、全従業員をハッシュテーブルに読み込む ためのフルスキャンが行われています(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表にはフルスキャンが 実行されています。

DB2
Explain Plan
----------------------------------------------------------------
ID | Operation              |                       Rows |  Cost
 1 | RETURN                 |                            | 16655
 2 |  HSJOIN                |             50795 of 10000 | 16655
 3 |   FETCH SALES          |   50795 of 50795 (100.00%) | 15958
 4 |    RIDSCN              |   50795 of 50795 (100.00%) |  1655
 5 |     SORT (UNQIUE)      |   50795 of 50795 (100.00%) |  1655
 6 |      IXSCAN SALES_DATE | 50795 of 1011118 (  5.02%) |  1631
 7 |   TBSCAN EMPLOYEES     |   10000 of 10000 (100.00%) |   688

Predicate Information
 2 - JOIN (Q2.SUBSIDIARY_ID = DECIMAL(Q1.SUBSIDIARY_ID, 10, 0))
     JOIN (Q2.EMPLOYEE_ID = DECIMAL(Q1.EMPLOYEE_ID, 10, 0))
 3 - SARG ((CURRENT DATE - 6 MONTHS) < Q2.SALE_DATE)
 6 - START ((CURRENT DATE - 6 MONTHS) < Q2.SALE_DATE)

欲しい結果を取り出すためにwhere句は 次のように書き換えられています : WHERE s.sale_date > current_date - 6 MONTH

Oracle
--------------------------------------------------------------
| Id | Operation                    | Name      | Bytes| Cost|
--------------------------------------------------------------
|  0 | SELECT STATEMENT             |           |   59M| 3252|
|* 1 |  HASH JOIN                   |           |   59M| 3252|
|  2 |   TABLE ACCESS FULL          | EMPLOYEES |    9M|  478|
|  3 |   TABLE ACCESS BY INDEX ROWID| SALES     |   10M| 1724|
|* 4 |    INDEX RANGE SCAN          | SALES_DATE|      |     |
--------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   1 - access("S"."SUBSIDIARY_ID"="E"."SUBSIDIARY_ID"
          AND "S"."EMPLOYEE_ID"  ="E"."EMPLOYEE_ID"  )
   4 - access("S"."SALE_DATE" > TRUNC(SYSDATE@!)
                           -INTERVAL'+00-06' YEAR(2) TO MONTH)

ハッシュ結合におけるインデックスは、入れ子ループ結合と比較して、対称的に なっています。これは、結合の順序はインデックスに関係ないという意味です。 結合順序が逆になっても、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|
--------------------------------------------------------------
Tweet this tip

ヒント

ハッシュ結合を高速化するために、必要な列だけを 選択しましょう。

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

Java

JPAでは、@Basicアノテーションで FetchType.LAZYが定義されています。これは、 プロパティレベルで適用されます。

@Column(name="junk")
@Basic(fetch=FetchType.LAZY)
private String junk;

JPAプロバイダは、これを無視することが許されています。

LAZYストラテジは、永続化プロバイダのランタイムに対して、 最初にアクセスされた時まで読み出しを遅延するよう伝えるヒントです。 この実装では、LAZYストラテジヒントが設定されたデータを先読みする ことを許可します。

Hibernate 3.6では遅延フェッチをビルド時に バイトコードを埋め込むことで実装しています。この実装では、 LAZYなプロパティがアクセスされるまで読み取られないよう、 追加のコードをコンパイル済みのクラスに追加します。このアプローチだと、 アプリケーションに対しては透過的ですが、N+1問題が起き得る、もう1つ 別の次元へ足を踏み入れてしまうことにもなります。つまり、 1つのselectで各レコードと各プロパティにも アクセスすることになる可能性があるのです。これは、JPAでは、必要な時に 先読みをランタイムで制御する方法を持たないので、特に危険だと言えます。

Hibernateのネイティブなクエリ言語HQLでは、この問題を FETCH ALL PROPERTIES句を使うことで解決しています。 (FewerColumnsInstrumentedHibernate.javaを参照)

select s from Sales s FETCH ALL PROPERTIES
 inner join fetch s.employee e FETCH ALL PROPERTIES
 where s.saleDate >:dt

FETCH ALL PROPERTIES 句は、コードがLAZYアノテーションを使って実装されて いても、Hibernateにエンティティを先読みするよう強制します。

選択した列のみをロードするには、エンティティの 代わりに、データ転送オブジェクト(DTO)を使う方法もあります。この方法は、クエリの中で オブジェクトを初期化してしまう、HQLやJPQLを使った 場合と同じように動作します。 (FewerColumnsJPA.java のサンプル)

select new SalesHeadDTO(s.saleDate , s.eurValue
                       ,e.firstName, e.lastName)
  from Sales s
  join s.employee e
 where s.saleDate > :dt

このクエリは、要求したデータだけを 選択し、エンティティではなく単純なJavaオブジェクト(POJO) であるSalesHeadDTOを返します。

実業務においてパフォーマンス問題を解決するには、 既存のコードにかなりの手を加えなければならない場合が多いでしょう。 そのようなコードを新しいクラスに移行するのは、恐らくやる意味のない ことです。しかし、バイトコードで解決するような実装は、元の パフォーマンス問題をさらに超えるかもしれないN+1問題の原因にも なり得るわけです。FewerColumnsJPA.java にある例では、問題の解決のためにエンティティやDTOを使う場合の 一般的なインタフェースを使っています。このインタフェースでは、 読み取りしかしない利用者側が入力にDTOを使うように簡単に変更できる ように、getterメソッドを定義しています。通常、何も更新しない処理が 現われた時にのみ、大きなハッシュ結合が使われるので、これで 十分と言えます。

もしこれから新しく実装を行うなら、FewerColumnsHibernate.java のサンプルにあるように、DTOあるいはシンプルなMapを 使ってデータを読み込むようにすることも考えられます。

Perl

DBIx::Classフレームワークは、エンティティマネージャとしては 動作しないため、継承によってエイリアシング 問題になることはありません。cookbookが この方法をサポートしています。以下のスキーマ定義は、2つのレベルで Salesクラスを定義したものです。

package UseTheIndexLuke::Schema::Result::SalesHead;
use base qw/DBIx::Class::Core/;

__PACKAGE__->table('sales');
__PACKAGE__->add_columns(qw/sale_id employee_id subsidiary_id
                            sale_date eur_value/);
__PACKAGE__->set_primary_key(qw/sale_id/);
__PACKAGE__->belongs_to('employee', 'Employees', 
           {'foreign.employee_id'   => 'self.employee_id'
           ,'foreign.subsidiary_id' => 'self.subsidiary_id'});

package UseTheIndexLuke::Schema::Result::Sales;
use base qw/UseTheIndexLuke::Schema::Result::SalesHead/;

__PACKAGE__->table('sales');
__PACKAGE__->add_columns(qw/junk/);

SalesクラスはSalesHeadから 派生したもので、足りない属性が追加されています。 どちらのクラスも必要に応じて使えます。テーブルのセットアップも 派生したクラス内で行う必要があることに注意しましょう。

prefetchで全従業員の詳細を 取りだすか、以下のように必要な列のみを取得します。

my @sales =
   $schema->resultset('SalesHead')
          ->search($cond
                  ,{      join => 'employee'
                   ,'+columns' => ['employee.first_name'
                                  ,'employee.last_name']
                   }
                  );

元のテーブル、つまりここでいうSalesHeadから 指定した列のみを読み込むことはできません。

DBIx::Class 0.08192は、以下のSQL文を出力します。この文は、 SALESテーブルの列全てを、 EMPLOYEESからは指定した属性のみを取り出します。

SELECT me.sale_id,
       me.employee_id,
       me.subsidiary_id,
       me.sale_date,
       me.eur_value,
       employee.first_name,
       employee.last_name
  FROM sales me
  JOIN employees employee
        ON( employee.employee_id   = me.employee_id
       AND  employee.subsidiary_id = me.subsidiary_id)
 WHERE(sale_date > ?)
PHP

Doctrineフレームワークのバージョン 2では、実行時に属性の 選択ができます。ドキュメントには、部分 オブジェクトは予期せぬ動作をする可能性があり、その リスクを喚起するためにpartialキーワードを 使うこと、と書かれています。また、プライマリキーの列を明示的に 選択する必要があります。

$qb = $em->createQueryBuilder();
$qb->select('partial s.{sale_id, sale_date, eur_value},'
          . 'partial e.{employee_id, subsidiary_id, '
                     . 'first_name , last_name}')
   ->from('Sales', 's')
   ->join('s.employee', 'e')
   ->where("s.sale_date > :dt")
   ->setParameter('dt', $dt, Type::DATETIME);

生成されたSQL文には、要求した列が含まれていますが、 SALESテーブルにもSUBSIDIARY_IDEMPLOYEE_IDが出現してしまっています。

SELECT s0_.sale_id       AS sale_id0,
       s0_.sale_date     AS sale_date1,
       s0_.eur_value     AS eur_value2,
       e1_.employee_id   AS employee_id3,
       e1_.subsidiary_id AS subsidiary_id4,
       e1_.first_name    AS first_name5,
       e1_.last_name     AS last_name6,
       s0_.subsidiary_id AS subsidiary_id7,
       s0_.employee_id   AS employee_id8
  FROM sales s0_
 INNER JOIN employees e1_
         ON s0_.subsidiary_id = e1_.subsidiary_id
        AND s0_.employee_id   = e1_.employee_id
 WHERE s0_.sale_date > ?

結果のオブジェクトは、完全なオブジェクトと互換性がありますが、 指定しなかった列は初期化されないままになります。しかも、これらの 列にアクセスしても例外は発生しません

警告

MySQLは、ハッシュ結合をサポートしていません(機能リクエストは#59025)。

Factbox

  • ハッシュ結合では、結合述語にインデックスは必要ありません。 代わりにハッシュテーブルを使います。

  • ハッシュ結合では、インデックスがそれぞれの 述語条件に作られている時のみ、インデックスを使います。

  • ハッシュテーブルのサイズは小さい方が パフォーマンスが良くなります。これは、水平方向(より少ない行)でも、 垂直方向(より少ない列)でも同じです。

  • ハッシュ結合は、結合述語に範囲条件が含まれている場合は 使えません(シータ 結合(theta joins))。

Photo of Markus Winand
Markus Winand氏は、開発者がSQLパフォーマンスを改善するお手伝いをしています。 彼は、SQL Performance Explainedの 著者でもあり、出張トレーニングhttp://winand.at/での リモート講義も 行っています。