Prova ad aggiungere qualche indice sui campi maggiormente richiamati nelle query,

oppure a partizionare le tabelle piu' corpose,

oppure utilizza la funzione optimize su tabelle che hanno subito vari delete...