А размер БД какой? Если в explain постоянно всплывает filesort, то определите где именно она идёт - в памяти или с использованием диска. Попробуйте увеличить sort_buffer_size чтобы избежать сортировки на диске. Профилируйте с помощью profiling, причиной длительного исполнения запроса может быть блокировка query_cache. И, конечно же, разберитесь с индексами, они у вас явно не оптимизированы под запрос.
@andreyvlru: "рост до 100Gb" вот поэтому 128. Насчёт дисков - на ваших нагрузках вы не почувствуете разницу между SAS и SSD, а первые элементарно дешевле.