SQLiteがBytecodeを使う理由

 (sqlite.org)
7 ポイント 投稿者 GN⁺ 2024-05-01 | 1件のコメント | WhatsAppで共有

SQLデータベースエンジンの一般的な動作方式

  • すべてのSQLデータベースエンジンは似たような方式で動作する
    • 入力されたSQL文を「Prepared Statement」に変換する
    • Prepared Statementを「実行」して結果を生成する
  • SQLiteでは、Prepared Statementはsqlite3_stmtオブジェクトのインスタンスとして表現される
  • Prepared Statementを表現する方法は大きく2つある
    • バイトコード方式: SQLiteで使用
    • オブジェクトツリー方式: MySQL、PostgreSQLで使用

バイトコード方式の利点

  • 理解しやすい
    • 単純な命令の列で構成されており、容易に出力できる
    • EXPLAINキーワードを使うとSQL文のバイトコードを確認できる
  • デバッグしやすい
    • パース/解析段階と実行段階を明確に区別できる
    • デバッグビルドではPRAGMA vdbe_trace=ONコマンドでバイトコード実行の追跡が可能
  • インクリメンタルに実行できる
    • バイトコードで記述されたSQL文は1行ずつ実行し、停止してから再開できる
    • オブジェクトツリー方式はツリー全体を一度に実行するため、インクリメンタル実行が難しい
  • メモリ使用量が少ない
    • バイトコードはASTよりサイズが小さい
    • Prepared Statementは長期間メモリにキャッシュされるため、メモリ使用量が重要
  • 実行速度が速い
    • 各段階で判断すべき事項が少なく、実行が速い

オブジェクトツリー方式の利点

  • ランタイムにクエリ計画を変更できる
    • オブジェクトツリーは実行中でも修正しやすい
    • クエリの進行状況に応じて動的に最適化できる
  • 並列化しやすい
    • 各処理ノードを別個のスレッドに割り当てられる
    • ノード間のデータ受け渡しだけを同期すればよい
    • 大規模な分析クエリ（OLAP）をマルチコアで実行する際に有利

GN⁺の見解

  • SQLiteの主要な目標はモノのインターネット環境におけるトランザクション処理（OLTP）であるため、バイトコード方式は適しているように見える。シンプルで軽量でありながら高速な性能を提供できるためだ。
  • 一方でMySQLやPostgreSQLは大規模データ分析にも多く使われるため、クエリ実行計画を動的に最適化し、並列化できるオブジェクトツリー方式の利点がより際立つ可能性がある。
  • ただし、オブジェクトツリー方式にもデバッグや性能分析が難しいという欠点がある。また、ツリー走査コストなどにより、単純なクエリではかえってバイトコードより遅くなる可能性もある。
  • 重要なのは、用途と目的に合った適切な方式を選ぶこと。汎用RDBMSでは、両方式の長所と短所を折衷したハイブリッド方式の採用も検討に値する。

関連記事

1件のコメント

 
GN⁺ 2024-05-01
Hacker Newsのコメント

  • SQLiteがSQLクエリの実行に抽象構文木（AST）ではなくバイトコード仮想マシン（VM）を使っているのは、データベースとして興味深い設計上の選択である。バイトコードがASTより優れている点は次のとおり。

    • コンパクトさ: バイトコードは部分式ごとの隠れたmalloc／オブジェクトヘッダーやポインタを必要としないため、ASTよりもコンパクトである。
    • 性能: キャッシュ効率が高く、ポインタ追跡によるキャッシュミスが少ないため、バイトコード実行のほうが高速である。
    • 増分実行: 明示的なスタックを使うことで、ネイティブスタックを巻き戻すことなく実行を一時停止・再開しやすい。

  • バイトコードVMやインタープリタはしばしば汎用プログラミング言語と結び付けて語られるが、次のような別の文脈でも驚くほど有用である。

    • eBPF: Linuxカーネルの拡張メカニズム。
    • DWARF式言語: GDBやLLDBのようなデバッガで使われている。
    • RARファイル形式: ユーザー定義のデータ変換のためのバイトコードエンコーディングを含んでいる。

  • Microsoft SQL Serverは内部的にはオブジェクトツリーを使っているが、クエリプランの出力は依然としてテーブル形式であり、オブジェクトツリーをテーブルとしてレンダリングすることの難しさを示している。

  • プログラマはしばしば、どのインデックス参照をループ内で行うべきかを正確に把握しているため、場合によってはSQLではなくバイトコードを直接書いたり、高水準の命令型言語を使ったりするほうが有利なことがある。これをSQLで表現するのは負担になり得る。

  • ボトルネックがバイトコード実行ではない場合（たとえばメモリやディスク速度）、JITコンパイルでネイティブコードに変換することは必ずしも必要ではないかもしれない。

  • Python、Ruby、Luaなど多くのプログラミング言語は、内部的にバイトコードまたはASTを使っている。データベースの設計判断によっては、エラーを起こしやすいサードパーティライブラリやORM実装に対して、容易に解析できる命令文が有用な場合がある。