Very slow DELETE in PostgreSQL, workaround?
I had a similar problem. As it turns out, those ON DELETE CASCADE triggers were slowing things down quite a bit, because those cascaded deletions were awfully slow.

I solved the problem by creating indexes on the foreign key fields on the referencing tables, and I went from taking a bunch of hours for the deletion to a few seconds.