Hola gabyrsh, mira, con respecto a tu pregunta sobre porque la primera vez que realizas una busqueda tarda mas que las siguientes, es por la cache que tiene el servidor de MySQL.
Yo trabajo con una base de datos que tiene al igual que tu, millones de registros. afortunadamente para mi, pude partir las tablas en base a la fecha, teniendo una tabla por mes... aun asi, cuando intento consultar en todas las tablas (gracias a uns sistema especializado de UNION entre tables) mi servidor MySQL se tarda demasiado : es natural.
pero, al mismo tiempo que indexa y obtiene los registros, guarda en cache la cadena de busqueda y el resultado, por eso es que la segunda busqueda suele ser mas rapida. Claro, si tu cambias la sentencia SQL tan solo por unos parametros, la cache se vuelve inservible y necesita reindexar...
mira, echale un ojo a estos enlaces, aqui puedes informarte sobre esto :
http://blackshell.usebox.net/archivo/617.php http://www.databasejournal.com/featu...le.php/3110171
Con respecto a como mejorar tu busqueda, se me ocurre una manera...
Entiendes el modelo ER ? (entidad relacion).
si lo entiendes, construye una tabla catalogo de palabaras clave, como un diccionario, y construye ademas una relacion entre las palabras clave y los registros de tus canciones.
Por ejemplo, la cancion de cielito lindo, contiene palabras clave, como "sierra" "morena", "cielito", "lindo", "canta", etc.
para evitar el crecimiento de tu catalogo, evita poner palabras verbos conjugados, es decir, en lugar de poner "juegas", "juego", "jugamos", pon solo "jugar" y no añadas enlaces a canciones que contienen verbos conjugados, en simples palabras, en tu catalogo mete unicamente nombres, verbos en su forma simple, sustantivos y adjetivos.
Primero construye tu diccionario, una vez que lo tengas entonces realiza una busqueda fulltext en tus canciones y por cada cancion y palabra coincidentes, añade un registro, uuuuuuuuuy, eso te darian posiblemente mas de 10 millones de registros... pero... partelos en tablas que contengan palabras que empiecen con una letra, luego te enseño como unirlas...
Esa es una idea, pero pueden haber mejores, pregunta en mas foros y tambien tu, analiza que seria mejor... si tienes dudas con gusto te respondo.
saludos