ハッシュJOIN

ハッシュJOINは、リレーショナルデータベースや分散処理基盤において、二つのテーブルをキー属性に基づいて結合する手法の一つです。結合対象のうち小さい方（ビルド側）をメモリ上にハッシュテーブルとして構築し、もう一方（プローブ側）の各行のキーにハッシュ関数を適用して対応するバケットを検索し、一致すれば結合結果を生成します。この方式は事前にデータをソートする必要がなく、キーの分布が均等であれば O(N) に近い計算量で処理できる点が特徴です。ハッシュテーブルの構築に必要なメモリはビルド側のデータサイズに比例しますが、プローブ側は逐次走査のみで済むため、ディスクI/Oを抑制できる利点があります。また、ハッシュ関数の選択やバケットサイズの調整により衝突率を低減させ、性能を最適化することが可能です。