Ik zal je hier een wilde gok geven:Database-caching.
De eerste keer dat u de pagina uitvoert, wordt de query niet in de cache opgeslagen in de database, dus het duurt langer, waardoor de tijdslimiet van PHP verloopt.
Op de andere momenten is de zoekopdracht veel sneller.
Je kunt de query splitsen, zoals je al zei, of je kunt proberen de tijdslimiet van het script te verhogen:
set_time_limit(0); //No time limit
set_time_limit(60); //60 seconds
Voor de zekerheid kun je deze om de databasecache op te schonen en altijd te gebruiken, zodat u de pagina altijd in een schone cache zult uitvoeren.