Re: BUG #8434: Why does dead lock occur many times ?

I spent a lot of time looking at this issue. Your problem scenario can
be reduced to the following test case:

CREATE TABLE t (a INT);
INSERT INTO t VALUES (1);

The three sessions need to execute the following commands, in this
sequence:

-- Session 1
/* 1 */ BEGIN;
SELECT * FROM t FOR UPDATE;

-- Session 2
/* 2 */ BEGIN;
UPDATE t SET a = 2; -- blocks waiting on S1

-- Session 3
/* 3 */ BEGIN;
UPDATE t SET a = 3; -- blocks
-- this is waiting on S1, but since S2 is also waiting on S1 and will acquire a
-- conflicting lock first, this session will only be released after S2 releases
-- its own lock.

Session 1
/* 4 */ UPDATE t SET a = 4;
COMMIT; -- releases session 2
BEGIN;
SELECT * FROM t FOR UPDATE; -- blocks waiting on S2 (*)

Session 2:
/* 5 */ COMMIT; -- releases session 1
BEGIN;
UPDATE t SET a = 5; -- blocks waiting on S3

Session 1:
/* 6 */ UPDATE t SET a = 6; -- blocks waiting on S3

At this point, all sessions are blocked on their UPDATE commands, and
deadlock is reported. (For debugging, it's useful to set a very large
deadlock_timeout and examine pg_locks, etc.)

The point at which things started to go wrong was where the session 1's
SELECT FOR UPDATE with the (*) was allowed to continue after session 2
commits. In 9.2 that session remains blocked, and instead we release
session 3.

The problem is the handling of following of the update chain during a
lock command; the question is should sessions be blocked waiting for
locks on future versions of the row? They currently don't block, which
is what leads the SELECT FOR UPDATE to continue; but if we make them
block, other things break. I initially toyed with the following patch,
which removes the deadlock the above report and also your original test
case:

--- a/src/backend/access/heap/heapam.c
+++ b/src/backend/access/heap/heapam.c
@@ -4832,15 +4832,12 @@ l4:
xmax = HeapTupleHeaderGetRawXmax(mytup.t_data);

/*
- * If this tuple is updated and the key has been modified (or
- * deleted), what we do depends on the status of the updating
- * transaction: if it's live, we sleep until it finishes; if it has
- * committed, we have to fail (i.e. return HeapTupleUpdated); if it
- * aborted, we ignore it. For updates that didn't touch the key, we
- * can just plough ahead.
+ * If this tuple is updated, what we do depends on the status of the
+ * updating transaction: if it's live, we sleep until it finishes; if
+ * it has committed, we have to fail (i.e. return HeapTupleUpdated); if
+ * it aborted, we ignore it.
*/
- if (!(old_infomask & HEAP_XMAX_INVALID) &&
- (mytup.t_data->t_infomask2 & HEAP_KEYS_UPDATED))
+ if (!(old_infomask & HEAP_XMAX_INVALID))
{
TransactionId update_xid;

However, the differences in behavior this causes (visible by running the
isolation tests) don't look good to me. It's quite possible that there
are other bugs elsewhere.

Sadly, I have to look at other things now and I won't have time to
research this further until after next week's minor releases; so
whatever we decide to do, if anything, will not be in 9.3.1.

Thanks for the report.

--
Álvaro Herrera http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services