Unbearably slow cascading deletes

I have (among other things) a parent table with 200 records and a child table with 20MM or more. I set up referential integrity on the FK with ON DELETE CASCADE.

It appears that when a DELETE is done on the parent table, the child table deletion is done with a sequential scan. I say this because it took over four minutes to delete a parent record THAT HAD NO CHILDREN. The DB is recently analyzed and SELECTs in the child table are done by the appropriate index on the FK.

Let me guess, the cascade trigger's query plan is decided at schema load time, when the optimizer has no clue. Is there a way to fix this without writing my own triggers, using PL/PGSQL EXECUTE to delay the planner?

And by the way, if FK conditions like IN (1,3,4) could be handled in a single invocation of the trigger, so much the better.