Запрос не сканирует таблицу в каком-либо определенном порядке; это может произойти, если произойдет обход определенного индекса по порядку (например, сканирование диапазона), что МОЖЕТ быть, потому что вы использовали ORDER BY.
Базы данных просто так не работают. Вы не можете полагаться на их поведение таким образом.
Если вы выполняете полное сканирование таблицы, ожидайте, что это займет некоторое время, особенно если вы недавно удалили много строк. Однако это займет еще больше времени, если у вас много строк.
Убедитесь, что в запросе используются индексы. Посмотрите на план объяснения и убедитесь, что он использует индексы.