Planner regression in 8.0.x ?

Last night I upgraded my three DB servers from 7.4.8 to 8.0.4 (RPM from
the PostgreSQL site). This morning I found my servers very busy from
three queries that were two hours old:

The following query ran in a fraction of a second on 7.4.8:

SELECT receipt_date, process_date, callsign AS applicant_callsign,
operator_class, geo_region, uls_file_num,
vanity_callsign, prediction, predict_level AS _level, licensee_id AS
_lid,
operator_group AS _oper_group, vanity_group AS _vanity_group,
vanity_region AS _vanity_region, usps AS _usps, end_date AS _end_date,
(SELECT TRUE FROM archivejb WHERE ( (callsign = gen.callsign AND
license_status = 'A' AND prev_callsign = gen.vanity_callsign)
OR (callsign =
gen.vanity_callsign AND licensee_id =
gen.licensee_id))
AND grant_date < receipt_date LIMIT
1) AS _verified,
(SELECT TRUE FROM "ReservedCall" WHERE vanity_callsign ~ pattern
LIMIT 1) AS _reserved, radio_service AS _service
FROM genapp_pending_ AS gen WHERE vanity_type::CHAR = 'A'
ORDER BY receipt_date DESC, SUBSTRING( callsign, '[0-9]' ), callsign,
uls_file_num DESC, seq_num

On 8.0.4, it runs for hours (stopped after two hours). Here's the plan:

Sort (cost=921303.61..921303.61 rows=2 width=114)
Sort Key: "_Pending".receipt_date,
"substring"(("_Pending".callsign)::text, '[0-9]'::text),
"_Pending".callsign, "_Pending".uls_file_num, "_Pending".seq_num
-> Nested Loop (cost=0.00..921303.60 rows=2 width=114)
Join Filter: (("outer".prediction)::text ~~
("inner".prediction)::text)
-> Seq Scan on "_Pending" (cost=0.00..2266.61 rows=10 width=112)
Filter: ((((((vanity_type)::text || ' - '::text) ||
(COALESCE((subplan), '???'::character
varying))::text))::bpchar)::character(1) = 'A'::bpchar)
SubPlan
-> Limit (cost=0.00..1.07 rows=1 width=19)
-> Seq Scan on "_VanityType" (cost=0.00..1.07
rows=1 width=19)
Filter: (vanity_id = $8)
-> Seq Scan on "_Prediction" (cost=0.00..1.21 rows=21 width=18)
SubPlan
-> Index Scan using "_HD_pkey" on "_HD" (cost=0.00..3.01
rows=1 width=6)
Index Cond: (unique_system_identifier = $7)
-> Limit (cost=0.00..1.01 rows=1 width=0)
-> Seq Scan on "_ReservedCall" (cost=0.00..1.01
rows=1 width=0)
Filter: ($2 ~ (pattern)::text)
-> Limit (cost=455905.32..459495.68 rows=1 width=0)
-> Subquery Scan archivejb (cost=455905.32..498989.60
rows=12 width=0)
Filter: (((callsign = $4) AND (license_status =
'A'::bpchar) AND (prev_callsign = $2)) OR ((callsign = $2) AND
(licensee_id = $5)))
-> Unique (cost=455905.32..488509.64
rows=465776 width=229)
-> Sort (cost=455905.32..457069.76
rows=465776 width=229)
Sort Key: callsign, fcc_reg_num,
licensee_id, prev_callsign, trustee_callsign, applicant_type,
operator_class, prev_class, radio_service, license_status, geo_region,
grant_date, effective_date, cancel_date, expire_date, last_action_date,
entity_name, first_name, middle_init, last_name, name_suffix, address,
po_box, city, state, zip9, sys_id
-> Append (cost=0.00..194809.19
rows=465776 width=229)
-> Subquery Scan "*SELECT* 1"
(cost=0.00..75019.36 rows=1 width=229)
-> Nested Loop
(cost=0.00..75019.35 rows=1 width=229)
Join Filter:
("outer".callsign = "inner".callsign)
-> Merge Join
(cost=0.00..75013.39 rows=1 width=216)
Merge Cond:
("outer".unique_system_identifier = "inner".unique_system_identifier)
Join Filter:
("outer".callsign = "inner".callsign)
-> Index
Scan using "_EN_pkey" on "_EN" (cost=0.00..37158.11 rows=911646 width=158)
-> Index
Scan using "_AM_pkey" on "_AM" (cost=0.00..21972.80 rows=906891 width=58)
-> Index Scan
using "_HD_pkey" on "_HD" (cost=0.00..5.91 rows=1 width=49)
Index Cond:
("outer".unique_system_identifier = "_HD".unique_system_identifier)
Filter:
(grant_date < $6)
-> Subquery Scan "*SELECT* 2"
(cost=0.00..119789.84 rows=465775 width=186)
-> Seq Scan on "_Lic"
(cost=0.00..115132.09 rows=465775 width=186)
Filter:
((COALESCE((grant_date)::timestamp without time zone, (expire_date - '10
years'::interval)))::date < $6)
-> Index Scan using "_HD_pkey" on "_HD" (cost=0.00..5.91
rows=1 width=8)
Index Cond: (unique_system_identifier = $3)
-> Seq Scan on "_GeoRestrict" (cost=0.00..1.20 rows=1 width=1)
Filter: ($2 ~ (pattern)::text)
-> Limit (cost=0.00..1.05 rows=1 width=9)
-> Seq Scan on "_CallsignGroup" (cost=0.00..1.05
rows=1 width=9)
Filter: (group_id = $1)
-> Limit (cost=0.00..2.17 rows=1 width=14)
-> Nested Loop (cost=0.00..2.17 rows=1 width=14)
Join Filter: ("inner".group_id = "outer".group_id)
-> Seq Scan on "_OperatorClass"
(cost=0.00..1.07 rows=1 width=5)
Filter: (class_id = $0)
-> Seq Scan on "_CallsignGroup"
(cost=0.00..1.04 rows=4 width=14)
-> Limit (cost=0.00..1.07 rows=1 width=13)
-> Seq Scan on "_OperatorClass" (cost=0.00..1.07
rows=1 width=13)
Filter: (class_id = $0)

In the query, if I remove the "(SELECT TRUE FROM archivejb ... LIMIT 1)
AS _verified", the query runs in a fraction of a second.

"archivejb" is a UNION of one VIEW (JOIN of three tables, w/ 0.9 million
rows) and one TABLE (1.3 million rows). All the other tables are tiny
(<100 rows).

If I can't fix this, I'll have to go back to 7.4.8.

HELP!

-- Dean