SELECT very slow when no results and a LIMIT is specified
Postgres does a bad job estimating the frequency of the combination of predicates in your query:

SELECT * FROM tbl
WHERE  related_id = 1 AND platform = 'p2'::platforms
LIMIT  20;


Each of your predicates is not very selective on its own - that information is available to Postgres ("most common values") - assuming your statistics are up to date:


  ~ 21 million rows total.
  ~ 3 million rows WHERE related_id=1
  ~ 8 million rows WHERE platform=p2  


IOW, ~ every 7th row passes the 1st filter and ~ every 3rd row passes the 2nd. Postgres does the (naive) math and expects that roughly every 20th row qualifies. Since there is no ORDER BY, any 20 qualifying rows will do. The fastest way should be to scan the table sequentially and be done after ~ 400 rows - only a few data pages, very cheap.

Using any indexes adds some extra cost, Postgres needs to scan index and table. (Exception: index-only scans, which are not possible here for your SELECT *). That will only pay if Postgres would otherwise have to read enough additional pages to estimate that to be more expensive. That's how I would explain that you see a sequential scan for a small LIMIT, but a bitmap index scan for a big (or no) LIMIT.

Unfortunately, the combination of your predicates turns out to be unexpectedly rare. Postgres has to scan the whole table just to find only 2 qualifying rows. (The index would actually be much cheaper in any case.)


  2 rows WHERE related_id=1 AND platform=p2


The combined frequency of values in multiple columns is not available to Postgres. Think about it: gathering statistics like that would quickly get out of hand.

A very simple and efficient solution for this particular case: Create a partial index:

CREATE INDEX related_id_1_platform_2_idx ON tbl (id)
WHERE  related_id = 1 AND platform = 'p2'::platforms;


Not only will this super-tiny index (2 rows) be a perfect match for your query, it will also make a count estimate available for your particular combination (entry in pg_class.reltuples). The actual index column is mostly irrelevant for this one, pick a small column, typically best to make it the PK.

If one of the two predicates can change, there is a more generic approach. Say, if related_id = 1 is the stable condition, then create:

CREATE INDEX related_id_1_idx ON tbl (platform)
WHERE  related_id = 1;


The index column is relevant again. This may not be enough to tip the scales because Postgres only collects complete statistics for index columns of functional indexes (else it relies on the statistics of the underlying table). I propose:

CREATE INDEX related_id_1_func_idx ON tbl ((platform::text::platforms))  -- double parens!
WHERE  related_id = 1;


Note the extra pair of parentheses - a syntactical necessity for the cast shorthand.
The expression platform::text::platforms doesn't actually change anything - it casts your enum to text and back. But it makes Postgres collect full statistics on the (presumed) new values.

Now, (after ANALYZE tbl) we have full statistics including most common values of platform for related_id = 1.

Check with:

SELECT *
FROM   pg_stats
WHERE  schemaname = 'public'  -- actual schema
AND    tablename  = 'related_id_1_func_idx';  -- actual idx name


And Postgres should choose the index for your case - if you repeat the same expression in your query. So:

SELECT ...
WHERE related_id = 1 AND platform::text::platforms = 'p2'::platforms;


Related:


Index that is not used, yet influences query


About most common values in the Postgres statistics:


Speeding up a GROUP BY, HAVING COUNT query