Apache Phoenix. HBase への SQL アクセスを提供するレイヤらしい。もともとの開発者はSalesforce.

文法は ANTLR3 で書かれていた。AST は自前で作る。人の書いた semantic action を眺めるのは勉強になる。そしてみんな SQL 実装してるな。自分で。実行部分の難しさと比べると SQL のパースなんてのは些細なものなのでしょう。

空のプロジェクトをつくった。次はとりあえず何か動くという状態にしたい。最小限の SQL として

• SELECT で複数のカラムを指定, AS による aliasing あり
• FROM で単一のテーブルを指定
• WHERE 以降はナシ

が動くようにする。WHERE に進むには式を評価する必要があるのであとまわし。AST は作る。実行計画やデータフローみたいのは不要。スキャンして row を生成し, それを rename し, 最終的な column を accumulate する、みたいなことをするだけだから。最初は aliasing ナシでもいいキハするけれど、式の評価とかをする上でそのレイヤは必要そうなのでいれてみる。すごい簡単だが、それでも AST など必要な足場のために多少の頑張りが必要。

あと一応 API を考えないといけない。まずはあまりカッコつけずべたっとしたものにしておく。

Impala は lexer と parser generator にそれぞれ JFLex と CUP を使っている。CUP は聞いたことがなかった。 Syntax が違う以外はだいたい Bison ぽい。ANTLR みたいに AST をつくってくれる機能もあるっぽいけれど Impala ではそれを使わず自力で書いている。

なお Presto や Hive は ANTLR を使う。Java はこの手のツールが妙に充実してるね。そして Presto の文法ファイルを Impala のファイルと比べると ANTLR の強力さがわかる。が、自分が使う PLY は記述力の低いツールなので Impala の CUP コードの方が参考になるのだった。

Impala の文法を眺めつつちょっとだけ PLY の文法を書いてみて思ったこと: (1) 自分は SQL を知らなすぎる。すくなくとも一冊くらい SQL の入門書を眺めないと自分の作ってる文法の正しさを少しも判断できない気がする。UNION とかしらねー。(2) Impala からコピペしているせいが大きいとは思うけれど、SQL の文法はサブセットにしておけばそんなにむずかしくない。古い言語だけあってコードを簡潔にしようみたいな頑張りを感じない。サブセットの AST までなら割と問題なくいけそうな予感。(3) Python+PLY でパーサを書くのはけっこうよい。Lex/Yacc のダメさも Python のおかげで若干やわらぐ。

実際にプロジェクトの stub を作り、作りを考えつつコードを書きはじめていい気がしてきた。

From Wikipedia.

GROUP BY は aggregation 操作の引数として表現する。そして aggregation は伝統的な relational algebra ではなく拡張されたもの、なのか。そして SELECT には式が書けるわけだが、それも伝統的なやつには入っておらず拡張。てか Projection とか Rename だけだとどうにもならいし、Join も微妙にしょぼい。Natural join が一番重要とかまじか。SQL を実装するなら SQL にあわせた Relational Algebra がいるね。というかそれがほとんど Volcano なわけだが・・・。

代数的な性質を使い式変形をすることで高速化できるということに目をつけて形式化した Codd さんはえらかったが、自分は最適化を実装する気はないのでもうちょっと雑な何かでよさそう。

Redbook でも推薦されていた Volcano の paper を読む。(実際にはいくつもあるシリーズの一つ。)

俺の考えた最強の SQL 実行エンジンフレームワークを作ったぜという話。実行計画の個々のノードをある種の高階関数として定義しカスタマイズによってノードの実装は数を絞る、同時に複数の入力ストリームから出力を一つつくるストリームとしてノードを抽象化し、そういうストリームをつなぎあわせて実行計画を作ろうな、という主張。Rx の話を読んでるみたいな気分。これが 1990 年とは、アカデミアなかなかやる。C 言語で書いてあるのにイテレータで遅延評価でストリームとか functional jargon が飛び交っている。こんなかっこいいもの作って 90 年代のハードウェアでまともに動いたのだろうか。そして謝辞に Jim Gray と Stonebraker が...

参考になったが、それ以上にかっこよさがやる気を起こす paper だった。

せっかくなので頭の中にあることを書き出しておく。良いプログラマの皆様はこの進め方に「そんなことやってるからダメなんだよ」と思うことも多いでしょうがそっとしといてください。大してコードを書けないおっさんが余暇プロジェクトをやるときに何を考えてるかというのは、役には立たないにせよ興味深い記録になるでしょう。

不安の一つだった parser generator は PLY でなんとかなりそうなのでよかった。言語処理系的な面倒は色々あるだろうけれど、そこはビギナーとして素直にがんばる。

まだコードを書き始められる気がしない。他にも no idea 事項が多すぎる。わからないこと:

• 全体のアーキテクチャ。一度は何か実物のコードを眺めたい気がする。OLAP 系のオープンソースのデータベースをなんか眺めたい。論文も読んだことだし Impala でいいのかな。分散しなくていいんだけど、いまさら C で書かれた昔ながらのデータベースを読むのはいやだ。
• AST から実行計画を作るところの見当がつかない。いま Volcano の論文を読んで実行計画のオブジェクトモデルみたいのが少しわかってきたが、それと SQL の関係がわかってない。コレはどうしたら良いのだろうなあ。いいかげん SQL の本を読むべきなのかもしれないが、それは先が長すぎるので Wikipedia とかで最低限の理解を得られないものか。
• それと関連し、SQL のパースの反対側、実際に DataFrame を enumerate してデータを extract するところ、実行計画というか実行そのものも、どういうデザインがよいかよくわからない。これは時間をとって考えないといけないが、その前にとりあえず関係代数の復習はしたい。
• などの疑問は教科書に書いてありそうなので、結果的に RDB の教科書を一冊手元に置いておくのがよい気もする。しかしどれもこれも厚くて高くてレビューが低いので気が乗らない。いっそ cow book を買い直せばいいのか・・・。
• 書捨てでない Python の書き方。これは blocking というほどではないけれど、いまいち Python でちゃんとしたコードがかける気がしない。不安をやわらげるべく、ジョギングのお供で Python の本を読むことにした。

書き出してわかるに、われながらまったく出来そうもないことに手を付けてる感。しかしここでくじけるリアル三日坊主なのでもうちょっとなんとか進めたい。やるべきこと:

• Volcano の論文を読み切る
• Impala の SQL の文法をパクリつつミニマルな SQL を PLY でパースしてみる。まずは書捨てで良い。
• Wikipedia か何かで関係代数について復習する
• Python 読書継続

やりたいが時間なさそう:

• Impala のコード全体を眺める
• RDB の教科書を物色する。関係代数とか SQL の評価について丁寧に扱っているもの。

Python 用の parser generator として PLY を試す。といっても簡単な四則演算を評価するだけのパーサをつくる hello world をコピペしつつ動かしただけ。

自分は Lex/Yacc を真面目に使ったことがなく、Hello World 以外では他人の助けを頼りに通りすがりで既存の g ファイルをいじったことがあるくらい。だからノウハウを何もわかっていない。若いうちに言語処理系を作っておくべきだったが仕方ない。トライアンドエラーでがんばるとしよう。 Lex / Yacc の本を読んだほうがいいのだろうか。乗り気になれないけれど。

その少ない経験にもづいて思うに、PLY は Python-Lex-Yacc というだけあってまるっきり Lex/Yacc だなあ。そういうコンセプトのライブラリなので仕方ないが、もうちょっとモダンな何かにはなれなかったのかと思ってしまう。bug tracker の会話を見ても「デザインが古いのは歴史があるからで仕方ないし直す気もないよ」と言っている。API がモダンになるだけでだいぶかっこよさそうなのに残念。この上のレイヤで誰かがんばってくれないものか。Lex/Yacc とか 40 年前のテクノロジじゃん。これが 40 年前にあったというのはすごいことだが・・・。

いいところもある。作者が主張するとおりエラーメッセージは丁寧でわかりやすい。そして Pure python な上にコード生成を実行時にやるため yacc/lex コマンドを走らせる必要がない。これは動的言語らしくてよい。あと古いとはいえきちんとメンテナンスされている安心感はある。

モダンな parser generator として ANTLR を使おうかとも一瞬考えたけれど、別コマンド実行の不便をふくめ Python との相性の良さが低めに見えたのでやめておいた。Combinator 系はどうか。なんとなく動的型で combinator は違う気がする。

まずは他の SQL 実装の文法ファイルを眺めつつ PLY で簡単な SQL を解釈してみようかなあ。SELECT 文 WHERE なし式なしみたいなやつ。

モダンな SQL つき OLAP 実装の輪郭を眺めるちょろい方法はないかと Impala の paper を読む。

AST から plan をつくって, そいつを色々 rewrite してから実行する。そういえばそんなものだった気がする。AST と plan が別なのは、AST にごてごて色々つけてく一般的なインタプリタと違う。VM のバイトコードといえばそうかもしらんが。そして MapReduce, Spark, Pandas などを通ってから見ると SQL の実行計画ってまったくもってデータフローだね。Hive みたいのを作りたくなる気持ちが今更わかった。

そのほか気になった点: 実行ノード間では tuple をやりとりする。columnar storage でも中間状態は tuple らしい。ただし将来的に materialize したい時は in memory columnar format にしたいと言っている。これは good news のような bad news のようなかんじ。そしてどういう時に materialize が必要なのか自分はわかってない。式の評価に LLVM をつかう。SparkSQL が bytecode generation でやっているところを LLVM でやる。どのくらいの粒度でコード生成してるのかね。書き方から判断するに tuple を渡して評価するくらいの規模に見えるけれど。まあ toyql は interpreter でよい気がする。

更に雑多なメモ: 標準フォーマットは Parquet. Parquet は Twitter と Cloudera の共同開発だったのか。nested/repeated はこの論文の時点ではサポートしていない。Parquet の意味なくね? そういえば Dremel paper は nested/repeated の話で半分くらい紙面を使っていた気がする。Impala paper はそれがないおかげでシステムの全体像にページが割かれており自分の目的には都合がよあかったとも言える。

システムとしては、実行計画をつくる coordinator と評価をする executor という分け方をする。MapReduce とかと同じ。インプロセスでもこういう切り口にするのがいいのかね。わからん。

ちょろく輪郭を冷やかすという目的には良い paper だった。

SQL の使えるデータベースでも書いてみるかなと思い立つ。そんな簡単なものではないはずだから完成の見込みは薄いけれど、できることがわかっているものを書いても面白くないからね。せっかくなので、今回は作業および調査の記録をここに書き残してみたい。でも挫折したら一連の投稿は公開せずに捨てると思う。かっこわるいから。

データベーステクノロジにはなんとなく憧れがあったけれど、仕事で縁がないせいかまったく詳しくない。趣味で自作するにしても B-tree から組み上げると気が遠くなりそう。 そして SQL は好きになれなかったし一方で NoSQL も面白くない。そんな状態のまま10年くらいが過ぎた。

けれどこのごろ仕事で BigQuery をさわったおかげでちょっとだけ SQL と縁が出てきた。そして OLTP でなく OLAP 寄りのデータベースなら B-tree からはじめなくてもよさそう。実装すれば SQL への理解も深まって良いかもしれない。なんて安直な動機がはじまり。

どんなものを実装すると楽しいかを考える。できれば新しい言語が使いたい。Rust や Scala が使えれば満足度が高そうだけれど、あまりに使いみちがなさそうで盛り上がらない。でもそれを Pandas あたりに繋げば使い道があるかもなあと考えた後、いっそ Pandas の DataFarme 相手に Python で SQL を実装するのはどうかと思い至った。DataFrame はほぼデータベースのテーブル(しかも column oriented) だし、データのロードとかはぜんぶ Pandas に任せられる。SQL を実装するところだけやればよい...気がする。Python は新しい言語とは言えないけれど、書捨てより真面目に使えるようになっていいとは思っていた。Java や C++ よりはやる気になる。

世の中には pandasql  という似たようなことをするライブラリがある。これはデータを sqlite にインポートして SQL を解釈させる。何も面白くない。そもそも現状の自分の SQL レベルを踏まえると競合や実用性を考えても仕方ない。気にしなくてよかろう。

遅そうではある。ま、仕方ないね。速さが気になるところまでいったら上出来。 C++ につなぐとか色々できることはあるでしょう。

名前。実用性を重んじず SQL を理解するのが主目的、ということを強調すべく toyql と呼ぶ。

自分のデータベースや SQL への理解度。ほぼ素人。むかし cow book を読んで感動した記憶があるものの、しょうじき中身は覚えてない。RDB エンドユーザ体験は通りすがりで何度かさわったくらい。大半は ORM 越し。最近ちょと BigQuery を書いているけれど、難しいことはしてない。真面目にスキーマを決めたことはない。正規化とか怪しい。たぶんできない。改めて書き出してみるとほんと素人だな・・・。

どこからはじめよう？今のところまったく何の見当もつかない。最初はデータベースの教科書を読みなおそうと思ったが、すごく時間がかかりそうな上にいまいちピンとくる教科書が見当たらない。じゃあ SQL の仕様書はどうかとおもって探すも 1000 ページくらいある。自分の現状だと歯が立たなそう。

PostgreSQL のマニュアルをみたら、それなりに詳しく SQL が載っていた。これを読むべきか？でも OLAP を作るのに OLTP を調べるのは何か違う気がする。手元に置いておくくらいにしよう。

まずはなにかデータベースのコードでも読もうか。あとは Python を少し勉強しなおし、NumPy と Pandas も少し調べて、Python 用の parser generator を探して試して・・・

コード書く前の準備がけっこうある。できれば一ヶ月くらい調査したらコードを書き始めたい。明らかに勉強する必要のあることが目の前にあるのは気が滅入るような元気がでるような。ガッと書き始められないところに力の無さを感じる。まあ事実なので仕方ない。

不安要素。なにより時間のなさ。そして時間がないことからくるやる気の低落。それにプログラミング力。他の優先事項もある。毎日読むなり書くなり何かはして、やる気を途切れさせないようにしたい。できればね。