авторСервер удалил 10 000 записей за 614 секунд.

Какова его производительность? Если что могу описать железо.
Для начала опишите имя сервера, какое ему "мама" (Sybase) при рождении дала, его возраст, измеряемый его номер версии, среду обитания (ОС и железо) и дополнительные сведения на таблицу (есть ли на нее CONSTRAINTS и триггера, производилось ли удаление при наличие работы других сессий с этой таблицей).

P.S. 10 000/614 = 16 записей в секунду. Недурно, прямо как будто БД на дискете находиться :)