Създайте съставен индекс на (foo_id, foo, date) (в този ред).
Имайте предвид, че ако изберете 500k записа (и ги върнете всички на клиента), това може да отнеме много време.
Сигурни ли сте, че имате нужда от всичките 500 000 записа на клиента (вместо някакъв вид агрегат или LIMIT )?
