Join - Evaluating Relational Operation - Database Management Systems
Database Management Systemsの14章。
マインドマップから再構成したまとめ
Nested Loop Join
- simple, but slow
- I/O 多すぎる
Block Nested Loop Join
- 前提：B バッファページ利用可能
- R を B に読み込み、S の tuple と比較
- R を読み込むのではなく B にメモリハッシュを構築して比較する方法もある
Index Nested Loop Join
- S に使える Index がある
- tuple r が s in S と join されるかを index を利用して確認する
- コスト
- R の読み込み
- r （1 tuple）につき 1-4 I/O 。Index の種類による
- r （1 tuple）につき 1 I/O 。データを読む。（clustered だと必要ない）
Sort Merge Join
- R と S どちらも Sort して Merge する
- 片方が既に Sorted の場合にチャンス
- コスト
- ソートは O(MlogM) + O(NlogN)
- Merge は M + N
Hash Join
- R と S をそれぞれ h で別々に partitioning
- partitioning Ri に対して h2 でオンメモりハッシュ構築
- Si の tuple を h2 して比較
- コスト
- R, S Scan and Write
- Partition scan once
- もっとメモリがあれば
- オンメモりハッシュを直接作る
- そうすれば partition の write が節約できる
所感
- 状況による Join 方法の選択の部分が感覚として理解できていない。それはまた今度かな。
