Eu também enfrentei um problema de busca lenta (MySQL, InnoDB). Finalmente descobri que innodb_buffer_pool_size está definido para 8 MB por padrão para o meu sistema, o que não é suficiente para lidar com a consulta. Depois de aumentá-lo para 1 GB, o desempenho parece bom:
Duration / Fetch
353 row(s) returned 34.422 sec / 125.797 sec (8MB innodb buffer)
353 row(s) returned 0.500 sec / 1.297 sec (1GB innodb buffer)
ATUALIZAÇÃO:
Para alterar innodb_buffer_pool_size, adicione isso ao seu my.cnf
innodb_buffer_pool_size=1G
reinicie seu mysql para fazer efeito
Referência:Como alterar o valor de innodb_buffer_pool_size no MySQL no Mac OS?