Eh, there was a spurious join in that query which was created by an ORM which messed things up apparently. Sorry for the noise. This abstracted version of the original query that does the same is fast: woome=> EXPLAIN ANALYZE SELECT * FROM webapp_invite i INNER JOIN webapp_person p ON (i.id = p.id) WHERE p.is_suspended = false AND p.is_banned = false AND i.woouser = 'suggus' ORDER BY i.id DESC LIMIT 5; QUERY PLAN ------------------------------------------------------------------------------------------------------------------------------------------------------- Limit (cost=4549.51..4549.52 rows=5 width=238) (actual time=0.071..0.071 rows=0 loops=1) -> Sort (cost=4549.51..4549.58 rows=31 width=238) (actual time=0.070..0.070 rows=0 loops=1) Sort Key: i.id Sort Method: quicksort Memory: 25kB -> Nested Loop (cost=12.20..4548.99 rows=31 width=238) (actual time=0.036..0.036 rows=0 loops=1) -> Bitmap Heap Scan on webapp_invite i (cost=12.20..1444.45 rows=382 width=44) (actual time=0.034..0.034 rows=0 loops=1) Recheck Cond: ((woouser)::text = 'suggus'::text) -> Bitmap Index Scan on webapp_invite_woouser_idx (cost=0.00..12.10 rows=382 width=0) (actual time=0.032..0.032 rows=0 loops=1) Index Cond: ((woouser)::text = 'suggus'::text) -> Index Scan using webapp_person_pkey on webapp_person p (cost=0.00..8.11 rows=1 width=194) (never executed) Index Cond: (p.id = i.id) Filter: ((NOT p.is_suspended) AND (NOT p.is_banned)) Total runtime: 0.183 ms (13 rows) Time: 1.114 ms