Bases de Datos - busquedas rápidas con bbdd grandes

Hola!

Me gustaria saber si alguien me puede echar una mano. He subido una base de datos de Access a MySQL con 15 millones de registros separados en en 10 tablas de 1,5 millones de registros cada una. Mi problema esta en que tengo que realizar busquedas rápidas pero cada vez que hago un select de cualquiera de las tablas tarda muchisimo. ¿Podría alguien decirme dónde esta el problema? ¿Debería utilizar otra plataforma de bases de datos? ¿Hay alguna forma de optimizar las búsquedas? Muchas Gracias de antermano!!

Fíjate por qué campos filtras las búsquedas.
Indexa las tablas por esos campos.

Si te sigue yendo lento, intenta un particionamiento vertical, siendo una de las tablas la que contiene los campos más demandados, y la otra contendrá el resto.
Ambas deben estar indexadas.

Qué tipo de búsquedas realizas? Cadenas de caracteres?
Si es así intenta cambiar el modelo de datos de tal forma que se asemeje al modelado en copo de nieve o snow-flake con el fin de que las búsquedas se hagan cruzando valores numéricos (más fáciles de indexar y más rápidos de cruzar).