Implement SKIP LOCKED for row-level locks

This clause changes the behavior of SELECT locking clauses in the
presence of locked rows: instead of causing a process to block waiting
for the locks held by other processes (or raise an error, with NOWAIT),
SKIP LOCKED makes the new reader skip over such rows.  While this is not
appropriate behavior for general purposes, there are some cases in which
it is useful, such as queue-like tables.

Catalog version bumped because this patch changes the representation of
stored rules.

Reviewed by Craig Ringer (based on a previous attempt at an
implementation by Simon Riggs, who also provided input on the syntax
used in the current patch), David Rowley, and Álvaro Herrera.

Author: Thomas Munro

5 files changed, 509 insertions, 0 deletions

diff --git a/src/test/isolation/expected/skip-locked-2.out b/src/test/isolation/expected/skip-locked-2.out
new file mode 100644
index 0000000000..9240543f3f
--- /dev/null
+++ b/src/test/isolation/expected/skip-locked-2.out
@@ -0,0 +1,49 @@
+Parsed test spec with 2 sessions
+
+starting permutation: s1a s2a s2b s1b s2c
+step s1a: SELECT * FROM queue ORDER BY id FOR SHARE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s2a: SELECT * FROM queue ORDER BY id FOR SHARE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s2b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s1b: COMMIT;
+step s2c: COMMIT;
+
+starting permutation: s2a s1a s2b s1b s2c
+step s2a: SELECT * FROM queue ORDER BY id FOR SHARE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s1a: SELECT * FROM queue ORDER BY id FOR SHARE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s2b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s1b: COMMIT;
+step s2c: COMMIT;
+
+starting permutation: s2a s2b s1a s1b s2c
+step s2a: SELECT * FROM queue ORDER BY id FOR SHARE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s2b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s1a: SELECT * FROM queue ORDER BY id FOR SHARE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s1b: COMMIT;
+step s2c: COMMIT;
diff --git a/src/test/isolation/expected/skip-locked-3.out b/src/test/isolation/expected/skip-locked-3.out
new file mode 100644
index 0000000000..fa8fe87d8a
--- /dev/null
+++ b/src/test/isolation/expected/skip-locked-3.out
@@ -0,0 +1,19 @@
+Parsed test spec with 3 sessions
+
+starting permutation: s1a s2a s3a s1b s2b s3b
+step s1a: SELECT * FROM queue ORDER BY id FOR UPDATE LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s2a: SELECT * FROM queue ORDER BY id FOR UPDATE LIMIT 1; <waiting ...>
+step s3a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s1b: COMMIT;
+step s2a: <... completed>
+id             data           status         
+
+1              foo            NEW            
+step s2b: COMMIT;
+step s3b: COMMIT;
diff --git a/src/test/isolation/expected/skip-locked-4.out b/src/test/isolation/expected/skip-locked-4.out
new file mode 100644
index 0000000000..2c9cfe895e
--- /dev/null
+++ b/src/test/isolation/expected/skip-locked-4.out
@@ -0,0 +1,21 @@
+Parsed test spec with 2 sessions
+
+starting permutation: s2a s1a s2b s2c s2d s2e s1b s2f
+step s2a: SELECT pg_advisory_lock(0);
+pg_advisory_lock
+
+               
+step s1a: SELECT * FROM foo WHERE pg_advisory_lock(0) IS NOT NULL ORDER BY id LIMIT 1 FOR UPDATE SKIP LOCKED; <waiting ...>
+step s2b: UPDATE foo SET data = data WHERE id = 1;
+step s2c: BEGIN;
+step s2d: UPDATE foo SET data = data WHERE id = 1;
+step s2e: SELECT pg_advisory_unlock(0);
+pg_advisory_unlock
+
+t              
+step s1a: <... completed>
+id             data           
+
+2              x              
+step s1b: COMMIT;
+step s2f: COMMIT;
diff --git a/src/test/isolation/expected/skip-locked-4_1.out b/src/test/isolation/expected/skip-locked-4_1.out
new file mode 100644
index 0000000000..552429ae89
--- /dev/null
+++ b/src/test/isolation/expected/skip-locked-4_1.out
@@ -0,0 +1,19 @@
+Parsed test spec with 2 sessions
+
+starting permutation: s2a s1a s2b s2c s2d s2e s1b s2f
+step s2a: SELECT pg_advisory_lock(0);
+pg_advisory_lock
+
+               
+step s1a: SELECT * FROM foo WHERE pg_advisory_lock(0) IS NOT NULL ORDER BY id LIMIT 1 FOR UPDATE SKIP LOCKED; <waiting ...>
+step s2b: UPDATE foo SET data = data WHERE id = 1;
+step s2c: BEGIN;
+step s2d: UPDATE foo SET data = data WHERE id = 1;
+step s2e: SELECT pg_advisory_unlock(0);
+pg_advisory_unlock
+
+t              
+step s1a: <... completed>
+error in steps s2e s1a: ERROR:  could not serialize access due to concurrent update
+step s1b: COMMIT;
+step s2f: COMMIT;
diff --git a/src/test/isolation/expected/skip-locked.out b/src/test/isolation/expected/skip-locked.out
new file mode 100644
index 0000000000..f9b9cf28be
--- /dev/null
+++ b/src/test/isolation/expected/skip-locked.out
@@ -0,0 +1,401 @@
+Parsed test spec with 2 sessions
+
+starting permutation: s1a s1b s1c s2a s2b s2c
+step s1a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s1b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s1c: COMMIT;
+step s2a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s2b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s2c: COMMIT;
+
+starting permutation: s1a s1b s2a s1c s2b s2c
+step s1a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s1b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s2a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s1c: COMMIT;
+step s2b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s2c: COMMIT;
+
+starting permutation: s1a s1b s2a s2b s1c s2c
+step s1a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s1b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s2a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s2b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s1c: COMMIT;
+step s2c: COMMIT;
+
+starting permutation: s1a s1b s2a s2b s2c s1c
+step s1a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s1b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s2a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s2b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s2c: COMMIT;
+step s1c: COMMIT;
+
+starting permutation: s1a s2a s1b s1c s2b s2c
+step s1a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s2a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s1b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s1c: COMMIT;
+step s2b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s2c: COMMIT;
+
+starting permutation: s1a s2a s1b s2b s1c s2c
+step s1a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s2a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s1b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s2b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s1c: COMMIT;
+step s2c: COMMIT;
+
+starting permutation: s1a s2a s1b s2b s2c s1c
+step s1a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s2a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s1b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s2b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s2c: COMMIT;
+step s1c: COMMIT;
+
+starting permutation: s1a s2a s2b s1b s1c s2c
+step s1a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s2a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s2b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s1b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s1c: COMMIT;
+step s2c: COMMIT;
+
+starting permutation: s1a s2a s2b s1b s2c s1c
+step s1a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s2a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s2b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s1b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s2c: COMMIT;
+step s1c: COMMIT;
+
+starting permutation: s1a s2a s2b s2c s1b s1c
+step s1a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s2a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s2b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s2c: COMMIT;
+step s1b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s1c: COMMIT;
+
+starting permutation: s2a s1a s1b s1c s2b s2c
+step s2a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s1a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s1b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s1c: COMMIT;
+step s2b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s2c: COMMIT;
+
+starting permutation: s2a s1a s1b s2b s1c s2c
+step s2a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s1a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s1b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s2b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s1c: COMMIT;
+step s2c: COMMIT;
+
+starting permutation: s2a s1a s1b s2b s2c s1c
+step s2a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s1a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s1b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s2b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s2c: COMMIT;
+step s1c: COMMIT;
+
+starting permutation: s2a s1a s2b s1b s1c s2c
+step s2a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s1a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s2b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s1b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s1c: COMMIT;
+step s2c: COMMIT;
+
+starting permutation: s2a s1a s2b s1b s2c s1c
+step s2a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s1a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s2b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s1b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s2c: COMMIT;
+step s1c: COMMIT;
+
+starting permutation: s2a s1a s2b s2c s1b s1c
+step s2a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s1a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s2b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s2c: COMMIT;
+step s1b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s1c: COMMIT;
+
+starting permutation: s2a s2b s1a s1b s1c s2c
+step s2a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s2b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s1a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s1b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s1c: COMMIT;
+step s2c: COMMIT;
+
+starting permutation: s2a s2b s1a s1b s2c s1c
+step s2a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s2b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s1a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s1b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s2c: COMMIT;
+step s1c: COMMIT;
+
+starting permutation: s2a s2b s1a s2c s1b s1c
+step s2a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s2b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s1a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+2              bar            NEW            
+step s2c: COMMIT;
+step s1b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s1c: COMMIT;
+
+starting permutation: s2a s2b s2c s1a s1b s1c
+step s2a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s2b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s2c: COMMIT;
+step s1a: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s1b: SELECT * FROM queue ORDER BY id FOR UPDATE SKIP LOCKED LIMIT 1;
+id             data           status         
+
+1              foo            NEW            
+step s1c: COMMIT;