PostgreSQLオプティマイザの10年にわたる改善

• PostgreSQL 8から16までを Join Order Benchmark で比較し、90パーセンタイルのクエリ遅延時間を通じて、長期的なテール性能の改善を実証的に確認
• PostgreSQL 8と比べて16では テール遅延時間 がほぼ半減しており、13〜16の区間はおおむね安定した水準にとどまる
• 回帰分析ではメジャーバージョンが1つ上がるごとに平均 15%の性能向上 が見られたが、線形モデルでは変化の傾向を十分に説明できない可能性がある
• 実験は GCC 13.2、Arch Linux Docker、shared_buffers 8GB、work_mem 8MB で条件を固定し、クエリオプティマイザの品質 に焦点を当てた
• 改善幅を解釈する際には、オプティマイザだけでなく、並列ワーカーや JITコンパイル のような実行エンジンの変化もあわせて考慮する必要がある

---

PostgreSQL 8〜16 ベンチマーク設定

• 分析対象はオープンソースのクエリオプティマイザである PostgreSQL の8から16までのメジャーバージョン
• ベンチマークには、複雑な結合が多いクエリ群である Join Order Benchmark が使われた
  • このベンチマークは「How Good are Query Optimizers, Really?」論文で導入された
• 各 PostgreSQL バージョンは GCC 13.2 により Arch Linux Docker コンテナ内でビルドされた
• 測定環境は、インデックスや I/O 性能よりも クエリオプティマイザの品質 を見るための構成に調整された
  • shared_buffers はデータベース全体を格納できる十分な大きさの 8GB に設定された
  • work_mem はすべてのバージョンで 8MB に固定された
• 各クエリはキャッシュウォームアップのために1回実行した後、追加の5回実行における 中央値遅延時間 を記録した
• 各メジャーバージョンには最新のマイナーバージョンが使われた
  • たとえば PostgreSQL 8 では 8.4.22 が対象
  • それらのマイナーバージョンは通常、新しいメジャーバージョンの後に出ているが、一般にはバグ修正のみを含み、新機能や性能改善は含まない

測定結果と解釈

• PostgreSQL の テール性能 は全体として大きく向上している
  • PostgreSQL 8 と 16 を比較すると、テール遅延時間はほぼ半減している
  • PostgreSQL 13 から 16 まではおおむね安定した水準を維持している
• 回帰分析は、メジャーバージョン番号とクエリ遅延時間の間に低下傾向が有意にあるかを確認し、バージョンごとの改善幅を定量化するために使われた
  • 線形回帰ベースでは、新しいメジャーバージョンごとに Join Order Benchmark で平均 15%の性能向上 が見られる
  • ただし、線形モデルは実際の変化傾向を測定するには不適切な可能性がある
• すべての改善を クエリオプティマイザ だけで説明するのは難しい
  • 並列ワーカーや JITコンパイル のような実行エンジンの改善も性能に影響する
  • JOB の各クエリプランが年ごとにどのように変わったかは、別途分析すべき課題として残っている
• PostgreSQL 8 から 16 へ上げることで、ワークロードの テール遅延時間 が大きく減る可能性がある
• 研究比較では、PostgreSQL 自体が継続的に強くなっているベンチマーク基準である点が重要
  • Neo と Bao は PostgreSQL 11 と比較していたが、より新しい研究は PostgreSQL 14、15、16 と比較している
  • 過去の手法が PostgreSQL 比で30%改善、最新の手法が25%改善だったとしても、最新手法はより強力な PostgreSQL と比較している可能性がある
• 元の測定値は raw data で確認できる

[GN⁺]

Hacker News のコメント

• Postgres を15年使ってきて、キャリアの大半を数学的最適化問題のモデル化と解決に費やしてきたが、このテーマで重要なのは3つだと思う。
  すべての最適化問題にはコストデータが必要で、データが多く質が高いほどよくなる。Postgres では列間統計などの改善はあったが、まだシステムコールのレイテンシのような大きな穴が残っている。ディスクからページを読むレイテンシはシステムごとに大きく違うのに、Postgres はそれを直接測定せず設定値に依存している。外部キー統計も欠けていて、外部キーをたどるジョインでは悪い計画が出るべきではないのに、今でも時々起きる。
  特に大きく高コストなクエリには、遅延計画立案や代替シナリオの計画が必要だ。現状では実行前に計画が確定するが、実行初期段階で得られる行数やカーディナリティ推定値が後半の計画を大きく改善し得る。
  機械学習も改善の余地がある領域だが、これまで見た試みは印象的ではなかった。計画そのものに機械学習を使うのではなく、コストの発見と推定に使うべきだ。より良いコストモデルを作り、最適化エンジンがそのデータを活用できるようにする必要がある。

  • もっと意見を聞きたい。たとえばシステムコールのレイテンシが上位リストに入っているのは意外だ。データベースコミュニティの一般的な見方としては、コストモデルは概ね問題なく、本当にひどいのはカーディナリティ推定だと思う。
    遅延／代替計画立案については、適応的クエリ実行が妥当な方法なのか気になる。クエリ実行初期の情報を後続の計画に影響させることはできるが、最初のいくつかのジョインを間違って選ぶのはよくあることで、Yannakakis/SIPs のようなものがなければリカバリが難しいのではないかという懸念がある。
    「クエリ最適化向け機械学習」については、確かに偏りがある。ただ、私が見た「計画向け機械学習」のアプローチはすべて、内部的には結局コストの発見／推定に機械学習を使っている。これらのアプローチは、収集するデータ、つまり探索と、生成する計画の品質、つまり活用とのバランスを取ろうとするものだ。興味深いことに、計画と完全に切り離した形で機械学習を使うと、推定はより正確になっても実際のクエリ計画は悪化する: https://people.csail.mit.edu/tatbul/publications/flowloss_vl...
    この分野に利害関係があるので、私の意見はその点を差し引いて見てほしい。
  • 代替計画は本当に良さそうだ。少し前に見たクエリ計画では、あるサブクエリから約1,000行が返ると見積もって、インデックススキャンにネストループを付けていたが、実際には約10億行だった。
    なぜ推定がそこまで外れたのかはまだ分からないが、行数があるしきい値を超えたらネストループからハッシュジョインへ切り替えられるなら、壊滅的な計画を避けるのに大いに役立ちそうだ。
  • 外部キー統計が欠けているというのが正確に何を意味するのか気になる。Postgres も多くのリレーショナルデータベースと同じく、外部キーにインデックスを自動作成しないが、それはすでに知っていそうだ。
    ジョイン順序の問題を言っているのか？
  • MSSQL はこの点でより優れていると思うのか気になる。

• Postgres のクエリ最適化器は、ディスクから読むページ数と、中間結果としてディスクに書き出すページ数を減らそうとする。だから、すべてのデータを収められるほどshared buffersを大きくしてクエリ最適化器をベンチマークするのは間違っているように見える。
  そうすると、生成されたクエリ計画の品質ではなく、クエリ最適化器とジョイン処理器の速度を測ることになる。実際には各バージョンで生成された計画がすべて同じで、実行速度だけを測っていた可能性があっても驚かない。

  • そうではない。最適化対象はディスクから読むページだけでなく、CPU 使用量なども含めたコストだ。
    コストはディスク読み取り回数ではなく所要時間と相関するように作られた任意単位なので、すべてが RAM に載った状態で計画を比較するのも十分に妥当だ。慣例上、ディスクから1ページ読むことを 1.0 にスケーリングしているが、これは「最適化器がディスクページ読み取り数を最小化する」という話とは違う。任意のマシンで 1ms を 1.0 としてもよかったはずだ。
  • 計画が似ていて、実行エンジンの改善を測っていた可能性は確かにある。Join Order Benchmarkは最適化器の品質をテストするように設計されている。
    PG の最適化器はディスクから読むページ数だけでなく、CPU が検査するタプル数、条件式の評価回数なども減らそうとし、これらの数値がすべて「コスト」としてまとめられて、最適化器が最小化する関数になる。
    コールドキャッシュとウォームキャッシュの性能測定は異なる結果を出す可能性があり、この実験は明らかにウォームキャッシュのシナリオだ。しかしコールドキャッシュにも述べた問題がある。Join Order Benchmark のデータサイズでは、PG の B-tree 改善で I/O を数回節約する効果が、CPU ベースの改善より支配的になり得る。
    参考までに、P90 レイテンシのクエリの計画は、PG 8.4 ではループジョインとマージジョインを使う計画だったが、PG 16 ではハッシュジョインを使う計画に変わっており、このクエリはもはや P90 クエリではない。これは少なくとも最適化器改善の一部の証拠と言える。

• 記事では PostgreSQL のJIT コンパイラに触れていたが、これまでのところクエリ性能を落とすのしか見たことがない。インストール時のチェックリストに無効化を入れている。

  • ある顧客が Postgres に移行した後、最悪の性能問題に遭遇した。奇妙なことに Docker とテストサーバーの設定でだけ発生し、開発者のマシンでは発生しなかった。開発者は Homebrew で Postgres を動かしていた。
    調べてみると Homebrew はJIT サポートなしで Postgres をインストールしており、開発者のマシンではあるクエリが 200ms で終わったが、JIT が有効な環境では 4〜5秒かかった。Postgres を深く使っているわけではないので原因を見つけるのに少し時間がかかり、それ以来いつも JIT を切って振り返っていない。
  • JIT コンパイラは分析クエリには素晴らしい。
    PostgreSQL では JIT 有効化のしきい値も設定できるので、JIT が有効になる基準をより高くできる。
  • pg の JIT は、LLVM が JIT にあまり向いていないことをかなりよく示していて、Postgres に永続的な共有クエリキャッシュがないためさらに悪化している。
    将来のクエリのために非同期コンパイルできるなら、害は少なくなりそうだ。実際、一般的な JIT、特に最適化バックエンドはその方式に近い。
  • Postgres はクエリを一度 JIT コンパイルしてから、コンパイル済みクエリを何度も実行することはできないのか？

• 興味深いが、Postgresのバージョン番号体系はv10で変わっている。9.6、9.5、9.4、9.3、9.2、9.1、9.0、8.4、8.3、8.2、8.1、8.0は、実質的にはすべて別々のメジャーバージョンである
  それらのバージョンで性能がどう変わったのかを見るのも興味深そうだ

  • それでもv9.0から9.6までは、バイナリだけ差し替える形でより速いインプレースアップグレードができるように、メジャーバージョン間のファイルシステム互換性を維持してくれた点はありがたかった
    そのせいで足かせになった可能性はあるが、より多くのダウンタイムや再インデックスが必要な年次アップデートはあまり楽しいものではなく、多くのサイトが旧バージョンのサポート終了までアップグレードを先延ばしにする理由になり得る。特にAWS RDSユーザーにとってはそうだろう
    v10以降の論理レプリケーションによるアップグレードは可用性の面で利点があるが、スキーマが比較的単純でないなら、避けられないコストと大きなリスクを伴う大規模プロジェクトである
  • 完全に同意する。バージョン番号をsemver方式で解釈して、各メジャーバージョンの最新バージョンを選んだが、これはPostgreSQLが伝統的にメジャーバージョン番号を扱ってきた方法とは異なる
    たとえばPG 8.2と8.1は互いに異なるメジャーバージョンだが、私はマイナーバージョンのように解釈した。こうした主な理由はテストすべきバージョン数を減らすためで、より完全な分析であれば各実際のメジャーバージョンをテストすべきだという点には同意する

• 「もちろん、この改善のすべてがクエリオプティマイザのおかげというわけではない」とあるが、バージョンごとに実行計画の変化があったのかを見ると興味深そうだ

• Proebstingの法則を思い出す: https://proebsting.cs.arizona.edu/law.html

  • コンパイラ最適化の良いところは、既存のCPUを物理的にいじらなくても性能を改善できることだ。毎年、誰かが設計した機械からより多くの性能を引き出し、それが積み重なると大きくなる
    Pythonの性能を1%最適化したら環境への影響はどれほどになるか想像してみてほしい。大気中のCO2をどれだけ減らせるだろうか。おそらく本人と家族、友人全員の環境フットプリントを合わせたものより大きい可能性が高い。もしかすると住んでいる都市全体に匹敵するかもしれない。誰かがいくつかのビット演算トリックを実装するのに時間を費やしたというだけで、そうなるのだ
  • なぜそうなるのか分からない。その法則はソフトウェア性能改善には大した意味がない、という方向の話に見えるが、この記事はPostgresの改善が相当なものだったという内容だ
    15%を低い数値だと見ているからだろうか。この文脈ではまったく低くない。リンク先の法則の60%より小さく、15/10のように割ればさらに小さいだろうが、Postgresの性能をハードウェアの向上と比較すべきではない。ここで測定している対象で1%の性能向上に匹敵するには、途方もないハードウェア改善が必要だ
    その法則が他の人たちが言うほど馬鹿げているとは思わないが、これはプログラミング言語のコンパイル時間に関する話だ。そのような相対的に重要でないものを、コンピュータサイエンスで最も重要なものの一つと言えるデータの保存と消費とは比較しない
  • このケースでは、研究者はすべてのPostgreSQLバージョンを同じGCC 13.2でビルドし、同じOS上でテストしている
  • かなり弱い「法則」に見える。冗談で作られたものなのだろうか。根拠は出どころの分からない数字や「仮定してみよう」程度のもので、結論も大きく外れている。世界中の多くのソフトウェアの性能を毎年4%ずつ改善する最適化が時間の無駄だ、と示唆しているように見える
    比較対象としてはMurphyの法則だけが提示されている。より高速なハードウェアを開発するコストと、コンパイラを継続的に改善するコストにどの程度の差があるのか気になる。投資収益率を、性能向上1%あたりのドルといった形で比較した場合によっては、この「法則」にある程度の重みが出るかもしれない
    一方でこのPostgresの記事は、最適化における収穫逓減を示しているように見え、これは毎年の利益が一定だと仮定するその「法則」の前提に反論している。同時に、長期的には最適化が悪い投資だというProebstingの示唆を裏付けるものにもなり得る

• この分析は少し混乱する。グラフでは見えない低下傾向を、データからどう確認したのか分からない
  中央値は初期の数バージョンで少し下がったあと、最近の数バージョンではまた上がっているように見える。R²が非常に低く、相関関係に説得力を感じない。基本的にはテールレイテンシは改善され、残りは環境次第という程度に見える

  • ブログ記事の著者です
    「テールレイテンシは改善され、残りは環境次第」という解釈は妥当だが、保守的な読み方だと思う。もちろん多くの、もしかすると大半のアプリケーションでテールレイテンシは非常に重要である。また、テールレイテンシはオプティマイザのエンジニアたちが主に狙う対象、つまり最も時間のかかるクエリの実行時間を短縮する対象でもある

• クエリ最適化とはどのようなものなのか？ SQL レベルで最適化するのか、アルゴリズムレベルで最適化するのかが気になる

  • PostgreSQL は除くとして、私が使ったことのあるデータベースでは、最適化のほとんどはアルゴリズムレベルで行われる。つまり、特定のクエリに使う最適なアルゴリズムと実行順序を選ぶということ
    複数の異なる SQL クエリが同じ「命令」または実行計画に変換されることがあり、SQL の意味論自体には言語レベルの最適化を行う余地があまりないためだと思われる
    他の返信で述べられているように、重要な判断の一つは、全テーブルスキャンをインデックス参照やインデックススキャンに置き換えられるかどうかである
    例えば、全テーブルスキャンが必要で、各行について結果セットに含めるかを決めるためにかなりの計算が必要な場合、オプティマイザは全テーブルスキャンを並列テーブルスキャンに変更し、各並列タスクの結果をマージできる
    コンパイラ向けに高性能なコードを書くときは、コンパイラのオプティマイザがソースコードを機械語にどう変換するかを知っておく必要がある。そうすれば、オプティマイザがうまく処理できるコードを優先し、より遅い機械語を出力するパターンを避けられる。結局のところ、オプティマイザは特定のパターンを検出して変換するようにプログラムされている
    クエリオプティマイザと実行計画も同じである。使っているデータベースのクエリオプティマイザが、どのようなパターンを処理して効率的な実行計画を作れるのかを学ぶ必要がある
  • SQL を実行できるあらゆる方法を記述したうえで、より速い計画を選ぶ。例えば user_id が xx のユーザー行を探すなら、テーブル全体を読んでフィルタするのか、それとも専用のデータ構造を使うのかを選ぶ、といった具合
    インデックスを使えば、行数に対して対数時間で見つけられる。このほかにも、結合順序の選択、結合戦略の選択、フィルタ条件を元のデータソース側へ押し込むことなど、多くのことが可能である。これが SQL 最適化の広い領域である
  • 非常に高いレベルで見ると、クエリプランナの目的は、ディスクからデータを読むコストを最小化することにある。行数や一意な値の数といった、事前に計算されたカラム統計を集め、クエリが一致する行数を推定する
    この情報を使って、結合順序を決めたり、インデックスを選んだりする。結合はハッシュ、ループ、マージなど複数のアルゴリズムで実行できる。最も安い選択肢は、片方が作業メモリに収まるか、両方がすでにソート済みか、例えばインデックススキャンのおかげか、といった要素によって変わる
  • クエリ最適化とは、SQL が要求した結果を提供するアルゴリズムを選ぶ作業である

• サイトが落ちているようなので、代わりにこちらを見られる: https://web.archive.org/web/20240417050840/https://rmarcus.i...