I've created an index with the statement create index `usuario_pasta_situacao` on `mensagens` (codusuario, codpasta, situacao);
And for mensagenspara table this index create index `mensagem_usuario_pasta_situacao_idx` on `mensagenspara` (codmensagem, codusuario, codpasta, situacao); This is query used: SELECT m.codmensagem, m.codprioridade, m.codusuario, m.codmensagemoriginal, m.codmensagempai, m.assunto, m.dataenvio, m.horaenvio, m.datalimite, m.horalimite, m.anexo, m.tipo, u.nome, up.nome as nomepara, mp.codrespondida, mp.codmensagempara, mp.codusuario as codusuariopara, mp.situacao FROM mensagens m, mensagenspara mp, usuarios u, usuarios up WHERE m.ativo=1 AND m.codmensagem=mp.codmensagem AND m.codusuario=u.codusuario AND mp.codusuario=up.codusuario AND ( ( m.codpasta=1 AND m.codusuario = 916 AND m.situacao <> 0 ) OR ( mp.codpasta=1 AND mp.codusuario = 916 AND mp.situacao <> 4 ) ) GROUP BY m.codmensagem ORDER BY m.dataenvio DESC, m.horaenvio DESC, m.codmensagem DESC LIMIT 0,20 And this is what explain shows: id: 1 select_type: SIMPLE table: m type: ALL possible_keys: PRIMARY,usuario_pasta_situacao key: key_len: ref: rows: 68337 Extra: Using where; Using temporary; Using filesort ------------------------------- id: 1 select_type: SIMPLE table: u type: eq_ref possible_keys: PRIMARY,codusuario key: PRIMARY key_len: 4 ref: teste2.m.codusuario rows: 1 Extra: ------------------------------- id: 1 select_type: SIMPLE table: mp type: ref possible_keys: mensagem_usuario_pasta_situacao_idx key: mensagem_usuario_pasta_situacao_idx key_len: 5 ref: teste2.m.codmensagem rows: 3 Extra: Using where ------------------------------- id: 1 select_type: SIMPLE table: up type: eq_ref possible_keys: PRIMARY,codusuario key: PRIMARY key_len: 4 ref: teste2.mp.codusuario rows: 1 Extra: ------------------------------- I'm a little consufed with these indexes... could you please suggest a better way to create them? And again, thank you for your attention and patience :-)