I said:
> It sounds like you're getting a really bad plan for the queries
> triggered by the foreign key constraints. One thing to make sure
> of is that the datatype of the referenced and referencing columns
> are the same in each foreign key relationship. Also check that the
> planner statistics are reasonably up to date (pg_class.relpages and
> pg_class.reltuples should be in the vicinity of reality, at least).
Oh, I almost forgot the most important thing: you need an index on the
referencing column in each FK relationship. The system requires you to
have an index on the referenced column, but not the other one.
Unfortunately, deletes in the referenced table are gonna be really slow
if you do not have such an index ...
regards, tom lane