8.4.7, incorrect estimate

Howdy. We've got a query that takes less than a second unless we add a
"order by" to it, after which it takes 40 seconds. Here's the query:

select page_number, ps_id, ps_page_id from ps_page where ps_page_id in
(select ps_page_id from documents_ps_page where document_id in (select
document_id from temp_doc_ids)) order by ps_page_id;

The parts of the schema used in this query:

Table "public.ps_page"
Column | Type | Modifiers

-------------+---------+--------------------------------------------------------------
ps_page_id | integer | not null default
nextval('ps_page_ps_page_id_seq'::regclass)
ps_id | integer | not null
page_number | integer | not null
Indexes:
"ps_page_pkey" PRIMARY KEY, btree (ps_page_id)
"ps_page_ps_id_key" UNIQUE, btree (ps_id, page_number)

Table "public.documents_ps_page"
Column | Type | Modifiers
-------------+---------+-----------
document_id | text | not null
ps_page_id | integer | not null
Indexes:
"documents_ps_page_pkey" PRIMARY KEY, btree (document_id, ps_page_id)
"documents_ps_page_ps_page_id_idx" btree (ps_page_id)

temp_doc_ids (temporary table):
document_id text not null

The query with the "order by" (slow):

explain analyze select page_number, ps_id, ps_page_id from ps_page where
ps_page_id in (select ps_page_id from documents_ps_page where
document_id in (select document_id from temp_document_ids)) order by
ps_page_id
Merge Semi Join (cost=212570.02..3164648.31 rows=34398932
width=12) (actual time=54749.281..54749.295 rows=5 loops=1)
Merge Cond: (ps_page.ps_page_id = documents_ps_page.ps_page_id)
-> Index Scan using ps_page_pkey on ps_page
(cost=0.00..2999686.03 rows=86083592 width=12) (actual
time=0.029..36659.393 rows=85591467 loops=1)
-> Sort (cost=18139.39..18152.52 rows=6255 width=4) (actual
time=0.080..0.083 rows=5 loops=1)
Sort Key: documents_ps_page.ps_page_id
Sort Method: quicksort Memory: 25kB
-> Nested Loop (cost=26.23..17808.09 rows=6255 width=4)
(actual time=0.044..0.073 rows=5 loops=1)
-> HashAggregate (cost=26.23..27.83 rows=200
width=32) (actual time=0.015..0.017 rows=5 loops=1)
-> Seq Scan on temp_document_ids
(cost=0.00..23.48 rows=1310 width=32) (actual time=0.004..0.007 rows=5
loops=1)
-> Index Scan using documents_ps_page_pkey on
documents_ps_page (cost=0.00..88.59 rows=31 width=42) (actual
time=0.009..0.010 rows=1 loops=5)
Index Cond: (documents_ps_page.document_id =
(temp_document_ids.document_id)::text)
Total runtime: 54753.028 ms

The query without the "order by" (fast):

production=> explain analyze select page_number, ps_id, ps_page_id from
ps_page where ps_page_id in (select ps_page_id from documents_ps_page
where document_id in (select document_id from temp_doc_ids));

QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------------------------
Nested Loop (cost=17821.42..87598.71 rows=34398932 width=12) (actual
time=0.099..0.136 rows=5 loops=1)
-> HashAggregate (cost=17821.42..17871.46 rows=6255 width=4)
(actual time=0.083..0.096 rows=5 loops=1)
-> Nested Loop (cost=26.23..17808.28 rows=6255 width=4)
(actual time=0.047..0.076 rows=5 loops=1)
-> HashAggregate (cost=26.23..27.83 rows=200 width=32)
(actual time=0.014..0.015 rows=5 loops=1)
-> Seq Scan on temp_doc_ids (cost=0.00..23.48
rows=1310 width=32) (actual time=0.005..0.005 rows=5 loops=1)
-> Index Scan using documents_ps_page_pkey on
documents_ps_page (cost=0.00..88.59 rows=31 width=42) (actual
time=0.010..0.010 rows=1 loops=5)
Index Cond: (documents_ps_page.document_id =
temp_doc_ids.document_id)
-> Index Scan using ps_page_pkey on ps_page (cost=0.00..11.14
rows=1 width=12) (actual time=0.007..0.007 rows=1 loops=5)
Index Cond: (ps_page.ps_page_id = documents_ps_page.ps_page_id)
Total runtime: 0.213 ms
(10 rows)

We notice that in all cases, the plans contain some estimated row counts
that differ quite a bit from the actual row counts. We tried increasing
(from 100 to 1,000 and 10,000) the statistics targets for each of the
indexed columns, one at a time, and analyzing the table/column with each
change. This had no effect.

Postgres version 8.4.7 on AMD64, Debian Linux "wheezy" (aka "testing").

Where should we look next?