PostgreSQL向けの新しいJITコンパイラを開発

 (pinaraf.info)
4 ポイント 投稿者 GN⁺ 2024-03-20 | 1件のコメント | WhatsAppで共有
  • 実験的なJITエンジン pg-copyjit は、LLVMより低い生成コストで、短いPostgreSQLクエリにも「十分に高速」なコードを作ることに重点を置いている
  • PostgreSQLの cost推定値 は実際の実行時間と直接対応しておらず、最適化コストの大きいLLVM JITは短いクエリではかえって損になる場合がある
  • copy-and-patch方式は、Cで作った ステンシル（stencil） を事前にコンパイルしておき、実行時に必要な断片をコピー・パッチして新しい関数のように実行する
  • pg-copyjitはPostgreSQL JIT providerインターフェースを通じて接続され、未実装のopcodeに遭遇すると PostgreSQLインタプリタ に自動でフォールバックする
  • 現在はPostgreSQL 16とAMD64で動作する 概念実証 段階で、コード生成は数百マイクロ秒程度だが、ビルド・ドキュメント化・サポートはまだ整っていない

pg-copyjitが狙う領域

  • pg-copyjit はPostgreSQLサーバーを高速化するための実験的なJITエンジンである
  • 現在のコードは、本番サーバーよりも 熟練のハッカー が試してみるのに近い水準である
  • 期待されているフィードバックは、興味深い実験結果、性能向上の事例、実装アイデアであり、業務の中核アプリケーションのダウンタイムを覚悟する段階ではない

PostgreSQLでLLVM JITが重荷になる理由

  • PostgreSQLにはすでにAndres Freundが導入した LLVMベースのJITコンパイラ がある
  • LLVMは効率的なコードを生成できるが、PostgreSQLでの使い方ではJITコンパイルと最適化のコストが大きい
  • オプティマイザを使わないとコンパイルしない場合より悪くなることがあり、オプティマイザを使うとコストがさらに大きくなり得る
  • JITを適用するかどうかの判断には、一般的な query cost estimation が使われる
    • PostgreSQLのcostはクエリ同士を比較するための値であり、実際の実行時間を意味するものではない
    • cost 100のクエリが1秒かかることもあれば、cost 1000のクエリが100msで終わることもある
  • クエリが10ms速くなっても、最適化に50msかかるなら全体の実行時間としては損になる
  • LLVM JITをより有用にする方法として、コンパイル済みクエリを キャッシュして再利用 する案があるが、実装は小さな作業ではない

copy-and-patch方式の構造

  • copy-and-patchは2021年に論文で紹介されたJITコンパイラの構成方式で、Python 3.13のJITエンジンにも使われている
  • 中心となる単位はCで書かれた ステンシル である
    • ステンシルは穴のある関数である
    • clangで事前にコンパイルされる
    • gcc対応はまだ保留中である
  • コンパイル時には必要なステンシルをつなぎ合わせ、穴を埋めたうえで、新しく作った「コンパイル済み」関数へジャンプする
  • 基本的な流れは単純である
    • 新しいメモリ領域にステンシルをコピーする
    • 必要な値をパッチする
    • 結果のコードを実行する
  • 追加の最適化余地もある
    • コンパイル時に計算可能な値を事前に計算する
    • ループを複数のステンシルに分割してunrollする
    • 複数のステンシルをまとめて一度に最適化する meta-stencil を作れる

PostgreSQLへ組み込む方法

  • PostgreSQLのJITは拡張可能な provider構造 を持つ
  • .so は _PG_jit_provider_init 関数を1つ提供し、この関数で3つのコールバックを初期化する
    • compile_expr
    • release_context
    • reset_after_error
  • 中心となるコールバックは compile_expr である
    • 入力はopcodeで構成された式ポインタ ExprState* である
    • opcodeを望む方法でコンパイルする
    • 生成したコードを実行可能としてマークする
    • evalfuncをPostgreSQLインタプリタの代わりに生成コードへ差し替える
  • 実装していないopcodeに遭遇すると、PostgreSQLインタプリタへ 自動フォールバック できる

pg-copyjitのコンパイル手順

  • pg-copyjitのcopy-and-patchアルゴリズムは、現時点ではいくつかの小さな最適化だけを含む単純な形である
  • 各opcodeについて、コンパイラは ステンシルコレクション を確認する
    • opcodeに対応するステンシルがあれば、生成中のコードに追加する
    • ステンシルがなければコンパイルを中断し、PostgreSQLインタプリタが実行を担当する
    • ステンシルを追加した後、各穴を必要な値でパッチする
  • CONST opcodeのステンシルは op を外部 ExprEvalStep として宣言し、コンパイル済みの .o ファイル内には op アドレス用の穴を残す
  • ステンシルコレクションはこのrelocation情報を保持し、JITコンパイラが現在のopcode構造体のアドレスを入れて実行可能なコードを作る
  • ビルドはまずステンシルを1つの .o ファイルにし、そこからアセンブリコードとrelocationを抽出して、Cで使える構造体へ変換する流れである

実装状況と性能

  • 初期にはアセンブリコードを手動で抽出し、SELECT 42; に必要な3つのopcodeを動作させた
  • その後、アセンブリコード抽出を自動化するDirtyPythonスクリプトを書き、数時間以内に次の機能を追加した
    • 関数呼び出し
    • 単一テーブルクエリ
    • より複雑なデータ型
    • いくつかの最適化
  • 現在確認されている状態は次のとおり
    • PostgreSQL 16で動作する
    • 以前のリリースでも問題ないと予想しているが、確認済みの環境はPostgreSQL 16である
    • 対応アーキテクチャは AMD64 のみである
    • ARM64対応を追加する計画がある
    • POWER64やS390xのようなターゲットにも関心はあるが、コンパイラのパッチと該当マシンへのアクセスが必要になる可能性がある
  • 性能値は、まだほとんど最適化していない状態での結果である
    • コード生成は 数百マイクロ秒 以内に終わる
    • 短いクエリでも使える水準である
    • SELECT 42; 基準では、no JITは0.3ms、copyjitは0.6ms、最適化なしLLVMは1.6ms、最適化LLVMは6.6msかかる
  • LLVMは非常に高速なコードを作れるが、pg-copyjitの目的は素早く 十分に高速なコード を作ることなので、2つのツールを直接比較するのは難しい
  • シンプルな非インデックスの90k rowsテーブルで2つのクエリをベンチマークしており、CPU処理のある where 句が入るとインタプリタ比で性能が良くなる
  • ベンチマークはノートPCで実施されたため信頼性は限定的で、今後デスクトップでより適切なベンチマークを行う予定である
  • 実装済みopcodeがまだ少なくても、どんなクエリでも実行できる
    • JITエンジンは未実装部分についてメッセージを出す
    • 実際の実行はインタプリタが担当する

コード公開と残作業

  • コードはGitHubの pg-copyjit で公開されている
  • 現在はgit historyの整理やドキュメント化よりも、コード自体に集中している状態である
  • ビルドするには、まず build-stencils.sh ファイルを手動で実行する必要がある
  • 現在の状態ではサポートを提供できないため、ドキュメント化もまだ行っていない
  • 残作業は比較的明確である
    • より多くのopcodeの実装
    • 最適化の探索
    • ビルドの利便性改善
    • パッケージ化可能な状態への整理
  • ビルドスクリプトは現時点では Debian と PostgreSQL 16 に特化している

想定用途とアーキテクチャ拡張

  • 目標は、安全にパッケージ化して自分の本番サーバーへデプロイできる水準に到達することである
  • サーバーごとにJITを使い分ける構想もある
    • GISサーバーのように、クエリが最適化コストを負担する価値のある場所ではLLVM JITを使う
    • 短いクエリ時間が重要なWebアプリケーションのデータベースではpg-copyjitを使う
  • 他のアーキテクチャへの移植も真剣な目標である
  • Alpha、Itanium、Sparc、M68kのようなさまざまなアーキテクチャの時代を懐かしみ、単一アーキテクチャ中心の monoculture 問題には加わりたくないという立場である

関連記事

1件のコメント

 
GN⁺ 2024-03-20
Hacker Newsのコメント
  • LLVM JITコンパイラをより使いやすくする方法であるコンパイル済みクエリのキャッシュと再利用は、実は数年前からLLVMに実装されている :) https://github.com/llvm/llvm-project/commit/a98546ebcd2a692e...
    • その通りで、もっと明確に言うべきだったが、問題はLLVMではなくPostgreSQL側にある。
      JITコンパイラがメモリアドレスを直接埋め込む必要があるため、生成されたコードはそのクエリとプロセスに縛られてしまう
    • PGは接続ごとに1プロセスを使い、LLVM JITコードはプロセスごとに固定されるため、DBのすべての接続でコードを共有できない。
      実行計画も、異なるプロセス間で共有するよう設計されたメモリ構造ではないため、同じ問題を抱えている。
      MSSQLのようなDBはスレッドを使う単一プロセス構成なのでこの問題がなく、外部プーラなしでもより多くの同時接続を扱える理由の1つでもある。
      MSSQLは実行計画をプロセスに縛られない表現にシリアライズしてDBに保存することもでき、実行計画固定のような機能に活用できる
  • 投稿者です。Hacker Newsに投稿してくれてありがとう。質問があればできる限り答えます
    • Cを対象とするcopy-and-patchと、コンパイラが中間表現を対象にするときに行うことの間に、根本的な違いがあるのか気になる。
      従来のコンパイル方式も、Cではない別の中間言語を使う「copy-and-patch」のように見える
    • Postgresの性能向上を見るのはいつもうれしい。実際のクエリでLLVMにかかる時間がどれくらいか、LLVMの設定がどうなっているのか気になる。
      たとえば、どのパスやどのバックエンド最適化を使っているのかといった点だ。
      私たちの経験では [1]、最適化を無効にして -O0 バックエンドパイプラインでコンパイル時間に合わせて調整するとLLVMもかなり高速化できるが、それでも他のアプローチより10〜20倍遅い。
      また、copy-and-patchで生成したコードは実行速度がかなり遅く、最適化もしにくいという経験がある。いくつか試したが [2; Sec. 5]、まだ差は大きい。データベース評価結果は Fig. 3 を参照。
      LLVMと比べた実行時間低下の数値があるのか、また、素早くコンパイルしたコードからLLVM最適化コードへ動的に切り替える多段JITを実装する計画があるのかも気になる。
      [1]: https://home.in.tum.de/~engelke/pubs/2403-cgo.pdf
      [2]: https://home.in.tum.de/~engelke/pubs/2403-cc.pdf
    • copy-and-patchは本当に新しいアイデアなのか、それとも古いアイデアに新しい名前を付けただけなのか気になる。
      2010年ごろにプログラミング、特にインタプリタを学んでいたとき、注意して使えばコンパイラが作った実行コード片を memcpy できるというのはよく知られた話だと思っていた。
      当時の大きな落とし穴は、NXビットがちょうど普及し始めていたことだった。Linuxでも大半はいまだに32ビット配布が当たり前で、CPUが64ビット対応だと知って驚く人もいた。
      後には、64ビットコードをまったくサポートしないネットブックを使っていたこともある。
      残念ながら残りのコードに時間を使いすぎて、これを十分掘り下げて実用になるものを作ることはできなかった
    • 6月のpgconf.euで扱うにはとても良いテーマになりそう。pgconはVancouverに移った。
      残念ながら発表提案の募集は終わっているが、「unconference」枠はある。ただしテーマは現地で決まるので保証はない
  • PostgreSQLにまだクエリ/実行計画キャッシュがないのはいまだに驚きだ。
    キャッシュができれば頻繁に実行されるクエリはキャッシュされ、より積極的に最適化されて、コンパイルコストを相殺する形で両アプローチがうまく噛み合いそうに見える。
    もちろん、それ自体がまったく新しい複雑さと頭痛の種を追加することにもなる
    • PGにも実行計画キャッシュの一形態はある。プリペアドステートメントで、実際のパラメータ値が実行計画に大きく影響しないと判断されると、PGは「generic plan」を使い、同じプリペアドステートメントのすべての実行に同じ実行計画を再利用する。
      https://www.postgresql.org/docs/current/sql-prepare.html の「notes」を参照
    • 私も最初は同じ考えだったが、実際にこれを作ってみると本当に難しいだろうと分かった。
      かなり単純化して言えば、実行エンジンのあちこちにクエリの一部を指すポインタが漏れ出している。
      これを取り除くには、実行エンジン、プランナ、そしてそれ以外の部分まで含めたかなり大規模な全面改修が必要になる。
      単一セッション内であっても、2つのコンパイル済みクエリはこのために互いに異なるコンパイルコードを持つことになる。LLVMも私のcopyjitも、複数の構造体のアドレスをアセンブリコードに埋め込む必要がある
    • Oracleの実行計画キャッシュは、オプティマイザがプリペアドステートメントのパラメータをのぞき見できない場合、過去にはかなり厄介だった。
      通常は自分で入ってヒントを追加したり、実行計画を強制したりする必要があった。
      SELECT * FROM t WHERE x = TRUE; のような単純なクエリでさえ、テーブル内の x 値の分布によっては悪夢になり得た。
      Postgresではそうした問題をほとんど経験していないが、プリペアドステートメントと一緒にPostgresを使ったことがない点は認める。
      計画立案時間が遅いクエリ（100ms超）を見たことはあるので、キャッシュが有用だった可能性はあるが、実際に最適化が絶対必要だったケースは思い出せない
  • 386時代には、アセンブリで自己書き換えコードという概念があった。
    ここで示されているステンシルに似ているが、コードは通常単一インスタンスだったため、コピーを作ることはまれだった。
    たとえばDOS版のDoomもこうした最適化手法を使っていた。古いCPUで厳しいレンダリングループ性能を十分引き出すには必要だった