yo primero añadiria un "limit" a la consulta. ten en cuenta que mysql_query carga todos los registros en memoria (
http://php.grn.es/manual/en/function...ered-query.php).
seria "select ... from tabla order ... limit 0, 10".
declara indices en aquellas consultas que se usaran frecuentemente para buscar u ordenar campos.