Maybe I don't understand the problem, but why don't you print your message then execute your query? Is it a buffering problem?
You could do this:
<body>
Please wait...
</body>
<?php
do the query
header("Location:/query result page");
You could pass the query results as a parameter or write a file that would be read by the results page.
If it doesn't flush the buffer, do a flush() before running the query.
F.