Dam ci dzikie zgadywanie tutaj:Buforowanie bazy danych.
Przy pierwszym uruchomieniu strony zapytanie nie jest buforowane w bazie danych, więc zajmuje to więcej czasu, co powoduje wygaśnięcie limitu czasu PHP.
W innych przypadkach zapytanie jest znacznie szybsze.
Możesz albo podzielić zapytanie, jak wspomniałeś, albo spróbować zwiększyć limit czasu w skrypcie:
set_time_limit(0); //No time limit
set_time_limit(60); //60 seconds
Dla pewności możesz użyć tego aby wyczyścić pamięć podręczną bazy danych i używać jej zawsze, aby zawsze uruchamiać stronę w czystej pamięci podręcznej.