Delete is very slow; PG not using existing index to check foreign keys

I've got a problem where Deletes on a certain table are taking very long (>5
sec) (PG 8.1.3, linux). Explain Analyze on the delete shows that two
(automatically created) triggers caused by foreign keys are responsible for
99% of the time.
* The two tables are large (>1.5mm and >400k rows), so sequential scans do
take a long time.
* I've got indices on these tables, but PG doesn't appear to be using them
during the delete.
* If I run the same SELECT in psql, it does use the index and responds very
quickly.

For example, I interrupted the Delete, and it appears that it was executing
a select from an FK table:
SELECT 1 FROM ONLY "public"."party_aliases" x WHERE "owner_party_id" = $1
FOR SHARE OF x;

OK, that's fine. There's an index on that column:
CREATE INDEX party_aliases_owner_party_idx ON party_aliases USING btree
(owner_party_id, id);

I've run ANALYZE, and that doesn't appear to make any difference. Why would
PG use the index when I run the select myself, but do a sequential scan when
the same statement is run by the delete trigger?

I looked through the mailing lists, but most suggestions appeared to be 1)
create an index, or 2) run analyze. Any ideas?

Thanks in advance,
Kian Wright

_________________________________________________________________
Express yourself instantly with MSN Messenger! Download today - it's FREE!
http://messenger.msn.click-url.com/go/onm00200471ave/direct/01/