CMU 15-445 Sorting + Aggregationsのメモ

• データがメモリに収まらない場合を想定する

• Sorting

  • 結果セットをページ内でソートしてディスクに書く
  • 2つのソート済みページを取り出して比較してページを埋めて、溢れたらディスクに書く
  • 利用するページは入力2つ、出力1つで3ページしか使わない

• Aggregation

  • ナイーブにやるならsortを使って結果を並び替えて、最後にシーケンシャルスキャンする
  • ソートが重いので、hashテーブルを使ってgroup byするキーごとに結果を作る
  • 結果がメモリに収まらないなら、ハッシュ関数h1を使ってタプルをバケットに分割してディスクに書く
  • 次にバケットごとにハッシュ関数h2を使って結果を作る