HN 日本語サマリー

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

Postgres SELECT DISTINCT Does Not Scale

Postgres SELECT DISTINCT Does Not Scale (dbos.dev)

106 pointsby KraftyOne28 コメント

要約

PostgreSQLのSELECT DISTINCT句は、一見シンプルで効率的であるかのように見えますが、実際にはテーブルの行数に比例してパフォーマンスが低下し、スケーラビリティに問題があることが判明しました。この記事では、その原因と、再帰CTEを用いた代替クエリによる回避策を解説しています。

全文翻訳

PostgresのSELECT DISTINCTはスケールしない

最近、Postgresのスケーリング方法や、あらゆる用途にPostgresを使うべき理由について、多くの人気ブログ記事が出ています。この記事では、少し趣向を変えて、直感的にはスケールするはずのPostgresの機能で発生した問題について説明します。実際には、それはスケールしません。

SELECT DISTINCTは、列のユニークな値すべてを見つける、無害に見える句です。しかし、そのパフォーマンス特性は期待とは異なります。テーブルにどのようなインデックスを張っても、取得すべきユニークな値がどれだけ少なくても、SELECT DISTINCTは常に述語に一致するすべての行をスキャンします。私たちは最近、Postgresベースのキューワークロードのパフォーマンスを診断している際に、これを観察しました。その際、SELECT DISTINCTは最もシンプルで安価に見えるにもかかわらず、最もコストのかかるクエリであることが判明しました。この記事では、何が起こったのか、Postgresのどのような設計上の決定がSELECT DISTINCTを遅くしているのか、そしてその回避策を説明します。

SELECT DISTINCTによるユニークパーティションの発見

私たちは、Postgresベースのパーティション化されたキューワークロードでスローダウンを観察しました。各キューはパーティション(例えば、ユーザーごとに1つ)に分割されており、これにより各パーティションに個別にフロー制御を適用できます(例えば、各ユーザーが一度に最大1つのタスクを実行できるようにする)。パーティション化されたキューからデキューするワークフローの最初のステップは、「アクティブ」なパーティション、つまり、それらにENQUEUED状態のワークフローを持つパーティションをすべて見つけることです。私たちは当初、これを実行するためにSELECT DISTINCTを使用していました。

[画像: SQLコード: 特定のキューでENQUEUED状態のワークフローのうち、NULLでないパーティションキーを除外した、dbos.workflow_statusからqueue_partition_keyのDISTINCT値を選択]

SELECT DISTINCTが行うのは、ある条件が与えられた場合に、列のユニークな値すべてを見つけることです。したがって、このクエリは、特定のキュー上のENQUEUED状態のワークフローの中で、ユニークな非NULLパーティションキーをすべて見つけます。私たちは、キュー名、ワークフローの状態、およびパーティションキーにインデックスが適切に張られているため、このクエリが高速に実行されると期待していました。

[画像: SQLコード: dbos.workflow_statusテーブルに対する部分インデックス。キュー名、ステータス、およびパーティションキーでフィルタリングされ、ENQUEUEDまたはPENDING状態の行で、パーティションキーがNULLでないもの]

直感的には、インデックスはこのようになります。ワークフローは、まずキュー名、次にステータス、そしてパーティションキーのツリー構造で配置されます。これにより、Postgresは3つのフィールドすべてを使用してワークフローを効率的に特定できます。

[画像: Postgres SELECT DISTINCTクエリプランの図]

インデックスがこの形状をしているため、このクエリのパフォーマンスはアクティブなパーティションの数に比例する(O(number of active partitions))と予想していました。結局のところ、このクエリを満たすためにPostgresは各ユニークパーティションから1行だけを検索し、見つかったパーティションキーを返すだけでよいはずです。

当初は意図した通りに機能しているように見えました。私たちのキューワークロードのほとんどは、「幅広く浅い」(多くのパーティションを持つが、パーティションあたりのエンキューされたワークフローは少ない)ものでした。それらの場合、クエリは期待通りに実行されました。しかし、すぐに「狭く深い」(パーティションは少ないが、それぞれに多くのエンキューされたワークフローが含まれている)ワークロードで問題に遭遇しました。パーティションは非常に少なかったため、クエリは1ミリ秒未満で完了すると予想していましたが、実際には数秒かかりました。このことから、クエリはアクティブなパーティションの数ではなく、エンキューされたワークフローの総数に比例してスケールしており、許容できないほど遅いことがすぐにわかりました。

私たちは、パーティション数を10に固定し、パーティションあたりの行数を100から1Mまでスケーリングして、ベンチマークでこの観測を検証しました。ご覧のとおり、クエリのレイテンシはパーティションあたりの行数に比例してスケールします。

[画像: Postgres SELECT DISTINCTパフォーマンスベンチマーク]

なぜそのようなことが起こり、どのように修正するかを理解するために、Postgresがこのクエリをどのように計画し、実行するかを調べる必要があります。

SELECT DISTINCTクエリプラン

SELECT DISTINCTクエリに使用されているPostgresのクエリプランを調べたところ、次のようになりました(ここでは3つのパーティションにわたる100万件のエンキューされたワークフローを想定しています)。

[画像: クエリプランの図: リーダーと2つのワーカーがそれぞれ約333,333タプルに対して並列インデックスオンリースキャンを実行し、合計1,000,000件のインデックスタプルをスキャンした後、Gather MergeとUniqueで3つのテナントキーのみを返している]

本質的に、Postgresはフルインデックススキャンを実行しています。つまり、インデックスを走査して、特定のキュー上のエンキューされたワークフロー(この例では合計100万行)をすべて取得し、ユニークなパーティションキーが含まれているかどうかを確認しています。これが、私たちが観測したパフォーマンスを説明しています。実行時間がエンキューされたワークフローの総数に比例する理由は、Postgresが実際にエンキューされたワークフローをすべてスキャンしているからです。これは非常に無駄です。この例では、Postgresは100万行をスキャンして、インデックスから直接取得できたはずのわずか3つのパーティションキーを見つけました。

Postgresのクエリプランナーがこのプランを選択するのは、代替手段がないためです。Postgresでインデックスをスキャンするために実装されているすべての演算子は、フルインデックススキャンを実行し、述語に一致するすべてのインデックス値を返します。他のリレーショナルデータベースはより優れています。MySQLは、述語を満たすユニークな値のみを取得する「ルーズインデックススキャン」演算子を提供しています。

興味深いことに、Postgres 18では、ルーズスキャンに似たものが追加されました。それはスキップスキャン最適化で、多列インデックスの左端以外の列を検索する際に、行を「スキップ」します。しかし、この場合でも述語に一致するすべての行をスキャンするため、SELECT DISTINCTの高速化には使用できません。別途、2018年にはルーズインデックススキャンの追加に向けた重要な試みがありましたが、4年間の努力とメンテナーの交代を経て断念されました。

スローダウンの軽減策

SELECT DISTINCTのパフォーマンスは、テーブルのサイズに比例してスケールし、含まれるユニークな値の数には比例しないため、大規模な環境では使用できません。テーブル内のユニークな値の数を効率的に数えるには、代わりに回避策が必要です。それは、Postgresに効率的なクエリプランを生成させる、より複雑なクエリです。

[画像: SQLコード: 最小のパーティションキーを見つけ、次に前のキーよりも大きい最小のキーを繰り返し選択し、何も残らなくなるまで続ける再帰CTE]

このクエリは、再帰的な共通テーブル式(CTE)を利用しているため、非常に読みにくいです。大まかに言うと、これは宣言的なSQLの中で命令型コードを書く方法です。本質的に、このクエリはループとして評価され、最初のイテレーションで「最小」のパーティションキーを見つけ、後続の各イテレーションでそれ以降の「次の」ユニークなパーティションキーを見つけます。その様子は次のとおりです。

[画像: 再帰CTEループの図: 各イテレーションは、ソートされたインデックスに対してmin()を選択し、最後のキーよりも大きい最小値を取得します。リーフページでtenant_aからtenant_b、tenant_cへとジャンプし、NULLで停止します]

各ループイテレーションはソートされたインデックスに対してSELECT min()を実行するため、インデックス全体をスキャンするのではなく、単一の値のみを取得します。したがって、各ループイテレーションは固定の作業を行い、ループイテレーションの総数はユニークなパーティションの数に等しいため、このクエリは必要なO(パーティション数)のパフォーマンスを提供します。

このパフォーマンスを検証するために、新しいクエリのベンチマークを取りました。パーティション数を10に固定し、パーティションあたりの行数を1Kから1Mまで変化させました。ご覧のとおり、パーティションがどれだけ大きくなっても、中央値レイテンシは変化しません。

[画像: 折れ線グラフ、対数スケール: パーティションあたりの行数が100から1Mに増加しても、再帰CTEの中央値クエリレイテンシは約1ミリ秒で一定]

さらに詳しく

スケーラブルで信頼性の高いシステムを構築することに興味があるなら、ぜひお話を聞かせてください。DBOSでは、Postgresベースの耐久性のある実行を可能な限りシンプルかつ高性能にすることを目指しています。ぜひご覧ください。