Postgres SELECT DISTINCT Does Not Scale

SELECT DISTINCT in Postgres can appear cheap but scales with total matching rows, not with the number of distinct values. In a partitioned-queue workload (index on queue, status, partition_key) the query was expected to be O(number of active partitions) - one seek per partition - but in “narrow but deep” cases (few partitions, many rows per partition) latency grew linearly with rows. A benchmark fixing partitions at 10 while increasing rows per partition from hundreds to a million showed SELECT DISTINCT runtimes ballooning into seconds, proving the operation effectively scanned every matching row.

The root cause is the planner/executor: Postgres lacks a “loose index scan” operator that would return just unique index entries, so it performs a full index walk and checks uniqueness at runtime. MySQL implements loose scans; Postgres has a skip-scan-like feature in v18 but it still scans all predicate-matching rows and prior attempts to add a true loose scan were abandoned. The practical mitigation is a recursive CTE that iteratively SELECTs min(partition_key) after the previous key, forcing single-row indexed seeks per unique value. That looped min() approach delivers O(number of partitions) behavior in practice and keeps latency constant as rows-per-partition grow.