1. Sempre use EXPLAIN(QUERY) para criar perfil e entender como o MySQL está analisando suas consultas.
2. Verifique seus INDEXes, o MySQL provavelmente está selecionando os índices errados para a seleção.
3. 
   Tente usar as dicas SELECT e INDEX. http://dev.mysql.com/doc/refman /5.1/en/index-hints.html .
   
   SELECT * FROM table1 USE INDEX (col1_index,col2_index)WHERE col1=1 AND col2=2 AND col3=3;
   
   SELECT * FROM table1 IGNORE INDEX (col3_index)WHERE col1=1 AND col2=2 AND col3=3;