Pode haver várias explicações sobre por que sua consulta demora muito:

1. Você pode ser bloqueado por outra sessão (provavelmente). Antes de excluir, você deve ter certeza de que ninguém mais está bloqueando as linhas, por exemplo:issue SELECT NULL FROM tablename WHERE colname=:value FOR UPDATE NOWAIT ,
2. Pode haver um ON DELETE TRIGGER que faz trabalho adicional,
3. Verifique se há UNINDEXED REFERENCE CONSTRAINTS apontando para esta tabela (há um script do AskTom que o ajudará a determinar se essas chaves estrangeiras não indexadas existem).