Well adding an index will take forever, just dropped them. Did the deletes then re-created.

Since this table will have deletes perhaps once per quarter, I think that's the way to go...