Poor performance of delete by primary key

Hello,

We are seeing a very strange behavior from postgres. For one of our very common tasks we have to delete records from a table of around 500,000 rows. The delete is by id which is the primary key. It seems to be consistently taking around 10 minutes to preform. This is totally out of line with the rest of the performance of the database.

This table does have children through foreign keys, but I am pretty sure that all foreign key constraints in the schema have indexes on their children.

Sometimes if we do a vacuum right before running the process the delete will go much faster. But then the next time we run the task, even just a few minutes later, the delete takes a long time to run.

We deploy the same application also on Oracle. The schemas are pretty much identical. On similar hardware with actually about 4 to 5 times the data, Oracle does not seem to have the same problem. Not that that really means anything since the internals of Oracle and PostgreSQL are so different, but an interesting fact anyway.

Any ideas on what might be going on?

Thanks,
B.