2019-01-01から1年間の記事一覧
MVCC は複数バージョンを持つことで、writer は reader をブロックせず、reader は writer をブロックしない writer がロックを取っていても reader は前のバージョンを読めば良いのでブロックされない 逆に read していても writer は新しいバージョンを作…
Timestamp Ordering Concurrency Control optimistic な方法 2PL がロックを使ってserializableになるのに対して、serializableでないならアボートしてリトライする トランザクションの実行時にタイムスタンプをふって、自分が触ったオブジェクトが、より新…
EFI system partition(ESP) の容量が足りなくて、ファームウェアアップデートが失敗したので拡張した。 今回は、ESP の後ろに別のパーティションが存在し、そのままではパーティションのサイズ変更ができなかった。 そのため、ESP を空き領域に作り直して内…
dependency graph はスケジュールを与えられたときにserializeかどうかを判定する方法 クエリをserializeに実行するにはどうするか？ lock を使う 2 Phase Locking grow phaseとshrink phaseがある 前者ではロックを取ること、後者は開放することしかできな…
トランザクションの性質としてACIDがある 一番簡単な方法はシングルスレッドで実行して、データベースファイルをコピーして、書き換えてスワップすること Aを守る方法としては shadow paging と logging がある schedule について serial schedule とはトラ…
B+-Treeのデリート時のロジックがいまいちわからなかったので、B+-Treeに最初にフォーマルに言及したというこの論文を読んだ。 この論文自体はサーベイみたいな感じで、B-Treeのアルゴリズムやそのバリエーションなどを記載している。 複数ユーザーが平行に…
query rewrite rule based optimizer 一般に可能なクエリの書き換えを行う selection は可能な限り先に行うと上で扱うデータ量が減る cost based optimizer 実データをもとにクエリプランを考える データの分布を一様分布として扱うと楽だけど実際はそんなこ…
特に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を保持してお…
データがメモリに収まらない場合を想定する Sorting 結果セットをページ内でソートしてディスクに書く 2つのソート済みページを取り出して比較してページを埋めて、溢れたらディスクに書く 利用するページは入力2つ、出力1つで3ページしか使わない Aggregati…
processing model iterator/volcano model タプルを一つ一つ返すモデル materialization model 一気にデータを返すモデル vectorized model バッチでデータを返すモデル optimization zone map page内のタプルにアグリゲーションを予め行ったページを記録し…
ここ最近のRDBはhashに次のものを使っている murmurhash cityhash farmhash clhash static hashing linear probe hashing コリジョンがあればその後ろの空きスロットを使う robin hood hashing 自分が入りたかったところからいくつ追い出されたかの値を持っ…
buffer poolの要素をframeという in memory heap file の page がそのままメモリに乗ったもの page table は in memory データ構造で page id から frame を参照するもの 複数スレッドから触るので適切に pin する コンテンションになりやすいのでよく分割さ…
ハードウェアページは典型的には4kb この単位で書き込む場合、all or nothingで書ける DBのファイルはheap fileをよく使う ページ単位で読み書きできるAPI heap fileの実装はpage dictionaryをよく使う link listだと効率が悪い page layoutはslotted pageを…
