This query is run on a test system just after a backup of the database has been restored and it does exactly what I expect it to do EXPLAIN ANALYZE SELECT foos.* FROM foos INNER JOIN bars ON foos.id = bars.foos_id WHERE ((bars.bars_id = 12345)) ORDER BY attr1 LIMIT 3 OFFSET 0; QUERY PLAN ---------------------------------------------------------------------------------------------------------------------------------------------------------- Limit (cost=12946.83..12946.83 rows=3 width=1175) (actual time=0.123..0.131 rows=1 loops=1) -> Sort (cost=12946.83..12950.83 rows=1602 width=1175) (actual time=0.116..0.119 rows=1 loops=1) Sort Key: foos.attr1 -> Nested Loop (cost=28.69..12035.56 rows=1602 width=1175) (actual time=0.071..0.086 rows=1 loops=1) -> Bitmap Heap Scan on bars (cost=28.69..2059.66 rows=1602 width=4) (actual time=0.036..0.039 rows=1 loops=1) Recheck Cond: (bars_id = 12345) -> Bitmap Index Scan on index_bars_on_bars_id (cost=0.00..28.29 rows=1602 width=0) (actual time=0.024..0.024 rows=1 loops=1) Index Cond: (bars_id = 12345) -> Index Scan using foos_pkey on foos (cost=0.00..6.21 rows=1 width=1175) (actual time=0.017..0.021 rows=1 loops=1) Index Cond: (foos.id = bars.foos_id) Total runtime: 0.350 ms This query is run on a production system and is using foos_1attr1 which is an index on attr1 which is a string. EXPLAIN ANALYZE SELECT foos.* FROM foos INNER JOIN bars ON foos.id = bars.foos_id WHERE ((bars.bars_id = 12345)) ORDER BY attr1 LIMIT 3 OFFSET 0; QUERY PLAN --------------------------------------------------------------------------------------------------------------------------------------------------- Limit (cost=0.00..2847.31 rows=3 width=332) (actual time=6175.515..6414.599 rows=1 loops=1) -> Nested Loop (cost=0.00..287578.30 rows=303 width=332) (actual time=6175.510..6414.591 rows=1 loops=1) -> Index Scan using foos_1attr1 on foos (cost=0.00..128038.65 rows=1602 width=332) (actual time=0.182..2451.923 rows=2498 loops=1) -> Index Scan using bars_1ix on bars (cost=0.00..0.37 rows=1 width=4) (actual time=0.006..0.006 rows=0 loops=421939) Index Cond: (foos.id = bars.foos_id) Filter: (bars_id = 12345) Total runtime: 6414.804 ms