2019-10-26

The Ubiquitous B-Treeを読んだ

B+-Treeのデリート時のロジックがいまいちわからなかったので、B+-Treeに最初にフォーマルに言及したというこの論文を読んだ。この論文自体はサーベイみたいな感じで、B-Treeのアルゴリズムやそのバリエーションなどを記載している。複数ユーザーが平行に利用するロッキングについても記述しているがちゃんと読み込めなかった。この辺は参照している論文をちゃんと読んだほうが良さそう。

もともとB-Treeはファイルシステムの実装のために考案されたらしい。古い時代の話なので、ディスクのアームがなんちゃらとかシリンダがなんちゃらとか書いてあって面白い。

IBMはファイルシステムとしてB-Treeをインデックスとして使うVSAMというのを作ったということが書いてあった。

2019-10-05

CMU 15-445 Query Optimization

query rewrite
- rule based optimizer
- 一般に可能なクエリの書き換えを行う
- selection は可能な限り先に行うと上で扱うデータ量が減る
cost based optimizer
- 実データをもとにクエリプランを考える
- データの分布を一様分布として扱うと楽だけど実際はそんなことない
- 統計情報はヒストグラムを使ったりする
- この頃のシステムだとサンプリングする
- 一部のページからサマリーテーブルを作っておいて、コストを見積もる

2019-09-28

CMU 15-445 Joins

特に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コストが減る
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)

2019-09-21

CMU 15-445 Sorting + Aggregationsのメモ

データがメモリに収まらない場合を想定する
Sorting
- 結果セットをページ内でソートしてディスクに書く
- 2つのソート済みページを取り出して比較してページを埋めて、溢れたらディスクに書く
- 利用するページは入力2つ、出力1つで3ページしか使わない
Aggregation
- ナイーブにやるならsortを使って結果を並び替えて、最後にシーケンシャルスキャンする
- ソートが重いので、hashテーブルを使ってgroup byするキーごとに結果を作る
- 結果がメモリに収まらないなら、ハッシュ関数h1を使ってタプルをバケットに分割してディスクに書く
- 次にバケットごとにハッシュ関数h2を使って結果を作る

2019-09-14

CMU 15-445 Query Processingのメモ

processing model
- iterator/volcano model タプルを一つ一つ返すモデル
- materialization model 一気にデータを返すモデル
- vectorized model バッチでデータを返すモデル
optimization
- zone map
  - page内のタプルにアグリゲーションを予め行ったページを記録しておいて使う
- late materialization
  - タプルじゃなくてオフセットを返して、最後にタプルを取得する
multi-index scan
- 複数のインデックスを使える場合、それぞれからレコードID取り出して or 条件の場合和集合を取り、and 条件の場合は積集合を取る
- postgresql は bitmap index scan とよんでいる
index scan page sorting
- クラスタインデックスではない場合、indexが参照しているページの順番がindexの内容と異なっている場合がある
- このときバッファプールが小さいと何度もリードが発生する
- これを防ぐためにpage idを最初に取得してソートしてページを読む

2019-08-24

CMU 15-445 Hash Tablesのメモ

ここ最近のRDBはhashに次のものを使っている
- murmurhash
- cityhash
- farmhash
- clhash
static hashing
- linear probe hashing
  - コリジョンがあればその後ろの空きスロットを使う
- robin hood hashing
  - 自分が入りたかったところからいくつ追い出されたかの値を持っておく
  - コリジョンしたら上記の値を見比べて小さい値のものを追い出す
  - もともと入りたかった場所からできるだけ離れないようにしている感じ
  - ブランチミスとかデータコピーとかがあって linear probe hashing のほうがうまく行くらしい
- cuckoo hashing
  - 複数のハッシュを使う
  - 片方でコリジョンしたら別のハッシュを試す
  - ぶつかりまくると無限ループになるので、テーブルサイズを増やす
dynamic hash table
- static だと要素があふれると全部作り直しなのでできるだけさける
- extendible hashing
  - あるバケットが溢れたら、そのバケットをsplitする
  - どのバケットを使うかを指し示すグローバルなスロットを用意する
    - このスロット数はsplitが起こるたびには先頭ビットの数が増えるので、倍々ゲームで増える
- linear hashing
  - 次にsplitするバケットを指す split pointer を用意する
  - 何らかの基準で split pointer のバケットをsplitする
  - このときにハッシュ関数をもう一つ用意する
  - もとのハッシュ関数で split pointer が指していたバケットだったら、新しいハッシュを使う
  - この方式だとバケットを指すスロットが線形に増える

linear hashing の挙動の理解が怪しいがモチベーションはわかった。

2019-08-24

CMU 15-445 Buffer Poolsのメモ

buffer poolの要素をframeという
- in memory
- heap file の page がそのままメモリに乗ったもの
page table は in memory データ構造で page id から frame を参照するもの
- 複数スレッドから触るので適切に pin する
- コンテンションになりやすいのでよく分割されること
  - index/data で分けるとか、無関係に分けたりもする
page eviction
- LRU
- CLOCK
  - frameをリングに並べて時計の針が回るように走査する。アクセスビットが立ってなければevictできる。
- LRU-K
  - アクセスヒストリを覚えておくことで、シーケンシャルスキャンでのevictionを軽減する。
  - たいていkは1が使われる