Pues tendrás que explicarnos en detalle cómo trabajas, el código de las búsquedas, las tablas y sus índices, relaciones entre ellas, etc. porque así, sin ninguna información, poco podemos hacer
Desde luego, 20 conexiones y 50.000 registros es poquita cosa para que tarde en hacer algo.