PostgreSQL 11 で登場した JIT コンパイルって結局何者？
(What is JIT Compilation Introduced inPostgreSQL 11? )長田 悠吾（Yugo Nagata）/ SRA OSS, Inc. 日本支社
PGConf.ASIA 20182018.12.12

自己紹介
●

長田 悠吾（Yugo Nagata）–チーフエンジニア@ SRA OSS, Inc. 日本支社

–PostgreSQL
●

技術支援

●

コンサルティング

●PostgreSQL インターナル講座講師

●

研究開発

Copyright © 2018 SRA OSS, Inc. Japan All rights reserved.

2

PostgreSQL 11●●●

PostgreSQL 11 の新機能として JIT コンパイル基盤が導入

実行時間を向上させるため、クエリプランの一部分に対し実行時（JIT）コンパイルを追加した
この機能を使うには LLVM が必要である

JIT コンパイル?
LLVM？
Copyright © 2018 SRA OSS, Inc. Japan All rights reserved.

3

Outline●

Just-in-Time (JIT) コンパイルとは●

LLVM とは●PostgreSQL のクエリ処理の中で、どのように使用されているか

Copyright © 2018 SRA OSS, Inc. Japan All rights reserved.

4コンパイラ（compiler）●

高水準言語によるソースコードから、機械語に（あるいは、元のプログラムよりも低い水準のコードに）変換するプログラム(Wikipedia)– 「コード」から「コード」への変換

コード

コード
コンパイル

– 変換後のコード●

コンピュータにより直接的に実行可能な機械語（ネイティブコード）●

元のプログラムよりも低水準な中間言語
Copyright © 2018 SRA OSS, Inc. Japan All rights reserved.

5

事前（AOT）コンパイル●

事前（Ahead-of-Time: AOT）コンパイラ–

アプリケーション実行前に事前にコンパイルするコンパイラ●

C言語– ソースコード（.c）を 機械語（ネイティブコード）に変換– PostgreSQL バイナリのビルド

C言語
●

機械語

Java
– ソースコード（.java） → バイトコード（.class）– バイトコードは、Java 仮想マシン（JVM）で実行可能

Javaバイトコード

Copyright © 2018 SRA OSS, Inc. Japan All rights reserved.

6インタプリタ（interpreter）●

プログラミング言語で書かれたソースコードないし中間表現を逐次解釈しながら実行するプログラム(Wikipedia)–

コードを「頭から順番に解釈しながら実行」

–

長所–

●

事前にコンパイルを必要としない●

特定のアーキテクチャに依存しないプログラム

短所●–実行時の性能の低さ

Java●

JVM によるバイトコードの解釈実行
Copyright © 2018 SRA OSS, Inc. Japan All rights reserved.

7

実行時（JIT）コンパイル●

実行時（Just-in-Time：JIT）コンパイラ–

ソフトウェアの実行時にコードのコンパイルを行い実行速度の向上を図るコンパイラ●

Java– 実行頻度の高いメソッドを実行時にネイティブコードにコンパイルJava
事前（AOT)
コンパイル●

Python + Numba

バイトコード

機械語実行時（JIT)
コンパイル– 指定した関数を実行時にコンパイルして実行

Copyright © 2018 SRA OSS, Inc. Japan All rights reserved.

8

PostgreSQL 11 における JIT コンパイル●●

SQL 中に含まれる「式」の評価–

WHERE 句–ターゲットリスト–

集約関数

タプルの deforming–

ディスク上のタプルを、インメモリの形式に変換する処理

Copyright © 2018 SRA OSS, Inc. Japan All rights reserved.

9

PostgreSQL のクエリ処理
●

パーサー–

●

–

パース処理
パーサー

意味解析

システムカタログを参照し、テーブルや演算子、型などの情報を追加
クエリツリーの書き換え

アナライズ処理
アナライザ

リライト処理リライタ
rewrite後のquery tree

クエリを処理するための最適な実行計画を生成

プラン処理
プランナ(オプティマイザ)エクゼキュータ–raw parse tree

query tree

プランナ–

●

問い合わせ文字列

リライタ
–

●

問い合わせを受信

アナライザ
–

●

構文解析

plan tree

クエリの実行

エグゼキュート処理
エグゼキュータ

Copyright © 2018 SRA OSS, Inc. Japan All rights reserved.

10パーサ（Parser）
●

パース処理

問い合わせを受信– SQLの文字列を解析し、パースツリーという木構造に変換する●例）SELECT a, b FROM tbl WHERE c < 10 AND d = 3;

問い合わせ文字列
パース処理
パーサー
raw parse tree
アナライズ処理アナライザ
query tree
リライト処理リライタ

SELECTrewrite後のquery tree

WHERE

プラン処理
プランナ(オプティマイザ)plan tree

Target Listab

エグゼキュート処理

FROMAND

エグゼキュータ<tblc=10d3

Copyright © 2018 SRA OSS, Inc. Japan All rights reserved.

11

アナライザ（Analyzer）●

アナライズ処理––

問い合わせを受信
問い合わせ文字列

システムカタログを参照しながら、パースツリーに必要な情報を追加して、クエリツリーに変換追加される情報●●

テーブルのOID–

スキーマサーチパスを考慮して参照されるテーブルを確定–テーブルに含まれる列名も調べられる

型のOID
–

●

パース処理
パーサー
raw parse tree
アナライズ処理アナライザ
query tree
リライト処理リライタ
rewrite後のquery tree
プラン処理
プランナ(オプティマイザ)plan tree
エグゼキュート処理
エグゼキュータ定数などの型を確定する演算子のOID–列や定数の型から、使用される演算子を確定する
Copyright © 2018 SRA OSS, Inc. Japan All rights reserved.

12

リライタ（Rewriter）●

リライト処理問い合わせを受信
問い合わせ文字列– パースツリーを書き換えを行う–

VIEW や RULE の機能を実現パース処理
パーサー
raw parse tree
アナライズ処理アナライザ
query tree●●

「ビュー」に対する SELECTは、定義された SQL クエリの実行に書き換えられる「ビュー」に対する更新クエリは、実テーブルの更新に書き換えられる– 自動更新可能ビュー

Copyright © 2018 SRA OSS, Inc. Japan All rights reserved.

リライト処理リライタ
rewrite後のquery tree
プラン処理
プランナ(オプティマイザ)plan tree
エグゼキュート処理
エグゼキュータ13プランナ（Planner）
●

プラン処理

問い合わせを受信
問い合わせ文字列– クエリツリーから、クエリの「実行計画」を生成●●

クエリ実行の推定コストを見積もる
最もコストが少なく、実行時間が短いと思われるプランを選択する– 実行計画はプランツリーという木構造で表される

パース処理
パーサー
raw parse tree
アナライズ処理アナライザ
query tree
リライト処理リライタ
rewrite後のquery tree
プラン処理
プランナ(オプティマイザ)plan treeエグゼキュート処理
エグゼキュータ

Copyright © 2018 SRA OSS, Inc. Japan All rights reserved.

14エクゼキュータ（Executor）●

エクゼキュート処理–●

問い合わせを受信

プランツリーを実行して、フロントエンドに結果を返す各ノードを再帰的に実行––

問い合わせ文字列
パース処理
パーサー
raw parse tree

各ノードはタプルを１行ずつ返す

アナライズ処理
アナライザ

上位のノードは下位ノードを呼び出し、その結果返ってきたタプルを受け取って処理する

query tree
リライト処理リライタ
rewrite後のquery tree

タプル

プラン処理
プランナ(オプティマイザ)エクゼキュータ
ノード

plan tree
エグゼキュート処理
エグゼキュータ

タプル

タプル

エクゼキュータ
ノード

エクゼキュータ
ノード

タプル

タプル
Copyright © 2018 SRA OSS, Inc. Japan All rights reserved.

15プランツリー実行の具体例
SELECT * FROM t1 INNER JOIN t2 USING(i) WHERE t1.i < 10;
QUERY PLAN-------------------------------------------------------Nested Loop (cost=0.00..2.03 rows=1 width=12)
Join Filter: (t1.i = t2.i)-> Seq Scan on t1 (cost=0.00..1.01 rows=1 width=8)
Filter: (i < 10)-> Seq Scan on t2 (cost=0.00..1.01 rows=1 width=8)(4 rows)
フロントエンド

ExecNestLoop(i < 10)t1

ExecScanアウター
プラン
ExecSeqScan(t1.i = t2.i)
インナープラン

ExecSeqScan

Copyright © 2018 SRA OSS, Inc. Japan All rights reserved.

ExecScant216

式の表現（expression）●

WHERE 句の条件などに含まれる式も、木構造で表現される–例）WHERE tbl.c < 10 AND tbl.d = 3
ANDの評価<の評価

カラム値
tbl.cの評価

定数
10の評価

=の評価

カラム値
tbl.dの評価

定数3の評価

Copyright © 2018 SRA OSS, Inc. Japan All rights reserved.

17式の評価 （〜9.6）●

PostgreSQL 9.6 までは、式の評価も再帰的に行われていた–

各ノードを評価する毎に、関数を実行–

上位ノードは下位ノードを評価した結果を利用→ 関数呼び出しのオーバヘッドが高かった
WHERE tbl.c < 10 AND tbl.d = 3

ANDの評価

評価

評価<の評価評価
カラム値
tbl.cの評価

評価定数10の評価

評価=の評価

カラム値tbl.dの評価

評価
定数3の評価Copyright © 2018 SRA OSS, Inc. Japan All rights reserved.

18

式の評価（10〜）●

木構造を以下のような中間表現（ExprState）に変換（= コンパイル）してから、実行（＝ インタプリタ）
EEOP_SCAN_FETCHSOME（タプルの取り出し）–EEOP_SCAN_VAR（tbl.c）–

EEOP_CONST

（10）

–

EEOP_FUNEXPR_STRICT（< の評価）–EEOP_BOOL_AND_STEP_FIRST

（AND）

–

EEOP_SCN_VAR（tbl.d）–●–

EEOP_CONST（3）–

EEOP_FUNCEXPR_STRICT（= の評価）–EEOP_BOOL_AND_STEP_LAST（AND）

WHERE tbl.c < 10 AND tbl.d = 3ANDの評価

変換

<の評価

カラム値
tbl.cの評価

定数10の評価=の評価

カラム値
tbl.dの評価

定数3の評価関数呼び出しコストが削減され、エクゼキュータの実行が高速化– それでもなお、条件分岐が多いのがネック

Copyright © 2018 SRA OSS, Inc. Japan All rights reserved.

19

JIT による式評価の高速化●●

一般的な式の評価を行うためには、あらゆる状況に対応しなければならない–

任意のテーブルに対する、任意の SQL–

次の命令を事前に知ることはできない–

予測のできない条件分岐（処理のジャンプ）が多くなる

クエリが決まった段階で、対象のテーブル、および評価すべき式も確定している–「式の評価」を予めネイティブコードにコンパイルしておき、それを呼び出すようにすれば、高速化できる可能性がある→ JIT コンパイルの出番●

LLVM を使用
Copyright © 2018 SRA OSS, Inc. Japan All rights reserved.

20

LLVM
●

LLVM
– 任意のプログラミング言語に対応可能なコンパイラ基盤●

コンパイラ作成のための、再利用可能なコンポーネントを提供

LLVM IR のレベルの最適化●
新しいコンパイラ作成の時間とコストを削減●– LLVMを使ったコンパイラの例●

Clang, Swift, Rust

– 機械語のコードを出力するだけではなく、JIT実行にも対応

フロントソースコード フロントフロントエンドエンドエンド

バックバック
バックエンド
エンド
エンド

最適化
中間表現
（LLVM IR)

機械語

中間表現
（LLVM IR)
JIT実行

Copyright © 2018 SRA OSS, Inc. Japan All rights reserved.

21

Clang の場合
●

Clang
–

バックエンドに LLVM を使った、C/C++ 向けコンパイラ–

C/C++ のコードを LLVM の中間表現に変換–

LLVM IR のレベルで最適化

ソースコード(C/C++)

最適化

clang
中間表現
（LLVM IR)

中間表現
（LLVM IR)

バックバックバックエンドエンドエンドCopyright © 2018 SRA OSS, Inc. Japan All rights reserved.

機械語22

LLVM IR●

LLVM で使われる内部表現言語●

３つの表現形式–––

メモリ内のバイナリ表現●

これを生成するための API が用意されている●PostgreSQL はこれを使っている

ディスク上でのバイナリ表現●

ビットコードと呼ばれる●ファイル拡張子は .bc

人間に読めるテキスト表現●

ファイル拡張子は .ll
Copyright © 2018 SRA OSS, Inc. Japan All rights reserved.

23

LLVM による JIT●

PostgreSQL の JIT– 式表現の中間表現（ExprState）を、LLVMの中間表現（LLVM IR）に変換– それを LLVM で JIT コンパイルして、ネイティブコードに変換– PostgreSQL 内部から関数として実行

式表現の中間表現（ExprState)式表現のツリーを変換

llvm_compile_expr

最適化
中間表現
（LLVM IR)

PostgreSQL
エクゼキュータ

バックエンド
中間表現（LLVM IR)

実行
（関数呼び出し）Copyright © 2018 SRA OSS, Inc. Japan All rights reserved.

JITコンパイル

ネイティブ
コード

24

JIT コンパイルのタイミング●

クエリ実行直前（= エクゼキュータの初期化段階）–

プランツリーの各ノードの初期化が行われる–

式表現（WHERE 条件など）を含むノードの初期化時：●

ツリー構造の式表現が中間表現（ExprState）に変換される●

続いて、ExorState は LLVM IR の関数に変換される– この時点ではまだコンパイルはされない–●

クエリに含まれる全ての式表現が対象

クエリ実行時（= エクゼキュータの実行段階）–

実際に式を評価する時に、その式評価に対応する関数が呼ばれる–

初回の関数呼び出し時に、全ての関数のコンパイルがまとめて実行される

Copyright © 2018 SRA OSS, Inc. Japan All rights reserved.

25

タプルの deforming●

ディスク上のタプルを、インメモリの形式に変換する処理–

式を評価するときに、タプルを取り出す命令の中で行われる●–

例えば、EEOP_SCAN_FETCHSOME

タプルからカラムの値を必要な分だけ取り出す●例）カラムを１０個持つテーブルの場合
CREATE TABLE tbl (a1 int, a2 text, ..., a10 timestamp);
SELECT a3, a7 from tbl;
– この場合は、７番目のカラム（a7） までの値を取り出す（８番目以降のカラムは必要ない）–

この処理もボトルネックとなるため、 JIT コンパイルによる高速化の対象

Copyright © 2018 SRA OSS, Inc. Japan All rights reserved.

26

タプルの構造●

固定長のタプルヘッダ●

null bitmap●–

列の数分だけのビット列–もしNULLの列がタプル中に存在しなければnull bitmapは省略される

padding–●

バイト位置調整のための「詰めもの」

列データ–型によってサイズが異なる（可変長の型もある）–

列と列の間には、データ型に応じたpaddingが入ることがある

null bitmap（オプション）

padding

タプルヘッダ

列１列２Copyright © 2018 SRA OSS, Inc. Japan All rights reserved.

・・・

27

タプルの deforming の JIT 化●

null bitmap（オプション）

条件分岐が多い–

値がNULLかどうかの確認が必要–

カラムの型によっても処理が異なる

padding

タプルヘッダ

列１列２・・・

カラム値を取り出すには、これらのオフセット位置を計算する必要がある→ CPUボトルネック●

テーブルのカラム型がわかっていれば、事前に取り除ける条件分岐がある–

NOT NULL 制約があるカラムは NULL かどうかの確認は不要–

カラムの型は事前に知ることができる→ JIT コンパイルによって分岐を事前に取り除くことで高速化
Copyright © 2018 SRA OSS, Inc. Japan All rights reserved.

28

関数のインライン展開（１）●式の評価には関数の実行が含まれている–組み込み関数●–

ユーザ定義関数–演算子の評価にも関数が使用される●●

sqrt, md5, random例）int8 同士の等号: int8eq()

インライン展開
––

LLVM IR のコードからこれらの関数を呼び出すのではなく、関数の方を LLVM IRに変換してしまう
関数呼び出しのオーバヘッドを削減

Copyright © 2018 SRA OSS, Inc. Japan All rights reserved.

29

関数のインライン展開（２）●関数のインライン展開を可能にするため、PostgreSQL のソースコードは LLVM IRにコンパイルされる––

拡張モジュールをインストールした場合も同様
バイナリは $pkglibdir/bitcode 以下にインストールされている$ tree postgresql/lib/bitcode/lib/bitcode/├── pg_trgm│├── trgm_gin.bc│├── trgm_gist.bc│├── trgm_op.bc│└── trgm_regexp.bc├── pg_trgm.index.bc├── postgres│├── access││├── brin│││├── brin.bc│││├── brin_inclusion.bc│││├── brin_minmax.bc│││├── brin_pageops.bc│││├── brin_revmap.bc│││├── brin_tuple.bc│││├── brin_validate.bc│││└── brin_xlog.bc││├── common│││├── bufmask.bc（以下略）

Copyright © 2018 SRA OSS, Inc. Japan All rights reserved.

30

JIT が有効に働く状況●●

CPU バウンドな状況が長時間になるようなクエリ–

複雑な式表現をもつ–

行数が多い–

主に解析系のクエリで有効–

短時間のクエリでは JIT のオーバーヘッドの方が大きくなってしまう

プランナの推定コストに基づく判断–

jit_above_costより大きくなる場合のみ JIT を使う–

jit_inline_above_cost より大きい場合には、関数のインライン化を行う–

jit_optimize_above_cost より大きい場合には、積極的な最適化を行う

Copyright © 2018 SRA OSS, Inc. Japan All rights reserved.

31

設定パラメータ
●

●

jit–

JIT コンパイルを使用するかどうか–

デフォルト：off––

JIT コンパイルを使用するコストの閾値●

デフォルト：100000–●–

関数のインライン化を使用するコストの閾値
デフォルト：500000

積極的な最適化を使用するコストの閾値
デフォルト：500000

jit_provider–

jit_inline_above_cost–

jit_optimize_above_cos–

jit_above_cost–●●

JIT 機能を提供するライブラリの名前
デフォルト：llvmjit

jit_dump_bitcode––生成された LLVM IR のファイル（ビットコード：.bc）に出力
デフォルト：off

Copyright © 2018 SRA OSS, Inc. Japan All rights reserved.

32動作例（１）

Copyright © 2018 SRA OSS, Inc. Japan All rights reserved.

33動作例（２）●

EXPLAIN ANALYZE の結果
Function Scan on f100000000 g(cost=0.25..5750000.25 rows=100000000 width=40)(actual time=22073.673..233385.687 rows=100000000 loops=1)
Planning Time: 0.255 ms
JIT:
Functions: 2実施された JIT 処理作成された関数の数

Options: Inlining true, Optimization true, Expressions true, Deforming true
Timing: Generation 1.926 ms, Inlining 5.988 ms, Optimization 36.134 ms,
Emission 20.168 ms, Total 64.215 ms
Execution Time: 236383.943 ms

JIT 処理の所要時間(7 rows)

Copyright © 2018 SRA OSS, Inc. Japan All rights reserved.

34

まとめ●

●

PostgreSQL 11 への JIT コンパイラ導入–JIT コンパイルとは何か–

LLVM とは何か–

PostgreSQL のどこで、どのように、なぜ使われるのか

JIT コンパイルはまだ登場したばかりの機能–

今後も改善されていくはず

Copyright © 2018 SRA OSS, Inc. Japan All rights reserved.

35

Thank you

Copyright © 2018 SRA OSS, Inc. Japan All rights reserved.

36