Se non hai un indice nel campo in base al quale stai ordinando, aggiungine uno:
"In alcuni casi, MySQL può utilizzare un indice per soddisfare una clausola ORDER BY senza eseguire alcun ordinamento aggiuntivo."
Modifica:(dalla sezione sezione sull'ottimizzazione ORDER BY nella documentazione di MySQL.)