1) Смотрите план выполнения запроса, тогда все станет на свои места: когда нумеруються записи, а когда происходит сортировка выборки.
2) ORDER BY во вложенных запросах можно использовать в коммандном SQL. Но попробуйте в PL/SQL блоке объявить такой курсор - шиш чего получится. Выход - использовать открытие динамического курсора (EXECUTE IMMEDIATE и все такое).
3) В реляционной модели, когда структура базы/таблиц создаеться девелопером и заранее известна практически всегда можно обойтись без ORDER BY используя индексы. Естественно при денормализации и траты пространства (памяти и дисковой и оперативной). Зато однозначный выигрыш в производительности.
Другое дело, когда структура таблиц заранее неизвестна и создаеться юзером; и есть какие-то причины, по которым ее нельзя сгенерить в статический вид. (Вроде бы такие хреновины называються Мета-данные.) Или пользователь задает, что мол хочу сортировать и по этой колонке и по пятой и по десятой. Тогда без ORDERA не обойтись.
4) И вообще, лафа вархаузерам - выполняеться запрос 0,1 секунду или 5 или 25 - по фигу, юзер подождет. В конце концов у системы ограниченный круг юзеров. В он-лайне такие штуки не прокатывают.