都内で働くSEの技術的なひとりごと / Technical soliloquy of System Engineer working in Tokyo

都内でサラリーマンやってます。SQL Server を中心とした (2023年からは Azure も。) マイクロソフト系(たまに、OSS系などマイクロソフト以外の技術も...)の技術的なことについて書いています。日々の仕事の中で、気になったことを技術要素関係なく気まぐれに選んでいるので記事内容は開発言語、インフラ等ばらばらです。なお、当ブログで発信、発言は私個人のものであり、所属する組織、企業、団体等とは何のかかわりもございません。ブログの内容もきちんと検証して使用してください。英語の勉強のため、英語の

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

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

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

f:id:koogucc11:20131001174843j:plain

 それでは本題に戻ります。まずは、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)

f:id:koogucc11:20130930090212j:plain

  実行プランの内容を見てみましょう。まず、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)

f:id:koogucc11:20131001094931j:plain

 実行プランの内容を見てみましょう。まず、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が採用される条件は、2つのテーブルがソート済みが条件です。各テーブルがソート済み出ない場合に 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 を記述することが可能です。(だと思います。)