Per capire perché l'ordinamento random è una pessima idea in termini di performance occorre capire come ciò avviene in MySQL.
MySQL deve innanzitutto reperire tutti i record di una tabella per poi effettuare l'ordinamento. Va da se che maggiore è il numero dei record maggiore sarà il tempo di elaborazione.