プログラミング
Postgresを分析クエリで300倍高速化する：バッチ処理、演算子融合、SIMD
Making Postgres 300x faster for analytics: batching, operator fusion, and SIMD (malisper.me)
要約
pgrustプロジェクトは、Postgresの分析クエリ性能を300倍向上させることに成功しました。これは、現代のハードウェア環境（RAM容量の増大、CPU・メモリ速度の向上）に合わせて、ディスクI/O中心だったPostgresのクエリエンジンを、CPU・メモリ帯域幅の効率を最大化するように再設計したためです。特に、行単位処理のオーバーヘッドを削減するバッチ処理、複数の処理を統合する演算子融合、そしてSIMD命令の活用が鍵となりました。
全文翻訳
先週、pgrustのバージョン0.2をリリースしました。このリリースはパフォーマンスにすべてを注力したもので、以前のバージョンより10倍高速です。OLTPベンチマークでは、pgrustはPostgresより30%高速であり、分析データベースのベンチマークであるClickbenchでは、pgrustはPostgresより300倍高速です。Clickhouseさえも上回っています。
クエリエンジンは、私たちが達成した大幅なパフォーマンス向上における最大の変更点の一つです。クエリエンジン単独で、300倍の約10倍の改善をもたらしました。Postgresのクエリエンジンのミニチュア版から始め、pgrustのクエリエンジンをこれほど高速にしたのと同じ最適化を一つずつ追加していきます。
Postgresと比較して改善の余地がこれほど大きい理由の背景として、Postgresは異なる時代に作成されたということがあります。オリジナルのPostgresプロジェクトは80年代に遡ります。当時は、データベースパフォーマンスの主なボトルネックがディスクI/Oでした。3つのトレンドが、この状況を変えました。
1. 多くのデータセットが現在ではRAMに収まるようになり、ほとんどのディスクI/Oが不要になりました。
2. RAMに収まらないデータセットの場合、ワークロードが異なります。データ分析はデータをバルクでスキャンします。ボトルネックはディスクのスループットではなく、CPUのスループットやメモリのスループットであることが多くなります。
3. 近年、ディスクは大幅に高速化しました。NVMeはハードドライブより数百倍高速です。
これら3つのトレンドにより、CPUとメモリの速度が歴史的に見てより重要になりました。私たちが実装した多くの最適化は、この点に焦点を当てています。
クエリエンジンは、データベースにおけるCPUの主な使用者です。私たちは、同じクエリを処理する際に、Postgresよりも少ないCPUとメモリ帯域幅で済むようにpgrustのクエリエンジンを最適化しました。
Postgresのクエリエンジンがいかに遅いかを示すために、最初の5億個の数値を合計する簡単なクエリを見てみましょう。
CREATE TABLE my_table AS select col::float8 from generate_series(1.0, 500000000.0) g(col);
SELECT SUM(col) FROM my_table;
Postgresでこれを実行すると、約20秒かかります。これは、並列クエリを無効にしたc8g.4xlで実行した結果です。
比較として、Rustで同等の処理を計測すると、以下のようになります。
let table: Vec<f64> = (1..=500_000_000usize).map(|i| i as f64).collect();
let mut sum = 0.0;
for &value in &table {
sum += value;
}
このクエリは358ミリ秒で完了します。これは約55倍高速であり、信じがたいかもしれませんが、さらに高速化することも可能です。
この例は厳密な比較ではありません。Postgresの内部では、はるかに多くの処理が行われています。同時に、データベースの最適化とは、これらのオーバーヘッドを可能な限り除去することです。（もし興味があれば、Postgresのオーバーヘッドの主な原因として、1. ロック、2. Postgresのストレージフォーマットの解析とクエリに関連するタプルの抽出、の2つが挙げられます。）
クエリエンジン自体の影響に焦点を絞るために、Postgresのクエリエンジンのミニチュア版を構築してみましょう。
まず、クエリエンジンとは何かを簡単に説明します。SQLクエリを処理する際、Postgresはまずクエリを「クエリプラン」と呼ばれる内部表現に変換します。これは、Postgresがクエリをどのように実行するかを記述したものです。上記の例では、Postgresは次のようなクエリプランを生成するでしょう。
これは実質的に「my_tableから行を取得し、それらの行の値を合計する」と言っています。このクエリプランは、クエリの性質上非常に単純ですが、結合、ソート、サブクエリなどを扱うようになると、はるかに複雑になります。Postgresには、合計で40種類以上のプランノードがあります。
クエリプランを生成した後、Postgresはそれをクエリエンジンに渡します。Postgresのクエリエンジンは、クエリプランを受け取り、実際に行を取得して集計を実行する部分です。Postgresは「ボルケーノモデル」と呼ばれる実行スタイルを使用しています。その仕組みを理解するために、Postgresクエリエンジンのミニチュア実装を見てみましょう。
```rust
use std::hint::black_box;
trait Node {
fn next(&mut self) -> Option<f64>;
}
struct SeqScan<'a> {
table: &'a [f64],
pos: usize,
}
impl Node for SeqScan<'_> {
fn next(&mut self) -> Option<f64> {
if self.pos >= self.table.len() {
return None; // end of table
}
let value = self.table[self.pos];
self.pos += 1;
Some(value)
}
}
struct SumAggregate<'a> {
child: Box<dyn Node + 'a>,
total: f64,
done: bool,
}
impl Node for SumAggregate<'_> {
fn next(&mut self) -> Option<f64> {
if self.done {
return None;
}
while let Some(value) = self.child.next() {
self.total += value;
}
self.done = true;
Some(self.total)
}
}
let table: Vec<f64> = (1..=500_000_000usize).map(|i| i as f64).collect();
let mut plan = SumAggregate {
child: black_box(Box::new(SeqScan { table: &table, pos: 0 })),
total: 0.0,
done: false,
};
let sum = plan.next().unwrap();
```
（black_boxは、コンパイラの最適化がベンチマークを妨げるのを防ぐために必要です）
ボルケーノモデルの主な特徴は、すべてのプランノードがサポートする`next()`メソッドです。`next()`の仕事は、単一行を返すことです。シーケンシャルスキャンの`next()`は、シーケンシャルスキャン内の次の行を返します。集計の`next()`は、集計全体を計算してから、単一行の結果を返します。クエリプランの実行は、ルートプランノードの`next()`を、それがこれ以上行を返さなくなるまで呼び出すだけです。
ボルケーノモデルの利点は、非常にシンプルであることです。プランノードごとに1つのメソッドを実装すればよく、それだけです。上記コードは簡略化されていますが、Postgresが内部で行っていることと非常に近いです。
ボルケーノモデルは物事をシンプルにしますが、多くのオーバーヘッドも追加します。この例を実行すると、1.3秒かかります。これは、クエリエンジン以外の多くの部分を削除しているため、Postgresのバージョンよりもはるかに高速ですが、ボルケーノモデルのオーバーヘッドのために、生のforループよりもまだ遅いです。
上記のコードで最もパフォーマンスに影響する点は、`next()`が一度に1行しか処理しないことです。バッチ処理がありません。`SeqScan.next()`関数は、行ごとに呼び出されます。これは、特に多くのCPU最適化（パイプライン処理など）が、実行時まで不明な関数を呼び出す場合にうまく機能しないため、かなりのオーバーヘッドを追加します。
実装できる最初の最適化は、バッチ処理です。
```rust
const BATCH: usize = 1024;
trait BatchNode {
fn next_batch(&mut self, out: &mut [f64; BATCH]) -> usize;
}
struct BatchSeqScan<'a> {
table: &'a [f64],
pos: usize,
}
impl BatchNode for BatchSeqScan<'_> {
fn next_batch(&mut self, out: &mut [f64; BATCH]) -> usize {
let n = (self.table.len() - self.pos).min(BATCH);
out[..n].copy_from_slice(&self.table[self.pos..self.pos + n]);
self.pos += n;
n
}
}
struct BatchSumAggregate<'a> {
child: Box<dyn BatchNode + 'a>,
total: f64,
}
impl BatchSumAggregate<'_> {
fn run(&mut self) -> f64 {
let mut buf = [0.0f64; BATCH];
loop {
let n = self.child.next_batch(&mut buf);
if n == 0 {
break;
}
for &value in &buf[..n] {
self.total += value;
}
}
self.total
}
}
let mut plan = BatchSumAggregate {
child: black_box(Box::new(BatchSeqScan { table: &table, pos: 0 })),
total: 0.0,
};
let sum = plan.run();
```
バッチ処理単独で、ほとんどのオーバーヘッドが除去されます。これにより、クエリの実行時間が1.3秒から約480ミリ秒に短縮されます。まだforループより遅いですが、はるかに近づきました。
非常に重要な詳細として、バッチバッファはスタック上に割り当てられます。これは、集計ノードが実行中にメモリを割り当てる必要がないことを意味します。メモリ割り当ては、遅い操作の一つになりがちです。したがって、超高速なコードを書く場合、メモリ割り当ての回数を最小限に抑えたいでしょう。
次に、バッチバージョンのプロファイリングを行うと、ホットスポットは`copy_from_slice`になります。バッチ処理を行っていても、アイテムをバッファにコピーする必要があります。このオーバーヘッドは、「演算子融合」として知られるもので排除できます。もし、一緒に行われることがわかっている一般的な操作があれば、2つのノードを置き換える単一のノードを作成できます。この場合、シーケンシャルスキャンと合計のロジックを組み合わせた単一の`SumAggregateSequentialScan`ノードを作成できます。
```rust
struct SumAggregateSequentialScan<'a> {
table: &'a