Os índices não necessariamente melhoram o desempenho. Para entender melhor o que está acontecendo, ajudaria se você incluísse o explain para as diferentes consultas.

Meu melhor palpite é que você tenha um índice em id_state ou mesmo id_state, id_mp que pode ser usado para satisfazer o where cláusula. Em caso afirmativo, a primeira consulta sem o order by usaria este índice. Deve ser bem rápido. Mesmo sem um índice, isso requer uma varredura sequencial das páginas nas orders mesa, que ainda pode ser muito rápido.

Então, quando você adiciona o índice em creation_date , o MySQL decide usar esse índice em vez do order by . Isso requer a leitura de cada linha no índice e a busca da página de dados correspondente para verificar o where condições e retornar as colunas (se houver correspondência). Essa leitura é altamente ineficiente, pois não está na ordem de "página", mas conforme especificado pelo índice. Leituras aleatórias podem ser bastante ineficientes.

Pior, mesmo que você tenha um limit , você ainda precisa ler todo porque todo o conjunto de resultados é necessário. Embora tenha salvo uma classificação em 38 registros, você criou uma consulta extremamente ineficiente.

A propósito, esta situação piora significativamente se os orders tabela não cabe na memória disponível. Então você tem uma condição chamada "thrashing", onde cada novo registro tende a gerar uma nova leitura de E/S. Portanto, se uma página tiver 100 registros, a página poderá ser lida 100 vezes.

Você pode fazer com que todas essas consultas sejam executadas mais rapidamente tendo um índice em orders(id_state, id_mp, creation_date) . O where cláusula usará as duas primeiras colunas e o order by usará o último.