GiST: SERIALIZABLE misses conflict when scan prunes at internal page

From: Michael Malis <malis(at)pgrust(dot)com>
To: pgsql-bugs(at)lists(dot)postgresql(dot)org
Subject: GiST: SERIALIZABLE misses conflict when scan prunes at internal page
Date: 2026-11-16 20:28:12
Message-ID: CANVD+MB+0iJC4dqLk9gse2GPMYnZJYEa1cPy9-VyFxTJBhB6aw@mail.gmail.com
Views: Whole Thread | Raw Message | Download mbox | Resend email
Thread:
Lists: pgsql-bugs

Reproduced on PostgreSQL 18.7 (REL_18_7, commit f5c41f6681c9) and verified
in the source on REL_18_STABLE (commit 2f613719fa4e) and master (commit
7fc2f0423320), where the GiST predicate-locking logic is unchanged.
Concurrent SERIALIZABLE transactions performing an index scan or index-only
scan on a multi-level GiST index can both commit after inserting rows that
match each other's scan predicates. When a GiST scan prunes a child subtree
at an internal index page, the first concurrent insert into that subtree
widens the internal downlink in place, and a subsequent concurrent insert
covered by that widened downlink descends to the leaf page without checking
predicate locks on the internal page. Both phantom insertions and
two-predicate write skew commit without raising SQLSTATE 40001, violating
the SERIALIZABLE guarantee in doc/src/sgml/mvcc.sgml ("Serializable
Isolation Level") that concurrent execution is consistent with some serial
order.

Steps to reproduce (psql -X on a freshly initialized cluster, no extensions
or GUC changes needed):

-- Setup (300 rows split bookings_span_gist_idx into root page 0 + 2 leaves;
-- VACUUM ANALYZE causes default plans to use Index Only Scan):
CREATE TABLE bookings (id int, span int4range);
INSERT INTO bookings
SELECT g, int4range(g * 10, g * 10 + 5)
FROM generate_series(1, 300) AS g;
CREATE INDEX bookings_span_gist_idx ON bookings USING gist (span);
CREATE INDEX bookings_id_btree_idx ON bookings (id);
VACUUM ANALYZE bookings;

-- Failing case (range [5000, 5005) is pruned at internal root page 0):
-- Session 1:
BEGIN ISOLATION LEVEL SERIALIZABLE;
SELECT count(*) FROM bookings WHERE span && '[5000, 5005)'::int4range;
-- count
-- -------
-- 0
-- (1 row)

-- Session 2:
BEGIN ISOLATION LEVEL SERIALIZABLE;
SELECT count(*) FROM bookings WHERE span && '[5000, 5005)'::int4range;
-- count
-- -------
-- 0
-- (1 row)

-- Session 1:
INSERT INTO bookings VALUES (501, '[5000, 5005)');

-- Session 2:
INSERT INTO bookings VALUES (502, '[5000, 5005)');

-- Session 1:
COMMIT;

-- Session 2:
COMMIT;
-- Actual: COMMIT (both transactions commit)
-- Expected:
-- ERROR: could not serialize access due to read/write dependencies among
transactions

SELECT id, span FROM bookings
WHERE span && '[5000, 5005)'::int4range ORDER BY id;
-- id | span
-- -----+-------------
-- 501 | [5000,5005)
-- 502 | [5000,5005)
-- (2 rows)

-- Controls on the same table (both abort Session 2 with SQLSTATE 40001):
-- Control A: B-tree index-only scan on absent id = 5000, or
-- Control B: GiST index-only scan on absent '[15, 20)'::int4range, which
-- overlaps the existing root downlink [10, 1505) and descends to leaf page
1.
-- Session 1:
BEGIN ISOLATION LEVEL SERIALIZABLE;
SELECT count(*) FROM bookings WHERE span && '[15, 20)'::int4range; -- 0

-- Session 2:
BEGIN ISOLATION LEVEL SERIALIZABLE;
SELECT count(*) FROM bookings WHERE span && '[15, 20)'::int4range; -- 0

-- Session 1:
INSERT INTO bookings VALUES (503, '[15, 20)');

-- Session 2:
INSERT INTO bookings VALUES (504, '[15, 20)');

-- Session 1:
COMMIT;

-- Session 2:
COMMIT;
-- ERROR: could not serialize access due to read/write dependencies among
transactions
-- DETAIL: Reason code: Canceled on identification as a pivot, during
commit attempt.
-- HINT: The transaction might succeed if retried.

Attached is gist-serializable-phantom.spec, an equivalent isolationtester
spec covering the B-tree control, the in-bounds GiST leaf control, the
phantom duplicate-range anomaly, and disjoint-range write skew ([4000, 4005)
vs. [5000, 5005)).

Observations from the source:

1. During a GiST scan, gistScanPage() in src/backend/access/gist/gistget.c
calls PredicateLockPage(r, BufferGetBlockNumber(buffer),
scan->xs_snapshot) on each visited page (line 345 on REL_18_STABLE, line
356 on master) and skips queueing child pages whose downlink fails
gistindex_keytest() (line 446 on REL_18_STABLE, line 460 on master).
When neither downlink on internal root page 0 overlaps '[5000, 5005)',
both scans hold an SIReadLock only on page 0 and never lock the child
leaf pages.

2. src/backend/storage/lmgr/README-SSI (lines 385 to 391 on REL_18_STABLE
and master) assumes that locking each visited level suffices because
"An index insert at the leaf level can then be trusted to ripple up to
all levels and locations where conflicting predicate locks may exist."
In src/backend/access/gist/gist.c, however,
CheckForSerializableConflictIn() is called only in gistinserttuples()
(line 1307 on REL_18_STABLE and master), on stack->buffer immediately
before modifying that page.

3. During top-down descent in gistdoinsert() (gist.c lines 744 to 832 on
REL_18_STABLE and master), an internal page is modified via
gistinserttuple() (lines 805 to 806) only when gistgetadjusted() (line
774) returns a non-NULL widened downlink tuple (or via gistfinishsplit()
if a child splits). In the failing permutations above, Session 1's
insert widens the chosen child's downlink on root page 0 in shared
buffers (recording s2 ->rw s1 on page 0) so that the downlink now covers
'[5000, 5005)' (as well as '[4000, 4005)' in the fourth permutation).
When Session 2 then inserts '[5000, 5005)' or '[4000, 4005)',
gistgetadjusted() on root page 0 returns NULL, so gistdoinsert() unlocks
page 0 (line 823) and descends to the leaf page without calling
CheckForSerializableConflictIn() on page 0. Session 2 checks conflicts
only on the leaf page (where Session 1 holds no SIReadLock), so s1 ->rw
s2 is never recorded and both transactions commit. An unrelated
committed READ COMMITTED insert that widens the downlink after Session
1's scan has the same effect on a subsequent SERIALIZABLE insert.

4. A naive fix of calling CheckForSerializableConflictIn() on every
internal page traversed in gistdoinsert() would record a root-page
rw-conflict between every concurrent GiST scan and GiST insert, because
gistScanPage() locks GIST_ROOT_BLKNO before testing downlinks even when
descending into matching children. That behaves like locking the whole
index and causes two-sided disjoint-subtree permutations such as
"rxy3 rxy4 wx3 wy4 c1 c2" in src/test/isolation/specs/predicate-gist.spec
to fail with false-positive serialization errors.

Cheers,
Michael

Attachment Content-Type Size
gist-serializable-phantom.spec text/plain 3.1 KB

Browse pgsql-bugs by date

  From Date Subject
Next Message Tom Lane 2026-11-16 20:40:28 Re: BUG #19908: pg_upgrade --check crashes instance if running in a different PID Namespace then the old cluster
Previous Message Michael Malis 2026-11-16 20:28:11 Logical replication commits duplicates in DEFERRABLE unique indexes