Neunomizuの日記

俺だけが俺だけじゃない

# CMU DB 10. Sorting + Aggregations

CMU DB
tags: CMU DB

また宿題が...(未だに手が付けられないが，私はやるのでしょうか…？)

授業

QUERYは木構造になっており，葉の結果が根の方に上がっていき，根の結果がQUERYの結果．

external merge sort

テーブルのtupleは特定の順序を持っていないが，クエリは特定の順序でtupleを手に入れたい．

  • 複製して消すことはありふれている
  • B+Treee indexに順序付けされたtupleを積む方が早い
  • 集約

external merge sortはrunsというものにデータを分けて，それらを別々にソートする

  • sorting
    • 主記憶に入るデータのブロックをソートし，ディスク上のファイルへ書き戻す
  • merging
    • subファイルを単一の大きなファイルに組み合わせる

N-way external merge sortのNは各passで新しいrunに統合するrunの数

データはNpagesに分けられ，DBMSは有限のBbuffer pagesを入出力データを保持するために持つ．以下は$N = 2$のとき

  • pass #0
    • テーブルのBpagesをメモリに読み込む
    • ページをソートしてrunに入れ，ディスクに書き戻す
  • pass #1, 2, 3...
    • 再帰的にrunのペアを二倍の長さrunに統合する
    • 3つのbuffer pagesを使う(2...input pages, 3...output pages)

passの数は$1 + \lceil \log_2{N} \rceil$

全体でのI/Oの費用は$2 N \cdot (\text{number of passes})$

Nは増やせる．bufferを複数持って，並列処理をすれば(特にI/Oの時間を)より効率化できる

  • pass #0
    • BBuffer pagesを使う
    • $\lceil N / B \rceil$の大きさがBの整列済みrunを作るう
  • pass #1, 2, 3...
    • B - 1のrunを統合する(つまりK-way merge)

Passの数は$1 + \lceil \log_{B-1}{\lceil N / B \rceil} \rceil$

全体でのI/Oの費用は$2 N \cdot (\text{number of passes})$

整列されなければならないテーブルがすでにB+Tree indexをソートする性質に持っていれば，それがsortを高速化するのに使える．

木の葉ページを走査するだけで期待されたsort順でのtupleを手に入れる．

  • clustered B+Tree
  • unclustered B+tree

を考慮する必要がある

clustered B+Tree

左端の葉へ走査し，全ての葉のページからtupleを手に入れる．

計算コストがなく，全てのディスクアクセスが連続的なので，external sortingよりもいつも良い．

unclustered B+Tree

データを持っているページへのポインタを追う．

一般的にデータレコードにつき，1回のI/Oがあるのでほとんどいつも悪い考え

aggregations

tupleを単一のスカラー値にする．sortingとhashingという実装がある．

sorting

hashing

データが順序付けられている必要がないときは，Hashingがbetter

複製を消す必要があるだけで，順序付ける必要はない．また，sortingよりも計算的に安価．

DBMSがテーブルを読んだ時，そのとき限りのhash tableを作る．各recordに対して，hash tableにエントリーがすでにあるかどうかを調べる．

もし，全てがメモリに収まったらeasy!もし，DBMSがデータをディスクに入れなければならないとき，もっと賢く成る必要がある．

  • phase1: partition
    • hash keyに基づいて，bucketにtuplesを分ける
    • いっぱいになったらディスクに書き戻す
  • phase2: rehash
    • in-memory hash tableをそれぞれのpartitionのために作り，合体したものを考える

結論

それぞれの場合でされた最適化に応じてsortingとhashingという選択肢がある．

感想

アルゴリズムとデータ構造をは真面目に勉強するべき以外の感想がない．