Jag ger dig en vild gissning här:Databascache.
Första gången du kör sidan cachelagras inte frågan i databasen, så det tar längre tid, vilket innebär att PHPs tidsgräns löper ut.
På andra tillfällen är frågan mycket snabbare.
Du kan antingen dela upp frågan, som du nämnde, eller så kan du försöka öka tidsgränsen för skriptet:
set_time_limit(0); //No time limit
set_time_limit(60); //60 seconds
För att vara säker kan du använda denna för att rensa databascache och använda den alltid så att du alltid kommer att köra sidan på ren cache.