ミニRDBMSを作ってみた
『WEB+DB PRESS Vol.122』の特集「作って学ぶ RDBMS のしくみ」を読みながら、誌面のコードを動かしてミニRDBMSを作りました。10時間くらいで動作確認までできて、頭の中で知っていたRDBMSの仕組みを、手を動かしながら実感できたのが良かったです。
上記はVol.122のリンクですが、今購入するならVol.1～136がセットになった以下の総集編がおすすめです。
ミニRDBMS自作の動機
私は数年おきに低レイヤー寄りの領域を学び直し、エンジニアとしての幅を少しずつ広げてきました。以前、NAND回路から OS までを自作する『コンピュータシステムの理論と実装』に取り組んだときは、手を動かして作る体験が大きな学びにつながったため、次も「何かを作る」形で挑戦したいと考えていました。ちょうど最近は仕事でデータベースや DWH に触れる機会が増え、データベースに強くなりたいという動機もありました。しかし、評価の高い『Database Design and Implementation』は英語で分量も多く、最後まで読み切る自信がありませんでした。そこで、日本語で約 30 ページという手頃な分量の特集「作って学ぶ RDBMS のしくみ」に目を留め、これなら気軽に試せそうだと感じたのが今回のミニ RDBMS 自作に取り組んだきっかけです。
ミニRDBMSの機能
ご覧の通り、ミニRDBMSは学習用途の非常に限られた機能のみを備えています。
ミニRDBMSの主要な機能
- テーブル作成(列名・型を指定)
- 行の挿入
INSERT - 行の検索
SELECT - セカンダリインデックス
ミニRDBMSにない機能
- テーブル削除、定義変更、複数テーブル
- 行の削除
DELETE - 結合
JOIN - トランザクション
前提知識
ざっくり以下の単語がわかるとスムーズに読み進められると思います。
- メモリ、ヒープ、ページ
- ファイルディスクリプタ
- B+Tree
学習メモ
RDBMS のアーキテクチャ
- 構文解析器(Parser): SQL を解析し、抽象構文木(AST) を作る
- クエリプランナ(Planner): AST から実行計画(Plan) を作る
- クエリエクスキュータ(Executor): 実行計画に従いアクセスメソッドを呼び出す
- アクセスメソッド: B+Tree などのディスク上データ構造をたどって結果を返す
- バッファプールマネージャ: ディスクI/Oの遅さを隠すため、ページをメモリにキャッシュする
- ディスクマネージャ: ページ単位でファイルの読み書きを担当する
ディスクマネージャ
- ヒープファイル(固定長ページの集合)を扱う
- 新規ページ確保と既存ページの read/write を担当
バッファプールマネージャ
- バッファプールにページをキャッシュ
- ページテーブルで「ページID → バッファ位置」を高速検索
- 空きがないときは Clock‑sweep アルゴリズムで破棄ページを決める
クエリ
- テーブル本体は PK を使ってクラスタードインデックス化(キー: PK、値: その他列)
- Memcomparable Format でエンコードし、順序を保つ
- 実行計画ノードとエクスキュータの実装はほぼ 1:1 対応
セカンダリインデックス
- ユニークインデックス: キーにセカンダリキー、値に PK を入れる
- ノンユニークインデックス: キーに「セカンダリキー + PK」を連結
- 検索は「セカンダリインデックス → PK でテーブル検索」の流れでフルスキャンを回避
感想
今回の取り組みで得た知識は、そのままデータベースの公式ドキュメントや技術記事を読む際に役立ちそうだと感じています。とくにセカンダリインデックスを実装してみたことで、検索が一気に速くなる一方、書き込み処理が増えるというトレードオフを肌で理解できました。最初は B+Tree を直接たたいて手続き的にクエリを実行していたのですが、あとからクエリエクスキュータとクエリプランナを用意して B+Tree の存在を隠せるようにしたときの “抽象化の進む感じ” がとても爽快でした。今後はこの経験を踏まえてDBのマニュアルを読み込んだり、気になっている書籍である『SQLパフォーマンス詳解』をじっくり読んだりして、DBへの理解をさらに深めていきたいと思います。
Discussion