Postgres SELECT DISTINCT scans every matching row regardless of indexing, DBOS finds

What DBOS found

The engineering team at DBOS, a company building durable execution on top of Postgres, has documented a scaling trap in one of the database's most familiar features. According to a post on the company's engineering blog, SELECT DISTINCT — the clause that returns the unique values of a column — always ends up scanning every row matching the query's predicates. No indexing strategy changes this, and neither does the number of distinct values being retrieved.

The team hit the problem while diagnosing a Postgres-backed queue workload. Queues were divided into partitions, one per user in their setup, so that flow control could be applied independently — allowing each user to run at most one task at a time, for example. Dequeueing begins by finding the active partitions, meaning those holding at least one workflow in the ENQUEUED state, and SELECT DISTINCT over the partition key is the natural way to express that.

Where the assumption broke

The query appeared well supported by an index on queue name, workflow status and partition key. Since the index is ordered along that hierarchy, DBOS expected Postgres to jump straight to the first row of each distinct partition key, making the cost proportional to the number of active partitions.

That assumption held for workloads with many partitions but few enqueued items per partition. It fell apart on workloads with the opposite shape: few partitions, each holding very large numbers of queued items. Queries that should have finished in under a millisecond took seconds instead.

A benchmark isolated the cause. With the partition count fixed at ten and rows per partition scaled from 100 to one million, query latency grew linearly with row count. The query was scaling with the total number of enqueued workflows rather than the number of unique partition keys — in the plan DBOS examined, one million rows were read to produce just three distinct keys.

Why the planner has no better option

According to the post, the plan Postgres produces is effectively a full index scan: it walks the index, pulls every matching row and checks each one for uniqueness. The waste is structural rather than a planning mistake — every index-scanning operator implemented in Postgres retrieves all indexed values that satisfy the predicates, so the planner simply has no shortcut available to choose.

The post contrasts this with MySQL, which offers a loose index scan operator that fetches only each unique value satisfying the query's conditions. Postgres 18 added a skip-scan optimisation for multicolumn indexes searched on a column other than the leftmost one, but DBOS notes it still visits every row matching the predicates and therefore cannot speed up SELECT DISTINCT. A separate effort to add a true loose index scan, begun in 2018, was abandoned after four years of work and maintainer churn.

The workaround

Because SELECT DISTINCT is not usable at scale in Postgres, DBOS replaced it with a deliberately awkward query built on a recursive common table expression. It behaves like an imperative loop: the first iteration selects the smallest partition key using min() against the sorted index, and each subsequent iteration selects the next key larger than the one before. Every iteration reads a single value, so the total cost is proportional to the number of unique partitions.

The company validated the rewrite with the same benchmark shape — ten partitions, between one thousand and one million rows each — and reports that median latency no longer changed as partitions grew.

Why it matters

SELECT DISTINCT is common enough that many teams will assume it behaves like an indexed lookup. DBOS's measurements show it behaves like a scan of everything matching the WHERE clause, which means latency tracks data volume rather than result size. That property stays invisible on small tables and tends to surface in production as queues, event tables and logs grow. Anyone running distinct-value queries for tenant listings, dashboards or deduplication on large Postgres tables should check their query plans for full index scans. Until Postgres ships a real loose index scan, the practical choice is between the recursive CTE pattern and queries that quietly degrade as data accumulates.