Postgres SELECT DISTINCT Does Not Scale

最近、Postgresがどのようにスケーリングするか、あるいはなぜあらゆるものにPostgresを使うべきかについて、人気のブログ記事が数多く登場しています。この記事では、少し違ったアプローチを取ります。直感的にはスケーリングするはずなのに、実際にはそうではないPostgresの機能に関する問題を説明します。 SELECT DISTINCTは、列のすべてのユニークな値を見つける、無害に見える句です。しかし、そのパフォーマンス特性は期待どおりではありません。テーブルにどのようなインデックスを張っても、取得すべきユニークな値がどれだけ少なくても、SELECT DISTINCTは常にその述語に一致するすべての行をスキャンします。最近、Postgresベースのキューワークロードのパフォーマンスを診断した際に、この問題に遭遇しました。SELECT DISTINCTが、最もシンプルで安価に見えるにもかかわらず、最もコストのかかるクエリであることが判明したのです。この記事では、何が起こったのか、Postgresのどのような設計上の決定がSELECT DISTINCTを遅くしているのか、そしてそれを回避する方法を説明します。 SELECT DISTINCTによるユニークパーティションの検索 この遅延は、Postgresベースのパーティション化されたキューワークロードで観測されました。各キューはパーティション（例えば、ユーザーごと）に分割されており、これにより各パーティションに独立してフロー制御を適用できます（例えば、各ユーザーが一度に最大1つのタスクを実行できるようにします）。パーティション化されたキューからワークフローをデキューする最初のステップは、「アクティブ」なパーティション、つまりエンキューされたワークフローがあるパーティションをすべて見つけることです。当初、私たちはこれにSELECT DISTINCTを使用していました。 SELECT DISTINCTが行うことは、ある条件が与えられた場合に、列のすべてのユニークな値を見つけることです。したがって、このクエリは、特定のキュー上のエンキューされたワークフローの中で、NULLでないユニークなパーティションキーをすべて見つけます。私たちは、キュー名、ワークフローの状態、パーティションキーにインデックスが張られているため、このクエリは高速になると予想していました。 直感的には、インデックスはこのようになります。ワークフローは、まずキュー名、次に状態、そしてパーティションキーのツリー構造で配置されます。これにより、Postgresは3つのフィールドすべてを使用してワークフローを効率的に見つけることができます。 インデックスがこの形状をしているため、このクエリのパフォーマンスはアクティブなパーティションの数に比例する（O(number of active partitions)）と予想していました。結局のところ、このクエリを満たすために、Postgresは各ユニークパーティションから1つの行を検索し、見つかったパーティションキーを返すだけでよいのです。 当初は意図したとおりに機能しているように見えました。私たちのキューワークロードのほとんどは「幅広く浅い」もので、多くのパーティションがありましたが、パーティションあたりのエンキューされたワークフローは少数でした。それらの場合、クエリは期待どおりに実行されました。しかし、すぐに「狭く深い」ワークロード、つまりパーティションは少ないが、それぞれに多くのエンキューされたワークフローが含まれているワークロードで問題に遭遇しました。パーティションが非常に少ないため、クエリは1ミリ秒未満で完了すると予想していましたが、実際には数秒かかりました。これは、クエリがアクティブなパーティションの数ではなく、エンキューされたワークフローの総数に比例してスケーリングしていることを意味し、許容できないほど遅いことがすぐにわかりました。 パーティション数を10に固定し、パーティションあたりの行数を100から1Mにスケーリングしてベンチマークを行い、この観測を検証しました。ご覧のとおり、クエリのレイテンシはパーティションあたりの行数に比例してスケーリングします。 なぜそれが起こっているのか、そしてそれをどのように修正するのかを理解するために、Postgresがこのクエリをどのように計画し、実行するかを調べる必要があります。 SELECT DISTINCTクエリの実行計画 PostgresがSELECT DISTINCTクエリに使用していた実行計画を調べたところ、次のようになりました（3つのパーティションにわたる1Mのエンキューされたワークフローを想定）： essentially, Postgres is doing a full index scan: walking the index to retrieve every single enqueued workflow on a particular queue (in this case, 1M rows total) and checking if it contains a unique partition key. This explains the performance we saw: the reason run time scales with the total number of enqueued workflows is because Postgres is actually scanning every single enqueued workflow. This is supremely wasteful: in this example Postgres scanned 1M rows to find just three partition keys it could have directly retrieved from the index. Postgresのクエリオプティマイザは、代替手段がないため、この計画を選択します。Postgresでインデックスをスキャンするために実装されているすべてのオペレータは、フルインデックススキャンを実行し、述語に一致するすべてのインデックス値を返します。他のリレーショナルデータベースはより優れています。MySQLは「ルーズインデックススキャン」オペレータを提供しており、述語を満たす各ユニークな値のみを取得します。興味深いことに、Postgres 18では、左端の列以外のマルチカラムインデックスを検索する際に、行を「スキップ」するスキップスキャン最適化であるルーズスキャンに似たものが追加されました。しかし、この場合でも、述語に一致するすべての行をスキャンするため、SELECT DISTINCTを高速化するために使用することはできません。別途、2018年にルーズインデックススキャンの追加に向けた大きな試みがありましたが、4年間の努力とメンテナーの交代を経て断念されました。 遅延の軽減 SELECT DISTINCTのパフォーマンスは、テーブルのサイズに比例してスケーリングし、含まれるユニークな値の数には比例しないため、スケーラブルな環境では使用できません。テーブル内のユニークな値の数を効率的に数えるには、代わりに回避策が必要です。これは、Postgresに効率的なクエリプランを生成させる、より複雑なクエリです。このクエリは、再帰的な共通テーブル式（CTE）を利用しているため、読むのが非常に困難です。大まかに言うと、これは宣言的なSQLの中で命令型のコードを書く方法です。本質的に、このクエリはループとして評価され、最初のイテレーションで「最小」のパーティションキーを見つけ、後続のイテレーションでその「次の」ユニークなパーティションキーを見つけます。これがその外観です。 Each loop iteration does a SELECT min() on a sorted index, so it only retrieves a single value instead of scanning the entire index. Therefore, because each loop iteration does fixed work and the total number of loop iterations is equal to the number of unique partitions, this query provides the O(number of partitions) performance we need. このパフォーマンスを検証するために、パーティション数を10に固定し、パーティションあたりの行数を1Kから1Mまで変化させて新しいクエリをベンチマークしました。ご覧のとおり、パーティションがどれだけ大きくなっても、中央値レイテンシは変化しません。 詳細はこちら スケーラブルで信頼性の高いシステムを構築するのが好きなら、ぜひお声を聞かせてください。DBOSでは、Postgresベースの耐久性のある実行を可能な限りシンプルかつ高性能にすることを目指しています。ぜひチェックしてみてください。 クイックスタート: https://docs.dbos.dev/quickstart GitHub: https://github.com/dbos-inc Discordコミュニティ: https://discord.gg/eMUHrvbu67 最近、Postgresがどのようにスケーリングするか、あるいはなぜあらゆるものにPostgresを使うべきかについて、人気のブログ記事が数多く登場しています。この記事では、少し違ったアプローチを取ります。直感的にはスケーリングするはずなのに、実際にはそうではないPostgresの機能に関する問題を説明します。 SELECT DISTINCTは、列のすべてのユニークな値を見つける、無害に見える句です。しかし、そのパフォーマンス特性は期待どおりではありません。テーブルにどのようなインデックスを張っても、取得すべきユニークな値がどれだけ少なくても、SELECT DISTINCTは常にその述語に一致するすべての行をスキャンします。最近、Postgresベースのキューワークロードのパフォーマンスを診断した際に、この問題に遭遇しました。SELECT DISTINCTが、最もシンプルで安価に見えるにもかかわらず、最もコストのかかるクエリであることが判明したのです。この記事では、何が起こったのか、Postgresのどのような設計上の決定がSELECT DISTINCTを遅くしているのか、そしてそれを回避する方法を説明します。 SELECT DISTINCTによるユニークパーティションの検索 この遅延は、Postgresベースのパーティション化されたキューワークロードで観測されました。各キューはパーティション（例えば、ユーザーごと）に分割されており、これにより各パーティションに独立してフロー制御を適用できます（例えば、各ユーザーが一度に最大1つのタスクを実行できるようにします）。パーティション化されたキューからワークフローをデキューする最初のステップは、「アクティブ」なパーティション、つまりエンキューされたワークフローがあるパーティションをすべて見つけることです。当初、私たちはこれにSELECT DISTINCTを使用していました。 SELECT DIS