How the foreign key can cause a deadlock (in Postgresql 9.2 and below).
Let say there is a child table referencing to a parent table:
CREATE TABLE time_slot(
id int primary key,
num_reservations int
);
CREATE TABLE reservation(
time_slot_id int,
created_timestamp timestamp,
CONSTRAINT time_slot_fk FOREIGN KEY (time_slot_id)
REFERENCES time_slot( id )
);
INSERT INTO time_slot values( 1, 0 );
INSERT INTO time_slot values( 2, 0 );
Suppose that the FK column in child table is modified in session one, that fires ordinary insert statement (to test this behavior, open one session in SQL Shell (psql) and turn auto commit off, or start the transaction using begin statement:
BEGIN;
INSERT INTO reservation VALUES( 2, now() );
When the FK column in child table is modified, DBMS will have to lookup the parent table to ensure the existence of the parent record.
If inserted value doesn't exists in the referenced (parent) table - DBMS breaks the transaction and reports an error.
In case the value exists, the record is inserted into child table, but DBMS has to ensure the transaction integrity - no other transaction can delete or modify referenced record in the parent table, until the transaction ends (until INSERT into child table is committed).
PostgreSql 9.2 (and below) ensure database integrity in a such case placing a read share lock on a record in the parent table. The read share lock doesn't prevents readers from reading locked record from the table, but prevent's writers from modyfying locked record in the shared mode.
OK - now we have a new record in the child table insered by session 1 (there is a write lock placed on this record by session 1), and the read share lock placed on the record 2 in the parent table. The transaction is not yet commitet.
Suppose that a session 2 starts the same transaction, that references the same record in the parent table:
BEGIN;
INSERT INTO reservation VALUES( 2, now() );
The query executes fine, without any errors - it inserts a new record into the child table, and also places a shared read lock on the record 2 in the parent table. Shared locks don't conflict, many transactions can lock a record in a shared read mode and don't have to wait for others (only write locks conflict).
Now (a few miliseconds later) the session 1 fires (as a part of the same transaction) this command:
UPDATE time_slot
SET num_reservations = num_reservations + 1
WHERE id = 2;
In Postgres 9.2 the above command "hangs" and is waiting for the shared lock placed by session 2.
And now, suppose that the same command, a few miliseconds later, is running in session 2:
UPDATE time_slot
SET num_reservations = num_reservations + 1
WHERE id = 2;
This command is supposed to "hang" and should wait for a write lock placed on the record by UPDATE from session 1.
But the result is:
BŁĄD: wykryto zakleszczenie
SZCZEGÓŁY: Proces 5604 oczekuje na ExclusiveLock na krotka (0,2) relacji 41363 bazy danych 16393; zablokowany przez 381
6.
Proces 3816 oczekuje na ShareLock na transakcja 1036; zablokowany przez 5604.
PODPOWIEDŹ: Przejrzyj dziennik serwera by znaleźć szczegóły zapytania.
("zakleszczenie" means "deadlock", "BŁĄD" means "ERROR")
- the update command from session 2 is trying to place a write lock on the record 2 locked by session 1
- session 1 is trying to place a write lock on the same record, locked (in the shared mode) by session 2
- ----> ...... deadlock.
The deadlock can be prevented by placing a write lock on the parent table using SELECT FOR UPDATE
The above test case will not cause the deadlock in PostgreSQL 9.3 (try it) - in 9.3 they improved locking behaviour in such cases.
------------ EDIT - additional questions -------------------
why does the insert statement not release the lock after it is done? Or does it remain for the entire transaction which is why not using a transaction does not cause a deadlock?
All statements that modify data within the transaction (insert, update, delete) place locks on modified records. These locks remain active until the transaction ends - by issuing commit or rollback.
Because autocommit is turned off in the JDBC connection, successive SQL commands are automaticaly grouped into one transaction
The explanation is here:
http://docs.oracle.com/javase/7/docs/api/java/sql/Connection.html#setAutoCommit%28boolean%29
If a connection is in auto-commit mode, then all its SQL statements will be executed and committed as individual transactions. Otherwise, its SQL statements are grouped into transactions that are terminated by a call to either the method commit or the method rollback.
How does the SELECT FOR UPDATE prevent the deadlock?
SELECT FOR UPDATE places a write lock on the record. This is the first command in the whole transaction, and the lock is placed in the beginning. When another transaction starts (in another session), is also executes SELECT FOR UPDATE, trying to lock the same record. Write locks conflict - two transactions cannot lock the same record at the same time - therefore the SELECT FOR UPDATE of the second transaction is hold, and is waiting until the first transaction releases the lock (by issuing commit or rollback) - actually the second transaction is waiting until the whole first transaction ends.
In the first scenario, the INSERT statements places two locks:
- a write lock on the inserted record in the reservation table
- and a read shared lock on the record in the time_slot table referenced by the foreign key constraint
Read shared locks don't conflict - two and more transactions can lock the same record in the shared mode, and can continue execution - then don't have to wait for each other. But later, when the UPDATE is issued within the same transaction, trying to place a write lock on the same record already locked in the shared mode, this cause a deadlock.
Would placing the increment first also prevent the deadlock?
Yes, you are right. This prevents the deadlock, because a write lock is placed on the record at the beginning of the transaction. Another transaction also tries to update the same record at the beginning, and has to wait at this point because the record is already locked (in write mode) by another session.