Often, you either can't or don't want to rewrite the query. However, you can still try and speed it up through any of the techniques discussed here.
As a first step, you can start providing better information to the optimizer.
If EXPLAIN ANALYZE reveals that the estimates in the database differ a lot from the metrics returned by the actual query execution, you need to instruct PostgreSQL to collect more fine-grained statistics.
The current default statistics target can be shown using this command:
SHOW default_statistics_target;
You can set it to a higher value in the postgresql.conf file. Alternatively, if you want to do this only for a single database, you can use ALTER DATABASE, as follows:
ALTER DATABASE mydb SET default_statistics_target = 200;
Usually, you wouldn't want to set it too high for all tables and fields, as it slows down the ANALYZE command. In fact, PostgreSQL gives you a more fine-grained way of doing this on a field...