This is the first post in a small series dedicated to analysing and dealing with deadlocks in PostgreSQL, and provides a rather gentle introduction to the topic.

What is a deadlock?

A deadlock is a situation in which a DBMS cannot execute all concurrent transactions running in a specific point in time. It must, and it will, automatically kill some of them in order to complete others.

Basic case is two transactions waiting for each other to complete. Since both are waiting none can make any progress, so the DBMS can either kill one of those and let the other finish or just wait forever. Since the latter option is less desirable, the DBMS will happily kill one as soon as the situation is detected (by the way: Postgres chooses which one and you can’t know the choice in advance).

There are theoretical and practical reasons why a DBMS can’t “magically” guarantee deadlock-free transactions, so this is something that just happens from time to time.

What does “waiting for a transaction” mean?

DBMSs try their best to ensure multiple transactions can work concurrently without interfering with one another, but sometimes this is simply not possible. To avoid data corruption Postgres conceptually maintains one lock for every table and every row in the database, and it will grant it only to one transaction at a time, typically the first one that starts working on it. Any others that come afterwards will have to wait until the former transaction is finished, its locks are released and are re-granted before proceeding. Since transactions without locks are basically temporarily suspended no data corruption happens, which is good!

But what if transaction T1 owns a lock L2 that is wanted by T2, while T2 has by chance a lock L1 that T1 is interested in? Well then T1 waits for T2 while T2 waits for T1. They will both wait forever. You got it… It’s a deadlock!

MVCC, or, how Postgres tries to minimize lock use

Since deadlocks only happen when locks are granted, one strategy to mitigate them is to minimize lock use, and Postgres of course attempts to do that. This is also good for performance, since less locks mean less time wasted waiting.

Postgres implements a mechanism called MVCC that prevents locking in a number of cases, it is similar in concept to copy-on-write in filesystems.

Every time you UPDATE a row, Postgres does not overwrite it, instead it creates a new copy and still keeps the old version around – the same happens when you DELETE a row (more details on MVCC are available here).

This has a lot of design consequences, but mainly:

• you need to run the VACUUM command from time to time, to get rid of very old rows no longer in use. AUTOVACUUM is enabled by default, so you typically don’t need to worry;
• read statements (SELECT) never block other read statements (SELECT);
• read statements (SELECT) never block write statements (INSERT, UPDATE or DELETE);
• write statements (INSERT, UPDATE or DELETE) never block read statements (SELECT).

So locks are only relevant, and deadlocks can only happen, when two transactions do write statements (INSERT, UPDATE or DELETE) that conflict with each other.

Locks can also be explicitly required by the application – in that case of course a deadlock can also happen.

Deadlock examples

Despite being possible only in write-write situations as explained above, deadlocks happen in a surprising number of creative ways.

Simple case example:

CREATE TABLE a(i INT PRIMARY KEY);
CREATE TABLE b(i INT PRIMARY KEY);

Transaction T1 does:

BEGIN;
INSERT INTO a VALUES(1);

Then transaction T2 does:

BEGIN;
INSERT INTO b VALUES(1);
INSERT INTO a VALUES(1);
-- waits for T1 here, specifically for row 1 in table a

Then transaction T1 does:

INSERT INTO b VALUES(1);
-- deadlock here!

Some other possibilities:

• UPDATEs instead of INSERTs in the above examples;
• SELECT ... FOR UPDATE instead of UPDATE (more info here);
• chains of three, four or more transactions each waiting for the following one;
• SELECT function() if function writes to any table, or calls any other function that does…;
• TRIGGERs, just like functions;
• UPDATEs to rows that refer to other rows via FOREIGN KEY. More about that in later articles in this series.

The next post in this series will present a general workflow to handle deadlock bugs and some more details on how to get information from PostgresSQL about deadlocks.