SELECT сам по себе быстрый если в нем нет JOIN. 600к строк проблема если серверу уже лет 20 и обрабатывает он как минимум еще около 10к людей.
Почитайте про настройку
MySQL
Так же про
Индексирование
Ну, а если еще захотите использовать некое кеширование то тут я не силен - скажу только что использую в первом запросе сохранение данных с него в кеш и периодически обновляю ID строк которые туда попадают.
Всего найлучшего!