В принципе, работая с PHP + MySQL делал выборку не самую тривиальную из таблиц с количеством записей выше миллиона и это не занимало больше двух секунд, так что, думаю, что
disc прав.
Конечно, можно посмотреть в сторону Oracle DB, а, смотря на Twitter, в сторону RoR. Но, для начала, нужно оптимизировать запросы, проверить индексы и т.д.