Se sua consulta não contiver um pedido até então, ela retornará os dados em qualquer ordem em que foram encontrados. Não há garantia de que os dados serão retornados na mesma ordem quando você executar a consulta novamente.

Quando você inclui uma cláusula order by, o dabatase precisa construir uma lista das linhas na ordem correta e, em seguida, retornar os dados nessa ordem. Isso pode exigir muito processamento extra, o que se traduz em tempo extra.

Provavelmente leva mais tempo para classificar um grande número de colunas, que sua consulta pode estar retornando. Em algum momento, você ficará sem espaço de buffer e o banco de dados terá que começar a trocar e o desempenho diminuirá.

Tente retornar menos colunas (especifique as colunas que você precisa em vez de Select *) e veja se a consulta é executada mais rapidamente.