Add missing EPQ recheck for TID Scan

The EvalPlanQual recheck for TID Scan wasn't rechecking the TID qual
still passed after following update chains.  This could result in tuples
being updated or deleted by plans using TID Scans where the ctid of the
new (updated) tuple no longer matches the clause of the scan.  This isn't
desired behavior, and isn't consistent with what would happen if the
chosen plan had used an Index or Seq Scan, and that could lead to hard to
predict behavior for scans that contain TID quals and other quals as the
planner has freedom to choose TID or some other scan method for such
queries, and the chosen plan could change at any moment.

Here we fix this by properly implementing the recheck function for TID
Scans.

Backpatch to 13, oldest supported version

Reported-by: Sophie Alpert <pg@sophiebits.com>
Author: Sophie Alpert <pg@sophiebits.com>
Author: David Rowley <dgrowleyml@gmail.com>
Reviewed-by: David Rowley <dgrowleyml@gmail.com>
Reviewed-by: Chao Li <li.evan.chao@gmail.com>
Discussion: https://postgr.es/m/4a6268ff-3340-453a-9bf5-c98d51a6f729@app.fastmail.com
Backpatch-through: 13

3 files changed, 97 insertions, 4 deletions

diff --git a/src/backend/executor/nodeTidscan.c b/src/backend/executor/nodeTidscan.c
index 5e56e29a15f..d50c6600358 100644
--- a/src/backend/executor/nodeTidscan.c
+++ b/src/backend/executor/nodeTidscan.c
@@ -402,12 +402,23 @@ TidNext(TidScanState *node)
 static bool
 TidRecheck(TidScanState *node, TupleTableSlot *slot)
 {
+	ItemPointer match;
+
+	/* WHERE CURRENT OF always intends to resolve to the latest tuple */
+	if (node->tss_isCurrentOf)
+		return true;
+
+	if (node->tss_TidList == NULL)
+		TidListEval(node);
+
 	/*
-	 * XXX shouldn't we check here to make sure tuple matches TID list? In
-	 * runtime-key case this is not certain, is it?  However, in the WHERE
-	 * CURRENT OF case it might not match anyway ...
+	 * Binary search the TidList to see if this ctid is mentioned and return
+	 * true if it is.
 	 */
-	return true;
+	match = (ItemPointer) bsearch(&slot->tts_tid, node->tss_TidList,
+								  node->tss_NumTids, sizeof(ItemPointerData),
+								  itemptr_comparator);
+	return match != NULL;
 }
 
 
diff --git a/src/test/isolation/expected/eval-plan-qual.out b/src/test/isolation/expected/eval-plan-qual.out
index 032d4208d51..2cba44f2bde 100644
--- a/src/test/isolation/expected/eval-plan-qual.out
+++ b/src/test/isolation/expected/eval-plan-qual.out
@@ -1218,6 +1218,77 @@ subid|id
 (1 row)
 
 
+starting permutation: tid1 tid2 c1 c2 read
+step tid1: UPDATE accounts SET balance = balance + 100 WHERE ctid = '(0,1)' RETURNING accountid, balance;
+accountid|balance
+---------+-------
+checking |    700
+(1 row)
+
+step tid2: UPDATE accounts SET balance = balance + 200 WHERE ctid = '(0,1)' RETURNING accountid, balance; <waiting ...>
+step c1: COMMIT;
+step tid2: <... completed>
+accountid|balance
+---------+-------
+(0 rows)
+
+step c2: COMMIT;
+step read: SELECT * FROM accounts ORDER BY accountid;
+accountid|balance|balance2
+---------+-------+--------
+checking |    700|    1400
+savings  |    600|    1200
+(2 rows)
+
+
+starting permutation: tid1 tidsucceed2 c1 c2 read
+step tid1: UPDATE accounts SET balance = balance + 100 WHERE ctid = '(0,1)' RETURNING accountid, balance;
+accountid|balance
+---------+-------
+checking |    700
+(1 row)
+
+step tidsucceed2: UPDATE accounts SET balance = balance + 200 WHERE ctid = '(0,1)' OR ctid = '(0,3)' RETURNING accountid, balance; <waiting ...>
+step c1: COMMIT;
+step tidsucceed2: <... completed>
+accountid|balance
+---------+-------
+checking |    900
+(1 row)
+
+step c2: COMMIT;
+step read: SELECT * FROM accounts ORDER BY accountid;
+accountid|balance|balance2
+---------+-------+--------
+checking |    900|    1800
+savings  |    600|    1200
+(2 rows)
+
+
+starting permutation: tid1 tid2 r1 c2 read
+step tid1: UPDATE accounts SET balance = balance + 100 WHERE ctid = '(0,1)' RETURNING accountid, balance;
+accountid|balance
+---------+-------
+checking |    700
+(1 row)
+
+step tid2: UPDATE accounts SET balance = balance + 200 WHERE ctid = '(0,1)' RETURNING accountid, balance; <waiting ...>
+step r1: ROLLBACK;
+step tid2: <... completed>
+accountid|balance
+---------+-------
+checking |    800
+(1 row)
+
+step c2: COMMIT;
+step read: SELECT * FROM accounts ORDER BY accountid;
+accountid|balance|balance2
+---------+-------+--------
+checking |    800|    1600
+savings  |    600|    1200
+(2 rows)
+
+
 starting permutation: simplepartupdate conditionalpartupdate c1 c2 read_part
 step simplepartupdate: 
 	update parttbl set b = b + 10;
diff --git a/src/test/isolation/specs/eval-plan-qual.spec b/src/test/isolation/specs/eval-plan-qual.spec
index 07307e623e4..b8983ea215f 100644
--- a/src/test/isolation/specs/eval-plan-qual.spec
+++ b/src/test/isolation/specs/eval-plan-qual.spec
@@ -99,6 +99,9 @@ step upsert1	{
 	  WHERE NOT EXISTS (SELECT 1 FROM upsert);
 }
 
+# Tests for Tid Scan
+step tid1 { UPDATE accounts SET balance = balance + 100 WHERE ctid = '(0,1)' RETURNING accountid, balance; }
+
 # tests with table p check inheritance cases:
 # readp1/writep1/readp2 tests a bug where nodeLockRows did the wrong thing
 # when the first updated tuple was in a non-first child table.
@@ -241,6 +244,10 @@ step updateforcip3	{
 step wrtwcte	{ UPDATE table_a SET value = 'tableAValue2' WHERE id = 1; }
 step wrjt	{ UPDATE jointest SET data = 42 WHERE id = 7; }
 
+step tid2 { UPDATE accounts SET balance = balance + 200 WHERE ctid = '(0,1)' RETURNING accountid, balance; }
+# here, recheck succeeds; (0,3) is the id that step tid1 will assign
+step tidsucceed2 { UPDATE accounts SET balance = balance + 200 WHERE ctid = '(0,1)' OR ctid = '(0,3)' RETURNING accountid, balance; }
+
 step conditionalpartupdate	{
 	update parttbl set c = -c where b < 10;
 }
@@ -392,6 +399,10 @@ permutation wrtwcte readwcte c1 c2
 permutation wrjt selectjoinforupdate c2 c1
 permutation wrjt selectresultforupdate c2 c1
 permutation wrtwcte multireadwcte c1 c2
+permutation tid1 tid2 c1 c2 read
+permutation tid1 tidsucceed2 c1 c2 read
+# test that a rollback on s1 has s2 perform the update on the original row
+permutation tid1 tid2 r1 c2 read
 
 permutation simplepartupdate conditionalpartupdate c1 c2 read_part
 permutation simplepartupdate complexpartupdate c1 c2 read_part