株式会社primeNumberPublicationへの投稿
🐘

Analyzer （一人自作RDBMS Advent Calendar 2025 5日目）

gtnao
に公開
Rust
Database
DB
RDBMS
transaction
tech

この記事は「一人自作RDBMS Advent Calendar 2025」5日目の記事です。

本日の実装はGitHubにあります。昨日からの差分は以下のコマンドで確認できます。

git diff --no-index day04 day05

今日のゴール

Analyzerを実装し、Parserが生成したASTに対してテーブル名・カラム名の解決と型情報の付与を行います。

Analyzerとは

Analyzerは、ASTに含まれる識別子（テーブル名、カラム名、関数名など）をカタログと照合して解決し、型情報を付与するコンポーネントです。

データベースによって呼び方は異なります。PostgreSQLでは「Analyzer」（analyze.c）、DuckDBでは「Binder」と呼ばれています。本記事ではPostgreSQLに倣ってAnalyzerと呼びます。

なぜAnalyzerが必要か

昨日実装したParserは、SQL文字列をASTに変換します。しかし、このASTには以下の情報が欠けています:

  • テーブルusersは実際に存在するのか？
  • カラムidはどのテーブルのどのカラムなのか？
  • id > 10の比較で、idはINTか？10と比較可能か？

これらを検証・解決するのがAnalyzerの役割です。

Parser出力: AST（生の構文木）
   ↓ Analyzer
Analyzer出力: Analyzed AST（識別子が解決され、型情報が付与された構文木）

Catalog（システムカタログ）

Analyzerが識別子を解決するには、テーブルとカラムの情報を持つCatalogが必要です。

PostgreSQLでは、カタログ情報自体もテーブルとして格納されています。pg_classにテーブル一覧、pg_attributeにカラム情報が入っており、SQLで直接参照できます。

-- PostgreSQLでテーブル一覧を見る
SELECT relname FROM pg_class WHERE relkind = 'r';

しかし、私たちの実装ではまだテーブルをまともに読み書きできる状態にありません。そこで今回はusers(id INT NOT NULL, name VARCHAR)という固定スキーマをハードコードしています。

Range Table Entry（RTE）

Analyzerはカラム参照を解決する際、「今どのテーブルがスコープにあるか」を追跡する必要があります。単一テーブルのクエリなら単純ですが、JOINやサブクエリが絡むと複雑になります。

SELECT u.id, o.order_date FROM users u JOIN orders o ON u.id = o.user_id

ここではuとoという2つの「テーブルのようなもの」がスコープに入ります。u.idを見たとき、uがどのテーブルを指すのかを解決する仕組みが必要です。

さらにサブクエリを考えると、状況はより複雑になります。

SELECT * FROM (SELECT id, name FROM users) AS subquery

このsubqueryはカタログに存在しません。クエリ実行時に動的に生成される「仮想的なテーブル」です。しかし、外側のSELECT文から見れば、subqueryも実テーブルusersも同じように「カラムを持つもの」として扱いたいはずです。

Range Table Entry（RTE）は、これらを統一的に扱うための抽象化です。RTEは「カラムを出力するもの」を表し、その出典（実テーブル、サブクエリ、JOIN結果など）に関わらず、同じインターフェースでカラム解決ができます。

RTEはPostgreSQLの内部実装に由来する概念です。

#[derive(Debug, Clone)]
pub enum TableSource {
    BaseTable {
        table_id: usize,
        table_name: String,
    },
    // 将来: Subquery { ... }, Join { ... }
}

#[derive(Debug, Clone)]
pub struct OutputColumn {
    pub name: String,
    pub data_type: DataType,
    pub nullable: bool,
}

#[derive(Debug, Clone)]
pub struct RangeTableEntry {
    pub rte_index: usize,
    pub source: TableSource,
    pub output_columns: Vec<OutputColumn>,
}

重要なのはoutput_columnsです。実テーブルならカタログから取得したカラム定義、サブクエリならそのSELECT結果のスキーマが入ります。カラム参照の解決は常にこのoutput_columnsに対して行われるため、RTEの出典が何であるかを意識する必要がありません。

今回は単一の実テーブルのみ対応なのでTableSource::BaseTableしかありませんが、この設計により将来SubqueryやJoinを追加しても、カラム解決のロジックは変更不要です。

Analyzed AST

Analyzerの結果として生成される型付きASTです。カラム参照はrte_index（どのRTEか）とcolumn_index（そのRTE内の何番目のカラムか）で表現されます。

#[derive(Debug, Clone)]
pub struct AnalyzedSelectStatement {
    pub range_table: Vec<RangeTableEntry>,
    pub select_items: Vec<AnalyzedSelectItem>,
    pub from_rte_index: usize,
    pub where_clause: Option<AnalyzedExpr>,
}

#[derive(Debug, Clone)]
pub struct AnalyzedSelectItem {
    pub expr: AnalyzedExpr,
    pub alias: Option<String>,
}

#[derive(Debug, Clone)]
pub struct AnalyzedColumnRef {
    pub rte_index: usize,
    pub column_index: usize,
    pub column_name: String,
    pub data_type: DataType,
}

生のASTとの違いは、Column("id")がColumnRef { rte_index: 0, column_index: 0, data_type: Int, ... }のように具体的な参照に解決されている点です。

Analyzer実装

Analyzerは解析中に2つの状態を持ちます。

pub struct Analyzer<'a> {
    catalog: &'a Catalog,
    range_table: Vec<RangeTableEntry>,  // 出力に含まれる
    scopes: Vec<Scope>,
}

range_tableは解析結果（AnalyzedSelectStatement）に含まれる出力です。一方、scopesは解析中に「現在どのRTEがカラム解決の対象か」を追跡するための内部状態で、出力には含まれません。

Scope（名前解決のコンテキスト）

SQLではテーブル名やエイリアスが有効な範囲が構文的に決まっています。Scopeはこの有効範囲を管理します。

struct ScopeEntry {
    name: String,      // テーブル名またはエイリアス
    rte_index: usize,  // range_table内のインデックス
}

struct Scope {
    entries: Vec<ScopeEntry>,
}

さらに、Scopeはスタックとして管理されます。これは相関サブクエリで、内側のクエリから外側のカラムを参照できるようにするためです。

SELECT * FROM users u
WHERE EXISTS (SELECT 1 FROM orders o WHERE o.user_id = u.id)
                                           ^^^^^^^^^^^
                                           外側のスコープを参照

内側のサブクエリでu.idを解決するには、外側のスコープも見る必要があります。スコープをスタックで管理し、内側から外側に向かって探索することで実現します。

SELECT文の解析

FROM句のテーブルからRTEを作成し、スコープに登録します。

let table_ref = &stmt.from;  // TableRef { name, alias }

// RTEを作成してrange_tableに追加
let rte_index = self.add_rte(
    TableSource::BaseTable { table_id, table_name: table_ref.name.clone() },
    output_columns,
);

// スコープにRTEを登録（解析中のみ使用）
self.push_scope();
let scope_name = table_ref.alias.clone().unwrap_or(table_ref.name.clone());
self.current_scope().add_rte(scope_name, rte_index);

カラム参照の解決

カラム名が与えられると、スコープを内側から外側へ探索してRTEを見つけます。

fn analyze_column(&self, name: &str) -> Result<AnalyzedExpr> {
    for scope in self.scopes.iter().rev() {
        for entry in &scope.entries {
            let rte = &self.range_table[entry.rte_index];
            if let Some(col_idx) = rte.get_column_index(name) {
                let col = &rte.output_columns[col_idx];
                return Ok(AnalyzedExpr::ColumnRef(AnalyzedColumnRef {
                    rte_index: entry.rte_index,
                    column_index: col_idx,
                    column_name: name.to_string(),
                    data_type: col.data_type.clone(),
                }));
            }
        }
    }
    bail!("column '{name}' not found")
}

スコープを内側から外側に向かって探索し、各RTEのoutput_columnsからカラムを検索します。

INSERT文の型チェック

INSERT文では、値の数がカラム数と一致するか、各値の型が期待される型と一致するかを検証します。NULL値については、対象カラムがNULL許容かどうかもチェックします。

動作確認

正常なクエリとエラーケースをテストします。

let valid_sqls = vec![
    "SELECT * FROM users",
    "SELECT id, name FROM users",
    "SELECT id FROM users WHERE id > 10",
    "INSERT INTO users VALUES (1, 'Alice')",
    "INSERT INTO users VALUES (2, NULL)",  // name is nullable
];

let error_sqls = vec![
    ("SELECT * FROM unknown_table", "table not found"),
    ("SELECT unknown_col FROM users", "column not found"),
    ("INSERT INTO users VALUES (1)", "wrong number of values"),
    ("INSERT INTO users VALUES ('Alice', 1)", "type mismatch"),
    ("INSERT INTO users VALUES (NULL, 'Alice')", "not nullable"),  // id is NOT NULL
];

実行結果（一部抜粋）:

SQL: SELECT * FROM users
Analyzed: Select(
    AnalyzedSelectStatement {
        range_table: [
            RangeTableEntry {
                rte_index: 0,
                source: BaseTable { table_id: 0, table_name: "users" },
                output_columns: [
                    OutputColumn { name: "id", data_type: Int, nullable: false },
                    OutputColumn { name: "name", data_type: Varchar, nullable: true },
                ],
            },
        ],
        select_items: [
            AnalyzedSelectItem { expr: ColumnRef(...), alias: None },
            AnalyzedSelectItem { expr: ColumnRef(...), alias: None },
        ],
        from_rte_index: 0,
        where_clause: None,
    },
)

SQL: SELECT id + 1 FROM users
Analyzed: Select(
    AnalyzedSelectStatement {
        ...
        select_items: [
            AnalyzedSelectItem {
                expr: BinaryOp { left: ColumnRef(...), op: Add, right: Literal(1), result_type: Int },
                alias: None,
            },
        ],
        ...
    },
)

=== Error Cases ===

SQL: SELECT * FROM unknown_table
Got: table 'unknown_table' not found

SQL: INSERT INTO users VALUES ('Alice', 1)
Got: type mismatch for column 'id': expected Int, got Varchar

SELECT *が2つのAnalyzedSelectItemに展開され、SELECT id + 1のような式も正しく解析されています。

現時点の課題

Analyzed ASTは「何をすべきか」を表現していますが、「どう実行するか」はまだ決まっていません。実際にディスクからデータを読み取り、結果を返すにはExecutorが必要です。

次回予告

明日はExecutorを実装します。

Analyzed ASTを受け取り、実際にデータを読み取って結果を返すエンジンを作ります。

GitHubで編集を提案
株式会社primeNumber
株式会社primeNumberPublication

「あらゆるデータを、ビジネスの力に変える」データテクノロジーカンパニー。クラウドETL「TROCCO」やクラウド データカタログ「COMETA」、データテクノロジー領域の課題解決を実現するプロフェッショナルサービスを提供しています。

Discussion