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@mail.gmail.com
	1290721684-sup-3951@alvh.no-ip.org
	1294953201-sup-2099@alvh.no-ip.org
	1320343602-sup-2290@alvh.no-ip.org
	1339690386-sup-8927@alvh.no-ip.org
	4FE5FF020200002500048A3D@gw.wicourts.gov
	4FEAB90A0200002500048B7D@gw.wicourts.gov

25 files changed, 1644 insertions, 161 deletions

diff --git a/src/test/isolation/expected/aborted-keyrevoke.out b/src/test/isolation/expected/aborted-keyrevoke.out
new file mode 100644
index 00000000000..8850614b8ab
--- /dev/null
+++ b/src/test/isolation/expected/aborted-keyrevoke.out
@@ -0,0 +1,276 @@
+Parsed test spec with 2 sessions
+
+starting permutation: s1s s1u s1r s1l s1c s2l s2c
+step s1s: SAVEPOINT f;
+step s1u: UPDATE foo SET key = 2;
+step s1r: ROLLBACK TO f;
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1c: COMMIT;
+step s2l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s2c: COMMIT;
+
+starting permutation: s1s s1u s1r s1l s2l s1c s2c
+step s1s: SAVEPOINT f;
+step s1u: UPDATE foo SET key = 2;
+step s1r: ROLLBACK TO f;
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s2l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1c: COMMIT;
+step s2c: COMMIT;
+
+starting permutation: s1s s1u s1r s1l s2l s2c s1c
+step s1s: SAVEPOINT f;
+step s1u: UPDATE foo SET key = 2;
+step s1r: ROLLBACK TO f;
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s2l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s2c: COMMIT;
+step s1c: COMMIT;
+
+starting permutation: s1s s1u s1r s2l s1l s1c s2c
+step s1s: SAVEPOINT f;
+step s1u: UPDATE foo SET key = 2;
+step s1r: ROLLBACK TO f;
+step s2l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1c: COMMIT;
+step s2c: COMMIT;
+
+starting permutation: s1s s1u s1r s2l s1l s2c s1c
+step s1s: SAVEPOINT f;
+step s1u: UPDATE foo SET key = 2;
+step s1r: ROLLBACK TO f;
+step s2l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s2c: COMMIT;
+step s1c: COMMIT;
+
+starting permutation: s1s s1u s1r s2l s2c s1l s1c
+step s1s: SAVEPOINT f;
+step s1u: UPDATE foo SET key = 2;
+step s1r: ROLLBACK TO f;
+step s2l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s2c: COMMIT;
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1c: COMMIT;
+
+starting permutation: s1s s1u s2l s1r s1l s1c s2c
+step s1s: SAVEPOINT f;
+step s1u: UPDATE foo SET key = 2;
+step s2l: SELECT * FROM foo FOR KEY SHARE; <waiting ...>
+step s1r: ROLLBACK TO f;
+step s2l: <... completed>
+key            value          
+
+1              1              
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1c: COMMIT;
+step s2c: COMMIT;
+
+starting permutation: s1s s1u s2l s1r s1l s2c s1c
+step s1s: SAVEPOINT f;
+step s1u: UPDATE foo SET key = 2;
+step s2l: SELECT * FROM foo FOR KEY SHARE; <waiting ...>
+step s1r: ROLLBACK TO f;
+step s2l: <... completed>
+key            value          
+
+1              1              
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s2c: COMMIT;
+step s1c: COMMIT;
+
+starting permutation: s1s s1u s2l s1r s2c s1l s1c
+step s1s: SAVEPOINT f;
+step s1u: UPDATE foo SET key = 2;
+step s2l: SELECT * FROM foo FOR KEY SHARE; <waiting ...>
+step s1r: ROLLBACK TO f;
+step s2l: <... completed>
+key            value          
+
+1              1              
+step s2c: COMMIT;
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1c: COMMIT;
+
+starting permutation: s1s s1u s2l s2c s1r s1l s1c
+step s1s: SAVEPOINT f;
+step s1u: UPDATE foo SET key = 2;
+step s2l: SELECT * FROM foo FOR KEY SHARE; <waiting ...>
+invalid permutation detected
+
+starting permutation: s1s s2l s1u s1r s1l s1c s2c
+step s1s: SAVEPOINT f;
+step s2l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1u: UPDATE foo SET key = 2; <waiting ...>
+invalid permutation detected
+
+starting permutation: s1s s2l s1u s1r s1l s2c s1c
+step s1s: SAVEPOINT f;
+step s2l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1u: UPDATE foo SET key = 2; <waiting ...>
+invalid permutation detected
+
+starting permutation: s1s s2l s1u s1r s2c s1l s1c
+step s1s: SAVEPOINT f;
+step s2l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1u: UPDATE foo SET key = 2; <waiting ...>
+invalid permutation detected
+
+starting permutation: s1s s2l s1u s2c s1r s1l s1c
+step s1s: SAVEPOINT f;
+step s2l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1u: UPDATE foo SET key = 2; <waiting ...>
+step s2c: COMMIT;
+step s1u: <... completed>
+step s1r: ROLLBACK TO f;
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1c: COMMIT;
+
+starting permutation: s1s s2l s2c s1u s1r s1l s1c
+step s1s: SAVEPOINT f;
+step s2l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s2c: COMMIT;
+step s1u: UPDATE foo SET key = 2;
+step s1r: ROLLBACK TO f;
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1c: COMMIT;
+
+starting permutation: s2l s1s s1u s1r s1l s1c s2c
+step s2l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1s: SAVEPOINT f;
+step s1u: UPDATE foo SET key = 2; <waiting ...>
+invalid permutation detected
+
+starting permutation: s2l s1s s1u s1r s1l s2c s1c
+step s2l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1s: SAVEPOINT f;
+step s1u: UPDATE foo SET key = 2; <waiting ...>
+invalid permutation detected
+
+starting permutation: s2l s1s s1u s1r s2c s1l s1c
+step s2l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1s: SAVEPOINT f;
+step s1u: UPDATE foo SET key = 2; <waiting ...>
+invalid permutation detected
+
+starting permutation: s2l s1s s1u s2c s1r s1l s1c
+step s2l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1s: SAVEPOINT f;
+step s1u: UPDATE foo SET key = 2; <waiting ...>
+step s2c: COMMIT;
+step s1u: <... completed>
+step s1r: ROLLBACK TO f;
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1c: COMMIT;
+
+starting permutation: s2l s1s s2c s1u s1r s1l s1c
+step s2l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1s: SAVEPOINT f;
+step s2c: COMMIT;
+step s1u: UPDATE foo SET key = 2;
+step s1r: ROLLBACK TO f;
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1c: COMMIT;
+
+starting permutation: s2l s2c s1s s1u s1r s1l s1c
+step s2l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s2c: COMMIT;
+step s1s: SAVEPOINT f;
+step s1u: UPDATE foo SET key = 2;
+step s1r: ROLLBACK TO f;
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1c: COMMIT;
diff --git a/src/test/isolation/expected/aborted-keyrevoke_2.out b/src/test/isolation/expected/aborted-keyrevoke_2.out
new file mode 100644
index 00000000000..85f6ccb63ee
--- /dev/null
+++ b/src/test/isolation/expected/aborted-keyrevoke_2.out
@@ -0,0 +1,278 @@
+Parsed test spec with 2 sessions
+
+starting permutation: s1s s1u s1r s1l s1c s2l s2c
+step s1s: SAVEPOINT f;
+step s1u: UPDATE foo SET key = 2;
+step s1r: ROLLBACK TO f;
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1c: COMMIT;
+step s2l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s2c: COMMIT;
+
+starting permutation: s1s s1u s1r s1l s2l s1c s2c
+step s1s: SAVEPOINT f;
+step s1u: UPDATE foo SET key = 2;
+step s1r: ROLLBACK TO f;
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s2l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1c: COMMIT;
+step s2c: COMMIT;
+
+starting permutation: s1s s1u s1r s1l s2l s2c s1c
+step s1s: SAVEPOINT f;
+step s1u: UPDATE foo SET key = 2;
+step s1r: ROLLBACK TO f;
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s2l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s2c: COMMIT;
+step s1c: COMMIT;
+
+starting permutation: s1s s1u s1r s2l s1l s1c s2c
+step s1s: SAVEPOINT f;
+step s1u: UPDATE foo SET key = 2;
+step s1r: ROLLBACK TO f;
+step s2l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1c: COMMIT;
+step s2c: COMMIT;
+
+starting permutation: s1s s1u s1r s2l s1l s2c s1c
+step s1s: SAVEPOINT f;
+step s1u: UPDATE foo SET key = 2;
+step s1r: ROLLBACK TO f;
+step s2l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s2c: COMMIT;
+step s1c: COMMIT;
+
+starting permutation: s1s s1u s1r s2l s2c s1l s1c
+step s1s: SAVEPOINT f;
+step s1u: UPDATE foo SET key = 2;
+step s1r: ROLLBACK TO f;
+step s2l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s2c: COMMIT;
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1c: COMMIT;
+
+starting permutation: s1s s1u s2l s1r s1l s1c s2c
+step s1s: SAVEPOINT f;
+step s1u: UPDATE foo SET key = 2;
+step s2l: SELECT * FROM foo FOR KEY SHARE; <waiting ...>
+step s1r: ROLLBACK TO f;
+step s2l: <... completed>
+key            value          
+
+1              1              
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1c: COMMIT;
+step s2c: COMMIT;
+
+starting permutation: s1s s1u s2l s1r s1l s2c s1c
+step s1s: SAVEPOINT f;
+step s1u: UPDATE foo SET key = 2;
+step s2l: SELECT * FROM foo FOR KEY SHARE; <waiting ...>
+step s1r: ROLLBACK TO f;
+step s2l: <... completed>
+key            value          
+
+1              1              
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s2c: COMMIT;
+step s1c: COMMIT;
+
+starting permutation: s1s s1u s2l s1r s2c s1l s1c
+step s1s: SAVEPOINT f;
+step s1u: UPDATE foo SET key = 2;
+step s2l: SELECT * FROM foo FOR KEY SHARE; <waiting ...>
+step s1r: ROLLBACK TO f;
+step s2l: <... completed>
+key            value          
+
+1              1              
+step s2c: COMMIT;
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1c: COMMIT;
+
+starting permutation: s1s s1u s2l s2c s1r s1l s1c
+step s1s: SAVEPOINT f;
+step s1u: UPDATE foo SET key = 2;
+step s2l: SELECT * FROM foo FOR KEY SHARE; <waiting ...>
+invalid permutation detected
+
+starting permutation: s1s s2l s1u s1r s1l s1c s2c
+step s1s: SAVEPOINT f;
+step s2l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1u: UPDATE foo SET key = 2; <waiting ...>
+invalid permutation detected
+
+starting permutation: s1s s2l s1u s1r s1l s2c s1c
+step s1s: SAVEPOINT f;
+step s2l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1u: UPDATE foo SET key = 2; <waiting ...>
+invalid permutation detected
+
+starting permutation: s1s s2l s1u s1r s2c s1l s1c
+step s1s: SAVEPOINT f;
+step s2l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1u: UPDATE foo SET key = 2; <waiting ...>
+invalid permutation detected
+
+starting permutation: s1s s2l s1u s2c s1r s1l s1c
+step s1s: SAVEPOINT f;
+step s2l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1u: UPDATE foo SET key = 2; <waiting ...>
+step s2c: COMMIT;
+step s1u: <... completed>
+error in steps s2c s1u: ERROR:  could not serialize access due to concurrent update
+step s1r: ROLLBACK TO f;
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1c: COMMIT;
+
+starting permutation: s1s s2l s2c s1u s1r s1l s1c
+step s1s: SAVEPOINT f;
+step s2l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s2c: COMMIT;
+step s1u: UPDATE foo SET key = 2;
+step s1r: ROLLBACK TO f;
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1c: COMMIT;
+
+starting permutation: s2l s1s s1u s1r s1l s1c s2c
+step s2l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1s: SAVEPOINT f;
+step s1u: UPDATE foo SET key = 2; <waiting ...>
+invalid permutation detected
+
+starting permutation: s2l s1s s1u s1r s1l s2c s1c
+step s2l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1s: SAVEPOINT f;
+step s1u: UPDATE foo SET key = 2; <waiting ...>
+invalid permutation detected
+
+starting permutation: s2l s1s s1u s1r s2c s1l s1c
+step s2l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1s: SAVEPOINT f;
+step s1u: UPDATE foo SET key = 2; <waiting ...>
+invalid permutation detected
+
+starting permutation: s2l s1s s1u s2c s1r s1l s1c
+step s2l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1s: SAVEPOINT f;
+step s1u: UPDATE foo SET key = 2; <waiting ...>
+step s2c: COMMIT;
+step s1u: <... completed>
+error in steps s2c s1u: ERROR:  could not serialize access due to concurrent update
+step s1r: ROLLBACK TO f;
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1c: COMMIT;
+
+starting permutation: s2l s1s s2c s1u s1r s1l s1c
+step s2l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1s: SAVEPOINT f;
+step s2c: COMMIT;
+step s1u: UPDATE foo SET key = 2;
+step s1r: ROLLBACK TO f;
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1c: COMMIT;
+
+starting permutation: s2l s2c s1s s1u s1r s1l s1c
+step s2l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s2c: COMMIT;
+step s1s: SAVEPOINT f;
+step s1u: UPDATE foo SET key = 2;
+step s1r: ROLLBACK TO f;
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1c: COMMIT;
diff --git a/src/test/isolation/expected/delete-abort-savept-2.out b/src/test/isolation/expected/delete-abort-savept-2.out
new file mode 100644
index 00000000000..f66a90c6f0f
--- /dev/null
+++ b/src/test/isolation/expected/delete-abort-savept-2.out
@@ -0,0 +1,76 @@
+Parsed test spec with 2 sessions
+
+starting permutation: s1l s1svp s1d s1r s2l s1c s2c
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1svp: SAVEPOINT f;
+step s1d: SELECT * FROM foo FOR NO KEY UPDATE;
+key            value          
+
+1              1              
+step s1r: ROLLBACK TO f;
+step s2l: SELECT * FROM foo FOR UPDATE; <waiting ...>
+step s1c: COMMIT;
+step s2l: <... completed>
+key            value          
+
+1              1              
+step s2c: COMMIT;
+
+starting permutation: s1l s1svp s1d s2l s1r s1c s2c
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1svp: SAVEPOINT f;
+step s1d: SELECT * FROM foo FOR NO KEY UPDATE;
+key            value          
+
+1              1              
+step s2l: SELECT * FROM foo FOR UPDATE; <waiting ...>
+step s1r: ROLLBACK TO f;
+step s1c: COMMIT;
+step s2l: <... completed>
+key            value          
+
+1              1              
+step s2c: COMMIT;
+
+starting permutation: s1l s1svp s1d s1r s2l2 s1c s2c
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1svp: SAVEPOINT f;
+step s1d: SELECT * FROM foo FOR NO KEY UPDATE;
+key            value          
+
+1              1              
+step s1r: ROLLBACK TO f;
+step s2l2: SELECT * FROM foo FOR NO KEY UPDATE;
+key            value          
+
+1              1              
+step s1c: COMMIT;
+step s2c: COMMIT;
+
+starting permutation: s1l s1svp s1d s2l2 s1r s1c s2c
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1svp: SAVEPOINT f;
+step s1d: SELECT * FROM foo FOR NO KEY UPDATE;
+key            value          
+
+1              1              
+step s2l2: SELECT * FROM foo FOR NO KEY UPDATE; <waiting ...>
+step s1r: ROLLBACK TO f;
+step s2l2: <... completed>
+key            value          
+
+1              1              
+step s1c: COMMIT;
+step s2c: COMMIT;
diff --git a/src/test/isolation/expected/delete-abort-savept.out b/src/test/isolation/expected/delete-abort-savept.out
new file mode 100644
index 00000000000..3420cf47d77
--- /dev/null
+++ b/src/test/isolation/expected/delete-abort-savept.out
@@ -0,0 +1,243 @@
+Parsed test spec with 2 sessions
+
+starting permutation: s1l s1svp s1d s1r s1c s2l s2c
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1svp: SAVEPOINT f;
+step s1d: DELETE FROM foo;
+step s1r: ROLLBACK TO f;
+step s1c: COMMIT;
+step s2l: SELECT * FROM foo FOR UPDATE;
+key            value          
+
+1              1              
+step s2c: COMMIT;
+
+starting permutation: s1l s1svp s1d s1r s2l s1c s2c
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1svp: SAVEPOINT f;
+step s1d: DELETE FROM foo;
+step s1r: ROLLBACK TO f;
+step s2l: SELECT * FROM foo FOR UPDATE; <waiting ...>
+step s1c: COMMIT;
+step s2l: <... completed>
+key            value          
+
+1              1              
+step s2c: COMMIT;
+
+starting permutation: s1l s1svp s1d s1r s2l s2c s1c
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1svp: SAVEPOINT f;
+step s1d: DELETE FROM foo;
+step s1r: ROLLBACK TO f;
+step s2l: SELECT * FROM foo FOR UPDATE; <waiting ...>
+invalid permutation detected
+
+starting permutation: s1l s1svp s1d s2l s1r s1c s2c
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1svp: SAVEPOINT f;
+step s1d: DELETE FROM foo;
+step s2l: SELECT * FROM foo FOR UPDATE; <waiting ...>
+step s1r: ROLLBACK TO f;
+step s1c: COMMIT;
+step s2l: <... completed>
+key            value          
+
+1              1              
+step s2c: COMMIT;
+
+starting permutation: s1l s1svp s1d s2l s1r s2c s1c
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1svp: SAVEPOINT f;
+step s1d: DELETE FROM foo;
+step s2l: SELECT * FROM foo FOR UPDATE; <waiting ...>
+step s1r: ROLLBACK TO f;
+invalid permutation detected
+
+starting permutation: s1l s1svp s1d s2l s2c s1r s1c
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1svp: SAVEPOINT f;
+step s1d: DELETE FROM foo;
+step s2l: SELECT * FROM foo FOR UPDATE; <waiting ...>
+invalid permutation detected
+
+starting permutation: s1l s1svp s2l s1d s1r s1c s2c
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1svp: SAVEPOINT f;
+step s2l: SELECT * FROM foo FOR UPDATE; <waiting ...>
+step s1d: DELETE FROM foo;
+step s1r: ROLLBACK TO f;
+step s1c: COMMIT;
+step s2l: <... completed>
+key            value          
+
+1              1              
+step s2c: COMMIT;
+
+starting permutation: s1l s1svp s2l s1d s1r s2c s1c
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1svp: SAVEPOINT f;
+step s2l: SELECT * FROM foo FOR UPDATE; <waiting ...>
+step s1d: DELETE FROM foo;
+step s1r: ROLLBACK TO f;
+invalid permutation detected
+
+starting permutation: s1l s1svp s2l s1d s2c s1r s1c
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1svp: SAVEPOINT f;
+step s2l: SELECT * FROM foo FOR UPDATE; <waiting ...>
+step s1d: DELETE FROM foo;
+invalid permutation detected
+
+starting permutation: s1l s1svp s2l s2c s1d s1r s1c
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1svp: SAVEPOINT f;
+step s2l: SELECT * FROM foo FOR UPDATE; <waiting ...>
+invalid permutation detected
+
+starting permutation: s1l s2l s1svp s1d s1r s1c s2c
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s2l: SELECT * FROM foo FOR UPDATE; <waiting ...>
+step s1svp: SAVEPOINT f;
+step s1d: DELETE FROM foo;
+step s1r: ROLLBACK TO f;
+step s1c: COMMIT;
+step s2l: <... completed>
+key            value          
+
+1              1              
+step s2c: COMMIT;
+
+starting permutation: s1l s2l s1svp s1d s1r s2c s1c
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s2l: SELECT * FROM foo FOR UPDATE; <waiting ...>
+step s1svp: SAVEPOINT f;
+step s1d: DELETE FROM foo;
+step s1r: ROLLBACK TO f;
+invalid permutation detected
+
+starting permutation: s1l s2l s1svp s1d s2c s1r s1c
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s2l: SELECT * FROM foo FOR UPDATE; <waiting ...>
+step s1svp: SAVEPOINT f;
+step s1d: DELETE FROM foo;
+invalid permutation detected
+
+starting permutation: s1l s2l s1svp s2c s1d s1r s1c
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s2l: SELECT * FROM foo FOR UPDATE; <waiting ...>
+step s1svp: SAVEPOINT f;
+invalid permutation detected
+
+starting permutation: s1l s2l s2c s1svp s1d s1r s1c
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s2l: SELECT * FROM foo FOR UPDATE; <waiting ...>
+invalid permutation detected
+
+starting permutation: s2l s1l s1svp s1d s1r s1c s2c
+step s2l: SELECT * FROM foo FOR UPDATE;
+key            value          
+
+1              1              
+step s1l: SELECT * FROM foo FOR KEY SHARE; <waiting ...>
+invalid permutation detected
+
+starting permutation: s2l s1l s1svp s1d s1r s2c s1c
+step s2l: SELECT * FROM foo FOR UPDATE;
+key            value          
+
+1              1              
+step s1l: SELECT * FROM foo FOR KEY SHARE; <waiting ...>
+invalid permutation detected
+
+starting permutation: s2l s1l s1svp s1d s2c s1r s1c
+step s2l: SELECT * FROM foo FOR UPDATE;
+key            value          
+
+1              1              
+step s1l: SELECT * FROM foo FOR KEY SHARE; <waiting ...>
+invalid permutation detected
+
+starting permutation: s2l s1l s1svp s2c s1d s1r s1c
+step s2l: SELECT * FROM foo FOR UPDATE;
+key            value          
+
+1              1              
+step s1l: SELECT * FROM foo FOR KEY SHARE; <waiting ...>
+invalid permutation detected
+
+starting permutation: s2l s1l s2c s1svp s1d s1r s1c
+step s2l: SELECT * FROM foo FOR UPDATE;
+key            value          
+
+1              1              
+step s1l: SELECT * FROM foo FOR KEY SHARE; <waiting ...>
+step s2c: COMMIT;
+step s1l: <... completed>
+key            value          
+
+1              1              
+step s1svp: SAVEPOINT f;
+step s1d: DELETE FROM foo;
+step s1r: ROLLBACK TO f;
+step s1c: COMMIT;
+
+starting permutation: s2l s2c s1l s1svp s1d s1r s1c
+step s2l: SELECT * FROM foo FOR UPDATE;
+key            value          
+
+1              1              
+step s2c: COMMIT;
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s1svp: SAVEPOINT f;
+step s1d: DELETE FROM foo;
+step s1r: ROLLBACK TO f;
+step s1c: COMMIT;
diff --git a/src/test/isolation/expected/fk-contention.out b/src/test/isolation/expected/fk-contention.out
index 24ed72d427c..0916f7f3d28 100644
--- a/src/test/isolation/expected/fk-contention.out
+++ b/src/test/isolation/expected/fk-contention.out
@@ -7,9 +7,8 @@ step upd: UPDATE foo SET b = 'Hello World';
 
 starting permutation: ins upd com
 step ins: INSERT INTO bar VALUES (42);
-step upd: UPDATE foo SET b = 'Hello World'; <waiting ...>
+step upd: UPDATE foo SET b = 'Hello World';
 step com: COMMIT;
-step upd: <... completed>
 
 starting permutation: upd ins com
 step upd: UPDATE foo SET b = 'Hello World';
diff --git a/src/test/isolation/expected/fk-deadlock.out b/src/test/isolation/expected/fk-deadlock.out
index 36813f11f51..69eac88c2b7 100644
--- a/src/test/isolation/expected/fk-deadlock.out
+++ b/src/test/isolation/expected/fk-deadlock.out
@@ -11,57 +11,151 @@ step s2c: COMMIT;
 starting permutation: s1i s1u s2i s1c s2u s2c
 step s1i: INSERT INTO child VALUES (1, 1);
 step s1u: UPDATE parent SET aux = 'bar';
-step s2i: INSERT INTO child VALUES (2, 1); <waiting ...>
+step s2i: INSERT INTO child VALUES (2, 1);
+step s1c: COMMIT;
+step s2u: UPDATE parent SET aux = 'baz';
+step s2c: COMMIT;
+
+starting permutation: s1i s1u s2i s2u s1c s2c
+step s1i: INSERT INTO child VALUES (1, 1);
+step s1u: UPDATE parent SET aux = 'bar';
+step s2i: INSERT INTO child VALUES (2, 1);
+step s2u: UPDATE parent SET aux = 'baz'; <waiting ...>
+step s1c: COMMIT;
+step s2u: <... completed>
+step s2c: COMMIT;
+
+starting permutation: s1i s1u s2i s2u s2c s1c
+step s1i: INSERT INTO child VALUES (1, 1);
+step s1u: UPDATE parent SET aux = 'bar';
+step s2i: INSERT INTO child VALUES (2, 1);
+step s2u: UPDATE parent SET aux = 'baz'; <waiting ...>
+invalid permutation detected
+
+starting permutation: s1i s2i s1u s1c s2u s2c
+step s1i: INSERT INTO child VALUES (1, 1);
+step s2i: INSERT INTO child VALUES (2, 1);
+step s1u: UPDATE parent SET aux = 'bar';
 step s1c: COMMIT;
-step s2i: <... completed>
 step s2u: UPDATE parent SET aux = 'baz';
 step s2c: COMMIT;
 
 starting permutation: s1i s2i s1u s2u s1c s2c
 step s1i: INSERT INTO child VALUES (1, 1);
 step s2i: INSERT INTO child VALUES (2, 1);
+step s1u: UPDATE parent SET aux = 'bar';
+step s2u: UPDATE parent SET aux = 'baz'; <waiting ...>
+step s1c: COMMIT;
+step s2u: <... completed>
+step s2c: COMMIT;
+
+starting permutation: s1i s2i s1u s2u s2c s1c
+step s1i: INSERT INTO child VALUES (1, 1);
+step s2i: INSERT INTO child VALUES (2, 1);
+step s1u: UPDATE parent SET aux = 'bar';
+step s2u: UPDATE parent SET aux = 'baz'; <waiting ...>
+invalid permutation detected
+
+starting permutation: s1i s2i s2u s1u s1c s2c
+step s1i: INSERT INTO child VALUES (1, 1);
+step s2i: INSERT INTO child VALUES (2, 1);
+step s2u: UPDATE parent SET aux = 'baz';
 step s1u: UPDATE parent SET aux = 'bar'; <waiting ...>
+invalid permutation detected
+
+starting permutation: s1i s2i s2u s1u s2c s1c
+step s1i: INSERT INTO child VALUES (1, 1);
+step s2i: INSERT INTO child VALUES (2, 1);
 step s2u: UPDATE parent SET aux = 'baz';
+step s1u: UPDATE parent SET aux = 'bar'; <waiting ...>
+step s2c: COMMIT;
 step s1u: <... completed>
-error in steps s2u s1u: ERROR:  deadlock detected
 step s1c: COMMIT;
+
+starting permutation: s1i s2i s2u s2c s1u s1c
+step s1i: INSERT INTO child VALUES (1, 1);
+step s2i: INSERT INTO child VALUES (2, 1);
+step s2u: UPDATE parent SET aux = 'baz';
 step s2c: COMMIT;
+step s1u: UPDATE parent SET aux = 'bar';
+step s1c: COMMIT;
 
-starting permutation: s1i s2i s2u s1u s2c s1c
+starting permutation: s2i s1i s1u s1c s2u s2c
+step s2i: INSERT INTO child VALUES (2, 1);
 step s1i: INSERT INTO child VALUES (1, 1);
+step s1u: UPDATE parent SET aux = 'bar';
+step s1c: COMMIT;
+step s2u: UPDATE parent SET aux = 'baz';
+step s2c: COMMIT;
+
+starting permutation: s2i s1i s1u s2u s1c s2c
 step s2i: INSERT INTO child VALUES (2, 1);
-step s2u: UPDATE parent SET aux = 'baz'; <waiting ...>
+step s1i: INSERT INTO child VALUES (1, 1);
 step s1u: UPDATE parent SET aux = 'bar';
+step s2u: UPDATE parent SET aux = 'baz'; <waiting ...>
+step s1c: COMMIT;
 step s2u: <... completed>
-error in steps s1u s2u: ERROR:  deadlock detected
 step s2c: COMMIT;
-step s1c: COMMIT;
 
-starting permutation: s2i s1i s1u s2u s1c s2c
+starting permutation: s2i s1i s1u s2u s2c s1c
 step s2i: INSERT INTO child VALUES (2, 1);
 step s1i: INSERT INTO child VALUES (1, 1);
+step s1u: UPDATE parent SET aux = 'bar';
+step s2u: UPDATE parent SET aux = 'baz'; <waiting ...>
+invalid permutation detected
+
+starting permutation: s2i s1i s2u s1u s1c s2c
+step s2i: INSERT INTO child VALUES (2, 1);
+step s1i: INSERT INTO child VALUES (1, 1);
+step s2u: UPDATE parent SET aux = 'baz';
 step s1u: UPDATE parent SET aux = 'bar'; <waiting ...>
+invalid permutation detected
+
+starting permutation: s2i s1i s2u s1u s2c s1c
+step s2i: INSERT INTO child VALUES (2, 1);
+step s1i: INSERT INTO child VALUES (1, 1);
 step s2u: UPDATE parent SET aux = 'baz';
+step s1u: UPDATE parent SET aux = 'bar'; <waiting ...>
+step s2c: COMMIT;
 step s1u: <... completed>
-error in steps s2u s1u: ERROR:  deadlock detected
 step s1c: COMMIT;
-step s2c: COMMIT;
 
-starting permutation: s2i s1i s2u s1u s2c s1c
+starting permutation: s2i s1i s2u s2c s1u s1c
 step s2i: INSERT INTO child VALUES (2, 1);
 step s1i: INSERT INTO child VALUES (1, 1);
-step s2u: UPDATE parent SET aux = 'baz'; <waiting ...>
+step s2u: UPDATE parent SET aux = 'baz';
+step s2c: COMMIT;
 step s1u: UPDATE parent SET aux = 'bar';
-step s2u: <... completed>
-error in steps s1u s2u: ERROR:  deadlock detected
+step s1c: COMMIT;
+
+starting permutation: s2i s2u s1i s1u s1c s2c
+step s2i: INSERT INTO child VALUES (2, 1);
+step s2u: UPDATE parent SET aux = 'baz';
+step s1i: INSERT INTO child VALUES (1, 1);
+step s1u: UPDATE parent SET aux = 'bar'; <waiting ...>
+invalid permutation detected
+
+starting permutation: s2i s2u s1i s1u s2c s1c
+step s2i: INSERT INTO child VALUES (2, 1);
+step s2u: UPDATE parent SET aux = 'baz';
+step s1i: INSERT INTO child VALUES (1, 1);
+step s1u: UPDATE parent SET aux = 'bar'; <waiting ...>
 step s2c: COMMIT;
+step s1u: <... completed>
 step s1c: COMMIT;
 
 starting permutation: s2i s2u s1i s2c s1u s1c
 step s2i: INSERT INTO child VALUES (2, 1);
 step s2u: UPDATE parent SET aux = 'baz';
-step s1i: INSERT INTO child VALUES (1, 1); <waiting ...>
+step s1i: INSERT INTO child VALUES (1, 1);
+step s2c: COMMIT;
+step s1u: UPDATE parent SET aux = 'bar';
+step s1c: COMMIT;
+
+starting permutation: s2i s2u s2c s1i s1u s1c
+step s2i: INSERT INTO child VALUES (2, 1);
+step s2u: UPDATE parent SET aux = 'baz';
 step s2c: COMMIT;
-step s1i: <... completed>
+step s1i: INSERT INTO child VALUES (1, 1);
 step s1u: UPDATE parent SET aux = 'bar';
 step s1c: COMMIT;
diff --git a/src/test/isolation/expected/fk-deadlock2.out b/src/test/isolation/expected/fk-deadlock2.out
index 2d8e5e5b25f..eda118550c2 100644
--- a/src/test/isolation/expected/fk-deadlock2.out
+++ b/src/test/isolation/expected/fk-deadlock2.out
@@ -17,91 +17,138 @@ step s2u1: <... completed>
 step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
 step s2c: COMMIT;
 
+starting permutation: s1u1 s1u2 s2u1 s2u2 s1c s2c
+step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
+step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
+invalid permutation detected
+
+starting permutation: s1u1 s1u2 s2u1 s2u2 s2c s1c
+step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
+step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
+invalid permutation detected
+
+starting permutation: s1u1 s2u1 s1u2 s1c s2u2 s2c
+step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
+step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
+invalid permutation detected
+
 starting permutation: s1u1 s2u1 s1u2 s2u2 s1c s2c
 step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
 step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
 step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
 step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
-step s1u2: <... completed>
-error in steps s2u2 s1u2: ERROR:  deadlock detected
-step s1c: COMMIT;
-step s2c: COMMIT;
+invalid permutation detected
 
 starting permutation: s1u1 s2u1 s1u2 s2u2 s2c s1c
 step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
 step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
 step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
 step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
-step s1u2: <... completed>
-error in steps s2u2 s1u2: ERROR:  deadlock detected
 step s2c: COMMIT;
+step s1u2: <... completed>
 step s1c: COMMIT;
 
 starting permutation: s1u1 s2u1 s2u2 s1u2 s1c s2c
 step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
 step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
-step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
-step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
-step s2u2: <... completed>
-error in steps s1u2 s2u2: ERROR:  deadlock detected
-step s1c: COMMIT;
-step s2c: COMMIT;
+step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
+invalid permutation detected
 
 starting permutation: s1u1 s2u1 s2u2 s1u2 s2c s1c
 step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
 step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
-step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
-step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
-step s2u2: <... completed>
-error in steps s1u2 s2u2: ERROR:  deadlock detected
+step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
 step s2c: COMMIT;
+step s1u2: <... completed>
 step s1c: COMMIT;
 
+starting permutation: s1u1 s2u1 s2u2 s2c s1u2 s1c
+step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
+step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s2c: COMMIT;
+step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s1c: COMMIT;
+
+starting permutation: s2u1 s1u1 s1u2 s1c s2u2 s2c
+step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
+step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
+invalid permutation detected
+
 starting permutation: s2u1 s1u1 s1u2 s2u2 s1c s2c
 step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
 step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
 step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
 step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
-step s1u2: <... completed>
-error in steps s2u2 s1u2: ERROR:  deadlock detected
-step s1c: COMMIT;
-step s2c: COMMIT;
+invalid permutation detected
 
 starting permutation: s2u1 s1u1 s1u2 s2u2 s2c s1c
 step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
 step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
 step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
 step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
-step s1u2: <... completed>
-error in steps s2u2 s1u2: ERROR:  deadlock detected
 step s2c: COMMIT;
+step s1u2: <... completed>
 step s1c: COMMIT;
 
 starting permutation: s2u1 s1u1 s2u2 s1u2 s1c s2c
 step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
 step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
-step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
-step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
-step s2u2: <... completed>
-error in steps s1u2 s2u2: ERROR:  deadlock detected
-step s1c: COMMIT;
-step s2c: COMMIT;
+step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
+invalid permutation detected
 
 starting permutation: s2u1 s1u1 s2u2 s1u2 s2c s1c
 step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
 step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
-step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
+step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
+step s2c: COMMIT;
+step s1u2: <... completed>
+step s1c: COMMIT;
+
+starting permutation: s2u1 s1u1 s2u2 s2c s1u2 s1c
+step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
+step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s2c: COMMIT;
 step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
-step s2u2: <... completed>
-error in steps s1u2 s2u2: ERROR:  deadlock detected
+step s1c: COMMIT;
+
+starting permutation: s2u1 s2u2 s1u1 s1u2 s1c s2c
+step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
+step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
+invalid permutation detected
+
+starting permutation: s2u1 s2u2 s1u1 s1u2 s2c s1c
+step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
+step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
 step s2c: COMMIT;
+step s1u2: <... completed>
 step s1c: COMMIT;
 
 starting permutation: s2u1 s2u2 s1u1 s2c s1u2 s1c
 step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
 step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
-step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1; <waiting ...>
+step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
 step s2c: COMMIT;
-step s1u1: <... completed>
+step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s1c: COMMIT;
+
+starting permutation: s2u1 s2u2 s2c s1u1 s1u2 s1c
+step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s2c: COMMIT;
+step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
 step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
 step s1c: COMMIT;
diff --git a/src/test/isolation/expected/fk-deadlock2_1.out b/src/test/isolation/expected/fk-deadlock2_1.out
index 30c4c998631..382734811cb 100644
--- a/src/test/isolation/expected/fk-deadlock2_1.out
+++ b/src/test/isolation/expected/fk-deadlock2_1.out
@@ -19,92 +19,87 @@ step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
 ERROR:  current transaction is aborted, commands ignored until end of transaction block
 step s2c: COMMIT;
 
-starting permutation: s1u1 s2u1 s1u2 s2u2 s1c s2c
+starting permutation: s1u1 s2u1 s1u2 s2u2 s2c s1c
 step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
 step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
 step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
 step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s2c: COMMIT;
 step s1u2: <... completed>
-error in steps s2u2 s1u2: ERROR:  deadlock detected
+error in steps s2c s1u2: ERROR:  could not serialize access due to concurrent update
 step s1c: COMMIT;
-step s2c: COMMIT;
 
-starting permutation: s1u1 s2u1 s1u2 s2u2 s2c s1c
+starting permutation: s1u1 s2u1 s2u2 s1u2 s2c s1c
 step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
 step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
-step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
 step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
-step s1u2: <... completed>
-error in steps s2u2 s1u2: ERROR:  deadlock detected
+step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
 step s2c: COMMIT;
+step s1u2: <... completed>
+error in steps s2c s1u2: ERROR:  could not serialize access due to concurrent update
 step s1c: COMMIT;
 
-starting permutation: s1u1 s2u1 s2u2 s1u2 s1c s2c
+starting permutation: s1u1 s2u1 s2u2 s2c s1u2 s1c
 step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
 step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
-step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
-step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
-step s2u2: <... completed>
-error in steps s1u2 s2u2: ERROR:  deadlock detected
-step s1c: COMMIT;
+step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
 step s2c: COMMIT;
-
-starting permutation: s1u1 s2u1 s2u2 s1u2 s2c s1c
-step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
-step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
-step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
 step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
-step s2u2: <... completed>
-error in steps s1u2 s2u2: ERROR:  deadlock detected
-step s2c: COMMIT;
+ERROR:  could not serialize access due to read/write dependencies among transactions
 step s1c: COMMIT;
 
-starting permutation: s2u1 s1u1 s1u2 s2u2 s1c s2c
+starting permutation: s2u1 s1u1 s1u2 s2u2 s2c s1c
 step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
 step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
 step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
 step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s2c: COMMIT;
 step s1u2: <... completed>
-error in steps s2u2 s1u2: ERROR:  deadlock detected
+error in steps s2c s1u2: ERROR:  could not serialize access due to concurrent update
 step s1c: COMMIT;
-step s2c: COMMIT;
 
-starting permutation: s2u1 s1u1 s1u2 s2u2 s2c s1c
+starting permutation: s2u1 s1u1 s2u2 s1u2 s2c s1c
 step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
 step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
-step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
 step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
-step s1u2: <... completed>
-error in steps s2u2 s1u2: ERROR:  deadlock detected
+step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
 step s2c: COMMIT;
+step s1u2: <... completed>
+error in steps s2c s1u2: ERROR:  could not serialize access due to concurrent update
 step s1c: COMMIT;
 
-starting permutation: s2u1 s1u1 s2u2 s1u2 s1c s2c
+starting permutation: s2u1 s1u1 s2u2 s2c s1u2 s1c
 step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
 step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
-step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
+step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s2c: COMMIT;
 step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
-step s2u2: <... completed>
-error in steps s1u2 s2u2: ERROR:  deadlock detected
+ERROR:  could not serialize access due to read/write dependencies among transactions
 step s1c: COMMIT;
-step s2c: COMMIT;
 
-starting permutation: s2u1 s1u1 s2u2 s1u2 s2c s1c
+starting permutation: s2u1 s2u2 s1u1 s1u2 s2c s1c
 step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
 step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
-step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
-step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
-step s2u2: <... completed>
-error in steps s1u2 s2u2: ERROR:  deadlock detected
+step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
 step s2c: COMMIT;
+step s1u2: <... completed>
+error in steps s2c s1u2: ERROR:  could not serialize access due to concurrent update
 step s1c: COMMIT;
 
 starting permutation: s2u1 s2u2 s1u1 s2c s1u2 s1c
 step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
 step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
-step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1; <waiting ...>
+step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
 step s2c: COMMIT;
-step s1u1: <... completed>
 step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
 ERROR:  could not serialize access due to read/write dependencies among transactions
 step s1c: COMMIT;
+
+starting permutation: s2u1 s2u2 s2c s1u1 s1u2 s1c
+step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s2c: COMMIT;
+step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
+step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s1c: COMMIT;
diff --git a/src/test/isolation/expected/fk-deadlock2_2.out b/src/test/isolation/expected/fk-deadlock2_2.out
new file mode 100644
index 00000000000..b6be4b98926
--- /dev/null
+++ b/src/test/isolation/expected/fk-deadlock2_2.out
@@ -0,0 +1,105 @@
+Parsed test spec with 2 sessions
+
+starting permutation: s1u1 s1u2 s1c s2u1 s2u2 s2c
+step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
+step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s1c: COMMIT;
+step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s2c: COMMIT;
+
+starting permutation: s1u1 s1u2 s2u1 s1c s2u2 s2c
+step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
+step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
+step s1c: COMMIT;
+step s2u1: <... completed>
+error in steps s1c s2u1: ERROR:  could not serialize access due to concurrent update
+step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+ERROR:  current transaction is aborted, commands ignored until end of transaction block
+step s2c: COMMIT;
+
+starting permutation: s1u1 s2u1 s1u2 s2u2 s2c s1c
+step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
+step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
+step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s2c: COMMIT;
+step s1u2: <... completed>
+error in steps s2c s1u2: ERROR:  could not serialize access due to concurrent update
+step s1c: COMMIT;
+
+starting permutation: s1u1 s2u1 s2u2 s1u2 s2c s1c
+step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
+step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
+step s2c: COMMIT;
+step s1u2: <... completed>
+error in steps s2c s1u2: ERROR:  could not serialize access due to concurrent update
+step s1c: COMMIT;
+
+starting permutation: s1u1 s2u1 s2u2 s2c s1u2 s1c
+step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
+step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s2c: COMMIT;
+step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+ERROR:  could not serialize access due to concurrent update
+step s1c: COMMIT;
+
+starting permutation: s2u1 s1u1 s1u2 s2u2 s2c s1c
+step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
+step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
+step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s2c: COMMIT;
+step s1u2: <... completed>
+error in steps s2c s1u2: ERROR:  could not serialize access due to concurrent update
+step s1c: COMMIT;
+
+starting permutation: s2u1 s1u1 s2u2 s1u2 s2c s1c
+step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
+step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
+step s2c: COMMIT;
+step s1u2: <... completed>
+error in steps s2c s1u2: ERROR:  could not serialize access due to concurrent update
+step s1c: COMMIT;
+
+starting permutation: s2u1 s1u1 s2u2 s2c s1u2 s1c
+step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
+step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s2c: COMMIT;
+step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+ERROR:  could not serialize access due to concurrent update
+step s1c: COMMIT;
+
+starting permutation: s2u1 s2u2 s1u1 s1u2 s2c s1c
+step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
+step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2; <waiting ...>
+step s2c: COMMIT;
+step s1u2: <... completed>
+error in steps s2c s1u2: ERROR:  could not serialize access due to concurrent update
+step s1c: COMMIT;
+
+starting permutation: s2u1 s2u2 s1u1 s2c s1u2 s1c
+step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
+step s2c: COMMIT;
+step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+ERROR:  could not serialize access due to concurrent update
+step s1c: COMMIT;
+
+starting permutation: s2u1 s2u2 s2c s1u1 s1u2 s1c
+step s2u1: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s2u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s2c: COMMIT;
+step s1u1: UPDATE A SET Col1 = 1 WHERE AID = 1;
+step s1u2: UPDATE B SET Col2 = 1 WHERE BID = 2;
+step s1c: COMMIT;
diff --git a/src/test/isolation/expected/fk-deadlock_1.out b/src/test/isolation/expected/fk-deadlock_1.out
index ca75322cc12..d648e48c480 100644
--- a/src/test/isolation/expected/fk-deadlock_1.out
+++ b/src/test/isolation/expected/fk-deadlock_1.out
@@ -11,61 +11,57 @@ step s2c: COMMIT;
 starting permutation: s1i s1u s2i s1c s2u s2c
 step s1i: INSERT INTO child VALUES (1, 1);
 step s1u: UPDATE parent SET aux = 'bar';
-step s2i: INSERT INTO child VALUES (2, 1); <waiting ...>
+step s2i: INSERT INTO child VALUES (2, 1);
 step s1c: COMMIT;
-step s2i: <... completed>
-error in steps s1c s2i: ERROR:  could not serialize access due to concurrent update
 step s2u: UPDATE parent SET aux = 'baz';
-ERROR:  current transaction is aborted, commands ignored until end of transaction block
+ERROR:  could not serialize access due to read/write dependencies among transactions
 step s2c: COMMIT;
 
 starting permutation: s1i s2i s1u s2u s1c s2c
 step s1i: INSERT INTO child VALUES (1, 1);
 step s2i: INSERT INTO child VALUES (2, 1);
-step s1u: UPDATE parent SET aux = 'bar'; <waiting ...>
-step s2u: UPDATE parent SET aux = 'baz';
-step s1u: <... completed>
-error in steps s2u s1u: ERROR:  deadlock detected
+step s1u: UPDATE parent SET aux = 'bar';
+step s2u: UPDATE parent SET aux = 'baz'; <waiting ...>
 step s1c: COMMIT;
+step s2u: <... completed>
+error in steps s1c s2u: ERROR:  could not serialize access due to concurrent update
 step s2c: COMMIT;
 
 starting permutation: s1i s2i s2u s1u s2c s1c
 step s1i: INSERT INTO child VALUES (1, 1);
 step s2i: INSERT INTO child VALUES (2, 1);
-step s2u: UPDATE parent SET aux = 'baz'; <waiting ...>
-step s1u: UPDATE parent SET aux = 'bar';
-step s2u: <... completed>
-error in steps s1u s2u: ERROR:  deadlock detected
+step s2u: UPDATE parent SET aux = 'baz';
+step s1u: UPDATE parent SET aux = 'bar'; <waiting ...>
 step s2c: COMMIT;
+step s1u: <... completed>
+error in steps s2c s1u: ERROR:  could not serialize access due to concurrent update
 step s1c: COMMIT;
 
 starting permutation: s2i s1i s1u s2u s1c s2c
 step s2i: INSERT INTO child VALUES (2, 1);
 step s1i: INSERT INTO child VALUES (1, 1);
-step s1u: UPDATE parent SET aux = 'bar'; <waiting ...>
-step s2u: UPDATE parent SET aux = 'baz';
-step s1u: <... completed>
-error in steps s2u s1u: ERROR:  deadlock detected
+step s1u: UPDATE parent SET aux = 'bar';
+step s2u: UPDATE parent SET aux = 'baz'; <waiting ...>
 step s1c: COMMIT;
+step s2u: <... completed>
+error in steps s1c s2u: ERROR:  could not serialize access due to concurrent update
 step s2c: COMMIT;
 
 starting permutation: s2i s1i s2u s1u s2c s1c
 step s2i: INSERT INTO child VALUES (2, 1);
 step s1i: INSERT INTO child VALUES (1, 1);
-step s2u: UPDATE parent SET aux = 'baz'; <waiting ...>
-step s1u: UPDATE parent SET aux = 'bar';
-step s2u: <... completed>
-error in steps s1u s2u: ERROR:  deadlock detected
+step s2u: UPDATE parent SET aux = 'baz';
+step s1u: UPDATE parent SET aux = 'bar'; <waiting ...>
 step s2c: COMMIT;
+step s1u: <... completed>
+error in steps s2c s1u: ERROR:  could not serialize access due to concurrent update
 step s1c: COMMIT;
 
 starting permutation: s2i s2u s1i s2c s1u s1c
 step s2i: INSERT INTO child VALUES (2, 1);
 step s2u: UPDATE parent SET aux = 'baz';
-step s1i: INSERT INTO child VALUES (1, 1); <waiting ...>
+step s1i: INSERT INTO child VALUES (1, 1);
 step s2c: COMMIT;
-step s1i: <... completed>
-error in steps s2c s1i: ERROR:  could not serialize access due to concurrent update
 step s1u: UPDATE parent SET aux = 'bar';
-ERROR:  current transaction is aborted, commands ignored until end of transaction block
+ERROR:  could not serialize access due to read/write dependencies among transactions
 step s1c: COMMIT;
diff --git a/src/test/isolation/expected/fk-deadlock_2.out b/src/test/isolation/expected/fk-deadlock_2.out
new file mode 100644
index 00000000000..503a7d28239
--- /dev/null
+++ b/src/test/isolation/expected/fk-deadlock_2.out
@@ -0,0 +1,67 @@
+Parsed test spec with 2 sessions
+
+starting permutation: s1i s1u s1c s2i s2u s2c
+step s1i: INSERT INTO child VALUES (1, 1);
+step s1u: UPDATE parent SET aux = 'bar';
+step s1c: COMMIT;
+step s2i: INSERT INTO child VALUES (2, 1);
+step s2u: UPDATE parent SET aux = 'baz';
+step s2c: COMMIT;
+
+starting permutation: s1i s1u s2i s1c s2u s2c
+step s1i: INSERT INTO child VALUES (1, 1);
+step s1u: UPDATE parent SET aux = 'bar';
+step s2i: INSERT INTO child VALUES (2, 1);
+step s1c: COMMIT;
+step s2u: UPDATE parent SET aux = 'baz';
+ERROR:  could not serialize access due to concurrent update
+step s2c: COMMIT;
+
+starting permutation: s1i s2i s1u s2u s1c s2c
+step s1i: INSERT INTO child VALUES (1, 1);
+step s2i: INSERT INTO child VALUES (2, 1);
+step s1u: UPDATE parent SET aux = 'bar';
+step s2u: UPDATE parent SET aux = 'baz'; <waiting ...>
+step s1c: COMMIT;
+step s2u: <... completed>
+error in steps s1c s2u: ERROR:  could not serialize access due to concurrent update
+step s2c: COMMIT;
+
+starting permutation: s1i s2i s2u s1u s2c s1c
+step s1i: INSERT INTO child VALUES (1, 1);
+step s2i: INSERT INTO child VALUES (2, 1);
+step s2u: UPDATE parent SET aux = 'baz';
+step s1u: UPDATE parent SET aux = 'bar'; <waiting ...>
+step s2c: COMMIT;
+step s1u: <... completed>
+error in steps s2c s1u: ERROR:  could not serialize access due to concurrent update
+step s1c: COMMIT;
+
+starting permutation: s2i s1i s1u s2u s1c s2c
+step s2i: INSERT INTO child VALUES (2, 1);
+step s1i: INSERT INTO child VALUES (1, 1);
+step s1u: UPDATE parent SET aux = 'bar';
+step s2u: UPDATE parent SET aux = 'baz'; <waiting ...>
+step s1c: COMMIT;
+step s2u: <... completed>
+error in steps s1c s2u: ERROR:  could not serialize access due to concurrent update
+step s2c: COMMIT;
+
+starting permutation: s2i s1i s2u s1u s2c s1c
+step s2i: INSERT INTO child VALUES (2, 1);
+step s1i: INSERT INTO child VALUES (1, 1);
+step s2u: UPDATE parent SET aux = 'baz';
+step s1u: UPDATE parent SET aux = 'bar'; <waiting ...>
+step s2c: COMMIT;
+step s1u: <... completed>
+error in steps s2c s1u: ERROR:  could not serialize access due to concurrent update
+step s1c: COMMIT;
+
+starting permutation: s2i s2u s1i s2c s1u s1c
+step s2i: INSERT INTO child VALUES (2, 1);
+step s2u: UPDATE parent SET aux = 'baz';
+step s1i: INSERT INTO child VALUES (1, 1);
+step s2c: COMMIT;
+step s1u: UPDATE parent SET aux = 'bar';
+ERROR:  could not serialize access due to concurrent update
+step s1c: COMMIT;
diff --git a/src/test/isolation/expected/fk-delete-insert.out b/src/test/isolation/expected/fk-delete-insert.out
new file mode 100644
index 00000000000..1ab15aaf761
--- /dev/null
+++ b/src/test/isolation/expected/fk-delete-insert.out
@@ -0,0 +1,41 @@
+Parsed test spec with 2 sessions
+
+starting permutation: s1d s1c s2i s2c
+step s1d: DELETE FROM A WHERE AID = 1;
+step s1c: COMMIT;
+step s2i: INSERT INTO B (BID,AID,Col2) VALUES (2,1,0);
+ERROR:  insert or update on table "b" violates foreign key constraint "b_aid_fkey"
+step s2c: COMMIT;
+
+starting permutation: s1d s2i s1c s2c
+step s1d: DELETE FROM A WHERE AID = 1;
+step s2i: INSERT INTO B (BID,AID,Col2) VALUES (2,1,0); <waiting ...>
+step s1c: COMMIT;
+step s2i: <... completed>
+error in steps s1c s2i: ERROR:  insert or update on table "b" violates foreign key constraint "b_aid_fkey"
+step s2c: COMMIT;
+
+starting permutation: s1d s2i s2c s1c
+step s1d: DELETE FROM A WHERE AID = 1;
+step s2i: INSERT INTO B (BID,AID,Col2) VALUES (2,1,0); <waiting ...>
+invalid permutation detected
+
+starting permutation: s2i s1d s1c s2c
+step s2i: INSERT INTO B (BID,AID,Col2) VALUES (2,1,0);
+step s1d: DELETE FROM A WHERE AID = 1; <waiting ...>
+invalid permutation detected
+
+starting permutation: s2i s1d s2c s1c
+step s2i: INSERT INTO B (BID,AID,Col2) VALUES (2,1,0);
+step s1d: DELETE FROM A WHERE AID = 1; <waiting ...>
+step s2c: COMMIT;
+step s1d: <... completed>
+error in steps s2c s1d: ERROR:  update or delete on table "a" violates foreign key constraint "b_aid_fkey" on table "b"
+step s1c: COMMIT;
+
+starting permutation: s2i s2c s1d s1c
+step s2i: INSERT INTO B (BID,AID,Col2) VALUES (2,1,0);
+step s2c: COMMIT;
+step s1d: DELETE FROM A WHERE AID = 1;
+ERROR:  update or delete on table "a" violates foreign key constraint "b_aid_fkey" on table "b"
+step s1c: COMMIT;
diff --git a/src/test/isolation/expected/lock-update-delete.out b/src/test/isolation/expected/lock-update-delete.out
new file mode 100644
index 00000000000..c4248657df8
--- /dev/null
+++ b/src/test/isolation/expected/lock-update-delete.out
@@ -0,0 +1,65 @@
+Parsed test spec with 2 sessions
+
+starting permutation: s1b s2b s1s s2u s2d s1l s2c s1c
+step s1b: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step s2b: BEGIN;
+step s1s: SELECT * FROM foo;
+key            value          
+
+1              1              
+step s2u: UPDATE foo SET value = 2 WHERE key = 1;
+step s2d: DELETE FROM foo;
+step s1l: SELECT * FROM foo FOR KEY SHARE; <waiting ...>
+step s2c: COMMIT;
+step s1l: <... completed>
+error in steps s2c s1l: ERROR:  could not serialize access due to concurrent update
+step s1c: COMMIT;
+
+starting permutation: s1b s2b s1s s2u s2d s1l s2r s1c
+step s1b: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step s2b: BEGIN;
+step s1s: SELECT * FROM foo;
+key            value          
+
+1              1              
+step s2u: UPDATE foo SET value = 2 WHERE key = 1;
+step s2d: DELETE FROM foo;
+step s1l: SELECT * FROM foo FOR KEY SHARE; <waiting ...>
+step s2r: ROLLBACK;
+step s1l: <... completed>
+key            value          
+
+1              1              
+step s1c: COMMIT;
+
+starting permutation: s1b s2b s1s s2u s2u2 s1l s2c s1c
+step s1b: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step s2b: BEGIN;
+step s1s: SELECT * FROM foo;
+key            value          
+
+1              1              
+step s2u: UPDATE foo SET value = 2 WHERE key = 1;
+step s2u2: UPDATE foo SET key = 2 WHERE key = 1;
+step s1l: SELECT * FROM foo FOR KEY SHARE; <waiting ...>
+step s2c: COMMIT;
+step s1l: <... completed>
+error in steps s2c s1l: ERROR:  could not serialize access due to concurrent update
+step s1c: COMMIT;
+
+starting permutation: s1b s2b s1s s2u s2u2 s1l s2r s1c
+step s1b: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step s2b: BEGIN;
+step s1s: SELECT * FROM foo;
+key            value          
+
+1              1              
+step s2u: UPDATE foo SET value = 2 WHERE key = 1;
+step s2u2: UPDATE foo SET key = 2 WHERE key = 1;
+step s1l: SELECT * FROM foo FOR KEY SHARE; <waiting ...>
+step s2r: ROLLBACK;
+step s1l: <... completed>
+key            value          
+
+1              1              
+step s1c: COMMIT;
diff --git a/src/test/isolation/expected/lock-update-traversal.out b/src/test/isolation/expected/lock-update-traversal.out
new file mode 100644
index 00000000000..c8e90661b20
--- /dev/null
+++ b/src/test/isolation/expected/lock-update-traversal.out
@@ -0,0 +1,18 @@
+Parsed test spec with 2 sessions
+
+starting permutation: s1b s2b s1s s2u s1l s2c s2d s1c
+step s1b: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step s2b: BEGIN;
+step s1s: SELECT * FROM foo;
+key            value          
+
+1              1              
+step s2u: UPDATE foo SET value = 2 WHERE key = 1;
+step s1l: SELECT * FROM foo FOR KEY SHARE;
+key            value          
+
+1              1              
+step s2c: COMMIT;
+step s2d: DELETE FROM foo WHERE key = 1; <waiting ...>
+step s1c: COMMIT;
+step s2d: <... completed>
diff --git a/src/test/isolation/expected/multixact-no-deadlock.out b/src/test/isolation/expected/multixact-no-deadlock.out
new file mode 100644
index 00000000000..5ba2e7818e2
--- /dev/null
+++ b/src/test/isolation/expected/multixact-no-deadlock.out
@@ -0,0 +1,24 @@
+Parsed test spec with 3 sessions
+
+starting permutation: s1lock s2lock s1svpt s3lock s1lock2 s2c s1c s3c
+step s1lock: SELECT * FROM justthis FOR SHARE;
+value          
+
+1              
+step s2lock: SELECT * FROM justthis FOR SHARE;
+value          
+
+1              
+step s1svpt: SAVEPOINT foo;
+step s3lock: SELECT * FROM justthis FOR UPDATE; <waiting ...>
+step s1lock2: SELECT * FROM justthis FOR SHARE;
+value          
+
+1              
+step s2c: COMMIT;
+step s1c: COMMIT;
+step s3lock: <... completed>
+value          
+
+1              
+step s3c: COMMIT;
diff --git a/src/test/isolation/isolation_schedule b/src/test/isolation/isolation_schedule
index 1d0770cd37e..c4d6719de6d 100644
--- a/src/test/isolation/isolation_schedule
+++ b/src/test/isolation/isolation_schedule
@@ -14,4 +14,9 @@ test: fk-contention
 test: fk-deadlock
 test: fk-deadlock2
 test: eval-plan-qual
+test: lock-update-delete
+test: lock-update-traversal
+test: delete-abort-savept
+test: delete-abort-savept-2
+test: aborted-keyrevoke
 test: drop-index-concurrently-1
diff --git a/src/test/isolation/isolationtester.c b/src/test/isolation/isolationtester.c
index 4c4556654b3..f1bb87d2f13 100644
--- a/src/test/isolation/isolationtester.c
+++ b/src/test/isolation/isolationtester.c
@@ -564,6 +564,7 @@ run_permutation(TestSpec * testspec, int nsteps, Step ** steps)
 			 * but it can only be unblocked by running steps from other
 			 * sessions.
 			 */
+			fflush(stdout);
 			fprintf(stderr, "invalid permutation detected\n");
 
 			/* Cancel the waiting statement from this session. */
diff --git a/src/test/isolation/specs/aborted-keyrevoke.spec b/src/test/isolation/specs/aborted-keyrevoke.spec
new file mode 100644
index 00000000000..c60aa0cebb2
--- /dev/null
+++ b/src/test/isolation/specs/aborted-keyrevoke.spec
@@ -0,0 +1,31 @@
+# When a tuple that has been updated is locked, the locking command
+# should traverse the update chain; thus, a DELETE should not be able
+# to proceed until the lock has been released.
+
+setup
+{
+  CREATE TABLE foo (
+	key		int PRIMARY KEY,
+	value	int
+  );
+
+  INSERT INTO foo VALUES (1, 1);
+}
+
+teardown
+{
+  DROP TABLE foo;
+}
+
+session "s1"
+setup		{ BEGIN; }
+step "s1s"	{ SAVEPOINT f; }
+step "s1u"	{ UPDATE foo SET key = 2; }	# obtain KEY REVOKE
+step "s1r"	{ ROLLBACK TO f; } # lose KEY REVOKE
+step "s1l"	{ SELECT * FROM foo FOR KEY SHARE; }
+step "s1c"	{ COMMIT; }
+
+session "s2"
+setup		{ BEGIN; }
+step "s2l"	{ SELECT * FROM foo FOR KEY SHARE; }
+step "s2c"	{ COMMIT; }
diff --git a/src/test/isolation/specs/delete-abort-savept-2.spec b/src/test/isolation/specs/delete-abort-savept-2.spec
new file mode 100644
index 00000000000..d35c67f670d
--- /dev/null
+++ b/src/test/isolation/specs/delete-abort-savept-2.spec
@@ -0,0 +1,34 @@
+# A funkier version of delete-abort-savept
+setup
+{
+  CREATE TABLE foo (
+     key INT PRIMARY KEY,
+     value INT
+  );
+
+  INSERT INTO foo VALUES (1, 1);
+}
+
+teardown
+{
+  DROP TABLE foo;
+}
+
+session "s1"
+setup			{ BEGIN; }
+step "s1l"		{ SELECT * FROM foo FOR KEY SHARE; }
+step "s1svp"	{ SAVEPOINT f; }
+step "s1d"		{ SELECT * FROM foo FOR NO KEY UPDATE; }
+step "s1r"		{ ROLLBACK TO f; }
+step "s1c"		{ COMMIT; }
+
+session "s2"
+setup			{ BEGIN; }
+step "s2l"		{ SELECT * FROM foo FOR UPDATE; }
+step "s2l2"		{ SELECT * FROM foo FOR NO KEY UPDATE; }
+step "s2c"		{ COMMIT; }
+
+permutation "s1l" "s1svp" "s1d" "s1r" "s2l" "s1c" "s2c"
+permutation "s1l" "s1svp" "s1d" "s2l" "s1r" "s1c" "s2c"
+permutation "s1l" "s1svp" "s1d" "s1r" "s2l2" "s1c" "s2c"
+permutation "s1l" "s1svp" "s1d" "s2l2" "s1r" "s1c" "s2c"
diff --git a/src/test/isolation/specs/delete-abort-savept.spec b/src/test/isolation/specs/delete-abort-savept.spec
new file mode 100644
index 00000000000..e41df20e89a
--- /dev/null
+++ b/src/test/isolation/specs/delete-abort-savept.spec
@@ -0,0 +1,29 @@
+# After rolling back a subtransaction that upgraded a lock, the previously
+# held lock should still be held.
+setup
+{
+  CREATE TABLE foo (
+     key INT PRIMARY KEY,
+     value INT
+  );
+
+  INSERT INTO foo VALUES (1, 1);
+}
+
+teardown
+{
+  DROP TABLE foo;
+}
+
+session "s1"
+setup			{ BEGIN; }
+step "s1l"		{ SELECT * FROM foo FOR KEY SHARE; }
+step "s1svp"	{ SAVEPOINT f; }
+step "s1d"		{ DELETE FROM foo; }
+step "s1r"		{ ROLLBACK TO f; }
+step "s1c"		{ COMMIT; }
+
+session "s2"
+setup			{ BEGIN; }
+step "s2l"		{ SELECT * FROM foo FOR UPDATE; }
+step "s2c"		{ COMMIT; }
diff --git a/src/test/isolation/specs/fk-deadlock.spec b/src/test/isolation/specs/fk-deadlock.spec
index 9f46c6b665c..44500d5b9bb 100644
--- a/src/test/isolation/specs/fk-deadlock.spec
+++ b/src/test/isolation/specs/fk-deadlock.spec
@@ -29,26 +29,3 @@ setup		{ BEGIN; SET deadlock_timeout = '10s'; }
 step "s2i"	{ INSERT INTO child VALUES (2, 1); }
 step "s2u"	{ UPDATE parent SET aux = 'baz'; }
 step "s2c"	{ COMMIT; }
-
-## Most theoretical permutations require that a blocked session execute a
-## command, making them impossible in practice.
-permutation "s1i" "s1u" "s1c" "s2i" "s2u" "s2c"
-permutation "s1i" "s1u" "s2i" "s1c" "s2u" "s2c"
-#permutation "s1i" "s1u" "s2i" "s2u" "s1c" "s2c"
-#permutation "s1i" "s1u" "s2i" "s2u" "s2c" "s1c"
-#permutation "s1i" "s2i" "s1u" "s1c" "s2u" "s2c"
-permutation "s1i" "s2i" "s1u" "s2u" "s1c" "s2c"
-#permutation "s1i" "s2i" "s1u" "s2u" "s2c" "s1c"
-#permutation "s1i" "s2i" "s2u" "s1u" "s1c" "s2c"
-permutation "s1i" "s2i" "s2u" "s1u" "s2c" "s1c"
-#permutation "s1i" "s2i" "s2u" "s2c" "s1u" "s1c"
-#permutation "s2i" "s1i" "s1u" "s1c" "s2u" "s2c"
-permutation "s2i" "s1i" "s1u" "s2u" "s1c" "s2c"
-#permutation "s2i" "s1i" "s1u" "s2u" "s2c" "s1c"
-#permutation "s2i" "s1i" "s2u" "s1u" "s1c" "s2c"
-permutation "s2i" "s1i" "s2u" "s1u" "s2c" "s1c"
-#permutation "s2i" "s1i" "s2u" "s2c" "s1u" "s1c"
-#permutation "s2i" "s2u" "s1i" "s1u" "s1c" "s2c"
-#permutation "s2i" "s2u" "s1i" "s1u" "s2c" "s1c"
-permutation "s2i" "s2u" "s1i" "s2c" "s1u" "s1c"
-#permutation "s2i" "s2u" "s2c" "s1i" "s1u" "s1c"
diff --git a/src/test/isolation/specs/fk-deadlock2.spec b/src/test/isolation/specs/fk-deadlock2.spec
index a8f1516c4ec..f500b26585c 100644
--- a/src/test/isolation/specs/fk-deadlock2.spec
+++ b/src/test/isolation/specs/fk-deadlock2.spec
@@ -34,26 +34,3 @@ setup		{ BEGIN; SET deadlock_timeout = '10s'; }
 step "s2u1"	{ UPDATE B SET Col2 = 1 WHERE BID = 2; }
 step "s2u2"	{ UPDATE B SET Col2 = 1 WHERE BID = 2; }
 step "s2c"	{ COMMIT; }
-
-## Many theoretical permutations require that a blocked session execute a
-## command, making them impossible in practice.
-permutation "s1u1" "s1u2" "s1c" "s2u1" "s2u2" "s2c"
-permutation "s1u1" "s1u2" "s2u1" "s1c" "s2u2" "s2c"
-#permutation "s1u1" "s1u2" "s2u1" "s2u2" "s1c" "s2c"
-#permutation "s1u1" "s1u2" "s2u1" "s2u2" "s2c" "s1c"
-#permutation "s1u1" "s2u1" "s1u2" "s1c" "s2u2" "s2c"
-permutation "s1u1" "s2u1" "s1u2" "s2u2" "s1c" "s2c"
-permutation "s1u1" "s2u1" "s1u2" "s2u2" "s2c" "s1c"
-permutation "s1u1" "s2u1" "s2u2" "s1u2" "s1c" "s2c"
-permutation "s1u1" "s2u1" "s2u2" "s1u2" "s2c" "s1c"
-#permutation "s1u1" "s2u1" "s2u2" "s2c" "s1u2" "s1c"
-#permutation "s2u1" "s1u1" "s1u2" "s1c" "s2u2" "s2c"
-permutation "s2u1" "s1u1" "s1u2" "s2u2" "s1c" "s2c"
-permutation "s2u1" "s1u1" "s1u2" "s2u2" "s2c" "s1c"
-permutation "s2u1" "s1u1" "s2u2" "s1u2" "s1c" "s2c"
-permutation "s2u1" "s1u1" "s2u2" "s1u2" "s2c" "s1c"
-#permutation "s2u1" "s1u1" "s2u2" "s2c" "s1u2" "s1c"
-#permutation "s2u1" "s2u2" "s1u1" "s1u2" "s1c" "s2c"
-#permutation "s2u1" "s2u2" "s1u1" "s1u2" "s2c" "s1c"
-permutation "s2u1" "s2u2" "s1u1" "s2c" "s1u2" "s1c"
-#permutation "s2u1" "s2u2" "s2c" "s1u1" "s1u2" "s1c"
diff --git a/src/test/isolation/specs/lock-update-delete.spec b/src/test/isolation/specs/lock-update-delete.spec
new file mode 100644
index 00000000000..4b9a5a64ed0
--- /dev/null
+++ b/src/test/isolation/specs/lock-update-delete.spec
@@ -0,0 +1,38 @@
+# If we update a tuple, and then delete (or update that touches the key) it,
+# and later somebody tries to come along and traverse that update chain,
+# he should get an error when locking the latest version, if the delete
+# committed; or succeed, when the deleting transaction rolls back.
+
+setup
+{
+  CREATE TABLE foo (
+	key		int PRIMARY KEY,
+	value	int
+  );
+
+  INSERT INTO foo VALUES (1, 1);
+}
+
+teardown
+{
+  DROP TABLE foo;
+}
+
+session "s1"
+step "s1b"	{ BEGIN ISOLATION LEVEL REPEATABLE READ; }
+step "s1s"	{ SELECT * FROM foo; }	# obtain snapshot
+step "s1l"	{ SELECT * FROM foo FOR KEY SHARE; } # obtain lock
+step "s1c"	{ COMMIT; }
+
+session "s2"
+step "s2b"	{ BEGIN; }
+step "s2u"	{ UPDATE foo SET value = 2 WHERE key = 1; }
+step "s2d"	{ DELETE FROM foo; }
+step "s2u2"	{ UPDATE foo SET key = 2 WHERE key = 1; }
+step "s2c"	{ COMMIT; }
+step "s2r"	{ ROLLBACK; }
+
+permutation "s1b" "s2b" "s1s" "s2u" "s2d" "s1l" "s2c" "s1c"
+permutation "s1b" "s2b" "s1s" "s2u" "s2d" "s1l" "s2r" "s1c"
+permutation "s1b" "s2b" "s1s" "s2u" "s2u2" "s1l" "s2c" "s1c"
+permutation "s1b" "s2b" "s1s" "s2u" "s2u2" "s1l" "s2r" "s1c"
diff --git a/src/test/isolation/specs/lock-update-traversal.spec b/src/test/isolation/specs/lock-update-traversal.spec
new file mode 100644
index 00000000000..6c6c805d50e
--- /dev/null
+++ b/src/test/isolation/specs/lock-update-traversal.spec
@@ -0,0 +1,32 @@
+# When a tuple that has been updated is locked, the locking command
+# should traverse the update chain; thus, a DELETE should not be able
+# to proceed until the lock has been released.
+
+setup
+{
+  CREATE TABLE foo (
+	key		int PRIMARY KEY,
+	value	int
+  );
+
+  INSERT INTO foo VALUES (1, 1);
+}
+
+teardown
+{
+  DROP TABLE foo;
+}
+
+session "s1"
+step "s1b"	{ BEGIN ISOLATION LEVEL REPEATABLE READ; }
+step "s1s"	{ SELECT * FROM foo; }	# obtain snapshot
+step "s1l"	{ SELECT * FROM foo FOR KEY SHARE; } # obtain lock
+step "s1c"	{ COMMIT; }
+
+session "s2"
+step "s2b"	{ BEGIN; }
+step "s2u"	{ UPDATE foo SET value = 2 WHERE key = 1; }
+step "s2c"	{ COMMIT; }
+step "s2d"	{ DELETE FROM foo WHERE key = 1; }
+
+permutation "s1b" "s2b" "s1s" "s2u" "s1l" "s2c" "s2d" "s1c"
diff --git a/src/test/isolation/specs/multixact-no-deadlock.spec b/src/test/isolation/specs/multixact-no-deadlock.spec
new file mode 100644
index 00000000000..205658b897e
--- /dev/null
+++ b/src/test/isolation/specs/multixact-no-deadlock.spec
@@ -0,0 +1,35 @@
+# If we already hold a lock of a given strength, do not deadlock when
+# some other transaction is waiting for a conflicting lock and we try
+# to acquire the same lock we already held.
+setup
+{
+  CREATE TABLE justthis (
+	value	int
+  );
+
+  INSERT INTO justthis VALUES (1);
+}
+
+teardown
+{
+  DROP TABLE justthis;
+}
+
+session "s1"
+setup			{ BEGIN; }
+step "s1lock"	{ SELECT * FROM justthis FOR SHARE; }
+step "s1svpt"	{ SAVEPOINT foo; }
+step "s1lock2"	{ SELECT * FROM justthis FOR SHARE; }
+step "s1c"		{ COMMIT; }
+
+session "s2"
+setup			{ BEGIN; }
+step "s2lock"	{ SELECT * FROM justthis FOR SHARE; }	# ensure it's a multi
+step "s2c"		{ COMMIT; }
+
+session "s3"
+setup			{ BEGIN; }
+step "s3lock"	{ SELECT * FROM justthis FOR UPDATE; }
+step "s3c"		{ COMMIT; }
+
+permutation "s1lock" "s2lock" "s1svpt" "s3lock" "s1lock2" "s2c" "s1c" "s3c"