Should I create the KEY as following?
KEY(Name, Gender, Phone, Email, DOB) -- Only good when "name=..." in included
OR following will be better?
KEY2(Gender) -- rarely worthwhile indexing on low-cardinality fields
Read about "compound" indexes here: http://mysql.rjweb.org/doc.php/index1
SELECT * FROM contacts WHERE Name = ?; -- INDEX(Name ...)
SELECT * FROM contacts WHERE Phone = ?; -- INDEX(Phone ...)
SELECT * FROM contacts WHERE Name = ? AND Gender = ?; -- Since Name is virtually unique, the test for Gender is unlikely to be useful
SELECT * FROM contacts WHERE Phone = ? AND Email = ?; -- INDEX(Phone, Email ...) or INDEX(Email, Phone, ...); but the issue of uniqueness makes a compound key not that useful.
SELECT * FROM contacts WHERE Name = ? AND Gender = ? AND Phone = ?; -- ditto
Assuming that there are very few duplicate names, duplicate phones, and duplicate emails, I recommend:
INDEX(Email) -- (although you did not have a use case for this)
INDEX(DOB) -- (although you did not have a use case for this)
If a user can search just on Gender (WHERE Gender = 'M'), a table scan is almost as good as having an index.
If a user can search for things other than exact equality (eg, WHERE Name LIKE 'Lee%'), then my recommendations may or may not be good enough. Please provide any such, so we can discuss further. Also, how many rows in the table?