O problema com a pesquisa do tipo '%keyword%' é que não há como pesquisá-la com eficiência em uma tabela normal, mesmo se você criar um índice nessa coluna. Pense em como você ficaria com aquela corda na lista telefônica. Na verdade, não há como otimizá-lo - você precisa escanear toda a lista telefônica - e é isso que o MySQL faz, um escaneamento completo da tabela.

Se você alterar essa pesquisa para 'keyword%' e usar um índice, poderá obter uma pesquisa muito rápida. Parece que isso não é o que você quer, no entanto.

Então, com isso em mente, usei bastante indexação/pesquisa de texto completo, e aqui estão alguns prós e contras:

Prós

• Muito rápido
• Retorna os resultados classificados por relevância (por padrão, embora você possa usar qualquer classificação)
• Palavras de parada podem ser usadas.

Contras

• Funciona apenas com tabelas MyISAM
• Palavras muito curtas são ignoradas (o mínimo padrão é 4 letras)
• Requer SQL diferente na cláusula where, portanto, você precisará modificar as consultas existentes.
• Não corresponde a strings parciais (por exemplo, 'palavra' não corresponde a 'palavra-chave', apenas 'palavra')

Aqui está uma boa documentação sobre pesquisa de texto completo .

Outra opção é usar um sistema de busca como Sphinx . Pode ser extremamente rápido e flexível. Ele é otimizado para pesquisa e se integra bem ao MySQL.