Si notas lentitud extrema .. a partir de los 50-60 mil registros q dice Necros .. pasate a PostgreSQL si el volumen de informacion es alto o con perspectivas de crecer ampliamente.
Eso si, PostgreSQL no es tan rapido en volumenes de informacion "pequeños".
De todas formas te dejo una comparativa entre Mysql, PostgreSQL, Interbase y SAP DB. Para que te hagas una idea sobre Mysql y otras BD con diferentes pruebas (incluye codigo fuente de las pruebas por si deseas testearlo tu mismo).
<a href='ir.asp?http://www.arrakis.es/~qenda/Articles/ArticleDB/Articulo_DB_9-5-01a.htm' target='_blank'>http://www.arrakis.es/~qenda/Articles/Ar...</a>
Un saludo,