Nested に続いて Hash および Merge について説明してみる

　『 SQL Server の実行プランを少しだけ詳しく説明したみた 』で Nested Loop に関して説明しました。今回は、 Hash , Merge について説明します。

※関係ないですけど、新幹線の移動中はブログを書くのにもってこいの環境です。

　それでは本題に戻ります。まずは、Hash です。実行プランを Hash に変更するため、OPTION句を 『 OPTION ( HASH JOIN ) 』 に変更します。

USE AdventureWorks2012
SET STATISTICS PROFILE ON
SELECT * FROM [Production].[Product] a 
	INNER JOIN [Production].[ProductInventory] b 
		ON a.ProductID  = b.ProductID OPTION(HASH JOIN)

 　実行プランの内容を見てみましょう。まず、3行目です。PK_Product_ProductID を Clustered Index Scan しており、実行回数は 1回です。

|--Clustered Index Scan(
OBJECT:([AdventureWorks2012].[Production].[Product].[PK_Product_ProductID] AS [a]))

 　次に、4行目です。PK_ProductInventory_ProductID_LocationID を Clustered Index Scan しており、実行回数は 1回です。

|--Clustered Index Scan(
OBJECT:([AdventureWorks2012].[Production].[ProductInventory].[PK_ProductInventory_ProductID_LocationID] AS [b]))

 　最後に4行目です。Hash Match になっています。

|--Hash Match(Inner Join, HASH:([a].[ProductID])=([b].[ProductID]))

　Hash 方式は、片方のテーブルデータをメモリ中にハッシュ化し、もう片方のテーブルのキー情報からハッシュコードを算出し、メモリに展開されているハッシュテーブルから結合データを探す方式です。しかし、経験上、Hash Match が出現した場合は、あまりいい兆候ではない (もちろん、すべて悪いとは言い切れません。場合によっては Hash の方が高速の場合もあります。) と思っています。また、メモリ中にハッシュテーブルを展開するため、CPUコストが他の方式より多く必要とするのも特徴です。それでは、ロジックにしてみます。

ProductionProductCollection ppc = ....;
ProductionProductInventoryCollection ppic = .....;

//Productテーブルの内容をメモリに保持する。
var ppcHash = new Dictionary<string, ProductionProductRecord>();

//ppcのキー情報を使用して、Hashテーブルをメモリ中に作成する。
//ロジックが長くなってしまうので、Hash算出は手を抜いています。(すいません。)
foreach ( var ppc_record in ppc ) {
    //キーからハッシュコードを算出し、そのコードをキーとして、オブジェクトを追加していく。
    ppcHash.Add ComputeHash(ppc_record.ProductID), ppc_record
}

//メモリ中のデータから、データを取得する。
foreach ( var ppic_record in ppic ) {
    if ( ppcHash.Exists ( ComputeHash ( ppic.ProductID ) ) ) {
        //レコードを生成して返す。みたいな感じです。
    }
}

　次は Merge です。Merge に変更するため、OPTION句を 『 OPTION ( MERGE JOIN ) 』 に変更しています。

USE AdventureWorks2012
SET STATISTICS PROFILE ON
SELECT * FROM [Production].[Product] a 
	INNER JOIN [Production].[ProductInventory] b 
		ON a.ProductID  = b.ProductID OPTION(MERGE JOIN)

　実行プランの内容を見てみましょう。まず、3行目です。PK_Product_ProductID を Clustered Index Scan しており、実行回数は 1回です。Hash Match の場合と異なり、ORDERED FORWARD というキーワードが付加されています。これは、一行目から順に読み込むという意味です。

|--Clustered Index Scan(
OBJECT:([AdventureWorks2012].[Production].[Product].[PK_Product_ProductID] AS [a]), ORDERED FORWARD)

　次は、4行目です。PK_ProductInventory_ProductID_LocationID を Clustered Index Scan しており、実行回数は 1回です。3行目と同じく、ORDERED FORWARD というキーワードが付加されています。

|--Clustered Index Scan(
OBJECT:([AdventureWorks2012].[Production].[ProductInventory].[PK_ProductInventory_ProductID_LocationID] AS [b]), ORDERED FORWARD)

　最後に、2行目です。Mergeが採用される条件は、２つのテーブルがソート済みが条件です。各テーブルがソート済み出ない場合に MERGE を指定すると、対象テーブルに対してソート処理が発生し、思わぬレスポンス悪化を招くことになります。

|--Merge Join(
Inner Join, MERGE:([a].[ProductID])=([b].[ProductID]), 
RESIDUAL:([AdventureWorks2012].[Production].[ProductInventory].[ProductID] as [b].[ProductID]=[AdventureWorks2012].[Production].[Product].[ProductID] as [a].[ProductID]))

　Merge を今回の例で説明すると下記の通りです。

　[AdventureWorks2012].[Production].[ProductInventory] を上から順に読み込んで、[AdventureWorks2012].[Production].[ProductInventory] の ProductID と [AdventureWorks2012].[Production].[Product] の ProductID を比較します。比較した条件によりデータの取得方法が異なってきます。

• [ProductInventory].[ProductID] = [Product].[ProductID] の場合
  [ProductInventory] と [Product] テーブルをJOINする。 Product テーブルのデータを一つ進める。
• [ProductInventory].[ProductID] < [Product].[ProductID] の場合
  ProductInventory テーブルのデータを一つ進める。
• 上記以外の場合
  Product テーブルのデータを一つ進める。

　それでは、ロジックにしてみましょう。

ProductionProductInventoryCollection ppic = .....;
ProductionProductCollection ppc = ....;

int ppic_counter = 0;
int ppc_counter = 0;

//どちらも最後の要素まで到達したら while 文を抜けます。
while ( ppc.Count == ppc_counter && ppic.Count == ppic_counter ) {
    //それぞれのレコードを取得する。
    var ppic_record = ppic[ppic_counter];
    var ppc_record = ppc[ppc_counter];
    //値が同じとき
    if (ppc_record.ProductID == ppic_record.ProductID) {
        ppc_counter++;
        //JOINしてデータを返す。
    //ProductProductionのレコードの値のほうが小さいとき
    else if (ppc_record.ProductID < ppic_record.ProductID) {
        //ProductionProductInventory コレクションを一つ進める。
        ppic_counter++;
    //上記以外のとき
    } else {
        //ProductionProduct コレクションを一つ進める。
        ppc_counter++;
    }
}

　実行プランの読み方、Nested・Hash・Merge アルゴリズムを十分理解し、業務システムで構築される SQL に適用することで、高速且つ I / O 負荷の低い SQL を記述することが可能です。(だと思います。)