Rustで作るSQL Parser
この記事は「Eureka Advent Calendar 2022」17日目の記事です。
こんにちは、今年の9月にBack-end Teamにジョインした @nao99999 です。
まだ入社して3ヶ月で右も左もわかりませんが、同僚は優秀で良い人が多く、楽しく働いています。
入社して日が浅いので、実務のネタではないのですが、今回はRustに関して書いてみようと思います。
(Rustといえばカニなのでカニの画像にしました。ただ同僚にカニが小さいとツッコみを受けました。)
Table of Contents
- Introduction
- Goals & Anti-Goals
- Design
- Lexer
- Parser
- Conclusion
- References
1 Introduction
ここ数年DBが好きになりまして、関連書籍を読んだり、調べたりしているのですが、もっと深く理解を得るためにDB関連で何か作ってみたいと思うようになりました。
一口にDBと言ってもとても範囲が広いです。ですので、まずはとっつきやすいところかなと思い、SQLの構文解析でもしてみようと思いました。また平行してRustにも興味が湧いていたので、Rustを使ってMySQLのSQL Parserを書いてみようと思いました。(過去に取り組んだことはあるのですが、もう一回チャレンジです。)
構文解析処理に関しては「Go言語でつくるインタプリタ」を読んで自分でも書けそうだなと思ったのもあり、今回の実装はとても参考にさせていただきました。
また今回書いたコードは下記になります。
2 Goals & Anti-Goals
2.1 Goals
- Pratt Parsingを参考にしたLexer/Parser実装
- 簡単なSELECT文までが対象
2.2 Anti-Goals
- yaccやbisonなどのParser Generatorの話はしない
3 Design
一般的に、一貫性や堅牢性などの観点や、自動生成の利点を考えるとParser Generatorを使用したほうが良いと思われます。Parser Generatorはアカデミックな分野などで長い間議論され成熟してるので、手書きに比べてバグの少なさやパフォーマンスの点で優れています。Productionなどで構文解析が必要な場合は、すでにあるParser Generatorの採用を第１に考えることが多いと思われます。
今回はRustの勉強とチャレンジも兼ねているので手書きで書こうと思います。
前述の通り今回はPratt Parserを参考にしてSQLをパースをします。具体的にはループ処理と再帰処理を組み合わせた再帰下降処理となります。流れとしては、LexerがSQLをTokenにし、ParserがTokenをASTにします。
- SQL → (by Lexer) → Token → (by Parser) → AST
最終的な出力結果としては、下記のようなSQLがあったとします。
SELECT 1+2, id, name FROM user WHERE id = 1;そのSQLを下記のようなASTの構造体にしたいと思います。
Select {
columns: [
Column {
value: Infix { op: Plus, left: Number(1), right: Number(2) }, alias: ""
},
Column {
value: Identifier("id"), alias: ""
},
Column {
value: Identifier("name"), alias: ""
}
],
table: TableExpression {
from: "user",
where_cond: Some(Infix { op: Eq, left: Identifier("id"), right: Number(1) }),
group_by: None
}
}4 Lexer
まずは字句解析です。下記のようにSQLを渡したらTokenにすることを期待します。 SelectKwd などの括弧の中はTokenの種類を指しています。
SELECT 1+2, id, name FROM user WHERE id = 1;
↓
- SELECT (SelectKwd)
- 1 (NumberType)
- + (Plus)
- 2 (NumberType)
- , (Comma)
- id (Ident)
- , (Comma)
- name (Ident)
- FROM (From)
- user (Ident)
- WHERE (Where)
- id (Ident)
- = (EqOp)
- 1 (NumberType)
- ; (Semicoln)Tokenの種類は、 pingcap/parser のyaccファイルを参考に抽出しました。量が多いので一部抜粋して記載します。( 全体はこちらです。 )
#[derive(Clone, Debug, Eq, EnumIter, Hash, PartialEq)]
pub enum TokenType {
/// System
StartToken,
Illegal(String),
EOF,
/// Synbol Char
RightBra, // ]
RightBrace, // }
/// Literal
Ident(String), // a~z, A~Z, 0~ 9
NumberType(i64), // 0 ~ 9
/// Keyword
Alter, // "ALTER"
And, // "AND"
Both, // "BOTH"
}基本的には1文字ずつ読み進めていくことで、この字句が何を意味しているかを判断していきます。
/// 1文字ずつ読んでいきます.
fn read_char(&mut self) {
if self.is_over_next_position() {
// '0' is EOF
self.current_char = CHAR_EOF;
} else {
self.current_char = self.query.as_bytes()[self.next_position] as char;
}
self.current_position = self.next_position;
self.next_position += 1;
}1文字ずつ読んでいきますが、時に先読みをしながら進めていくような箇所もあります。( ex. = を読んだ時に =か ==かを判定しないといけない。 )
また演算子やデリミタ以外の文字列(予約語やカラム名)の場合は、アルファベットである限りLexerの位置を進めて単語を抽出します。
// 1文字ずつ読んでTokenにしていきます.
// 説明のため実装を省略して記載しています.
pub fn next_token(&mut self) -> Option<Token> {
self.skip_whitespace();
let token = match self.current_char {
// Symbol系
'&' => Token::new(TokenType::Ampersand),
'@' => Token::new(TokenType::AtMark),
// 先読みをして判断する場合
'=' => {
if self.peek_char() == '=' {
self.read_char();
Token::new(TokenType::EqEqOp)
} else {
Token::new(TokenType::EqOp)
}
}
'0' => Token::new(TokenType::EOF),
_ => {
if self.is_letter() {
// 予約語やカラム名
let ident = self.read_identifier();
let token_type = Token::lookup_ident(ident.clone());
Token::new(token_type)
} else if self.is_number() {
// 数字
let number = self.read_number();
Token::new(TokenType::NumberType(number))
} else {
Token::new(TokenType::Illegal(self.current_char.to_string()))
}
}
};
self.read_char();
Some(token)
}SQLの予約語はそれなりに数が多く正直驚きましたが、用意してしまえば字句解析に関してはそれなりに作れるのだなと手応えを感じました。一方で知らないMySQLの予約語郡を眺めて、知らないことばかりだなと気が遠くなりました。
5 Parser
次にParserです。LexerによってTokenに変換できたので、これをASTにしていきます。標準SQLのBNFを参考に、今回簡易なBNFを定義してみました。このイメージでParserを実装していこうと思います。
余談ですがBNFで表現しておくと後々yaccなどにinputできる利点もありそうです。
<select statement> ::= SELECT [ <expression> ] <table expression>
<table expression> ::= <from clause> [ <where clause> ]
<where clause> ::= <value expression>
<value expression> ::= <clause> | <clause> (+|-|+|/|=|AND|OR) <clause>
<clause> ::= <identifier> | <number> | <function>...5.1 AST
ASTはこちらです。一部抜粋して記載します。できる限りBNFに表現を寄せています。
まずは value expression を表現していきます。またRustのENUMを使って複数の value expressoinを同じ型として扱えるようにしています。
一部前置演算子式のvalue型が
i64だけになってますがご容赦ください。本来は Value Expressionで表現したほうが良さそうです。
#[derive(Debug, Clone)]
pub enum ValueExpression {
Identifier(String),
Number(i64),
Bool(bool),
Prefix {op: PrefixOp, right: i64},
Infix {op: InfixOp, left: Box<ValueExpression>, right: Box<ValueExpression>},
}次にselect statement とtable expression です。こちらも同様にENUMを使って複数の文をまとめて表現できるようにしています。今後INSERT文やUPDATE文なども増えた時に対応できるようになっています。これでSELECT文をASTとして表現できました。
#[derive(Debug, Clone)]
pub enum Statement {
Select {
columns: Vec<Column>,
table: TableExpression,
},
}
#[derive(Debug, Clone)]
pub struct TableExpression {
pub from: String,
pub where_cond: Option<ValueExpression>,
pub group_by: Option<Vec<Column>>,
}5.2 Parsing
最後にParserの実装です。Parserは、現在位置のToken (current_token)と、1つ先のToken (peek_token)を保持しています。
pub struct Parser {
lexer: Lexer,
current_token: Token,
peek_token: Token,
}この保持しているTokenを読み進めながら、Tokenが特定の文や式に対して期待した通りの順番になっているかを検証していく作業がParserの役割です。例えばSELECT文であるなら、今回BNFで定義した通りの順番でTokenが並んでいることを検証します。
まずは先頭のTokenをチェックします。先頭のTokenが SELECTならSELECT文と期待してパースしていきます。下記がSELECT文のパース処理です。 SELECT とカラムをパースしたら、次は FROM 句であることを期待しますが、FROM 句じゃない場合はエラーになります。
fn parse_select_statement(&mut self) -> Statement {
self.next_token();
let columns = self.parse_columns();
if !self.expect_peek(TokenType::From) {
panic!("not expected type");
}
let table = self.parse_table_expression();
if self.expect_peek(TokenType::SemiColon) {
self.next_token();
}
Statement::Select { columns, table }
}次に FROM句以降のパースです。こちらも同様にBNFの定義に従ってパースしていきます。今回はサブクエリには対応してないので、FROM 句のあとはtable名が来ることを期待しています。table名は識別子( Ident)のTokenTypeですので、もしそうじゃなかったら同じくここでもエラーにしています。
またoptionalですが、もしWHERE 句があれば同様にパースしていきます。
fn parse_table_expression(&mut self) -> TableExpression {
self.next_token();
let table_name = match &self.current_token.token_type {
TokenType::Ident(table_name) => table_name.clone(),
_ => panic!("not expected type!"),
};
let where_cond = if self.expect_peek(TokenType::Where) {
self.next_token();
Some(self.parse_value_expression(LOWEAT))
} else {
None
};
TableExpression {
from: table_name.to_string(),
where_cond: where_cond,
group_by: None,
}
}このようにループ処理でTokenをチェックし、時には先読みをすることで、クエリが正しいかどうかを検証しながら、ASTを構築していきます。
最終的に出来上がったParserはこちらです。またASTも想定通り生成できました。
Pratt Parserによる、演算子優先度を考慮した前置演算子式や中置演算子式の実装が入っていますが、時間と記事のサイズの関係で今回は説明しません。参考：Go言語でつくるインタプリタ
6 Conclusion
Pratt Parserを参考に何とかSQLをパースすることができました。抜粋だらけで丁寧に説明することが出来なかったので、わかりづらい記事になってしまったかもしれません。ただ、何だか自分にも出来そうだなとか、敷居が下がったなとか、雰囲気でも伝われば嬉しいです。
Rustのコードに関しては、 clone を多様したり、エラーハンドリングが panic になってたりと手抜きになってしまってる点に関しては、温かく見てもらえればなと思います。
今後は、今回書いたParserにDDLやDMLのサポートを広げていったり、Rust製のyaccを使ってMySQL Parserを自動生成したりしてみたいです。
明日は @stereowind さんよる「10 tips for building an advanced data platform」です。お楽しみに！
