Should SELECT … FOR UPDATE always contain ORDER BY

Question

Let's say we execute...

SELECT * FROM MY_TABLE FOR UPDATE

...and there is more than one row in MY_TABLE.

Theoretically, if two concurrent transactions execute this statement, but it happens to traverse (and therefore lock) the rows in different order, a deadlock may occur. For example:

• Transaction 1: Locks row A.
• Transaction 2: Locks row B.
• Transaction 1: Attempts to lock row B and blocks.
• Transaction 2: Attempts to lock row A and deadlocks.

The way to resolve this is to use ORDER BY to ensure rows are always locked in the same order.

So, my question is: will this theoretical deadlock ever occur in practice? I know there are ways to artificially induce it, but could it ever occur in the normal operation? Should we just always use ORDER BY, or it's actually safe to omit it?

I'm primarily interested in behavior of Oracle and MySQL/InnoDB, but comments on other DBMSes would be helpful as well.

--- EDIT ---

Here is how to reproduce a deadlock under Oracle when locking order is not the same:

Create the test table and fill it with some test data...

CREATE TABLE DEADLOCK_TEST (
    ID INT PRIMARY KEY,
    A INT 
);

INSERT INTO DEADLOCK_TEST SELECT LEVEL, 1 FROM DUAL CONNECT BY LEVEL <= 10000;

COMMIT;

...from one client session (I used SQL Developer), run the following block:

DECLARE
    CURSOR CUR IS 
        SELECT * FROM DEADLOCK_TEST
        WHERE ID BETWEEN 1000 AND 2000 
        ORDER BY ID 
        FOR UPDATE;
BEGIN
    WHILE TRUE LOOP
        FOR LOCKED_ROW IN CUR LOOP
            UPDATE DEADLOCK_TEST 
            SET A = -99999999999999999999 
            WHERE CURRENT OF CUR;
        END LOOP;
        ROLLBACK;
    END LOOP;
END;
/

From a different client session (I simply started one more instance of SQL Developer), run that same block, but with DESC in the ORDER BY. After few seconds, you'll get the:

ORA-00060: deadlock detected while waiting for resource

BTW, you'll likely achieve the same result by completely removing the ORDER BY (so both blocks are identical), and adding the...

ALTER SESSION SET OPTIMIZER_INDEX_COST_ADJ = 1;

...in front of one block but...

ALTER SESSION SET OPTIMIZER_INDEX_COST_ADJ = 10000;

...in front of the other (so Oracle chooses different execution plans and likely fetches the rows in different order).

This illustrates that locking is indeed done as rows are fetched from the cursor (and not for the whole result-set at once when the cursor is opened).

Answer 1

Look at it another way. Barring bizarre implementations, omitting the ORDER BY clauses is almost certain to yield the same order every time, but including them provides an opportunity for 'maintenance' programmers and other well-wishers to fiddle with them, or some of them, so that they have some finite probability of ending up different over the life of the application.

Answer 2

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.

Answer 3

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.