論文メモ: Mison: A Fast JSON Parser for Data Analytics

2019-02-16

論文メモ

L. Yinan, N. R. Katsipoulakis, B. Chandramouli, J. Goldstein, D. Kossmann. “Mison: A Fast JSON Parser for Data Analytics,” Proceedings of the VLDB Endowment, Volume 10 Issue 10, June 2017, p1118-1129. を読んだメモ。本当にただのメモなので内容を知りたければ論文を読むように。

Apache Spark や Apache Drill などいわゆるビッグデータを処理するソフトウェアでJSONをパースするのに無視できないコストが掛かる。特に、JSONにクエリを投げるのに一旦パースしてからクエリを処理するのにはかなり無駄が多い。Parquetなどのフォーマットもあるが、MisonはJSONのまま処理を高速化した。事前変換が必要ないので手軽に利用できる。

面白いのがパースの技法。岐の塊である有限状態機械(FSM)を使ったパースではなく、構造インデックスを目的とすることでSIMDによる処理を可能にした。

JSONの構造に興味があるので着目するのは {, }, : など。: を見つければ直前がキーだし、 { や } を見つければネスト関係が分かる。なので : の位置をビットマップで保持すると簡単にキーが見つかる。さらに、クエリに応じてネストレベルが決まるのでネストレベル毎に情報を持つと手っ取り早い。

例えば以下のようにJSONにインデックス付けされる。

JSON {"id":"id:\"a\"","reviews":50,"attributes":{"breakfast":false,"lunch":true,"dinner":true,"latenight":true},"categories":["Restaurant","Bars"],"state":"WA","city":"seattle"}
Lv1  0000010000000000000000000010000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000010000000000010000000000
Lv2  0000000000000000000000000000000000000000000000000000000100000000000001000000000000010000000000000000100000000000000000000000000000000000000000000000000000000000000000000000

これがあれば簡単にクエリを処理できることが分かると思う。

このインデックスは現実的にはワード単位で処理し、さらにリトルエンディアンでひっくり返ったりするがだいたいこのまま。

さて、ここで問題になるのがクォート。" や \ を意識しながらパースしないといけない。しかしこれもbitmapに落とし込める。{, }, : に加えて " と \ のbitmapも作る。例えば上記JSONの最初の256bitだとこう。

JSON {"id":"id:\"a\"","reviews":50,"a
`\`  00000000001001000000000000000000
`"`  01001010000100110100000001000010
`:`  00000100010000000000000000100000
`{`  10000000000000000000000000000000
`}`  00000000000000000000000000000000

構造を見ずにデータだけを見てるので簡単にSIMDで処理できることが見て取れる。

\ のbitmapを1シフトして自身とANDを取るなどすればエスケープされてない \ の位置が取れる。エスケープされていない \ を1シフトしたものとクォートでANDを取ればエスケープされたクォートが取れる。それ以外が構造的クォートだ。

この処理をすると以下のように構造的クォートだけが得られる。

JSON {"id":"id:\"a\"","reviews":50,"a
S-"  01001010000000010100000001000010

ここから文字列部分を表すマスクを作る。詳しいアルゴリズムは論文を読んでくれ。

JSON {"id":"id:\"a\"","reviews":50,"a
mask 00111001111111110011111111000001

ワード単位で処理しているので前のワードで文字列中に入っていたらこのマスクをflipしないといけない。このマスクから構造的 : や { , } の位置が分かる。あとは多少のアルゴリズムでレベル別の : のインデックスが作れる。詳細は論文を読んでくれ。

さらにはクエリに応じた投機的パースなんかもやってるらしい。

クエリ処理用なので、プロトコルでやり取りするようなJSONのパースに向いているかは知らないが、エスケープ文字の処理の扱いが面白かった。