これは、SQL Server InternalsProblematicOperatorsシリーズの一部です。最初の投稿を読むには、ここをクリックしてください。
SQL Serverは約30年以上前から存在しており、私はSQLServerをほぼ同じくらい長い間使用してきました。私はこの素晴らしい製品の何年にもわたって（そして何十年にもわたって！）そしてバージョンの多くの変化を見てきました。これらの投稿では、SQL Serverの機能や側面のいくつかを、時には歴史的な視点とともにどのように見ているかを紹介します。
前回、SQL Serverのクエリプランでのスキャン操作について、SQLServerの診断で問題が発生する可能性のある演算子として説明しました。スキャンは、有用なインデックスがないという理由だけで頻繁に使用されますが、実際には、インデックスシーク操作よりもスキャンの方が適している場合があります。
この記事では、問題があると見なされることがある別の演算子ファミリーであるハッシュについて説明します。ハッシュは非常によく知られているデータ処理アルゴリズムであり、何十年も前から存在しています。大学で最初にコンピュータサイエンスを勉強していたとき、私はデータ構造のクラスでそれを勉強しました。ハッシュとハッシュ関数の背景情報が必要な場合は、ウィキペディアでこの記事を確認してください。ただし、SQL Serverは、SQL Server 7までクエリ処理オプションのレパートリーにハッシュを追加しませんでした（余談ですが、SQLServerは独自の内部検索アルゴリズムの一部でハッシュを使用していました。Wikipediaの記事に記載されています。 、ハッシュは特別な機能を使用して任意のサイズのデータを固定サイズのデータにマップします。SQLは検索手法としてハッシュを使用して、各ページを任意のサイズのデータベースから固定サイズのメモリ内のバッファにマップします。 、以前は sp_configureのオプションがありました 「ハッシュバケット」と呼ばれ、データベースページをメモリバッファにハッシュするために使用されるバケットの数を制御できます。）
ハッシュとは何ですか？
ハッシュは、データを並べ替える必要のない検索手法です。 SQL Serverは、JOIN操作、集計操作（DISTINCTまたはGROUP BY）、またはUNION操作に使用できます。これらの3つの操作に共通しているのは、実行中にクエリエンジンが一致する値を探しているということです。 JOINでは、あるテーブル（または行セット）で、別のテーブルの行と一致する値を持つ行を検索する必要があります。 （はい、等式に基づいて行を比較していない結合を認識していますが、これらの非等結合はこの説明には関係ありません。）GROUP BYの場合、同じグループに含まれる一致する値が見つかり、UNIONの場合およびDISTINCTでは、それらを除外するために一致する値を探します。 （はい、UNION ALLは例外です。）
SQL Server 7より前は、これらの操作で一致する値を簡単に見つけることができる唯一の方法は、データが並べ替えられている場合でした。したがって、データを並べ替えられた順序で維持する既存のインデックスがない場合、クエリプランはプランにSORT操作を追加します。ハッシュは、内部ハッシュ関数からの同じ結果を持つすべての行を同じ「ハッシュバケット」に配置することにより、効率的な検索のためにデータを整理します。
ダイアグラムを含むSQLServerのハッシュJOIN操作の詳細については、SQLShackのこのブログ投稿を参照してください。
ハッシュがオプションになると、SQL Serverは、結合または集約の前にデータを並べ替える可能性を完全に無視しませんでしたが、オプティマイザーが検討する可能性になりました。ただし、一般に、ソートされていないデータに対してUNIONを結合、集約、または実行しようとしている場合、オプティマイザーは通常、ハッシュ操作を選択します。非常に多くの人が、プラン内のHASH JOIN（または他のHASH操作）は適切なインデックスがないことを意味し、ハッシュ操作を回避するために適切なインデックスを作成する必要があると考えています。
例を見てみましょう。最初に、インデックス付けされていない2つのテーブルを作成します。
USE AdventureWorks2016 GO DROP TABLE IF EXISTS Details;
GO
SELECT * INTO Details FROM Sales.SalesOrderDetail;
GO
DROP TABLE IF EXISTS Headers;
GO
SELECT * INTO Headers FROM Sales.SalesOrderHeader;
GO
Now, I’ll join these two tables together and filter the rows in the Details table:
SELECT *
FROM Details d JOIN Headers h
ON d.SalesOrderID = h.SalesOrderID
WHERE SalesOrderDetailID < 100;
Quest Spotlight Tuning Packは、ハッシュ結合が問題であることを示していないようです。 2つのテーブルスキャンのみが強調表示されます。
提案では、すべての非キー列をINCLUDED列として含む各テーブルにインデックスを作成することを推奨しています。私はそれらの推奨事項をめったに受けません（以前の投稿で述べたように）。 詳細のインデックスのみを作成します テーブル、結合列にあり、含まれる列はありません。
CREATE INDEX Header_index on Headers(SalesOrderID);
そのインデックスが作成されると、HASHJOINはなくなります。インデックスは、ヘッダーのデータを並べ替えます テーブルを作成し、SQL Serverがインデックスの並べ替え順序を使用して、内部テーブル内の一致する行を検索できるようにします。さて、計画の最も費用のかかる部分は、外側のテーブルのスキャンです（詳細 ） SalesOrderIDにインデックスを作成することで削減できます そのテーブルの列。読者の練習問題として残しておきます。
ただし、HASHJOINを使用した計画は必ずしも悪いことではありません。代替演算子（特別な場合を除く）はNESTED LOOPS JOINであり、通常、適切なインデックスが存在する場合に選択されます。ただし、NESTEDループ操作では、内部テーブルを複数回検索する必要があります。次の擬似コードは、ネストされたループ結合アルゴリズムを示しています。
for each row R1 in the outer table
内部テーブルの各行R2の for each row R2 in the inner table
if R1 joins with R2
return (R1, R2)
名前が示すように、NESTEDLOOPJOINはネストされたループとして実行されます。内側のテーブルの検索は通常、外側のテーブルの適格な行ごとに1回ずつ、複数回実行されます。対象となる行が数パーセントしかない場合でも、テーブルが非常に大きい場合（おそらく、数億、数十億、または行）、読み取る行が多くなります。 I / Oバウンドのシステムでは、これらの数百万または数十億の読み取りが実際のボトルネックになる可能性があります。
一方、HASH JOINは、どちらのテーブルに対しても複数の読み取りを行いません。外側のテーブルを1回読み取ってハッシュバケットを作成し、次に内側のテーブルを1回読み取り、ハッシュバケットをチェックして一致する行があるかどうかを確認します。各テーブルを1回通過する上限があります。はい、ハッシュ関数を計算し、バケットの内容を管理するために必要なCPUリソースがあります。ハッシュされた情報を保存するために必要なメモリリソースがあります。ただし、I / Oバウンドシステムを使用している場合は、メモリとCPUリソースに余裕がある可能性があります。 HASH JOINは、I / Oリソースが限られていて、非常に大きなテーブルを結合しているような状況では、オプティマイザーにとって妥当な選択です。
ハッシュ結合アルゴリズムの擬似コードは次のとおりです。
for each row R1 in the build table
begin
calculate hash value on R1 join key(s)
insert R1 into the appropriate hash bucket
end
for each row R2 in the probe table
begin
calculate hash value on R2 join key(s)
対応するハッシュバケットの各行R1の for each row R2 in the inner table
if R1 joins with R2
output (R1, R2)
end
前述のように、ハッシュは集約（およびUNION）操作にも使用できます。繰り返しになりますが、すでにデータがソートされている有用なインデックスがある場合、データのグループ化は非常に効率的に行うことができます。ただし、ハッシュがまったく悪い演算子ではない状況も多くあります。 詳細のデータをグループ化する次のようなクエリについて考えてみます。 ProductID によるテーブル（上記で作成） 桁。テーブルには121,317行あり、266の異なる ProductID 値。
SELECT ProductID, count(*)
FROM Details
GROUP BY ProductID;
GO
ハッシュ操作の使用
ハッシュを使用するには、SQL Serverは266個のバケットを作成して維持するだけで済みますが、これはそれほど多くはありません。実際、Quest Spotlight Tuning Packは、このクエリに問題があることを示していません。 
はい、テーブルスキャンを実行する必要がありますが、これはテーブル内のすべての行を調べる必要があるためです。スキャンは必ずしも悪いことではないことがわかっています。インデックスはデータの事前並べ替えにのみ役立ちますが、このような少数のグループにハッシュ集計を使用すると、有用なインデックスが利用できない場合でも、通常は妥当なパフォーマンスが得られます。
テーブルスキャンと同様に、ハッシュ操作は、計画に含めるべき「悪い」演算子と見なされることがよくあります。有用なインデックスを追加してハッシュ操作を削除することでパフォーマンスを大幅に向上できる場合がありますが、それが常に当てはまるとは限りません。また、大幅に更新されるテーブルのインデックスの数を制限しようとしている場合、ハッシュ操作は必ずしも「修正」する必要があるとは限らないため、ハッシュを使用するようにクエリを残すことは合理的なことである可能性があることに注意してください。やること。さらに、I / Oバウンドシステムで実行されている大きなテーブルに対する特定のクエリでは、実行する必要のある読み取りの数が限られているため、ハッシュは実際には代替アルゴリズムよりも優れたパフォーマンスを提供できます。確実に知る唯一の方法は、クエリとデータを使用して、システムのさまざまな可能性をテストすることです。
このシリーズの次の投稿では、クエリプランに表示される可能性のある他の問題のある演算子について説明しますので、しばらくしてからもう一度確認してください。