クエリに order by が含まれていない場合、見つかった順序でデータが返されます。クエリを再度実行したときにデータが同じ順序で返されるという保証はありません。
order by 句を含めると、データベースは正しい順序で行のリストを作成し、その順序でデータを返す必要があります。これには多くの余分な処理が必要になり、余分な時間がかかる可能性があります。
クエリが返す可能性のある多数の列を並べ替えるには、おそらく時間がかかります。ある時点でバッファ領域が不足し、データベースがスワッピングを開始する必要が生じ、パフォーマンスが低下します。
返される列を減らして (Select * の代わりに必要な列を指定して)、クエリがより速く実行されるかどうかを確認してください。