Podrías crear un índice por apellido1 y apellido2 si no los tienen. Esto de todas maneras no te valdrá de nada si usas LIKE '%garcia%', deberías usar sólo el % final, LIKE 'garcia%'. Creo que en este caso el resultado sería el mismo, y acelerarías mucho la consulta, eso sí, los índices tendrías que tenerlos igualmente.
|