Re: augmenting MultiXacts to improve foreign keys

On Tue, Aug 09, 2011 at 01:01:04PM -0400, Alvaro Herrera wrote:
> 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.)

On tables with no key columns, we can skip the datum comparisons and use KEY
UPDATE, because it does not matter: nobody would try to take KEY SHARE anyway.
(If KEY SHARE is SQL-exposed, a manual acquisition remains possible. It does
not seem important to cater to that, though.) Key columns should be those
columns actually referenced by incoming foreign keys; the relcache can maintain
that list. This was less important for the previous version, which didn't
compare datums prior to encountering a live KEY LOCK. It will now be more
important to avoid that overhead for tables lacking incoming FKs.

> 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.

Is there a case not involving manual SELECT ... FOR <locktype> that will depend
on this for correctness? Even if not, there's a lot to like about this
proposal. However, I think I may be missing the condition you had in mind when
designing it.

> 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.

Interesting. Growing pg_multixact/members by 6% seems reasonable for those two
benefits. It also makes possible a manual FOR UPDATE over a KEY LOCK; that
previously looked problematic due to the lack of a later tuple version to
continue bearing the KEY LOCK.

Consider the simple case of a tuple with a single KEY LOCK which we then proceed
to UPDATE, not touching any key column. Will that old tuple version get a
multixact bearing both the FOR UPDATE locker and the KEY LOCK locker, or will it
carry just the FOR UPDATE locker with the new tuple witnessing the KEY LOCK?
The latter seems preferable to avoid an increase in pg_multixact usage, but I
haven't worked out whether it covers enough of the problem space.

Thanks,
nm

--
Noah Misch http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services