Rustでデータベースを自作する Part4: クエリ実行エンジン

はじめに

Part 3ではSQLパーサーを作って、SQL文字列をASTに変換できるようになった。

でもAST作っただけじゃ何も起きない。今回はいよいよクエリ実行エンジンを作って、実際にデータを操作できるようにする。

クエリ実行エンジンって何？

パースしたSQLを実際に実行する部分。

SQL文字列 → [パーサー] → AST → [実行エンジン] → 結果

例えばSELECT * FROM users WHERE age > 25を実行したら、usersテーブルから条件に合う行を返す。シンプルでしょ？

基本的なデータ構造

行（Row）

データベースの基本単位は行。カラム名と値のペアを保持する。

use std::collections::HashMap;
use crate::sql::*;

/// 行（レコード）
#[derive(Debug, Clone)]
pub struct Row {
    pub values: HashMap<String, Value>,
}

impl Row {
    pub fn new() -> Self {
        Row {
            values: HashMap::new(),
        }
    }

    pub fn get(&self, column: &str) -> Option<&Value> {
        self.values.get(column)
    }

    pub fn set(&mut self, column: &str, value: Value) {
        self.values.insert(column.to_string(), value);
    }
}

HashMapを使ってカラム名から値を引けるようにしてる。

テーブルスキーマ

/// テーブルのスキーマ
#[derive(Debug, Clone)]
pub struct TableSchema {
    pub name: String,
    pub columns: Vec<ColumnDefinition>,
}

impl TableSchema {
    pub fn get_column(&self, name: &str) -> Option<&ColumnDefinition> {
        self.columns.iter().find(|c| c.name == name)
    }

    pub fn column_names(&self) -> Vec<&str> {
        self.columns.iter().map(|c| c.name.as_str()).collect()
    }
}

テーブル

スキーマと行の集合：

/// テーブル（メモリ上の簡易実装）
#[derive(Debug, Clone)]
pub struct Table {
    pub schema: TableSchema,
    pub rows: Vec<Row>,
}

impl Table {
    pub fn new(schema: TableSchema) -> Self {
        Table {
            schema,
            rows: Vec::new(),
        }
    }

    pub fn insert(&mut self, row: Row) {
        self.rows.push(row);
    }
}

今回はメモリ上にデータを保持するシンプルな実装。永続化はPart 5以降で。

データベース

複数のテーブルを管理：

/// データベース
#[derive(Debug)]
pub struct Database {
    pub tables: HashMap<String, Table>,
}

impl Database {
    pub fn new() -> Self {
        Database {
            tables: HashMap::new(),
        }
    }

    pub fn create_table(&mut self, name: &str, columns: Vec<ColumnDefinition>) -> Result<(), String> {
        if self.tables.contains_key(name) {
            return Err(format!("Table '{}' already exists", name));
        }

        let schema = TableSchema {
            name: name.to_string(),
            columns,
        };
        self.tables.insert(name.to_string(), Table::new(schema));
        Ok(())
    }

    pub fn drop_table(&mut self, name: &str) -> Result<(), String> {
        if self.tables.remove(name).is_none() {
            return Err(format!("Table '{}' does not exist", name));
        }
        Ok(())
    }
}

クエリ結果の表現

実行結果は3種類：

/// クエリ実行結果
#[derive(Debug)]
pub enum QueryResult {
    /// SELECT結果
    Select {
        columns: Vec<String>,
        rows: Vec<Row>,
    },
    /// INSERT/UPDATE/DELETE結果
    Affected(usize),
    /// DDL成功
    Success(String),
}

impl QueryResult {
    /// 結果を表示用の文字列に変換
    pub fn to_display_string(&self) -> String {
        match self {
            QueryResult::Select { columns, rows } => {
                let mut result = String::new();
                
                // ヘッダー
                result.push_str(&columns.join(" | "));
                result.push('\n');
                result.push_str(&"-".repeat(columns.len() * 15));
                result.push('\n');
                
                // 行
                for row in rows {
                    let values: Vec<String> = columns
                        .iter()
                        .map(|col| {
                            row.get(col)
                                .map(|v| format!("{}", v))
                                .unwrap_or_else(|| "NULL".to_string())
                        })
                        .collect();
                    result.push_str(&values.join(" | "));
                    result.push('\n');
                }
                
                result.push_str(&format!("\n({} rows)", rows.len()));
                result
            }
            QueryResult::Affected(n) => format!("{} row(s) affected", n),
            QueryResult::Success(msg) => msg.clone(),
        }
    }
}

SELECTは行のリスト、INSERT/UPDATE/DELETEは影響を受けた行数、DDLは成功メッセージ。

実行器（Executor）本体

ここからが本番。

/// クエリ実行器
pub struct Executor<'a> {
    db: &'a mut Database,
}

impl<'a> Executor<'a> {
    pub fn new(db: &'a mut Database) -> Self {
        Executor { db }
    }

    /// SQL文を実行
    pub fn execute(&mut self, stmt: Statement) -> Result<QueryResult, String> {
        match stmt {
            Statement::Select(s) => self.execute_select(s),
            Statement::Insert(s) => self.execute_insert(s),
            Statement::Update(s) => self.execute_update(s),
            Statement::Delete(s) => self.execute_delete(s),
            Statement::CreateTable(s) => self.execute_create_table(s),
            Statement::DropTable(s) => self.execute_drop_table(s),
        }
    }
}

ライフタイム'aを使って、データベースへの可変参照を保持してる。

SELECT実行

一番複雑なのがSELECT：

fn execute_select(&self, stmt: SelectStatement) -> Result<QueryResult, String> {
    let table = self.db.get_table(&stmt.from)
        .ok_or_else(|| format!("Table '{}' does not exist", stmt.from))?;

    // カラム名を決定
    let columns: Vec<String> = match &stmt.columns[..] {
        [SelectColumn::Wildcard] => {
            // SELECT * の場合は全カラム
            table.schema.column_names().into_iter().map(String::from).collect()
        }
        cols => {
            // 指定されたカラムのみ
            cols.iter()
                .filter_map(|c| {
                    if let SelectColumn::Column(name) = c {
                        Some(name.clone())
                    } else {
                        None
                    }
                })
                .collect()
        }
    };

    // フィルタリング（WHERE）
    let mut result_rows: Vec<Row> = table
        .rows
        .iter()
        .filter(|row| {
            if let Some(ref where_clause) = stmt.where_clause {
                evaluate_expression(where_clause, row)
                    .map(|v| matches!(v, Value::Boolean(true)))
                    .unwrap_or(false)
            } else {
                true  // WHERE句なければ全部通す
            }
        })
        .cloned()
        .collect();

    // ソート（ORDER BY）
    if let Some(order_by) = stmt.order_by {
        for clause in order_by.iter().rev() {
            result_rows.sort_by(|a, b| {
                let va = a.get(&clause.column);
                let vb = b.get(&clause.column);
                let cmp = compare_values(va, vb);
                if clause.ascending {
                    cmp
                } else {
                    cmp.reverse()
                }
            });
        }
    }

    // LIMIT
    if let Some(limit) = stmt.limit {
        result_rows.truncate(limit as usize);
    }

    Ok(QueryResult::Select {
        columns,
        rows: result_rows,
    })
}

処理の流れ：

1. テーブルを取得
2. SELECT *か特定カラムかでカラム名リストを作成
3. WHERE句があれば条件でフィルタ
4. ORDER BYがあればソート
5. LIMITがあれば切り詰め

INSERT実行

fn execute_insert(&mut self, stmt: InsertStatement) -> Result<QueryResult, String> {
    let table = self.db.get_table_mut(&stmt.table)
        .ok_or_else(|| format!("Table '{}' does not exist", stmt.table))?;

    let column_names: Vec<String> = stmt.columns.unwrap_or_else(|| {
        // カラム指定なければスキーマ順
        table.schema.column_names().into_iter().map(String::from).collect()
    });

    let mut count = 0;
    for values in stmt.values {
        if values.len() != column_names.len() {
            return Err("Column count doesn't match value count".to_string());
        }

        let mut row = Row::new();
        for (col, val) in column_names.iter().zip(values.into_iter()) {
            row.set(col, val);
        }
        table.insert(row);
        count += 1;
    }

    Ok(QueryResult::Affected(count))
}

カラム名と値をペアにしてRowを作成。

UPDATE実行

fn execute_update(&mut self, stmt: UpdateStatement) -> Result<QueryResult, String> {
    let table = self.db.get_table_mut(&stmt.table)
        .ok_or_else(|| format!("Table '{}' does not exist", stmt.table))?;

    let mut count = 0;
    for row in &mut table.rows {
        // WHERE条件をチェック
        let matches = if let Some(ref where_clause) = stmt.where_clause {
            evaluate_expression(where_clause, row)
                .map(|v| matches!(v, Value::Boolean(true)))
                .unwrap_or(false)
        } else {
            true
        };

        if matches {
            // SET句の値を適用
            for (col, val) in &stmt.set {
                row.set(col, val.clone());
            }
            count += 1;
        }
    }

    Ok(QueryResult::Affected(count))
}

DELETE実行

fn execute_delete(&mut self, stmt: DeleteStatement) -> Result<QueryResult, String> {
    let table = self.db.get_table_mut(&stmt.table)
        .ok_or_else(|| format!("Table '{}' does not exist", stmt.table))?;

    let original_len = table.rows.len();

    // Vec::retainで条件に合わない行を残す
    table.rows.retain(|row| {
        if let Some(ref where_clause) = stmt.where_clause {
            // WHEREに一致しないものを残す
            !evaluate_expression(where_clause, row)
                .map(|v| matches!(v, Value::Boolean(true)))
                .unwrap_or(false)
        } else {
            false // WHERE句がなければ全削除
        }
    });

    let deleted = original_len - table.rows.len();
    Ok(QueryResult::Affected(deleted))
}

retainを使って条件に一致しない行だけ残す。逆転の発想。

式の評価

WHERE句の条件評価は再帰的に行う：

fn evaluate_expression(expr: &Expression, row: &Row) -> Result<Value, String> {
    match expr {
        Expression::Literal(v) => Ok(v.clone()),
        
        Expression::Column(name) => {
            row.get(name)
                .cloned()
                .ok_or_else(|| format!("Column '{}' not found", name))
        }
        
        Expression::BinaryOp { left, op, right } => {
            let lv = evaluate_expression(left, row)?;
            let rv = evaluate_expression(right, row)?;
            apply_binary_op(&lv, op, &rv)
        }
        
        Expression::LogicalOp { left, op, right } => {
            let lv = evaluate_expression(left, row)?;
            let lb = matches!(lv, Value::Boolean(true));
            
            match op {
                LogicalOperator::And => {
                    // 短絡評価
                    if !lb {
                        return Ok(Value::Boolean(false));
                    }
                    let rv = evaluate_expression(right, row)?;
                    Ok(Value::Boolean(matches!(rv, Value::Boolean(true))))
                }
                LogicalOperator::Or => {
                    if lb {
                        return Ok(Value::Boolean(true));
                    }
                    let rv = evaluate_expression(right, row)?;
                    Ok(Value::Boolean(matches!(rv, Value::Boolean(true))))
                }
            }
        }
        
        Expression::Not(inner) => {
            let v = evaluate_expression(inner, row)?;
            Ok(Value::Boolean(!matches!(v, Value::Boolean(true))))
        }
        
        Expression::IsNull { expr, negated } => {
            let v = evaluate_expression(expr, row)?;
            let is_null = matches!(v, Value::Null);
            Ok(Value::Boolean(if *negated { !is_null } else { is_null }))
        }
    }
}

ポイント：

• Literal：そのまま値を返す
• Column：行から値を取得
• BinaryOp：両辺を評価して比較演算を適用
• LogicalOp：ANDとORの短絡評価
• Not：否定
• IsNull：NULL判定

比較演算

fn apply_binary_op(left: &Value, op: &BinaryOperator, right: &Value) -> Result<Value, String> {
    let result = match op {
        BinaryOperator::Eq => values_equal(left, right),
        BinaryOperator::NotEq => !values_equal(left, right),
        BinaryOperator::Lt => compare_values(Some(left), Some(right)) == std::cmp::Ordering::Less,
        BinaryOperator::LtEq => compare_values(Some(left), Some(right)) != std::cmp::Ordering::Greater,
        BinaryOperator::Gt => compare_values(Some(left), Some(right)) == std::cmp::Ordering::Greater,
        BinaryOperator::GtEq => compare_values(Some(left), Some(right)) != std::cmp::Ordering::Less,
        BinaryOperator::Like => {
            if let (Value::Text(s), Value::Text(pattern)) = (left, right) {
                like_match(s, pattern)
            } else {
                false
            }
        }
    };
    Ok(Value::Boolean(result))
}

LIKE演算

%ワイルドカードに対応：

fn like_match(s: &str, pattern: &str) -> bool {
    let parts: Vec<&str> = pattern.split('%').collect();
    
    if parts.len() == 1 {
        return s == pattern;  // %がなければ完全一致
    }
    
    let mut pos = 0;
    
    // 先頭がパターンで始まるか
    if !parts[0].is_empty() {
        if !s.starts_with(parts[0]) {
            return false;
        }
        pos = parts[0].len();
    }
    
    // 中間のパターンをチェック
    for part in &parts[1..parts.len()-1] {
        if let Some(found) = s[pos..].find(part) {
            pos += found + part.len();
        } else {
            return false;
        }
    }
    
    // 末尾がパターンで終わるか
    if let Some(last) = parts.last() {
        if !last.is_empty() && !s[pos..].ends_with(last) {
            return false;
        }
    }
    
    true
}

A%で始まるか、%iceで終わるか、%li%を含むか、などを判定できる。

テスト

#[test]
fn test_select_with_where() {
    let mut db = setup_test_db();  // 3人のユーザーがいる
    let stmt = parse_sql("SELECT * FROM users WHERE age > 25").unwrap();
    let result = Executor::new(&mut db).execute(stmt).unwrap();
    
    if let QueryResult::Select { rows, .. } = result {
        assert_eq!(rows.len(), 2); // Bob(30) と Charlie(35)
    }
}

#[test]
fn test_update() {
    let mut db = setup_test_db();
    let stmt = parse_sql("UPDATE users SET age = 26 WHERE name = 'Alice'").unwrap();
    let result = Executor::new(&mut db).execute(stmt).unwrap();
    
    assert!(matches!(result, QueryResult::Affected(1)));
    
    // 確認
    let stmt = parse_sql("SELECT * FROM users WHERE name = 'Alice'").unwrap();
    let result = Executor::new(&mut db).execute(stmt).unwrap();
    
    if let QueryResult::Select { rows, .. } = result {
        assert_eq!(rows[0].get("age"), Some(&Value::Integer(26)));
    }
}

動かしてみる

$ cargo run
=== Query Executor デモ ===

SQL: CREATE TABLE users (id INTEGER PRIMARY KEY, name TEXT NOT NULL, age INTEGER)
  → Table 'users' created

SQL: INSERT INTO users (id, name, age) VALUES (1, 'Alice', 25)
  → 1 row(s) affected

SQL: INSERT INTO users (id, name, age) VALUES (2, 'Bob', 30)
  → 1 row(s) affected

SQL: INSERT INTO users (id, name, age) VALUES (3, 'Charlie', 35)
  → 1 row(s) affected

SQL: INSERT INTO users (id, name, age) VALUES (4, 'Dave', 28)
  → 1 row(s) affected

SQL: SELECT * FROM users
id | name | age
---------------------------------------------
1 | 'Alice' | 25
2 | 'Bob' | 30
3 | 'Charlie' | 35
4 | 'Dave' | 28

(4 rows)

SQL: SELECT * FROM users WHERE age > 28
id | name | age
---------------------------------------------
2 | 'Bob' | 30
3 | 'Charlie' | 35

(2 rows)

SQL: SELECT * FROM users ORDER BY age DESC
id | name | age
---------------------------------------------
3 | 'Charlie' | 35
2 | 'Bob' | 30
4 | 'Dave' | 28
1 | 'Alice' | 25

(4 rows)

SQL: UPDATE users SET age = 26 WHERE name = 'Alice'
  → 1 row(s) affected

SQL: DELETE FROM users WHERE id = 4
  → 1 row(s) affected

SQL: SELECT * FROM users ORDER BY id
id | name | age
---------------------------------------------
1 | 'Alice' | 26
2 | 'Bob' | 30
3 | 'Charlie' | 35

(3 rows)

おおお、動いてる！CREATE TABLE、INSERT、SELECT、UPDATE、DELETEが全部動作してる。

実装の注意点

借用チェッカーとの戦い

Rustで実行エンジン作ると、必ずぶつかるのが借用問題。

// これはダメ
fn execute_update(&mut self, stmt: UpdateStatement) -> Result<QueryResult, String> {
    let table = self.db.get_table_mut(&stmt.table)?;  // 可変借用
    
    for row in &mut table.rows {
        // selfを使おうとするとエラー
        self.evaluate_expression(...);  // ここでself不変借用が発生
    }
}

解決策：evaluate_expressionをメソッドじゃなくフリー関数にする。

fn evaluate_expression(expr: &Expression, row: &Row) -> Result<Value, String> {
    // selfを使わない
}

NULLの扱い

SQLのNULLは特殊。比較するとFALSE（というかUNKNOWN）になる：

// NULL = NULL は true じゃない
fn values_equal(a: &Value, b: &Value) -> bool {
    match (a, b) {
        (Value::Null, Value::Null) => true,  // 今回は簡易実装でtrueにしてる
        // ...
    }
}

本来は3値論理（TRUE/FALSE/UNKNOWN）が必要だけど、今回は簡易実装。

まとめ

Part 4では：

1. データ構造：Row、Table、Database
2. クエリ結果：Select/Affected/Successの3種類
3. SELECT実行：WHERE、ORDER BY、LIMIT対応
4. INSERT/UPDATE/DELETE：CRUD操作
5. 式の評価：比較演算、論理演算、LIKEマッチング

これでSQLを実際に実行できるようになった。

次回Part 5では**トランザクションとWAL（Write-Ahead Log）**を実装して、データの永続化と障害復旧に対応する予定。