Я бы не стал надеятся что оракел вас спасет. По моему опыту, тормозить в таких случаях он умеет отлично :)
— Придется потратить массу времени на возню с ним.
— А ваще он еще и платный — может за эти бабки докупить оперативы, Xeonов и SSD винтов?
Я не знаю сколько там у вас оперативки на сервере, но посмотрите на индексные файлы, их размер и в настройках мускула отведите, если есть возможность, размер памяти под индексы чуть больший чем размер этих индексных файлов
Может быть 10 запросов объединить в одну транзакцию/один запрос? ( Если еще не сделано )?
Таблицу, наверное можно разбить как нибудь, но особый эффект будет если разные части будут на разных винтах.
А еще может быть попробовать drizzle или какие то другие форки MySQL?