Cita:  
					Iniciado por xcars 
  pues muchas veces no falta con indexar... a veces es necesario indexar BIEN. 
Debes conocer un poco sobre la teoria de los indices y ver si realmente tus indices andan bien, ver los criterios de busqueda y comparar si estos se apegan a los indices, porque eso de "recorrer" toda la tabla es una busqueda secuencial no x indices.
Yo tengo uan BD con 10 M y pues con buenos indices anda bien.
    El problema puede ser el siguiente, me hacen más de 10 busquedas por segundo. 
La tabla tiene los siguientes campos:  
 
La busqueda la realizo de la siguiente manera: 
$sacar = 	"SELECT DISTINCT idsong\r\n" . 
		"FROM tags AS found_song\r\n" . 
		"WHERE (tag = '{$tags[0]}')\r\n";
for ($x = 1; $x < count($tags); $x++) {
  $sacar .= "AND (0 < (SELECT COUNT(id) FROM tags WHERE tag = '{$tags[$x]}' AND idsong = found_song.idsong))\r\n";
}  
Como la mejorariais??? es importante, gracias!