Ti darò un'ipotesi selvaggia qui:memorizzazione nella cache del database.
Alla prima esecuzione della pagina, la query non viene memorizzata nella cache nel database, quindi impiega più tempo, quindi scade il limite di tempo di PHP.
Nelle altre volte, la query è molto più veloce.
Puoi dividere la query, come hai detto, oppure puoi provare ad aumentare il limite di tempo sullo script:
set_time_limit(0); //No time limit
set_time_limit(60); //60 seconds
Per sicurezza, potresti usare questo per pulire la cache del database e usarla sempre così eseguirai sempre la pagina su clean cache.
