HN 日本語サマリー

← 一覧へ戻る
プログラミング

Postgresを分析クエリで300倍高速化する:バッチ処理、演算子融合、SIMD

Making Postgres 300x faster for analytics: batching, operator fusion, and SIMD (malisper.me)

293 pointsby poly2it149 コメント

要約

pgrustプロジェクトは、Postgresの分析クエリ性能を300倍向上させることに成功しました。これは、現代のハードウェア環境(RAM容量の増大、CPU・メモリ速度の向上)に合わせて、ディスクI/O中心だったPostgresのクエリエンジンを、CPU・メモリ帯域幅の効率を最大化するように再設計したためです。特に、行単位処理のオーバーヘッドを削減するバッチ処理、複数の処理を統合する演算子融合、そしてSIMD命令の活用が鍵となりました。

全文翻訳

Postgresを分析クエリで300倍高速化:バッチ処理、演算子融合、SIMD

先週、pgrustのバージョン0.2をリリースしました。このリリースはパフォーマンスに焦点を当てたもので、以前のバージョンから10倍高速化されています。OLTPベンチマークではPostgresより30%高速であり、分析データベースのベンチマークであるClickbenchでは、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.4xlargeインスタンスで実行しました。

比較のために、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から行を取得し、それらの行の値の合計を計算する」と言っています。このクエリプランは、クエリの性質上非常にシンプルですが、JOIN、ソート、サブクエリなどが含まれると、はるかに複雑になる可能性があります。Postgresには合計で40種類以上のプランノードがあります。

クエリプランを生成した後、Postgresはそれをクエリエンジンに渡します。Postgresのクエリエンジンは、クエリプランを受け取り、実際に行を取得して集計を実行する部分です。Postgresは「Volcanoモデル」と呼ばれるスタイルのエグゼキュータを使用しています。その仕組みを理解するために、Postgresクエリエンジンのミニチュア実装を以下に示します。

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は、コンパイラの最適化によってベンチマークが妨げられるのを防ぐために必要です)。

Volcanoモデルの重要な特徴は、すべてのノードがサポートするnext()メソッドです。next()の仕事は、単一行を返すことです。シーケンシャルスキャンのnext()は、シーケンシャルスキャン内の次の行を返します。集計のnext()は、集計全体を計算してから単一行の結果を返します。クエリプランの実行は、ルートプランノードのnext()を、行を返さなくなるまで呼び出すだけです。Volcanoモデルの利点は、非常にシンプルであることです。プランノードごとに1つのメソッドを実装するだけで済みます。これは簡略化されていますが、上記のコードはPostgresが内部で行っていることに非常に近いです。

Volcanoモデルは物事をシンプルにしますが、多くのオーバーヘッドも追加します。この例を実行すると、1.3秒かかります。クエリエンジンの部分以外の多くの要素を削除しているため、Postgresのバージョンよりもはるかに高速ですが、生のforループよりも遅いです。これはVolcanoモデルのオーバーヘッドのためです。

上記のコードで最もパフォーマンスに影響しているのは、next()が一度に1行しか処理しないことです。バッチ処理がありません。SeqScan.next()関数は行ごとに呼び出されます。これは、特にパイプライン処理などの多くのCPU最適化が、実行時に未知の関数を呼び出す場合にうまく機能しないため、かなりのオーバーヘッドを追加します。実装できる最初の最適化はバッチ処理です。

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ノードを作成できます。

struct SumAggregateSequentialScan<'a> {
    table: &'a [f64],
    done: bool,
}

impl Node for SumAggregateSequentialScan<'_> {
    fn next(&mut self) -> Option<f64> {
        if self.done {
            return None;
        }
        self.done = true;
        let mut total = 0.0;
        for &value in self.table {
            total += value;
        }
        Some(total)
    }
}

これは、事実上forループと同じコードであるため、ストレートなforループと同じパフォーマンスを提供します。これはずるいように聞こえるかもしれませんが、事前にわかっている特定のクエリに対して最適化をハードコーディングしているため、確かにずるいです。演算子融合では、最も一般的なケースをいくつかハードコーディングするのは理にかなっていますが、それでも事前に準備していないケースにすぐに遭遇するでしょう。

これはJITコンパイルで解決できます。JITコンパイルを使用すると、理想的なコードを生成して、すべてのクエリで「ずるい」ことができます。JITコンパイルにより、クエリに関係なく完璧なコードを生成し、常に演算子融合を実行できます。残念ながら、この記事はすでに長くなっているため、pgrustがJITコンパイルをどのように活用するかについては、別の機会に説明します。

最後の最適化として、SIMDに目を向けます。SIMDは、複数のデータ要素に対して同時に1つの操作を実行できるCPU命令セットを指します。複数の行に対して同時に操作を実行するためにSIMDを使用することは、1行ずつ操作を実行するよりも通常はるかに高速です。コードをSIMDを使用するように変更すると、次のようになります。

#[cfg(target_arch = "aarch64")]
struct SumAggregateSequentialScanSimd<'a> {
    table: &'a [f64],
    done: bool,
}

#[cfg(target_arch = "aarch64")]
impl Node for SumAggregateSequentialScanSimd<'_> {
    fn next(&mut self) -> Option<f64> {
        if self.done {
            return None;
        }
        self.done = true;
        use std::arch::aarch64::*
        let mut acc = unsafe { [vdupq_n_f64(0.0); 4] };
        let (chunks, rest) = self.table.as_chunks::<8>();
        for chunk in chunks {
            for lane in 0..4 {
                unsafe {
                    let v = vld1q_f64(chunk.as_ptr().add(2 * lane));
                    acc[lane] = vaddq_f64(acc[lane], v);
                }
            }
        }
        let mut tail = 0.0;
        for &value in rest {
            tail += value;
        }
        Some(unsafe {
            let s01 = vaddq_f64(acc[0], acc[1]);
            let s23 = vaddq_f64(acc[2], acc[3]);
            vaddvq_f64(vaddq_f64(s01, s23)) + tail
        })
    }
}

私たちのコードは現在135ミリ秒かかります。これは、forループよりも約3倍、元のVolcanoコードよりも10倍高速です。コンパイラがforループをSIMD等価物に置き換えることは一般的ですが、そうならないようにこの例を選びました。浮動小数点演算は結合法則を満たさないため、合計の実行順序を変更するとわずかに異なる結果が生じる可能性があるため、コンパイラは通常、浮動小数点数の操作時にSIMDの導入を避けます。

—

すべてをまとめると、3つの簡単な最適化により、クエリを10倍高速化することができました。最終的な結果は以下の通りです。

実装時間加速率
Postgres約20秒—
Volcanoモデル1.3秒1倍
+ バッチ処理480ミリ秒2.7倍
+ 演算子融合358ミリ秒3.6倍
+ SIMD135ミリ秒9.6倍

これらの最適化(およびさらに多くの最適化)により、pgrustは分析クエリにおいてPostgresの数百倍のパフォーマンスを発揮できるようになります。

ベンチマーク設定:AWS c8g.4xlarge (Graviton4, 16 vCPU)、PostgreSQL 18.4 (max_parallel_workers_per_gather = 0)、shared buffers内のデータウォーム、5回の実行の中央値。Rustはcargo build –releaseでビルド、各実装につき4回実行、すべて単一マシン上の単一プロセスで測定。

お読みいただきありがとうございます。プロジェクトをサポートしたい場合は、pgrustをサポートする最善の方法はGitHubでスターを付けることです。フォローしたい場合は以下をご覧ください。

  1. GitHub
  2. Discord
  3. メーリングリスト — JITコンパイルのフォローアップを含む、pgrustに関する週次アップデート
  4. pgrust.com