Fix missing EvalPlanQual recheck for TID scans
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)
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
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
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
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)
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/
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
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/
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/
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
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
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��t bKGD � � ����� 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#qZ�����&��-"�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|}}1W<hii�d2���Joo/F�����!��:�5���g3k�,f����i�����/��d2q��I�����-[��k����v�/��?��x���A��#�?����}�_�P�]��L��+
�%G��(C��
���DGGGLLQQQ���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~���MpD s�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��:&��sMrK�'�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��EfXI wWg���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�i6E o���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�r 6�����-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��Q nn���t�J�!Q��R�|\\�@K�p7<�Db'�Tr��X_�� $F�o$�(�
��r���w�B___!O��� ~T��4���8E"q8��"�����x2� ���A����?��!
��@g��pH��S 2e9�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�7 rK���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����nJ�\*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.<