Avendo a che fare con una tabella molto grossa (milioni di righe) come si può fare per velocizzare una select ?

La tabella è semplicissima:
campo1 - campo2

la query:
select campo2 from tabella where campo1='xxx' order by rand() limit 0,1

Attualmente impiega 2 minuti ad estrapolare un singolo record..
qualche idea ?