Busca demorada

Boa noite, minha pergunta é a seguinte quando faço estas buscas:

SELECT * FROM lojas WHERE (NOME_EMPRESA RLIKE '[[:<:]]Bar[[:>:]]')OR (PESQUISA RLIKE'[[:<:]]Bar[[:>:]]') or (CATEGORIA RLIKE '[[:<:]]Bar[[:>:]]') AND CIDADE_BUSCA = 'Curitiba, pr' ORDER BY PRIORIDADE desc
0.0589 segundos
retorna 29 registros

-----------------------------------------------------------
SELECT * FROM lojas WHERE MATCH(NOME_EMPRESA,PESQUISA,CATEGORIA) AGAINST ('Bar') AND CIDADE_BUSCA = 'Curitiba, pr' ORDER BY PRIORIDADE desc
0.0017 segundos
retorna 0 registros

-----------------------------------------------------------
SELECT * FROM lojas WHERE CIDADE_BUSCA = 'Curitiba, pr' AND (PESQUISA like '%Bar%' or NOME_EMPRESA LIKE '%Bar%' or CATEGORIA LIKE '%Bar%') ORDER BY PRIORIDADE desc
0.0275 segundos
retorna 279 registros

O ideal seria a primeira condição retorna exatamente o que eu quero, mas o problema é que a busca no site se torna muito lenta como resolver esse problema?
a segunda opição é a mais rapida mais não retorna o registro como eu quero.
a terceira é mais rápida que a primeira mais não retorna exatamente o que eu quero.