Otimizar Busca em Categorias retornando ocorrências

[phpando 0]

Boa noite.

Estou procurando otimizar uma pesquisa que retorne o número de Produtos de cada Categoria, que contenham determinada palavra-chave.

O banco de dados de produtos é reduzido, cerca de 500 produtos e meu cliente deseja a busca em 2 campos distintos. Outra questão é que se o usuario digitar 2 palavras, deve buscar as duas separadamente, ou seja, "PALAVRA BUSCADA" deve ter 2 LIKES.

Segue os exemplos que utilizei.
Se alguém souber como otimizar esta query, agradeço, pois estou com as "placas coladas" de tanto tentar uma solução.

1. Sem fazer COUNT(), retorna corretamente as categorias, de forma rápida:

SELECT 
   C.nome 
FROM 
   Produtos_Categorias C 
INNER JOIN 
   Produtos P ON P.id_cat = C.id AND (P.nome LIKE '%PALAVRA%' OR P.resumo LIKE '%PALAVRA%') 
GROUP BY 
   C.id 

/* 0 rows affected, 2 rows found. Duration for 1 query: 0,047 sec. */


2. Realizando COUNT(), retorna corretamente as categorias, mas muito lentamente:

SELECT 
   C.nome, 
   COUNT(P.id) AS num_ocorrencias 
FROM 
   Produtos_Categorias C 
INNER JOIN 
   Produtos P ON P.id_cat = C.id AND (P.nome LIKE '%PALAVRA%' OR P.resumo LIKE '%PALAVRA%') 
GROUP BY 
   C.id 

/* 0 rows affected, 2 rows found. Duration for 1 query: 12,262 sec. */

[Motta 645]

http://dev.mysql.com/doc/refman/5.0/en/fulltext-search.html