2019/10/02

Summer InternshipでSpannerのSQLパーサ・型チェッカを作りました！

Author:: tenntenn

, 2019/10/02

Summer InternshipでSpannerのSQLパーサ・型チェッカを作りました！

こんにちは。Summer Internship for Engineer 2019の「Expert team Go Engineer (Backend)」に参加した@make.now.justです。
（なお、記事の投稿は代理で@tenntennが行っています。）

本稿では、Summer Internshipの報告として、作成したGoogle Cloud Spanner（以下、Spanner）のSQLパーサ・型チェッカであるmemefishの解説と、また少しですがSummer Internshipの紹介をします。

TL; DR

memefishというSpannerのSQLのパーサ・型チェッカを作りました。
SQLの構文解析・意味解析は通常のプログラミング言語と少し異なる部分があり苦労しました。
Expert teamでのインターンではこういった自由な開発が行えます。興味のある学生は来年のSummer Internshipに参加しましょう。

作ったもの

memefishというSpannerで利用できるSQLのパーサ・型チェッカを作りました。

SpannerはGCP (Google Cloud Platform)のサービスの1つの分散RDBで、高い可用性や水平分散などの特徴を持ちます。
このSpannerで使われているSQLのパーサと、式の型チェックやクエリの意味解析を行う部分を実装しました。

memfishはOSSとして、以下のGitHubのリポジトリで公開されています。

github.com

執筆時では特にCLIツールなどを用意していません。しかし、GitHubからcloneしてきてtools/ディレクトリ以下にあるプログラムを実行することで、どういうライブラリか雰囲気は掴めるでしょう。

$ go run ./tools/analyze 'select 1 as x, "foo" as y'
+-------+--------+
|   X   |   Y    |
+-------+--------+
| INT64 | STRING |
+-------+--------+

パースや型チェックの際にエラーを検出すると、丁寧なエラーメッセージが出力されます。たとえば、以下のように、型エラーのメッセージに加えて、行番号や対応するソースコードの部分も出力されます。

$ go run ./tools/analyze 'select x + 1 from (select "foo" as x)'
analyze error::1:8: operator + requires two INT64/FLOAT64, but: STRING, INT64
1:  select x + 1 from (select "foo" as x)
^~~~~

ライブラリとしての使い方ははREADME.mdに記載しているのでそちらも参照してください。

memfishで出来ることは主に以下の3つです。列挙しておくと、

Spanner SQLのパース
抽象構文木(AST)からSpanner SQLを生成
SQLの式の型チェック・意味解析

なぜ作ったのか？

Spannerを用いてサービスの開発・運用を行っていると、分析・検証のためマニュアルでSQLを実行したい場合があります。
しかし、個人情報保護などの観点から、開発者であれば誰でもSQLを実行できる状態は好ましくありません。そこで、メルペイでは実前に実行したいSQLを申請し、認可を得る仕組みがあります。申請されたSQLのチェックは手作業で行われています。
この作業の一部を自動で行うことができれば、チェックするコストを下げることができるでしょう。たとえば、以下のように「個人情報を含む列にアクセスしていないか」などをチェックして事前に警告を出すことも可能です。なお、もちろん以下のSQLはサンプルであり、実際にメルペイで使われているものではありません。

また、執筆時点ではSpannerを対象にしたツールはあまりありません。そのため、それらのツールを作るための基盤もほとんどありません。。
そこで、パーサや意味解析を行うライブラリを作ることで、こうしたツールの開発を補助できると考えました。

このような背景からSpanner SQLの解析の基盤となるmemefishを開発するに至りました。

既存ライブラリとの比較

memefishの開発を始める前に、既存のライブラリでSpanner SQLを解析できるものが無いか調べました。

ZetaSQL

ZetaSQLはGoogleの開発しているSQLの解析フレームワークで、Spanner SQLに近い構文のSQLをパース・解析することができます。
しかし、C++で書かれておりGoから呼び出すのが簡単ではないことや、執筆時ではmacOSでのビルドが公式にサポートされていないことから、今回は利用しませんでした。

spanner/spansql

spanner/spansqlはGoのGCPライブラリ(googleapis/google-cloud-go)中にあるSpanner SQLのパーサです。
2019年の7月末に公開された、新しいライブラリです。

基本的なSQLのパースは行えるのですが、いくつか求めた機能が足りない場合がありました。
特にASTにソースコード上の位置が保存されていないため、ASTの解析中に起きたエラーの位置を上手く報告できません。
こうした理由から、spansqlを利用せず、独自にパーサから開発することにしました。

また、後で書くようにこのライブラリへのコントリビュートもしました。

大変だったこと

次に、memfishを開発する上で大変だったことについて、”前提編”、”パーサ編”、”型チェック・意味解析編”の3つに分けて解説します。

前提編

ここまでSpanner SQLと記載してきましたが、公開された仕様は存在しません。
なお、SpannerのドキュメントにはSpanner SQLの構文に関する簡易的な解説はありますが、完全なものは公開されていません。

もちろん、ドキュメントに記載されている通りにSQLを書いても実際のSpannerで動かないということではありません。しかし、筆者が試したところ実際にはドキュメントに記載されているよりも柔軟な構文を受け入れているようでした。

たとえば、公式のドキュメントには「0xから始まる数値は16進数の数値として解釈される」とありますが、実際には0xだけではなく0Xも受け入れます。
可能な限り実際のSpannerに近い挙動を実現するため、こうしたエッジケースをひたすら探していました。
それらのクエリをひとつひとつ実行して検証していくことが作業の大半だったといっても過言ではありません。

パーサ編

まずトークナイザレベルの問題で、.のあとの識別子の特別な挙動があります。
たとえば、次のSQLは正しく動作します。

select t.1 from (select 1 as <span class="synConstant">1</span>) as t

.の後に数値が続いても識別子として認識されて、列へのアクセスになります。

これはトークナイザの段階で特別に処理するしかなく、Lexerに状態を持たせて特定のトークンのあとに.が来たら、次のパースを別の処理にする、という対応を取りました。

https://github.com/MakeNowJust/memefish/blob/c4eed89c6691fae02de9565a33177a71b95008ab/pkg/parser/lexer.go#L113-L115

また、SQLをパースする上で有名な問題として、()がサブクエリの始まりか通常の式を囲うものかどうかの判断が難しい、というものがあります。

もちろん(select ...のような並びであればこの括弧はサブクエリの始まりと判断できます。
一方、((select ...のような場合はどうでしょうか。
最初の括弧の部分でサブクエリを始めるべきか、次の括弧でサブクエリを始めるべきか、この位置では判断できません。

-- 1. 最初の括弧でサブクエリを始める場合
((select ...) union all ...)
-- 2. 次の括弧でサブクエリを始める場合
((select ...) + ...)

そのため、内側の括弧が閉じるまで先読みして、その次のトークンで判断する、といった処理が必要になります。

https://github.com/MakeNowJust/memefish/blob/c4eed89c6691fae02de9565a33177a71b95008ab/pkg/parser/parser.go#L1460-L1509

この方法はうまく動いていますが、あまり効率の良い処理とは言えないでしょう。読者のみなさま中でもっと効率的な方法を思い付いた方がいたらPull Requestをお願いします。

型チェック・意味解析編

型チェックについては特段複雑なところはありません。しかし、注意する点としてNULLの存在があります。
NULLはSQLの型として明示的に記述することはないのですが、どの型へも暗黙的に変換が可能です。
他にも、いくつかのケースで暗黙的に型が変換される場合があり、その対応には少し苦労しました。

たとえば、次のクエリの結果のXの型はFLOAT64になります。

(select 1 as x) union all (select 1.5)

この暗黙の型変換(coercion)というのはドキュメントに何となく書かれているのですが、具体的にどういった場面で行なわれているのかまでは明記されていません。
検証のためにナンセンスなクエリを投げまくる必要があり、かなり大変でした。

他に難しかったところは、GROUP BYでの集計のあとSELECTなどの式が有効かチェックする部分です。
たとえば次のクエリは全て無効なものになります。

-- 1. 集計キーに指定されていない y を SELECT で使っているからエラー
select x, y from (select 1 as x, 2 as y) group by x
-- 2. 集計キーに指定されていない t.y が t.* の中に含まれるからエラー
select t.* from (select 1 as x, 2 as y) as t group by t.x
-- 3. 集計キーに指定されていない y を HAVING 節で使っているからエラー
select x from (select 1 as x, 2 as y) group by t.x having y = 2

3番目の例でGROUP BYではt.xと指定しているにも関わらず、SELECTではxとしても有効なことに注意してください。

また、GROUP BYで単純に名前を指定した場合、FROM節の名前よりも先にSELECTの結果の列を検索するという特徴があります。

-- x が集計キーに指定されていないのでエラー
select 1 + 2 as x, x as x1 from (select 1 as x, 2 as y)
group by x -- <- この x は 1 + 2 as x をさす

しかし、SELECTがexpression.*を含んでいた場合、結果の列の名前を得るには、その式を評価する必要があります。
つまり、

SELECTの式が有効か確認するにはGROUP BYをチェックする必要がある
GROUP BYをチェックするにはSELECTの式を評価する必要がある

という循環参照の状態になっています。

これを回避するため、現状ではSELECTの式を評価して一度結果の列の名前を得たあとGROUP BYをチェックして、必要ならもう一度SELECTの式が有効か確認する、という2段階の評価を行なっています。
ただ、これは効率の良い方法ではないので、より効率的な方法に直したいと考えています。

今後の展望

インターンの期間は4週間という短い期間だったため、達成できていないこともいくつもあります。
それらを含め、現在の状態・今後の展望を列挙します。

Spannerとの互換性をより高める
- Spannerの挙動を完全に捉えきれてない部分
  - = で比較できる型なのかどうか、などの判定
  - INTERSECTやEXCEPTした場合の結果の型
- 単純に時間が足りなくて実装できていないところ
  - 大半の関数の実装
    - 執筆時点ではSUMとCONCATしか実装できていない
    - 関数のシグネチャを書くとチェックしてくれるような仕組みが必要
  - TABLESAMPE節など一部の構文
    - 後回しにした
memefishを使ったツールの開発
- 間に合わなかったのが勿体無いところ
- 色々とアイディアはある
  - ridgepoleのようなDDLを利用するマイグレーションツール
  - Goのソースコード中のSELECT文を解析して、パフォーマンス的に問題のあるSQLを警告するlinter
  - 当初のモチベーションにあった、センシティブな列へのアクセスを検出するツール

また、最終的な目標としてはこれらを使って ローカルで動くSpannerのエミュレータ が作れればいいと思っています。

インターンについて

やったことについて

今回のインターンですが、始めからこうしたSQLのパーサ・型チェッカの開発を行うということを決めていたわけではありませんでした。
Expert teamのインターンでは、GoのOSSの開発・コントリビュートを行う以外の方向は決まっておらず、具体的に何をやるかは参加者に一任されていました。
最初の方はGoの静的解析を行うつもりで、いくつか簡単な静的解析ツールを開発したりもしていました。

https://github.com/MakeNowJust/enumcase:
列挙型っぽい値をswitch文で分岐しているときに漏れがないかチェックするツール
https://github.com/MakeNowJust/bluesoul:
コメントに含まれるthe theのような冠詞の重複を指摘してくれるツール

後者は、多くの著名なOSSのコードからもthe theのような文法ミスを見つけることができてコントリビュートの機会を作ってくれるので、面白いツールだと思っています。

しかし、別のインターン参加者である@masahiro.matsuiさんと方向性が被ってしまいそうだったのと、Goの静的解析でインターンの成果と呼べる程度の大きさのものを作るのが難しそうだと感じていたため、別の方向を模索し始めました。
自分はパーサを書くのが好きなので、最終的にこういったパーサや解析器を作ることが出来て良かったです。

他には、業務時間中にいくつかのOSSへコントリビュートすることができて、特にgoogle-cloud-goのspanner/spansqlへ出した文字列リテラルのトークナイザを追加するものがマージされたのは嬉しかったです。
この変更は300行以上の変更があり、一筋縄ではマージされなかったのですが、やり取りのうちにコードが良くなっていくという体験が貴重だったと思います。

https://code-review.googlesource.com/c/gocloud/+/44490code-review.googlesource.com

環境について

メルカリ／メルペイのオフィスは六本木ヒルズにあるので、毎日六本木まで通う必要があります。
自宅から六本木まで地味に遠かったのでちょっと辛かったです。

しかし、出勤時間などは比較的融通が利いたので、朝起きれなくて困る、みたいなことはありませんでした。

また、六本木という土地柄ランチがどこも高く、どこで食べても1000円くらいは持っていかれます。
なので、メンターランチやチームビルディングなどの制度を上手く使っていくといいのだと思います。
僕は面倒だったのでマクドナルドでハンバーガーとチキンクリスプばかり食べてましたが‥‥。

社内にはフリーの自販機があって、モンスターエナジーなどが飲み放題です。
エナドリの飲み過ぎには注意したいところです。

そんなこんなで、この長い記事に最後まで目を通していただきありがとうございました。