MySQL: registros aleatorios sin ORDER BY RAND()

No es recomendable usar el ORDER BY RAND() en una sentencia mysql, ya que ejecutar RAND() requiere de más potencia de procesado para cada una de las filas antes de ordenarlas y devolver una simple fila.

// MAL
mysql_query("SELECT * FROM mitabla ORDER BY RAND() LIMIT 1");

Es mucho más optimizado generar la fila aleatoria en php. Un ejemplo:

// BIEN
$query_filas = mysql_query("SELECT count(*) FROM mitabla");
$array_fila = mysql_fetch_row($query_filas);
$fila = $array_fila[0];
$aleatorio = rand(0, $fila-1);
mysql_query("SELECT * FROM mitabla LIMIT $aleatorio, 1");