The curious case of two inserts, a shrinking xmax, and a ShareLock on transaction

Hi,

I've been trying to understand this curious case of a shrinking xmax.

Suppose we have two tables: foo and bar.

CREATE TABLE foo (
foo_id text PRIMARY KEY NOT NULL
);

CREATE TABLE bar (
bar_id text NOT NULL,
foo_id text NOT NULL REFERENCES foo (foo_id) ON DELETE CASCADE
);

... and we have a foo_id1:

[console] sandbox=# insert into foo (foo_id) values ('foo_id1');
INSERT 0 1
[console] sandbox=# select *, xmin, xmax from foo;
foo_id | xmin | xmax
---------+------+------
foo_id1 | 694 | 0
(1 row)

Now we start transaction A:

[A] sandbox=# begin;
BEGIN
[A] sandbox=# insert into bar (bar_id, foo_id) values ('bar_id1',
'foo_id1');
INSERT 0 1
[A] sandbox=# select *, xmin, xmax from bar;
bar_id | foo_id | xmin | xmax
---------+---------+------+------
bar_id1 | foo_id1 | 695 | 0
(1 row)

[A] sandbox=# select *, xmin, xmax from foo;
foo_id | xmin | xmax
---------+------+------
foo_id1 | 694 | 695
(1 row)

Ok, foo_id1's xmax is 695, which locks the row as explained by this
excellent blog post: http://rhaas.blogspot.com/2011/10/deadlocks.html

Now let's start transaction B:

[B] sandbox=# begin;
BEGIN
[B] sandbox=# insert into bar (bar_id, foo_id) values ('bar_id2',
'foo_id1');
INSERT 0 1
[B] sandbox=# select *, xmin, xmax from bar;
bar_id | foo_id | xmin | xmax
---------+---------+------+------
bar_id2 | foo_id1 | 696 | 0
(1 row)

[B] sandbox=# select *, xmin, xmax from foo;
foo_id | xmin | xmax
---------+------+------
foo_id1 | 694 | 1
(1 row)

Wait, what? foo_id1's xmax is 1? What does that even mean?

If I do a SELECT FOR UPDATE on foo_id1 in transaction A, it hangs waiting
for transaction B to finish:

[A] sandbox=# select * from foo where foo_id = 'foo_id1' for update;

I can see transaction A (transactionid 695, virtualtransaction 3/41)
takes a ShareLock on transaction B (transactionid 696). How does it
know to do that since foo_id1's xmax is 1?

[console] sandbox=# select locktype, relation::regclass, page, tuple,
virtualxid, transactionid, virtualtransaction, pid, mode, granted, fastpath
from pg_locks where virtualtransaction = '3/41' or virtualtransaction =
'4/15';
locktype | relation | page | tuple | virtualxid | transactionid |
virtualtransaction | pid | mode | granted | fastpath
---------------+----------+------+-------+------------+---------------+--------------------+-----+---------------------+---------+----------
relation | foo_pkey | | | | |
4/15 | 171 | AccessShareLock | t | t
relation | foo | | | | |
4/15 | 171 | AccessShareLock | t | t
relation | foo | | | | |
4/15 | 171 | RowShareLock | t | t
relation | bar | | | | |
4/15 | 171 | AccessShareLock | t | t
relation | bar | | | | |
4/15 | 171 | RowExclusiveLock | t | t
virtualxid | | | | 4/15 | |
4/15 | 171 | ExclusiveLock | t | t
relation | foo_pkey | | | | |
3/41 | 165 | AccessShareLock | t | t
relation | foo | | | | |
3/41 | 165 | AccessShareLock | t | t
relation | foo | | | | |
3/41 | 165 | RowShareLock | t | t
relation | bar | | | | |
3/41 | 165 | AccessShareLock | t | t
relation | bar | | | | |
3/41 | 165 | RowExclusiveLock | t | t
virtualxid | | | | 3/41 | |
3/41 | 165 | ExclusiveLock | t | t
transactionid | | | | | 696 |
3/41 | 165 | ShareLock | f | f
transactionid | | | | | 695 |
3/41 | 165 | ExclusiveLock | t | f
transactionid | | | | | 696 |
4/15 | 171 | ExclusiveLock | t | f
tuple | foo | 0 | 2 | | |
3/41 | 165 | AccessExclusiveLock | t | f

At this point, if I commit or rollback transaction B, transaction A
can continue. If I do a SELECT FOR UPDATE on foo_id1 for transaction
B, I'll create a deadlock and the deadlock detector will kill one of
the transactions.

I'd really love to learn:

1. Why the xmax for foo_id1 goes from 696 to 1 and what does that
mean?
2. How does transaction A know it needs to take a ShareLock on
transaction B?
3. What is a virtualtransaction and what do its numerator and denominator
mean?

Thanks,
Jeff