Индексируйте все соответствующие поля, конечно, которые, я уверен, у вас есть
Затем найдите, какие соединения являются самыми дорогостоящими, запустив EXPLAIN SELECT...
Рассмотрите возможность их разделения на отдельный запрос, т.е. сузьте записи, которые вы ищете, затем выполните объединения на этих записях, а не на всех записях
т.е.
SELECT c.*, ....
FROM (SELECT x, y, z .... ) AS c