Postgres SELECT DISTINCT Does Not Scale | DBOS

DBOS is now Patented Technology!

PricingCustomersResources

Docs

Blog

Explore

...

Sign in

Get started

July 24: DBOS User Group Meeting

CustomersPricingBlogDocs<br>Resources

Start your project

Login

Login<br>Start your project

Back to posts

Postgres SELECT DISTINCT Does Not Scale

Peter Kraft

August 10, 2026<br>Benchmarks

Add to Google<br>Share this post

At DBOS, we love Postgres and build everything on it. Often, it surprises us in a good way, scaling to handle workloads most people say it can’t. But other times, we find unexpected limitations. This blog post is about one of those times. We recently noticed a significant slowdown in a Postgres-backed queues workload that traced back to surprisingly poor performance from Postgres SELECT DISTINCT. We’ll explain what happened, what design decisions in Postgres caused this, and how we mitigated it.<br>Finding Unique Partitions with SELECT DISTINCT<br>The workload where we observed the slowdown was using partitioned Postgres-backed queues. Each queue is divided into partitions (for example, one per user) so flow control can be applied independently to each partition (for example, allowing each user to run at most one task at a time). The first step in dequeueing workflows from a partitioned queue is to find all “active” partitions, meaning partitions with an ENQUEUED workflow on them. We originally used `SELECT DISTINCT` to do this:

What SELECT DISTINCT does is find all unique values of a column given some condition. So this query finds all unique non-NULL partition keys among ENQUEUED workflows on a particular queue. We expected this query to be fast because it’s properly indexed using an index on queue name, workflow status, and partition key:

Intuitively, the index looks like this. Workflows are laid out in a tree structure first by queue name, then by status, then by partition key. This allows Postgres to efficiently locate workflows using all three fields.

Because the index has this shape, we expected the performance of this query to be O(number of active partitions). After all, to satisfy this query Postgres only needs to seek a single row from each unique partition, then return the partition keys it found.<br>Initially, this appeared to be working as intended. Most of our queue workloads were “wide but shallow” with many partitions but few enqueued workflows per partition. For those, the query performed as expected. However, we soon encountered issues with “narrow but deep” workloads where there were few partitions, but they each contained many enqueued workflows. We expected the query to finish in under a millisecond because there were so few partitions, but instead it took seconds. We quickly realized this meant the query was scaling not with the number of active partitions, but with the total number of enqueued workflows, making it unacceptably slow.<br>We validated this observation with a benchmark fixing the number of partitions at 10 but scaling the number of rows per partition from 100 to 1M. As we can see, query latency scales linearly with the number of rows per partition.

To understand why that was happening and how to fix it, we’ll have to examine how Postgres plans and executes this query.<br>The SELECT DISTINCT Query Plan<br>When we examined the query plan Postgres was using for the SELECT DISTINCT query, it looked like this (assuming 1M enqueued workflows across 3 partitions):

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.<br>The Postgres query planner chooses this plan because it doesn’t have an alternative. Every operator implemented in Postgres for scanning an index performs a full index scan, retrieving all indexed values matching its predicates. Other relational databases do better: MySQL provides a “loose index scan” operator that retrieves only each unique value that satisfies its predicates.<br>Interestingly, Postgres 18 added something like a loose scan: a skip scan optimization that “skips” rows when searching a multicolumn index on a column other than its leftmost column. However, in our case, this still scans all rows that match its predicates, so it can’t be used to speed up SELECT DISTINCT. Separately, there was a significant attempt to add a loose index scan in 2018, but it was abandoned after four years of effort and maintainer churn.<br>Mitigating the Slowdown<br>Because the performance of SELECT DISTINCT scales with the size of the table and not the number of unique values it contains, it is not usable at...