// HACKER NEWS — CYBERSECURITY
Postgres SELECT DISTINCT Does Not Scale
Recently, there has been no shortage of popular blog posts about how Postgres scales or why you should use it for everything. In this post, we'll do something a little different: describe an issue we had with a Postgres feature that intuitively should scale, but actually doesn't.
SELECT DISTINCT is an innocuous-seeming clause that finds all unique values of a column. However, its performance characteristics aren't what you'd expect: no matter how you index your table, no matter how few unique values there are to retrieve, SELECT DISTINCT will always scan every row that matches its predicates. We recently observed this when diagnosing the performance of a Postgres-backed queues workload, where SELECT DISTINCT turned out to be the most expensive query despite appearing to be the simplest and cheapest. In this blog post, we’ll explain what happened, what design decisions in Postgres make SELECT DISTINCT slow, and how to work around it.
We observed the slowdown in a Postgres-backed partitioned queues workload. 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.
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.
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.
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):