- 特にequal joinを扱う
- N =num of outer table blocks, M = inner
- nested loop join
- simple nested loop join
- outer table のタプルごとにinterのblockを舐める
- block nested loop join
- outer tableのblockごとにinterのblockを舐める
- 仮にouterを保持しておくバッファがあるなら、ioコストはN+Mになる
- index nested loop join
- innerがindexを持っているとすると、probeにインデックスが使えるのでioコストが減る
- simple nested loop join
- sort merge join
- 2-phaseでやる
- phase1は2つのテーブルをソートする
- pahse2で2つのテーブルの突合を行う
- コストはN+M+sort
- hash join
- basic hash join
- outerのハッシュテーブルを作る
- コストはN+M
- grace hash join
- basicだとouterのハッシュテーブルがメモリに収まらないといけない
- 東大のgraceというシステムで開発されたやつ
- outer, innerのハッシュテーブルを作り、それをバケットに分割してディスクに書く
- コストは3(N+M)
- basic hash join