Best performance to get distinct values for a given key from a big table

Question

Given a table like so:

CREATE TABLE attr (user_id uuid, key text, value text);

with indexes on key and value (but not a combined index) what are my options for getting a list of distinct values by key, without also destroying write performance? The obvious SELECT DISTINCT value WHERE key = :key is not cutting it performance-wise (currently the table is at ~20M rows, the actual table in production has more columns but is semantically similar).

I could maintain a separate table of the distinct values, which is easy enough to append to but is hard to determine when there are no longer any rows with the corresponding value in the attr table. I don't expect a lot of values to become "stale" given the nature of my data (user attributes) but it is possible, and I'd like to avoid having to manually clean it up!

Answer 1

Assuming many entries for the same (key, value), an emulated index skip scan should be your best option.

WITH RECURSIVE cte AS (
   (   -- parentheses required
   SELECT value
   FROM   attr
   WHERE  key = :key
   ORDER  BY 1
   LIMIT  1
   )
   UNION ALL
   SELECT l.*
   FROM   cte c
   CROSS  JOIN LATERAL (
      SELECT a.value
      FROM   attr a
      WHERE  a.key = :key
      AND    a.value > c.value  -- lateral reference
      ORDER  BY 1
      LIMIT  1
      ) l
   )
TABLE  cte;

See:

• SELECT DISTINCT is slower than expected on my table in PostgreSQL

You need the multicolumn index on (key, value) for best performance. You might replace the one on just (key) with it. See:

• Is a composite index also good for queries on the first field?

If values are sparse (only few duplicates on (key, value)), your current query with DISTINCT is the optimum. (Ruling out an additional table or materialized view with distinct entries.) See:

• Select first row in each GROUP BY group?

Aside 1: UUID seems like overkill for a user_id, but you probably have your reasons.

Aside 2: If key names are not very short, storing them in a key table (once) and just using integer key_id in attr should be more efficient: smaller table and index - keyword "database normalization".