Extremely slow PostgreSQL query with ORDER and LIMIT clauses

When you have both the LIMIT and ORDER BY, the optimizer has decided it is faster to limp through the unfiltered records on foo by key descending until it gets five matches for the rest of the criteria. In the other cases, it simply runs the query as a nested loop and returns all the records.

Offhand, I'd say the problem is that PG doesn't grok the joint distribution of the various ids and that's why the plan is so sub-optimal.

For possible solutions: I'll assume that you have run ANALYZE recently. If not, do so. That may explain why your estimated times are high even on the version that returns fast. If the problem persists, perhaps run the ORDER BY as a subselect and slap the LIMIT on in an outer query.

Probably it happens because before it tries to order then to select. Why do not try to sort the result in an outer select all? Something like:SELECT * FROM (SELECT ... INNER JOIN ETC...) ORDER BY ... DESC

Your query plan indicates a filter on

(((NOT privacy_protected) OR (user_id = 67962)) AND ((status)::text = 'DONE'::text))

which doesn't appear in the SELECT - where is it coming from?

Also, note that expression is listed as a "Filter" and not an "Index Cond" which would seem to indicate there's no index applied to it.