MS SQL

プログラミング

MS SQLを使用しての結合アルゴリズムを解説(loop&merge&hash)

オプティマイザによる最適化は、けっして完璧ではありません。データの分布が偏っていたり、統計情報が不正確だったりなんてことも十分にあり得ます。

SQLコーディングを行う際には、クエリのパフォーマンスを低下させないためにも、ある程度の工夫は必要となってくるでしょう。

今回は、SQLの中でも最も負荷のかかる処理でもあります結合アルゴリズムに焦点を当てていきます。使用データベースはSQL Server 2017 Expressです。

ネスト・ループ結合

loop

出典:チューニング ~ SQLチューニングを実施する ~

ネスト・ループ結合とは、二重ループを回してテーブルを結合する方法です。

一例として、AとBの二つのテーブルがあるとします。Aの各レコード毎にBの全レコードとの比較を行い、項目の値が一致するものを探します。その為、コストは二つのテーブルのレコード数の積に比例します。

一般的には、インデックスが設定されていない小さなテーブルとインデックスが設定されている大きなテーブルの二つを結合する場合に利用することが多いです。

マージ結合

マージ

出典:チューニング ~ SQLチューニングを実施する ~

マージ結合では、前提として二つのテーブルを結合する項目についてあらかじめソートしておく必要があります。

そして,両テーブルのレコードに対して持たせたポインタを,レコードの上から下へと順に走査させながら項目の値が一致するものを探します。その為、レコードの走査が1回で済むのがポイントです。

ハッシュ結合

ハッシュ

出典:チューニング ~ SQLチューニングを実施する ~

ハッシュ結合では、まずはレコード数の少ないテーブルの結合条件列をハッシュ関数にかけ、メモリ上にハッシュテーブルを作成します。

そしてもう一方のテーブルの結合条件列もハッシュ関数にかけ、結合できるかをハッシュテーブルで確認します。ハッシュ値が等しいレコードを結合して結果を返してくれます。

注意点として挙げられるのが、ハッシュ結合では、結合条件に等価条件(=)しか指定できません。その為、大量レコード、あるいは大部分を結合する場合にのみ有効な結合方法だと言えます。

また、上述のマージ結合と違って事前のソート処理は不要です。

まとめ

ネスト・ループ結合<マージ結合<ハッシュ結合の順で処理速度が上がります。

しかし、二つのテーブルのレコードの数が極端に違う場合や、両方のレコードの数が十分小さい場合では,必ずしもこの順番になるとは限りません。

また、「処理がすべて終了するまでの時間を短くするより,とにかく最初に検索条件に合致した1レコードを返したい」というような場合には,ネスト・ループの方が向いていると言えるでしょう。

-プログラミング
-,

© 2020 秀凛堂