I have too much scar tissue around accidental table scans caused by the fact that foreign key constraints don't implicitly create an index. If you think logarithmic insertion time is bad for your p95 times, try quadratic times on delete operations gone horribly wrong.