Before trying to optimize, you need to know what happens.
In the case of PHP and MySQL (the other BDD), we have 4 points:
BDD side treatment time
PHP side treatment time
data transmission time between server and browser
browser page build time
For point 1 you can check using this:
$start_time = microtime(true); // Antes
$result = @mysqli_query($handle,$query);
$end_time = microtime(true); // Depois
$ecart = $end_time - $start_time; // Diferença
For point 2, you can do the same thing: put a microtime (true) at the top of the PHP page, one on the last line, calculate the difference and echo the result.
After that, you will be able to see if the exposure time is the same as the calculation: if the "PHP" time is 0.03 seconds, the Mysql time of 0.01 which takes 3 seconds to see the page, this means that the problem does not happen in Point 1 or Point 2 ...
On Point 4, there is one thing to know: I do not know the structure of your page, but browsers start displaying the contents of the pages with tables, only after receiving the whole code.
For example, if you have 500 results (after the query) and you put the results in a table only (then you have the TABLE tag at the top of the page, then 500 TD and TR tags for the 500 results and at the bottom of the page tag of the TABLE), the browser will expect to receive the 500 data BEFORE starting the show anything.
To avoid this, you need to open and close the table, for example every 30 results. So the user will quickly see the top 30 when the other results will continue to arrive. This will not change the "real" time but it will change the perception of time a lot!
Last chance: Your internet connection is weak.
PS: a detail. The "mysql" module is considered obsolete. Need to use mysqli.