Crie um índice composto em (foo_id, foo, date) (nesta ordem).

Observe que, se você selecionar 500 mil registros (e devolvê-los todos ao cliente), isso pode demorar.

Tem certeza de que precisa de todos os 500 mil registros no cliente (em vez de algum tipo de agregado ou um LIMIT )?