ayuda con select y problema de NULL

[diegomel]

Hola a todos, tengo la siguiente consulta a mysql

$sql_1 = mysql_query("SELECT nombre,tomo,folio from publeje where nombre like '$busqueda%' and (tomo is not NULL and folio is not NULL) ") or die(mysql_error());

mi problema esta en que lo que necesito es hacer la consulta de esa manera que el tomo y folio no sean nulos, el problema es que de esa forma las primeras busquedas tardan como 6 seg debido a esa condifcion, yo tengo indexado el tomo y folio (juntos) y el nombre .
hay alguna forma de hacer esa consulta pero que sea mas rapido la respuesta?.
aclaro que estoy buscando en 240.000 registros.
Lo raro es que si no pongo la condicion de nulos osea solo que nombre like busqueda anda rapido.
Espero que me puedan ayudar.
esta bien indexados asi osea indexar nombre, y (tomo y folio)? o hay alguna forma de indexar mejor?-

Saludos y gracias.