Hola!
tienes las tablas de tu BD bien indexadas? sino si q es posible q la consulta te tarde mucho!
Aparte mirate lo q te ha dicho Cluster,
http://es2.php.net/set_time_limit asi no tendras q avisar a tu proveedor para q te modifique el php.ini!
saludos
