Skip to content

1st.md

Latest commit

 

History

History
487 lines (352 loc) · 13.8 KB

1st.md

File metadata and controls

487 lines (352 loc) · 13.8 KB

学習対話ログ

RDBMS自作プロジェクトの学習過程で得た知見、Q&A、設計決定の記録。

2026-03-13: プロジェクト開始と方針決定

質問: SQLパーサーは手動実装すべきか？

前提:

  • SQLレベル: 簡単な SELECT * FROM xxx_table WHERE id = 1; 程度しか書けない
  • 複雑な構文や UPDATE/DELETE は書けない

回答:

学習用として RDBMS を自作するのはかなり良い題材です。 ただし最初に結論を言うと、「フルSQL対応のRDBMS」を作る必要はありません。学習目的なら、まずは「単一テーブル・固定スキーマ・SELECT/INSERTだけ」の極小DBから始めるのが正解です。実際、SQLite系の教育用チュートリアルも、REPL → 行保存 → ページャ → B-tree という順で段階的に作っていきます。SQLite 自体も内部は「パーサ → コード生成/VM → B-tree → pager → OS interface」のように層分割されています。

あなたの現在のレベル感だと、最初から JOIN、GROUP BY、UPDATE、DELETE、最適化器、トランザクション分離レベルまで全部やるとほぼ確実に破綻します。 なので目標は次です。

最初の完成形

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

これで十分です。RDBMS学習で重要なのは、SQLの暗記量よりも、SQL文字列がどう AST になり、どう実行され、どうページに保存されるかを理解することです。DuckDB の内部説明でも、parser は文字列を AST に変換するだけで、表や型の解決は後段の binder/planner が担うと整理されています。PostgreSQL でも parser と、その後の変換処理は分かれています。

SQLパーサーは手動実装すべきか

学習用なら「小さい範囲だけ手動実装」はかなりおすすめです。 ただし、フルSQLパーサを手書きする必要はありません。PostgreSQL は flex + bison、SQLite は Lemon を使っていて、本格DBはだいたいパーサ生成系を使います。つまり、実務級のDB実装では「巨大な SQL 文法を全部手で書く」のは普通ではありません。

おすすめ方針

  1. 最初は手書きパーサ
    • SELECT * FROM users WHERE id = 1;
    • INSERT INTO users VALUES (1, 'Alice'); だけ対応する
  2. AST を自分で定義する
  3. 実行器が AST を見てテーブルスキャンする
  4. その後、必要なら parser generator や既存ライブラリに置き換える

この順が良い理由は、字句解析・構文解析・AST・実行の責務分離が自分の頭に入るからです。SQLite も SQL parser を独立したコンポーネントとして持ち、DuckDB でも parser は catalog を知らない独立段階として説明されています。

「手動実装」が必要なのはどこまでか

必要なのは「SQLっぽい文字列を自分の内部表現に変換する最小部分」までです。 極端に言えば、最初は SQL でなくても成立します。

たとえば最初はこんなコマンドでもよいです。

insert users 1 Alice
select users id 1

これでも、内部で以下の流れは学べます。

  • tokenize
  • parse
  • AST化
  • 実行
  • 永続化

その後に SQL 風構文へ寄せればよいです。教育用の「簡易DBを作る」系でも、最初は非常に狭い構文から始めて、段階的に B-tree や pager に進める構成が一般的です。

何から実装するべきか

RDBMS は大きく分けると次の層です。

  1. フロントエンド
    • tokenizer / lexer
    • parser
    • AST
  2. セマンティクス
    • テーブル名・列名の解決
    • 型チェック
  3. 実行器
    • table scan
    • filter
  4. ストレージ
    • 行の保存
    • ページ管理
    • インデックス
  5. トランザクション / リカバリ
    • commit / rollback
    • WAL / journal

SQLite の説明でも、B-tree、pager、OS interface が明確に分かれており、WAL や rollback journal で atomic commit を実現しています。

あなたの場合、最初の順番はこうするのが最も安全です。

学習ロードマップ

フェーズ1: インメモリDB

最初はファイル保存すら不要です。

やること:

  • 1テーブルだけ持つ
  • 行は Vec<Row> / []Row に積む
  • INSERT
  • SELECT *
  • WHERE id = 1

この段階で学べるのは:

  • SQL文字列をどう解釈するか
  • AST とは何か
  • テーブルスキャンとは何か

フェーズ2: 固定長レコードでファイル保存

次に、メモリではなくファイルに行を書きます。

やること:

  • 1ページ = 4096 bytes
  • 行を固定長にシリアライズ
  • ページに詰める
  • 起動時に読む

SQLite のファイル形式もページ中心で構成されており、B-tree の各ノードはページ単位で保存されます。

フェーズ3: B-tree or B+Tree

次に id 検索を速くします。

なぜ必要か:

  • WHERE id = 1 を毎回全件スキャンすると遅い
  • 順序付き索引の中心は B+Tree 系

CMU 15-445 の資料でも、現代的なDBMSで順序保持インデックスとして B+Tree が広く使われると説明されています。SQLite もテーブルやインデックスを B-tree で保持します。

フェーズ4: 最小トランザクション

やること:

  • BEGIN
  • COMMIT
  • ROLLBACK

最初は本格的な並行制御は不要です。 単一スレッド・単一接続で、まずは「途中で落ちても壊れない」を目標にします。SQLite は rollback journal や WAL で atomic commit を実現しています。

現実的な学習戦略

あなたの現状だと、最初に学ぶべきは SQL 構文よりも次の4つです。

  • AST
  • 行の表現
  • ページ
  • 実行器

SQL を流暢に書けなくても問題ありません。 むしろ DB 実装の初学者が最初に詰まるのは SQL ではなく、「パーサのあとに何が続くのか分からない」ことです。DuckDB や PostgreSQL の説明を見ると、parser は最初の一段でしかなく、その後に名前解決や実行計画の段階が続きます。

最小実装の設計案

おすすめは以下です。

サポートするSQL

INSERT INTO users VALUES (1, 'Alice');
SELECT * FROM users;
SELECT * FROM users WHERE id = 1;

制約

  • テーブルは1つだけ
  • 列は id INT, name TEXT
  • WHERE は id = 数字 だけ
  • UPDATE / DELETE は後回し
  • JOIN / ORDER BY / GROUP BY は未対応

内部AST

Rust なら例えば:

#[derive(Debug, Clone)]
enum Statement {
    Insert {
        table: String,
        values: Vec<Value>,
    },
    Select {
        table: String,
        filter: Option<Expr>,
    },
}

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

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

Go なら:

package main

type Statement interface {
    isStatement()
}

type InsertStmt struct {
    Table  string
    Values []Value
}
func (InsertStmt) isStatement() {}

type SelectStmt struct {
    Table  string
    Filter *EqExpr
}
func (SelectStmt) isStatement() {}

type EqExpr struct {
    Column string
    Value  Value
}

type Value struct {
    Int  *int64
    Text *string
}

この AST に落とせれば、あとは実行器が見て処理するだけです。 重要なのは、SQL文字列を直接実行しないで、一度「木構造の中間表現」にすることです。これは一般的なDB実装の基本です。

最初の手書きパーサ例

Go の超簡易版

これは本当に最初の一歩用です。

package main

import (
    "fmt"
    "strconv"
    "strings"
)

type StatementType int

const (
    StatementUnknown StatementType = iota
    StatementSelect
    StatementInsert
)

type Statement struct {
    Type  StatementType
    Table string
    ID    *int64
    Name  *string
}

func parse(input string) (*Statement, error) {
    s := strings.TrimSpace(input)
    s = strings.TrimSuffix(s, ";")

    parts := strings.Fields(s)
    if len(parts) == 0 {
        return nil, fmt.Errorf("empty input")
    }

    upper := make([]string, len(parts))
    for i, p := range parts {
        upper[i] = strings.ToUpper(p)
    }

    // SELECT * FROM users WHERE id = 1
    if len(parts) >= 4 &&
        upper[0] == "SELECT" &&
        parts[1] == "*" &&
        upper[2] == "FROM" {
        stmt := &Statement{
            Type:  StatementSelect,
            Table: parts[3],
        }

        if len(parts) == 8 &&
            upper[4] == "WHERE" &&
            strings.ToLower(parts[5]) == "id" &&
            parts[6] == "=" {
            id, err := strconv.ParseInt(parts[7], 10, 64)
            if err != nil {
                return nil, fmt.Errorf("invalid id: %w", err)
            }
            stmt.ID = &id
        }

        return stmt, nil
    }

    // INSERT INTO users VALUES (1, 'Alice')
    if len(parts) >= 4 &&
        upper[0] == "INSERT" &&
        upper[1] == "INTO" {
        return &Statement{
            Type:  StatementInsert,
            Table: parts[2],
        }, nil
    }

    return nil, fmt.Errorf("unsupported syntax")
}

func main() {
    stmt, err := parse("SELECT * FROM users WHERE id = 1;")
    if err != nil {
        panic(err)
    }
    fmt.Printf("%+v\n", stmt)
}

これは雑ですが、学習としては十分です。 本質は「完全な SQL 文法」ではなく、トークン列から内部表現へ変換する感覚を掴むことです。大規模DBは parser generator や既存 parser を使いますが、最小実装ではこの程度の手書きでも十分に学習効果があります。

Rust の超簡易版

fn parse_select(input: &str) -> Result<(&str, Option<i64>), String> {
    let s = input.trim().trim_end_matches(';');
    let parts: Vec<&str> = s.split_whitespace().collect();

    if parts.len() < 4 {
        return Err("too short".into());
    }

    if !parts[0].eq_ignore_ascii_case("SELECT") {
        return Err("expected SELECT".into());
    }
    if parts[1] != "*" {
        return Err("expected *".into());
    }
    if !parts[2].eq_ignore_ascii_case("FROM") {
        return Err("expected FROM".into());
    }

    let table = parts[3];

    if parts.len() == 4 {
        return Ok((table, None));
    }

    if parts.len() == 8
        && parts[4].eq_ignore_ascii_case("WHERE")
        && parts[5].eq_ignore_ascii_case("id")
        && parts[6] == "="
    {
        let id = parts[7].parse::<i64>().map_err(|e| e.to_string())?;
        return Ok((table, Some(id)));
    }

    Err("unsupported WHERE clause".into())
}

fn main() {
    let parsed = parse_select("SELECT * FROM users WHERE id = 1;");
    println!("{parsed:?}");
}

既存パーサを使うのはアリか

アリです。むしろ後半では推奨です。

  • Rust なら sqlparser-rs は SQL を AST に落とすライブラリです。
  • Go なら Vitess の sqlparser が有名です。

ただし学習目的で「RDBMSの中身を理解したい」なら、最初の数ステップは自前の極小パーサのほうが学びが大きいです。理由は、既存パーサを使うと文字列→AST の境界がブラックボックス化しやすいからです。 一方で、B-tree や pager や execution engine を学ぶ段階に進んだら、パーサを既存ライブラリに置き換えるのは非常に合理的です。DuckDB や PostgreSQL のような本格系でも、parser は一段にすぎず、真に難しいのは storage / execution / recovery 側です。

あなた向けの現実的な到達目標

今のレベルなら、次の順に作るのがよいです。

目標1: SQL風 REPL を作る

  • insert
  • select
  • エラーメッセージ

目標2: インメモリで rows を保持

  • Vec<Row> / []Row

目標3: ファイル永続化

  • 固定長 record
  • 4KB page

目標4: WHERE id = ?

  • 全件スキャンでよい

目標5: B+Tree インデックス

  • id の高速検索

目標6: 簡単な commit / rollback

  • 単一接続
  • ジャーナル方式

これで「RDBMSの骨格」はかなり理解できます。 特に、SQLite のような実用DBでも B-tree、pager、journal/WAL が中核であることを考えると、この順番は学習効率が高いです。

逆に最初はやらなくていいもの

以下は後回しで大丈夫です。

  • JOIN
  • GROUP BY
  • ORDER BY
  • UPDATE
  • DELETE
  • 複数テーブル
  • 型推論
  • 最適化器
  • 並行実行制御
  • MVCC
  • WAL checkpoint
  • 分散DB

RDBMS を理解する入口としては、これらは重すぎます。 CMU 15-445 のようなDB実装教育でも、ストレージ、B+Tree、実行、並行性、回復は別々の大きいトピックとして扱われています。

結論

結論を整理すると次の通りです。

  • 学習用にRDBMSを自作するのは非常に良い
  • フルSQL対応は不要
  • SQLパーサは「小さい範囲だけ手動実装」で十分
  • むしろ最初は手動実装したほうが理解しやすい
  • ただし本格的なSQL文法は parser generator や既存ライブラリを使うのが普通
  • あなたの今のレベルなら、まずは INSERT / SELECT * / WHERE id = 1 だけ対応するインメモリDB から始めるのが最適

必要なら次に、あなた向けに「Go で作る最小RDBMSの設計書」か「Rust で作る最小RDBMSのステップ別実装ガイド」のどちらかに落として、ディレクトリ構成・型定義・実装順まで具体化します。