# CMU DB 11. Joins Algorithms - Neunomizuの日記

tags: `CMU DB`

雨の日の次の日の花粉症はひどいですね…生物兵器ですあれは…

授業

JOINが必要な理由．情報の繰り返しを避けるため．JOINにより情報の損失なしで元々のtuplesを再構築できる．

inner equijoinアルゴリズムで組み合わせる2つのテーブルに注目する．

一般的に，小さい方のテーブルは左のテーブル(outer table)にいつも来てほしい．

JOIN

output
- join opがクエリの木において，親のopにどのデータを放出するか
- 比較するattribute以外に他のデータを組み合わせるもの，record idを組み合わせるものがある
- 後者はlate materializationと呼ばれ，クエリで必要のないものをコピーする必要がない
cost analysis criteria
- どのようにあるjoin algorithmが他のものよりも優れていると決めるのか
- I/Oの計算コストを考える
RにはMpagesがあり，mtuplesがある
SにはNpagesがあり，ntuplesがある

と仮定する．

stupid nested loop join

$M + (m \cdot N)$の計算コストが必要

foreach tuple r in R:
    foreach tuple s in S:
        emit if r and s match

block nested loop join
outer tableには小さいものを

コストは#M + (M \cdot N)$

foreach block Br in R:
    foreach block Bs in S:
        foreach tuple r in R:
            foreach tuple s in S:
                emit if r and s match

B-2のBufferを持つ時はコストは$M + (\lceil M / (B - 2) \rceil \cdot N)$

合致するinner tableとのindexを使えば，連続的なスキャンを避けられる(線形計算量を改善できる)．hash tableやB+ Treeを使えば良い

index nested loop join

コストは

コストは$M + (m \cdot C)$

foreach tuple r in R:
    foreach tuple s in Index(r = s):
        emit if r and s match

sort merge join
phase #1
- 両方のテーブルをjoin keyでソートする
- merge sort algorithmが利用可
phase #2
- 2つの整列済みのテーブルを見ていく
- join typeによってはbacktrackが必要

コストは

R: $2M \cdot (\log M / \log B)$
S: $2N \cdot (\log N / \log B)$
merge sort: $(M + N)$
合計: $Sort + Merge$
最悪計算コストは$(M \cdot N) + (sort cost)$
basic hash join algorithm
- #1
  - ハッシュ関数h1でouter tableをハッシュ化する
- #2
  - ハッシュ関数h2でinner tableをハッシュ化し，合致するtupleを探す

build hash table HTr for R foreach tuple s in S output if h1(s) in HTr

hash table values
- full tuple
  - より多くのメモリが必要
- tuple identifier
  - 必要ないなら持ってこない

bloom filterを使う．←前これに関する記事を作ったのでそれを下に貼る

propyon.hateblo.jp

grace hash join

build phase
- 両方のテーブルのjoin attributeをそれぞれ別のpartitionsに入れる
probe phase
- それぞれのテーブルの関連s似たpartitionsのtuplesを比較する

foreach tuple r in bucketR0:
    foreach tuple s in bucketS:
        emit if match(r, s)

もし，bucketsがメモリに載らなければ，載るようにテーブルを分割し，hash関数h2 != h2を使い別のbucketRiを作る．

そのレベルでの他のテーブルのbucketのtupleを調べる．

コストは$3(M + N)$

もし，outer tableの大きさが分かれば，静的なハッシュテーブルを使え，分からなければ動的なものを使うか，overflow pagesを使う．

結論

ソートするよりもハッシュした方がほとんどいつも良い．

均質でないデータではソートの方が良い．結果がソートされる必要があるときはソートの方がいい．

良いDBMSは両方を使っている．

感想

ハッシュに関してLeetCodeですごく使うので，こういう所で使うのかとDBMSの授業は非常に思う．

tags: CMU DB

授業

結論

感想

tags: `CMU DB`