Re: [COMMITTERS] pgsql: Improve concurrency of foreign key locking

Improve concurrency of foreign key locking

This patch introduces two additional lock modes for tuples: "SELECT FOR
KEY SHARE" and "SELECT FOR NO KEY UPDATE". These don't block each
other, in contrast with already existing "SELECT FOR SHARE" and "SELECT
FOR UPDATE". UPDATE commands that do not modify the values stored in
the columns that are part of the key of the tuple now grab a SELECT FOR
NO KEY UPDATE lock on the tuple, allowing them to proceed concurrently
with tuple locks of the FOR KEY SHARE variety.

Foreign key triggers now use FOR KEY SHARE instead of FOR SHARE; this
means the concurrency improvement applies to them, which is the whole
point of this patch.

The added tuple lock semantics require some rejiggering of the multixact
module, so that the locking level that each transaction is holding can
be stored alongside its Xid. Also, multixacts now need to persist
across server restarts and crashes, because they can now represent not
only tuple locks, but also tuple updates. This means we need more
careful tracking of lifetime of pg_multixact SLRU files; since they now
persist longer, we require more infrastructure to figure out when they
can be removed. pg_upgrade also needs to be careful to copy
pg_multixact files over from the old server to the new, or at least part
of multixact.c state, depending on the versions of the old and new
servers.

Tuple time qualification rules (HeapTupleSatisfies routines) need to be
careful not to consider tuples with the "is multi" infomask bit set as
being only locked; they might need to look up MultiXact values (i.e.
possibly do pg_multixact I/O) to find out the Xid that updated a tuple,
whereas they previously were assured to only use information readily
available from the tuple header. This is considered acceptable, because
the extra I/O would involve cases that would previously cause some
commands to block waiting for concurrent transactions to finish.

Another important change is the fact that locking tuples that have
previously been updated causes the future versions to be marked as
locked, too; this is essential for correctness of foreign key checks.
This causes additional WAL-logging, also (there was previously a single
WAL record for a locked tuple; now there are as many as updated copies
of the tuple there exist.)

With all this in place, contention related to tuples being checked by
foreign key rules should be much reduced.

As a bonus, the old behavior that a subtransaction grabbing a stronger
tuple lock than the parent (sub)transaction held on a given tuple and
later aborting caused the weaker lock to be lost, has been fixed.

Many new spec files were added for isolation tester framework, to ensure
overall behavior is sane. There's probably room for several more tests.

There were several reviewers of this patch; in particular, Noah Misch
and Andres Freund spent considerable time in it. Original idea for the
patch came from Simon Riggs, after a problem report by Joel Jacobson.
Most code is from me, with contributions from Marti Raudsepp, Alexander
Shulgin, Noah Misch and Andres Freund.

This patch was discussed in several pgsql-hackers threads; the most
important start at the following message-ids:
AANLkTimo9XVcEzfiBR-ut3KVNDkjm2Vxh+t8kAmWjPuv(at)mail(dot)gmail(dot)com
1290721684-sup-3951(at)alvh(dot)no-ip(dot)org
1294953201-sup-2099(at)alvh(dot)no-ip(dot)org
1320343602-sup-2290(at)alvh(dot)no-ip(dot)org
1339690386-sup-8927(at)alvh(dot)no-ip(dot)org
4FE5FF020200002500048A3D(at)gw(dot)wicourts(dot)gov
4FEAB90A0200002500048B7D(at)gw(dot)wicourts(dot)gov

Branch
------
master

Details
-------
http://git.postgresql.org/pg/commitdiff/0ac5ad5134f2769ccbaefec73844f8504c4d6182

Modified Files
--------------
contrib/file_fdw/output/file_fdw.source | 2 +-
contrib/pageinspect/heapfuncs.c | 2 +-
contrib/pg_upgrade/controldata.c | 46 +
contrib/pg_upgrade/pg_upgrade.c | 46 +
contrib/pg_upgrade/pg_upgrade.h | 7 +
contrib/pgrowlocks/Makefile | 2 +-
contrib/pgrowlocks/pgrowlocks--1.0--1.1.sql | 17 +
contrib/pgrowlocks/pgrowlocks--1.0.sql | 15 -
contrib/pgrowlocks/pgrowlocks--1.1.sql | 15 +
contrib/pgrowlocks/pgrowlocks.c | 178 ++-
contrib/pgrowlocks/pgrowlocks.control | 2 +-
doc/src/sgml/pgrowlocks.sgml | 15 +-
doc/src/sgml/ref/select.sgml | 146 +-
src/backend/access/common/heaptuple.c | 2 +-
src/backend/access/heap/README.tuplock | 139 ++
src/backend/access/heap/heapam.c | 2245 ++++++++++++++++----
src/backend/access/heap/pruneheap.c | 10 +-
src/backend/access/heap/rewriteheap.c | 17 +-
src/backend/access/rmgrdesc/heapdesc.c | 56 +-
src/backend/access/rmgrdesc/mxactdesc.c | 37 +-
src/backend/access/rmgrdesc/xlogdesc.c | 5 +-
src/backend/access/transam/README | 6 +-
src/backend/access/transam/multixact.c | 1191 +++++++----
src/backend/access/transam/varsup.c | 2 +
src/backend/access/transam/xlog.c | 14 +-
src/backend/catalog/heap.c | 14 +-
src/backend/catalog/index.c | 9 +-
src/backend/commands/analyze.c | 9 +-
src/backend/commands/cluster.c | 37 +-
src/backend/commands/dbcommands.c | 15 +-
src/backend/commands/sequence.c | 10 +-
src/backend/commands/tablecmds.c | 12 +-
src/backend/commands/trigger.c | 32 +-
src/backend/commands/vacuum.c | 96 +-
src/backend/commands/vacuumlazy.c | 24 +-
src/backend/executor/execMain.c | 21 +-
src/backend/executor/nodeLockRows.c | 25 +-
src/backend/executor/nodeModifyTable.c | 6 +-
src/backend/nodes/copyfuncs.c | 4 +-
src/backend/nodes/equalfuncs.c | 4 +-
src/backend/nodes/outfuncs.c | 4 +-
src/backend/nodes/readfuncs.c | 2 +-
src/backend/optimizer/plan/initsplan.c | 6 +-
src/backend/optimizer/plan/planner.c | 37 +-
src/backend/parser/analyze.c | 58 +-
src/backend/parser/gram.y | 29 +-
src/backend/postmaster/autovacuum.c | 45 +-
src/backend/rewrite/rewriteHandler.c | 32 +-
src/backend/storage/lmgr/lock.c | 15 +-
src/backend/storage/lmgr/predicate.c | 4 +-
src/backend/tcop/utility.c | 50 +-
src/backend/utils/adt/ri_triggers.c | 23 +-
src/backend/utils/adt/ruleutils.c | 28 +-
src/backend/utils/cache/relcache.c | 31 +-
src/backend/utils/time/combocid.c | 5 +-
src/backend/utils/time/tqual.c | 466 ++++-
src/bin/pg_controldata/pg_controldata.c | 4 +
src/bin/pg_resetxlog/pg_resetxlog.c | 37 +-
src/include/access/heapam.h | 23 +-
src/include/access/heapam_xlog.h | 33 +-
src/include/access/htup.h | 6 +-
src/include/access/htup_details.h | 62 +-
src/include/access/multixact.h | 66 +-
src/include/access/rewriteheap.h | 2 +-
src/include/catalog/catversion.h | 2 +-
src/include/catalog/pg_class.h | 24 +-
src/include/catalog/pg_control.h | 4 +-
src/include/catalog/pg_database.h | 10 +-
src/include/catalog/pg_proc.h | 2 +
src/include/commands/cluster.h | 3 +-
src/include/commands/vacuum.h | 6 +-
src/include/executor/executor.h | 2 +-
src/include/nodes/execnodes.h | 8 +-
src/include/nodes/parsenodes.h | 36 +-
src/include/nodes/plannodes.h | 12 +-
src/include/parser/analyze.h | 2 +-
src/include/postgres.h | 7 +
src/include/storage/lock.h | 1 +
src/include/utils/builtins.h | 3 +
src/include/utils/rel.h | 1 +
src/include/utils/relcache.h | 4 +-
src/include/utils/tqual.h | 1 +
src/test/isolation/expected/aborted-keyrevoke.out | 276 +++
.../isolation/expected/aborted-keyrevoke_2.out | 278 +++
.../isolation/expected/delete-abort-savept-2.out | 76 +
.../isolation/expected/delete-abort-savept.out | 243 +++
src/test/isolation/expected/fk-contention.out | 3 +-
src/test/isolation/expected/fk-deadlock.out | 126 +-
src/test/isolation/expected/fk-deadlock2.out | 113 +-
src/test/isolation/expected/fk-deadlock2_1.out | 75 +-
src/test/isolation/expected/fk-deadlock2_2.out | 105 +
src/test/isolation/expected/fk-deadlock_1.out | 44 +-
src/test/isolation/expected/fk-deadlock_2.out | 67 +
src/test/isolation/expected/fk-delete-insert.out | 41 +
src/test/isolation/expected/lock-update-delete.out | 65 +
.../isolation/expected/lock-update-traversal.out | 18 +
.../isolation/expected/multixact-no-deadlock.out | 24 +
src/test/isolation/isolation_schedule | 5 +
src/test/isolation/isolationtester.c | 1 +
src/test/isolation/specs/aborted-keyrevoke.spec | 31 +
.../isolation/specs/delete-abort-savept-2.spec | 34 +
src/test/isolation/specs/delete-abort-savept.spec | 29 +
src/test/isolation/specs/fk-deadlock.spec | 23 -
src/test/isolation/specs/fk-deadlock2.spec | 23 -
src/test/isolation/specs/lock-update-delete.spec | 38 +
.../isolation/specs/lock-update-traversal.spec | 32 +
.../isolation/specs/multixact-no-deadlock.spec | 35 +
107 files changed, 6036 insertions(+), 1500 deletions(-)

On 01/23/2013 10:12 AM, Alvaro Herrera wrote:
> Improve concurrency of foreign key locking
>
>

It looks like isolation_tester.c needs a few calls to fflush(stderr)
(basically in those places where it won't be exiting right afterwards.)
This would probably account for the windows buildfarm failure I see on
frogmouth.

cheers

andrew

On 01/23/2013 10:12 AM, Alvaro Herrera wrote:
> Improve concurrency of foreign key locking

This error message change looks rather odd, and has my head spinning a bit:

- errmsg("SELECT FOR UPDATE/SHARE cannot be applied
to the nullable side of an outer join")));
+ errmsg("SELECT FOR UPDATE/SHARE/KEY UPDATE/KEY
SHARE cannot be applied to the nullable side of an outer join")))

Can't we do better than that?

(It's also broken my FDW check, but I'll fix that when this is sorted out)

cheers

andrew

On 2013-01-23 11:58:28 -0500, Andrew Dunstan wrote:
>
> On 01/23/2013 10:12 AM, Alvaro Herrera wrote:
> >Improve concurrency of foreign key locking
>
> This error message change looks rather odd, and has my head spinning a bit:
>
> - errmsg("SELECT FOR UPDATE/SHARE cannot be applied to
> the nullable side of an outer join")));
> + errmsg("SELECT FOR UPDATE/SHARE/KEY UPDATE/KEY SHARE
> cannot be applied to the nullable side of an outer join")))
>
> Can't we do better than that?

I don't really see how? I don't think listing only the current locklevel
really is an improvement and something like "SELECT ... FOR $locktype
cannot .." seem uncommon enough in pg error messages to be strange.
Now I aggree that listing all those locklevels isn't that nice, but I
don't really have a better idea.

Andres

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

Andres Freund <andres(at)2ndquadrant(dot)com> writes:
> On 2013-01-23 11:58:28 -0500, Andrew Dunstan wrote:
>> This error message change looks rather odd, and has my head spinning a bit:
>>
>> - errmsg("SELECT FOR UPDATE/SHARE cannot be applied to
>> the nullable side of an outer join")));
>> + errmsg("SELECT FOR UPDATE/SHARE/KEY UPDATE/KEY SHARE
>> cannot be applied to the nullable side of an outer join")))
>>
>> Can't we do better than that?

> I don't really see how? I don't think listing only the current locklevel
> really is an improvement and something like "SELECT ... FOR $locktype
> cannot .." seem uncommon enough in pg error messages to be strange.
> Now I aggree that listing all those locklevels isn't that nice, but I
> don't really have a better idea.

I don't really see what's wrong with the original spelling of the
message. The fact that you can now insert KEY in there doesn't really
affect anything for the purposes of this error.

regards, tom lane

On 23 January 2013 17:15, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
> On 2013-01-23 11:58:28 -0500, Andrew Dunstan wrote:
>>
>> On 01/23/2013 10:12 AM, Alvaro Herrera wrote:
>> >Improve concurrency of foreign key locking
>>
>> This error message change looks rather odd, and has my head spinning a bit:
>>
>> - errmsg("SELECT FOR UPDATE/SHARE cannot be applied to
>> the nullable side of an outer join")));
>> + errmsg("SELECT FOR UPDATE/SHARE/KEY UPDATE/KEY SHARE
>> cannot be applied to the nullable side of an outer join")))
>>
>> Can't we do better than that?
>
> I don't really see how? I don't think listing only the current locklevel
> really is an improvement and something like "SELECT ... FOR $locktype
> cannot .." seem uncommon enough in pg error messages to be strange.
> Now I aggree that listing all those locklevels isn't that nice, but I
> don't really have a better idea.

"row level locks cannot be applied to the NULLable side of an outer join"
Hint: there are no rows to lock

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

Andrew Dunstan wrote:
>
> On 01/23/2013 10:12 AM, Alvaro Herrera wrote:
> >Improve concurrency of foreign key locking
>
> This error message change looks rather odd, and has my head spinning a bit:
>
> - errmsg("SELECT FOR UPDATE/SHARE cannot be
> applied to the nullable side of an outer join")));
> + errmsg("SELECT FOR UPDATE/SHARE/KEY UPDATE/KEY
> SHARE cannot be applied to the nullable side of an outer join")))
>
> Can't we do better than that?

Basically this message says "a SELECT with a locking clause attached
cannot be blah blah". There are many messages that had the original
code saying "SELECT FOR UPDATE cannot be blah blah", which was later
(8.1) updated to say "SELECT FOR UPDATE/SHARE cannot be blah blah". I
expanded them using the same logic, but maybe there's a better
suggestion? Note that the SELECT reference page now has a subsection
called "The locking clause", so maybe it's okay to use that term now.

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

On 01/23/2013 12:48 PM, Simon Riggs wrote:
> On 23 January 2013 17:15, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
>> On 2013-01-23 11:58:28 -0500, Andrew Dunstan wrote:
>>> On 01/23/2013 10:12 AM, Alvaro Herrera wrote:
>>>> Improve concurrency of foreign key locking
>>> This error message change looks rather odd, and has my head spinning a bit:
>>>
>>> - errmsg("SELECT FOR UPDATE/SHARE cannot be applied to
>>> the nullable side of an outer join")));
>>> + errmsg("SELECT FOR UPDATE/SHARE/KEY UPDATE/KEY SHARE
>>> cannot be applied to the nullable side of an outer join")))
>>>
>>> Can't we do better than that?
>> I don't really see how? I don't think listing only the current locklevel
>> really is an improvement and something like "SELECT ... FOR $locktype
>> cannot .." seem uncommon enough in pg error messages to be strange.
>> Now I aggree that listing all those locklevels isn't that nice, but I
>> don't really have a better idea.
> "row level locks cannot be applied to the NULLable side of an outer join"
> Hint: there are no rows to lock
>

Yeah, this is really more informative than either, I think.

cheers

andrew

Simon Riggs <simon(at)2ndQuadrant(dot)com> writes:
> On 23 January 2013 17:15, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
>> On 2013-01-23 11:58:28 -0500, Andrew Dunstan wrote:
>>> Can't we do better than that?

> "row level locks cannot be applied to the NULLable side of an outer join"

I think it should read "row-level locks cannot ...", but otherwise this
is a fine idea.

> Hint: there are no rows to lock

This bit doesn't seem to be either accurate or helpful, though.

regards, tom lane

Alvaro Herrera wrote:
> Improve concurrency of foreign key locking

I noticed a bug in visibility routines when pg_upgrade is involved:
tuples marked FOR UPDATE in the old cluster (i.e. HEAP_XMAX_INVALID not
set, HEAP_XMAX_EXCL_LOCK set, HEAP_XMAX_IS_MULTI not set) are invisible
(dead) on the new cluster. I had defined the HEAP_XMAX_IS_LOCKED_ONLY
thusly:

#define HEAP_XMAX_IS_LOCKED_ONLY(infomask) \
((infomask) & HEAP_XMAX_LOCK_ONLY)

but this doesn't work for the reason stated above. The fix is to
redefine the macro like this:

/*
* A tuple is only locked (i.e. not updated by its Xmax) if the
* HEAP_XMAX_LOCK_ONLY bit is set; or, for pg_upgrade's sake, if the Xmax is
* not a multi and the EXCL_LOCK bit is set.
*
* See also HeapTupleHeaderIsOnlyLocked, which also checks for a possible
* aborted updater transaction.
*
* Beware of multiple evaluations of the argument.
*/
#define HEAP_XMAX_IS_LOCKED_ONLY(infomask) \
(((infomask) & HEAP_XMAX_LOCK_ONLY) || \
(((infomask) & (HEAP_XMAX_IS_MULTI | HEAP_LOCK_MASK)) == HEAP_XMAX_EXCL_LOCK))

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

--On 23. Januar 2013 15:12:00 +0000 Alvaro Herrera
<alvherre(at)alvh(dot)no-ip(dot)org> wrote:

> This patch introduces two additional lock modes for tuples: "SELECT FOR
> KEY SHARE" and "SELECT FOR NO KEY UPDATE". These don't block each
> other, in contrast with already existing "SELECT FOR SHARE" and "SELECT
> FOR UPDATE". UPDATE commands that do not modify the values stored in
> the columns that are part of the key of the tuple now grab a SELECT FOR
> NO KEY UPDATE lock on the tuple, allowing them to proceed concurrently
> with tuple locks of the FOR KEY SHARE variety.

Out of curiousity, shouldn't we update chapter 13.3.2 in the docs to
mention the additional new lock modes, too?

--
Thanks

Bernd

Tom Lane wrote:
> Simon Riggs <simon(at)2ndQuadrant(dot)com> writes:
> > On 23 January 2013 17:15, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
> >> On 2013-01-23 11:58:28 -0500, Andrew Dunstan wrote:
> >>> Can't we do better than that?
>
> > "row level locks cannot be applied to the NULLable side of an outer join"
>
> I think it should read "row-level locks cannot ...", but otherwise this
> is a fine idea.

Thanks for the suggestion, I have changed all these messages.

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