augmenting MultiXacts to improve foreign keys

Hi,

Previously, we had some discussion to introduce a new type of tuple lock
to let foreign keys be lighter weight, allowing for more concurrency.
During the course of that discussion, it became evident that the
solution being proposed didn't go all the way to solve the problem.  A
proposal by Noah Misch seems like it would fix the whole problem, but it
requires some more rejiggering than I had considered.

This email summarizes what I just posted in a blog article here:
http://www.commandprompt.com/blogs/alvaro_herrera/2011/08/fixing_foreign_key_deadlocks_part_three/
and adds some implementation details.

The proposal there is to create two new tuple lock types, not one.  They
have been called "KEY UPDATE" and "KEY SHARE".

Proposed conflict table:            KEY UPDATE    FOR UPDATE   FOR SHARE   KEY SHARE
KEY UPDATE       X             X            X           X
FOR UPDATE       X             X            X
FOR SHARE        X             X
KEY SHARE        X

DELETE always grabs KEY UPDATE lock on a tuple.
UPDATE grabs KEY UPDATE if the key is being modified, otherwise FOR UPDATE.
SELECT FOR UPDATE grabs FOR UPDATE.
SELECT FOR SHARE grabs FOR SHARE.
SELECT FOR KEY SHARE grabs FOR KEY SHARE.  This is the mode used by RI triggers.

Note that this means that UPDATE would always have to check whether key
columns are being modified.  (I loosely talk about "key columns" here
referring to columns involving unique indexes.  On tables with no unique
indexes, I think this would have to mean all columns, but I haven't
thought much about this bit.)

Note that the KEY UPDATE lock would be an internal option, not exposed
to SQL.  I think we already have enough extensions in this area.  We are
forced to expose KEY SHARE because RI triggers get to it via SPI, but I
would be happy to avoid doing it if I knew how.  I would also love to
get rid of FOR SHARE because I don't think they serve any purpose
anymore, but since it has already been exposed to SQL for several
releases, I'm not sure that it's a viable thing to do.

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.  This should be relatively simple, though
this forecloses the option of using MultiXact for some other purpose
than locking tuples.  This being purely theoretical, I don't have a
problem with that.

Note that the original keylocks patch I posted a couple of weeks ago has
a caveat: if transaction A grabs share lock and transaction B grabs key
lock, there's no way to know who owns which.  I dismissed that problem
as unimportant (and probably infrequent); the good thing about this new
idea is that we wouldn't have that problem.

This would also help us find a solution to the problem that an aborted
subtransaction that updates or excl-locks a tuple causes an earlier
shared lock to be forgotten.  We would deal with this by marking the
Xmax with a new MultiXact that includes both the lock and the update.
This means that this MultiXact would have to be WAL-logged.  I would
leave that for a later patch, but I think it's good that there's a way
to fix it.

Thoughts?

-- 
Álvaro Herrera <alvherre@alvh.no-ip.org>