Fastest query for distinct IDs in a many-to-many relationship
What would be the most optimal plan for querying all distinct user_id
  for a significant part of the operation_id set (20%-60%).


Use a recursive query:

WITH RECURSIVE cte AS (
   (  -- parentheses are required
   SELECT user_id
   FROM   user_operations
   WHERE  operation_id &lt; 500
   ORDER  BY user_id
   LIMIT  1
   )
   UNION ALL
   SELECT u.user_id
   FROM   cte, LATERAL (
      SELECT user_id
      FROM   user_operations
      WHERE  operation_id &lt; 500
      AND    user_id &gt; cte.user_id  -- lateral reference
      ORDER  BY user_id
      LIMIT  1
      ) u
   )
TABLE cte;


In combination with an index on (user_id, operation_id) - columns in that order. I expect index scans that filter on the second column. Reasonably accurate table statistics are important so Postgres knows it will only have to skip a few rows in the index to find the next user_id. Generally, one might want to increase the statistics target for operation_id in particular:

ALTER TABLE user_operations ALTER operation_id SET STATISTICS 1000;


Since there are only ~1000-2000 different operations, this may not even be necessary, but it's a small price to pay.

Details:


Optimizing queries on a range of timestamps (two columns)


If the predicate operation_id &lt; 500 is stable (always the same), make that a partial index on just (user_id) instead:

CREATE INDEX foo ON user_operations (user_id) WHERE operation_id &lt; 500;


Then statistics on operation_id are not relevant to this query any more.

Even if the predicate is not stable, there may be ways to optimize - depending on the full range of possible conditions and value frequencies.

Performance should be ... delicious.

I optimized the technique in this related answer on SO (with detailed explanation):


Optimize GROUP BY query to retrieve latest record per user


If you have a separate users table and a large part of all users can be found in your sample, even faster query styles are possible. Details in the linked answer.