I've never done this but thought about it.
In your PHP script, output the meta refresh tag set at 1 sec and HTML saying "wait" or whatever. Then at the end start your mySQL queries. Make sure to set a long timeout for your script.
What I'd expect to happen is the meta refresh and HTML should be outputed to the client for them to view. But, the script would continue to run queries, keeping the connection open (to the client). When the queries are done the connection is closed and the meta refresh is activated refreshing the page.
Again, I havn't tested this and I'm not sure if it'll work. But it was a thought. Also, maybe check to see how vBulletin does it.