ayuda con select y indexacion

[diegomel]

Hola a todos, tengo un problema que me esta volviendo loco ajaj.
resulta que yo estoy trabajando con una base en mysql la cual la tabla tiene mas de 320.000 registros .
Yo necesito hacer el siguiente select

$consulta = mysql_query("SELECT publeje.nombre nombre,publeje.tomo t,publeje.folio f,publeje.fecha_nac fechanac,publeje.tm,publeje.fm,publeje.tp,publeje. fp,a.tomo,a.folio,a.nombre np,b.tomo,b.folio,b.nombre nm from publeje LEFT JOIN publeje as a on (publeje.tp=a.tomo and publeje.fp=a.folio) LEFT JOIN publeje as b on (publeje.tm=b.tomo and publeje.fm=b.folio) where publeje.nombre like '$busqueda%' and publeje.tomo is not null and publeje.folio is not NULL order by publeje.nombre");

lo que estoy haciendo ahi es una tabla llamada publeje, la estoy relacionando con sigo misma 2 veces mas o sea me quedarian 3 tablas iguales relacionadas.

el problema que tengo , (creo) es que cuando reincio el servidor , osea ejecuto por primera ves la consulta, y busco por ej con m (que daria como resultado 28000 registros) el rigido empieza a leer por 30 seg o 40 seg , luego de eso anda instanataneo ( supongo que lo pone el memoria el indice).
Ahora mi pregunta y duda es: con esa query que tendria que indexar exactamente?
2do es normal que haga eso de leer el rigido tanto tiempo por primera ves?.
yo tengo reindexado lo siguiente.
en 1 tomo y folio juntos, en otro, nombre,tomo y folio (3 en 1) y en otro lado por fecha(para otra busqueda).

Espero que se haya entendido y puedan ayudarmen porque me estoy volviendo loco con esto, no se si es normal que haga esto el mysql o yo estoy haciendo algo mal.

Saludos y gracias.