how to index for multi-field searches on 15m rows

[gilberta]

I have a 15 million row table that includes the first middle and last names of the person and their parents. The structure and keys are listed below.

The question is what should be indexed and which kind of index, primary, index, all in one index or what to allow fast searches on any significant field or combination of fields.

It works really fast on Last_Name but really bad on other fields.

Any help or pointers to sources of information would be appreciated.

I have looked at the manuals chap 12 and various faq on performance etc.

table births
[tt]
Field Type Key
Last_Name char(21) MUL
First_Name char(16) MUL
Middle_Name char(16)
Name_Suffix char(4)
Birth_Year char(4)
Birth_Month char(2)
Birth_Day char(2)
Birth_County char(20)
Sex char(1)
Mothers_Last_Name char(21)
Mothers_First_Name char(16)
Mothers_Middle_Name char(16)
Fathers_Last_Name char(21)
Fathers_First_Name char(16)
Fathers_Middle_Name char(16)
Fathers_Suffix_Name char(4)

Keyname Unique Field
lname No Last_Name
lname No First_Name
lname No Middle_Name
lname No Name_Suffix
lname No Birth_Day
First_Name No First_Name
[/tt]