解説

分散型データベースにおける結合演算と通信負荷の最適化

それぞれの結合方法の特徴

ア: 入れ子ループ法 (Nested Loop Join)

• 一方のテーブルの各行に対して、もう一方のテーブルを順に検索する方式
• 分散環境では大きい方のテーブルを全て転送する必要があり、通信コストが非常に大きい
• 異なるノード間での転送量が多いため通信負荷は高い

イ: インデックスジョイン法 (Index Join)

• 片方のテーブルのキーに対してインデックスを用いて効率的に結合を行う
• 分散環境で複数ノードにインデックスが存在するなら効果的だが、
• ネットワークを介したアクセスが頻繁になる場合があり、通信負荷が減るとは限らない

ウ: セミジョイン法 (Semi-Join)

• 結合キーのみを事前に片方のノードからもう一方へ送信し、結合に必要な行だけを選択してから本体データの転送を行う
• 不要なデータの転送を大幅に削減できる
• 通信負荷を最小化するためにデータ量を絞ることが可能
• 特に、テーブルの行数が双方で大きく差がない場合に効果的

エ: マージジョイン法 (Merge Join)

• 両テーブルをキーでソートしてから、ソート済みのデータをマージする方式
• 両方のテーブル全体を転送しなければならないため、通信負荷は高い
• データセットが大きい場合は特に不利

まとめ：なぜ「ウ: セミジョイン法」が正解なのか

• セミジョイン法は、結合に必要なキー情報だけを先に通信して、不要なデータの転送を防止する。
• 結果として、両テーブル間のデータ転送量（通信負荷）を最小化できる。
• 特に、問題の条件「表の行数が双方で大きく異ならない」という状況では、双方のキー情報の交換により必要な行が絞り込まれ、通信負荷削減効果が大きい。

参考：セミジョイン法の流れ

1. ノードAからノードBへ、テーブルAの結合キーのみを送信
2. ノードBで受け取ったキー情報を使って、テーブルBから対応する行を抽出
3. 抽出した行をノードAに送信し、実際の結合処理を行う