RDBMSを自作して学ぶ：第8章 クエリプランナーと実行エンジン
前回は、SQLの文字列を抽象構文木（AST）に変換するLexerとParserを実装しました。今回は、そのASTを受け取って「どういう手順でデータを読むか」という実行計画を作るPlannerと、計画に従って実際にデータを読み書きするExecutorを実装します。この章を終えると、これまで作ってきたストレージエンジンに対して、SQLで行を挿入したり検索したりできるようになります。
クエリ処理の流れ
論理プランと物理プラン
SQLは「何が欲しいか」を書く言語で、「どうやって取ってくるか」は書きません。たとえば次のSQLを考えます。
SELECT name FROM users WHERE id = 2このSQLの意味は「usersテーブルから、idが2の行を選び、nameだけを取り出す」です。この意味を木で表したものを論理プランと呼びます。
Projection [name] ← nameだけを取り出す
└─ Filter [id = 2] ← idが2の行を選ぶ
└─ users ← usersテーブル一方、「usersテーブルをどう読むか」には選択肢があります。ヒープファイルを先頭から全件読んでもよいし（SeqScan）、idにインデックスがあればB+木で目的の行だけを引いてもかまいません（IndexScan）。こうした具体的なやり方まで決めたものが物理プランです。
Projection [NAME]
└─ Filter (ID = 2)
└─ IndexScan USERS [2, 2] ← B+木で id=2 の行だけを読む本格的なデータベースは論理プランを作ってから、統計情報を使って最も安く実行できそうな物理プランを選びます（コストベース最適化）。本シリーズでは両者を区別せず、Plannerが決まったルールに従って物理プランを直接作ります。
PlannerとExecutorの分担
本シリーズでは、PlannerとExecutorの役割を次のように分けます。
AST ──▶ Planner ──▶ 実行計画（Plan：ただのデータ）──▶ Executor ──▶ オペレータの木 ──▶ 結果Plannerが作る実行計画は「どのテーブルをどの方法で読み、どの条件で絞るか」を表すだけのデータで、実際にページを読むことはしません。Executorは実行計画を受け取り、同じ形をしたオペレータ（実際に行を生み出すオブジェクト）の木を組み立てて実行します。PostgreSQLも、プランナが作った計画木（Plan）から、エグゼキュータが実行用の状態を持った木（PlanState）を組み立てる、という同じ分担になっています。
この分け方にすると、パッケージの依存関係も一方向になります。executor は planner の計画を読みますが、planner は executor を知りません。Goでは循環importがコンパイルエラーになるので、依存の向きを最初に決めておくことが大切です。
executor ──▶ planner ──▶ catalog ──▶ storage（heap・btree・buffer）
│ │
└────────────┴──▶ parserこの章で使う最小限のカタログ
PlannerもExecutorも、「usersテーブルにはどんなカラムがあるか」「ヒープファイルとインデックスはどれか」を知る必要があります。この情報を管理するのがカタログです。カタログの設計と永続化は次章で詳しく扱うので、この章ではメモリ上だけで動く最小限のカタログを用意します。
まずカラムとスキーマの型です。
// sql/catalog/schema.go
package catalog
// DataType はカラムのデータ型
type DataType int
const (
TypeInt DataType = iota // 32ビット符号付き整数
TypeVarchar // 可変長文字列
)
func (t DataType) String() string {
if t == TypeInt {
return "INT"
}
return "VARCHAR"
}
// Column はカラムの定義
type Column struct {
Name string
Type DataType
Length int // VARCHARの最大文字数
PrimaryKey bool
}
// Schema はテーブルのカラム定義の並び
type Schema struct {
Columns []Column
}
// PrimaryKeyIndex は主キーのカラム位置を返す（主キーがなければ-1）
func (s *Schema) PrimaryKeyIndex() int {
for i, c := range s.Columns {
if c.PrimaryKey {
return i
}
}
return -1
}カタログ本体は、テーブル名からテーブル情報（スキーマ・ヒープファイル・インデックス）を引くマップです。テーブルを作るときにヒープファイルを用意し、主キーがあれば主キーのB+木も作ります。
// sql/catalog/catalog.go
package catalog
import (
"fmt"
"sort"
"sync"
"github.com/yourname/go-rdbms/storage/btree"
"github.com/yourname/go-rdbms/storage/buffer"
"github.com/yourname/go-rdbms/storage/heap"
)
// TableInfo はテーブルの定義と、実データ・インデックスへの参照を持つ
type TableInfo struct {
Name string
Schema *Schema
Heap *heap.HeapFile
Index *btree.BPlusTree // 主キーのインデックス（主キーがなければnil）
}
// Catalog はテーブル定義を管理する（第8章の時点ではメモリ上だけで管理する）
type Catalog struct {
mu sync.RWMutex
bpm *buffer.BufferPoolManager
tables map[string]*TableInfo
}
// NewCatalog は空のカタログを作る
func NewCatalog(bpm *buffer.BufferPoolManager) *Catalog {
return &Catalog{bpm: bpm, tables: make(map[string]*TableInfo)}
}
// CreateTable はテーブルを作成し、ヒープファイルと主キーのインデックスを用意する
func (c *Catalog) CreateTable(name string, columns []Column) (*TableInfo, error) {
c.mu.Lock()
defer c.mu.Unlock()
if _, exists := c.tables[name]; exists {
return nil, fmt.Errorf("catalog: テーブル %s は既に存在します", name)
}
schema := &Schema{Columns: columns}
if err := validateSchema(schema); err != nil {
return nil, err
}
hf, err := heap.NewHeapFile(c.bpm)
if err != nil {
return nil, err
}
info := &TableInfo{Name: name, Schema: schema, Heap: hf}
if schema.PrimaryKeyIndex() >= 0 {
if info.Index, err = btree.NewBPlusTree(c.bpm); err != nil {
return nil, err
}
}
c.tables[name] = info
return info, nil
}
// GetTable はテーブル名からテーブル情報を返す
func (c *Catalog) GetTable(name string) (*TableInfo, error) {
c.mu.RLock()
defer c.mu.RUnlock()
info, ok := c.tables[name]
if !ok {
return nil, fmt.Errorf("catalog: テーブル %s は存在しません", name)
}
return info, nil
}
// ListTables はテーブル名の一覧を名前順で返す
func (c *Catalog) ListTables() []string {
c.mu.RLock()
defer c.mu.RUnlock()
names := make([]string, 0, len(c.tables))
for name := range c.tables {
names = append(names, name)
}
sort.Strings(names)
return names
}
// validateSchema はカラム定義の妥当性を確認する
func validateSchema(s *Schema) error {
if len(s.Columns) == 0 {
return fmt.Errorf("catalog: カラムが1つもありません")
}
seen := map[string]bool{}
pkCount := 0
for _, col := range s.Columns {
if seen[col.Name] {
return fmt.Errorf("catalog: カラム %s が重複しています", col.Name)
}
seen[col.Name] = true
if col.PrimaryKey {
pkCount++
if col.Type != TypeInt {
return fmt.Errorf("catalog: PRIMARY KEY は INT 型のカラムにだけ指定できます")
}
}
}
if pkCount > 1 {
return fmt.Errorf("catalog: PRIMARY KEY は1つのカラムにだけ指定できます")
}
return nil
}第6章のB+木は整数キーしか扱わないので、PRIMARY KEY はINT型のカラム1つだけに指定できる、という制約にしています。
イテレータモデル（Volcano Model）
Open・Next・Close
Executorはイテレータモデルで実装します。Goetz Graefeが提案したクエリ実行システム Volcano にちなんで、Volcano Model とも呼ばれます。
イテレータモデルでは、すべてのオペレータが同じインターフェースを持ちます。
type Operator interface {
Open() error // 準備
Next() (*Tuple, error) // 次の1行を返す（もうなければ nil）
Close() error // 後片付け
}オペレータは木の形に組み合わせます。最上位のオペレータの Next を呼ぶと、それが子の Next を呼び、さらにその子の Next を呼び……と下に向かって呼び出しが連鎖し、最下層のスキャンが1行を読んで上に返します。
Projection.Next()
└▶ Filter.Next() 条件を満たさない行は捨てて、子のNextを呼び直す
└▶ SeqScan.Next() ヒープファイルから1行読むPostgreSQLのエグゼキュータは、この方式で動いています。一方SQLiteは、SQLを独自の仮想マシン用のバイトコードにコンパイルして実行する方式（VDBE）で、イテレータモデルとは作りが異なります。
イテレータモデルの利点
- メモリ効率がよい: 結果を1行ずつ上に流すので、全件を一度にメモリに載せる必要がない
- 組み合わせが自由: どのオペレータも同じインターフェースなので、FilterをJoinの上にもScanの上にも置ける
- 実装が単純: 各オペレータは「子から1行もらって、加工して返す」ことだけを考えればよい
一方で、1行ごとに関数呼び出しが重なるので、大量の行を処理する分析系のデータベースでは、複数行をまとめて処理する方式（ベクトル化実行）が使われることもあります。
値とタプル
値の型とエンコード
オペレータの間を流れる値を Value として定義します。ヒープファイルには第5章の形式（長さ + データ）でバイト列として格納されているので、スキーマに従って Value との間で変換します。
// sql/executor/value.go
package executor
import (
"encoding/binary"
"fmt"
"math"
"strconv"
"unicode/utf8"
"github.com/yourname/go-rdbms/sql/catalog"
"github.com/yourname/go-rdbms/storage/heap"
)
// Value は1つのカラムの値
type Value struct {
Type catalog.DataType
Int int64 // TypeInt のときに使う
Str string // TypeVarchar のときに使う
}
func NewInt(v int64) Value { return Value{Type: catalog.TypeInt, Int: v} }
func NewString(s string) Value { return Value{Type: catalog.TypeVarchar, Str: s} }
func (v Value) String() string {
if v.Type == catalog.TypeInt {
return strconv.FormatInt(v.Int, 10)
}
return v.Str
}
// Compare はaとbを比較し、a<bなら負、a==bなら0、a>bなら正を返す
// 型が異なる値どうしは比較できない
func Compare(a, b Value) (int, error) {
if a.Type != b.Type {
return 0, fmt.Errorf("executor: %s と %s は比較できません", a.Type, b.Type)
}
if a.Type == catalog.TypeInt {
switch {
case a.Int < b.Int:
return -1, nil
case a.Int > b.Int:
return 1, nil
}
return 0, nil
}
switch {
case a.Str < b.Str:
return -1, nil
case a.Str > b.Str:
return 1, nil
}
return 0, nil
}
// EncodeTuple はスキーマに従って値の並びをレコードのバイト列にする
// INT は4バイトのビッグエンディアン（符号付き）、VARCHAR はUTF-8のバイト列
func EncodeTuple(values []Value, schema *catalog.Schema) ([]byte, error) {
if len(values) != len(schema.Columns) {
return nil, fmt.Errorf("executor: 値の数(%d)がカラム数(%d)と一致しません", len(values), len(schema.Columns))
}
fields := make([][]byte, len(values))
for i, col := range schema.Columns {
v := values[i]
if v.Type != col.Type {
return nil, fmt.Errorf("executor: カラム %s は %s 型です", col.Name, col.Type)
}
switch col.Type {
case catalog.TypeInt:
if v.Int < math.MinInt32 || v.Int > math.MaxInt32 {
return nil, fmt.Errorf("executor: カラム %s の値 %d はINTの範囲外です", col.Name, v.Int)
}
fields[i] = binary.BigEndian.AppendUint32(nil, uint32(int32(v.Int)))
case catalog.TypeVarchar:
if n := utf8.RuneCountInString(v.Str); n > col.Length {
return nil, fmt.Errorf("executor: カラム %s は最大%d文字です（%d文字）", col.Name, col.Length, n)
}
fields[i] = []byte(v.Str)
}
}
return heap.EncodeRecord(fields)
}
// DecodeTuple はレコードのバイト列をスキーマに従って値の並びに戻す
func DecodeTuple(data []byte, schema *catalog.Schema) ([]Value, error) {
fields, err := heap.DecodeRecord(data)
if err != nil {
return nil, err
}
if len(fields) != len(schema.Columns) {
return nil, fmt.Errorf("executor: レコードのフィールド数(%d)がカラム数(%d)と一致しません", len(fields), len(schema.Columns))
}
values := make([]Value, len(fields))
for i, col := range schema.Columns {
switch col.Type {
case catalog.TypeInt:
if len(fields[i]) != 4 {
return nil, fmt.Errorf("executor: カラム %s のデータ長が不正です", col.Name)
}
// int32 を経由することで負の値も正しく復元できる
values[i] = NewInt(int64(int32(binary.BigEndian.Uint32(fields[i]))))
case catalog.TypeVarchar:
values[i] = NewString(string(fields[i]))
}
}
return values, nil
}INT型は4バイトの符号付き整数としてビッグエンディアンで格納します。復元するときに uint32 から直接 int64 に変換すると、負の値（例えば -1 は 0xFFFFFFFF）が大きな正の数になってしまうので、いったん int32 を経由して符号を戻している点に注意してください。VARCHARの長さは、バイト数ではなく文字数（utf8.RuneCountInString）で確かめています。
型の異なる値どうしの比較はエラーにしています。WHERE id = 'abc' のような比較を、暗黙の型変換なしに黙って偽にするよりも、誤りに気づきやすいからです。
タプルと出力列
// sql/executor/operator.go
package executor
import (
"fmt"
"github.com/yourname/go-rdbms/sql/parser"
)
// Tuple はオペレータ間を流れる1行
type Tuple struct {
Values []Value
}
// OutputColumn はオペレータが出力する列の情報
type OutputColumn struct {
Table string
Name string
}
// Operator はイテレータモデル（Volcano Model）のオペレータ
type Operator interface {
Open() error
// Next は次の1行を返す。行がもうなければ nil を返す
Next() (*Tuple, error)
Close() error
// Columns は出力する列の並びを返す
Columns() []OutputColumn
}
// resolveColumn はカラム参照が列の並びの何番目かを求める
func resolveColumn(cols []OutputColumn, ref *parser.ColumnRef) (int, error) {
found := -1
for i, c := range cols {
if c.Name != ref.Name || (ref.Table != "" && c.Table != ref.Table) {
continue
}
if found >= 0 {
return -1, fmt.Errorf("executor: カラム %s があいまいです（テーブル名で修飾してください）", ref)
}
found = i
}
if found < 0 {
return -1, fmt.Errorf("executor: カラム %s が見つかりません", ref)
}
return found, nil
}OutputColumn は、オペレータが出力する列が「どのテーブルのどのカラムか」を表します。JOINでは2つのテーブルの列が並ぶので、users.id と orders.id を区別するためにテーブル名も持たせています。resolveColumn は、カラム参照がその並びの何番目かを求め、テーブル名で修飾されていない名前が複数の列に一致した場合は「あいまい」というエラーにします。
条件式の評価
WHERE句とON句の条件式を、1行（タプル）に対して評価する関数です。
// sql/executor/eval.go
package executor
import (
"fmt"
"github.com/yourname/go-rdbms/sql/parser"
)
// evalValue はカラム参照またはリテラルを評価して値を返す
func evalValue(expr parser.Expression, tuple *Tuple, cols []OutputColumn) (Value, error) {
switch e := expr.(type) {
case *parser.ColumnRef:
idx, err := resolveColumn(cols, e)
if err != nil {
return Value{}, err
}
return tuple.Values[idx], nil
case *parser.IntLiteral:
return NewInt(e.Value), nil
case *parser.StringLiteral:
return NewString(e.Value), nil
default:
return Value{}, fmt.Errorf("executor: %s は値として評価できません", expr)
}
}
// evalPredicate は条件式を評価して真偽を返す
func evalPredicate(expr parser.Expression, tuple *Tuple, cols []OutputColumn) (bool, error) {
switch e := expr.(type) {
case *parser.NotExpr:
v, err := evalPredicate(e.Expr, tuple, cols)
return !v, err
case *parser.BinaryExpr:
switch e.Op {
case "AND", "OR":
left, err := evalPredicate(e.Left, tuple, cols)
if err != nil {
return false, err
}
// 短絡評価: 左辺だけで結果が決まれば右辺は評価しない
if e.Op == "AND" && !left || e.Op == "OR" && left {
return left, nil
}
return evalPredicate(e.Right, tuple, cols)
}
left, err := evalValue(e.Left, tuple, cols)
if err != nil {
return false, err
}
right, err := evalValue(e.Right, tuple, cols)
if err != nil {
return false, err
}
c, err := Compare(left, right)
if err != nil {
return false, err
}
switch e.Op {
case "=":
return c == 0, nil
case "<>":
return c != 0, nil
case "<":
return c < 0, nil
case ">":
return c > 0, nil
case "<=":
return c <= 0, nil
case ">=":
return c >= 0, nil
}
}
return false, fmt.Errorf("executor: %s は条件式ではありません", expr)
}AND と OR は短絡評価にしています。AND の左辺が偽なら、右辺を評価しなくても結果は偽に決まります。
なお、本シリーズはNULLを扱わないので、条件式の結果は真か偽の2通りです。実際のSQLでは、NULLとの比較結果が「不明（UNKNOWN）」になる3値論理を扱う必要があります。
オペレータの実装
SeqScan と IndexScan
テーブルを読むオペレータは2種類です。SeqScanは第5章のスキャナでヒープファイルを全件読み、IndexScanは第6章のB+木で範囲 [lo, hi] のRIDを求めてから、そのレコードだけをヒープファイルから読みます。
// sql/executor/scan.go
package executor
import (
"github.com/yourname/go-rdbms/sql/catalog"
"github.com/yourname/go-rdbms/storage/heap"
)
// tableColumns はテーブルの全カラムを出力列の並びに変換する
func tableColumns(table *catalog.TableInfo) []OutputColumn {
cols := make([]OutputColumn, len(table.Schema.Columns))
for i, c := range table.Schema.Columns {
cols[i] = OutputColumn{Table: table.Name, Name: c.Name}
}
return cols
}
// SeqScan はヒープファイルを先頭から全件読むオペレータ
type SeqScan struct {
table *catalog.TableInfo
scanner *heap.HeapScanner
}
func NewSeqScan(table *catalog.TableInfo) *SeqScan {
return &SeqScan{table: table}
}
func (s *SeqScan) Open() error {
s.scanner = s.table.Heap.Scan()
return nil
}
func (s *SeqScan) Next() (*Tuple, error) {
_, data, ok, err := s.scanner.Next()
if err != nil || !ok {
return nil, err
}
values, err := DecodeTuple(data, s.table.Schema)
if err != nil {
return nil, err
}
return &Tuple{Values: values}, nil
}
func (s *SeqScan) Close() error { return nil }
func (s *SeqScan) Columns() []OutputColumn { return tableColumns(s.table) }
// IndexScan は主キーのB+木で範囲 [lo, hi] のRIDを求め、そのレコードだけを読むオペレータ
type IndexScan struct {
table *catalog.TableInfo
lo, hi int64
rids []heap.RID
pos int
}
func NewIndexScan(table *catalog.TableInfo, lo, hi int64) *IndexScan {
return &IndexScan{table: table, lo: lo, hi: hi}
}
func (s *IndexScan) Open() error {
rids, err := s.table.Index.RangeScan(s.lo, s.hi)
if err != nil {
return err
}
s.rids, s.pos = rids, 0
return nil
}
func (s *IndexScan) Next() (*Tuple, error) {
if s.pos >= len(s.rids) {
return nil, nil
}
rid := s.rids[s.pos]
s.pos++
data, err := s.table.Heap.GetRecord(rid)
if err != nil {
return nil, err
}
values, err := DecodeTuple(data, s.table.Schema)
if err != nil {
return nil, err
}
return &Tuple{Values: values}, nil
}
func (s *IndexScan) Close() error { return nil }
func (s *IndexScan) Columns() []OutputColumn { return tableColumns(s.table) }IndexScanは、Open の時点で範囲内のRIDをまとめて取得しています。B+木の葉をたどりながら1件ずつ返す作りにもできますが、その場合は Next の呼び出しをまたいでB+木の位置を覚えておく必要があり、実装が複雑になります。
Filter
子から受け取った行のうち、条件を満たすものだけを返します。条件を満たさない行は捨てて、次の行を子に要求します。
// sql/executor/filter.go
package executor
import "github.com/yourname/go-rdbms/sql/parser"
// Filter は条件を満たす行だけを上に流すオペレータ
type Filter struct {
child Operator
predicate parser.Expression
}
func NewFilter(child Operator, predicate parser.Expression) *Filter {
return &Filter{child: child, predicate: predicate}
}
func (f *Filter) Open() error { return f.child.Open() }
func (f *Filter) Close() error { return f.child.Close() }
func (f *Filter) Columns() []OutputColumn { return f.child.Columns() }
func (f *Filter) Next() (*Tuple, error) {
for {
tuple, err := f.child.Next()
if err != nil || tuple == nil {
return nil, err
}
ok, err := evalPredicate(f.predicate, tuple, f.child.Columns())
if err != nil {
return nil, err
}
if ok {
return tuple, nil
}
}
}Projection
必要なカラムだけを取り出します。カラム名から列の位置を求める処理は、行ごとに繰り返さないように、作成時に一度だけ行っています。
// sql/executor/projection.go
package executor
import "github.com/yourname/go-rdbms/sql/parser"
// Projection は指定されたカラムだけを取り出すオペレータ
type Projection struct {
child Operator
indexes []int // 子の出力列のうち、何番目を取り出すか
columns []OutputColumn
}
// NewProjection はカラム参照を子の出力列の位置に解決してから作る
func NewProjection(child Operator, refs []*parser.ColumnRef) (*Projection, error) {
childCols := child.Columns()
p := &Projection{child: child}
for _, ref := range refs {
idx, err := resolveColumn(childCols, ref)
if err != nil {
return nil, err
}
p.indexes = append(p.indexes, idx)
p.columns = append(p.columns, childCols[idx])
}
return p, nil
}
func (p *Projection) Open() error { return p.child.Open() }
func (p *Projection) Close() error { return p.child.Close() }
func (p *Projection) Columns() []OutputColumn { return p.columns }
func (p *Projection) Next() (*Tuple, error) {
tuple, err := p.child.Next()
if err != nil || tuple == nil {
return nil, err
}
values := make([]Value, len(p.indexes))
for i, idx := range p.indexes {
values[i] = tuple.Values[idx]
}
return &Tuple{Values: values}, nil
}Nested Loop Join
結合は、最も単純なNested Loop Joinで実装します。外側（outer）の1行ごとに内側（inner）を最初から最後まで読み、結合条件を満たす組を返します。
for 外側の行 in 外側:
for 内側の行 in 内側:
if 結合条件(外側の行, 内側の行):
結果として返す(外側の行 + 内側の行)イテレータモデルでは、この二重ループを Next が呼ばれるたびに1組ずつ進めます。内側を読み終えたら、内側を Close → Open して先頭に戻し、外側を1行進めます。
// sql/executor/nested_loop_join.go
package executor
import "github.com/yourname/go-rdbms/sql/parser"
// NestedLoopJoin は外側の1行ごとに内側を最初から読み直し、条件を満たす組を返すオペレータ
type NestedLoopJoin struct {
outer, inner Operator
condition parser.Expression
columns []OutputColumn
outerTuple *Tuple // 現在処理中の外側の行
}
func NewNestedLoopJoin(outer, inner Operator, condition parser.Expression) *NestedLoopJoin {
cols := append(append([]OutputColumn{}, outer.Columns()...), inner.Columns()...)
return &NestedLoopJoin{outer: outer, inner: inner, condition: condition, columns: cols}
}
func (j *NestedLoopJoin) Columns() []OutputColumn { return j.columns }
func (j *NestedLoopJoin) Open() error {
j.outerTuple = nil
if err := j.outer.Open(); err != nil {
return err
}
return j.inner.Open()
}
func (j *NestedLoopJoin) Next() (*Tuple, error) {
for {
// 外側の行がなければ次の行を読む。外側が尽きたら結合も終わり
if j.outerTuple == nil {
t, err := j.outer.Next()
if err != nil || t == nil {
return nil, err
}
j.outerTuple = t
}
innerTuple, err := j.inner.Next()
if err != nil {
return nil, err
}
if innerTuple == nil {
// 内側を読み終えたら、内側を先頭に戻して外側を1行進める
if err := j.inner.Close(); err != nil {
return nil, err
}
if err := j.inner.Open(); err != nil {
return nil, err
}
j.outerTuple = nil
continue
}
combined := &Tuple{Values: append(append([]Value{}, j.outerTuple.Values...), innerTuple.Values...)}
ok, err := evalPredicate(j.condition, combined, j.columns)
if err != nil {
return nil, err
}
if ok {
return combined, nil
}
}
}
func (j *NestedLoopJoin) Close() error {
if err := j.outer.Close(); err != nil {
return err
}
return j.inner.Close()
}外側が N 行、内側が M 行なら、N × M 回の組み合わせを調べることになります。小さなテーブルどうしなら十分ですが、大きなテーブルどうしでは非常に遅くなります。PostgreSQLなどは、一方をハッシュ表にして突き合わせるHash Joinや、ソート済みの2つの入力を先頭から並行して読むMerge Joinも持っていて、データの量に応じて使い分けます。
プランナー
実行計画の表現
実行計画のノードを定義します。どれも「どのテーブル」「どの条件」といった情報を持つだけの構造体です。デバッグとテストのために、計画の木をテキストで表示する Explain も用意します。
// sql/planner/plan.go
package planner
import (
"fmt"
"math"
"strings"
"github.com/yourname/go-rdbms/sql/catalog"
"github.com/yourname/go-rdbms/sql/parser"
)
// Plan は実行計画の木のノード
// 「何をどの順に行うか」だけを表すデータで、実行はExecutorが担当する
type Plan interface {
planNode()
}
// SeqScanPlan はテーブルの全件走査
type SeqScanPlan struct {
Table *catalog.TableInfo
}
// IndexScanPlan は主キーのインデックスを使った範囲 [Min, Max] の走査
type IndexScanPlan struct {
Table *catalog.TableInfo
Min, Max int64
}
// FilterPlan は条件による絞り込み
type FilterPlan struct {
Child Plan
Predicate parser.Expression
}
// ProjectionPlan は出力カラムの選択
type ProjectionPlan struct {
Child Plan
Columns []*parser.ColumnRef
}
// NestedLoopJoinPlan は2つの入力の結合
type NestedLoopJoinPlan struct {
Outer, Inner Plan
Condition parser.Expression
}
func (*SeqScanPlan) planNode() {}
func (*IndexScanPlan) planNode() {}
func (*FilterPlan) planNode() {}
func (*ProjectionPlan) planNode() {}
func (*NestedLoopJoinPlan) planNode() {}
// Explain は実行計画の木を、字下げしたテキストにする
func Explain(p Plan) string {
var sb strings.Builder
explain(&sb, p, 0)
return sb.String()
}
func explain(sb *strings.Builder, p Plan, depth int) {
sb.WriteString(strings.Repeat(" ", depth))
switch n := p.(type) {
case *SeqScanPlan:
fmt.Fprintf(sb, "SeqScan %s\n", n.Table.Name)
case *IndexScanPlan:
fmt.Fprintf(sb, "IndexScan %s [%s, %s]\n", n.Table.Name, bound(n.Min), bound(n.Max))
case *FilterPlan:
fmt.Fprintf(sb, "Filter %s\n", n.Predicate)
explain(sb, n.Child, depth+1)
case *ProjectionPlan:
names := make([]string, len(n.Columns))
for i, c := range n.Columns {
names[i] = c.String()
}
fmt.Fprintf(sb, "Projection %s\n", strings.Join(names, ", "))
explain(sb, n.Child, depth+1)
case *NestedLoopJoinPlan:
fmt.Fprintf(sb, "NestedLoopJoin %s\n", n.Condition)
explain(sb, n.Outer, depth+1)
explain(sb, n.Inner, depth+1)
}
}
func bound(v int64) string {
switch v {
case math.MinInt64:
return "-inf"
case math.MaxInt64:
return "+inf"
}
return fmt.Sprint(v)
}SELECT文の実行計画を作る
Plannerは、SELECT文から次の形の木を組み立てます。
Projection ← SELECT句（* のときは付けない）
Filter ← WHERE句（あるとき）
NestedLoopJoin ← JOIN句（あるとき）
Scanテーブルの読み方は、WHERE句に主キーの条件があるかどうかで決めます。
// sql/planner/planner.go
package planner
import (
"math"
"github.com/yourname/go-rdbms/sql/catalog"
"github.com/yourname/go-rdbms/sql/parser"
)
// Planner はSELECT文のASTから実行計画を組み立てる
type Planner struct {
catalog *catalog.Catalog
}
func New(cat *catalog.Catalog) *Planner {
return &Planner{catalog: cat}
}
// PlanSelect はSELECT文の実行計画を作る
//
// Projection ← SELECT句（* のときは付けない）
// Filter ← WHERE句（あるとき）
// NestedLoopJoin ← JOIN句（あるとき、左から順に積み上げる）
// Scan
func (p *Planner) PlanSelect(stmt *parser.SelectStatement) (Plan, error) {
from, err := p.catalog.GetTable(stmt.From)
if err != nil {
return nil, err
}
var plan Plan
if len(stmt.Joins) == 0 {
plan = chooseScan(from, stmt.Where)
} else {
plan = &SeqScanPlan{Table: from}
for _, join := range stmt.Joins {
inner, err := p.catalog.GetTable(join.Table)
if err != nil {
return nil, err
}
plan = &NestedLoopJoinPlan{Outer: plan, Inner: &SeqScanPlan{Table: inner}, Condition: join.On}
}
}
// インデックスで範囲を絞った場合も、WHERE句全体のFilterは必ず残す。
// インデックスが扱うのは主キーの条件だけなので、残りの条件をここで確かめる
if stmt.Where != nil {
plan = &FilterPlan{Child: plan, Predicate: stmt.Where}
}
if stmt.Columns != nil {
plan = &ProjectionPlan{Child: plan, Columns: stmt.Columns}
}
return plan, nil
}
// chooseScan はWHERE句に主キーの条件があればIndexScanを、なければSeqScanを選ぶ
func chooseScan(table *catalog.TableInfo, where parser.Expression) Plan {
if lo, hi, ok := indexRange(table, where); ok {
return &IndexScanPlan{Table: table, Min: lo, Max: hi}
}
return &SeqScanPlan{Table: table}
}
// indexRange はANDでつながった条件のうち「主キー 比較演算子 整数」の形のものを集め、
// 主キーが取りうる範囲 [lo, hi] を求める
func indexRange(table *catalog.TableInfo, where parser.Expression) (lo, hi int64, ok bool) {
pk := table.Schema.PrimaryKeyIndex()
if where == nil || pk < 0 || table.Index == nil {
return 0, 0, false
}
pkName := table.Schema.Columns[pk].Name
lo, hi = math.MinInt64, math.MaxInt64
for _, cond := range splitAnd(where) {
op, v, isPK := pkComparison(cond, table.Name, pkName)
if !isPK {
continue
}
switch op {
case "=":
lo, hi = max(lo, v), min(hi, v)
case ">":
lo = max(lo, v+1)
case ">=":
lo = max(lo, v)
case "<":
hi = min(hi, v-1)
case "<=":
hi = min(hi, v)
default: // <> はインデックスで絞れない
continue
}
ok = true
}
return lo, hi, ok
}
// splitAnd は A AND B AND C を [A, B, C] に分解する
func splitAnd(expr parser.Expression) []parser.Expression {
if b, ok := expr.(*parser.BinaryExpr); ok && b.Op == "AND" {
return append(splitAnd(b.Left), splitAnd(b.Right)...)
}
return []parser.Expression{expr}
}
// pkComparison は条件が「主キー op 整数」または「整数 op 主キー」の形なら、
// 主キーを左辺にそろえた演算子と整数を返す
func pkComparison(cond parser.Expression, tableName, pkName string) (string, int64, bool) {
b, ok := cond.(*parser.BinaryExpr)
if !ok {
return "", 0, false
}
isPK := func(e parser.Expression) bool {
col, ok := e.(*parser.ColumnRef)
return ok && col.Name == pkName && (col.Table == "" || col.Table == tableName)
}
if lit, ok := b.Right.(*parser.IntLiteral); ok && isPK(b.Left) {
return b.Op, lit.Value, true
}
if lit, ok := b.Left.(*parser.IntLiteral); ok && isPK(b.Right) {
// 5 < id は id > 5 と同じ
flipped := map[string]string{"=": "=", "<>": "<>", "<": ">", ">": "<", "<=": ">=", ">=": "<="}
return flipped[b.Op], lit.Value, true
}
return "", 0, false
}indexRange は、WHERE句を AND で分解し、「主キー 比較演算子 整数」の形の条件だけを集めて、主キーが取りうる範囲を求めます。例えば id >= 10 AND id < 20 AND name = 'x' なら、範囲は [10, 19] です。name = 'x' はインデックスでは絞れないので無視します。
ここで大事なのは、IndexScanを使う場合もFilterを外さないことです。IndexScanが保証するのは「主キーが範囲内であること」だけで、WHERE句のほかの条件は確かめていません。インデックスには候補を絞り込む役目だけを任せ、最終的な判定は必ずFilterで行います。こうしておけば、範囲の計算が多少広めになっても結果は正しくなります。
次のような場合は、IndexScanを使いません。
id = 1 OR id = 2のようにORを含む場合（ANDで分解できないため）id <> 5のように、範囲で表せない条件しかない場合- JOINを含む場合（本シリーズでは、JOINのときは常にSeqScanを使うことにしています）
エグゼキュータ
Executorは、ASTの種類に応じて処理を振り分けます。SELECTはPlannerで実行計画を作り、build で同じ形のオペレータの木に変換して、Next が nil を返すまで行を集めます。
// sql/executor/executor.go
package executor
import (
"fmt"
"github.com/yourname/go-rdbms/sql/catalog"
"github.com/yourname/go-rdbms/sql/parser"
"github.com/yourname/go-rdbms/sql/planner"
)
// Result はSQL文の実行結果
type Result struct {
Columns []string // SELECTの列名
Rows [][]Value // SELECTの結果行
RowsAffected int // INSERTで追加した行数
Message string // CREATE TABLEなどの結果メッセージ
}
// Executor はSQL文（AST）を実行する
type Executor struct {
catalog *catalog.Catalog
planner *planner.Planner
}
func New(cat *catalog.Catalog) *Executor {
return &Executor{catalog: cat, planner: planner.New(cat)}
}
// Execute はSQL文を1つ実行する
func (e *Executor) Execute(stmt parser.Statement) (*Result, error) {
switch s := stmt.(type) {
case *parser.SelectStatement:
return e.executeSelect(s)
case *parser.InsertStatement:
return e.executeInsert(s)
case *parser.CreateTableStatement:
return e.executeCreateTable(s)
default:
return nil, fmt.Errorf("executor: 未対応の文です: %T", stmt)
}
}
// ---- SELECT ----
func (e *Executor) executeSelect(stmt *parser.SelectStatement) (*Result, error) {
plan, err := e.planner.PlanSelect(stmt)
if err != nil {
return nil, err
}
op, err := e.build(plan)
if err != nil {
return nil, err
}
if err := op.Open(); err != nil {
return nil, err
}
defer op.Close()
result := &Result{}
for _, c := range op.Columns() {
if len(stmt.Joins) > 0 {
result.Columns = append(result.Columns, c.Table+"."+c.Name)
} else {
result.Columns = append(result.Columns, c.Name)
}
}
for {
tuple, err := op.Next()
if err != nil {
return nil, err
}
if tuple == nil {
break
}
result.Rows = append(result.Rows, tuple.Values)
}
return result, nil
}
// build は実行計画の木から、同じ形のオペレータの木を組み立てる
func (e *Executor) build(plan planner.Plan) (Operator, error) {
switch p := plan.(type) {
case *planner.SeqScanPlan:
return NewSeqScan(p.Table), nil
case *planner.IndexScanPlan:
return NewIndexScan(p.Table, p.Min, p.Max), nil
case *planner.FilterPlan:
child, err := e.build(p.Child)
if err != nil {
return nil, err
}
return NewFilter(child, p.Predicate), nil
case *planner.ProjectionPlan:
child, err := e.build(p.Child)
if err != nil {
return nil, err
}
return NewProjection(child, p.Columns)
case *planner.NestedLoopJoinPlan:
outer, err := e.build(p.Outer)
if err != nil {
return nil, err
}
inner, err := e.build(p.Inner)
if err != nil {
return nil, err
}
return NewNestedLoopJoin(outer, inner, p.Condition), nil
default:
return nil, fmt.Errorf("executor: 未対応の実行計画です: %T", plan)
}
}
// ---- INSERT ----
func (e *Executor) executeInsert(stmt *parser.InsertStatement) (*Result, error) {
table, err := e.catalog.GetTable(stmt.Table)
if err != nil {
return nil, err
}
values, err := insertValues(stmt, table.Schema)
if err != nil {
return nil, err
}
data, err := EncodeTuple(values, table.Schema)
if err != nil {
return nil, err
}
// 主キーの重複はヒープに書く前に確かめる
pk := table.Schema.PrimaryKeyIndex()
if pk >= 0 {
if _, found, err := table.Index.Search(values[pk].Int); err != nil {
return nil, err
} else if found {
return nil, fmt.Errorf("executor: 主キー %d は既に存在します", values[pk].Int)
}
}
rid, err := table.Heap.InsertRecord(data)
if err != nil {
return nil, err
}
if pk >= 0 {
if err := table.Index.Insert(values[pk].Int, rid); err != nil {
return nil, err
}
}
return &Result{RowsAffected: 1}, nil
}
// insertValues はVALUESのリテラルを、テーブルのカラム順に並んだ値に変換する
// NULLは扱わないので、すべてのカラムに値を指定する必要がある
func insertValues(stmt *parser.InsertStatement, schema *catalog.Schema) ([]Value, error) {
order := make([]int, len(stmt.Values)) // i番目の値を入れるカラム位置
if stmt.Columns == nil {
for i := range order {
order[i] = i
}
} else {
if len(stmt.Columns) != len(stmt.Values) {
return nil, fmt.Errorf("executor: カラム数(%d)と値の数(%d)が一致しません", len(stmt.Columns), len(stmt.Values))
}
for i, name := range stmt.Columns {
order[i] = -1
for j, col := range schema.Columns {
if col.Name == name {
order[i] = j
}
}
if order[i] < 0 {
return nil, fmt.Errorf("executor: カラム %s は存在しません", name)
}
}
}
if len(stmt.Values) != len(schema.Columns) {
return nil, fmt.Errorf("executor: すべてのカラム(%d個)に値を指定してください", len(schema.Columns))
}
values := make([]Value, len(schema.Columns))
filled := make([]bool, len(schema.Columns))
for i, expr := range stmt.Values {
idx := order[i]
if filled[idx] {
return nil, fmt.Errorf("executor: カラム %s が重複しています", schema.Columns[idx].Name)
}
filled[idx] = true
switch lit := expr.(type) {
case *parser.IntLiteral:
values[idx] = NewInt(lit.Value)
case *parser.StringLiteral:
values[idx] = NewString(lit.Value)
default:
return nil, fmt.Errorf("executor: VALUESにはリテラルを指定してください: %s", expr)
}
}
return values, nil
}
// ---- CREATE TABLE ----
func (e *Executor) executeCreateTable(stmt *parser.CreateTableStatement) (*Result, error) {
columns := make([]catalog.Column, len(stmt.Columns))
for i, def := range stmt.Columns {
col := catalog.Column{Name: def.Name, Length: def.Length, PrimaryKey: def.PrimaryKey}
if def.Type == "INT" {
col.Type = catalog.TypeInt
} else {
col.Type = catalog.TypeVarchar
}
columns[i] = col
}
if _, err := e.catalog.CreateTable(stmt.Table, columns); err != nil {
return nil, err
}
return &Result{Message: fmt.Sprintf("テーブル %s を作成しました", stmt.Table)}, nil
}INSERTでは、VALUESのリテラルをテーブルのカラム順に並べ替えてから、次の順で処理します。
- 主キーのB+木を検索して、同じキーがないことを確かめる
- ヒープファイルにレコードを挿入し、RIDを得る
- 主キーとRIDの組をB+木に挿入する
重複の確認をヒープファイルへの挿入より先に行うのは、重複していた場合にヒープファイルだけに行が残るのを避けるためです。
テストを書く
テーブルの作成から、WHERE句での絞り込み、IndexScanの選択、JOIN、INSERTのエラーまでを、SQLを実行してテストします。IndexScanのテストでは、Plannerが作った実行計画に IndexScan が含まれるかと、結果の件数の両方を確かめています。
// sql/executor/executor_test.go
package executor_test
import (
"fmt"
"os"
"strings"
"testing"
"github.com/yourname/go-rdbms/sql/catalog"
"github.com/yourname/go-rdbms/sql/executor"
"github.com/yourname/go-rdbms/sql/parser"
"github.com/yourname/go-rdbms/sql/planner"
"github.com/yourname/go-rdbms/storage/buffer"
"github.com/yourname/go-rdbms/storage/disk"
)
type testDB struct {
t *testing.T
cat *catalog.Catalog
exec *executor.Executor
}
func setup(t *testing.T) *testDB {
t.Helper()
f, err := os.CreateTemp("", "test-exec-*.db")
if err != nil {
t.Fatal(err)
}
f.Close()
dm, err := disk.NewFileDiskManager(f.Name())
if err != nil {
t.Fatal(err)
}
t.Cleanup(func() {
dm.Close()
os.Remove(f.Name())
})
bpm := buffer.NewBufferPoolManager(dm, 64)
cat := catalog.NewCatalog(bpm)
return &testDB{t: t, cat: cat, exec: executor.New(cat)}
}
// run はSQLを実行し、エラーならテストを失敗させる
func (db *testDB) run(sql string) *executor.Result {
db.t.Helper()
res, err := db.try(sql)
if err != nil {
db.t.Fatalf("%s: %v", sql, err)
}
return res
}
func (db *testDB) try(sql string) (*executor.Result, error) {
stmt, err := parser.Parse(sql)
if err != nil {
return nil, err
}
return db.exec.Execute(stmt)
}
// rows は結果を "1,Alice" のような文字列の並びにする
func rows(res *executor.Result) []string {
var out []string
for _, row := range res.Rows {
vals := make([]string, len(row))
for i, v := range row {
vals[i] = v.String()
}
out = append(out, strings.Join(vals, ","))
}
return out
}
func (db *testDB) seedUsers() {
db.run("CREATE TABLE users (id INT PRIMARY KEY, name VARCHAR(20), age INT)")
db.run("INSERT INTO users VALUES (1, 'Alice', 30)")
db.run("INSERT INTO users VALUES (2, 'Bob', 25)")
db.run("INSERT INTO users (name, age, id) VALUES ('Charlie', 35, 3)") // カラム順を入れ替えてもよい
}
func TestExecutor_SelectWhere(t *testing.T) {
db := setup(t)
db.seedUsers()
res := db.run("SELECT name, id FROM users WHERE age >= 30 AND name <> 'Bob'")
if got := strings.Join(res.Columns, ","); got != "NAME,ID" {
t.Errorf("列名不一致: got %s", got)
}
if got := strings.Join(rows(res), " | "); got != "Alice,1 | Charlie,3" {
t.Errorf("結果不一致: got %s", got)
}
}
func TestExecutor_IndexScan(t *testing.T) {
db := setup(t)
db.run("CREATE TABLE items (id INT PRIMARY KEY, label VARCHAR(10))")
for i := 1; i <= 500; i++ {
db.run(fmt.Sprintf("INSERT INTO items VALUES (%d, 'item%d')", i, i))
}
tests := []struct {
where string
wantPlan string
wantCount int
}{
{"id = 42", "IndexScan ITEMS [42, 42]", 1},
{"id > 490", "IndexScan ITEMS [491, +inf]", 10},
{"100 >= id AND id >= 91", "IndexScan ITEMS [91, 100]", 10},
{"id >= 10 AND label = 'item20'", "IndexScan ITEMS [10, +inf]", 1},
{"label = 'item20'", "SeqScan ITEMS", 1},
{"id = 1 OR id = 2", "SeqScan ITEMS", 2}, // ORはインデックスで絞らない
}
for _, tt := range tests {
sql := "SELECT * FROM items WHERE " + tt.where
stmt, _ := parser.Parse(sql)
plan, err := planner.New(db.cat).PlanSelect(stmt.(*parser.SelectStatement))
if err != nil {
t.Fatal(err)
}
if explain := planner.Explain(plan); !strings.Contains(explain, tt.wantPlan) {
t.Errorf("%s: 実行計画に %q が含まれない:\n%s", tt.where, tt.wantPlan, explain)
}
if got := len(db.run(sql).Rows); got != tt.wantCount {
t.Errorf("%s: want %d件, got %d件", tt.where, tt.wantCount, got)
}
}
}
func TestExecutor_Join(t *testing.T) {
db := setup(t)
db.seedUsers()
db.run("CREATE TABLE orders (id INT PRIMARY KEY, user_id INT, item VARCHAR(20))")
db.run("INSERT INTO orders VALUES (10, 1, 'book')")
db.run("INSERT INTO orders VALUES (11, 3, 'pen')")
db.run("INSERT INTO orders VALUES (12, 1, 'desk')")
res := db.run("SELECT users.name, orders.item FROM users JOIN orders ON users.id = orders.user_id WHERE orders.id >= 11")
if got := strings.Join(res.Columns, ","); got != "USERS.NAME,ORDERS.ITEM" {
t.Errorf("列名不一致: got %s", got)
}
if got := strings.Join(rows(res), " | "); got != "Alice,desk | Charlie,pen" {
t.Errorf("結果不一致: got %s", got)
}
// どちらのテーブルにもある ID を修飾せずに使うとエラー
if _, err := db.try("SELECT id FROM users JOIN orders ON users.id = orders.user_id"); err == nil {
t.Error("あいまいなカラム参照がエラーにならなかった")
}
}
func TestExecutor_InsertErrors(t *testing.T) {
db := setup(t)
db.seedUsers()
for _, sql := range []string{
"INSERT INTO users VALUES (1, 'Dup', 20)", // 主キーの重複
"INSERT INTO users VALUES ('x', 'Eve', 20)", // 型の不一致
"INSERT INTO users VALUES (4, 'Eve')", // 値が足りない
"INSERT INTO users VALUES (5, 'abcdefghijklmnopqrstu', 1)", // VARCHAR(20)を超える
"INSERT INTO users VALUES (3000000000, 'Big', 1)", // INTの範囲外
"INSERT INTO nothing VALUES (1)", // 存在しないテーブル
} {
if _, err := db.try(sql); err == nil {
t.Errorf("エラーになるはず: %s", sql)
} else {
t.Logf("%s → %v", sql, err)
}
}
if got := len(db.run("SELECT * FROM users").Rows); got != 3 {
t.Errorf("失敗したINSERTで行が増えている: %d件", got)
}
}
func TestPlanner_Explain(t *testing.T) {
db := setup(t)
db.seedUsers()
stmt, _ := parser.Parse("SELECT name FROM users WHERE id = 2")
plan, err := planner.New(db.cat).PlanSelect(stmt.(*parser.SelectStatement))
if err != nil {
t.Fatal(err)
}
want := "Projection NAME\n" +
" Filter (ID = 2)\n" +
" IndexScan USERS [2, 2]\n"
if got := planner.Explain(plan); got != want {
t.Errorf("Explain不一致:\nwant:\n%s\ngot:\n%s", want, got)
}
}go test ./sql/executor/... -v期待される出力（=== RUN の行は省略）：
--- PASS: TestExecutor_SelectWhere (0.00s)
--- PASS: TestExecutor_IndexScan (0.00s)
--- PASS: TestExecutor_Join (0.00s)
executor_test.go:167: INSERT INTO users VALUES (1, 'Dup', 20) → executor: 主キー 1 は既に存在します
executor_test.go:167: INSERT INTO users VALUES ('x', 'Eve', 20) → executor: カラム ID は INT 型です
executor_test.go:167: INSERT INTO users VALUES (4, 'Eve') → executor: すべてのカラム(3個)に値を指定してください
executor_test.go:167: INSERT INTO users VALUES (5, 'abcdefghijklmnopqrstu', 1) → executor: カラム NAME は最大20文字です（21文字）
executor_test.go:167: INSERT INTO users VALUES (3000000000, 'Big', 1) → executor: カラム ID の値 3000000000 はINTの範囲外です
executor_test.go:167: INSERT INTO nothing VALUES (1) → catalog: テーブル NOTHING は存在しません
--- PASS: TestExecutor_InsertErrors (0.00s)
--- PASS: TestPlanner_Explain (0.00s)
PASS
ok github.com/yourname/go-rdbms/sql/executor 0.235sここまでのコード全体像
go-rdbms/
├── storage/
│ ├── page/ disk/ buffer/ heap/ btree/
└── sql/
├── lexer/ ← 字句解析
├── parser/ ← 構文解析・AST
├── catalog/
│ ├── schema.go ← データ型・カラム・スキーマ（本章）
│ └── catalog.go ← メモリ上のカタログ（本章。次章で永続化）
├── planner/
│ ├── plan.go ← 実行計画のノードとExplain（本章）
│ └── planner.go ← SELECT文の実行計画を作る（本章）
└── executor/
├── value.go ← 値・タプルのエンコード（本章）
├── operator.go ← Operatorインターフェース（本章）
├── eval.go ← 条件式の評価（本章）
├── scan.go ← SeqScan・IndexScan（本章）
├── filter.go ← Filter（本章）
├── projection.go ← Projection（本章）
├── nested_loop_join.go ← Nested Loop Join（本章）
└── executor.go ← SQL文の実行（本章）PlannerとExecutorの設計で意識したポイント
① 計画（データ）と実行（オペレータ）を分ける
Plannerは実行計画というデータを作るだけで、ページには触れません。計画を Explain で表示してテストできるうえ、パッケージの依存も一方向に保てます。
② すべてのオペレータが同じインターフェースを持つ
Open / Next / Close / Columns さえ実装すれば、どのオペレータの上にも下にも置けます。新しいオペレータ（例えばソートや集約）を追加するときも、既存のオペレータを変える必要はありません。
③ インデックスは候補を絞るだけで、最終判定はFilterに任せる
IndexScanを使うかどうかにかかわらずFilterを残すことで、結果の正しさがインデックスの選び方に左右されないようにしています。
④ 型を厳密に扱う
型の違う値の比較、範囲外のINT、長すぎるVARCHARはすべてエラーにします。暗黙の変換をしないことで、実装を単純にしつつ、誤ったデータが入るのを防ぎます。
まとめ
- 論理プランは「何をするか」、物理プランは「どうやるか」を表す。本シリーズではPlannerが物理プランを直接作る
- Plannerは実行計画というデータを作り、Executorはそれと同じ形のオペレータの木を組み立てて実行する
- イテレータモデル（Volcano Model）では、すべてのオペレータが
Open/Next/Closeを持ち、1行ずつ上に流す - SeqScan・IndexScan・Filter・Projection・Nested Loop Joinを実装し、WHERE句に主キーの条件があればIndexScanを選ぶようにした
- IndexScanを使うときもFilterを残し、インデックスには候補の絞り込みだけを任せる
次章では、この章で用意したメモリ上のカタログを発展させ、テーブル定義をファイルに永続化して、データベースを開き直してもテーブルが使えるようにします。