If I were in your position, my first thoughts would be:

Do my tables have all of the necessary/appropriate indexes?  Missing
indexes can *reall* slow a query, especially a join.

Are my SQL queries as efficient as they could be?  Use EXPLAIN to see
which indexes are being used.

Does my MySQL server have large enough internal buffers, especially the
key buffer which is used to store indexes for tables?  It's no use
having indexes if the server cannot keep them in memory long enough to
use them.

By the way, this is a Java database programming newsgroup.  You're using
PHP, not Java.  Why on earth did you post here, and not a PHP-related
group?  Fortunately, your problems are likely to be unrelated to your
choice of programming language.

David Harper
Cambridge, England