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).

Viscose

What if your Transaction 2 only locks Rows A and C while transaction 1 locks B, C and D? In that case an order by is useless, so you will only be able to reduce the probability of occurance for a fraction of the deadlocks. – Gabo

@Gabo There would be no deadlock. One transaction would simply wait for another until it unlocks C. – Viscose

It is easy to prove that the locking is done before the fetching: create a large table, run SELECT /*+ FIRST_ROW */ * FROM table ORDER BY pk and you will see that the query takes a long time to fetch the first few rows (because it locked all rows in the execute phase). I agree with you though that the locking is done in the order specified by the ORDER BY clause. This could be used to prevent deadlocks although there are easier methods IMO. – Anneliese

Why did you tag it with MySQL? – Sausa

@a_horse_with_no_name Because MySQL also supports this syntax and I'm interested in its behavior too. – Viscose

That syntax is supported by (nearly) all DBMS. – Sausa

Answer 1

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.

Anneliese

But what it I do want to wait on other transaction to finish and just want to prevent a deadlock? Wouldn't ORDER BY be enough for such scenario? – Viscose

If all transactions lock the rows in the same order, you won't have a deadlock you're right. – Anneliese

Actually the second session can hurl ORA-00060 even if it specifies a WAIT time, provided the wait is longer than the deadlock timeout. – Centre

@APC: thanks, didn't know about that. Interesting link you've provided in your answer. – Anneliese

@BrankoDimitrijevic: the locking depends upon the order in which you lock the rows. This order is not always the same as the ORDER BY clause. You could get different access paths with the same query even with the same ORDER BY clause, therefore this method could still let some deadlocks happen. – Anneliese

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.

Centre

"It acquires the locks when the cursor is activated" - that's not actually true. It locks rows on-by-one as they are fetched from the cursor. So you can have a point in time when some rows are locked but some are still waiting to be locked. Now in this particular example in my question, if Oracle decides to optimize the query and lock the whole table, there cannot be a deadlock since there is only one lock (can anyone confirm this is actually allowed?), but if that is the case imagine there is a WHERE that limits the locking to some subset of all rows in the table. – Viscose

BTW, the above is Oracle-specific. I'm not sure how MySQL behaves. – Viscose

@Centre Each row has an individual lock so it is not possible to lock all rows at the same time. This is why you can have a deadlock with two sessions each with only one query although in practice you have to engineer a really special case to observe this. – Anneliese

With all due respect have you tried this? In Oracle? If Transaction 1 has opened a cursor with FOR UPDATE Transaction 2 will hurl ORA-00054 when it tries to open the FOR UPDATE cursor in its session. – Centre

@Centre We are talking about separate client sessions. ORA-00060 (a deadlock) can be reproduced with a cursor on SELECT ... FOR UPDATE - see the edit in my question. – Viscose

@APC: it's quite possible to engineer such a test case. With a sufficiently large table and a pk in the same order as the rows: make one session lock the rows in the ascending pk order, make another session lock the rows in descending order (both queries should have a FIRST_ROW hint) and you should get an ORA-600. This is possible because the locking of the rows is not instantaneous (even though both sessions will try to lock all rows before fetching). – Anneliese

@APC: your example won't work with two sessions: session 2 will not raise an error, it will just wait nicely. Try it. Your assertion "Any subsequent session attempting to update any of those records will fail" is wrong. – Anneliese