После оптимизации и добавления нужных индексов запрос начал выполнять 2-3 секунды на сервере.
Индексы вообще-то должны были быть сразу "какие надо".
С чего вы решили, что ваша "локальная машина"
близка по параметрам к серверу?
Тем более, если там виртуальный сервер - то ресурсы делятся на всех.
У вас то же железо?
Та же версия ОС?
Те же настройки MySQL?
Та же версия MySQL?
Полагаю, ответ на все вопросы -
нет?