Re: augmenting MultiXacts to improve foreign keys

Excerpts from Alvaro Herrera's message of mar ago 09 13:01:04 -0400 2011:

> To implement this, we need to augment MultiXact to store the lock type
> that each comprising Xid holds on the tuple. Two bits per Xid are
> needed. My thinking is that we could simply extend the "members" to add
> a byte for every four members.

So I've been working on this, and I've noticed that somehow it seems to
have turned into a giant snowball. I'd like opinions on the items below
before I continue work here; if any of these ideas turns out to be a
showstopper, I'd like to know sooner rather than later.

1. since MultiXacts are going to contain updates and not just locks, it
means they will need to persist beyond OldestXmin -- in fact,
pg_multixact is going to have the same truncation rules as pg_clog,
namely the vacuum freeze horizon. Currently they are truncated very
quickly; this is not going to be true anymore.

2. This also means that we may have to resolve MultiXacts to their
comprising TransactionIds when tqual.c is doing visibility checks on the
tuples. Right now, the code simply does things like this:

if (tuple->t_infomask & HEAP_XMAX_IS_MULTI)
{
/* MultiXacts are currently only allowed to lock tuples */
Assert(tuple->t_infomask & HEAP_IS_LOCKED);
return true;
}
/* further code checks HeapTupleHeaderGetXmax(tuple) */

It's now going to need to do something more like

if (tuple->t_infomask & HEAP_XMAX_IS_MULTI)
{
if (tuple->t_infomask & HEAP_IS_LOCKED)
return true;
xmax = HeapTupleGetUpdateXid(tuple);
}
else
xmax = HeapTupleHeaderGetXmax(tuple);
/* further code checks our derived xmax */

where the HeapTupleGetUpdateXid function looks more or less like this

TransactionId
HeapTupleGetUpdateXid(HeapTupleHeader tuple)
{
TransactionId update_xact;

Assert(!(tuple->t_infomask & HEAP_XMAX_IS_NOT_UPDATE));
Assert(tuple->t_infomask & HEAP_XMAX_IS_MULTI);

MultiXactMember *members;

nmembers = GetMultiXactIdMembers(xwait, &members);

if (nmembers > 0)
{
int i;

for (i = 0; i < nmembers; i++)
{
/* KEY SHARE lockers are okay -- ignore it */
if (members[i].status == MultiXactStatusKeyShare)
continue;
/* there should be at most one updater */
Assert(update_xact == InvalidTransactionId);
/* other status values not acceptable because they
* conflict with update */
Assert(members[i].status == MultiXactStatusUpdate);
update_xact = members[i].xid;
}
}

return update_xact;
}

Which leads us to:

3. I've come up with HEAP_XMAX_IS_NOT_UPDATE in t_infomask, which means
that the Xmax, being a MultiXact, does not contain an update Xid. This
reuses the old value of HEAP_XMAX_SHARED_LOCK. I've used this rather
weird semantics for these reasons:

a) it's pg_upgrade compatible. Any tuple that has the SHARED_LOCK bit
from the older version set cannot contain an update, and so the bit is
automatically right.
b) it quickly avoids having to run the GetMultiXactIdMembers thingy
(which is expensive) in the common case that there's no update.
c) it lets me keep the HEAP_IS_LOCKED semantics; which means "this tuple
is only locked by Xmax, not updated", which is used extensively in
various places.
/*
* if any of these bits is set, xmax hasn't deleted the tuple, only locked it.
*/
#define HEAP_IS_LOCKED (HEAP_XMAX_EXCL_LOCK | HEAP_XMAX_IS_NOT_UPDATE | \
HEAP_XMAX_KEYSHR_LOCK)

4. FOR SHARE is not a very widely used clause, I think. FOR UPDATE is
part of the standard and thus it warrants quick innards, i.e. its own
hint bit. FOR KEY SHARE is going to be used by RI triggers and so it
should also be quick; I've also given it its own hint bit. However,
FOR SHARE is probably not used much and I've relegated it to being
mandatorily stored in MultiXact. That is, if someone requests a FOR
SHARE lock on a tuple, it will get a singleton MultiXact. The reason
for this is that I didn't want to use one more hint bit.

5. I've now used three hint bits -- reused HEAP_XMAX_SHARED_LOCK as
HEAP_XMAX_IS_NOT_UPDATE (already explained); used the free hint bit from
t_infomask as HEAP_XMAX_KEYSHR_LOCK (should be obvious); and I've used
0x2000 in t_infomask2 as HEAP_UPDATE_KEY_INTACT, to mean that this tuple
has been updated but the key columns have not been modified. This lets
heapam.c know that this tuple can be further key-share locked.

6. When locking a tuple that is being concurrently updated, the locking
transaction must obviously walk up the update chain (t_self) and lock
the updated version too. I have not tried to implement this yet but I
think it's going to be a bit weird -- I think I might need to modify
tuples that are HeapTupleInvisible and/or HeapTupleSelfUpdated according
to HeapTupleSatisfiesUpdate. (I even wonder if I'm going to need to
create a new HeapTupleSatisfies routine for this purpose).

Thoughts?

--
Álvaro Herrera <alvherre(at)commandprompt(dot)com>
The PostgreSQL Company - Command Prompt, Inc.
PostgreSQL Replication, Consulting, Custom Development, 24x7 support