Allora la prima cosa da fare è rivedere gli indici e cercare di ottimizzarli per le ricerche che devi andare a fare.

Poi eventualmente si valuta come gestire le query (es. tramite tabelle temporanee etc.) se proprio non riesci ad ottenere le performance che desideri.