1. Обычный хостинг сильнее многих VPS - на момент запроса вам доступна практически вся мощь физического сервера, очень редко хостеры делают ограничения здесь
2. Запрос может быть и простым, но вы не написали кол-во данных в этой таблице 100? 10 000 000?
3. У вас одна таблица? Почему грешите именно на этот запрос? Опять же сколько в БД данных и какая структура (индексы)
4. Бывало тормозила VPSка пока не перекинули на другую железку, бывают плохие соседи и они по полной насилуют жесткий диск.