Write skew observed under serializable isolation

Started by Jacob Brazeal4 months ago14 messageshackers
Jump to latest
#1Jacob Brazeal
jacob.brazeal@gmail.com

Hi hackers,

I found that a query using a Tid Range Scan can allow write skew under
`SERIALIZABLE`.

Setup:

CREATE TABLE trs (id int, v int);
INSERT INTO trs VALUES (1, 0), (2, 0);

Then run the following in two sessions, interleaved as shown.

Session 1:

BEGIN ISOLATION LEVEL SERIALIZABLE;
SET enable_seqscan = off;
SELECT sum(v) FROM trs WHERE ctid >= '(0,0)' AND ctid <= '(0,100)';
-- 0 -- implies session 2 has not committed yet

Session 2:

BEGIN ISOLATION LEVEL SERIALIZABLE;
SET enable_seqscan = off;
SELECT sum(v) FROM trs WHERE ctid >= '(0,0)' AND ctid <= '(0,100)';
-- 0 -- implies session 1 has not committed yet

EXPLAIN shows a Tid Range Scan for both reads. Now:

-- session 1
UPDATE trs SET v = 1 WHERE ctid = '(0,1)';

-- session 2
UPDATE trs SET v = 1 WHERE ctid = '(0,2)';

-- session 1
COMMIT;

-- session 2
COMMIT; -- succeeds

Both transactions commit, and the final sum is 2:
SELECT sum(v) FROM trs;
-- 2

This result is not possible in any serial order: since both transactions
read the full range, whichever transaction ran second would have observed a
sum of 1 in its initial select instead of 0.

As a control, the same schedule using a sequential scan causes the second
commit to fail with:

ERROR: could not serialize access due to read/write dependencies among
transactions

(To run with seqscan, make sure to first do both SET enable_tidscan = off
and SET enable_seqscan = on.)

I reproduced this on current master. Tid Range Scans were introduced in
PostgreSQL 14, and the behavior appears present in all branches since then.

Best,
Jacob Brazeal

#2Jacob Brazeal
jacob.brazeal@gmail.com
In reply to: Jacob Brazeal (#1)
Re: Write skew observed under serializable isolation

A candidate patch to fix is attached.

Attachments:

t253201_2
serializable-silently-accepts-write-skew-tid-range-scan-take-v1.patchapplication/octet-stream; name=serializable-silently-accepts-write-skew-tid-range-scan-take-v1.patchDownload+180-13
#3Jacob Brazeal
jacob.brazeal@gmail.com
In reply to: Jacob Brazeal (#2)
Re: Write skew observed under serializable isolation

Let me give a similar example that also makes the final sum query incorrect
under serializable isolation.

Same setup:

CREATE TABLE trs (id int, v int);
INSERT INTO trs VALUES (1, 0), (2, 0);

Session 1:

BEGIN ISOLATION LEVEL SERIALIZABLE;
SET enable_seqscan = off;
SELECT sum(v) FROM trs WHERE ctid >= '(0,0)' AND ctid <= '(0,100)';
-- 0

Session 2:

BEGIN ISOLATION LEVEL SERIALIZABLE;
SET enable_seqscan = off;
SELECT sum(v) FROM trs WHERE ctid >= '(0,0)' AND ctid <= '(0,100)';
-- 0

-- session 1
UPDATE trs SET v = 1 + (SELECT sum(v) FROM trs
WHERE ctid >= '(0,0)' AND ctid <= '(0,100)')
WHERE ctid = '(0,1)';

-- session 2
UPDATE trs SET v = 1 + (SELECT sum(v) FROM trs
WHERE ctid >= '(0,0)' AND ctid <= '(0,100)')
WHERE ctid = '(0,2)';

-- session 1
COMMIT;

-- session 2
COMMIT; -- succeeds

Both transactions commit, and the final sum is 2:

SELECT sum(v) FROM trs;
-- 2

Neither serial order produces 2; both produce 3. The serial run is shown at
the end of this mail.

The range read is a Tid Range Scan standalone and as the InitPlan of the
UPDATE:

Update on trs
InitPlan expr_1
-> Aggregate
-> Tid Range Scan on trs trs_1
TID Cond: ((ctid >= '(0,0)'::tid) AND (ctid <=
'(0,100)'::tid))
-> Tid Scan on trs
TID Cond: (ctid = '(0,1)'::tid)

As a control, force the same reads through a sequential scan by setting

SET enable_tidscan = off;

in both sessions instead of enable_seqscan. (Note that merely leaving
enable_seqscan on is not enough: the planner still prefers a Tid Range Scan
for this qual, so a control written that way is not a control.) The
identical
schedule then fails at the second commit with

ERROR: could not serialize access due to read/write dependencies among
transactions

and leaves sum = 1. A Tid Scan control aborts correctly as well, since
heap_fetch() takes PredicateLockTID on each visible tuple it returns.

The cause appears to be the scan-type test in heap_beginscan(), in
src/backend/access/heap/heapam.c:

if (scan->rs_base.rs_flags & (SO_TYPE_SEQSCAN | SO_TYPE_SAMPLESCAN))
{
Assert(snapshot);
PredicateLockRelation(relation, snapshot);
}

SO_TYPE_TIDRANGESCAN is not in the list, so a TID range scan takes no SIREAD
lock at all. The comment just above already describes the rule that covers
this case -- "in a heap scan there is nothing more fine-grained to lock" --
and a TID range scan is a heap scan with no index involved. The conflict-out
edge is still recorded by heap_prepare_pagescan(); what is missing is the
conflict-in edge, so a later writer's CheckForSerializableConflictIn() finds
no read to conflict with and no cycle can be detected.

As mentioned previously, I reproduced this on current master. Tid Range
Scans were introduced in
PostgreSQL 14, the test above is unchanged on master, and the behavior
appears
present in all branches since then.

Finally, for reference, here are the same statements run serially --
session 1
start to finish, then session 2 -- which is what a serializable execution is
required to be equivalent to. Starting again from the setup above:

-- session 1
BEGIN ISOLATION LEVEL SERIALIZABLE;
SET enable_seqscan = off;
SELECT sum(v) FROM trs WHERE ctid >= '(0,0)' AND ctid <= '(0,100)';
-- 0
UPDATE trs SET v = 1 + (SELECT sum(v) FROM trs
WHERE ctid >= '(0,0)' AND ctid <= '(0,100)')
WHERE ctid = '(0,1)';
COMMIT;

-- session 2
BEGIN ISOLATION LEVEL SERIALIZABLE;
SET enable_seqscan = off;
SELECT sum(v) FROM trs WHERE ctid >= '(0,0)' AND ctid <= '(0,100)';
-- 1 <-- sees session 1's write, so it stores 2 rather than 1
UPDATE trs SET v = 1 + (SELECT sum(v) FROM trs
WHERE ctid >= '(0,0)' AND ctid <= '(0,100)')
WHERE ctid = '(0,2)';
COMMIT;

SELECT sum(v) FROM trs;
-- 3

Running session 2 first gives 3 as well, by symmetry. The interleaved result
of 2 is therefore not equivalent to any serial order.

Best,
Jacob Brazeal

On Sun, Jul 26, 2026 at 11:05 PM Jacob Brazeal <jacob.brazeal@gmail.com>
wrote:

Show quoted text

A candidate patch to fix is attached.

#4Matthias van de Meent
boekewurm+postgres@gmail.com
In reply to: Jacob Brazeal (#2)
Re: Write skew observed under serializable isolation

On Mon, 27 Jul 2026 at 07:58, Jacob Brazeal <jacob.brazeal@gmail.com> wrote:

Hi hackers,

I found that a query using a Tid Range Scan can allow write skew under `SERIALIZABLE`.

Good find!

On Mon, 27 Jul 2026 at 08:05, Jacob Brazeal <jacob.brazeal@gmail.com> wrote:

A candidate patch to fix is attached.

I think this patch is taking locks too aggressively; we shouldn't take
a predlock on the whole relation when we're only looking at a small
portion of the table using TID ranges. I think the more appropriate
place to add the predicate locks is in heap_set_tidrange(), and have
Assert(PageIsPredicateLocked(...)) for the returned TID in
heap_getnextslot_tidrange() to make sure we don't regress.

Kind regards,

Matthias van de Meent.

#5Jacob Brazeal
jacob.brazeal@gmail.com
In reply to: Matthias van de Meent (#4)
Re: Write skew observed under serializable isolation

[cc'ing hackers this time, oops!]

Hi Matthias,

Thanks for looking at this.

I think this patch is taking locks too aggressively; we shouldn't take
a predlock on the whole relation when we're only looking at a small
portion of the table using TID ranges. I think the more appropriate
place to add the predicate locks is in heap_set_tidrange(), and have
Assert(PageIsPredicateLocked(...)) for the returned TID in
heap_getnextslot_tidrange() to make sure we don't regress.

I tried the page-level approach, but I don't think heap page locks are
sufficient here. heap_insert() checks only for relation-level predicate
locks; heap page locks are treated as consolidated tuple locks and do not
cover gaps. Thus an insert can land within the scanned TID range, even on a
page covered by a page lock, without conflicting with the reader.

There is also a problem for ranges extending beyond the current end of the
relation. heap_set_tidrange() limits the scan using the relation's current
size, so it cannot lock pages subsequently added by an insert even when
those pages fall within the requested TID range.

The proposed assertion in heap_getnextslot_tidrange() also does not appear
safe after predicate-lock promotion. PageIsPredicateLocked() intentionally
checks only for a page-level lock, not a covering relation-level lock,
while acquiring enough page locks can promote them to a relation lock.

It seems that using page locks here would require some additional notion of
heap gap locking, or corresponding changes to the insert conflict checks.
With the existing predicate-locking scheme, I think the relation lock is
needed to cover inserts as well as updates.

Best,

Jacob

#6Aleksander Alekseev
aleksander@tigerdata.com
In reply to: Jacob Brazeal (#5)
Re: Write skew observed under serializable isolation

Hi Jacob,

Thanks for the bug report and the fix.

[...]

It seems that using page locks here would require some additional notion of heap gap locking, or corresponding changes to the insert conflict checks. With the existing predicate-locking scheme, I think the relation lock is needed to cover inserts as well as updates.

Yes it looks like an architecturally correct approach with minimum
overall overhead. In any case anyone who wants to implement an
optimization can submit it as a separate patch.

My only nitpick is that the patch doesn't update README-SSI. The
corrected patch is attached. Also I added a proper commit message.

I believe the patch is Ready for Committer.

--
Best regards,
Aleksander Alekseev

Attachments:

t253201_6
v2-0001-Fix-write-skew-under-SERIALIZABLE-for-Tid-Range-S.patchtext/x-patch; charset=US-ASCII; name=v2-0001-Fix-write-skew-under-SERIALIZABLE-for-Tid-Range-S.patchDownload+186-14
#7Andrey Borodin
amborodin@acm.org
In reply to: Aleksander Alekseev (#6)
Re: Write skew observed under serializable isolation

The locking change looks correct to me.

On 21 Sep 2026, Aleksander Alekseev wrote:

+# other one read. No serial order produces sum(p) = 2, ...

The constant assignments in this test produce a final sum of 2 in either
serial order too. The anomaly is that both preceding reads return 0.
Could we correct the comment? The test itself demonstrates the bug.

Maybe we could also cover inserts after scanning an initially empty
table. That would guard against moving lock acquisition into a per-page
path later: there are no existing pages to lock. Without the fix both
transactions commit; with v2 one is aborted.

Thank you!

Best regards, Andrey Borodin.

#8Aleksander Alekseev
aleksander@tigerdata.com
In reply to: Andrey Borodin (#7)
Re: Write skew observed under serializable isolation

Hi Andrey,

Thanks for the great feedback.

+# other one read. No serial order produces sum(p) = 2, ...

The constant assignments in this test produce a final sum of 2 in either
serial order too. The anomaly is that both preceding reads return 0.
Could we correct the comment? The test itself demonstrates the bug.

Good catch. Fixed.

Maybe we could also cover inserts after scanning an initially empty
table. That would guard against moving lock acquisition into a per-page
path later: there are no existing pages to lock. Without the fix both
transactions commit; with v2 one is aborted.

Agree. Added.

--
Best regards,
Aleksander Alekseev

Attachments:

t253201_8
v3-0001-Fix-write-skew-under-SERIALIZABLE-for-Tid-Range-S.patchtext/x-patch; charset=US-ASCII; name=v3-0001-Fix-write-skew-under-SERIALIZABLE-for-Tid-Range-S.patchDownload+245-14
#9Andres Freund
andres@anarazel.de
In reply to: Aleksander Alekseev (#8)
Re: Write skew observed under serializable isolation

Hi,

On 2026-09-21 15:41:54 +0300, Aleksander Alekseev wrote:

+	 * For seqscan, sample and TID range scans in a serializable transaction,
+	 * acquire a predicate lock on the entire relation. This is required not
+	 * only to lock all the matching tuples, but also to conflict with new
+	 * insertions into the table. In an indexscan, we take page locks on the
+	 * index pages covering the range specified in the scan qual, but in a
+	 * heap scan there is nothing more fine-grained to lock. A bitmap scan is
+	 * a different story, there we have already scanned the index and locked
+	 * the index pages covering the predicate. But in that case we still have
+	 * to lock any matching heap tuples. For sample scan we could optimize the
+	 * locking to be at least page-level granularity, but we'd need to add
+	 * per-tuple locking for that.  A TID range scan is like a seqscan in this
+	 * respect: it reads heap blocks directly with no index involved, so there
+	 * is nothing finer to lock, and heap_insert() only checks for conflicts
+	 * against relation-level predicate locks anyway.
+	 */
+	if (scan->rs_base.rs_flags & (SO_TYPE_SEQSCAN | SO_TYPE_SAMPLESCAN |
+								  SO_TYPE_TIDRANGESCAN))
{
/*
* Ensure a missing snapshot is noticed reliably, even if the

Seems like it'd be good to add a note to the SO_TYPE definitions mentioning
that this needs to be updated for additional scans.

I wish we could easily make the SO_TYPE ones an enum, so we could trigger
compiler warnings here by making it an switch() without a default. But it'd
probably be more annoying to change this than it's worth...

Do we have test coverage for the bitmap scan cases?

Greetings,

Andres Freund

#10Aleksander Alekseev
aleksander@tigerdata.com
In reply to: Andres Freund (#9)
Re: Write skew observed under serializable isolation

Hi Andres,

Thanks for the feedback.

Seems like it'd be good to add a note to the SO_TYPE definitions mentioning
that this needs to be updated for additional scans.

Good point. Added.

Do we have test coverage for the bitmap scan cases?

It looks like predicate-lock-hot-tuple.spec sort of covers it but it
is not guaranteed to use bitmap scan and all in all this is a
regression test for another scenario. v4 adds a dedicated test. I
choose not to split the patch into two parts.

--
Best regards,
Aleksander Alekseev

Attachments:

t253201_10
v4-0001-Fix-write-skew-under-SERIALIZABLE-for-TID-range-s.patchtext/x-patch; charset=US-ASCII; name=v4-0001-Fix-write-skew-under-SERIALIZABLE-for-TID-range-s.patchDownload+334-15
#11Zsolt Parragi
zsolt.parragi@percona.com
In reply to: Aleksander Alekseev (#10)
Re: Write skew observed under serializable isolation

Hello!

-	/* one of SO_TYPE_* may be specified */
+	/*
+	 * One of SO_TYPE_* may be specified.  When adding a scan type, check
+	 * whether it must take predicate locks to be safe under SERIALIZABLE: see
+	 * the flag test in heap_beginscan() and "Heap locking" in
+	 * src/backend/storage/lmgr/README-SSI.
+	 */

A wider llm-audit based on this claim pointed out that there's one more preexisting issue: a tid scan that probes a tid holding no tuple takes no predicate lock of any kind, so a concurrent INSERT that materialises a tuple at exactly that TID creates no rw-conflict.

I'm not sure what's the proper solution for this, and if it even should be part of this patch or something separate (as this patch is a clear improvement even with this leftover issue), but it seems to be at least worth a mention in a comment/commit message to state the limitation?

An isolation test reproducing the problem:

setup
{
create table ta (id int);
insert into ta values (1), (2);
create table tb (id int);
insert into tb values (1), (2);
}
teardown { drop table ta; drop table tb; }

session s1
setup { begin isolation level serializable; set enable_seqscan = off; }
step r1 { select count(*) from tb where ctid = '(0,3)'; }
step w1 { insert into ta values (100); }
step c1 { commit; }

session s2
setup { begin isolation level serializable; set enable_seqscan = off; }
step r2 { select count(*) from ta where ctid = '(0,3)'; }
step w2 { insert into tb values (200); }
step c2 { commit; }

permutation r1 r2 w1 w2 c1 c2

#12Aleksander Alekseev
aleksander@tigerdata.com
In reply to: Zsolt Parragi (#11)
Re: Write skew observed under serializable isolation

Hi Zsolt,

An isolation test reproducing the problem:

setup
{
create table ta (id int);
insert into ta values (1), (2);
create table tb (id int);
insert into tb values (1), (2);
}
teardown { drop table ta; drop table tb; }

session s1
setup { begin isolation level serializable; set enable_seqscan = off; }
step r1 { select count(*) from tb where ctid = '(0,3)'; }
step w1 { insert into ta values (100); }
step c1 { commit; }

session s2
setup { begin isolation level serializable; set enable_seqscan = off; }
step r2 { select count(*) from ta where ctid = '(0,3)'; }
step w2 { insert into tb values (200); }
step c2 { commit; }

permutation r1 r2 w1 w2 c1 c2

Great find, thanks for reporting.

Technically this is another bug since it affects Tid Scans, not Tid
Range Scans. This being said I see no reason not to fix it in the
scope of this discussion. The proper fix is to acquire SIREAD on the
relation.

Implemented as a separate patch.

--
Best regards,
Aleksander Alekseev

Attachments:

t253201_12
v5-0001-Fix-write-skew-under-SERIALIZABLE-for-TID-range-s.patchtext/x-patch; charset=US-ASCII; name=v5-0001-Fix-write-skew-under-SERIALIZABLE-for-TID-range-s.patchDownload+334-15
v5-0002-Fix-write-skew-under-SERIALIZABLE-for-TID-scans.patchtext/x-patch; charset=US-ASCII; name=v5-0002-Fix-write-skew-under-SERIALIZABLE-for-TID-scans.patchDownload+100-17
#13Zsolt Parragi
zsolt.parragi@percona.com
In reply to: Aleksander Alekseev (#12)
Re: Write skew observed under serializable isolation

The proper fix is to acquire SIREAD on the relation.

That's a way to fix it, but I am not sure that it is the proper way to do it because it locks way more than needed.

One issue is that now this takes a whole relation lock for UPDATE ... WHERE CURRENT OF, which can cause false-positive abort of cursor loops. I think this part is fixable with an extended condition.

Also after I looked into this a bit more today, cb5b28613d5 in 2020 introduced SO_TYPE_TIDSCAN exactly to prevent full relation locks. Maybe the reasoning of that commit was wrong, and we indeed need whole relation locks there, but it doesn't seem like a trivial decision to me.

#14Aleksander Alekseev
aleksander@tigerdata.com
In reply to: Zsolt Parragi (#13)
Re: Write skew observed under serializable isolation

Hi Zsolt,

That's a way to fix it, but I am not sure that it is the proper way to
do it because it locks way more than needed.

[...]

This looks like the same concern Matthias expressed above.

Let's be mindful of the fact that SIREAD locks despite the name are
not actually locks. Also our SERIALIZABLE implementation allows
false-positives by design [1]https://arxiv.org/abs/1208.4179.

Perhaps there is a smart way of minimizing false positives but
personally I don't instantly see them. Firstly we should fix the
broken feature and optimizations can be discussed as a separate patch.
Users concerned with rollbacks can always choose other isolation
levels.

[1]: https://arxiv.org/abs/1208.4179

--
Best regards,
Aleksander Alekseev