Skip to content

01-sql-parser.md

Latest commit

 

History

History
227 lines (179 loc) · 9.59 KB

01-sql-parser.md

File metadata and controls

227 lines (179 loc) · 9.59 KB

SQL Parser Plan

目的

SQL 構文を理解することを主目的として、学習用 RDBMS の最初の実装対象として SQL パーサーを作る。

方針は次の通り。

  • 最初は文字列を直接読み進める手書き parser を実装する
  • parser は構文解析だけを担当し、テーブル存在確認や型解決はしない
  • 将来的に sqlparser-rs を導入しやすいよう、自前 AST を中心に設計する
  • トランザクション構文は最初の parser スコープから外し、 単一文の CRUD を優先したうえで後続計画へ切り出す

現在の実装状況

2026-03-22 時点で、sql crate の hand-written parser は 次の最小 CRUD をサポートしている。

CREATE TABLE users (id INT, name TEXT, active BOOLEAN);
CREATE TABLE metrics (score FLOAT, note NULL);
INSERT INTO users VALUES (1, 'Alice');
INSERT INTO users (id, name, active) VALUES (1, 'Alice', true);
UPDATE users SET name = 'Bob' WHERE id = 1;
UPDATE users SET active = false;
DELETE FROM users WHERE id = 1;
DELETE FROM users;
SELECT id FROM users;
SELECT id, name FROM users;
SELECT * FROM users;
SELECT DISTINCT id FROM users;
SELECT id AS user_id FROM users;
SELECT id user_id FROM users;
SELECT COUNT(id) FROM users;
SELECT COUNT(*) FROM users;
SELECT id + 1 FROM users;
SELECT -1 FROM users;
SELECT id FROM users WHERE id = 1;
SELECT id FROM users WHERE id = (SELECT id FROM users);
SELECT id FROM users WHERE NOT id = 1;
SELECT id FROM users WHERE id = 1 AND active = 1;
SELECT id FROM users WHERE id = 1 OR active = 1;
SELECT id FROM users WHERE (id = 1);
SELECT id FROM users AS u;
SELECT id FROM (SELECT id FROM users) AS u;
SELECT users.id FROM users JOIN orders ON users.id = orders.user_id;
SELECT id FROM users JOIN orders USING (user_id);
SELECT id FROM users GROUP BY id;
SELECT id FROM users GROUP BY id HAVING COUNT(id) > 1;
SELECT id FROM users ORDER BY COUNT(id) DESC;

現在の式パーサーは比較式、NOT、unary -、AND、OR、括弧付き条件、 簡単な算術演算、COUNT(...) のような関数呼び出し、 scalar subquery、true / false / NULL の最小リテラルを対象とする。 内部では式パーサーを独立させ、 primary、unary、乗除、加減算、比較、NOT、AND、OR の順に優先順位を積み上げている。 JOIN ... ON ...、UPDATE ... SET ...、DELETE ... WHERE ...、 INSERT ... VALUES (...) でも同じ式の仕組みを再利用している。

SELECT 項目は * を除き、 単純列、AS 付き列別名、暗黙列別名、関数呼び出し、一般式を できるだけ同じ考え方で表現する。 FROM と JOIN の参照先も、 通常テーブルと最小の subquery を同じ枠組みで扱う。

INSERT は列リスト省略形と列リスト明示形の単一行 VALUES をサポートする。 UPDATE は単一テーブルに対する SET 句と任意の WHERE をサポートする。 DELETE は単一テーブルに対する任意の WHERE をサポートする。 CREATE TABLE は列名と最小データ型だけを持つ定義をサポートする。

スコープ

現段階で到達した SELECT

SELECT については、現在の実装状況に列挙した最小形を 第一段階の到達点とする。

JOIN の派生構文、派生表の広い対応、LIMIT / OFFSET などの 追加拡張はこの計画には含めず、後続の 05-select-extensions.md に切り出す。

今後サポートしたい CRUD 全体

SELECT 以外については、次の最小形を到達点とする。

CREATE TABLE users (id INT, name TEXT, active BOOLEAN);
INSERT INTO users VALUES (1, 'Alice', true);
INSERT INTO users (id, name, active) VALUES (1, 'Alice', true);
UPDATE users SET name = 'Bob' WHERE id = 1;
DELETE FROM users WHERE id = 1;

現時点の制約

  • SELECT の関数呼び出しは最小形の COUNT(...) と scalar subquery から対応しているが、 一般的な関数群や方言差までは未対応
  • ORDER BY / GROUP BY / HAVING / DISTINCT は最小実装であり、 すべての SQL 方言や派生構文を網羅しているわけではない
  • subquery は WHERE id = (SELECT ...) や FROM (SELECT ...) AS alias のような 最小形に限って対応しており、結合先 subquery や複雑な派生表は未対応
  • JOIN は JOIN / LEFT JOIN / RIGHT JOIN / FULL JOIN と ON / USING の最小形に限って対応しており、 INNER JOIN、LEFT OUTER JOIN、結合先 (SELECT ...) AS alias の広い派生形は未対応
  • 行数制御は未対応であり、LIMIT / OFFSET やそれに類する方言構文はまだ読めない
  • INSERT は単一行 VALUES だけに限って対応しており、 複数行 VALUES や INSERT ... SELECT ... は未対応
  • UPDATE は単一テーブルの SET ... [WHERE ...] だけに限って対応しており、 UPDATE ... FROM ... のような派生構文は未対応
  • DELETE は単一テーブルの DELETE FROM ... [WHERE ...] だけに限って対応しており、 USING を伴う派生構文や結合削除は未対応
  • CREATE TABLE は列名と型名だけの最小形に限って対応しており、 制約、既定値、PRIMARY KEY、NOT NULL、VARCHAR(n) は未対応
  • データ型は INT / TEXT / BOOLEAN / FLOAT / NULL から開始し、 INTEGER と BOOL は最小の別名として受け付ける
  • BEGIN / COMMIT / ROLLBACK はまだ未対応であり、 後続の 03-transaction-control.md で扱う

実装方針

1. Statement parser

文単位は再帰下降で実装する。

現時点では Parser が文字列を直接読み進める方式を採る。 空白スキップ、キーワード読取、識別子読取のような小さい補助処理を組み合わせ、 必要に応じて先読みと消費で句境界を判定する。

2. FROM 句の設計

FROM 句は単なる文字列ではなく、 基準テーブル、結合先、結合条件を区別できる構造で表現する。

これにより、最小形の FROM users から、 FROM users AS u JOIN orders USING (user_id) のような形まで段階的に拡張できる。

3. Expression parser

現時点では式パーサーを分離し、 WHERE と JOIN ... ON ... で共通利用している。 論理条件、算術演算、関数呼び出し、scalar subquery までは実装済みで、 UPDATE ... SET ... やさらに広い式構文への展開を今後進める。

最終的に目指す優先順位は次の通り。

  1. primary: identifier, literal, parenthesized expression, simple function call
  2. unary: NOT, unary -
  3. multiplicative: *, /
  4. additive: +, -
  5. comparison: =, !=, <, <=, >, >=
  6. logical and: AND
  7. logical or: OR

AST設計

既存の AST は土台として使い、現時点では次の方針を採っている。

  • INSERT は対象テーブル、任意の列リスト、値リストで表現する
  • UPDATE と DELETE を表現できるようにする
  • JOIN 条件で ON と USING の両方を表現できるようにする
  • 列別名や関数呼び出しを扱うため、SELECT 項目は式ベースを基本形にする
  • * は通常の式とは別扱いにする
  • 列定義の型は types crate のデータ型を使う
  • リテラル値は共通の値表現を使う
  • parser と binder の責務を分けるため、AST では名前解決をしない

実装順

直近の優先順位

  1. query 側で使いやすい形に AST と executor の境界を調整する
  2. SELECT の将来拡張へ進むか、CRUD を planner / executor へ接続する
  3. 将来の SELECT 拡張

SELECT の将来拡張は、現在の CRUD 実装を一通り通したあとに 05-select-extensions.md の計画として進める。

CRUD 全体の実装順

  1. AST を CRUD 対応の形に整理する
  2. SELECT を今後の句拡張に耐える形へ寄せる
  3. INSERT を実装する
  4. UPDATE / DELETE を実装する
  5. CREATE TABLE を実装する
  6. query 側で使いやすい形に AST と executor の境界を調整する

1 から 5 までは完了し、現在は 6 の段階に入っている。

テスト方針

Parser

  • SQL 文字列から期待した AST が得られる
  • SELECT、INSERT、UPDATE、DELETE、CREATE TABLE は 正常系と異常系をテーブルドリブンで検証する
  • 別名、JOIN ... ON ...、JOIN ... USING (...) を個別ケースで固定する
  • WHERE は NOT、AND、OR の優先順位と括弧あり式を追加で検証する
  • 不正な構文で分かりやすいエラーが返る

第一段階の成功条件

第一段階の SELECT については、以下がすべてパースできれば完了とする。

SELECT id FROM users;
SELECT id, name FROM users;
SELECT * FROM users;
SELECT id AS user_id FROM users;
SELECT id user_id FROM users;
SELECT id FROM users WHERE id = 1;
SELECT id FROM users WHERE NOT id = 1;
SELECT id FROM users WHERE id = 1 AND active = 1;
SELECT id FROM users WHERE id = 1 OR active = 1;
SELECT id FROM users WHERE (id = 1);
SELECT id FROM users AS u;
SELECT users.id FROM users JOIN orders ON users.id = orders.user_id;
SELECT id FROM users JOIN orders USING (user_id);

後続方針

  • まずは自前パーサーで SQL -> AST の流れを理解する
  • その後、必要なら sqlparser-rs を使って自前 AST へ変換する adapter を追加する
  • planner, optimizer, transaction はこの段階では広げすぎない