- PostgreSQL 16 はクエリプランナー/オプティマイザに 10 の改善を追加し、
DISTINCT、集約、結合、ウィンドウ関数、パーティションテーブルクエリにおける実行計画の選択肢を広げた
SELECT DISTINCT、ORDER BY/DISTINCT 集約、Merge Join 後の処理で 部分的にソート済みの入力 をより積極的に活用し、全体ソートより少ないメモリで結果を生成できるUNION ALL 内部の Memoize、Right Anti Join、FULL/RIGHT 結合での並列ハッシュ結合のサポートは、反復参照と大きなハッシュテーブル生成コストの削減に重点を置いている- ウィンドウ関数では不要な
RANGE 処理や最後まで実行する必要のある WindowAgg を減らし、一部の関数では条件に応じて 早期停止 が可能になった
- すべての改善はデフォルトで有効になっているため、PostgreSQL 16 へのアップグレード前後で実際のワークロードの
EXPLAIN と実行時間を比較してみる価値がある
PostgreSQL 16 プランナー改善の範囲
- PostgreSQL 16 はクエリプランナーに複数の改善を導入し、多くの SQL クエリを従来の PostgreSQL バージョンより高速に実行できるようにした
- PG16 リリースノート に含まれるプランナー改善をより詳しく解説し、PG15 と PG16 の
EXPLAIN 出力比較と再現可能なテスト例をあわせて扱う
- ここでいうプランナーは、他のリレーショナルデータベースで一般に オプティマイザ と呼ばれるコンポーネントである
ソートと DISTINCT の最適化
-
SELECT DISTINCT での Incremental Sort 利用
- Incremental Sort は PostgreSQL 13 で初めて追加され、結果が先行カラムを基準にすでにソート済みの場合、残りのカラムだけをソートしてコストを下げる
- PostgreSQL 16 プランナーは
SELECT DISTINCT クエリでも Incremental Sort を考慮する
- たとえば
a カラムに btree インデックスがあり、a, b の順序が必要な場合、インデックスで a 基準のソート結果を得たあと、a の値が変わるたびに b だけをソートできる
- PostgreSQL の quicksort では、大きな 1 グループをソートするより小さな複数グループをソートするほうが効率的な場合がある
- 例のクエリでは PG15 は
HashAggregate とシーケンシャルスキャンを使い、PG16 は distinct_test_a_idx インデックスと Incremental Sort を選択した
- PG16 出力の
Presorted Key: a は、a を基準にすでにソート済みの入力を活用したことを意味する
- PG15 のハッシュ方式は約 30MB をディスクにスピルしたが、PG16 の
Incremental Sort の最大メモリは 26KB だった
- 実行時間は PG15 の 414.226ms から PG16 の 263.167ms に短縮された
-
ORDER BY または DISTINCT を含む集約の最適化
- PostgreSQL 15 以前では、
ORDER BY や DISTINCT 句を含む集約関数は常に Aggregate ノード内部でソートを実行していた
- PostgreSQL 16 プランナーは
Aggregate ノードに正しい順序の行を供給する実行計画を作成でき、実行器は入力がすでにソート済みなら内部ソートを省略する
COUNT(DISTINCT b) の例では PG15 と PG16 の両方が GroupAggregate と Index Only Scan を使うが、PG15 の出力には temp read=4540 written=4560 が現れる- この一時ファイル I/O は、PG15 の暗黙的なソートがディスクにスピルした結果である
- PG16 の出力にはその一時 I/O がなく、実行時間は PG15 の 302.693ms から PG16 の 115.534ms へと 2 倍以上高速化した
反復参照と結合計画の改善
-
UNION ALL 内部への Memoize 適用
Memoize プランノードは PostgreSQL 14 で初めて導入され、パラメータ化された Nested Loop と内部入力の間で キャッシュ層 のように動作する- PostgreSQL 16 プランナーは、パラメータ化された
Nested Loop の内部に UNION ALL クエリがある場合でも Memoize の利用を考慮する
- 例では PG15 は
Append を 100 万回実行したが、PG16 は Append の上に Memoize を配置した
- PG16 の
Memoize は Hits: 999990、Misses: 10、Memory Usage: 2kB を記録した
Append の実行回数は PG15 の 100 万回から PG16 の 10 回に減少した- 実行時間は PG15 の 1926.151ms から PG16 の 282.120ms へと約 6 倍高速化した
-
Right Anti Join のサポート
INNER JOIN の Hash Join では、通常はより小さいテーブルにハッシュテーブルを作るほうが有利である- 小さいハッシュテーブルは生成作業が少なく、CPU キャッシュに優しく、メインメモリからデータを待つ CPU stall の可能性も低い
- PostgreSQL 16 より前の
Anti Join は、NOT EXISTS で言及されたテーブルを常に結合の内部側に置いていたため、より大きいテーブルにハッシュテーブルを作らなければならないことがあった
- PostgreSQL 16 は Right Anti Join をサポートし、2 つのテーブルのうちより小さい側をハッシュ化できるようにした
- 例では PG15 は 100 万行の
large テーブルをハッシュし、メモリ使用量は 6446KB だったが、PG16 は 100 行の small テーブルをハッシュして 12KB しか使わなかった
- 実行時間は PG15 の 139.023ms から PG16 の 77.076ms へとほぼ半減した
-
FULL/RIGHT 結合の並列ハッシュ結合
- PostgreSQL 11 は、複数の並列ワーカーが単一のハッシュテーブル生成に参加する
Parallel Hash Join を導入した
- PostgreSQL 16 の
Parallel Hash Join は FULL と RIGHT の結合タイプをサポートする
FULL OUTER JOIN と Right Join の計画も並列実行できるFULL JOIN の例で、PG15 は単一の Hash Full Join を使ったが、PG16 は Parallel Hash Full Join と Gather を使った- PG16 の出力には
Workers Planned: 1、Workers Launched: 1 が現れる
- 実行時間は PG15 の 220.677ms から PG16 の 129.769ms に大きく短縮された
ウィンドウ関数の最適化
-
不要な RANGE 処理の省略
row_number(), rank(), dense_rank(), percent_rank(), cume_dist(), ntile() のようなウィンドウ関数では、ウィンドウ句に ROWS オプションがないと PostgreSQL はデフォルトの RANGE オプションを使うRANGE オプションは、同じソート値を持つ peer row を探すために前方の行を確認する必要があり、ORDER BY 基準で同じ値が多いとコストが高くなりうる- これらの関数は
ROWS と RANGE の指定有無で動作が変わらないが、PostgreSQL 16 以前の実行器はこれを区別できず、すべての場合で peer row の検査を行う必要があった
- PostgreSQL 16 プランナーは、どのウィンドウ関数が
ROWS/RANGE オプションの影響を受けるかを把握し、実行器が不要な処理をスキップできるよう情報を渡す
row_number() <= 10 の例で、PG15 はインデックスから 50,410 行を読んでから停止したが、PG16 は 11 行しか読まなかった- PG16 は
row_number が 11 に達した時点で、<= 10 条件を満たす行がもう存在しないことを活用する
- 実行時間は PG15 の 29.775ms から PG16 の 0.058ms へと 500 倍以上高速化した
-
単調増加するウィンドウ関数での早期停止拡大
- PostgreSQL 15 は、
WHERE 句の条件が特定のウィンドウ関数に対して一度 false になると再び true になりえない場合、WindowAgg の実行を早めに止められるようにした
- PostgreSQL 16 はこの最適化の対象を
ntile(), cume_dist(), percent_rank() にまで拡張した
- PostgreSQL 15 では
row_number(), rank(), dense_rank(), count(), count(*) にしか適用されなかった
percent_rank() <= 0.01 の例では、PG15 は条件をサブクエリの Filter として処理し、WindowAgg は 50,000 行すべてを処理した- PG16 は同じ条件を
Run Condition として使い、WindowAgg の実行を早期に停止した
- 実行時間は PG15 の 84.358ms から PG16 の 19.454ms へと 4 倍以上高速化した
パーティションテーブルと自明な DISTINCT 処理
-
パーティションテーブルの LEFT JOIN 除去
- PostgreSQL は以前から、クエリに不要で行の重複可能性もない
LEFT JOIN を除去できた
- PostgreSQL 16 以前では、パーティションテーブルに対する LEFT JOIN 除去 はサポートされていなかった
- 内部側の行が外部側の行を重複させる可能性がないことを判断するために必要な証明が、パーティションテーブルにはなかったためである
- PostgreSQL 16 プランナーは、パーティションテーブルにも
LEFT JOIN 除去の最適化を適用する
- この最適化は特にビューで有用になりうる
- ビューには多くのカラムがあっても、実際のクエリですべてのカラムを常に参照するとは限らないためである
- 例では PG15 の計画は
part_tab への結合を含むが、PG16 の計画は normal_table のシーケンシャルスキャンだけを実行する
-
結果が 1 つに確定する DISTINCT を Limit で処理
- PostgreSQL プランナーは、すべての行が同じ値を持つことを検出できれば、結果の重複除去用プランノードを省略できる
- PostgreSQL 16 は、
DISTINCT 対象カラムがすべて WHERE 句の等価条件で固定されている場合、結果に同じ値しか含まれないことを利用して LIMIT 1 で処理する
- 例のクエリ
SELECT DISTINCT a,b,c FROM abc WHERE a = 5 AND b = 5 AND c = 5 では、各 DISTINCT カラムが同じ値に制限されている
- PG15 は結果全体を読み込み、
Unique 演算子で 1 行に絞った
- PG16 は
Limit とシーケンシャルスキャンを使って 1 行だけ返す
- 実行時間は PG15 の 30.381ms から PG16 の 0.025ms へと 1200 倍以上高速化した
Merge Join 後の Incremental Sort 活用拡大
- PostgreSQL 16 以前のプランナーは
Merge Join を考慮する際、結合のソート順が上位の DISTINCT、GROUP BY、ORDER BY 処理の要件と正確に一致する場合にのみその順序を使っていた
- このルールは、
Incremental Sort が上位処理で部分的にソート済みの入力を活用できることを十分に反映していなかった
- PostgreSQL 16 は
Merge Join の順序を考慮するルールを、「正確に一致している必要がある」から「先行カラムのうち少なくとも 1 つが正しくソートされていればよい」へと緩和した
- この変更により、プランナーは
Merge Join の結果を上位処理に合わせるために Incremental Sort をより頻繁に使えるようになった
- Incremental Sort は部分的にソート済みの入力を活用して小さなバッチ単位でソートするため、全体ソートよりメモリ使用量と比較回数を減らせる
- 例では PG15 は
Merge Join の後に全体 Sort を使ったが、PG16 は Incremental Sort を使った
- PG16 の
Incremental Sort の最大メモリは 26KB だった
- 実行時間は PG15 の 1010.738ms から PG16 の 915.589ms へとわずかに短縮され、ソートに使うメモリは大幅に減少した
適用方法と実務での確認
- PostgreSQL 16 の 10 のプランナー改善はすべて デフォルトで有効 になっている
- 各最適化は、可能なすべてのケースに適用されるか、あるいはプランナーが有効だと判断した場合に選択的に適用される
- 既存の PostgreSQL バージョンを使用しているなら、PostgreSQL 16 で実際のワークロードを実行し、どのクエリが高速化するか確認できる
- 実際の利用フィードバックは pgsql-general@postgresql.org メーリングリストで共有できる
1件のコメント
Hacker Newsのコメント
PostgreSQLのクエリプランナーが、実行途中でクエリを再計画できるようになると本当に良さそう
病的に遅いクエリは、プランナーがデータ分布について必要な情報を知らず、コストを誤って見積もることで起きる場合が多く、実行時間が1msではなく1秒になるような1000倍の差も簡単に出る
テーブル統計が100%正確になることはないので、クエリ開始後に進行速度が想定より遅ければ、スキャン済みページ数やマッチしたタプル数のような現在の進捗情報をプランナーに戻して、新しいプランを作れると良さそう
ただしPostgreSQLは結果を最後まで作ってから送るのではなくストリーミングで送るため、途中でプランを変えるには、すでにクライアントへ送った結果を追跡する必要があり、インフラ変更が大きい
さらにクライアントがクエリ途中で方向を反転し、以前の結果を逆順で再要求することもあり得るので、複雑さはさらに増す
新しいプランが同じタプルを返す保証すらないから。たとえば
SELECT * FROM table LIMIT 10のようにORDER BYがなければ、どのタプルが出るかは非決定的むしろX個のタプルをキューにためておき、キューが満杯になった時点で送信を始める方式のほうが簡単かもしれない。キューが満杯になった後は、再計画には遅すぎると見なして現在のプランに固定する形
ユーザーはXを調整することで、より多くのメモリと最初のタプルまでの遅延を受け入れる代わりに、プラン変更可能な時間を伸ばせる
新しいクエリは単に先頭のN件をスキップできず、すでに送った各行と照合する必要がある
クエリの可視化にはこのツールを使っている: https://explain.dalibo.com/
https://www.pgexplain.dev/ もあり、以前は出力がやや劣っていたが、今はどちらも同じくらいに見える
こうした状況で役立つ実行計画のサニタイズツールがあるのか気になる
クエリプランナーの改善はいつでも歓迎だし、データベースにおいて非常に重要な部分。もちろん通常は、自分の望みどおりにならないときに一番目立つ
個人的にかなりもどかしかったのは、最近のPostgreSQLのJIT。いつ使うかを決めるヒューリスティックがまったく堅牢に見えない
典型的なORM生成クエリで見かけたのだが、クエリ自体は単純でも、JOINで多くのテーブルを引っ張ってくる。JITなしなら数ミリ秒で終わるのに、JITが追加で1〜1.5秒を使い、小さなデータでも非常に遅くなる
今ではJITを単にオフにすればよいと分かっているが、なぜ遅いのかまだ把握できていないユーザーにとっては、PostgreSQLへの印象を大きく損ねかねない。PostgreSQLは好きだが、JITをデフォルトでオンにしておくのは危険すぎるように見える
PG16ではプランの推定総コストだけを見ており、コンパイルすべき式の数は考慮していない
式をいくつかコンパイルするのは速いが、数百個のパーティションを持つパーティションテーブルを検索し、そのパーティションがすべてプランに含まれると、JITコンパイラの作業量は多くなる
同僚と一緒にこれを改善するコードは持っているが、現時点でPG17に入るかは確実ではない
PostgreSQLメーリングリストのJIT関連の議論を探しても、納得できる理由は見つからなかった
OLTPワークロードではJITを切るのが正しい
ORMを使っていないので、単におかしなクエリパターンのせいというわけでもない
一方でクエリ並列化は実際に有用なことがあり、何より害を及ぼすことがまれ
aptでいくつかのパッケージを更新したところ、5分ごとに走らせている大きなクエリが突然失敗し始めた。正確には、PostgreSQLがクエリ実行中にログも残さず、接続を静かに切ってしまう手動で
EXPLAINを実行して確認したところ、JITを使うようになったクエリの変形だけが壊れ、使わないほうは問題なかった。JITをオフにすると再び正常に戻ったこうした変更が実際のクエリでどれくらい頻繁に効果を発揮するのか気になる。特に「可能な場合、
DISTINCTの実装にUniqueではなくLimitを使う」という変更は、かなり愚かなクエリにしか適用されないように感じるPostgreSQL 開発者たちに、それを判断するための情報源があるのか気になる
DISTINCT の改善によって悪いクエリに対してより堅牢になるなら、得るものは大きい。すべての問題を直せるわけではないだろうが、どんな改善でも歓迎だ
pgsql-hackersメーリングリストで出てきたものだ頻繁に適用される可能性は低いという点には同意するが、良いところは、適用可能かどうかの検出がポインタが
NULLかどうかを確認するのと同じくらい単純だったことだ検出は非常に簡単で、ほとんどの場合は適用されないだろうが、適用できる場合にはかなりの性能向上をもたらし得る
ごく一般的な問題ではないだろうが、ときどき現れても驚かない
select distinct email from users where email = ?クエリを実行していた同じメールアドレスを持つ行が 100 件を超えることはなかったと思う。大半は削除してもよかったテストユーザーだったが、話が少しそれた
PostgreSQL にアプリのテスト用の厳格モードがあるといい。クエリ自体だけを見て、統計情報とは無関係に、インデックスがあれば漸近的にクエリが改善されるのにそのインデックスがなければエラーを返すモードだ
アプリのアップグレード用にそのインデックスを作る
CREATE INDICES FORコマンドもあるとよく、対話的・開発用に自動インデックス生成モードもほしい全体として、システムは漸近的に非最適な実行が決して起こらないよう設計されるべきだ
なぜヒントを実装しないのかわからない
pg_hint_plan拡張がある。ヒントのリスクは、書いた時点では正しくても、テーブルサイズやデータの偏りが変わると、かえって悪くなり得ることだ以前ヒントの議論を見たときは、プランナーを過度に縛らず、基礎データの変化に適応できる方式であれば、一般的な反対はなかったと記憶している
たとえば、特定の述語が 10 行に一致すると指定する代わりに、2 つのカラムの間に相関があると知らせるようなものだ
https://news.ycombinator.com/item?id=2179433（コメント 60 件、2011 年）
PostgreSQL Wiki の公式見解は https://wiki.postgresql.org/wiki/OptimizerHintsDiscussion にある
「ほかのデータベースでよく実装されている厳密な形のヒントには関心がない」という立場だ
既存のヒントシステムの問題としては、アプリケーションコードの保守性低下、アップグレードの妨げ、悪い DBA 習慣の助長、データサイズの拡大に合わないことが挙げられている
その立場を責めたいわけではないが、PostgreSQL が愚かなプランを選んでしまい、合理的な選択をするよう説得できないときはもどかしい
中堅企業向けの Microsoft DBA をしている友人が、PostgreSQL では本格的な仕事はできないと言っていた。PostgreSQL にはクエリプランナーすらないと知って衝撃を受けた、とまで言っていた
嘲笑はひとまず置いておくとして、MSSQL は PostgreSQL が不向きな規模を扱える、というより大きな主張にもっともらしさがあるのか気になる。直感的にはあり得ないと思うが、私は DBA ではまったくない
これらはお金とハードウェア、つまりさらに多くのお金を投入して、問題が解決するまで押し切るやり方で対処してきた。もちろん賢い技術も入っているが、根本的には長い期間にわたり、はるかに多くのエンジニアリングが注ぎ込まれてきた
PostgreSQL が合理的にできる範囲よりも大きく水平スケールできる
ただし PostgreSQL も追いつきつつあり、MySQL/MariaDB はこの方面の話はもともと悪くなかったとも言える。水平スケールの選択肢はどんどん良くなっている
今では少数のマシンでマルチテラバイトの PostgreSQL クラスターを運用して大きなトラフィックを処理し、「ビッグデータ」はより特化したデータベースに入れることも容易になった。すべてを MSSQL/Oracle に押し込んでいた昔のやり方は、少し時代遅れかもしれない
友人が言っていたのは、PostgreSQL にはクエリプランをキャッシュしたり固定したりする方法がないという事実かもしれない。PostgreSQL は手動で prepared statement を使わない限り文ごとに再プランニングし、それも接続ごとにしか機能しない
MSSQL はかなり昔からプランをキャッシュして再利用してきたので、プランナーはプラン作成により多くの時間を使える。またヒントがあり、プランを固定することもできる
PostgreSQL には本当にヒントが必要だ。オプティマイザが優秀でも、時には自分のほうがよく分かっていて、自分の指示を聞かせたいことがある
さらに PostgreSQL には真のクラスタ化インデックスがなく、すべてのテーブルがヒープだ。MSSQL ではたいてい頻繁に使われ、通常は主キーをクラスタ化インデックスに設定するので、テーブル自体がインデックスになり、キー検索に間接参照がない
興味深いことに SQLite は逆で、テーブルは作るかどうかにかかわらず常にクラスタ化インデックスを持ち、MSSQL はヒープとインデックス構成テーブルのどちらかを選べるようにしている
非常に大きな PostgreSQL データベースでもうまく動いている事例はあるので、PostgreSQL も確実にスケール可能だ
ただし SQL Server には PostgreSQL にない機能もあり、それらが重要なら特定のユースケースにはより合うかもしれない。結局のところ、互いに異なる強みと弱みを持つ別のデータベースだ
最初は、SQL Server が必要なベンダー提供アプリケーションさえなければ、会社に PostgreSQL への移行を勧めていただろう、と書こうとしていた
ところが Microsoft が含めている reporting services、integration services、ジョブ、AD 統合、service broker のようなものを置き換えるのがどれほど大変かに気づいた。
notify/listenにはメッセージタイプがないanalysis services はもう使っていないが、以前使っていたときはそれも置き換えるのは難しかったはずだ
こうしたものが人を引き留める。これらすべてを置き換えるのにどれだけかかるか見当もつかず、すでに持っているものを置き換えるために1年を費やすのは投資対効果が良くない
なぜこの内容が postgresql.org ではなく citusdata で公開されたのか気になる。有料機能専用なのか、オープンソースへの追加なのか分からない
IS NOT DISTINCT FROMクエリを速くするためにインデックスを使えるようになるのは、いつ頃だろう ;)