Si vous n'avez pas d'index sur le champ par lequel vous triez, ajoutez-en un :
"Dans certains cas, MySQL peut utiliser un index pour satisfaire une clause ORDER BY sans effectuer de tri supplémentaire."
Modifier :(De la section sur l'optimisation ORDER BY dans la documentation MySQL.)
