Query plan for a dynamically built `query_int` using `format()`
First of all, you can simplify the query you have. format() is not needed, among other things:

SELECT *
FROM   media
WHERE  tag_ids @@ array_to_string(ARRAY (
         WITH  tag_ids AS (SELECT id FROM tags WHERE tag IN ('kittens', 'puppies'))
         TABLE tag_ids
         UNION ALL
         SELECT 0 WHERE NOT EXISTS (TABLE tag_ids)
         ), '&amp;')::query_int
ORDER  BY rating DESC
LIMIT  20;


While your query_int value only uses &amp;, further simplify to:

SELECT *
FROM   media
WHERE  tag_ids @&gt; COALESCE(NULLIF(ARRAY(SELECT id FROM tags WHERE tag IN ('kittens', 'puppies')), '{}'), '{0}')
ORDER  BY rating DESC
LIMIT  20;


Should be faster already. But the core problem remains - which is very similar to the one discussed in detail here:


Postgres sometimes uses inferior index for WHERE a IN (...) ORDER BY b LIMIT N


Basically this: Postgres (necessarily) chooses the query plan based on incomplete information. Column statistics cannot contain all frequencies for many rare values. So it's very hard to estimate which plan will be faster: 


plan A: traverse the index media_rating_index and filter  
plan B: bitmap index scan on media_tag_ids_gin__int_ops_index, sort by ratings, limit


Your case adds complication with a convoluted subquery, which makes it even harder to estimate what might come out of it.

Whatever else you do, make sure you run the most recent version of Postgres available to you, as your particular problem may well profit from a number of recent improvements around this.

Depending on undisclosed information, one of these may work:

1.

Rewrite your query with LEFT JOIN LATERAL as demonstrated in the referenced answer.

2.

Completely disable plan A by obfuscating the ORDER BY. Assuming it's a numerical column:

SELECT ...
ORDER  BY rating + 0 DESC
LIMIT  20;


Like Laurenz suggested:


Postgres sometimes uses inferior index for WHERE a IN (...) ORDER BY b LIMIT N


3.

Even more radical, delete the index media_rating_index - unless it's needed for other queries!

4.

Jeff suggested a manual setting for n_distinct in the related case, but I am not sure how to achieve the same for array elements ...


Postgres sometimes uses inferior index for WHERE a IN (...) ORDER BY b LIMIT N


5.

Here is a related case from the pgsql-performance list. Your case is simpler, you may improve your situation by just upping the statistics target for tag_ids:

ALTER TABLE media ALTER COLUMN tag_ids SET STATISTICS 1000;


And then run ANALYZE media.
This may be useful in addition to other options, especially the following.

6.

In a related case I had success with a fake-IMMUTABLE function:

CREATE FUNCTION f_tag_id_array(VARIADIC text[])
  RETURNS int[] IMMUTABLE PARALLEL SAFE LANGUAGE plpgsql AS
$func$
BEGIN
   RETURN COALESCE(NULLIF(ARRAY(SELECT id FROM tags WHERE tag = ANY($1)), '{}'), '{0}');
END
$func$


Then use it in your query:

SELECT *
FROM   media
WHERE  tag_ids @&gt; f_tag_id_array('kittens', 'puppies')
ORDER  BY rating DESC
LIMIT  20;


Since Postgres now assumes that f_tag_id_array() is immutable it may choose to evaluate it early and continue with the returned constant - thereby achieving the different query plan for known rare IDs you were after.

Note that we are lying about IMMUTABLE - it is not. So don't build an index on it. And it's not safe to use with concurrent write access on table tags.

And since we are lying there, the function cannot be inlined, so using a simpler SQL function won't buy anything in this case. Rather have the saved query plan feature of plpgsql.

The same worked with STABLE on a Postgres 11 instance, while a Postgres 10 instance required the IMMUTABLE hack ...