Você tem que entender no MySQL (no caso do InnoDB) que ele usa apenas o prefixo mais à esquerda de seus índices. Portanto, se o índice estiver em Field1 + Field2, consultando apenas com Field2 em WHERE não pode fazer uso de todo o índice.

E se Field1 + Field2 + Field3 é o índice, uma consulta com apenas Field1 & Field3 em ONDE o mesmo aconteceria.

Opção 1

Você teria que criar um índice separado para cada cenário de pesquisa se deseja otimizar cada pesquisa. No entanto, se as tabelas forem grandes, os índices também se tornarão extremamente grandes. Se essas consultas de pesquisa forem feitas com muita frequência, valeria a pena.

Opção 2

Você pode usar um truque bacana se suas pesquisas tiverem uma baixa seletividade (ou seja, Gênero) colocando as colunas de baixa seletividade mais à esquerda e use Gender IN(M, F) para incluí-lo em ONDE cláusula junto com a(s) outra(s) coluna(s) para fazer uso de todo o índice.