Se la tua query non contiene un ordine, restituirà i dati nell'ordine in cui è stato trovato. Non vi è alcuna garanzia che i dati vengano restituiti nello stesso ordine quando esegui di nuovo la query.
Quando includi una clausola order by, il dabatase deve creare un elenco delle righe nell'ordine corretto e quindi restituire i dati in quell'ordine. Questo può richiedere molta elaborazione extra che si traduce in tempo extra.
Probabilmente ci vuole più tempo per ordinare un numero elevato di colonne, che la tua query potrebbe restituire. Ad un certo punto si esaurirà lo spazio nel buffer e il database dovrà iniziare a scambiare e le prestazioni diminuiranno.
Prova a restituire meno colonne (specifica le colonne che ti servono invece di Seleziona *) e verifica se la query viene eseguita più velocemente.
