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

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.