なぜSQLiteはバイトコードを使うのか

以前にデータベースを自作しようとして、SQLiteのアーキテクチャを見てみたらVMだったことに疑問を感じ、それをツイートしたところ作者からリプをもらいました。

https://x.com/DRichardHipp/status/1784720563090465208

作者いわく、次のような背景があったとのことでした。

• SQLiteを作った当初はデータベースエンジンのことをよく知らないがコンパイラのことをよく知っていた
• SQLデータベース・エンジンを書くという問題をコンパイラ構築の問題として扱うのは自然なことだった

データベースエンジンのコアの部分をVMにするという発想がまったくなかったので、どんなメリットがあるのか？と気になっていました。
それを作者に聞いたら、詳細な説明ページを作ってくれました。

個人的にVMにしたことで、評価&実行のパフォーマンスは多少良くなると思うが、データベースエンジンのパフォーマンスにそれほど寄与していないんじゃないかな？って思ったりしました。

https://x.com/DRichardHipp/status/1785037995101290772

本記事はそのページについて自分の備忘録として理解した内容を残します。

結論

SQLiteはOLTPに主な焦点をおいていて、OLTPの観点からVM（バイトコード）が適切という話のようです。
Why SQLite Uses Bytecodeには次のように説明されています。

3.2. Dataflow Programs Are Easy To Parallelize
In a dataflow program, each processing node can be assigned to a different thread. There needs to be some kind of threadsafe queuing mechanism for transferring intermediate results from one node to the next. But no synchronization primitives are typically needed within each node of the program. Node schedule is trivial: A node becomes eligible to run when it has data available and there is space in its output queue.

This is an important consideration for database engines that are designed to run large analytic queries (OLAP) on large multi-core servers. The primary focus of SQLite is transaction processing (OLTP) on the internet-of-things, so there is less need to represent prepared statements as dataflow programs in SQLite.

データフロー・プログラムでは、各処理ノードを異なるスレッドに割り当てることができる。あるノードから次のノードへ中間結果を転送するために、ある種のスレッドセーフな待ち行列メカニズムが必要である。しかし、通常、プログラムの各ノード内では同期プリミティブは必要ない。ノードのスケジュールは簡単である：ノードは、利用可能なデータがあり、その出力キューに空きがあるときに実行可能になる。

これは、大規模なマルチコア・サーバー上で大規模な分析クエリー（OLAP）を実行するように設計されたデータベース・エンジンにとって重要な考慮事項である。SQLiteの主な焦点はモノのインターネット上でのトランザクション処理（OLTP）であるため、SQLiteではプリペアドステートメントをデータフロープログラムとして表現する必要性はあまりありません。

要は次のことかなと理解しています。

• OLAPは膨大なデータを統計処理して「有意義なデータを抽出する」ことが目的なので、並行処理でスケールできることが大事
• OLTPはトランザクション処理を通じて「確実にデータを保存できる」ことが目的なので、スケールできるメカニズムはそれほど大事ではない

具体的にバイトコードは次のメリットがあるとのことです。

• バイトコードはシンプルでわかりやすい
  • MySQLやPostgreSQLはSQLをASTに変換して、ASTから実行に適したデータ構造（オブジェクトツリー）に変換している
  • オブジェクトツリーを人間が読める形で公開するのが難しい
• バイトコードはデバッグがしやすい
  • SQLの解析と実行に分かれるが、問題がおきた場合バイトコードを調べることで解析時または実行時のどちらの問題かを速く切り分けられる
• バイトコードは段階的に実行できる
  • オブジェクトツリーはそれが難しい
  • オブジェクトツリーを走査して実行するが、途中で止めるということはスタックの復元が必要になる
• バイトコードは小さくて速い
• バイトコードは一度生成されると固定される
  • これをキャッシュしておくことでSQLのコンパイルが不要になる
• OP_ColumnやOP_CreateBTreeなどDBに特化した命令がある

OLTPを実現するうえでこれらのメリットがあることで処理・メンテがしやすい、ということかなと思っていて、確かに理にかなっているなと思いました。

さいごに

SQLiteがVMだったことに驚いたけど、詳細を知って勉強になりました。
そのうちSQLiteをRustで再実装して完全理解したいと思います。