Ok done, all the dusty corners of my DB have been vacuumed!
The EXPLAIN ANALYZE was a TON faster now, I could even run it with the 20,000 limit. Perhaps the vacuum did the trick?
sudo -u postgres psql discourse -c "EXPLAIN ANALYZE SELECT posts.id FROM posts LEFT JOIN post_search_data pd ON pd.locale='en' AND pd.version=2 AND pd.post_id=posts.id LEFT JOIN topics ON topics.id=posts.topic_id WHERE pd.post_id IS NULL AND topics.id IS NOT NULL AND topics.deleted_at IS NULL AND posts.raw!='' ORDER BY posts.id DESC LIMIT 20000;";
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=1440033.74..1440033.75 rows=1 width=4) (actual time=4549.789..4550.293 rows=3077 loops=1)
-> Sort (cost=1440033.74..1440033.75 rows=1 width=4) (actual time=4549.788..4550.104 rows=3077 loops=1)
Sort Key: posts.id DESC
Sort Method: quicksort Memory: 241kB
-> Nested Loop (cost=599461.35..1440033.73 rows=1 width=4) (actual time=2535.778..4548.345 rows=3077 loops=1)
-> Gather (cost=599460.92..1440030.82 rows=1 width=8) (actual time=2535.705..4734.830 rows=3118 loops=1)
Workers Planned: 2
Workers Launched: 2
-> Hash Anti Join (cost=598460.92..1439030.72 rows=1 width=8) (actual time=2551.745..4510.171 rows=1039 loops=3)
Hash Cond: (posts.id = pd.post_id)
-> Parallel Seq Scan on posts (cost=0.00..798106.15 rows=1718754 width=8) (actual time=0.022..810.363 rows=1377851 loops=3)
Filter: (raw <> ''::text)
Rows Removed by Filter: 169
-> Hash (cost=530651.93..530651.93 rows=4133119 width=4) (actual time=2535.564..2535.564 rows=4130922 loops=3)
Buckets: 1048576 Batches: 8 Memory Usage: 26319kB
-> Seq Scan on post_search_data pd (cost=0.00..530651.93 rows=4133119 width=4) (actual time=0.037..1846.142 rows=4130922 loops=3)
Filter: (((locale)::text = 'en'::text) AND (version = 2))
Rows Removed by Filter: 3104
-> Index Only Scan using index_topics_on_id_and_deleted_at on topics (cost=0.43..2.91 rows=1 width=4) (actual time=0.004..0.004 rows=1 loops=3118)
Index Cond: ((id = posts.topic_id) AND (id IS NOT NULL) AND (deleted_at IS NULL))
Heap Fetches: 709
Planning time: 2.687 ms
Execution time: 4750.903 ms
(23 rows)