What is a deadlock in a database?

In general, deadlock means that two or more entities are blocking some sources, and none of them is able to finish, because they are blocking sources in a cyclic way.

One example: Let's say I have table A and table B, I need to do some update in A and then B and I decide to lock both of them at the moment of usage (this is really stupid behaviour, but it serves it's purpose now). At the same moment, someone else does the same thing in opposite order - locks B first, then locks A.

Chronologically, this happens:

proc1: Lock A

proc2: Lock B

proc1: Lock B - starts waiting until proc2 releases B

proc2: Lock A - starts waiting until proc1 releases A

Neither of them will ever finish. That's a deadlock. In practice this usually results in timeout errors since it is not desired to have any query hanging forever, and the underlying system (e.g. the database) will kill queries that don't finish in time.

One real world example of a deadlock is when you lock your house keys in your car, and your car keys in your house.

What is a deadlock

A deadlock happens when two concurrent transactions cannot make progress because each one waits for the other to release a lock, as illustrated in the following diagram.

Because both transactions are in the lock acquisition phase, neither one releases a lock prior to acquiring the next one.

Recovering from a deadlock situation

If you're using a Concurrency Control algorithm that relies on locks, then there is always the risk of running in a deadlock situation. Deadlocks can occur in any concurrency environment, not just in a database system.

For instance, a multithreading program can deadlock if two or more threads are waiting on locks that were previously acquired so that no thread can make any progress. If this happens in a Java application, the JVM cannot just force a Thread to stop its execution and release its locks.

Even if the Thread class exposes a stop method, that method has been deprecated since Java 1.1 because it can cause objects to be left in an inconsistent state after a thread is stopped. Instead, Java defines an interrupt method, which acts as a hint as a thread that gets interrupted can simply ignore the interruption and continue its execution.

For this reason, a Java application cannot recover from a deadlock situation, and it is the responsibility of the application developer to order the lock acquisition requests in such a way that deadlocks can never occur.

However, a database system cannot enforce a given lock acquisition order since it's impossible to foresee what other locks a certain transaction will want to acquire further. Preserving the lock order becomes the responsibility of the data access layer, and the database can only assist in recovering from a deadlock situation.

The database engine runs a separate process that scans the current conflict graph for lock-wait cycles (which are caused by deadlocks). When a cycle is detected, the database engine picks one transaction and aborts it, causing its locks to be released, so that the other transaction can make progress.

Unlike the JVM, a database transaction is designed as an atomic unit of work. Hence, a rollback leaves the database in a consistent state.

Deadlock priority

While the database chooses to rollback one of the two transactions being stuck, it's not always possible to predict which one will be rolled back. As a rule of thumb, the database might choose to roll back the transaction with a lower rollback cost.

Oracle

According to the Oracle documentation, the transaction that detected the deadlock is the one whose statement will be rolled back.

SQL Server

SQL Server allows you to control which transaction is more likely to be rolled back during a deadlock situation via the DEADLOCK_PRIORITY session variable.

The DEADLOCK_PRIORITY session can accept any integer between -10 and 10, or pre-defined values such as LOW (-5), NORMAL (0) or HIGH (5).

In case of a deadlock, the current transaction will roll back, unless the other transactions have a lower deadlock priority value. If both transactions have the same priority value, then SQL Server rolls back the transaction with the least rollback cost.

PostgreSQL

As explained in the documentation, PostgreSQL does not guarantee which transaction is to be rolled back.

MySQL

MySQL tries to roll back the transaction that modified the least number of records, as releasing fewer locks is less costly.