[Delirium]

Способов оптимизации очень много. Это и партиционирование таблиц, и перестройка индексов, и оптимизация самих запросов и так далее. Вы описываете слишком общую картину, чтобы дать конкретный ответ.
Для ясности:
размер базы? количество индексов, участвующих в запросах? Количество строк в таблицах? Пример SQL запроса?

У меня есть таблица, в которой порядка миллиарда записей, так в ней простой ORDER BY делается довольно долго.