Calcite の Adapter を書いている中で、それぞれのRelNode(Scan/Filter/Aggregation …) の結果(タプル)の生成と、それに使用されるメモリ量が気になっていた。

別の件で調べていた時にこの Paper を見つけ、Pocket に入れっぱなしにしていたので読んでみた。日本語の論文なので読むのが楽で良い。

• 分析用データ処理系における効率的なデータ配送機構

問題領域と読んだ理由

この Paper で扱われている問題領域は、分析データ処理時に発生する「メモリ枯渇」と「タプル複製のコスト」の2点。

「タプル複製のコスト」に関しては Filter を実装する時に色々と調べた。その結果、Filter の結果をタプルとして生成するのではなく、Filter されたレコードのID をベクターとして保持する方式を見つけ、実装でもそれを採用している。

Aggregation は入力と出力でタプルの形が異なるので、Aggregation の計算処理が終わった時点で結果をタプルとして生成している。Aggregation の結果セットが大きいと大量のタプルが生成されるので、Filter のように上手いやり方が無いか知りたい。

Solution

メモリ枯渇に関する対応は、演算子ごとに使用するメモリ量を見積って出力量を制限する、というもの。1つの演算子の処理を複数のイテレーションに分割することができれば、ストレージに Spill するよりも良いのかも。(1つの演算子を複数のイテレーションに分ける、という話はこの Paper には載ってません。念の為)

「タプル複製のコスト」も説明されているが、子演算子が親演算子にタプルを渡す際に、それぞれに対して複製せずに同じデータを参照しろ、参照カウンタを使え、というごもっともな意見が記載されているので割愛。

Conclusion

メモリ枯渇に関しては、演算処理を分割して出力するタプルの量を制限する、というのは一つの方法だと思った。ただ、Scan や Filter は処理してすぐに出力できるのに対して、Aggregation は 集約単位毎の計算が終わるまで計算中の状態を保持しておく必要がある。その為、仮に演算処理をイテレーションに分割したとしても、次の処理に出力するまでに時間がかかるので、別の対応が必要になる。

Aggregation に限って言えば、入力データが予め集約単位で纏まっていており、その単位で処理できればメモリの使用効率は良くなるはずだが、その纏めるコストもあるのでどちらが良いか。このあたりも調べてみたい。