Should SELECT ... FOR UPDATE always contain ORDER BY?

Your example in your question shows that the order of locking depends upon the access method. This access path is not directly decided by the ORDER BY clause of the query, there are many factors that can influence this access path. Therefore, you can't prevent a deadlock just by adding an ORDER BY because you could still have two distinct access paths. In fact by running your test case with the order by and changing the session parameters I was able to cause two session to run into an ORA-60 with the same query.

If the sessions involved have no other lock pending, locking the rows in the same order in all sessions will prevent deadlocks but how can you reliably force this order? Note that this would only prevent this very special case of deadlock anyway. You could still get deadlocks with multiple queries in each session or different plans.

In practice this case is really special and shouldn't happen often anyway: if you're worried about deadlocks, I still think there are easier methods to prevent them.

The easiest way to prevent a deadlock is to use either FOR UPDATE NOWAIT or FOR UPDATE WAIT X (although WAIT X can still trigger a deadlock with values of X superior to the deadlock detection mechanism, currently 3 seconds as of 11g I believe -- thanks @APC for the correction).

In other words, both transactions should ask: give me those rows and lock them but if another user already has a lock return an error instead of waiting indefinitely. It is the indefinite waiting that causes deadlocks.

In practice I would say that most applications with real person users would rather receive an error immediately than have a transaction wait indefinitely for another transaction to finish. I would consider FOR UPDATE without NOWAIT only for non-critical batch jobs.

I think you have misunderstood how FOR UPDATE works. It acquires the locks when the cursor is activated ;that is, when the SELECT is issued.

So, running your query, Transaction 1 will lock the entire table (because you haven't specified a WHERE clause). Transaction 2 will either hang or fail (depending on what you've specified in the WAIT clause) regardless of whether Transaction 1 has issued any DML against the selected set of records. If fact, Transaction 1 doesn't even have to fetch any records; Transaction 2 will hurl ORA-00054 once Transaction 1 has opened the FOR UPDATE cursor.

The deadlock scenario you describe is the classic outcome of an application which uses optimistic locking (i.e. assumes it will be able to acquire a lock when it needs to). The whole point of FOR UPDATE is that it is a pessimistic locking strategy: grab all the locks potentially required now in order to guarantee successful processing in the future.

The inestimable Mr Kyte provides the crucial insight in his blog:

"deadlock detection trumps a waiting period"

In my code I was using NOWAIT in the FOR UPDATE clause of the cursor used in the second session:

cursor c10000 is     select * from order_lines     where header_id = 1234     for update;cursor c1 is     select * from order_lines     where header_id = 1234     and line_id = 9999     for update nowait;

Consequently Session 2 fails immediately and hurls ORA-00054.

However the OP doesn't specify anything, in which case the second session will wait indefinitely for the row to be released. Except that it doesn't, because after a while deadlock detection kicks in and terminates the command with extreme prejudice i.e. ORA-00060. If they had specified a short wait period - say WAIT 1 - they would have seen ORA-30006: resource busy.

Note that this happens regardless of whether we use the verbose syntax...

open c10000;loop    fetch c10000 into r; 

or the snazzier....

for r in c10000 loop

And it really doesn't matter whether Session 1 has fetched the row of interest when Session 2 starts.

tl;dr

So the key thing is, ORDER BY doesn't solve anything. The first session to issue FOR UPDATE grabs all the records in the result set. Any subsequent session attempting to update any of those records will fail with either ORA-00054, ORA-30006 or ORA-00060, depending on whether they specified NOWAIT, WAIT n or nothing.... unless the first session releases the locks before the WAIT period times out or deadlock detection kicks in.

Here is a worked example. I am using an autonmous transaction to simulate a second session. The effect is the same but the output is easier to read.

declare    cursor c1 is        select * from emp        where deptno = 10        for update;    procedure s2     is        cursor c2 is            select * from emp            where empno = 7934 -- one of the employees in dept 10            for update            -- for update nowait            -- for update wait 1            ;        x_deadlock exception;        pragma exception_init( x_deadlock, -60);        x_row_is_locked exception;        pragma exception_init( x_row_is_locked, -54);        x_wait_timeout exception;        pragma exception_init( x_wait_timeout, -30006);        pragma autonomous_transaction;    begin        dbms_output.put_line('session 2 start');        for r2 in c2 loop            dbms_output.put_line('session 2 got '||r2.empno);            update emp            set sal = sal * 1.1            where current of c2;            dbms_output.put_line('session 2 update='||sql%rowcount);        end loop;            rollback;     exception        when x_deadlock then            dbms_output.put_line('session 2: deadlock exception');        when x_row_is_locked then           dbms_output.put_line('session 2: nowait exception');        when x_wait_timeout then            dbms_output.put_line('session 2: wait timeout exception');           end s2;begin    for r1 in c1 loop        dbms_output.put_line('session 1 got '||r1.empno);        s2;    end loop;end;/

In this version I have specified a straightfor update in the second session. This is the configuration the OP uses and as can be seen from the output hurls because a deadlock has been detected:

session 1 got 7782                                                              session 2 start                                                                 session 2: deadlock exception                                                   session 1 got 7839                                                              session 2 start                                                                 session 2: deadlock exception                                                   session 1 got 7934                                                              session 2 start                                                                 session 2: deadlock exception                                                   PL/SQL procedure successfully completed.

What this clearly demonstrates is

1. The first session has locked the whole result set from the go-get, because the second session never gets a lock on that one row, even when the first session has not yet retrieved it.
2. The Deadlock detected exception is hurled even though the second session has not been able to update anything. 1.  The Deadlock detected exception is hurled even though the first session does not update any of the fetched wows.

The code is easily modifiable to demonstrate the different behaviours of the FOR UPDATE variants.