ミニSQL

実装: db/minisql/ / 実行: go test ./db/minisql/

db 編の完結編。クラッシュセーフな B-Tree ストレージに、SQL でアクセスする層を被せる。処理は、文字列をトークンに切り、構文木に組み、歩いて実行する3段で、コンパイラと同じ骨格になる。最後の段が読むページ数を数えると、WHERE の有無で 1600 行のとき 3 と 530 に分かれ、差は行が増えるほど開く。ここが実物のプランナに当たる。

この章で作るもの

ここまでの B-Tree + WAL は Go の関数(Insert, Get, Scan)で叩く ストレージだった。その上に、SQL 文字列を受け取って実行する層を載せる。

INSERT INTO users VALUES (1, 100)
SELECT * FROM users WHERE id = 1

前提章

B-Tree + WAL(この章のストレージ層)の上に立つ。

順に見ていく。

1. 3段のパイプライン: 文字列 → トークン → 構文木 → 実行。コンパイラと同じ骨格になる
2. 最後の段が道を選ぶ: WHERE があれば1点引き、なければ全走査。この分岐がプランナの最小版
3. 代償はページ数で出る: 同じ結果を返す2通りの書き方で、読むページが15倍違う

① 3段のパイプライン

DB が SELECT * FROM users という文字列を受け取ってから結果を返すまで、 処理は3つの段を順に通る。

SQL文字列"SELECT * FROM users"

→

lexerトークンに切る

→

parserAST を組む

→

engineストレージ操作へ

→

結果の行

SQL 実行の3段パイプライン。文字列を機械が扱える形に段階的に変換していく。lexer/parser はコンパイラの前半と同じ

lexer は文字の並びを意味の最小単位に切る。SELECT * FROM users は 「キーワード SELECT」「記号 *」「キーワード FROM」「識別子 users」の4トークンになる。 空白を捨て、キーワードと識別子を見分けるのが仕事。

// Package minisql は SQL の極小サブセット(INSERT / SELECT)を、
// これまで作った btreewal ストレージの上に載せた「ミニ実データベース」。db 編の完結編。
//
// SQL の実行は3段のパイプライン: 文字列 → [lexer] トークン列 → [parser] AST → [engine] 実行。
// このファイルは第1段、lexer(字句解析器)。文字の並びを意味の最小単位(トークン)に切り分ける。
package minisql

import (
	"fmt"
	"strings"
	"unicode"
)

// Kind はトークンの種類。
type Kind int

const (
	TokEOF Kind = iota
	TokKeyword
	TokIdent
	TokNumber
	TokStar
	TokComma
	TokLParen
	TokRParen
	TokEq
)

// Token は1つのトークン。
type Token struct {
	Kind Kind
	Text string
}

var keywords = map[string]bool{
	"INSERT": true, "INTO": true, "VALUES": true,
	"SELECT": true, "FROM": true, "WHERE": true,
}

// Lex は入力文字列をトークン列に切り分ける(末尾に TokEOF を付ける)。
func Lex(input string) ([]Token, error) {
	var toks []Token
	runes := []rune(input)
	i := 0
	for i < len(runes) {
		c := runes[i]
		switch {
		case unicode.IsSpace(c):
			i++
		case c == '*':
			toks = append(toks, Token{TokStar, "*"})
			i++
		case c == ',':
			toks = append(toks, Token{TokComma, ","})
			i++
		case c == '(':
			toks = append(toks, Token{TokLParen, "("})
			i++
		case c == ')':
			toks = append(toks, Token{TokRParen, ")"})
			i++
		case c == '=':
			toks = append(toks, Token{TokEq, "="})
			i++
		case unicode.IsDigit(c):
			start := i
			for i < len(runes) && unicode.IsDigit(runes[i]) {
				i++
			}
			toks = append(toks, Token{TokNumber, string(runes[start:i])})
		case unicode.IsLetter(c) || c == '_':
			start := i
			for i < len(runes) && (unicode.IsLetter(runes[i]) || unicode.IsDigit(runes[i]) || runes[i] == '_') {
				i++
			}
			word := string(runes[start:i])
			// キーワードは大小無視。識別子はそのまま。
			if keywords[strings.ToUpper(word)] {
				toks = append(toks, Token{TokKeyword, strings.ToUpper(word)})
			} else {
				toks = append(toks, Token{TokIdent, word})
			}
		default:
			return nil, fmt.Errorf("minisql: unexpected character %q", c)
		}
	}
	toks = append(toks, Token{Kind: TokEOF})
	return toks, nil
}

parser はトークン列を消費して AST(抽象構文木)を組み立てる。 「INSERT の次は INTO、その次はテーブル名、その次は VALUES…」と、文法の形どおりに トークンを1つずつ確かめて進む再帰下降方式。

// Stmt は解析済みの文(AST)。INSERT か SELECT のどちらか。
type Stmt interface{ stmt() }

// InsertStmt は INSERT INTO <table> VALUES (<key>, <value>)。
type InsertStmt struct {
	Table string
	Key   uint64
	Value uint64
}

// SelectStmt は SELECT * FROM <table> [WHERE id = <key>]。
type SelectStmt struct {
	Table    string
	WhereKey *uint64 // nil なら全件
}

func (*InsertStmt) stmt() {}
func (*SelectStmt) stmt() {}

// parser はトークン列を1つずつ消費して AST を組み立てる再帰下降パーサ。
type parser struct {
	toks []Token
	pos  int
}

// Parse は SQL 文字列を解析して AST を返す。
func Parse(input string) (Stmt, error) {
	toks, err := Lex(input)
	if err != nil {
		return nil, err
	}
	p := &parser{toks: toks}
	stmt, err := p.parseStmt()
	if err != nil {
		return nil, err
	}
	if p.peek().Kind != TokEOF {
		return nil, fmt.Errorf("minisql: unexpected token %q after statement", p.peek().Text)
	}
	return stmt, nil
}

func (p *parser) peek() Token { return p.toks[p.pos] }

func (p *parser) next() Token {
	t := p.toks[p.pos]
	if p.pos < len(p.toks)-1 {
		p.pos++
	}
	return t
}

// expect は次のトークンが期待した種類かを確かめて消費する。
func (p *parser) expect(kind Kind, what string) (Token, error) {
	t := p.peek()
	if t.Kind != kind {
		return t, fmt.Errorf("minisql: expected %s, got %q", what, t.Text)
	}
	return p.next(), nil
}

// expectKeyword は次が特定のキーワードかを確かめて消費する。
func (p *parser) expectKeyword(kw string) error {
	t := p.peek()
	if t.Kind != TokKeyword || t.Text != kw {
		return fmt.Errorf("minisql: expected %s, got %q", kw, t.Text)
	}
	p.next()
	return nil
}

func (p *parser) parseStmt() (Stmt, error) {
	t := p.peek()
	if t.Kind != TokKeyword {
		return nil, fmt.Errorf("minisql: expected a statement, got %q", t.Text)
	}
	switch t.Text {
	case "INSERT":
		return p.parseInsert()
	case "SELECT":
		return p.parseSelect()
	default:
		return nil, fmt.Errorf("minisql: unsupported statement %q", t.Text)
	}
}

func (p *parser) parseInsert() (Stmt, error) {
	p.next() // INSERT
	if err := p.expectKeyword("INTO"); err != nil {
		return nil, err
	}
	table, err := p.expect(TokIdent, "table name")
	if err != nil {
		return nil, err
	}
	if err := p.expectKeyword("VALUES"); err != nil {
		return nil, err
	}
	if _, err := p.expect(TokLParen, "'('"); err != nil {
		return nil, err
	}
	key, err := p.parseNumber()
	if err != nil {
		return nil, err
	}
	if _, err := p.expect(TokComma, "','"); err != nil {
		return nil, err
	}
	value, err := p.parseNumber()
	if err != nil {
		return nil, err
	}
	if _, err := p.expect(TokRParen, "')'"); err != nil {
		return nil, err
	}
	return &InsertStmt{Table: table.Text, Key: key, Value: value}, nil
}

func (p *parser) parseSelect() (Stmt, error) {
	p.next() // SELECT
	if _, err := p.expect(TokStar, "'*'"); err != nil {
		return nil, err
	}
	if err := p.expectKeyword("FROM"); err != nil {
		return nil, err
	}
	table, err := p.expect(TokIdent, "table name")
	if err != nil {
		return nil, err
	}
	sel := &SelectStmt{Table: table.Text}

	if p.peek().Kind == TokKeyword && p.peek().Text == "WHERE" {
		p.next() // WHERE
		col, err := p.expect(TokIdent, "column name")
		if err != nil {
			return nil, err
		}
		if col.Text != "id" {
			return nil, fmt.Errorf("minisql: only WHERE id = ... is supported, got %q", col.Text)
		}
		if _, err := p.expect(TokEq, "'='"); err != nil {
			return nil, err
		}
		key, err := p.parseNumber()
		if err != nil {
			return nil, err
		}
		sel.WhereKey = &key
	}
	return sel, nil
}

func (p *parser) parseNumber() (uint64, error) {
	t, err := p.expect(TokNumber, "a number")
	if err != nil {
		return 0, err
	}
	n, err := strconv.ParseUint(t.Text, 10, 64)
	if err != nil {
		return 0, fmt.Errorf("minisql: invalid number %q", t.Text)
	}
	return n, nil
}

parseInsert を読むと、expectKeyword("INTO") → expect(TokIdent, ...) → expectKeyword("VALUES") と、期待するトークンを順に消費しているだけになっている。 このコードの並びが、そのまま INSERT INTO <表> VALUES (<数>, <数>) という文法の形。 再帰下降の読みやすさはここにあって、文法規則1つが関数1つに対応する。 自作言語の parser も、同じ形で書いてある。

② 最後の段が道を選ぶ

engine は AST の種類を見て、B-Tree + WAL の操作を呼ぶ。

// Row は1行。このミニ実装は (key, value) の2列だけ。
type Row struct {
	Key   uint64
	Value uint64
}

// DB は AST を実行するエンジン。ストレージは btreewal(クラッシュセーフな B-Tree)。
// このミニ SQL には「テーブル」の概念が1つしかなく、table 名は受け取るが1本の木に格納する。
type DB struct {
	store *btreewal.Tree
}

// Open はデータベースを開く。
func Open(dir string) (*DB, error) {
	store, err := btreewal.Open(dir, 4)
	if err != nil {
		return nil, err
	}
	return &DB{store: store}, nil
}

// Close はデータベースを閉じる。
func (db *DB) Close() error {
	return db.store.Close()
}

// Exec は SQL 文字列を解析して実行し、SELECT なら結果の行を返す。
// SQL の3段パイプラインの最終段: AST を見て、ストレージ操作に translate する。
func (db *DB) Exec(sql string) ([]Row, error) {
	stmt, err := Parse(sql)
	if err != nil {
		return nil, err
	}
	switch s := stmt.(type) {
	case *InsertStmt:
		return nil, db.store.Insert(s.Key, s.Value)
	case *SelectStmt:
		return db.execSelect(s)
	default:
		return nil, fmt.Errorf("minisql: cannot execute %T", stmt)
	}
}

// execSelect は WHERE の有無で「1件 Get」か「全件 Scan」に振り分ける。
// これは実DBのクエリプランナが「インデックスで1点引く」か「全走査する」かを
// 選ぶのの、最小版。
func (db *DB) execSelect(s *SelectStmt) ([]Row, error) {
	if s.WhereKey != nil {
		// WHERE id = k: B-Tree を1点引き(前章までで作った Get)。
		v, ok, err := db.store.Get(*s.WhereKey)
		if err != nil {
			return nil, err
		}
		if !ok {
			return nil, nil
		}
		return []Row{{Key: *s.WhereKey, Value: v}}, nil
	}
	// WHERE なし: 木を1回歩いて、キーと値をそろえて持ち帰る。
	pairs, err := db.store.ScanRows()
	if err != nil {
		return nil, err
	}
	rows := make([]Row, 0, len(pairs))
	for _, p := range pairs {
		rows = append(rows, Row{Key: p.Key, Value: p.Value})
	}
	return rows, nil
}

見どころは execSelect の分岐だ。WHERE id = k があれば store.Get(k) で B-Tree を1点引き、なければ木を1回歩いて全件返す。 この2択が、実DBのクエリプランナの最小版になる。

分岐しているだけに見えるが、選んだ結果は代償として出る。EXPLAIN に当たるものを 足して、実際に読んだページ数を数えられるようにした。

// Plan は execSelect がどちらの道を選んだかと、その代償。
type Plan struct {
	// Access は "index"(WHERE で1点引き)か "scan"(全走査)。
	Access string
	// Reads は読んだノード(ページ)の数。
	Reads int
	// Hits と Misses は、そのうちバッファプールに載っていた数と、
	// ディスクまで取りに行った数。
	Hits, Misses int
	// Rows は返した行数。
	Rows int
}

// Explain は SELECT を実行して、選んだ道と実際に読んだページ数を返す。
//
// 見積もりではなく実測なので、実物でいえば EXPLAIN ANALYZE のほうにあたる。
// 実DBのプランナは、これを事前に見積もって道を選ぶ。
func (db *DB) Explain(sql string) (Plan, []Row, error) {
	stmt, err := Parse(sql)
	if err != nil {
		return Plan{}, nil, err
	}
	s, ok := stmt.(*SelectStmt)
	if !ok {
		return Plan{}, nil, fmt.Errorf("minisql: EXPLAIN can only run on SELECT, got %T", stmt)
	}

	access := "scan"
	if s.WhereKey != nil {
		access = "index"
	}
	return db.measure(access, func() ([]Row, error) { return db.execSelect(s) })
}

// measure は実行の前後で数え直して、読んだページ数を拾う。
func (db *DB) measure(access string, run func() ([]Row, error)) (Plan, []Row, error) {
	db.store.ResetStats()
	rows, err := run()
	if err != nil {
		return Plan{}, nil, err
	}
	h, m := db.store.PoolStats()
	return Plan{
		Access: access,
		Reads:  db.store.Reads(),
		Hits:   h,
		Misses: m,
		Rows:   len(rows),
	}, rows, nil
}

見積もりではなく実測なので、実物でいえば EXPLAIN ANALYZE のほうにあたる。 行数を変えて測るとこうなった:

行数	1点引き	全走査	比
100	3 ページ	32 ページ	11倍
400	3 ページ	131 ページ	44倍
1,600	3 ページ	530 ページ	177倍

1点引きは 3 ページのまま動かない。読むのは根から葉までの高さぶんで、 行が16倍になっても高さは変わらないからだ。全走査は行数に比例して増える。 だから比は行が増えるほど開く。テストで、行を16倍にしたとき比が一桁上がることを固定した。

ただし、比べているのは「1行取り出す代償」であって速さの優劣ではない。 全走査は 1600 行返している。全部要るなら全部読むしかない。 プランナが選んでいるのは、速い遅いではなく、訊かれたことに対する最短の道になる。

③ 代償はページ数で出る

道を選んだあとにも、まだ差がつくところがある。この章の execSelect は最初こう書いてあった。

// scanThenGet は「キーを並べてから1件ずつ引き直す」書き方。
//
// 直す前の execSelect はこうなっていた。返す結果は同じだが、
// 1行につき根から葉まで降り直すので、読むページが行数に比例して増える。
// 実物でも N+1 と呼ばれる形で、比較のために残してある。
func (db *DB) scanThenGet() ([]Row, error) {
	keys, err := db.store.Scan()
	if err != nil {
		return nil, err
	}
	rows := make([]Row, 0, len(keys))
	for _, k := range keys {
		v, ok, err := db.store.Get(k)
		if err != nil {
			return nil, err
		}
		if ok {
			rows = append(rows, Row{Key: k, Value: v})
		}
	}
	return rows, nil
}

Scan() がキーしか返さないので、値を取りに1件ずつ根から降り直している。 返る結果は正しい。だが 1600 行で測るとこうなった:

	読んだページ	返した行
木を1回歩く	530	1,600
1件ずつ引き直す	8,005	1,600

同じ 1600 行を返すのに、15倍のページを読んでいる。増えたぶんは1行あたり 4.7 ページ、 つまり木の高さそのものだ。これは実物でも N+1 と呼ばれる形で、1回で取れるものを 件数ぶん問い合わせに分けてしまう間違いになる。直し方は単純で、1回歩くついでに値も 持ち帰ればいい。テストで、両者の返す行が1件ずつ一致することと、読むページが5倍以上 違うことを固定した。

バッファプールにも差が出る。プールは 128 ページしか持てない:

	ヒット	ミス
1点引き	2	1
1件ずつ引き直す	6,946	1,059

1点引きは根の付近しか触らないので、ほぼ載っている。降り直すほうは、 プールに載りきらない下の段へ何度も取りに行くことになる。 同じ SQL でも、engine の書き方ひとつでディスクに降りる回数が変わる。

動かす

SQL を入力すると、lexer が切ったトークン、parser が組んだ AST、engine の実行結果が 段ごとに見える。WHERE を付けたり外したりすると、engine が選ぶ道の札が変わる。 文法を外した SQL(例: SELECT users)を入れると、parser がどの段で何を期待して 失敗したかも見える。

デモSQL の3段パイプライン2 行

1. lexer → トークン

SELECT*FROMusersWHEREid=1

2. parser → AST

Select{ table: "users", where: id=1 }

3. engine → 実行

1行

index WHERE があるので B-Tree を1点引き。読むのは根から葉までの高さぶん

id	value
1	100

db 編、これで完結

第1段のログ構造KVから始まって、ここまで来た。

• 二分探索木 / B-Tree: 速い検索
• ディスクとページ / B-Treeページストア: 永続化
• LRU / バッファプール: キャッシュ
• WAL / B-Tree + WAL: クラッシュ耐性
• この章: SQL でのアクセス

積み上げると「SQL で叩ける、永続化された、インデックス付きの、クラッシュしても 壊れないデータベース」になった。本物には遠く及ばないが、PostgreSQL や SQLite が 内部でやっていることの骨格は、全部この積み木の中にある。

設計の観点

• 段を分ける: lexer と parser を分けると、片方の変更がもう片方に届かない。文法を足すのは parser だけの仕事になる
• 文法を関数の形で書く: 規則1つに関数1つを対応させると、コードを読めば文法が読める
• 道の選択を1か所に集める: どう取りに行くかを engine の分岐に閉じ込めておくと、後からコストで選ぶように差し替えられる
• 代償を数えられるようにする: 「インデックスのほうが速い」は主張なので、ページ数を数える口を用意する
• 1回で取れるものを分けない: 走査のついでに値を持ち帰るか、後から引き直すかで、読むページが桁で変わる
• キャッシュの容量を意識する: プールに載る量を超える読み方をすると、ヒット率ではなくディスクへの往復が効いてくる

対照と実例

	段の分け方	道の選び方	実行の仕方
この章	lexer / parser / engine	WHERE の有無だけ	行をまとめて返す
SQLite	tokenizer / parser / code generator	コストで選ぶ(統計あり)	VDBE(バイトコード)を回す
PostgreSQL	parser / analyzer / planner / executor	コストで選ぶ(統計あり)	節を1行ずつ流す
DuckDB	同上	コストで選ぶ	列をまとめて処理する
自作言語	lexer / parser / evaluator	(選択なし)	AST をそのまま歩く

裏どり:

• 3段は実物も同じ: SQLite の構成図が tokenizer → parser → code generator → VDBE と並べている。違うのは、この章が AST を直に実行するのに対し、SQLite はバイトコードに落としてから回すこと。バイトコード VM の章で作ったのと同じ形になる
• プランナは見積もりで選ぶ: PostgreSQL は表の行数や値の分布を統計として持ち、道ごとのコストを計算して選ぶ。EXPLAIN は見積もり、EXPLAIN ANALYZE は実測。この章の Explain は後者に当たる
• インデックスが常に勝つわけではない: 表の大半を返す問い合わせでは、インデックスをたどるより全走査のほうが安い。実物のプランナはこれを見積もりで判断していて、この章の分岐にはその判断が無い
• N+1 は実物でよく出る: ORM で1件ずつ関連を引き直す形が代表例。N+1 の解説はどのフレームワークの文書にもある。原因はいつも同じで、1回で取れるものを件数ぶんに分けている
• 行を1つずつ流す形: 実物の executor は結果を一度に作らず、1行ずつ上へ渡す(Volcano モデル)。この章は全部作ってから返すので、行数ぶんのメモリを使う

簡略化したこと

• テーブルは1つ・列は (id, value) 固定: CREATE TABLE もスキーマもない
• INSERT / SELECT のみ: UPDATE / DELETE / JOIN / 集約なし
• WHERE は id = 定数 のみ: 式評価器を持たない。範囲も AND も無い
• コストで選ばない: 統計を持たないので、WHERE の有無だけで道を決めている
• 行をまとめて返す: 1行ずつ流す形ではないので、返す行数ぶんメモリを使う
• バイトコードに落とさない: AST を直に歩く。実物は中間表現を経由する

参考資料

• SQLite: The Architecture Of SQLite — 実物の tokenizer → parser → VDBE
• Writing a SQL database from scratch — Go で SQL DB を作る連載。この章と同じ3段構成
• CMU 15-445 — クエリ実行・最適化まで含む決定版講義
• 実装: db/minisql