No, il limite non è imposto dal browser ma da php: è possibile che nella seconda esecuzione mysql si fosse preparato ad una simile mole di lavoro e quindi sia stato più rapido.

Hai due strade per aggredire il problema: se lo script dev'essere eseguito solo sul tuo server di sviluppo, allora puoi tranquillamente settare il max_execution_time a 0, il che permette agli script di andare avanti per sempre.

Se, invece, dev'essere eseguito su un server in produzione, devi metterti in condizioni di poter richiamare più volte lo script, facendo in modo che ogni volta processi solo un numero ridotti di record, ma che alla chiamata successiva proceda di lì in poi:

script.php -> Processa 100 record dall'inizio della query (dallo 0 al 99), poi richiama...
script.php?indiziada=100 ->Processa altri 100 record (dal 100 al 199), poi richiama...

e così via; in questo modo potrai tenere sotto controllo il tempo di esecuzione massimo di ogni singola chiamata, ma potrai processare grandi moli di dati in più esecuzioni sequenziali.