Dipende sempre dalla quantità di dati presenti nelle tabelle coinvolte nelle query.
Caso mai il problema sarebbe nella memoria del server che deve visualizzare un certo ammontare di dati e il tempo di esecuzione max di uno script.
Per intenderci, devi vedere la configurazione in php.ini

;;;;;;;;;;;;;;;;;;;
; Resource Limits ;
;;;;;;;;;;;;;;;;;;;

max_execution_time = 30 ; Maximum execution time of each script, in seconds
max_input_time = 60 ; Maximum amount of time each script may spend parsing request data
memory_limit = 8M ; Maximum amount of memory a script may consume (8MB)


Se 8M sono pochi puoi sempre aumentare. E' vero che su hosting non lo puoi fare, però puoi sempre provare con il comando ini_set()... non si sa mai.

Cmq per le ottimizzazioni delle query, se ti scarichi il manuale di MySQL lì ci sono delle dritte.

Ciao.