I just reread the original post and noted this:
"Reuven M. Lerner" <reuven@lerner.co.il> writes:
> (1) I tried to write this as a join, rather than a subselect. But B has
> an oid column that points to large objects, and on which we have a rule
> that removes the associated large object when a row in B is removed.
A rule? Really? That's probably bad enough in itself, but when you
write an overcomplicated join delete query, I bet the resulting plan
is spectacularly bad. Have you looked at the EXPLAIN output for this?
I'd strongly recommend getting rid of the rule in favor of a trigger.
Also, as already noted, the extra join inside the IN sub-select is
probably hurting far more than it helps.
> (3) There are some foreign-key constraints on the B table.
If those are FK references *to* the B table, make sure the other end
(the referencing column) is indexed. Postgres doesn't require an index
on a referencing column, but deletes in the referenced table will suck
if you haven't got one.
I don't think any of the fancy stuff being discussed in the thread is
worth worrying about until you've got these basic issues dealt with.
regards, tom lane