Rustで実装！ 作って学ぶRDBMSのしくみ を読んだ感想とメモ
はじめに
WEB+DB PRESS Vol.122 の特集『Rustで実装！ 作って学ぶRDBMSのしくみ』を読みました。
この特集は、出版社のサイトにも説明があるように、(実際の RDBMS に比べて) わずかな機能のみをサポートする小さな RDBMS を作りあげることで RDBMS の仕組みを知ろうという特集です。
説明が簡潔でソースコードの例示がたくさんあり読みやすかったです。ソースコードの全体 https://github.com/KOBA789/relly を見てみるとより理解が深まりそうです。
読むにあたって最低限必要な準備は
でしょうか。
以降は各章のメモです。
第 1 章: RDBMS を作ろう
- よくある RDBMS のアーキテクチャは、上から (RDBMS を使う側に近いところから) 、構文解析器/クエリプランナ&実行計画/クエリエクスキュータ/アクセスメソッド/バッファプールマネージャ/ディスクマネージャ
第 2 章: ディスクマネージャの実装
- ヒープファイル
- ディスクマネージャが読み書きするファイルのこと
- ディスクマネージャは「ページ」ごとにアクセスする
- ページ
- (Rust) New Type パターン
第 3 章: バッファプールマネージャの実装
- ディスクアクセス遅すぎ問題 (メモリアクセスに比べると)
- バッファプールマネージャは一度ディスクアクセスで得たページの内容を覚えておく (キャッシュする)
- 実は、ほとんどのファイルシステムにもキャッシュ機構がある
- バッファ: ページのデータ (ただのバイト列
[u8; 4096]) + α の情報 - バッファプール: バッファを並べたもの
- バッファプールがいっぱいになったとき、もう使われてないバッファのうち再利用しなさそうなバッファを捨てる
- Clock-sweep アルゴリズム: PostgreSQL で使われている
- 直近でたくさん貸し出していたバッファは捨てられにくくなっていそう
第 4 章: B+Tree の観察
- B-Tree: 平衡 N 分木のひとつ
- 実際はいろいろとバリエーションがある (B+Tree など)
- 木のリーフノードは (ひとつだけデータを持っているわけではなく)
Vec<(Key, Value)>のような感じで、さらにKeyの順に並ぶように保っている- 中間ノードは同じく
KeyでソートされていてVec<(Key, 子へのポインタ)>を持つ
- 中間ノードは同じく
- ほぼすべての RDBMS で B+Tree が使われている (!)
- key に対応する value を検索: 中間ノードではどの子に降りるべきかが二分探索で分かり、リーフノードでもやはり二分探索できる
- key-value のペアを挿入
- ひとつのノードをひとつのページに対応付けて使う
- 検索・挿入時にたどるノード数 (= ページ数) はたかだか木の高さ
第 5 章: テーブルの実装
- テーブル (行と列からなる) を B+Tree に格納する
- 各行のプライマリーキー列を B+Tree の key に、それ以外の列を value に
- プライマリーキー (複合キーもありうる) → B+Tree key のエンコード方法によってはソート順がこわれる
- かしこいエンコーディング: Memcomparable format (すごそう)
- もしくは、B+Tree の比較関数をカスタムできるようにする
- クエリエクスキュータ
- テーブルをプライマリーキーで検索するもの・列の値で行をフィルタするもの、など
- 実行計画
- クエリエクスキュータの組み合わせ方を示す
idがプライマリーキーだとしてSELECT * WHERE id >= 'w' AND first_name < 'Dave'の場合は、プライマリーキーで検索したあとfirst_nameでフィルタする、など
