Indexe o que parece mais lógico (esperamos que seja óbvio, por exemplo, uma coluna de ID do cliente na tabela CLIENTES).

Em seguida, execute seu aplicativo e colete estatísticas periodicamente para ver o desempenho do banco de dados. RUNSTATS no DB2 é um exemplo, espero que o MySQL tenha uma ferramenta semelhante.

Quando você encontra algumas consultas executadas com frequência fazendo varreduras completas de tabela (ou demorando muito por outros motivos), então, e só então , você deve adicionar mais índices. Não adianta otimizar uma consulta de execução à meia-noite uma vez por mês para que ela possa terminar às 12h05 em vez de 12h07. No entanto, é uma grande melhoria reduzir uma consulta voltada para o cliente de 5 segundos para 2 segundos (isso ainda é muito lento, as consultas voltadas para o cliente devem ser inferiores a um segundo, se possível).

Mais índices tendem a desacelerar as inserções e acelerar as consultas. Então é sempre um ato de equilíbrio. É por isso que você só adiciona índices em resposta específica a um problema. Qualquer outra coisa é otimização prematura e deve ser evitada.

Além disso, revise os índices que você já possui periodicamente para ver se eles ainda são necessários. Pode ser que as consultas que fizeram com que você adicionasse esses índices não sejam mais executadas com frequência suficiente para garantir isso.

Para ser honesto, não acredito que indexar três colunas em uma tabela fará com que você sofra, a menos que planeje armazenar um número realmente grande de linhas :-) - a indexação é bastante eficiente.

Após sua edição, que afirma:

Minha resposta é que 200 registros por dia é um valor extremamente pequeno para um banco de dados, você definitivamente não terá nada com que se preocupar com esses três índices.

Apenas esta semana, importei um dia de transações para uma de nossas tabelas de banco de dados no trabalho e continha 2,1 milhões de registros (obtemos pelo menos uma transação por segundo durante todo o dia de 25 máquinas separadas). E tem quatro teclas compostas separadas que são um pouco mais intensas do que suas três teclas individuais.

Agora concedido, isso está em um banco de dados DB2, mas não consigo imaginar que a IBM seja tão muito melhor do que o pessoal do MySQL que o MySQL só pode lidar com menos de 0,01% da carga do DB2.