Fix missing EvalPlanQual recheck for TID scans

Started by Sophie Alpert4 months ago24 messages
#1Sophie Alpert
pg@sophiebits.com
1 attachment(s)

Hi all,

I learned that the TID Scan node does not properly implement EvalPlanQual recheck, which has already been noted in comment added in 2002 (commit 6799a6ca21). This does seem to have the potential to manifest in observable and surprising ways when queries are filtering on `ctid`, like for optimistic concurrency control as in https://stackoverflow.com/q/78487441.

Attached is an attempt from me at fixing this issue for TID Scan as well as TID Range Scan which appears to have the same issue.

This is my first time looking at the Postgres source (nor do I work with C on a regular basis), so I will not be surprised to hear that I've done things wrong, but I'm hopeful that this is usable as written. Running `meson test` passes for me, including the added isolation tests, and I confirmed that both of the tests that now result in a negative recheck were previously failing.

In my implementation I am calling TidRangeEval every time TidRangeRecheck is called; let me know if this is a performance concern. It didn't seem that any of the existing TidRangeScanState flags are quite right to know if the bounds have been initialized, but I am happy to add one.

The original issue appears to have been present since the introduction of TID scans in 1999 (commit 6f9ff92cc0) so I imagine it may make sense to backport the fix, although evidently not many people are running into this.

Thanks,
Sophie

Attachments:

0001-Fix-missing-EvalPlanQual-recheck-for-TID-scans.v1.patchapplication/octet-stream; name="=?UTF-8?Q?0001-Fix-missing-EvalPlanQual-recheck-for-TID-scans.v1.patch?="Download
From c9d0b873f6a093de44edb95ba17076cf9ffe9198 Mon Sep 17 00:00:00 2001
From: Sophie Alpert <git@sophiebits.com>
Date: Sat, 6 Sep 2025 00:30:34 -0700
Subject: [PATCH] Fix missing EvalPlanQual recheck for TID scans

---
 src/backend/executor/nodeTidrangescan.c       |  5 +-
 src/backend/executor/nodeTidscan.c            | 18 +++--
 .../isolation/expected/eval-plan-qual.out     | 70 +++++++++++++++++++
 src/test/isolation/specs/eval-plan-qual.spec  | 13 ++++
 4 files changed, 99 insertions(+), 7 deletions(-)

diff --git a/src/backend/executor/nodeTidrangescan.c b/src/backend/executor/nodeTidrangescan.c
index 26f7420b64b..ef40be856f6 100644
--- a/src/backend/executor/nodeTidrangescan.c
+++ b/src/backend/executor/nodeTidrangescan.c
@@ -274,7 +274,10 @@ TidRangeNext(TidRangeScanState *node)
 static bool
 TidRangeRecheck(TidRangeScanState *node, TupleTableSlot *slot)
 {
-	return true;
+	if (!TidRangeEval(node))
+		return false;
+	return ItemPointerCompare(&node->trss_mintid, &slot->tts_tid) <= 0
+		&& ItemPointerCompare(&slot->tts_tid, &node->trss_maxtid) <= 0;
 }
 
 /* ----------------------------------------------------------------
diff --git a/src/backend/executor/nodeTidscan.c b/src/backend/executor/nodeTidscan.c
index 5e56e29a15f..c1499cded33 100644
--- a/src/backend/executor/nodeTidscan.c
+++ b/src/backend/executor/nodeTidscan.c
@@ -402,12 +402,18 @@ TidNext(TidScanState *node)
 static bool
 TidRecheck(TidScanState *node, TupleTableSlot *slot)
 {
-	/*
-	 * 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 ...
-	 */
-	return true;
+	void *match;
+
+	if (node->tss_isCurrentOf)
+		/* WHERE CURRENT OF always intends to resolve to the latest tuple */
+		return true;
+
+	if (node->tss_TidList == NULL)
+		TidListEval(node);
+
+	match = 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..5687911920b 100644
--- a/src/test/isolation/expected/eval-plan-qual.out
+++ b/src/test/isolation/expected/eval-plan-qual.out
@@ -1218,6 +1218,76 @@ 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: tidrange1 tidrange2 c1 c2 read
+step tidrange1: UPDATE accounts SET balance = balance + 100 WHERE ctid < '(0,2)' RETURNING accountid, balance;
+accountid|balance
+---------+-------
+checking |    700
+(1 row)
+
+step tidrange2: UPDATE accounts SET balance = balance + 200 WHERE ctid < '(0,2)' RETURNING accountid, balance; <waiting ...>
+step c1: COMMIT;
+step tidrange2: <... 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: 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..c4f98c78f68 100644
--- a/src/test/isolation/specs/eval-plan-qual.spec
+++ b/src/test/isolation/specs/eval-plan-qual.spec
@@ -99,6 +99,11 @@ step upsert1	{
 	  WHERE NOT EXISTS (SELECT 1 FROM upsert);
 }
 
+# ctid predicate
+# same filter in both sessions; only one should succeed
+step tid1 { UPDATE accounts SET balance = balance + 100 WHERE ctid = '(0,1)' RETURNING accountid, balance; }
+step tidrange1 { UPDATE accounts SET balance = balance + 100 WHERE ctid < '(0,2)' 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 +246,11 @@ 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; }
+step tidrange2 { UPDATE accounts SET balance = balance + 200 WHERE ctid < '(0,2)' 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 +402,9 @@ 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
+permutation tidrange1 tidrange2 c1 c2 read
 
 permutation simplepartupdate conditionalpartupdate c1 c2 read_part
 permutation simplepartupdate complexpartupdate c1 c2 read_part
-- 
2.39.5 (Apple Git-154)

#2David Rowley
dgrowleyml@gmail.com
In reply to: Sophie Alpert (#1)
Re: Fix missing EvalPlanQual recheck for TID scans

On Mon, 8 Sept 2025 at 10:31, Sophie Alpert <pg@sophiebits.com> wrote:

I learned that the TID Scan node does not properly implement EvalPlanQual recheck, which has already been noted in comment added in 2002 (commit 6799a6ca21). This does seem to have the potential to manifest in observable and surprising ways when queries are filtering on `ctid`, like for optimistic concurrency control as in https://stackoverflow.com/q/78487441.

Thanks for the report and the patch.

I'll summarise this issue, as you provided an external link which
might one day disappear:

drop table if exists test_optimistic_lock;
create table public.test_optimistic_lock (
id bigserial primary key,
name varchar,
rest_count integer,
update_user varchar,
update_time timestamp without time zone,
create_time timestamp without time zone
);

insert into public.test_optimistic_lock (name, rest_count,
update_time, create_time) values
('Product1', 1, current_timestamp, current_timestamp);

S1: begin;
S1: select ctid, rest_count from public.test_optimistic_lock where
name = 'Product1';

S2: begin;
S2: select ctid, rest_count from public.test_optimistic_lock where
name = 'Product1';

S1: update public.test_optimistic_lock set rest_count = rest_count -
1, update_user = 'A', update_time = current_timestamp where name =
'Product1' and ctid = '(0,1)';
S2: update public.test_optimistic_lock set rest_count = rest_count -
1, update_user = 'A', update_time = current_timestamp where name =
'Product1' and ctid = '(0,1)'; -- waits for S1

S1: commit:
S2: Gets UPDATE 1 when it should get UPDATE 0!!

I agree that this is a bug and we should fix it. The behaviour should
match what you'd get if you ran it with "SET enable_tidscan = 0;".
When that's done, the Seq Scan will have the ctid related expressions
within the qual and it will correctly filter out the non-matching
tuple.

Attached is an attempt from me at fixing this issue for TID Scan as well as TID Range Scan which appears to have the same issue.

I think this is generally pretty good. Here's a quick review:

1. This part is quite annoying:

+ if (node->tss_TidList == NULL)
+ TidListEval(node);

Of course, it's required since ExecReScanTidScan() wiped out that list.

Maybe we can add a boolean variable named tts_inScan to TidScanState
after tss_isCurrentOf (so as it consumes the existing padding bytes
and does not enlarge that struct), and have ExecReScanTidScan() set
that to false rather than wipe out the tss_TidList. Then just reuse
the existing list in TidRecheck(). That should save on the extra
overhead of having to rebuild the list each time there's an EPQ
recheck.

2. For TidRangeRecheck, I don't see why this part is needed:

+ if (!TidRangeEval(node))
+ return false;

The TID range is preserved already and shouldn't need to be recalculated.

3. In TidRecheck(), can you make "match" an "ItemPointer" and do:
match = (ItemPointer) bsearch(...);

4. Can you put this comment above the "if"?

+ if (node->tss_isCurrentOf)
+ /* WHERE CURRENT OF always intends to resolve to the latest tuple */
+ return true;

What you've got there doesn't meet the style we use. Technically there
should be braces because there are multiple lines (per our style (not
C)), but it's a bit needless to do that as the comment makes the same
amount of sense if it goes before the "if".

5. Can you make TidRangeRecheck() look like this?

static bool
TidRangeRecheck(TidRangeScanState *node, TupleTableSlot *slot)
{
/* Recheck the ctid is still within range */
if (ItemPointerCompare(&slot->tts_tid, &node->trss_mintid) < 0 ||
ItemPointerCompare(&slot->tts_tid, &node->trss_maxtid) > 0)
return false;

return true;
}

The reason being that it's closer to how heap_getnextslot_tidrange()
does it, and I'd rather the conditions were kept as similar as
possible to that function.

6. For the tests. It should be ok to make the Tid range scan test do
ctid BETWEEN '(0,1)' AND '(0,1)'. I feel this is more aligned to the
TID Range Scan version of what you're doing in the TID Scan test.

I'll need to give the tests a closer inspection later.

David

#3Sophie Alpert
pg@sophiebits.com
In reply to: David Rowley (#2)
Re: Fix missing EvalPlanQual recheck for TID scans

Thanks for taking a look.

On Sun, Sep 7, 2025 at 9:51 PM, David Rowley <dgrowleyml@gmail.com> wrote:

I agree that this is a bug and we should fix it. The behaviour should
match what you'd get if you ran it with "SET enable_tidscan = 0;".

I've confirmed that my new tests already pass on current master if `SET enable_tidscan = off;` is added to both session setups.

1. This part is quite annoying:

+ if (node->tss_TidList == NULL)
+ TidListEval(node);

Of course, it's required since ExecReScanTidScan() wiped out that list.

Maybe we can add a boolean variable named tts_inScan to TidScanState
after tss_isCurrentOf (so as it consumes the existing padding bytes
and does not enlarge that struct), and have ExecReScanTidScan() set
that to false rather than wipe out the tss_TidList. Then just reuse
the existing list in TidRecheck(). That should save on the extra
overhead of having to rebuild the list each time there's an EPQ
recheck.

2. For TidRangeRecheck, I don't see why this part is needed:

+ if (!TidRangeEval(node))
+ return false;

The TID range is preserved already and shouldn't need to be recalculated.

I am a bit unclear on the exact logic around what order Next, ReScan, and Recheck are called in, so I may have written the code too defensively. Concretely: For ExecReScanTidScan wiping out tss_TidList, I was thinking that when ExecReScanTidScan is called, there may be changed params that require the list to be recalculated. I also wasn't sure if Recheck can be called without a preceding Next and/or ReScan having been called with the same params, or if it can always rely on those having been called immediately prior. (I had reviewed IndexRecheck as I figured it seems the most likely to be a correct example here, but I wasn't able to infer from how it's written.)

If you could help clarify the guarantees here I'd appreciate it. For what it's worth, if I test removing the tss_TidList clearing in ExecReScanTidScan and recomputation in TidRecheck (of course this is not correct in general), then my `tid1 tidsucceed2 c1 c2` test now fails due to TidRecheck incorrectly returning false.

I'm actually digging in more now and if I'm reading the code correctly, EvalPlanQualStart calls ExecInitNode to create an entirely separate PlanState tree for EPQ so I'm unsure if any of the state is carried over to the Recheck calls? If I'm understandign correctly, then it seems the best we can do in this patch is to leave TidRecheck as I had it but for TidRangeRecheck I can add a node->trss_boundsInitialized flag, so that we recompute it once per EPQ instead of per tuple checked.

(I'll be happy to make the stylistic changes you mentioned.)

Appreciate your time,

Sophie

#4David Rowley
dgrowleyml@gmail.com
In reply to: Sophie Alpert (#3)
Re: Fix missing EvalPlanQual recheck for TID scans

On Mon, 8 Sept 2025 at 18:57, Sophie Alpert <pg@sophiebits.com> wrote:

I'm actually digging in more now and if I'm reading the code correctly, EvalPlanQualStart calls ExecInitNode to create an entirely separate PlanState tree for EPQ so I'm unsure if any of the state is carried over to the Recheck calls?

Oh, you're right. The EPQ executor start isn't the same as the normal
executor state, so the recalc seems to be needed.

David

#5Sophie Alpert
pg@sophiebits.com
In reply to: David Rowley (#4)
1 attachment(s)
Re: Fix missing EvalPlanQual recheck for TID scans

Updated patch attached.

On Sun, Sep 7, 2025 at 9:51 PM, David Rowley <dgrowleyml@gmail.com> wrote:

1. This part is quite annoying:

+ if (node->tss_TidList == NULL)
+ TidListEval(node);

Of course, it's required since ExecReScanTidScan() wiped out that list.

Given that EPQ uses separate PlanState, I've left this as is.

2. For TidRangeRecheck, I don't see why this part is needed:

+ if (!TidRangeEval(node))
+ return false;

The TID range is preserved already and shouldn't need to be recalculated.

I've added a new trss_boundsInitialized flag such that we calculate the range once per EPQ rescan. In order to preserve the semantics when the min or max is NULL, I'm setting trss_mintid/trss_maxtid to have invalid ItemPointers as a sentinel in the cases where TidRangeEval returns false. I added a ItemPointerIsValid assertion given that it's now more relevant to correctness but I can remove it if it feels superfluous. Let me know if there is a more idiomatic way to treat this.

3. In TidRecheck(), can you make "match" an "ItemPointer" and do:
match = (ItemPointer) bsearch(...);
4. Can you put this comment above the "if"?
5. Can you make TidRangeRecheck() look like this?
6. For the tests. It should be ok to make the Tid range scan test do
ctid BETWEEN '(0,1)' AND '(0,1)'. I feel this is more aligned to the
TID Range Scan version of what you're doing in the TID Scan test.

All done.

Do let me know if other changes would be helpful.

Sophie

Attachments:

0001-Fix-missing-EvalPlanQual-recheck-for-TID-scans.v2.patchapplication/octet-stream; name="=?UTF-8?Q?0001-Fix-missing-EvalPlanQual-recheck-for-TID-scans.v2.patch?="Download
From aefec8d280fe9960806a4d40de95135b7d033b9c Mon Sep 17 00:00:00 2001
From: Sophie Alpert <git@sophiebits.com>
Date: Sat, 6 Sep 2025 00:30:34 -0700
Subject: [PATCH] Fix missing EvalPlanQual recheck for TID scans

---
 src/backend/executor/nodeTidrangescan.c       | 33 ++++++++-
 src/backend/executor/nodeTidscan.c            | 19 +++--
 src/include/nodes/execnodes.h                 |  2 +
 .../isolation/expected/eval-plan-qual.out     | 70 +++++++++++++++++++
 src/test/isolation/specs/eval-plan-qual.spec  | 13 ++++
 5 files changed, 130 insertions(+), 7 deletions(-)

diff --git a/src/backend/executor/nodeTidrangescan.c b/src/backend/executor/nodeTidrangescan.c
index 26f7420b64b..d98e8809b71 100644
--- a/src/backend/executor/nodeTidrangescan.c
+++ b/src/backend/executor/nodeTidrangescan.c
@@ -128,7 +128,8 @@ TidExprListCreate(TidRangeScanState *tidrangestate)
  *		TidRangeEval
  *
  *		Compute and set node's block and offset range to scan by evaluating
- *		node->trss_tidexprs.  Returns false if we detect the range cannot
+ *		node->trss_tidexprs.  Returns false and sets trss_mintid/trss_maxtid
+ *		to be invalid ItemPointers if we detect that the range cannot
  *		contain any tuples.  Returns true if it's possible for the range to
  *		contain tuples.  We don't bother validating that trss_mintid is less
  *		than or equal to trss_maxtid, as the scan_set_tidrange() table AM
@@ -165,7 +166,16 @@ TidRangeEval(TidRangeScanState *node)
 
 		/* If the bound is NULL, *nothing* matches the qual. */
 		if (isNull)
+		{
+			ItemPointerSet(&node->trss_mintid, InvalidBlockNumber,
+						   InvalidOffsetNumber);
+			ItemPointerSet(&node->trss_maxtid, InvalidBlockNumber,
+						   InvalidOffsetNumber);
+
+			node->trss_boundsInitialized = true;
+
 			return false;
+		}
 
 		if (tidopexpr->exprtype == TIDEXPR_LOWER_BOUND)
 		{
@@ -207,6 +217,8 @@ TidRangeEval(TidRangeScanState *node)
 	ItemPointerCopy(&lowerBound, &node->trss_mintid);
 	ItemPointerCopy(&upperBound, &node->trss_maxtid);
 
+	node->trss_boundsInitialized = true;
+
 	return true;
 }
 
@@ -274,6 +286,23 @@ TidRangeNext(TidRangeScanState *node)
 static bool
 TidRangeRecheck(TidRangeScanState *node, TupleTableSlot *slot)
 {
+	if (!node->trss_boundsInitialized) {
+		if (!TidRangeEval(node))
+			return false;
+
+		/*
+		 * If TidRangeEval returned false, then subsequent calls of Recheck will
+		 * return false due to the bounds having InvalidOffsetNumber.
+		 */
+	}
+
+	Assert(ItemPointerIsValid(&slot->tts_tid));
+
+	/* Recheck the ctid is still within range */
+	if (ItemPointerCompare(&slot->tts_tid, &node->trss_mintid) < 0 ||
+		ItemPointerCompare(&slot->tts_tid, &node->trss_maxtid) > 0)
+		return false;
+
 	return true;
 }
 
@@ -311,6 +340,7 @@ ExecReScanTidRangeScan(TidRangeScanState *node)
 {
 	/* mark scan as not in progress, and tid range list as not computed yet */
 	node->trss_inScan = false;
+	node->trss_boundsInitialized = false;
 
 	/*
 	 * We must wait until TidRangeNext before calling table_rescan_tidrange.
@@ -370,6 +400,7 @@ ExecInitTidRangeScan(TidRangeScan *node, EState *estate, int eflags)
 	 * mark scan as not in progress, and TID range as not computed yet
 	 */
 	tidrangestate->trss_inScan = false;
+	tidrangestate->trss_boundsInitialized = false;
 
 	/*
 	 * open the scan relation
diff --git a/src/backend/executor/nodeTidscan.c b/src/backend/executor/nodeTidscan.c
index 5e56e29a15f..1bee0ef55e0 100644
--- a/src/backend/executor/nodeTidscan.c
+++ b/src/backend/executor/nodeTidscan.c
@@ -402,12 +402,19 @@ TidNext(TidScanState *node)
 static bool
 TidRecheck(TidScanState *node, TupleTableSlot *slot)
 {
-	/*
-	 * 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 ...
-	 */
-	return true;
+	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);
+
+	match = (ItemPointer) bsearch(&slot->tts_tid, node->tss_TidList,
+								  node->tss_NumTids, sizeof(ItemPointerData),
+								  itemptr_comparator);
+	return match != NULL;
 }
 
 
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index de782014b2d..ec7020512d2 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -1927,6 +1927,7 @@ typedef struct TidScanState
  *		trss_mintid			the lowest TID in the scan range
  *		trss_maxtid			the highest TID in the scan range
  *		trss_inScan			is a scan currently in progress?
+ *		trss_boundsInitialized	has the scan range been computed?
  * ----------------
  */
 typedef struct TidRangeScanState
@@ -1936,6 +1937,7 @@ typedef struct TidRangeScanState
 	ItemPointerData trss_mintid;
 	ItemPointerData trss_maxtid;
 	bool		trss_inScan;
+	bool    trss_boundsInitialized;
 } TidRangeScanState;
 
 /* ----------------
diff --git a/src/test/isolation/expected/eval-plan-qual.out b/src/test/isolation/expected/eval-plan-qual.out
index 032d4208d51..f279a680d5b 100644
--- a/src/test/isolation/expected/eval-plan-qual.out
+++ b/src/test/isolation/expected/eval-plan-qual.out
@@ -1218,6 +1218,76 @@ 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: tidrange1 tidrange2 c1 c2 read
+step tidrange1: UPDATE accounts SET balance = balance + 100 WHERE ctid BETWEEN '(0,1)' AND '(0,1)' RETURNING accountid, balance;
+accountid|balance
+---------+-------
+checking |    700
+(1 row)
+
+step tidrange2: UPDATE accounts SET balance = balance + 200 WHERE ctid BETWEEN '(0,1)' AND '(0,1)' RETURNING accountid, balance; <waiting ...>
+step c1: COMMIT;
+step tidrange2: <... 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: 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..1498e775c0f 100644
--- a/src/test/isolation/specs/eval-plan-qual.spec
+++ b/src/test/isolation/specs/eval-plan-qual.spec
@@ -99,6 +99,11 @@ step upsert1	{
 	  WHERE NOT EXISTS (SELECT 1 FROM upsert);
 }
 
+# ctid predicate
+# same filter in both sessions; only one should succeed
+step tid1 { UPDATE accounts SET balance = balance + 100 WHERE ctid = '(0,1)' RETURNING accountid, balance; }
+step tidrange1 { UPDATE accounts SET balance = balance + 100 WHERE ctid BETWEEN '(0,1)' AND '(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 +246,11 @@ 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; }
+step tidrange2 { UPDATE accounts SET balance = balance + 200 WHERE ctid BETWEEN '(0,1)' AND '(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 +402,9 @@ 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
+permutation tidrange1 tidrange2 c1 c2 read
 
 permutation simplepartupdate conditionalpartupdate c1 c2 read_part
 permutation simplepartupdate complexpartupdate c1 c2 read_part
-- 
2.39.5 (Apple Git-154)

#6Chao Li
li.evan.chao@gmail.com
In reply to: David Rowley (#4)
Re: Fix missing EvalPlanQual recheck for TID scans

Hi Sophie,

Thanks for the fix. We do have a lot of applications that use ctid to update/delete rows for performance considerations.

On Sep 8, 2025, at 17:15, David Rowley <dgrowleyml@gmail.com> wrote:

On Mon, 8 Sept 2025 at 18:57, Sophie Alpert <pg@sophiebits.com> wrote:

I'm actually digging in more now and if I'm reading the code correctly, EvalPlanQualStart calls ExecInitNode to create an entirely separate PlanState tree for EPQ so I'm unsure if any of the state is carried over to the Recheck calls?

Oh, you're right. The EPQ executor start isn't the same as the normal
executor state, so the recalc seems to be needed.

David

Following the reproduce procedure that David provided, I tested and traced the fix, basically it works for me.

However, I noticed that, when “TidRecheck()” is called, it is actually passed with “epqstate->recheckplanstate” that is always newly created, which means we repeatedly call “TidListEval(node)” and run “bsearch()” when there are multiple row involved in the update. If update qual is just “ctid = <a single ctid>”, that should fine. But if we do “update .. where ctid in (a list of ctid)”, then duplicately call “TidListEval()” might not be a good thing.

As “TidRecheck(TidScanState *node, TupleTableSlot *slot)” gets the second parameter “slot” with the updated slot, so I am thinking the other solution could be that, we just check if the updated slot is visible to current transaction. So I made a local change like this:

```
static bool
TidRecheck(TidScanState *node, TupleTableSlot *slot)
{
HeapTuple tuple;
bool visible;

if (node->tss_isCurrentOf)
/* WHERE CURRENT OF always intends to resolve to the latest tuple */
return true;

tuple = ExecCopySlotHeapTuple(slot);
visible = HeapTupleSatisfiesVisibility(tuple, GetActiveSnapshot(), slot->tts_tableOid);
return visible;
}
```
This seems also work for me. WDYT?

Best regards,
--
Chao Li (Evan)
HighGo Software Co., Ltd.
https://www.highgo.com/

#7Sophie Alpert
pg@sophiebits.com
In reply to: Chao Li (#6)
Re: Fix missing EvalPlanQual recheck for TID scans

Hi Chao,

Thanks for taking a look.

On Tue, Sep 9, 2025 at 12:52 AM, Chao Li <li.evan.chao@gmail.com> wrote:

However, I noticed that, when “TidRecheck()” is called, it is actually passed with “epqstate->recheckplanstate” that is always newly created, which means we repeatedly call “TidListEval(node)” and run “bsearch()” when there are multiple row involved in the update. If update qual is just “ctid = <a single ctid>”, that should fine. But if we do “update .. where ctid in (a list of ctid)”, then duplicately call “TidListEval()” might not be a good thing.

Based on my current understanding, the EPQ PlanState is shared across all EPQ
checks for a given plan and that ReScan is called at similar times as it is for
the initial access path with, ExecScanFetch delegating to the appropriate *Next
or *Recheck method as each row is processed. Therefore, my patch does not
recompute the TidList for every row.

As “TidRecheck(TidScanState *node, TupleTableSlot *slot)” gets the second parameter “slot” with the updated slot, so I am thinking the other solution could be that, we just check if the updated slot is visible to current transaction. So I made a local change like this:

...
tuple = ExecCopySlotHeapTuple(slot);
visible = HeapTupleSatisfiesVisibility(tuple, GetActiveSnapshot(), slot->tts_tableOid);

This is semantically different from the patch I've proposed. My test
`permutation tid1 tidsucceed2 c1 c2 read` fails against your code, despite
passing with the `SET enable_tidscan = OFF;` flag that I understand we want to
match the behavior of. (In addition, I understand HeapTupleSatisfiesVisibility
is specific to the heap access method and can't be used here, though perhaps
tuple_fetch_row_version could be used instead.)

Sophie

#8Chao Li
li.evan.chao@gmail.com
In reply to: Sophie Alpert (#7)
Re: Fix missing EvalPlanQual recheck for TID scans

On Sep 10, 2025, at 02:20, Sophie Alpert <pg@sophiebits.com> wrote:

Hi Chao,

Thanks for taking a look.

On Tue, Sep 9, 2025 at 12:52 AM, Chao Li <li.evan.chao@gmail.com> wrote:

However, I noticed that, when “TidRecheck()” is called, it is actually passed with “epqstate->recheckplanstate” that is always newly created, which means we repeatedly call “TidListEval(node)” and run “bsearch()” when there are multiple row involved in the update. If update qual is just “ctid = <a single ctid>”, that should fine. But if we do “update .. where ctid in (a list of ctid)”, then duplicately call “TidListEval()” might not be a good thing.

Based on my current understanding, the EPQ PlanState is shared across all EPQ
checks for a given plan and that ReScan is called at similar times as it is for
the initial access path with, ExecScanFetch delegating to the appropriate *Next
or *Recheck method as each row is processed. Therefore, my patch does not
recompute the TidList for every row.

No, that’s not true. If you extend David’s procedure and use 3 sessions to reproduce the problem, s1 update (0,1), s2 update (0,2) and s3 update (0,1) or (0,2), and trace the backend process of s3, you will see every time when TidRecheck() is called, “node” is brand new, so it has to call TidListEval(node) every time.

As “TidRecheck(TidScanState *node, TupleTableSlot *slot)” gets the second parameter “slot” with the updated slot, so I am thinking the other solution could be that, we just check if the updated slot is visible to current transaction. So I made a local change like this:

...
tuple = ExecCopySlotHeapTuple(slot);
visible = HeapTupleSatisfiesVisibility(tuple, GetActiveSnapshot(), slot->tts_tableOid);

This is semantically different from the patch I've proposed. My test
`permutation tid1 tidsucceed2 c1 c2 read` fails against your code, despite
passing with the `SET enable_tidscan = OFF;` flag that I understand we want to
match the behavior of. (In addition, I understand HeapTupleSatisfiesVisibility
is specific to the heap access method and can't be used here, though perhaps
tuple_fetch_row_version could be used instead.)

I think TidScan only applies to HeapTable, so we can use HeapTupleSatisfiesVisibility(0 in TidRecheck().

With my proposal, my theory is that, TidNext() fetches a tuple by ctid, if other concurrent transaction update/delete the tuple, the tuple's visibility changes.

Best regards,
--
Chao Li (Evan)
HighGo Software Co., Ltd.
https://www.highgo.com/

#9Chao Li
li.evan.chao@gmail.com
In reply to: Chao Li (#8)
Re: Fix missing EvalPlanQual recheck for TID scans

On Sep 10, 2025, at 13:18, Chao Li <li.evan.chao@gmail.com> wrote:

With my proposal, my theory is that, TidNext() fetches a tuple by ctid, if other concurrent transaction update/delete the tuple, the tuple's visibility changes.

I did some more debugging on this issue today, and I withdraw my previous proposal of checking visibility.

I can confirm that, every time when TidRecheck() is called, “node” is brand new, so the current patch do duplicately calculate TidListEval().

But, why can't we make TidRecheck() to simplify return FALSE?

Looks like the only case where TidRecheck() is called is a concurrent transaction upadated the row, and in that case, ctid have must be changed.

The following case WON’T call TidRecheck():

Case 1. Concurrent delete
=====
S1:
Begin;
delete t where ctid = ‘(0,1)’

S2:
Update t set something where ctid = ‘(0,1)’; // block

S1:
Commit;

S2 will just fail to update the row because the row has been deleted by s1.

Case 2: select for update/share
======
S1:
Begin;
Select * from t where ctid = ‘(0,1)’ for share;

S2:
Update t set something where ctid = ‘(0,1)’; // block

S1:
Commit;

S2 will just successfully update the row, because s1 release the lock and the row is still there.

Case 3: join update
======
S1:
Begin;
Update t2 set something where id = 1;

S2:
Update t2 set something where id = (select id from t where ctid = ‘(0, 1)’); // block

S1: commit

S2 will successfully update t2’s row. In this process, index scan’t recheck against t2 will be called, TidRecheck() against t will not be called.
======

Unless I missed some cases, we can simply return FALSE from TidRecheck().

Best regards,
--
Chao Li (Evan)
HighGo Software Co., Ltd.
https://www.highgo.com/

#10Sophie Alpert
pg@sophiebits.com
In reply to: Chao Li (#9)
Re: Fix missing EvalPlanQual recheck for TID scans

On Tue, Sep 9, 2025 at 10:18 PM, Chao Li <li.evan.chao@gmail.com> wrote:

No, that’s not true. If you extend David’s procedure and use 3 sessions to reproduce the problem, s1 update (0,1), s2 update (0,2) and s3 update (0,1) or (0,2), and trace the backend process of s3, you will see every time when TidRecheck() is called, “node” is brand new, so it has to call TidListEval(node) every time.

After more investigation I agree you are correct here; in a single query, ReScan is called once for each subsequent tuple being rechecked. (ExecUpdate calls EvalPlanQualBegin which always sets rcplanstate->chgParam.)

On Wed, Sep 10, 2025 at 10:30 PM, Chao Li <li.evan.chao@gmail.com> wrote:

But, why can't we make TidRecheck() to simplify return FALSE?

Looks like the only case where TidRecheck() is called is a concurrent transaction upadated the row, and in that case, ctid have must be changed.

Although returning FALSE is clever, it is only correct if several other unstated preconditions for the function hold, which I am loath to rely on.

And indeed, like I mentioned in my previous message, my isolation test `permutation tid1 tidsucceed2 c1 c2 read` from eval-plan-qual.spec in my patch will fail if Recheck were to return false in this case. Though somewhat contrived, you can imagine this happening with multiple sessions driven by the same application:

setup: two rows exist with ctid=(0,1) and (0,2)
S1: BEGIN;
S2: BEGIN;
S1: UPDATE WHERE ctid=(0,1) RETURNING ctid;
-- returns (0,3), which the application uses in the next query from another session:
S2: UPDATE WHERE ctid=(0,1) OR ctid=(0,3); -- statement snapshot sees (0,1); recheck will see (0,3) and should pass
S1: COMMIT;
S2: COMMIT;

I would not defend this as good code from an application developer but the behavior is observable. So I understand it would be best to match the enable_tidscan = off behavior, which my existing strategy more verifiably does. Of course if the team disagrees with me then I will defer to everyone's better judgement.

I hope it is rare that many tuples need to be rechecked in a single query but if this is common, then I would suggest it would be better to rework the generic EPQ machinery so that EPQ nodes do not need to be not reset for every row, rather than depending on subtle implicit guarantees in the TidRecheck code.

Sophie

#11Sophie Alpert
pg@sophiebits.com
In reply to: Sophie Alpert (#10)
Re: Fix missing EvalPlanQual recheck for TID scans

On Sat, Sep 13, 2025 at 3:12 PM, Sophie Alpert <pg@sophiebits.com> wrote:

And indeed, like I mentioned in my previous message, my isolation test
`permutation tid1 tidsucceed2 c1 c2 read` from eval-plan-qual.spec in
my patch will fail if Recheck were to return false in this case. Though
somewhat contrived, you can imagine this happening with multiple
sessions driven by the same application:

Another case where returning FALSE does not give the correct behavior is when two relations are involved, only one of which is modified:

S1: BEGIN;
S2: BEGIN;
S1: UPDATE accounts SET balance = balance + 100 WHERE ctid = '(0,1)' RETURNING accountid, balance;
S2: SELECT * FROM accounts JOIN accounts_ext USING (accountid) WHERE accounts_ext.ctid = '(0,1)' FOR UPDATE OF accounts;
S1: COMMIT;
S2: COMMIT;

In my patch the S2 query correctly returns one row, whereas with your proposed change it incorrectly returns none.

accountid|balance|balance2|balance|other|newcol|newcol2
---------+-------+--------+-------+-----+------+-------
checking | 700| 1400| 600|other| 42|

Sophie

#12Chao Li
li.evan.chao@gmail.com
In reply to: Sophie Alpert (#10)
1 attachment(s)
Re: Fix missing EvalPlanQual recheck for TID scans

On Sep 14, 2025, at 06:12, Sophie Alpert <pg@sophiebits.com> wrote:

And indeed, like I mentioned in my previous message, my isolation test `permutation tid1 tidsucceed2 c1 c2 read` from eval-plan-qual.spec in my patch will fail if Recheck were to return false in this case. Though somewhat contrived, you can imagine this happening with multiple sessions driven by the same application:

setup: two rows exist with ctid=(0,1) and (0,2)
S1: BEGIN;
S2: BEGIN;
S1: UPDATE WHERE ctid=(0,1) RETURNING ctid;
-- returns (0,3), which the application uses in the next query from another session:
S2: UPDATE WHERE ctid=(0,1) OR ctid=(0,3); -- statement snapshot sees (0,1); recheck will see (0,3) and should pass
S1: COMMIT;
S2: COMMIT;

I would not defend this as good code from an application developer but the behavior is observable. So I understand it would be best to match the enable_tidscan = off behavior, which my existing strategy more verifiably does. Of course if the team disagrees with me then I will defer to everyone's better judgement.

This is a wrong example and (0,3) should NOT be updated. According to the definition of “read committed”:

https://www.postgresql.org/docs/current/transaction-iso.html#XACT-READ-COMMITTED
13.2. Transaction Isolation
postgresql.org

“A query sees only data committed before the query began”.

In this example, the update is s1 (0,3) is committed after s2’s update, so s2’s update should not see (0,3).

This behavior can be easily proved with a simple example with master branch:

S1:
```
evantest=# select * from t;
id | a | b
----+---+----
1 | 5 | 20
(1 row)
evantest=# begin;
BEGIN
evantest=*# update t set b=30 where id = 1;
UPDATE 1
evantest=*# insert into t values (2, 3, 4); # this simulate (0,3) in your example
INSERT 0 1
```

S2:
```
evantest=# select * from t;
id | a | b
----+---+----
1 | 5 | 20
(1 row)
evantest=# begin;
BEGIN
evantest=*# update t set b = 30; # block here
```

S1:
```
evantest=*# commit;
COMMIT
```

S2:
```
UPDATE 1
evantest=*# select * from t;
id | a | b
----+---+----
2 | 3 | 4 <=== the newly inserted tuple by s1 is NOT updated
1 | 5 | 30 <=== only the old tuple is updated
(2 rows)
```

This example also proves that your solution of TidListEval() is wrong, it may lead to unexpected update: (0,3) in your example.

It also proves the my proposal of checking visibility should work, because (0,3) is invisible to s2. And my proposal also works for your second example of doing “select for update” in s2, in that case, (0,1). After s1 committed, (0,1) is dead, so select of s2 should return nothing. The behavior can also be easily proved with a non-ctid example:

S1:
```
evantest=# begin;
BEGIN
evantest=*# update t set id=2 where id = 1;
UPDATE 1
```

S2:
```
evantest=# select * from t;
id | a | b
----+---+----
1 | 5 | 30
(1 row)

evantest=# select * from t where id = 1 for update; <=== block here
```

S1:
```
evantest=*# commit;
COMMIT
```

S2:
```
id | a | b
----+---+---
(0 rows) <=== s2 returned nothing, because id=1 is no long valid
```

And this example also proves my solution of checking visibility works.

And from this two examples, always returning FALSE seems to also work. But I am still not 100% sure if there are other use case that returning FALSE may not work. So, feels like checking visibility is a safe solution.

Best regards,
--
Chao Li (Evan)
HighGo Software Co., Ltd.
https://www.highgo.com/

Attachments:

elephant.pngimage/png; name=elephant.png; x-unix-mode=0666Download
�PNG


IHDR-r��tbKGD�������tIME�NS� IDATx���wxT�����Q�*HBB$z0`�1`p���&N�8q������I�������5��������t������z������8�1H �}F3��y�� �^{�3���*:$�D2�	B ������p<��h:��0m@;�4���(���f�Bgk$�D�/�@��G,D���_]m��`hJ���%�i ���k��B
�D"�-�@����s_�1>
1\i�� ����%�"q���H$��A�S���)@�-��sZ�t����Q ���SuH�!�H$���GSQ��$���N9(���9�r,c��S��#�D"���Lf�u�"���[�(�}�`p)@�)8$I���#�0 ��#��W�u��J��3W��oA	�7���
t�����s?�8��Z�������]��-�7�
������k1\hv;QH:JU���H��P>|QB��s�A)�s?��������n�;��s�;�?������%����?���w�k�������|S�TgQ
��=�5���X�"2&N������zb+�:�����	BI2�R�r�k��G���CywU�"<��x~�������!�Kru��:���#��Y�6���EH��?��{���=���`)0%r#qZ�����&��-"�2Rp�J}}20��E�WX7�A�("��B��r�����#%�?%�`J4C�5�(�#�s��n���8>=(�w�u(�x+!����RwqY�D���H��b��r��G�4�F�q�!%�-��hD��%���|�">�"�h�� Y�x�p��s�I����P�R���r�y���$�$X���{&�
$m(�>�(��/��2%�l!�%�_�
M|�������3xGf�m����D"�f�R��P�2�T)8�������r��l[wF=@���8Z%�(�~����D2�4��WQ��%�D
���GI����\fo4��C|-B�m��:\�e�����%
qqq��KI��������^���������<��;`�W`2�c�H�1pR���� �J��(�.`������8�{(���"�gt:!!!���Fhh(!!!���������/~~~������{����bidF����v�F#���������@MM
������R[[Kee���566j���;����"�\)8��/J$�(��� ���+��][��<�=��K	z����h=z4������\x������MMMRXXHQQ��������;�+���������"/l}3x����(�������2�a��T�P�L��hO��Hbb"���c���$$$\����fk��Nww7dee�����S�HOO����e��Vt�F!�����k|��Q��$�"�(5�[�/Q�P�&x�	r��������dRRR��5<<����%---�:u�S�Nq��I�=Jzz�p�������+t)8�
�'P����}��gP���(�0"e�a�����]��+z����$f����3�9s&'N6G ���h���C8p��{�r��aZ[[m���hB/����HcQ.��"�qI���g0l��AwW�x
�)�U���www|}}1W<hii�d2���Joo/F�����!��:�5���g3k�,f����i�����/��d2q��I�����-[��k����v�/��?��x���A��#�?����}�_�P�]��L��+
�%G��(C��
���DGGGLLQQQ���Lpp0!!!��s�I�W������&���hll������:***���������J***(--��������P,X���Y�p!c����K�����;w�q�F6m�DAA��]��\�1�r��HA�/Q*�m&�������������~������N���'������?�	J��b�d2���r��


�����sCC���TUU
��.-9?j
���:���1�����'%%�������Lbb"���DDD����7�L���S\\|��!//���\rss���N#Hooo/^���Y�h���G�I���Inn.�6mb��
�����dk���	�_����#��<��*��9�����H\\������3z�h�����Xww7������QRRr����g)++��������
!!!���2k�,�M���	��t��2&����"������&++�S�N������f��1�X��+V0�|���RYY�G}�|@ZZ���h����a���������2
���L�8������QT�R[[K^^yyy�>}���|���(((��]�H'&&����`�f��M\\��]�	���dffr��1N�8q�j���d����p������do%C�������X�z5yyy6wx�{�C���#��~��������Y��5k���$''���lk�l��d����������KVV���dff��Y�p�`0�d�n���,YB||��]�[���HKKc���9r����~�i���m��d�9v�o��6�����[��*l��5��c���������)c��a��E�}CC�U��M���%77��'Or��)N�8AFF����������b�
n���.]�� �m%5�F�}�]^}�U233m�F�+����
�t(�1�0�V8;;3w�\n��&V�\)�0�@EEiii>|�C�q��1{���777�.]������e�do�Dcv����������m�h,
�.�i<h3Ap�Q����
��;;;�d����N�/_N@@�P�0�1�L���p��a>�����v���I�&��p�]w��3�d(//���_���^��~��Nw�@�����.8Fo��z���gs�]w��o��9������c��}����={����nO�p�����[n��Gy�y�����dD�����/��/�@]���H�|(���f8�����w >>>�s�=��'?!99y��������}���g��m�������}<����C=���>JDD����CZ��0�wa�������S����;��X��������
�=���t8;��ps���wW�]��6�������
?o����h4��������S[[;�[7�T��?��j�p��p�Ci=$�?��{�����B�,��������������}�v���m��y���x��Ge���2�{MT5�RU�Ju���&#
��4�tP��Fck�-m��}��^����o|z��� ���Q�>D����a��]�@[[����=�555C�����C~���MpDs�b���T~��_�r�J���(����O�e�6n����;�����_��O>��?,E���������T7r�����f*�[�lh������	���Nd���|� >"���AD�2�$������k��/J�Q��2�zX1��{������,�E����O�`�ko%�3�����c_~�%7n���������x��'y��'�����l�����e�T�s�����zjG�PQ���A�G2.:�����
"�h4��+�������4$��{QB��0J(��,>���6������{���Zkn#F����n�:��[�im���+>� O?��Cv��\N���c���T�}����������tg��p&���1���	�����n�KUU�����[o�5Tyb�QzO��c�@��G(MP���399�?��O�X��Z[H���<��[���k9v��j;��z+�=���m5>�i2v�f�)��J������;\��7:�Y�������!v��z��	z�!:4���PZ��5��?�M�e��U�����g���{��9�AQ\\|A|:th@w3			���K�p�
C����-���4���h����Is['�=&�zz1vt��c����Ai����z<�]��ux���mp������^���yy�P�Z�zz��@�o?Ai����o�L������&E���nk�.`�X�����/~Ai��+Z�;�������v^E�nh���+?���x����tw����zL&Z����������5�i�Rf���w�����P�_�8;���t�twu��E	Yzy��kp��7�=RQQ�'�|�{����#G.����;����x��'�~�hs['���8[�HE}u-���P��JSk�!j������A��'A�����""���@"�|	�������`�X�����2���aYx`7��:&��sMrK�'�kk�%���g���^����Q-���57���n�{���a|������+�jd{W��L���6Z;hlm������v���;�3�L��;������t� D��<�&���P/��qs��rssY�z5���>���������o���[K{�EU���4��������Dx�71a������`��pfK����#�����2��)�a,����i	����2??���������[��v8�����X��a^|�E���~�MkFw����Z���8S^OAE=�U
��?/E��y���@_F���OD�/�N���@
����
����������#ye�)���
��p����8�DbT0I��j����Q���kb��,����C���z��Y���a�XN���������_���z���kn����+`OoA�����[o1z�h�MQ�����r����*�&��������{�8���
�!��3*���A����b�����r�V��d�sK�=[3dG"����;�������cBq��j���>�q�w���M�7g�����Maj��:��������m���r�X	4Xs��`/��|��3Q���������?nw����/�Hn)G��(�����8�����HbT0	�A$F�E(t8a6[8v���'
��^0b{:\
7���b��(f$F26*�.�A�����kve\���d�$Dq����83����l�Xx���x�������
\��,����;�Elh������O>a��Z�4�U���(dOF����#�S-a��������P�F�����8S^����l:�K���s�c��C���l�t%�Z����|q0�!��l�����f'��k'�7��gggs�=�p��	kmqX������p���}4c��%�^���� -�����lN�c��|J�eCK��z�#I�#%6�)	�
��}vE{g7����,rJ�t��C������,����c����K�(���v�_6�K�R�Fs����L�����������/�l�-������` �Zp��2�F3~��_��3���4�����lJ�esZ�g��(	��f���$�bJ|1a�=������v���`m���L�(��:�%D�xZ����o��d6���^������*L���d�����[�f
<���J[�������-�S���2����?������ker@�<S����<Q@��'||LM�`��(f%E�M=�(�����3�eX�8;����M���?)��-�k��x��=l;f�
&�-)�a�p�,�$��(**�[��������v�Kk��7��h����k��a���Z��*��&�<��;�)��z���`_f��"u|4��F�Ff���y}�!���E���)�������	L�	��/�sJ���d���c�^����C�_GG<��W����n���5�0~%l!8�i�&��aaa|���L�:UsW�����{2Y��	Y#?L��u$E�0/%�9�1$E��m���:^�t?�����H�
���),��h�d��^o|��[[���t+�xZ��6��������s��?��?�L�G�M(#��Tt����"6&ha,,,��;w2n�8-��KWO/kve���Gin��>*A}\s�:aVR�M��������d����7c8bpweEjw/�l�c���J~��m�[�qsq���S���CR1�e������5��":>��p�����������c������<^^���V��#�=��N�L�b��x������-�������d��D�+z��ES���
�H���;�zxq�>��=%s}�HX�7��r
�Ok�(iVV��-���Dk�=(�c����b(�#h4Tf(�FQU�`G������~q�����uS�Y8%������
<��v2�����dh����K�2gB����:�3�l���Vfr�(~q�"�������+Vp��1�Mw�������K���4� �g���$&&�{������1����p�6����mp���oa���TMf3�l=��6�UNL|D �,�����t�\K['Z�SV�Xg'=�[:��8��-�������;��K��L����CZ���~�q V���#�EU���mW5Z��dx�����?���V�B(�j����"��� ������T�L�~�b�8���?�Ig�l�nM�F�����f�=zzz����y����6��Nim�<CQH�>0G����/;v�`�M�M�A�����<������Vyv.Q_zt�q��p|~ ����%��27h$����W����TA>DMribT0sSb9�[*��Hck_�������QV�f999q��7S__��#G�4����b=`��nk���#j����/�����T
\�&�u�<��gl9��EfXIwWg���J&����vw������o<B����}��������s9y���������g�����IW7�(��X����3�29~�U���t:�-[��db�M�z����c��)8���QT�jt:o��6�V������w��G_���:����C\�������������F~��'�
�$�(�ka��,��I��zY���K�������ye�&���5����l�
nVk�h�"<<<��}��fC����(�:4�Z�C��I4I���~�;y�q�.�l���
����t��D=��N����\75^s�;N���?���]s���OAE=��������1���������1�LK��@�Y:�z���H�d6�?���eu�?�*};������/[�n��l,|��Qk	�G��D��|�����+�4|��w����_�~�f6%��#7���k'jj�b�l8�_>�EO�<B��O�����v�,$!2���,�}�qf"'�TP�$Kg�IqU#���f��Q�yjn����Q��ivfc
�����b�			l��ww��/�������s��iK���9���ms5���k��oo��]���86
��|q0���V&�	���z��
��,�5����U6Xm	��w�����
$����>55��c!�}�!�5�?P�n��`0�m�6���;G?[���]'�T��H�
��.�4������_���E����,�Jk�l6>�n�����g'=��&���KzA�u6�`2[�{����vR��5�bIMM������5�����jQcZ�����F�x�
���z
�Q�.�������$��c���o�t�lms?~a���!�����E�T0=1/7�������hB��8�uV���29gk8�W���X<4�������+;v������rE(	MK���R�,b���n���6Y��<��Oim���G2�qqv�o��b��@�lV������Q�M)�k�����{�i����C����B����T7�r4�YI��4�=o�<�F#���?�����j5���x�O�@XX7n�`���Ly=?��Z�����8�s�BL�����&~����A���kb��
*���i����`_�O�e�YZ;���5i��fSZI�!�7�[�d	eee�8qB+��(m.T��j%8<QF�
u�y����:u�&�4y���d�PI��:/��������f|a5MF�lJ$}QT����y���g�=��
\75��Y�4egRk��kb��|��<5�����X�|9'O�$//O+�����Y5��?G�6���~��<��S�8c���'/����Y{�blT0�=�\����&#�u=�����dhh��a��<�����i��a��,�6���R�[d�kb�X�s.�|��H����zV�Z�W_}Ey�&��:�\��L�Z��������g���)^���k�g�~Af�pB��quq��GW��M-�yq+[EKlANI
�3�������-�=�\�~�XN����QF�����r��:�3!F![$d IDAT��$V�Z���~JC�&U�~@J�������(	%����~Gp�P��^�t?G��4�%q<�y�fI�=�&�|}g��5�'�����������VA�mp���nffR�U�K��G;���[[1���
f��M��iv�#�q��B4���o]u�������k��� ���h>/��'lG���H���;iv���w�b��Bm�I$����~���.f��B���i���K���Ly=g�e4���.�����ES�5�����3Y�z5f�p�c�(��t#���iT����t:��]�I����z�xu���)��/��f�����$oo9��-�D+NUq$���Fk>�I�g��xJ��(��Q=kSX���������1�?J3���.(�@T_����n{�1��z������^�~y������?�W�����Ib�T7�t8�����
����^�c��1W5R(�6[����V7�p��D��Y�())����Z�����"����j;;;�v�Z\P����9�S"lG��,����W�jb����G��^N���5��lL�����x�G��t:M������*):�MAE=�-��M���8��od��mZT��U����X���>@i��x�������b^\�W���1�tw��GVj^���������V�[K���ec��fVR��S�u:&��_Z'��9%5��L��M����K�.������S���$�e���i�
��[T�����O>��p_K['���m��nS�7��r
�I�9B�������j��D2t�*�"����c5������hj<Y���InuN�����I��aBCC�����M����P�o�3J���R�Gy�o��j�_��w��QX%lG��$D����C�������yw�q
��H������.a��XM�I��zM��dA������9�WJT�	����<y2iii�9sF�T2J.��6������S]����t=�}�-G���H�~q�M��V6��u��Z2��)����~�y�wWg^|�&&��kjWr9<��vM{M���Z4�������\��P��?�0��bIL��&��p��
�c�<5I��cO�����Bw���)��4��skH���h�����]E���@$}�u��Q�F���ka��%��S������?W���m;.�$��mp�������?7&��V[�=������|��tm��yy(�#*�:�$_c�����?�l���O>�����U����+�`�����}�{��G��yUC+onP�d�������+q�Loo���$�Gw�����F6�i6Eo���JM��+S�h��|IO�x�5((H�(��U#8��;�z���x����.�������{��T%#��on��"l�������M�y�=a2�����v�)M�F����n���YS����(�������O<����P���y�Fp���]T��-c���j��_Z��c2QT�??�)W
J���x�u��O���-��`'�h�K�
��,�|���r�����]��vBCCy��E��f������-r7^���l'-������'l�x~9_���#����X���?7�����q��4�)���~���g*����g?�b����~0P�iKNNf��j��U\��SEB6$��OV����5���������8�����	�um
��a��6%���k��oo�%�Y
,������q����]z��d�%�H�
c��1�v>�qRN���X^�t?��d��^5��)1���\NYm3�~vP��]w�%jb�g}�`�*\]]������"U
��8Q dC��<�r��`��&#��8�,�7^X��u{35����������9�d�|�3���j!��~;�������+������S�����		k���tL�+vL��`�'F23I|��_���]N���p,���l8���M/W^x�&�<�k�.����?��i���a��e��,���7#0��?������w�VC�-q<~|�����9%l;vZo$����������]s��?���e�����Y,�s����n���9���8%,,�n�A�r6�����-dC���L�nan2�y�#�*_"����/��Lf�v2�$���������r,�t8W����}(C���7��������@���[pvk���Y�(�����g��?���F
��H���^�x�Jk�%q��SY2-A3{����&��j��q�%<���(���u����n��6�K�/�#��F���qI�
&u|�����^��2M#�$��������9����|�����3W�Eim�pdJ�(��K�q5���<$00�k��V�r>?�%�^���w�xt����45�F"q\Jk�x��/4+apw��n��E�+��oDs����#��e3&�&8T���\�R�8��������8��,�/d��������#����,���ol�l����`~�m��RI��-Z?q�DQ&p�����HD����[oU�k
��SE4�u
��8.�,���`�����c� ��Q����kf��y�\?}�f�$_s���&��c���!��@�����[u]��``��>�~������8.~^��#6����w�<�HF�l=��#�
���=�*��i��b�X~������DG���q���U����qsS�kJw�������K�[�%���"dc��S��wi��D2�������(�����~p.Ly�|��yeB�5�r|c�f��	�rX��!�sJh��7$}����e^����^���"$��Dgw/���4�\���;�\��J��d�k-y��3_�;�
��rn��fOMx�����G��i��)�5�F�|}=�&M�}���L��-�Bae�P�oRR����Z�n5���N�������m�X��bA���H%��R�.�z��g�w=��R��t��
5mKLLu�������C'0�3��RVH�$���k�UN������<�H$��f�)M����<q��Y��>������nU��f��~�u}�l0i������k&������F�H$��������en2�'
�I�QY��zmHH��B~C��[y_W�$@�!����
 ��o��zn�f�����&����/�Dk��zx�_5�D����cP_�(��N�:����Q.$��%8f�����%��j���t2��q�3a4!�^B6>���E�&�����������s�z���s5�5�M��������L��'}	��I��O��I}-���e����87�K^��5������H$}�~_G��g�5��(�a7��nT���cg5�p��)VG}([��%�cpwe������
�8Q ��W"��gW���F|��N�{�"�\����@]s��z
���r��0��Df�R�U%�!�\��Iq���]t��9��7��J�w����l�$Z���V�}��tD�hz{��=�
�#	P}e�p�w��rEI�,�)v�R\���3�g
H$���YT����hb��%SH�
��%}"*8|||D]�`�R��z"V@@��YOVq����\�������l|~ K&�J$C���>+>o�I����"��iD��k��G}7X����M��9[-�^��\75^����ba���z$�HB���o�����R���0��
������L� �#�T�,��\�
3��SN�����H$�(�j����kb��[��[��PE���� ���"����R�=�$8�i�mZ.K$u|�+�c���>\���G#��l^^b���Gpx������&#��m��K��)��n{zMl?~FC�$�`�X����#8��R3*P�$C���\�D��vUD���z�k%���<���gi��%�SR��?�<,l�I���w\��G�!�p���#F�5???�� E�Vr	n.��� 6vsZ�F�H$Q��z���Za;3#��"��
��xtI��O.���������RR�Gu���eOF��I$Lf3�{�+Lf���Go�Fxr�H�K ������/ ��E�5��(VI #�K=N9�}V����DrKjx�Ia;q���F�FW20��_4@4�p���9Q\%��kt:�'8;eOF�F�H$-y���T5���?xS*7���%�G��:8������.��%�GBd0���������C"�G��zxq�>a;�>�Y2U��YT����1�Dp��>�O�+q,R[�gV��*'�J$���c�9�'�����S��t��#������/������/�
��\4�m������k%���qb�cw�L�H��?��^�X���+��(�U�twU��h4�n����P]����,T[Y/#��quvbjB��
��!��?EU
|�C<�������`G"���h�����#D��������U���"&�	*�-�n�lu��I$k��/�hhi�aps����i��c"rM��o\0p^p�X!r�2�!�&3��' �-���Dbm�:������^0�@��7
7����E8(pan�y���RXX��'r���bf
�o�)���D2���E�`k7g�_:C#�'�^�IZW�p��3�#��P�Z�&��&�(��:3.Zu�2f���yRpH$�	���K���u^2!~��M_O7��

�}�.�p��(6��Y���#96LH�gWa�>o�H$C���B����puq�}9�@�lX�q����������Z���RpH&�Q�J��\��~�Db^\��E��-s'��%+V.�WPp��
��Np��4�u`�
�8���/�8�#F%��Jvq5���lx��p��Iy��
0
"u����HE�H������>�������*
=�H$C�?�8$|z���r��E�F84�����H�I�H�����nxY�����4�H"�5g���~���
Own����G�{��Rk)(H�R��d��D!9V�����
�<�H$���MG�s9��p�P�#�gg9����)>>>��h�
#q�F��� ��R#O$�-9S^��L��a�,�2F#��7A�����F-f�\P,��j���/����Z�@��V/8��
���H��6�q���x2�	�W����L����Kf��Qnn���t�J�!Q��R�|\\�@K�p7<�Db'�Tr��X_��	$F�o$�(�
��r���w�B___!O��� ~T��4���8E"q8��"�����x2�	���A����?��!
��@g��pH��S2e9�D�p�:Ka�X���i	x�>��3�7�a
�7�����0�H�@w�,c��'����\�E�dXa��'�3�l��:�tF�F
?�F**���.;RQ-�D*T�������C-]=�T��K$;d��Z��n����7���Q�$��
B9:�N��.Y�"�����eu��f
��H$�B{W��g	�H�b�`u� 8{������y$@�I~P�t���:�������Y�;C�����Iy3��+�(,,u���X�B" .\}k|���RpH$�LE]i9�B6O;";�����jZ[[���+������? �+D�7rK���J$;g��L�������7��(�q��-\��HE5�e�I�@���l�X�lN"��?{O��*6{���c5�f� ���8�	�F_t!�!Z+�����6�-'�J$OO��
s�l�M�A�9>����N����%�) �T$6&&�_��3��z"�H���i�B�}<����7��h�hAA�����Cb3�}=�P��]%��!��N�&cnr�6�F��	���H�����5�`������E��/���C"�Gt:������z��������wv�k6�����l��������7��x8��n�F�_sSbyy����q1rs�"J�e�EHp���x
�_�F�����k���D2X�����@L�?��~�z��M��g'�z��Ls['�����4�u��,f3>"��o���=������j���D]������f����i������MD���(�k���Dr%��=H�
g��p��C��#,���{:;�	�1�c���5�1��sJS����GN�X��9.��pT�����y���~��d�#�����M�`���psq&*��/�
�y�c���	OwW��:\]���1���Kw�	cG��F*�[�jh�����N9kHb��z�$�bnr���&����H�
sx�apw%�_� ��k'�%�~�P}����)���NB�%��QA�GE��C�>����bt�?�a��)a���P�d������*����*����M��D���Y1;����'����� t
�@p��,p�����Kl��#����!>Nq���JJ\bBIBT�X����"����IQ�WR���|u�4����D\���qf"w/�"�.D�������=|D�5y}}��K:�
�Q�R��He����D�����C!8�F�:>�ic#�������&:����0���0������`��L����d���8q��d�]2�����^�#:�������Z������3�:La2�)D�N&��TF�;��j_������q��O�cnJ��_�G���������������'��G.���������<�l&!��E�p&:���GRt���UUU����d��Mg@(���__ug�"c�%��Q�*��D8t:�<f7������x�v������d*�^0��{2���#v�P+�-��F����vD�\��@���A��� ����S+�~#B�&"���He�)�0
�=8b��Y6kKg&
���\������4;��>���}Y�-[�%�<�]y��kY1;����}5 sF����48N1}��:��������� uj��[��j��A�C�\���twe���,K'r�w�
n���E��3�����C��%W'%6����"E�#��+�%��I-vm���u��3����(U	"g=��0|-����&c]=�~}T�w,���9IB����a���;x���l=�okw$6���c�������K�i+x�g�����8qB��~�d���
S���/���c�����zms����f$Fr�u����^���wWg����$D��g���{K����9���q4*�w,��������)��h������R�J����~����;.�N�8p=��oD��7��v����lV"w-�BB�Xi������K��������,E����g�����v�n1v����Wt:1����%������G���ree��e����V��i���4/?��u�8s?\>S�e�#s���Rt88�[:]�������GL�!�Bb�?���9/8j�Z.)��]������c������R�V��u�	�N�uS�y��Tb���p���~�X�zL<��6����q���<r�[�a���

J�[&���m� ��>������z�Z����j�J�C2���t��hl�@��y)q�dU�<:$7�N��������+
Y<-���>�f���wQ�d������6�[�ii��������zzii�<\�cp�I����7g�]���t���_/w|=�	��&����^6��)q�B��;&��	�0���P��p�{7G����C�z���/�`|L�F�<��n2M���t���H4`��@~s��!K5vt�QXIfQ�EU���X���^�#����@on�>�;N��~���tf����~�/��d��a
��#��Q��,���'COw����Jz��]��mSF����dVr4Ou�Sb��8���n�z3�����*boF���C�d6[�i2R�dn���\�� ���/<
8y�
��������S793*��7%������X{���MNI
E�
��n������6j��hhi�����!:�R&��Ix�c#�H�
#%6�����:���%������;f��H���g`�
�lN����v�@�S���#V�L�	�y9t��n(�!t.������3U���Ju�!��,(���h~�
��>[CIM��DL�E�Kil� �������B����)�,�2�`_O��J��/�^�S����m����}�O��nim��t�Miyv���SpW{�P�m�D4C��A?-��s^pT��yP�>}Z�������B{���H�f��1�knc��b�rK9�_FC����b6[8�W���2L'1� IDAT��h7sSb����L���>��%0�@6��jjWb}~�2U�D���^���0�8i�B�<����n�<�D�7@����#����0��h5���\Q�\�"C��/U]�+f��O{�3���8q�}���)��Y)��baOF!{2
Y4e������k�����s8�}V��#�c�X0i�f�rJj����p��Q3���Sp������t����F-f�\U�\�(A��8s�����/�B�����4������9vun}�'
8�]��n���s'hb31*����e�9se���M�4�J�`�I��v�&uC��]�	��"�����.NN��Z�;�i4R��vu#�@�����d��5�������a2	��Jp���"�*GG��k`��f��6��X~���i�����}E~Y-?�}>�N�a�����W��������G1{����o`6[x��=|�+}�k��z&��23)�	1��G~�j���N��.g���:~fP��B$����S���Z�Q���G��]��9��bA�RnG���#	��p?]�'�O�;�P�"h>��AqU#/<t�p���`_n�=�O�	�V%V���S4������x��z/$F����\?}���/�x��p�N�������d�^��g�~�F6X�_�-��`s�Q���"_�N��������R���U��-�G�����5��h>�H'�D��c{!-�����&���r�H����`���9;a���+l���bB���Y\���N����{^n��U]g���uM���v 8�E�\�����T�h��cD�a�#�����9����[���?�}=��'��������^�-ts5MFU�/{O��
���v�x�h���a���3^�2�Ly=�~����qwu����q���t0��t����c�	�Nz=���[U��G�C�(�?}�4���9�R,�3�P��u��i�,Y�f)����zj�X$�O<\�Vp��5���G���G����]�����q�E��[;8]^GzA%i9%�*�P^�[[�2g�h&����3A
;����B��f��������n.�������KW�����P�AG}
B
�j,�1-!Rh�����pc����J����P?)8$�R����7���6I��u^2�<�Av���`��(f�����g��������x8����~����~s�u������"�CE]�j�0:��1��>�y���W������V=�&��?)<D �*4GB4at��!��@�@^xi\N�m������u�������wX�7s��F����o1��{���F_�z���kSx��o��_~����}meC+�}>���~��t��=^���:�J�Z��k���G�������d�*Z��
G�pLM�D8������xi�#���pX,���,n���|�#}��O�����r�u>���Cx��<������X�7�����9^��Y���K��hr��c��Z��cpt�>�}J��� �})�#2�W�`QQ���w`���R��:q��������>���8F^�s�"���<�����MF�+{������������d��mW��tUF�,�����1���W�1li��ty��>W���g8~�\���`��[��b������P�<�����Cui��l��i��.v.)>��8if�����|��{������Q����-}�������t��2S0|/�o�j������
��ooQW�:j�<���0��nhiw�9*��C���o�/�,�����zmx���B��B�aSY������xW:f��t-�l��"��<oo��f�1�7 ~1�hKl�������>�����S�B��Egw/�����	D	D�K(������h�
������/���2���>w>yR�Rt:�z�d��#���l��������5��
�����!���$���g	���)T~(��(pZn��^����LfQ���c�����?����$�e���I�Z{c���~��BYY����nJ�\*8�$����_H�12����m=/�?`�3?6������f�,�*5�1�1~t���m�p�\�D[g7�m=���?�(�m�G���A�p)�A�B"�l������<w��r��"$8@@pdd�'�GH�1���o�����Ps�L9Y��C�_UC�Y�����~��D[D:2W7���?�����_����T��m�XX�;�;���2�DT��Q{���%u������[E]0{��/�������\�EjbT�����C�@�p���X�����d������#�+y��I�!�*Y������������w�������k���9|������t����f,�q������q���[,���+Q7N��Y��xIu����������S�6.<�^gW	����FI�5�+�������;Xu���>?���h4():Dh�D;D��4�w�lm��__����G�>.���1�G]��a������c�e��,�d�K��U� �c���A����TV
W�
Z��%8�g~��q�n.D�q�zP�I2�0v�����i��b������d6��;����kn���I����0�\���+���aps���~QC�v�
�i9�����f�@��z*�MMR5����o���A�K"�A���
�8*�����3>����fe�C�����b���0�-��?[T��[:��X���� ��6�C@l�XT���Q���(�
��)1B��m�&�B�L���	�T��h����9>">�*��?��n�����)��^�yk��'��\eP��-�8l�hd��S�
[���L���<������%�vuu���;<�2���Lz��BIB��z�^�(����]�������(�v��)�((X��{o�	�&��RHOf�?�HI��L�����KI����I�9�)��Bc
�{T4�H�k�.����p'4�77WG����c|��^|6{O~<��{,�F��|xksk0z�/�x#7@���ao<���R�G &"�@�U2������]���"q��P��R=����������cuk]Rq}
�?oYz�^,�� ;���:s�5�xy\������3y�V����������=��q�*G]D��{R�y���8�7�
8"C�	��&���"8�c#�p8S�������e|>{=��'�;%��"/)fTRV����X�)��[�(28Z�WXB��|���m��o����a��4u=�RUN�.��?����T���1W�pXC	,i�h���l�W�%C�Cp8Q���)(����b�F��=I�����oOw��+I;�������<��2px����tY�Dc�">O��g�����j%�d��$6��fff�u�V�����1��)���E����8\������%e��u���H���o�8����D���������V����4J�<s��r��c��S�����*��2<S{�P�pYE>��k���������`�Q=������]"��T�]��l2�Mp��=[�+�k2W
8G
YYY;f|I����6�����W5f��qTO����"�}mA��p�y{�k��+�S��#4������R�_;���p��"�,G\T�X�F��H5$��u���B��c������/4^V	�u��C���h��Z6�|�r�����:NmpH�8�f���������n|[������wyh��	2~��]s!��u���yb?�z�@Y9e�����C���^�m�D��$6�':�q\�*d�[5�����aGC���FN�����q�`Q��)���#��~M���l(8��$�pXd9���I:�pi$���N*�eo�S&Mc�9��a��N����������OYv#55�H�XD��\m��p����*���k#��p��m��t�����!}���w���^��GE���|u�r�Aoa����"6r�;��4Eee%�6m2z���@B�����j&���g�b��;��+ ���*u��AI�t~�����D���X���?H��s�F�p�$�6n�(9NR�����E"�#Q�����WrR�Zv�7,W��0���y'��	���#��M�hi��S�X�z����@������;���
6=
���+#i���M�F9|"����A��eG�K8#�6����HAI%+��8�#��M�����3��W$(��\��Q���"
8Z9�/���	���t�a�t������>�$}������@G���M��q���7��i������r
�R������G�r��	�����#�<����������>��p���'��^�G�)��v�.k<[,�CcOz���J����,^�X��)@�q��|'�;?��q�y�op��Dm�������sc=kW	JbIM��/��[&Z����D����Ki��������c����������|Ia�A�x�Xg8��TK%96J�'��<�!S6���>tl�PdCQ9e�
#P��cU��
�~�(^���T�h�q"��rA�nC��p����O��������Y��6N��]ZZ���"%r�b`���y���X�U6o��U0��84uX,V�"�z!��E���e�6|�Qd0Q��$�M�o�,��o�Lt~������w�,�J�\	�
��ErrrHKK3z���"�(�RQ)���1�$��ILk��<d��k���<��}���e8B}�� +�L�6M�+?�0r� +�xy��L��v9J�*��t�S*�O�>�������ecOv<.:�%��"OjO���d�^�k/a.--����B%�����T7���H$���Q�ox�m�"��d����+��2��8�G]b@Y9e�����&���@����T7��@ k*mu�Q.��Q�*/���}9z��Hq4��K�S�� ?��G�lL�:U�+JF\.�&����m��QVf<��G5uH��}y�1��
������\}u��a,O)))a���R7�(������"%%%�����q���W��5%H3�:�ao�	��M�8�	6S����[����3����[��%�I�!j����&��hq*W��!���Q���G�l\o�(�����G�[R��F�����g�Q�)P��c#yS���3
�h4�Hiy�hTP�T�Ov^!i��~�~m�y��H�\jiv��������Y�N����I���7z!�N��8Y���0	j�
V-�yN�/���Q�`�.Y��o;�8��e�=~^��{�l21�Ss����gSX(+�RUN1�^%j��e�qt��=��RR��z�����6~p���#rJ���{8�u{���'5�Od����
Kd:��{Mm��Y�X��o�Q��M�P���p]�b����>�N�ZY�qD�}A��&U��z��"���&�s�U���2p0���������9s�nXq��CTY�v���.��>^����O<�=[b����'�nz�������b�A�
g(�H�����jO7�	_����N$?q���!���Q���6��w�z�j�Gh�G]�~Iw����2�S��7wo9 :�&.��0��VNPR��:V��n��I*\Q2�r9jz�/�����kE
zR�u��C��Yj�}0�p���s�"����;�mMA��C�����Y�f��
+�d���0��i8M�����]��':,�H��H��TT�))��
��Rwu��+Y������]["�9g���2nh��Z5��4iVy�w-�.5r%j5��Q�.����#p�)f��u��0,��&:Lr���W��+Ee�������.-�=Q��)6k=���R1�Z�Jr\�U\��d���
i����8�����_����T��m���q���kE���_���b��Jl�������Z��h����������F�H3�)#�Z�K�Y�M�<��}3�V��l�
�w�G��(���P��XH�{�M1��15<x�'�_����cN�+#i���h��Dp���:�5j��n��|����5S��z\5�1��,�QVV�jw����j�z�����l�M���pv���}�L6�.�8��fp��lC��I��QO� ����{�>^\�A���=���,�+g��*�Ka4�5b��J����S�4z��������RY�.�8��9���l���&�A��%�����:`���x����	T�� ^�R�{�3F/*k��&H(p#Q��TQ^)[�%k���9���m��3Y�'���C�����V�������?_�+�RN��Xg��[�lm�k�(R+:1~���:�����C'r�}������-��z��,���`G�z��U_}����L`��Hu��.�TTT���nf�c�>��/��G�`a�F��H�G�}<��C�"o�qB���h�a]EbkV��/��B�+�R5[+HQ]d�����o�Pt^c?��
��+3w�>�N����y�i�#2X��]%�n�SV�Z�B{j����c=`��/
8�6��*��tIQA����"���N�hlCAQ)6��l4���}�c=���U�_h����e8���#T�~��YtUYk
I�Ql0zx��
���JjR���j4�Gp���_oY���W�:,3V��p�,���e������)l�-((`���*\��
#5A&�������[g��O7���>g$�W�4�K*���u�${�����&����A��Q?�12M����,�L�"�8G�\N;+W�]�]��uF�%ph4W���;E���fn����5H2A����owrF�Lo�����U�2+���+�0���|�r��;6w�:��zH�T���t�Fs�m�'��~M+��E���1�8j6���S�M���p/���m6�d��Z/��<�(6=�v�Z����T'�F����������1�o��O{�E�hlAQi9?�����z1T��C%�@=;��vLgw?����(��9&�e���"6m�d����n���u��Fx� ��*Jk�����3e�/�l����8D)�Z��IQ�,:y�d�L��7.D�O��."-�tp��-��	2���������qW~�NzV.�v�hD����<�!�p�3�h�(��&�D6&M����2=�
(Q3���c5UR����qtl#:��]<=�H�g����!�'�O�&��],�Y�����FGd��Jy�C�p��Q����8���T��/F�X�B����8R��\S�D����ru��iI%O��8�����������l��#�X,V���p��0�ss��5k��}�v�(Q3���������B��_o��nf�^W�DD;�u�C
��2�C���X�j�wj��9�(�5�G�x�AQv#P�fU����K��.�A��:
��
��*$������Jjj�9���{V���>�!IM�/�(	8�!o�f63�G��Fvv6��MS��D��Mp����^/�m��}�CTX����\q��Y��^s.J�+�n�<��
��!	8|�j����m�8�2q�D��sX�O�F��
8r��F�[���b��W|�0q�XS;DI
W���]�0�||�l�8+��u,�c"yd�,�Gdp�f9n��Ft�b��l�	�(@�����Jii)�W�vo6�h�e��I�Q^QI�nUB�`[��|�8�g���z����\�Y�G���T�=d5�yL)q2�������4�(�Z�8D��>��-��kj��p���g
���"D>�����Mm1i�*-2����ci�(R�G5G:�&��)���e7>��c�p
�^�!)*�UTm�3��%�x�.:�p
$���|���]"��D]��������)`��}"&�]'E����E��a��U�kBh��vH���{7,P����U�2�(o���q#���od����D>��=a���7�����NQ��>�:8/lA�$�g��YJ*7�H���Md�����*��Z���Q�j�|�i���J��h�D��pd����O���5U47^N8�K*N������~Pd��Y���J��\m�T<����Wk����\������0���h�U\V��CSO(-����-�p���S���
N���)0^V�l��.�wi)l>��s{S�A�E��:�X�@Xd��E��wh�w7��l��#�Ce#i'���4U4�4^z,.-'W�� IDATGXG����GO)�r<p�}�yg�g8$����d��������|��*�9
�RaH���K�j5��;���4|q?oO�P��\���3Z�K	
�k)��Q���f�g9z$�'��/�Tl���Gr,�Q�"�f���Q���s|�`��-�E:@TV�f9�&������
:�-V�VU���;M�B�?z*W�7{�/=�i������$�������Q�w�}W�'�>WaH%�8D����E��R��;*A�����"�jjMq
�p3��?|B�yT�88k�C�t���!��IM��>A��k���,[�L�;��Rw(lpl��^�h�h�U�z6��i�!�c�S`��C.C�4�����<��UY�?�����Q (����w�o+���o(�+��
C��E�aA��8u���_�l6�����:$�>��KB���i�X�4�/������TA��{r��G�q�Hw�� �hD��q"G�e�t%��2{a������Ru5=�����p�-��T�R��.*-��I���j�*�r<r�5
����%t����q[�6�R%��o�MEE�
w>Ra��*�E��C7�:&���Ja��pH	��M������l\Y���(z��U��U(������P�I��>��(������	T������^���c�.��W�^MQ��Y����73|^cL&��]���k����k���)��hUY����b���q�����Q�[���O>�D����8�(���R%�p���������.�=����F�jtl.�������,G\t�ui���+PT*�v�J������}e��eee��������*�
[v�����Dt^�q5:��u��uIM�b��b;�����N��=��M��'O����*����[��R5����x����J#Y���	
�!.�x������Z������5TZd����F
�]���~.O5=^��QX����o����
t�Blp#�9��k�H���l��nu($�PoO���u��c�����e���4���g��v�����D�;��M����I$L��0w�\v�V2�:���)��7����g�]\�U����l�|s������e(�D��|:k=�����`Fh���?��!+����GO=������b;������9�Ve���:���K�nIMj�kZS=$�]����������eM����+�F���:s��K�������hw������W��jwjN��������z�j�/T=�oUa���:��0��u��%��|

�!�I=��5j�:�a�v�����J��'T�_��$V�������l����MpT�J�f���v�7n���9�Re���:��"(���c��d�:N��V��J�2������s8����/,����vF�H�q=���/����KZ2��c���ll��Q<q�_
m�&�8DuqYECVn����^�(V��L�;E��a�^]N�kLY���<���P����M�%�������f�II�Fav�m�����8��f��#�I=B|D64j8�[ :�����Cb�zD���l��~X�3������f����:�v	
x�>^�Gq����A���6;v�`���"���j:�i���#Xk�����w����M&�:� �:#���6i�Ew�)?�fds,;O�7g����9zJ�#���E#��/{�,.5VRq3��o�<�1~�x�jv�8����8@XV�;w����}��O���G���2�nfvL�X�@}R��TZ,|�����&������	��se,
��\������w�}'�q���E�
�8���'�x�V����JbM�8r��h��D)�.��UB��Dp�m�lMc���b;c�w�g�'<�x�QXRf�i��l�>����W���}�v�8�p�@0�|�r�&=/w�$62|^����J���7|�US=�\��*+���#5#[�7g�j�w����

��>)
<��@��\���M�]��%
��_ ==���V�[�'�1��p�1z����E��.�+E6�Q�����q$4���$������e��+�5����L%��{u$H�s��@�Y�����S����;���k���7���LI��G��j��8De���Yt���M���pHp���$6�Y��0�ss<���s7�S����y���T�I�j�]EY""���������5���@�����d��	"�(�Qa��f�����Y�fa,�

��u\���5H2�~
���7�L�8�yZ��������|�r������4�0^���e9k������!������).�y�s	��M5v�6���a��S�N�f��cZ�U���c�E�;���8W�}BC�������(��5�l��z�Zz���n���5�5�>Y���z&%�?v��}����9��7T��p��M~��'��{����I���D��1%.
_�8zEF
�����u���=g
��r�&��~��������qQ���&<~���Q����k�QRR"�L�	V�_��8D�Ru�F��iR_k9��J���G�g=���+��A~�n#�2_���X�Z��L^��92�`�	�:�������5(��i@;�Xyzz:�����9*��*���8����SSSE����f�����	�y���+3�g2�n�_������e��|��a��_I�����{q�����WH~a�2
�>�����k�g��q�����_�!{R��U~��G��u����v\t�O�8�f=qt1^���%+��)(f��4Ei\�y�)i(~��n5Z���f�E�H��;�Y�r�=�;���i�Z�������9,��T�7�8DuiG�&���-�����/]4b�K���
=r
�tnA�p��O�wQ^ax���`�Zy���b;���0�GR���E�H�������S���S^����*����=*�{+��6l����S�f����tY�������,���}3E��&�&L[�V�_�S�GWf��tV�<,�s����<o-�Vu3�O����C����/E6�a����#`�������ba��Y"���oV�f��#�������8��ecb�d��kv!S =��[���j,����`�_��Z_��e��Zi��.���N�Es������\l��Ra��G� j���q��Ed\�_#g��C���~��m�3U������m���
<��f�f�:y����������N�f���*-�j���M�H��~&N�(�q��
C�����TG/^,Z�f6���6��y�������#�Y]���P��l,��������������OkE�:�!��pM���C�������l�K��qh��=[�'�^x�Ua��"���W��,3z������E�.��}vg�f��W��hq���_�k�&-���*K�k�Yy�LZ�El����8��=������+/+�h�\��M��>}��U��Ta���W� 7�6m���m��+����p�,�P�(����0��l
}��bf�u�)M-���-��[�~������H�f���mi������Z������y��y�j�o���h����+3w�\�������&C�3u:�����=D�unY��qn��$n���b'��JR��:HQI_+�r����%?������b��q_�e?������]
�?��%KX�p��P���n\�=�L��0QQs������N�q�������IQ��s������Z�l�WT2m�n����b��������%w�\�!Adw���]�e���m�"[�f�Zy���D6.`����#a���"`��J���b�|����R)n���OJ�,�]�!A��Y�)�l�7E#����I��Y��������=����]�o������i�3f�q�F�\8��8D}�g����xT��*���������>^�]'E9�+�_�f�6�h40m�vr���}����A����6����_^�s�E,a^QQ�K/�$�q��;���;��^�p��YqY���;�,�&����G2	1�<r|��G�\��nN�`_z�"�4u���r�]"`M&�����k }~)�����h|�0n�V=��+1q�D�R�s��TrT�p|/9,A���!au0�H�g��t��%�@U���[z��C�i����F=*����#�A�c"�r�W��{|d����b�����l\���L��q��C1��5������f�I\#��Q1��6>�!�[*���	�����g���^5���=[�a��l21vx7%%������e#��w�y�c��<r[M
q����8B��	8l�pAA,9�B;_#c����}Tl���{�|���.-�*}5�,�E}il����!�������e��_���?����ybdO�m��'O��������]@���	p���
����UZ5�GLD���F��?�����o��Q��cb2Q�����������V��F�{�Q�I��M�����K�<��o���x�����W��0��
C��#P��03g�����ju�e{���	V�8,���M�X}�QiM�z����u{(��^	�F���^o����]ruBd�?(�h��k&L�9�x O�1G�Q�
��|z^^s��x������Ok������7
#�x�X�v�%WW�b���R-���-��T��`�V��dP���k�c�O=����b;@:��
C������7�|#r�q�Z6�k�kd�fd�����x2���x
{	oOw�:�����g�*�H��<��)�Qi�\r<�m|��/`�����7Ol�����G	8@XV��������Hu��1�d�:**-b;-E*��(�J��O�t6c�LJ^��.��d�V�2K�Y��'r
~�1Uc����<��S2#���*��:�#���E�����!J�pm��uE���9z*W��,����&,C8
�u������r����|�F��CM�z��?|lD�$%��&L`�NeA��TI��)��`��JD���lh�������=����n�C���Jl��� ?�u~^���
%ug��Z�g������Z�������������0�6���|^~�e��s�G(z��8R�B�e�����)r@�U���r���J�-w7��?��G�wj.VE�y����>�l���V�\�o�/����-���k�q��I��s<EU�b�����T��7��ba��)"��k������F
�7��B�fH��?:��`%�j�����);����3���h�O^a	���`����y��N��c-E�uk����;��#�s����)'�� ��eO�$�F�M^B������`��<��&�c"�����N�r)��S�����,QS���~/h6�x����� ���?.�z:G)��
C�����a������O��T�@����B���\���a|��	
�Qf��H�E�+*��)U�7M����0��eb����t�v�}���^�Il,�:�={6�g��9���lS����f@1H��(��Q���{Y��
3!&�O������l�
7�Y�W�r�a������A������Qn�����_���E���
�F���R�q��s��,h��p�0�!
8�&C��,�#��IK8zR�`U���L|�%O@��[���l�-n�����B���y�[����~oxrTO�f
Tm���_.Dx�uZu�Q��:x���X�f��������DQI�}>��ruc�a��|��M�n#[�nKv����=[��]Gy����/*�__-VVZ�Z������x��&J���;��q��v��
|��������g��@�Qnnn:���^l;p�c�ub��Sp:���9�i�.@�pwc@���&���Y������8��h��5�Y�h�G�QAFVa��$6�'�e2�h��u{)�������c���%���������("f�{�:?����U�L�Baa�����QD�z������6)�i2�}�u���'���I�'7���Cdc�Z]N�8����,5s��a����Lp�u������\��o��V�w,~Re��q��a�qEeee4o������D3}�vJ��5r6�K�E�����i���-8t<�tE7C	���Q���<��G?�U��F���J{��bh�DL
J��Q��zqK�6�1���
��J���	8q�/T�ht�������3��?���@C��P%Q�GoR�2z�W�^,[�L���o�2}��
�z�=����I��Rn�j�V����+)������������O����������5�<8��_�I�-+j���}�]��)�2v	L@,�h�:����tm����J�=G�)�p��2z�d2��~�����w>����>���>����#Ihn����������q�&�����	���p���
�?�?N�)��k4v�l6��#7�Y�'H$&&RP����4���U�OU@�H9�������R`&���G���(2z�j����_�HlR��2�G�m8[\���~P:.{!
��xw�0��������G89���Llh����_�W>*k��{LU����
�������������a�`��X��`���3_2z�a��9r��xl5c�^�f�������O�D�z�[�VZ^����1q�f�/�rw3�����1�#����|���^i4�#%.�O��	w7�=����6L��m@�z8.���OGUY��[���X`~M9C��X,10o�<h�|Qi9���@aI��
�
������H��jI/�����W�����l�T�%��}t�������M�t����FS����-O���.�>{�,III9�L�f����"��*�p|y��1x8^�/v�)���?����3r�H�x����{�Z������E[������@_�]������(F�nM����r<'_�5n������
���/C7:k����O�4*T���/��"s��Qi2��^���?B�*M�ITi�l�����pX� ��Qiii<��C���X�
d�����klOqi97��s����lz-7����\��%C:�������B��,y�����h���-�>rJ��FS���y���cm��p1���c���b��$h]�EU���O:�p@U��Q��*++i���;w6�@H��S�q����Y�ZJ�+��1����hT+����C����'�~��	�������E5V.����v1���
�NZB���y5	���9��.-��p���,#F�����6����������~�3������G������x{��x�U�F;SQYI�VM�2]�K����=�����u\a�~����/,����OQ=[�������b�����k4�&�������\�(�����O���Omz�:��*�,+��r_�,�N�R7�,^���}�>_^Q���$;O&���-O���m}����?`�Z9�S����?]@NAE��-.�����J/��W��������
��h��JQ�Kq��q����\m�����?h���:~�*�a�y���>�n�����
�a�gP�6�&�a�Jv=\��v)�hl�g���E��wx^��c��`�v|l^�AG���b@�M���~���c"'FtO�M����#{%3vx7{�a7��
����E5���b��/��d�{��������j~%��E�9���q�,�~��-�����~>���gq���64���/��o���#�j��_{���}h\/��`B})-���B/!�8�n�D���fvv6C�o�\�(��(��h9��y;�l�pTTG����x5isj������tl����wg����5-7��&�6g^���"d�&5=��GN�v����j45�������1�Ss�'4P�Q�����2e�R���RL���qp���Q�=�������o�Y���^����:}mo������������]q:�+*��/�����t��������5�=C:������������{������&�Z�hA�-h��%�5"22������L�����={���_��e���G���8��tKk�����%KDN,����}6WdC##6*�O������n�*�
K��b�mU"^��T�� ?�����[�J�����W_}���~[��6�`2����%%%���Z�nMRRf�]U IDAT������egg��'����os�����b�$-N8c�Ukr
�r�L&v��Ibb�a*-nxq"'r���Y����gF�nYbee%nnu�,STR��K~a��MZ<LcS|��������
���?0y���N����SY�b��+�������L���i��
)))$''�~�-77��_���zKU��-�)g
8�"u�Gy���_���%���w��7����&<u����eee�9���<��G�����vFN�����KX��l56�m|4�3���������c��1��K��z�j���������5"..����_���U+���k��h���~������f
�5�X
�����'==��`�oZE��\��/t�]-����'��-7��������<�7]���K/���}�W:
?�����.��%�L0fpG��f��������u���o�>���8x� ���SRR����d"<<���0����S�^=5j�kp#h�3f����nS��h�������������z�)���q
_��$���f��7�|=[V��$=���%?��S'�}�Y�n�&�
lK����g����	���7�4<d�������O^^yyy�����@!  �������7�|���~Zj�o�px��p����9t����;���
�����'@�b2�?���N���}��W��?�q�����������{�%::Z����������9SPloW4N��/��7\����hPZZJ||<3K��C��

h��)))�����$#+���l�64W������Wk�6?���jG�g��a������{�_���J�F���6�F��
����&,��FIY����8����=����� ������1k�,����h@ ���uk�m�&R�<x<�[�9����5�cd�d����R��'O�������xf������{3|�p���C�-z���K����gp�X�D��#����n�jo74B����r8{��3p����y�8p����~8Sw�����cy���)m0�?>��
S�y�;�������;w�]�v������nl�Q�~�8���.#j�J��1��������W"99��;w>�
?�����^����EN�>r���O�Y�$5��'��P:��~�z���KQ���Pc6�����U�V4o�����4iB�&M������y�Q�/���o���
������WF�zAw]e��QL�6��y���1�|`7`X�k��l����m�v"�q$�$5�YE�D��CC�;v�`��!�l@���������?|�d2LHH���<����s�=���
F�Jf���_��i4s�u�u��bH���;��V���E����\��9�����S*Y~���BNN�2��V+g������l����p��Vv��[{�W7�f55#"��[��m��3O3q�f�1q!Yy6�^]����������
�j�!<<<HKK�Q�F"G���gVl?$�Q�������n$�I=e6������ii��4��c�)	x���+w��d�^"����-��������Qi��y�1�o?�����<������=y��k��g�~����wg�����;�X��T>@_�,V��A��i\/�Vo���x�����a��W�s�����v;���C���/��m?x��K��xK�db6��

Mc]���plL��`�_	��������gz��|6{=�����W�d����^�����U;�95���0"t9G9O?�4����x\)~F
������&vz��Y��~Pd��aa���2,�l+Z�h��u�

Rf�T�Y�MZ�������������{�&:\����Ry��y��i���n�������~�8����=GO����=��r���i�(R�/u�/��*�"�>������
***<x������u������Z��}����9S�M��h�"6l��������#���^<U\V�����n�v
�Ji�������Q�,�z@��j�pw������K6�e�Z���M������=k�������r';��AX�dQ��)��$��i��9Jx����8��~�����4W�p��4���r<��<lJ��+�B��o����WjS&�����3b�e6��:�����6F|�0�;L��N����m�^'�Qi����?�f�E^U��0���sm��\$�8SPLjF�3�I��fF6�N�`2������(c\PP@��M9}���L�+��^H0e�@qq1�����d�5,��e�Z�J�l�3��Vj��>p�`����WllN���Og�X�+��i�?��=;��0Y��_�x"C�9u�����5P�X������������j��F��e�c�h����}Z�AV^!Yy�����3��WYy���� ?^`)q�g(��{��'
6~q�@`�����7iii4h�@��G?����E6\[{M�<���GcuP�A�1k�,���T3��r����x��&<}��u�|�>�y�����Y��}��>�--����^��f����0�c�h\/���PF�[-mx-)��DNAUP�]�'#+���|2�r����:.��BD��V�?���E||<���W��+�/W8V=$�����_��%e���W������3����Tkc��%<X�d�*�����q#���J��)(f��H�����{/����P����Wb_4�ILD0?��N����Oe����<���f�~h1�4�"2�?oO��=�������_/��=�
����w*+-�T�).+'�����"rK�=[|�O���ST"�g���5O��w����<������]5���P���a�N�Mr�)	{����n��/d�������<��	

b���4k�L����J���#[R�)�g2����H��1";��k2i���W�2�Ss�=��N�}�Y�1�[��
B|x����n�����K0`�h��9r�HWP�s�
%%%���kbGn����ab;����;�<4Ti������!C6�pssc����
�~�HY�`����,/d��R&��q^��rg������C���Ly�������nSl@�{r������������0�M<1�����l6��}�HjZ_����<�"~�l����O�~����r�&�n����y2��X����F�Xu�j��iT����Z����zy��m�yo�
�	zf.GQQ�F���Ie��/�5v�\���&����R��'v�S��'7�qv�]I�y���1b;v�PfS5�>�,=��2{7�����(�w1�-�.:���:�X�s��^���YyzJ5���)���'n���&�eee�5�U�V�2�X�p�Cj��/�����bG�z��fgbd�d��o|��X�V����*�O>�������,^���������]u	
���[����yp3�Ee��eK��������u���P���FG����;�����g�4����q��c6�^���2^z�%�#M��(��u6l����c�1y�d�6U����|��o���f^a	O}:���
e6/��je�6�,���	���8�CD���.���/w����WF����^��TVVr���2u�T�f������P��1y�d6l�-�7�
#���p���}�0�������|���JZ�l����y������X��0a���9�j�q_��|+��~5�AT����DN�"O\�	vL`�+�y����*�(�����'�6�����p��V��'�xB,&����\����������{=������"$$�7�|�m�����v-��3��n�Q�6��t��Q������-:��
����s����q�R�z�J���p��7�"�������������B]���W3}�tn��f�#]1�Ss��`���������o 2D���%K�0f��RMNNf��1�{����1,�����E��5&�@&T����2�������z�_U����w��
����>�����6]
<u��J�1��ZR��g�}�a�����%r��[z�qo:�]T��l61��!J�Gv����#BE4::��n�����������:i�N��/m�$z)����	j.G����(��wv�&�Rb���N4�����=z��C��}�l2�2<�aez]	8��Sv����C�x���x��gD��y���}x�����3���K�:(G�j��C���o�s���m�c�LA1�8���r�^�RH�7G�@ij�-�3]��n��7�HR*�X�,Y����JV�M�u�_�u)����,��q����{���E�}���dieT�F�JVf�^�^����W�^����k���F�jOA����'?��q;5�5f�tz\SS*+-�v�V��p�K����@�6qx�A*�����������&o��.���p@U/�<����|^~�e>���\�x��^l��!�=p$�%5��Q�TU+++���;l.����FRR�\s
]�v�[�n���(�)�������K�>����Y��4W��������]<=Z7�Z�f��9��>��i�lu�"`p�'��p�V"�$����3v�X���D��y��1y���X�;
� �W��t���GQ-@@hh(]�v��O��m��i������u��)a2��d;_�Ky�q��O�n
G�d���p:���s�F�Kh�tR�K�.����"=]6�~��R��'��:�***��_���+����r��������DPIH�o��z��	���W�Eh��1=z���O�-�����m|���d������iR_�����P������K&��������l&.:����i����-b
��{������^z���z���e����]���b����Ibd��UL�0����O���C��q_;���m<��x���+4���EZM�6e�������={�j��Q�Y��w�����Bx��^b;�i���+����_�u��VM�i�n�nM#��1�df����@Z6��U�z�jZ�1��P��(���������L��:�c^��Dk������g������F�6�3��pg2�?���N���\�~=}�����f#�-[����nb���m�ng���Z��V����v������O�DJ�|���������.��7X\�;OE���GN�%�[���-�8E��d6��#:,�����iR?���P�F�������������|��G��j�n������r�#xxQb����<���|��Wb�����1y����������iii:���F`` <�c���e�����-�**���Y�)�����
]�E��i����D��f�ul�c���X,VN�p���O��{�����
K�/,!�����
J/�3TPTB��7&�xa6�������L��������C��A�>D�Q/D������<��#;v�6.7��jPw���{�]������[oe��!b�:�l����������lM��q����2{yyy:�Zs��7����� 0�v��Uq�T./N���#���
}��3z���4�O�P��J��Ue���@�&��2N����y��G�7O4�Y>���RY�C����,��y���~��9����W�5��M���{�������#F�w��+~]��
���OHMM����r�`�b�2m�v�4�[�6��D��{�U�ZN����#<HT��$;;��c����X���?���a�u;���*5����O<!��������/�B��!����uJ��x��,Yr�������SO�����>���s�������W������� z1a�����P�#{���ij��`u;�4W������z�f����G�J��b*���������K,�1��_~�O?����n��01��u�����-�			�^�����?��8��YM�u�$�����=��m"%\c�}<y��aJ_KM�����@�T4�QYY��I�h��O=�����u�R�V�#���p,���E�}�����j"C|x��aD:���������J���9�^x���o��-�V��S�N��Y�l�����~���SY�������s���6R��jM��C4���������&11���G���V�����}RU������f����F�b"����7h����2O����<��m���n���U��mY�p������lq���������w�g����v�wx�����C���S\�K*u	��a;***�8q"����y������D�v��T�������TEq":���/��w�{���+%���QP\�b8f��������;����_�~�>}������g��e���+��-)-�`���L���}��e����x�q�=�y�����,i��6����ZK�j�Lr���o�F�CSEff&o��6w�y'_�5999�pc
ppR���<{1wR��x������k��"�����y����,[���`6���]���2�EEE�9���_M&_���g6N��~�Q��r�5��P����!>���P�������+tI�.� e_g�j��l�2>��Cf��Iy���)����wT��oT��NmYY�F�b��MDGG+q.<��	O���d���w�^��w�Z5Vf�j�r��w�~���~�
7�@�.]�]S��lK�d���������,�E��Qd0�=2����K�k�c^� D����f���L�>��S�r��{������la\�g��������5jK�,Q6������a��M|4s����������^�R�/���W#�L&^y���4���"�<�/����q�9EYE�����5IM�����)����GM�Z�l���i��1}�tG2���g�[]D���0�������y��G���O�^��d��u�u\��jYy�l����o���
j������kW��~�����WU��e!	$�!,&,!����,�#"R�`�j����������Y�����:� ;L�Z�Q�����hQPA��BaK !d����q@��{��������8f��=����=�|����{���3��~}����t_-�e��������W���k�����^y!�]5�� ���������������{������y���8t(�E�NQ��n�;R�q�v��8������������~���j��~���c���xyM���~z�n<p�%�7���b����|���=Et�L��J}���F�����]�l�s0�s0��+5����\8|@H�o��JT	��������;v�a�>��S>��v���a�K��/@PN
U�qn��������=������x�b'����]��%3���~���{��3�H����#�u�dR��|u [[���6,0%��Z��PR��]�(�U�_�vm�������^�����d�p������J�.�w��/:::(--e���l����������s��q��@[����5hp|�.f�>���r�
7��O�M�f>�3�������WS�����aq��l��~A�O���I��R��f���>�����n�cM��-.���R>����vwO�g�&��Kfr��!��D�nI	tK�,���k�u�]L�:�3f0k�,&M�DRRx�mmm����;v�}�v�m���;())����0R�u�XV���R���:��"@���MMM��7�w�y'`�3�e�r��i��h����������[�z�t��HNV��d�3%�e�����?�_�z�4�EQV]������tDA����XO��(1T��4a������F�}�]�}�J!���#77���|������c���:���������jkk���f��=TTTPQQ����w��`�WH/w����A�7�n^�?������3�>��q��sR�QvF^<2�}|���w���o��z.���`�w���JnV�Za��H0u������7=�C9McsD��'zn���o�Y�����{��s����kW222HOO�������~YINN&!!���������c��x<�����x���9��x\=�+�x'�Q�q~�XP9�����/����W�dGF�y<n��F
�n[RR������OJ���2�_��6��*_�K|������e�����9��o[������gO577�w���-(����E�/���S�������>|����� IDAT�.��uAG{{;�]w��b���-[��_��'�v��8��+k��p�v�kr����7�;���b���!?[G��>��
WWW;49E3����@X�����6(�������7�0��>����d�^�u��8p �����:�`g���%����N�����
A�f�[b����y
��Q9����kCC���?������G$�������g����w��>'��y��
�
�) �p�����q�����Z.��RV�X���_��#C���������o=����7�|�y��94�����0e�Lq�^/%{Q��������@�� {�L���9�7�I�����KKKy������{���D���=l�mnnV���`9�����b����	��P�#�?>��/��ot��As��!.\�'�|���z�!�����d�����>�������odk��Vd[�vW�ed`�����bdN��K����0��6l���������C3�8Y���T*++ITj�
4~���!�)������X������M7������o~1Ep6o�������q#/���]w�c��Efj2��
>��j}ce��Py�(����j�ihj�����?�U�#66����t��H�n��tM �{7�e��_f*�z�2�&=��@�����M7�Dccc��"$+�����={IT��x�0��8��bc�`���.]����y����7<w ����/s��7��������o�5�����!���������������_�����EN��["���
��_Z�������6����C=�p|r����5���{��G;�����}�{,Y�$`�
=z����SSS������C��;�_���
6�o&����G�;�l�:"8�&v����u��n��.\V�(�z�-F��3�<���������t��U�3f���E���#`�`�
�&a$�#r�3���`�0���+W���������#���q�W0w�\�����oqq1�\r	Z�n����w��UW]��W1���1��:���!�X��]_�rP����\!��+������#�<�������NCC��o���p���2q�D�-�vm���3f�u�����&����1���-��1Fvb���.�r�4�B]��T�)�p�K����������OJnn.?��O��u����t�M�5��^z)�/��;w2y�d�/_��D���w�h�",X���������u�4�:��X;K����[�����jT���g�z�)@������`��A,X��g�}���9,[��q��1i�$�}���:������n����g�}��P'"���p�=�0r�H�
��jn
�
��������v���Z����\�b�h�x������g����@@��x<RXXHll,���c��q���3|�p������%.��J�---TUUQZZ��m���ek������5k�0v�Xn��Vx�����!��#G���#��t�R�?�w�3?3��tl�O��jpp+������@	arPZ8R���B`��?{��^Gtvv�i�&6m�t�OLL$55���`CC�+J	wttPPP��O?�m���}��Gv�{ke����#<���,]��c���~���������%3�����NVPQ��+��u����,J)������[@�*x���r��!:�!TKKK�.e����z����G?b����o�2��o����g�}�(��U��b
j���:/�7��N����Z�8S;pk��h�*�U���:q��
2�v)���#p�`e����I�����K��l�2���������9s"�D�����X��'�|�5k��z8eB�C��pIM�h��#�����?ap������7���7� ##�����a�����1����8�������O?���_���������D�����Q��p�A`:V�r���=�`.��`tX[[KAAt���Y�f1{�l.��B&L�@r����`jjj�����O���]��#�/D3��!_OGp�7���xy>��Z��U���`����U�V�j�*���=z4]t�'O��/d��a���~�xEE���g��
�_���7����a���o�����z��40>�c	�v�_�_��61/�#�k-6$:::(**������������O~~>#F�`������0p�@���K|�s�T:::���������Rv����m�(**R�q�&3��������T��p_10x������b��X����>������jmm���������oqqqdee���CVViii��������S�=J}}�����)++�������-����2��BT�����QEGh���U�I�-�n��5���=�����<���z<�����}�B=��hll4j�5���]YERN0I5���e�S	�_��n%�%���^���M`���o�g��I�5(	��8}��Yjr]�o9786��T���B�����53�����X\�U��_��q��NJD#�58��p��:��|�e�����*�[�%z��Y{������^D�T���%�p��J�c��c�������x��*3�T�a���'��imm
�$��0��Lk����u�<+����n��kk`�2H����:���J�d�u?��������.��Y_9�����f�+��%�>����k�c8��`�W�~��Y"���^Lf8:;;��w�������z;���+�����������}Z��6c�����T;0^S��C�c������W"b�$����6�A�����#ru�N\���J<���~�g~C�`-]Tc�,	���k��������E����PB��$�0XN�y�`
8�������cX����zn�
t
���P=�PlV������l�<Vk*��GF����p���Ht2��F�������������w��N~�l��k��e��)i���f�0��18�(�+�i�C"]=Vy�'����s������	|��������O_���~�z��������Q����,�����+�l�T���&����G��G��<�/�����!8T��p�[�c����X<�6�)X��@��o��U�m��k=�N"�<���8";��&��(��n��e+����u1��X�]��n:kw�``�t*{Z�
�m>�r�`�Nnnh0�n��Uj�[���?���z)+�s��eAWP�!������Sur�*�b%bf=O��������5�r���'�=XK@e'�j���W���W|r����Zq�l��c���&e�5���f9[;�����*C/Q�_��%��
P��
��q?MG����	���h��A��3�

8D���$S�7������6����#�gGI(�q?�J�;f��%)!��������~]��5�\���k��f���8}���I�(�p1�\���D�����Mg8�%j���LF�8iT3.��C��������mj����mndRe����}���t�P�!�~~�v�����d��J�������2
dp����i�:��������b�0
Pk�	="����JS�_�Z��������.��D&��f8\A����A�� N�T\�dv�FAI���o��k�������tU�	���`U5��%,(�q�F47����4]����6!8�u.aC�"���o��6�j���d�_�����`�4z��s	
8D���}���~O�|)A������������M�W��
8D�������'E��g���'����r���>@���k�: ����vgI	��p���X����n�@�q��p�D�H������os�>i)�����:P������ �
8���mw����%�	���P�!�J5���5�mX��I�(82��m�.�o���WR�IGrW�6w�r8���
8D��_3&�Tt:����28<h[�k(��~&u8��m���cp�����a��_	+
8D��_��&��U��]B|,�^�H�P�!���r��_��&�K���H�OF�n��;�0Ze�	
8D��_3&�bA��naz,�	�������C$:�p��p$')�p�~�M���C$:��4��C��i�^K*r*"�!�3ZRq���K*�w�6�f8\D�Ht�k��4�#E[c]a`o�3TV�
8\D�Ht��J�f8\a@/���={hoo7���r"���)�pH��8����n�k�.�!��>@������KvFb
��;��a\5L����p����s8pD:��
p$��i�	/
8D�C�?7744��zmw��UI��.v�h��ep�D�&���&�*ZR�|B?�a�"�E�H�����F#��������8�S��(��5��l2����w�A����J�-�m����(��~�q��p�Gd���
���]���!^p�D��T����3zk���@��V�H�Q�!=�phI%����@����$�(��������������D���Qb�Y�F�XR�n�	?
8D��n>|����bccHM�j����}���������)��~�U[�W��YR����K����?����a�����Qq%"�����:d�YZw�pD��,�3����[bw�&����C$z���RS�W�����(��D����N����a��$<)��~%�/��hI%��o����t��>@�����
�����J�8Kz�nF�%4L�7���������C$��<�a:��S3)�pK�a���v��������[[[�����d�m%tr�T�b�(�T�������X�����q��
8"Qn�����j�3xP���)��.�8z*��4]��'-�v{�76�>@����R���{���s��=���$4���$��&��Z�H�R�!]����d�#)!^��G�����n���
@����R�����~'=K�T�rD������o�����GF�K�S�!]���.��^���(y�3���4���s	{
8D��?G+**�:�J�n�^��K|��3l�/++����d��p9"�������J�8K��T��<C�3�g����F5`�q*�M�H������G��U���a�����}��ou.A�H�����ee>�'g����#R��m�~�&�C^pD"�g�?7��q��G���������n��Xm��D"��������vG�R�IJ���^�#'+���]m�/))����v���K�R�!}*�_o6YR�5<}To��~F���5*��Q�1p�D/����
�G��WG��1f�Q{��C�QB�Ht�yY�4�0�� ����_���o|������F�K�P�!�|��8x� G���Q�@��9$�.q�]������SYYi��;@���%�(��N��������9YF'�J`]<*�������F�KDQ�!�6m���u�_��5�A���G�11�k���z�����F�KDQ�!�Z�'���AfU,%0&h�������c���el%�(��^�|��4�gX�Rc���F���[g����Q�qp�D/����":;���M�C\��n�I�n��;��+W����(4�\"��D���}�����h{ljr���K���zR	]���,�|�u.G�H�:|������<!rN�Mj�^����#��������'����s�H
8D��;��hp\>)�n�]��!�;�/#s�=����������s�H
8D����a�jR�&0�"�$Eq�Ms&������g����%��h�p�D���f_n,++������kf�A5�BkPv�G�=��w�e���v����s�X
8D�[3~�r���kF�
����<�s;��L1�~����m����%R)���}�q�
���%��5~��3y�@fV������}����q���%
)��?_n���/��i�Qg������������X��f��s�qZZZ�4��6�D,"R����������bc���'=C�w�����0zFcc#��-������F����CD��e������z���$�G7�g��gg��S���������;M;��� �������~���y�	;::���S���������eCI��g�o����G��3��9\{�����:o�������>���'�x��l�kf��,G��hC��-�������NS������9�;p�/7���1q�D�
f��.�q$%������!�l��A�}��m����\s�5����i���l�����^|��x����;\t�(���4~��mTn��o�p������)//�������
T�ODN�10���?��3&M2+���t?���:�*����z��?]CZ�������#//����i�?����W�����*����555,Y����>���mhb��CF�K��d��E��:����y����4��`m�����&���������e�F�e�iCS+K~�<��T��D��T
~�����<����1c����n��f7�4���S�C|mp���Y��.������%he�����/��C3^������]�v�i��E�r
"r�`��7���p���3`��N�3z���e��}F��F����W�]I�n��=��'����l���/��#��%9Sw��s��i�����w�����GW(��QRB<\?�+'�;��;v0i�$����4��[Y��^���3�c�3���;v,��7�8&&��#���]4��=���
���;0y�@G�������s���]������f8D�\������a���u+�������W�-��_�7+�8SRB<7�"��tq���R����y��G�6/�
Vme���i�CD���{�XV���%--�)S�w���#s�x���x:�Ez������xt�NT�:CAA>����`!�����h�CD������4HIIa����	�'m�Q�=O�������ypvw,������Gaa!�/����}�w98$q"�u��_k$��������A|Q~�xl%��Z{f��/�.�����I�6mb���v�D���������&�aM����W_e����
����/_�Hccc�5vK.�����o�����=���}Dp1��s�7R�!"�d����222��e����
������1/�)v���$35�����3F;V��|6�X�����p���|�x�e��Y�^���8gs�Wo��/��K,��%r���\q�0&��'66x_��6mb��9��}
�Pf���v����T7��������8f����`eg0�j������gCJ�f���/����f��!��L%&�9g�����3gG�5yL9p%������4�!"��k��/qqq�\��y��`H�i�>~���l��7 �w��~Ly�F�0nHv@�g���������6I+oc*���QI4P�!"��
�g�ajj*}��G�vxH_�^q�o���v�[h�e�2~h6��ds����INN��,[�����������X���$�(�_������?�|�	��v�ESk;��AQ)��U������bc������7$�qC�����~�q��qn��V^|�E'�<�]'$�E���j&��n���G�f������7hk�P\���;��i�>�Ru��|�>i��;���4�
������AB��M�+))a���������}��ZR����{X�+��?���W-�8���F�k�Q{��c��kj����N�W�,����5��I	tK�Bfj2�=����JR��91���������C���H=��Xy:VDDn<���
��5a������8���w����F���C��9��������UUU�~/���c����s�7>>��`����������{1|����xw���w�+455y~�aoff�����`cd ?L"""�d!�������}�Y���������Ox����4�X����"""!�^l�����{,��������}��������4�@1�7p��34�IDAT�%bU�t�%�p�B���GC�.k


�'�x�;d��@^`-�3@�[u8�����������~�����w{���no��=hx�W���|TDDD�,:q�����������{>�ZZZ�+W����7��@�<���0�0�SRR�=�����!�����x<�>��{�-�x����dx�N{�=�	��c��;�B���������666�:���v��~���������V�q��.t�� ""P}��R����wo��~�3ommm�cc����>��S��������� ���2���@DD$Xr�~k��299������n��P�
>�����Z��{���{������	U��j�k���������� �<��������|������:��Ruu����_��y���q��y���B`�z����OY�O:-VD!x������1c�f�b��	�3��=_N������7STT������q#�����O;�;�N�		"(o���rss6l#G�d��A������Cvv�O�HKK����C��w�^���Gii)�v�b��]?~<�����kQK��"QN��R�&�W���bbbHKK;+����������&Z[[C4:G���	�@DDD�!XE����ZL��'#""�2q����e��k-p��?7�6p�����ru�S��!���D�@!�YG�U���"""�
�z.�������!k"""~I���h'�/�p�����]"""����{�\_�&"""n6�@�_���:���O����"""������c�:�U<
\d9��&"""v��������W-V���hCDD$lM��	}��������X������"ib������E@���`�`���C:"�0��CD"]��;�d;�O'�(�:��/�v�+��o������y�@pIEND�B`�
#13Sophie Alpert
pg@sophiebits.com
In reply to: Chao Li (#12)
Re: Fix missing EvalPlanQual recheck for TID scans

On Sun, Sep 14, 2025 at 6:49 PM, Chao Li <li.evan.chao@gmail.com> wrote:

This is a wrong example and (0,3) should NOT be updated. According to the definition of “read committed”:
https://www.postgresql.org/docs/current/transaction-iso.html#XACT-READ-COMMITTED
“A query sees only data committed before the query began”.

You paraphrased the docs here but did so incorrectly: the actual quote is "a SELECT query (without a FOR UPDATE/SHARE clause) sees only data committed before the query began". We are not discussing the behavior of a plain SELECT query so this description is not relevant. For Update and LockRows, the expected EvalPlanQual behavior is that rows are checked against the predicate twice — once as of the statement snapshot and once as of locking time — and the rows that match both times are used.

In my example with ctid (0,3), the row matches the 'ctid = (0,1) OR ctid = (0,3)' predicate both times. The row is not newly created, so the newly-created row in your example is not analogous.

I continue to believe that my implementation of TidRecheck plainly satisfies the contract for what the scan recheck is meant to do; the fact that it matches the enable_tidscan=OFF behavior is further corroboration of that fact.

Sophie

#14David Rowley
dgrowleyml@gmail.com
In reply to: Chao Li (#12)
Re: Fix missing EvalPlanQual recheck for TID scans

On Mon, 15 Sept 2025 at 13:49, Chao Li <li.evan.chao@gmail.com> wrote:

This is a wrong example and (0,3) should NOT be updated. According to the definition of “read committed”:

13.2. Transaction Isolation
postgresql.org

“A query sees only data committed before the query began”.

I'm afraid your understanding of the documentation isn't correct.
Maybe you've observed some translated version which isn't correct, or
you've made a mistake in your translation back to English.

For the quoted line, I'm not quite sure where that comes from, but I
don't see it as it is in the documents. The particular part of the
documentation that's relevant is in [1]https://www.postgresql.org/docs/current/transaction-iso.html#XACT-READ-COMMITTED. The following is the
relevant text:

"If the first updater commits, the second updater will ignore the row
if the first updater deleted it, otherwise it will attempt to apply
its operation to the updated version of the row. The search condition
of the command (the WHERE clause) is re-evaluated to see if the
updated version of the row still matches the search condition. If so,
the second updater proceeds with its operation using the updated
version of the row."

And this example also proves my solution of checking visibility works.

The specific part that Sophie aims to fix is the incorrect behaviour
regarding the "re-evaluation" of the updated row. The correct way to
fix that is to ensure the updated tuple matches the WHERE clause of
the statement. Adding some visibility checks in place of that is
complete nonsense. What does need to happen is validation that the
ctid of the updated tuple matches the WHERE clause of the UPDATE
statement. The reason anything special must happen for TID Scan and
TID Range Scan and not Seq Scan is that in Seq Scan the ctid qual will
be part of the scan's qual, whereas in the TID Scan variants, that's
been extracted as it's assumed the scan itself will handle only
getting the required rows. It's just that's currently not enforced
during the recheck.

If you review the ExecScan() comments, you'll see the recheck
function's role is the following:

* A 'recheck method' must also be provided that can check an
* arbitrary tuple of the relation against any qual conditions
* that are implemented internal to the access method.

If you need guidance about how this should be behaving, try with "SET
enable_tidscan = 0;" and see what that does.

David

[1]: https://www.postgresql.org/docs/current/transaction-iso.html#XACT-READ-COMMITTED

#15Chao Li
li.evan.chao@gmail.com
In reply to: David Rowley (#14)
Re: Fix missing EvalPlanQual recheck for TID scans

Hi David and Sophie,

If you need guidance about how this should be behaving, try with "SET
enable_tidscan = 0;" and see what that does.

David

[1] https://www.postgresql.org/docs/current/transaction-iso.html#XACT-READ-COMMITTED

Thanks for pointing out “SET enable_tidsan=0”, with that, yes, (0,3) can be updated.

I was reading the official doc at https://www.postgresql.org/docs/current/transaction-iso.html:

```
Read Committed is the default isolation level in PostgreSQL. When a transaction uses this isolation level, a SELECT query (without a FOR UPDATE/SHARE clause) sees only data committed before the query began; it never sees either uncommitted data or changes committed by concurrent transactions during the query's execution. In effect, a SELECT query sees a snapshot of the database as of the instant the query begins to run. However, SELECT does see the effects of previous updates executed within its own transaction, even though they are not yet committed. Also note that two successive SELECT commands can see different data, even though they are within a single transaction, if other transactions commit changes after the first SELECT starts and before the second SELECT starts.

UPDATE, DELETE, SELECT FOR UPDATE, and SELECT FOR SHARE commands behave the same as SELECT in terms of searching for target rows: they will only find target rows that were committed as of the command start time.

```

It says that UPDATE will only find target rows that were committed as of the command start time. I think the statement implies that an “update” statement will never update a “future” tuple.

With Sophie’s example, when s2 start “update where ctid=(0,1) or (0,3)”, s1 has not committed yet, so based on the doc, (0,3) should not be updated by s2. But with enable_tidscan off, the implementation actually updated (0,3). Is it a bug of the doc or the implementation of SeqScan as SeqScan also doesn’t have recheck implemented? Or any part of my understanding is wrong?

Also, for the example I put in my previous email, in s1, I inserted a tuple, and s2 didn’t update the inserted row, which complied with the behavior the doc described. So, does PG treat CTID query condition specially? Maybe I missed that part?

Best regards,
--
Chao Li (Evan)
HighGo Software Co., Ltd.
https://www.highgo.com/

#16David G. Johnston
david.g.johnston@gmail.com
In reply to: Chao Li (#15)

On Sunday, September 14, 2025, Chao Li <li.evan.chao@gmail.com> wrote:

It says that UPDATE will only find target rows that were committed as of
the command start time. I think the statement implies that an “update”
statement will never update a “future” tuple.

It will indeed see a future physical tuple so long as the logical row that
said tuple refers to already was committed, and it found the corresponding
past physical tuple.

Admittedly, I’m unclear on how exactly the system communicates/understands
that the past and future physical tuples refer to same logical row
reliably. In the docs, one is left to assume that feature just works.

David J.

#17David G. Johnston
david.g.johnston@gmail.com
In reply to: Chao Li (#12)
Re: Fix missing EvalPlanQual recheck for TID scans

On Sunday, September 14, 2025, Chao Li <li.evan.chao@gmail.com> wrote:

evantest=*# update t set b=30 where id = 1;

evantest=*# update t set b = 30; # block here
```

1 | 5 | 30 <=== only the old tuple is updated

Can’t test right now myself but I believe you’ll find this much more
illustrative if you don’t have both S1 and S2 set the same column to the
same value when doing their updates. Also, include ctid in the select
outputs. If the second update would have been a=10 your final output
should be 1,10,30 - I.e. you’d find that both updates applied to id=1
after the second commit finished, and three tuples exist where id=1.

David J.

#18David Rowley
dgrowleyml@gmail.com
In reply to: Chao Li (#15)
Re: Fix missing EvalPlanQual recheck for TID scans

On Mon, 15 Sept 2025 at 17:32, Chao Li <li.evan.chao@gmail.com> wrote:

UPDATE, DELETE, SELECT FOR UPDATE, and SELECT FOR SHARE commands behave the same as SELECT in terms of searching for target rows: they will only find target rows that were committed as of the command start time.

It says that UPDATE will only find target rows that were committed as of the command start time. I think the statement implies that an “update” statement will never update a “future” tuple.

I think you've only read the first sentence in that paragraph. Please
read the entire paragraph. You'll see it goes on to explain "it will
attempt to apply its operation to the updated version of the row".

David

#19Chao Li
li.evan.chao@gmail.com
In reply to: David Rowley (#18)
Re: Fix missing EvalPlanQual recheck for TID scans

On Sep 15, 2025, at 14:27, David Rowley <dgrowleyml@gmail.com> wrote:

I think you've only read the first sentence in that paragraph. Please
read the entire paragraph. You'll see it goes on to explain "it will
attempt to apply its operation to the updated version of the row".

Ah… Sorry for missing the part of the paragraph. Now it’s clear to me.

Then the solution of TidListEval() is correct, and the only issue is repeatedly calling TidListEval() on every recheck.

Best regards,
--
Chao Li (Evan)
HighGo Software Co., Ltd.
https://www.highgo.com/

#20Chao Li
li.evan.chao@gmail.com
In reply to: Chao Li (#19)
Re: Fix missing EvalPlanQual recheck for TID scans

On Sep 15, 2025, at 16:12, Chao Li <li.evan.chao@gmail.com> wrote:

Then the solution of TidListEval() is correct, and the only issue is repeatedly calling TidListEval() on every recheck.

I want to add that, the issue of repeatedly calling TidListEval() is not a problem of this patch. I am okay if you decide to defer the problem to a separate patch.

Best regards,
--
Chao Li (Evan)
HighGo Software Co., Ltd.
https://www.highgo.com/

#21David Rowley
dgrowleyml@gmail.com
In reply to: Sophie Alpert (#5)
2 attachment(s)
Re: Fix missing EvalPlanQual recheck for TID scans

On Tue, 9 Sept 2025 at 04:36, Sophie Alpert <pg@sophiebits.com> wrote:

I've added a new trss_boundsInitialized flag such that we calculate the range once per EPQ rescan. In order to preserve the semantics when the min or max is NULL, I'm setting trss_mintid/trss_maxtid to have invalid ItemPointers as a sentinel in the cases where TidRangeEval returns false. I added a ItemPointerIsValid assertion given that it's now more relevant to correctness but I can remove it if it feels superfluous. Let me know if there is a more idiomatic way to treat this.

This part seems a bit pointless as EPQ queries will only return 1 row
anyway (Check EvalPlanQual() where it calls EvalPlanQualNext()). There
will be a rescan, which will wipe out the range before the recheck
function is ever called again.

I think if we want to do better at not continuously recalculating the
TIDList or range, then something more generic might be better. If the
planner were to note down which ParamIds exist in the TID exprs, we
could just mark that the TID List / Range needs to be recalculated
whenever one of those parameters changes. That should help in non-EPQ
cases too.

For the v2 patch, I've hacked on that a bit and stripped out the
trss_boundsInitialized stuff and just make it so we recalculate the
TID List/Range on every recheck. I also added another isolation test
permutation to have s1 rollback and ensure that s2 updates the ctid =
'(0,1)' tuple.

The attached v3-0001 is the updated v2 patch, and v3-0002 is a POC of
what I described above. Seems there is something to it as the
performance is better. It is a very contrived test case, however.

create table empty(a int);
create table million (a int);
insert into million select generate_series(1,1000000);

set max_parallel_Workers_per_gather=0;
set enable_seqscan=0;
set enable_material=0;
set jit=0;
select sum(c) from million m left join lateral (select count(*) c from
empty where ctid in
('(1,1)','(1,2)','(1,3)','(1,4)','(1,5)','(1,6)','(1,7)','(1,8)','(1,9)','(1,10)','(1,11)','(1,12)','(1,13)','(1,14)','(1,15)','(1,16)','(1,17)','(1,18)','(1,19)','(1,20)','(1,21)','(1,22)','(1,23)','(1,24)','(1,25)','(1,26)','(1,27)','(1,28)','(1,29)','(1,30)','(1,31)','(1,32)','(1,33)','(1,34)','(1,35)','(1,36)','(1,37)','(1,38)','(1,39)','(1,40)','(1,41)','(1,42)','(1,43)','(1,44)','(1,45)','(1,46)','(1,47)','(1,48)','(1,49)','(1,50)','(1,51)','(1,52)','(1,53)','(1,54)','(1,55)','(1,56)','(1,57)','(1,58)','(1,59)','(1,60)','(1,61)','(1,62)','(1,63)','(1,64)','(1,65)','(1,66)','(1,67)','(1,68)','(1,69)','(1,70)','(1,71)','(1,72)','(1,73)','(1,74)','(1,75)','(1,76)','(1,77)','(1,78)','(1,79)','(1,80)','(1,81)','(1,82)','(1,83)','(1,84)','(1,85)','(1,86)','(1,87)','(1,88)','(1,89)','(1,90)','(1,91)','(1,92)','(1,93)','(1,94)','(1,95)','(1,96)','(1,97)','(1,98)','(1,99)','(1,100)'))
on 1=1;

master:

Time: 613.541 ms
Time: 621.037 ms
Time: 623.430 ms

master + v3-0002:

Time: 298.863 ms
Time: 298.015 ms
Time: 297.172 ms

Overall, I'm keen to get moving fixing the initial reported problem.
Maybe the 0002 part can be done in master or not at all. 0002 modifies
the TidScan and TidRangeScan, which we can't really do in the back
branches anyway.

David

Attachments:

v3-0001-Fix-missing-EvalPlanQual-recheck-for-TID-scans.patchapplication/octet-stream; name=v3-0001-Fix-missing-EvalPlanQual-recheck-for-TID-scans.patchDownload
From 24af23003f1f77b560d301d5cbdcc7961527f683 Mon Sep 17 00:00:00 2001
From: Sophie Alpert <git@sophiebits.com>
Date: Sat, 6 Sep 2025 00:30:34 -0700
Subject: [PATCH v3 1/2] Fix missing EvalPlanQual recheck for TID scans

---
 src/backend/executor/nodeTidrangescan.c       | 10 ++
 src/backend/executor/nodeTidscan.c            | 19 +++-
 .../isolation/expected/eval-plan-qual.out     | 94 +++++++++++++++++++
 src/test/isolation/specs/eval-plan-qual.spec  | 14 +++
 4 files changed, 133 insertions(+), 4 deletions(-)

diff --git a/src/backend/executor/nodeTidrangescan.c b/src/backend/executor/nodeTidrangescan.c
index 26f7420b64b..1bce8d6cbfe 100644
--- a/src/backend/executor/nodeTidrangescan.c
+++ b/src/backend/executor/nodeTidrangescan.c
@@ -274,6 +274,16 @@ TidRangeNext(TidRangeScanState *node)
 static bool
 TidRangeRecheck(TidRangeScanState *node, TupleTableSlot *slot)
 {
+	if (!TidRangeEval(node))
+		return false;
+
+	Assert(ItemPointerIsValid(&slot->tts_tid));
+
+	/* Recheck the ctid is still within range */
+	if (ItemPointerCompare(&slot->tts_tid, &node->trss_mintid) < 0 ||
+		ItemPointerCompare(&slot->tts_tid, &node->trss_maxtid) > 0)
+		return false;
+
 	return true;
 }
 
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..3d31d0f84e5 100644
--- a/src/test/isolation/expected/eval-plan-qual.out
+++ b/src/test/isolation/expected/eval-plan-qual.out
@@ -1218,6 +1218,100 @@ 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: tidrange1 tidrange2 c1 c2 read
+step tidrange1: UPDATE accounts SET balance = balance + 100 WHERE ctid BETWEEN '(0,1)' AND '(0,1)' RETURNING accountid, balance;
+accountid|balance
+---------+-------
+checking |    700
+(1 row)
+
+step tidrange2: UPDATE accounts SET balance = balance + 200 WHERE ctid BETWEEN '(0,1)' AND '(0,1)' RETURNING accountid, balance; <waiting ...>
+step c1: COMMIT;
+step tidrange2: <... 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 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..c6eee685586 100644
--- a/src/test/isolation/specs/eval-plan-qual.spec
+++ b/src/test/isolation/specs/eval-plan-qual.spec
@@ -99,6 +99,10 @@ step upsert1	{
 	  WHERE NOT EXISTS (SELECT 1 FROM upsert);
 }
 
+# Tests for Tid / Tid Range Scan
+step tid1 { UPDATE accounts SET balance = balance + 100 WHERE ctid = '(0,1)' RETURNING accountid, balance; }
+step tidrange1 { UPDATE accounts SET balance = balance + 100 WHERE ctid BETWEEN '(0,1)' AND '(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 +245,11 @@ 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; }
+step tidrange2 { UPDATE accounts SET balance = balance + 200 WHERE ctid BETWEEN '(0,1)' AND '(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 +401,11 @@ 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
+permutation tidrange1 tidrange2 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
-- 
2.43.0

v3-0002-Reduce-rescan-overheads-in-TID-Range-Scan.patchapplication/octet-stream; name=v3-0002-Reduce-rescan-overheads-in-TID-Range-Scan.patchDownload
From aa53366a3fe4257cf73b096b53875fb95addf813 Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Mon, 15 Sep 2025 21:59:36 +1200
Subject: [PATCH v3 2/2] Reduce rescan overheads in TID [Range] Scan

Until how the TIDs to scan have been recalculated after every rescan of
both TID Scan and TID Range Scan.  Here we adjust things so that the
calculated list of TIDs or calculated range of TIDs is only marked as
needing recalculated whenever a parameter has changed that might require
a recalculation.
---
 src/backend/executor/nodeTidrangescan.c | 59 ++++++++++++++++++-------
 src/backend/executor/nodeTidscan.c      | 17 +++++--
 src/backend/optimizer/plan/createplan.c | 25 ++++++++---
 src/include/nodes/execnodes.h           |  4 ++
 src/include/nodes/plannodes.h           |  4 ++
 5 files changed, 84 insertions(+), 25 deletions(-)

diff --git a/src/backend/executor/nodeTidrangescan.c b/src/backend/executor/nodeTidrangescan.c
index 1bce8d6cbfe..39239c6692b 100644
--- a/src/backend/executor/nodeTidrangescan.c
+++ b/src/backend/executor/nodeTidrangescan.c
@@ -128,14 +128,17 @@ TidExprListCreate(TidRangeScanState *tidrangestate)
  *		TidRangeEval
  *
  *		Compute and set node's block and offset range to scan by evaluating
- *		node->trss_tidexprs.  Returns false if we detect the range cannot
- *		contain any tuples.  Returns true if it's possible for the range to
- *		contain tuples.  We don't bother validating that trss_mintid is less
- *		than or equal to trss_maxtid, as the scan_set_tidrange() table AM
- *		function will handle that.
+ *		node->trss_tidexprs.  Sets node's trss_rangeIsEmpty to true if the
+ *		calculated range must be empty of any tuples, otherwise sets
+ *		trss_rangeIsEmpty to false and sets trss_mintid and trss_maxtid to the
+ *		calculated range.
+ *
+ *		We don't bother validating that trss_mintid is less than or equal to
+ *		trss_maxtid, as the scan_set_tidrange() table AM function will handle
+ *		that.
  * ----------------------------------------------------------------
  */
-static bool
+static void
 TidRangeEval(TidRangeScanState *node)
 {
 	ExprContext *econtext = node->ss.ps.ps_ExprContext;
@@ -165,7 +168,10 @@ TidRangeEval(TidRangeScanState *node)
 
 		/* If the bound is NULL, *nothing* matches the qual. */
 		if (isNull)
-			return false;
+		{
+			node->trss_rangeIsEmpty = true;
+			return;
+		}
 
 		if (tidopexpr->exprtype == TIDEXPR_LOWER_BOUND)
 		{
@@ -207,7 +213,7 @@ TidRangeEval(TidRangeScanState *node)
 	ItemPointerCopy(&lowerBound, &node->trss_mintid);
 	ItemPointerCopy(&upperBound, &node->trss_maxtid);
 
-	return true;
+	node->trss_rangeIsEmpty = false;
 }
 
 /* ----------------------------------------------------------------
@@ -234,12 +240,19 @@ TidRangeNext(TidRangeScanState *node)
 	slot = node->ss.ss_ScanTupleSlot;
 	direction = estate->es_direction;
 
-	if (!node->trss_inScan)
+	/* First time through, compute TID range to scan */
+	if (!node->trss_rangeCalcDone)
 	{
-		/* First time through, compute TID range to scan */
-		if (!TidRangeEval(node))
-			return NULL;
+		TidRangeEval(node);
+		node->trss_rangeCalcDone = true;
+	}
+
+	/* Check if the range was detected not to contain any tuples */
+	if (node->trss_rangeIsEmpty)
+		return NULL;
 
+	if (!node->trss_inScan)
+	{
 		if (scandesc == NULL)
 		{
 			scandesc = table_beginscan_tidrange(node->ss.ss_currentRelation,
@@ -274,13 +287,18 @@ TidRangeNext(TidRangeScanState *node)
 static bool
 TidRangeRecheck(TidRangeScanState *node, TupleTableSlot *slot)
 {
-	if (!TidRangeEval(node))
-		return false;
+	/* First call? Compute the TID Range */
+	if (!node->trss_rangeCalcDone)
+	{
+		TidRangeEval(node);
+		node->trss_rangeCalcDone = true;
+	}
 
 	Assert(ItemPointerIsValid(&slot->tts_tid));
 
 	/* Recheck the ctid is still within range */
-	if (ItemPointerCompare(&slot->tts_tid, &node->trss_mintid) < 0 ||
+	if (node->trss_rangeIsEmpty ||
+		ItemPointerCompare(&slot->tts_tid, &node->trss_mintid) < 0 ||
 		ItemPointerCompare(&slot->tts_tid, &node->trss_maxtid) > 0)
 		return false;
 
@@ -322,6 +340,13 @@ ExecReScanTidRangeScan(TidRangeScanState *node)
 	/* mark scan as not in progress, and tid range list as not computed yet */
 	node->trss_inScan = false;
 
+	/*
+	 * Set the Tid Range to be recalculated when any parameters that might
+	 * effect the calculated range have changed.
+	 */
+	if (bms_overlap(node->ss.ps.chgParam, ((TidRangeScan *) node->ss.ps.plan)->tidparamids))
+		node->trss_rangeCalcDone = false;
+
 	/*
 	 * We must wait until TidRangeNext before calling table_rescan_tidrange.
 	 */
@@ -380,6 +405,10 @@ ExecInitTidRangeScan(TidRangeScan *node, EState *estate, int eflags)
 	 * mark scan as not in progress, and TID range as not computed yet
 	 */
 	tidrangestate->trss_inScan = false;
+	tidrangestate->trss_rangeCalcDone = false;
+
+	/* This will be calculated correctly in TidRangeEval() */
+	tidrangestate->trss_rangeIsEmpty = true;
 
 	/*
 	 * open the scan relation
diff --git a/src/backend/executor/nodeTidscan.c b/src/backend/executor/nodeTidscan.c
index d50c6600358..b40a31e0d2f 100644
--- a/src/backend/executor/nodeTidscan.c
+++ b/src/backend/executor/nodeTidscan.c
@@ -457,10 +457,19 @@ ExecTidScan(PlanState *pstate)
 void
 ExecReScanTidScan(TidScanState *node)
 {
-	if (node->tss_TidList)
-		pfree(node->tss_TidList);
-	node->tss_TidList = NULL;
-	node->tss_NumTids = 0;
+	/*
+	 * Set the TidList to be recalculated when any parameters that might
+	 * effect the computed list has changed.
+	 */
+	if (bms_overlap(node->ss.ps.chgParam,
+					 ((TidScan *) node->ss.ps.plan)->tidparamids))
+	{
+		if (node->tss_TidList)
+			pfree(node->tss_TidList);
+		node->tss_TidList = NULL;
+		node->tss_NumTids = 0;
+	}
+
 	node->tss_TidPtr = -1;
 
 	/* not really necessary, but seems good form */
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 6791cbeb416..87e2597ee8c 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -201,9 +201,10 @@ static BitmapHeapScan *make_bitmap_heapscan(List *qptlist,
 											List *bitmapqualorig,
 											Index scanrelid);
 static TidScan *make_tidscan(List *qptlist, List *qpqual, Index scanrelid,
-							 List *tidquals);
+							 List *tidquals, Bitmapset *paramids);
 static TidRangeScan *make_tidrangescan(List *qptlist, List *qpqual,
-									   Index scanrelid, List *tidrangequals);
+									   Index scanrelid, List *tidrangequals,
+									   Bitmapset *paramids);
 static SubqueryScan *make_subqueryscan(List *qptlist,
 									   List *qpqual,
 									   Index scanrelid,
@@ -3384,6 +3385,7 @@ create_tidscan_plan(PlannerInfo *root, TidPath *best_path,
 	TidScan    *scan_plan;
 	Index		scan_relid = best_path->path.parent->relid;
 	List	   *tidquals = best_path->tidquals;
+	Bitmapset  *paramids;
 
 	/* it should be a base rel... */
 	Assert(scan_relid > 0);
@@ -3459,10 +3461,13 @@ create_tidscan_plan(PlannerInfo *root, TidPath *best_path,
 			replace_nestloop_params(root, (Node *) scan_clauses);
 	}
 
+	paramids = pull_paramids((Expr *) tidquals);
+
 	scan_plan = make_tidscan(tlist,
 							 scan_clauses,
 							 scan_relid,
-							 tidquals);
+							 tidquals,
+							 paramids);
 
 	copy_generic_path_info(&scan_plan->scan.plan, &best_path->path);
 
@@ -3481,6 +3486,7 @@ create_tidrangescan_plan(PlannerInfo *root, TidRangePath *best_path,
 	TidRangeScan *scan_plan;
 	Index		scan_relid = best_path->path.parent->relid;
 	List	   *tidrangequals = best_path->tidrangequals;
+	Bitmapset  *paramids;
 
 	/* it should be a base rel... */
 	Assert(scan_relid > 0);
@@ -3524,10 +3530,13 @@ create_tidrangescan_plan(PlannerInfo *root, TidRangePath *best_path,
 			replace_nestloop_params(root, (Node *) scan_clauses);
 	}
 
+	paramids = pull_paramids((Expr *) tidrangequals);
+
 	scan_plan = make_tidrangescan(tlist,
 								  scan_clauses,
 								  scan_relid,
-								  tidrangequals);
+								  tidrangequals,
+								  paramids);
 
 	copy_generic_path_info(&scan_plan->scan.plan, &best_path->path);
 
@@ -5622,7 +5631,8 @@ static TidScan *
 make_tidscan(List *qptlist,
 			 List *qpqual,
 			 Index scanrelid,
-			 List *tidquals)
+			 List *tidquals,
+			 Bitmapset *paramids)
 {
 	TidScan    *node = makeNode(TidScan);
 	Plan	   *plan = &node->scan.plan;
@@ -5633,6 +5643,7 @@ make_tidscan(List *qptlist,
 	plan->righttree = NULL;
 	node->scan.scanrelid = scanrelid;
 	node->tidquals = tidquals;
+	node->tidparamids = paramids;
 
 	return node;
 }
@@ -5641,7 +5652,8 @@ static TidRangeScan *
 make_tidrangescan(List *qptlist,
 				  List *qpqual,
 				  Index scanrelid,
-				  List *tidrangequals)
+				  List *tidrangequals,
+				  Bitmapset *paramids)
 {
 	TidRangeScan *node = makeNode(TidRangeScan);
 	Plan	   *plan = &node->scan.plan;
@@ -5652,6 +5664,7 @@ make_tidrangescan(List *qptlist,
 	plan->righttree = NULL;
 	node->scan.scanrelid = scanrelid;
 	node->tidrangequals = tidrangequals;
+	node->tidparamids = paramids;
 
 	return node;
 }
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 71857feae48..e625d04363e 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -1926,6 +1926,8 @@ typedef struct TidScanState
  *		trss_mintid			the lowest TID in the scan range
  *		trss_maxtid			the highest TID in the scan range
  *		trss_inScan			is a scan currently in progress?
+ *		trss_rangeCalcDone	has the TID range been calculated yet?
+ *		trss_rangeIsEmpty	true if the TID range is certainly empty
  * ----------------
  */
 typedef struct TidRangeScanState
@@ -1935,6 +1937,8 @@ typedef struct TidRangeScanState
 	ItemPointerData trss_mintid;
 	ItemPointerData trss_maxtid;
 	bool		trss_inScan;
+	bool		trss_rangeCalcDone;
+	bool		trss_rangeIsEmpty;
 } TidRangeScanState;
 
 /* ----------------
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
index 29d7732d6a0..a3d220e9d5e 100644
--- a/src/include/nodes/plannodes.h
+++ b/src/include/nodes/plannodes.h
@@ -677,6 +677,8 @@ typedef struct TidScan
 	Scan		scan;
 	/* qual(s) involving CTID = something */
 	List	   *tidquals;
+	/* Set of ParamIds mentioned in tidquals */
+	Bitmapset  *tidparamids;
 } TidScan;
 
 /* ----------------
@@ -691,6 +693,8 @@ typedef struct TidRangeScan
 	Scan		scan;
 	/* qual(s) involving CTID op something */
 	List	   *tidrangequals;
+	/* Set of ParamIds mentioned in tidrangequals */
+	Bitmapset *tidparamids;
 } TidRangeScan;
 
 /* ----------------
-- 
2.43.0

#22Sophie Alpert
pg@sophiebits.com
In reply to: David Rowley (#21)
Re: Fix missing EvalPlanQual recheck for TID scans

On Mon, Sep 15, 2025 at 4:23 AM, David Rowley <dgrowleyml@gmail.com> wrote:

For the v2 patch, I've hacked on that a bit and stripped out the
trss_boundsInitialized stuff and just make it so we recalculate the
TID List/Range on every recheck. I also added another isolation test
permutation to have s1 rollback and ensure that s2 updates the ctid =
'(0,1)' tuple.

Thanks, this seems sensible given the reality that rescan happens once per tuple. The `if (node->tss_TidList == NULL)` check you kept from me seems likewise pointless in v3-0001 but not particularly intrusive (though of course you use it in v3-0002).

Otherwise v3-0001 lgtm. (I also took a look at v3-0002 and don't see any immediate issues, though neither would I really consider myself qualified to review it.)

Sophie

#23Chao Li
li.evan.chao@gmail.com
In reply to: David Rowley (#21)
Re: Fix missing EvalPlanQual recheck for TID scans

On Sep 15, 2025, at 19:23, David Rowley <dgrowleyml@gmail.com> wrote:

The attached v3-0001 is the updated v2 patch, and v3-0002 is a POC of
what I described above. Seems there is something to it as the
performance is better. It is a very contrived test case, however.

create table empty(a int);
create table million (a int);
insert into million select generate_series(1,1000000);

set max_parallel_Workers_per_gather=0;
set enable_seqscan=0;
set enable_material=0;
set jit=0;
select sum(c) from million m left join lateral (select count(*) c from
empty where ctid in
('(1,1)','(1,2)','(1,3)','(1,4)','(1,5)','(1,6)','(1,7)','(1,8)','(1,9)','(1,10)','(1,11)','(1,12)','(1,13)','(1,14)','(1,15)','(1,16)','(1,17)','(1,18)','(1,19)','(1,20)','(1,21)','(1,22)','(1,23)','(1,24)','(1,25)','(1,26)','(1,27)','(1,28)','(1,29)','(1,30)','(1,31)','(1,32)','(1,33)','(1,34)','(1,35)','(1,36)','(1,37)','(1,38)','(1,39)','(1,40)','(1,41)','(1,42)','(1,43)','(1,44)','(1,45)','(1,46)','(1,47)','(1,48)','(1,49)','(1,50)','(1,51)','(1,52)','(1,53)','(1,54)','(1,55)','(1,56)','(1,57)','(1,58)','(1,59)','(1,60)','(1,61)','(1,62)','(1,63)','(1,64)','(1,65)','(1,66)','(1,67)','(1,68)','(1,69)','(1,70)','(1,71)','(1,72)','(1,73)','(1,74)','(1,75)','(1,76)','(1,77)','(1,78)','(1,79)','(1,80)','(1,81)','(1,82)','(1,83)','(1,84)','(1,85)','(1,86)','(1,87)','(1,88)','(1,89)','(1,90)','(1,91)','(1,92)','(1,93)','(1,94)','(1,95)','(1,96)','(1,97)','(1,98)','(1,99)','(1,100)'))
on 1=1;

I just tested v3.

V3-0002 looks a nice solution. Now when the first time TidRecheck() is called, “node” is a brand-new one, next time “node” is from the previous recheck, thus it doesn’t need to recalculate TidList.

The change also helps the rescan situation by avoiding deleting tss_TidList.

So, overall v3 looks good to me.

Best regards,
--
Chao Li (Evan)
HighGo Software Co., Ltd.
https://www.highgo.com/

#24David Rowley
dgrowleyml@gmail.com
In reply to: Sophie Alpert (#22)
Re: Fix missing EvalPlanQual recheck for TID scans

On Tue, 16 Sept 2025 at 05:42, Sophie Alpert <pg@sophiebits.com> wrote:

Thanks, this seems sensible given the reality that rescan happens once per tuple. The `if (node->tss_TidList == NULL)` check you kept from me seems likewise pointless in v3-0001 but not particularly intrusive (though of course you use it in v3-0002).

That was a defensive coding choice. It could have been an
Assert(node->tss_TidList == NULL);, but I just prefer it as an "if".

Otherwise v3-0001 lgtm. (I also took a look at v3-0002 and don't see any immediate issues, though neither would I really consider myself qualified to review it.)

Thanks for looking, and for the report and patches. I've pushed and
backpatched the fixes. v13 doesn't have TID Range Scans, so I opted
to break the fix into 2 parts and apply to the relevant branches to
try and keep the commit messages as accurate as possible.

David