@azyobuzinの技術ブログ

Making an Embedded DBMS JIT-friendly について。

原本は例によって CodiMD にあります: https://hackmd.azyobuzi.net/s/Hk7lBbN14

どんなもの?

SQLite の一部を Python(PyPy) に移植したから「SQPyte」!!

  • SQLite の一部を RPython に移植し、プログラミング言語と SQLite(Cライブラリ)の境界を取っ払った。
    • 通常 C ライブラリの関数を呼び出すと、その呼び出し部分をインライン化することができないので、ここを RPython に移植することで、 JIT コンパイラによってインライン化され、高速化する。
  • RPython の Meta-tracing JIT を使って、 SQLite の命令インタプリタを JIT コンパイルした。
    • SQLite は SQL を独自の内部表現である命令列に変換する。
    • その命令列の実行は、命令を取り出して、命令の種類(opcode)で分岐して、命令を実行する、というループになっており、データベースの読み出しではこのループがものすごい回数行われることになる。
    • Meta-tracing JIT で命令列自体をコンパイルすることで、このタイトなループを最も効率的な方法で実行できるようになった。

※ JIT(Just In Time) コンパイル … プログラムの実行時にコンパイルを行う。(例: Java は実行時に Java の中間表現から機械語へコンパイルする。このようにすることで、実行環境に最適な機械語を出力することができる。)

※ Tracing JIT … コンパイル処理には時間がかかるので、コンパイルを行うのは、プログラムの中でも特に重い部分だけにしたいもの。プログラムの実行中に特に時間を食う場所というのは大体タイトなループなので、実行環境がタイトなループを実行していることに気づいたときに、そこを重点的にコンパイルすることで、無駄なく最適化を行うことができる。

※ Meta-tracing JIT … プログラミング言語で他のプログラミング言語のインタプリタを書くと、命令を取り出して、命令の種類で分岐して、命令を実行する、というループになるので、これがタイトなループになるが、さらに、そのインタプリタで実行している別のプログラミング言語でタイトなループが書かれている場合がある。インタプリタを書くときに、実行環境にここはインタプリタだぞ!と伝えると、インタプリタで実行中のプログラムに対して JIT コンパイルを行ってくれるのが Meta-tracing JIT。

目的 / 技術的な重要なポイント

組み込みデータベースは、プログラムと同じプロセスで動いているのに、データベースはデータベースといった感じに分離されている。ここにはまだ高速化の余地があるのではないか?という研究。

Hypothesis 1 Optimisations that cross the barrier between a programming language and embedded DBMS significantly reduce the execution time of queries.

プログラミング言語とデータベース部分のプログラムがライブラリとして明確に分かれてしまっている(インライン化できない)ことで、遅くなっているのではないか。この境界をいい感じに最適化する(できるだけなくす)ことで、クエリの実行時間を短くできるのではないのか。

  1. クエリの実行結果を 1 行ずつ取り出すループは、データベースに 1 件くれと問い合わせて、プログラミング言語に戻ってきて処理をし、また次の 1 件をくれと問い合わせる……のループである。
  2. SQLite では、クエリ内で使える関数を自分で定義することもできるが、これはクエリ実行中にプログラミング言語側に処理が戻ってくるということになる。

この実験では、境界を手作業で取っ払い(RPython に移植する)、 PyPy の JIT によってインライン化を行う。

Hypothesis 2 Replacing the query execution engine of a DBMS with a JIT reduces execution time of standalone SQL queries.

クエリを JIT コンパイルすれば実行時間を短くできるのではないか。これには Meta-tracing JIT を使う。

Hypothesis 3 Exposing the type information in the flags attribute associated with registers allows the JIT compiler to speed up query execution.

3つ目は、 JIT コンパイルの特性を使ったおまけ調査。

SQLite は、スキーマでデータの型を厳格に指定する必要がないデータベースである。そのため、格納されているデータには、データの型を表す flags という属性がついている。しかし、多くの場合、1つの列に入っているデータの型は同じである。元々の SQLite では、データを扱う処理を行う前に flags を確認する処理(これはメモリーの読み取りが発生するので比較的遅い処理)が入るが、本論文では、これをできるだけ命令の戻り値に含めるようにした。このことによってメモリー読み取りの回数を減らし、さらに同じ型なことが多いことから、型による分岐部分が JIT コンパイラによって、削除され(例外時のためにガードは挿入される)、効率的なクエリの実行ができるはずだと考えられた。

結果

Hypothesis 1 は、すべてのテストケースで SQLite より高速だった。このことから、プログラミング言語とデータベースライブラリの呼び出し間のインライン化は効果的だということがわかった。

Hypothesis 2 は、時間のかかるクエリなら有効。すぐに終わるクエリだと遅くなることもある。

Hypothesis 3 は、あまり効果がなかった。

先行研究との比較

  • SQL を JIT コンパイルする例はいろいろある。 JVM にやらせたり、 LLVM にやらせたり、 C にコンパイルしてみたり。
  • プログラミング言語と融合ということで、プログラミング言語から SQL へ変換しようという取り組みがあった。
    • Ferry
    • Ferry インスパイアがいくつか
  • PyPy で動く組み込みデータベースを作成した例もある、 SQPyte より高速だが、フルスクラッチで作ったものなので、苦労が大きい。 SQPyte はできる限り SQLite を流用した。

課題

  • SQLite 内部のデータ構造をもっと RPython に移植すれば、もっと速くできそう。
    • (それはそうでしょ。疲れるけれど。)
    • (いや、 PyPy の JIT コンパイラより C コンパイラの方が頭いいこともあるかもしれないしな……)

このログへのコメント

コメントはありません