A quantidade de indexação e a linha de fazer demais dependerão de muitos fatores. Em tabelas pequenas, como sua tabela de "categorias", você geralmente não quer ou precisa de um índice e isso pode prejudicar o desempenho. A razão é que leva E/S (ou seja, tempo) para ler um índice e, em seguida, mais E/S e tempo para recuperar os registros associados às linhas correspondentes. Uma exceção é quando você consulta apenas as colunas contidas no índice.

No seu exemplo, você está recuperando todas as colunas e com apenas 22 linhas e pode ser mais rápido apenas fazer uma varredura na tabela e classificá-las em vez de usar o índice. O otimizador pode/deve estar fazendo isso e ignorando o índice. Se for esse o caso, o índice está apenas ocupando espaço sem nenhum benefício. Se sua tabela de "categorias" for acessada com frequência, você pode considerar fixá-la na memória para que o servidor db a mantenha acessível sem precisar acessar o disco o tempo todo.

Ao adicionar índices, você precisa equilibrar o espaço em disco, o desempenho da consulta e o desempenho da atualização e inserção nas tabelas. Você pode obter mais índices em tabelas que são estáticas e não mudam muito, ao contrário de tabelas com milhões de atualizações por dia. Você começará a sentir os efeitos da manutenção do índice nesse ponto. O que é aceitável em seu ambiente é e só pode ser determinado por você e sua organização.

Ao fazer sua análise, certifique-se de gerar/atualizar suas estatísticas de tabela e índice para que você possa ter certeza de cálculos precisos.