RDBMS実装 - 第2版アーキテクチャと実装ロードマップ

はじめに

あなたが書いた最終アーキテクチャは「最終形としては良い」ですが、最小RDBMSの学習実装としては重すぎます。

SQLite や DuckDB の内部も、最終的には parser / planner / executor / storage / page cache / B-tree / transaction という層に分かれますが、実際に理解しながら作るなら SQL → 実行 → 永続化 の順で薄く積み上げる方が圧倒的に進めやすいです。SQLite は B-tree と pager/page cache を中核に持ち、DuckDB も parser と binder/planner/executor を段階分離しています。

1. 最初に決めるべきこと

学習用の最小版では、最初から以下を捨てます。

JOIN
GROUP BY
ORDER BY
UPDATE
DELETE
複数テーブル結合
オプティマイザ
MVCC
本格WAL
バッファプール置換アルゴリズム
SQL方言のフル対応

代わりに、最初の完成目標をこれに固定します。

CREATE TABLE users (id INT, name TEXT);
INSERT INTO users VALUES (1, 'Alice');
SELECT * FROM users;
SELECT * FROM users WHERE id = 1;

この範囲でも、AST、実行計画、行表現、ページ、永続化、B+Treeの入口まで十分学べます。

2. アーキテクチャを「学習順」に並べ替える

最終形としては自然ですが、実装順は次の方がよいです。

フェーズ	コンポーネント
1	types
2	sql または最小コマンドパーサ
3	catalog
4	query::executor
5	storage::heap 的な単純ストレージ
6	storage::page
7	storage::btree
8	query::planner
9	transaction
10	wal
11	buffer_pool
12	optimizer

最初は planner / optimizer / WAL / MVCC を作らない こと。

CMU 15-445 系の教材でも、Buffer Pool、B+Tree、Executors、Concurrency Control は大きな別トピックとして分けて扱われます。

3. 学習用に最適化した最小クレート構成

最初は crates 分割より単一workspace + 3〜5 crate くらいが扱いやすいです。

mini-rdbms/
├── Cargo.toml
├── crates/
│   ├── types/
│   │   └── src/lib.rs
│   ├── sql/
│   │   ├── src/ast.rs
│   │   ├── src/lexer.rs
│   │   ├── src/parser.rs
│   │   └── src/lib.rs
│   ├── storage/
│   │   ├── src/row.rs
│   │   ├── src/table.rs
│   │   ├── src/page.rs
│   │   ├── src/heap.rs
│   │   ├── src/btree.rs
│   │   └── src/lib.rs
│   ├── engine/
│   │   ├── src/catalog.rs
│   │   ├── src/planner.rs
│   │   ├── src/executor.rs
│   │   └── src/lib.rs
│   └── cli/
│       └── src/main.rs

理由は単純で、最初から catalog / query / transaction / buffer_pool / wal を完全分割すると、モジュール境界の設計負債の方が難しくなるからです。まずは engine に planner/executor/catalog をまとめ、後から切り出す方が学習効率が高いです。

4. 各フェーズの到達目標

フェーズ1: REPLとAST

目的

SQL文字列を内部表現に変換する
ASTとは何かを理解する

実装範囲

CREATE TABLE
INSERT
SELECT * FROM ...
SELECT * FROM ... WHERE id = 1

AST例

#[derive(Debug, Clone, PartialEq)]
pub enum Statement {
    CreateTable(CreateTableStmt),
    Insert(InsertStmt),
    Select(SelectStmt),
}

#[derive(Debug, Clone, PartialEq)]
pub struct CreateTableStmt {
    pub table_name: String,
    pub columns: Vec<ColumnDef>,
}

#[derive(Debug, Clone, PartialEq)]
pub struct ColumnDef {
    pub name: String,
    pub data_type: DataType,
}

#[derive(Debug, Clone, PartialEq)]
pub struct InsertStmt {
    pub table_name: String,
    pub values: Vec<Value>,
}

#[derive(Debug, Clone, PartialEq)]
pub struct SelectStmt {
    pub table_name: String,
    pub projection: Projection,
    pub filter: Option<Expr>,
}

#[derive(Debug, Clone, PartialEq)]
pub enum Projection {
    All,
}

#[derive(Debug, Clone, PartialEq)]
pub enum Expr {
    Eq {
        column: String,
        value: Value,
    },
}

補足: DuckDB の内部説明でも、parser はテーブルの存在確認や型解決をせず、まず構文木相当へ落とす段階です。この分離は学習上かなり重要です。

フェーズ2: まずは手書きパーサでよいか

はい。最初は手書きで十分です。ただし、フルSQLを手で書く必要はありません。

推奨方針

ステップ1: 手書きの最小 parser
ステップ2: AST と executor の理解が進んだら sqlparser-rs 導入
ステップ3: 自前の AST へ変換する adapter を書く

sqlparser-rs は ANSI SQL 2011 ベースの lexer/parser を提供し、Rust で AST を扱えます。学習用としては最終的にかなり便利です。

なぜ最初は手書きが良いか

SQL文字列 → token → AST の流れが見える
エラー位置と構文ルールを自分で意識できる
planner/executor との境界を理解しやすい

なぜ途中で sqlparser-rs に移ると良いか

SQL文法そのものは本題ではない
本当に難しいのは storage / page / index / transaction 側
parser 実装コストを切って中核に時間を使える

フェーズ3: インメモリ実行器

目的

DBエンジンの最小の「動く核」を作る

内部モデル例

#[derive(Debug, Clone, PartialEq)]
pub enum Value {
    Int(i64),
    Text(String),
    Null,
}

#[derive(Debug, Clone)]
pub struct Row {
    pub values: Vec<Value>,
}

#[derive(Debug, Clone)]
pub struct TableSchema {
    pub name: String,
    pub columns: Vec<ColumnDef>,
}

#[derive(Debug, Default)]
pub struct InMemoryTable {
    pub schema: TableSchema,
    pub rows: Vec<Row>,
}

executor の最小責務

CreateTable で catalog に schema 登録
Insert で行追加
Select で rows を全件走査
WHERE id = 1 を predicate 評価

実装イメージ

pub fn execute_select(table: &InMemoryTable, stmt: &SelectStmt) -> Vec<Row> {
    table
        .rows
        .iter()
        .filter(|row| match &stmt.filter {
            None => true,
            Some(expr) => eval_expr(expr, &table.schema, row),
        })
        .cloned()
        .collect()
}

この段階では planner は不要です。AST を直接 executor に渡してよいです。

フェーズ4: Catalog を入れる

目的

テーブル定義と実データを分離する
「存在しないテーブル」などの検証を入れる

catalog の役割

table name → schema
table name → storage handle
index metadata

SQLite も schema 情報を管理し、DuckDB でも parser の後に binder が catalog を参照して名前解決します。

最小構造

use std::collections::HashMap;

pub struct Catalog {
    pub schemas: HashMap<String, TableSchema>,
}

この段階で入れるべき検証

テーブルが存在するか
列数が一致するか
値型が schema と一致するか

フェーズ5: Planner を入れる

ここで初めて planner を入れます。最初は optimizer ではなく論理プランを1種類だけ作るので十分です。

PlanNode 例

#[derive(Debug, Clone)]
pub enum PlanNode {
    SeqScan {
        table_name: String,
        filter: Option<Expr>,
    },
    Insert {
        table_name: String,
        values: Vec<Value>,
    },
    CreateTable {
        schema: TableSchema,
    },
}

planner の役割

AST を実行器向けの plan に変換
名前解決済み構造へ寄せる
将来の index scan や projection pushdown の受け皿を作る

DuckDB でも parser 後に binder / planner が続き、実行段階と分離されています。

フェーズ6: 永続化の最初の一歩は Heap File

目的

メモリだけでなく、ファイルに行を保存する

ここで重要な判断: 最初から B-tree に保存しない方がよいです。先に heap file 的な単純配置を作ります。

なぜか

B-tree は「配置」と「検索」と「分割」が同時に来る
まず行のシリアライズとページ管理を覚えるべき
SQLite でも pager と B-tree は分離された概念です

最初の保存形式

1 page = 4096 bytes
row を固定長で保存
page header に件数を持つ
table file に page を連結

Rowの固定長化例

たとえば学習用に:

id: i64 = 8 bytes
name: [u8; 32]
合計 40 bytes

pub const NAME_SIZE: usize = 32;
pub const ROW_SIZE: usize = 8 + NAME_SIZE;

pub fn serialize_row(row: &Row) -> [u8; ROW_SIZE] {
    let mut buf = [0u8; ROW_SIZE];

    let id = match &row.values[0] {
        Value::Int(v) => *v,
        _ => panic!("expected int"),
    };
    buf[0..8].copy_from_slice(&id.to_le_bytes());

    let name = match &row.values[1] {
        Value::Text(s) => s,
        _ => panic!("expected text"),
    };
    let bytes = name.as_bytes();
    let len = bytes.len().min(NAME_SIZE);
    buf[8..8 + len].copy_from_slice(&bytes[..len]);

    buf
}

フェーズ7: Page Manager

目的

ディスクI/Oの単位をページに統一する
B-tree 実装の前提を作る

SQLite も B-tree は page cache / pager を通じてページを扱います。

最小API

allocate_page() -> PageId
read_page(page_id) -> Page
write_page(page_id, page)

Rustの型例

pub type PageId = u32;
pub const PAGE_SIZE: usize = 4096;

#[derive(Clone)]
pub struct Page {
    pub id: PageId,
    pub data: [u8; PAGE_SIZE],
}

実装ポイント

std::fs::File
seek して page offset を計算
read_exact / write_all

フェーズ8: B+Tree インデックス

目的

WHERE id = ? を全件走査でなく index lookup にする

B+Tree は現代DBMSの代表的な順序付きインデックスです。CMU 15-445 の資料でも B+Tree を中心に扱っています。

最小仕様

キー: id
値: RowId または (page_id, slot_id)
leaf node のみ値を持つ
internal node は分岐キーだけ

実装順

in-memory B+Tree
page-backed B+Tree
insert split
search
range scan は後回し

RowId 例

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct RowId {
    pub page_id: PageId,
    pub slot_id: u16,
}

planner/executor 側の変化

条件が id = const なら IndexScan
それ以外は SeqScan

pub enum PlanNode {
    SeqScan {
        table_name: String,
        filter: Option<Expr>,
    },
    IndexScan {
        table_name: String,
        index_name: String,
        key: Value,
    },
    Insert {
        table_name: String,
        values: Vec<Value>,
    },
    CreateTable {
        schema: TableSchema,
    },
}

フェーズ9: Buffer Pool は後回し

最終図には Buffer Pool がありますが、学習用の最小版では page manager の直上で十分です。CMU 15-445 でも buffer pool は独立テーマですが、最初から置換戦略や pin/unpin を入れるとかなり複雑になります。

先にやること

page 読み書きのAPIを固める
B+Tree が page 上で動くようにする

後から入れること

fetch_page
unpin_page
dirty flag
eviction

フェーズ10: Transaction / WAL は最終段階

学習用最小RDBMSでは、最初から ACID 全部を目指さないこと。

SQLite では power-safe transactions のために rollback journal や WAL を使いますが、これはかなり大きいテーマです。

現実的な段階

単一スレッド
単一接続
オートコミットのみ
クラッシュ安全性なし
その後に簡易 journal
さらに後で WAL

最小ジャーナル方式

書き換える前のページを別ファイルへコピー
commit 成功で journal 削除
起動時に journal が残っていたら rollback

これは SQLite の rollback journal の考え方をかなり単純化したものです。

5. 実装順の具体的ロードマップ

Step 1: types を作る

DataType
Value
Row
DbError

#[derive(Debug, Clone, PartialEq)]
pub enum DataType {
    Int64,
    Text,
}

#[derive(Debug, Clone, PartialEq)]
pub enum Value {
    Int(i64),
    Text(String),
    Null,
}

Step 2: 手書き lexer / parser を作る

対応文

CREATE TABLE users (id INT, name TEXT);
INSERT INTO users VALUES (1, 'Alice');
SELECT * FROM users;
SELECT * FROM users WHERE id = 1;

最初は nom なしでもよいです。peekable() な token stream で十分です。

Step 3: AST を executor に直結する

Catalog
InMemoryTable
execute(stmt)

この時点で REPL が動くようにします。

Step 4: ユニットテストを書く

最低限

parser test
create table test
insert/select test
where filter test

Rust は型が強いので、ここで Result<T, DbError> を徹底すると後が楽です。

Step 5: planner を導入する

AST → PlanNode
SeqScan
Insert
CreateTable

この時点では optimizer 不要です。

Step 6: heap file を作る

fixed-length row
page header
slot 配置
file persistence

Step 7: page manager を切り出す

page allocation
read/write
page id 管理

Step 8: B+Tree を追加する

in-memory search/insert
split
root update
page-backed 化

Step 9: planner に index scan を追加

WHERE id = literal
index があれば IndexScan
なければ SeqScan

Step 10: 簡易 transaction / journal

single writer
before-image journal
startup recovery

6. 最終アーキテクチャの段階的な進化

今の図は完成系としては自然ですが、学習用の最小版としては次のように読み替えるとよいです。

第1段階: インメモリ版

┌───────────────────────────────┐
│            CLI / REPL         │
└──────────────┬────────────────┘
               │
┌──────────────▼────────────────┐
│          SQL Parser           │
│        AST / Statement        │
└──────────────┬────────────────┘
               │
┌──────────────▼────────────────┐
│      Planner (very small)     │
│   CreateTable / Insert / Scan │
└──────────────┬────────────────┘
               │
┌──────────────▼────────────────┐
│           Executor            │
└──────────────┬────────────────┘
               │
┌──────────────▼────────────────┐
│     Catalog + Heap Storage    │
└───────────────────────────────┘

第2段階: 永続化追加

Parser -> Planner -> Executor
                    |
                    v
             Catalog / Storage
                    |
          Page Manager / Heap File
                    |
                 Disk I/O

第3段階: インデックスとトランザクション

Parser -> Planner -> Executor
                    |
                    v
             Catalog / Storage
                    |
       B+Tree / Page Manager / Buffer Pool
                    |
                 Journal/WAL
                    |
                 Disk I/O

7. Rustで使うと良いライブラリ

最初は依存を増やしすぎない方がよいですが、候補はあります。

初期フェーズ

thiserror: エラー型
anyhow: CLI側の一時的なエラー集約
serde: デバッグや将来のメタデータ保存に便利

中盤以降

sqlparser: SQL文法を既存実装に寄せる場合
parking_lot: 後で lock を入れる場合
bytes: バイナリページ操作を少し楽にしたい場合

8. 学習効率が高い進め方

おすすめはこれです。

1週目

AST
手書き parser
in-memory catalog
insert/select

2週目

planner
executor 分離
テスト整理

3週目

row serialization
heap file
page manager

4週目以降

B+Tree
index scan
recovery の入口

9. 詰まりやすいポイント

SQLパーサにハマる

対策: フルSQLをやらない。必要なら途中で sqlparser-rs に切り替える。

B+Tree を早く始めすぎる

対策: 先に page と heap file を作る。ページ上のレコード配置が分からないと B+Tree のノード表現も理解しづらいです。

transaction を盛り込みすぎる

対策: 最初は単一スレッド・単一接続。WAL は最後でよいです。SQLite でもトランザクション回復は独立した深いトピックです。

10. 最終提案

あなた向けの実装順は次で固定すると進めやすいです。

types
sql::ast
sql::lexer/parser
engine::catalog
engine::executor
engine::planner
storage::heap
storage::page
storage::btree
transaction::journal
buffer_pool
optimizer

マイルストーン

最初のマイルストーン

CREATE TABLE
INSERT
SELECT *
SELECT * WHERE id = 1
インメモリ
単一テーブル

次のマイルストーン

ファイル永続化
fixed-length row
page manager

その次

B+Tree
index scan

最後に

journal / WAL
buffer pool
transaction

FilesExpand file tree

2nd.md

Latest commit

History