String match is too slow in huge table

[Juan Roberto Perilla]

Hi there,

I have a table with 21 million records. The table contains two names, and two surnames, id and other information from several people(21Million persons). We built indexes in order to optimize the search by name and surname, but the search is still too slow(about 8seconds).
An application using Visual Foxpro uses the same table, but with different indexes(we don't know Foxpro neither the indexes built in it) and run faster than mysql, so we think we are doing something wrong with our indexes. The table looks something like this:

|id|name1|name2|surname1|surname2|other information|

Our query is something like this:

select * from sisben where name1 like 'john%' and surname1 like 'smith%';

without the % the search is really fast, but with the '%' the searh time just got too high. We need the % and the foxpro application is actually doing the search this way. The indexes we have built are something like:

create index namesur on sisben (name1,surname1);

and other combinations from name1, name2, surname1 and surname2. If someone could advice us we would really apreaciate it, thanks in advance.