agora inbox for pgsql-bugs@postgresql.org
help / color / mirror / Atom feedBUG #17949: Adding an index introduces serialisation anomalies.
28+ messages / 6 participants
[nested] [flat]
* BUG #17949: Adding an index introduces serialisation anomalies.
@ 2023-05-28 12:26 PG Bug reporting form <noreply@postgresql.org>
0 siblings, 1 reply; 28+ messages in thread
From: PG Bug reporting form @ 2023-05-28 12:26 UTC (permalink / raw)
To: pgsql-bugs@lists.postgresql.org; +Cc: artem.anisimov.255@gmail.com
The following bug has been logged on the website:
Bug reference: 17949
Logged by: Artem Anisimov
Email address: artem.anisimov.255@gmail.com
PostgreSQL version: 15.3
Operating system: fedora 38
Description:
Hello dear pg authors,
I have come across a behaviour in pg that contradicts
https://www.postgresql.org/docs/15/transaction-iso.html#XACT-SERIALIZABLE.
I've minimised my testcase to a scenario that essentially duplicates a
scenario that you describe in the following paragraph:
> In particular, it is possible to see unique constraint violations
> caused by conflicts with overlapping Serializable transactions
> even after explicitly checking that the key isn't present
> before attempting to insert it.
> This can be avoided by making sure that all Serializable transactions
that
> insert potentially conflicting keys explicitly check if they can do so
first.
At the end of the report there is a C reproducer that highlights the
problem. Let me give a high-level overview of the scenario first.
I have N threads each trying to "acquire an exclusive lock" this way:
BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE;
SELECT * FROM locks WHERE path = $1;
quit if there already is a lock
INSERT INTO locks(path, ...) VALUES($1, ...);
COMMIT;
Once all threads have attempted to acquire a lock, I count how many of them
succeeded to INSERT INTO. Normally, there is only one thread that succeeds,
which is what I expect. However, if I add a HASH or a BTREE index on "path",
it becomes possible for multiple threads to do a successful INSERT INTO,
which violates the serialisability.
The problem can be reproduced with the default postgresql.conf, but it takes
some time. If I increase "shared_buffers" to 1024MB, the issue appears
almost immediately (fewer chances to promote predicate locks to locks on the
whole table?).
I've seen this behaviour with pg 13, 15 and 16 (503b055).
Now let us see the reproducer. It has two primary components:
1. test_once() spawns 32 threads that try to acquire a lock, waits for them,
and counts the number of "acquired exclusive locks",
2. try_acquire_lock() executes a transaction described above.
To build the reproducer:
$ gcc -std=c99 -o test test.c -pthread `pkg-config libpq --cflags --libs`
To run the reproducer:
$ ./test
or
$ DB_CONNSTR="dbname=abc host=def user=ghi" ./test
The reproducer:
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <assert.h>
#include <libpq-fe.h>
// Comment this to make serialisation anomalies go away.
#define WITH_INDEX
// I have seen the problem with as few as 3 threads. 32 threads make
// the issue appear much sooner.
#define NR_THREADS (32)
#define NR_RUNS (1024 * 1024)
static PGconn *conns[NR_THREADS];
static void* try_acquire_lock(void *arg)
{
PGconn *c = arg;
PGresult *res;
int ntuples;
res = PQexec(c, "BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE");
assert(PQresultStatus(res) == PGRES_COMMAND_OK);
PQclear(res);
res = PQexec(c, "SELECT * FROM locks WHERE path = 'xyz'");
assert(PQresultStatus(res) == PGRES_TUPLES_OK);
ntuples = PQntuples(res);
PQclear(res);
if (ntuples > 0) {
// someone else already has a lock
res = PQexec(c, "COMMIT");
assert(PQresultStatus(res) == PGRES_COMMAND_OK);
PQclear(res);
return NULL;
}
res = PQexec(c, "INSERT INTO locks(path) VALUES('xyz')");
PQclear(res);
res = PQexec(c, "COMMIT");
PQclear(res);
return NULL;
}
static void test_once(void)
{
PGconn *c = conns[0];
PGresult *res;
int ntuples;
pthread_t thrs[NR_THREADS];
for (int i = 0; i < NR_THREADS; ++i)
pthread_create(&thrs[i], NULL, &try_acquire_lock,
conns[i]);
for (int i = 0; i < NR_THREADS; ++i)
pthread_join(thrs[i], NULL);
res = PQexec(c, "SELECT * FROM locks WHERE path = 'xyz'");
assert(PQresultStatus(res) == PGRES_TUPLES_OK);
ntuples = PQntuples(res);
PQclear(res);
if (ntuples != 1)
printf("ntuples = %d\n", ntuples);
assert(ntuples == 1);
res = PQexec(c, "TRUNCATE TABLE locks");
assert(PQresultStatus(res) == PGRES_COMMAND_OK);
PQclear(res);
}
static void prepare_db(void)
{
PGconn *c = conns[0];
PGresult *res;
res = PQexec(c, "DROP TABLE locks");
PQclear(res);
res = PQexec(c, "CREATE TABLE locks (path TEXT NOT NULL)");
assert(PQresultStatus(res) == PGRES_COMMAND_OK);
PQclear(res);
#ifdef WITH_INDEX
res = PQexec(c, "CREATE INDEX ON locks USING HASH(path)");
assert(PQresultStatus(res) == PGRES_COMMAND_OK);
PQclear(res);
#endif
}
int main(void)
{
const char *connstr = getenv("DB_CONNSTR");
if (connstr == NULL)
connstr = "dbname=postgres";
for (int i = 0; i < NR_THREADS; ++i) {
conns[i] = PQconnectdb(connstr);
assert(PQstatus(conns[i]) == CONNECTION_OK);
}
prepare_db();
for (int i = 0; i < NR_RUNS; ++i)
test_once();
for (int i = 0; i < NR_THREADS; ++i)
PQfinish(conns[i]);
return 0;
}
^ permalink raw reply [nested|flat] 28+ messages in thread
* Re: BUG #17949: Adding an index introduces serialisation anomalies.
@ 2023-05-30 01:29 Thomas Munro <thomas.munro@gmail.com>
parent: PG Bug reporting form <noreply@postgresql.org>
0 siblings, 2 replies; 28+ messages in thread
From: Thomas Munro @ 2023-05-30 01:29 UTC (permalink / raw)
To: artem.anisimov.255@gmail.com; pgsql-bugs@lists.postgresql.org
Hi,
Reproduced here. Thanks for the reproducer. I agree that something
is wrong here, but I haven't had time to figure out what, yet, but let
me share what I noticed so far... I modified your test to add a pid
column to the locks table and to insert insert pg_backend_pid() into
it, and got:
postgres=# select xmin, * from locks;
┌───────┬──────┬───────┐
│ xmin │ path │ pid │
├───────┼──────┼───────┤
│ 17634 │ xyz │ 32932 │
│ 17639 │ xyz │ 32957 │
└───────┴──────┴───────┘
Then I filtered the logs (having turned the logging up to capture all
queries) so I could see just those PIDs and saw this sequence:
2023-05-29 00:15:43.933 EDT [32932] LOG: duration: 0.182 ms
statement: BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE
2023-05-29 00:15:43.934 EDT [32957] LOG: duration: 0.276 ms
statement: BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE
2023-05-29 00:15:43.935 EDT [32932] LOG: duration: 1.563 ms
statement: SELECT * FROM locks WHERE path = 'xyz'
2023-05-29 00:15:43.936 EDT [32932] LOG: duration: 0.126 ms
statement: INSERT INTO locks(path, pid) VALUES('xyz',
pg_backend_pid())
2023-05-29 00:15:43.937 EDT [32957] LOG: duration: 2.191 ms
statement: SELECT * FROM locks WHERE path = 'xyz'
2023-05-29 00:15:43.937 EDT [32957] LOG: duration: 0.261 ms
statement: INSERT INTO locks(path, pid) VALUES('xyz',
pg_backend_pid())
2023-05-29 00:15:43.937 EDT [32932] LOG: duration: 0.222 ms statement: COMMIT
2023-05-29 00:15:43.939 EDT [32957] LOG: duration: 1.775 ms statement: COMMIT
That sequence if run (without overlap) in the logged order is normally
rejected. The query plan being used (at least when I run the query
myself) looks like this:
Query Text: SELECT * FROM locks WHERE path = 'xyz'
Bitmap Heap Scan on locks (cost=4.20..13.67 rows=6 width=36)
Recheck Cond: (path = 'xyz'::text)
-> Bitmap Index Scan on locks_path_idx (cost=0.00..4.20 rows=6 width=0)
Index Cond: (path = 'xyz'::text)
^ permalink raw reply [nested|flat] 28+ messages in thread
* Re: BUG #17949: Adding an index introduces serialisation anomalies.
@ 2023-06-13 08:00 Artem Anisimov <artem.anisimov.255@gmail.com>
parent: Thomas Munro <thomas.munro@gmail.com>
1 sibling, 1 reply; 28+ messages in thread
From: Artem Anisimov @ 2023-06-13 08:00 UTC (permalink / raw)
To: Thomas Munro <thomas.munro@gmail.com>; pgsql-bugs@lists.postgresql.org
Hi Thomas,
thank you for the confirmation and analysis. Did you have a chance to
take a more detailed look at the problem?
Best regards,
Artem.
On 30/05/2023 04:29, Thomas Munro wrote:
> Hi,
>
> Reproduced here. Thanks for the reproducer. I agree that something
> is wrong here, but I haven't had time to figure out what, yet, but let
> me share what I noticed so far... I modified your test to add a pid
> column to the locks table and to insert insert pg_backend_pid() into
> it, and got:
>
> postgres=# select xmin, * from locks;
>
> ┌───────┬──────┬───────┐
> │ xmin │ path │ pid │
> ├───────┼──────┼───────┤
> │ 17634 │ xyz │ 32932 │
> │ 17639 │ xyz │ 32957 │
> └───────┴──────┴───────┘
>
> Then I filtered the logs (having turned the logging up to capture all
> queries) so I could see just those PIDs and saw this sequence:
>
> 2023-05-29 00:15:43.933 EDT [32932] LOG: duration: 0.182 ms
> statement: BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE
> 2023-05-29 00:15:43.934 EDT [32957] LOG: duration: 0.276 ms
> statement: BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE
> 2023-05-29 00:15:43.935 EDT [32932] LOG: duration: 1.563 ms
> statement: SELECT * FROM locks WHERE path = 'xyz'
> 2023-05-29 00:15:43.936 EDT [32932] LOG: duration: 0.126 ms
> statement: INSERT INTO locks(path, pid) VALUES('xyz',
> pg_backend_pid())
> 2023-05-29 00:15:43.937 EDT [32957] LOG: duration: 2.191 ms
> statement: SELECT * FROM locks WHERE path = 'xyz'
> 2023-05-29 00:15:43.937 EDT [32957] LOG: duration: 0.261 ms
> statement: INSERT INTO locks(path, pid) VALUES('xyz',
> pg_backend_pid())
> 2023-05-29 00:15:43.937 EDT [32932] LOG: duration: 0.222 ms statement: COMMIT
> 2023-05-29 00:15:43.939 EDT [32957] LOG: duration: 1.775 ms statement: COMMIT
>
> That sequence if run (without overlap) in the logged order is normally
> rejected. The query plan being used (at least when I run the query
> myself) looks like this:
>
> Query Text: SELECT * FROM locks WHERE path = 'xyz'
> Bitmap Heap Scan on locks (cost=4.20..13.67 rows=6 width=36)
> Recheck Cond: (path = 'xyz'::text)
> -> Bitmap Index Scan on locks_path_idx (cost=0.00..4.20 rows=6 width=0)
> Index Cond: (path = 'xyz'::text)
^ permalink raw reply [nested|flat] 28+ messages in thread
* Re: BUG #17949: Adding an index introduces serialisation anomalies.
@ 2023-06-15 00:12 Thomas Munro <thomas.munro@gmail.com>
parent: Artem Anisimov <artem.anisimov.255@gmail.com>
0 siblings, 0 replies; 28+ messages in thread
From: Thomas Munro @ 2023-06-15 00:12 UTC (permalink / raw)
To: Artem Anisimov <artem.anisimov.255@gmail.com>; +Cc: pgsql-bugs@lists.postgresql.org
On Tue, Jun 13, 2023 at 8:00 PM Artem Anisimov
<artem.anisimov.255@gmail.com> wrote:
> thank you for the confirmation and analysis. Did you have a chance to
> take a more detailed look at the problem?
Looking into it...
^ permalink raw reply [nested|flat] 28+ messages in thread
* Re: BUG #17949: Adding an index introduces serialisation anomalies.
@ 2023-06-15 07:29 Dmitry Dolgov <9erthalion6@gmail.com>
parent: Thomas Munro <thomas.munro@gmail.com>
1 sibling, 1 reply; 28+ messages in thread
From: Dmitry Dolgov @ 2023-06-15 07:29 UTC (permalink / raw)
To: Thomas Munro <thomas.munro@gmail.com>; +Cc: artem.anisimov.255@gmail.com; pgsql-bugs@lists.postgresql.org
> On Mon, May 29, 2023 at 09:29:09PM -0400, Thomas Munro wrote:
> Starred
>
> Hi,
>
> Reproduced here. Thanks for the reproducer. I agree that something
> is wrong here, but I haven't had time to figure out what, yet, but let
> me share what I noticed so far... I modified your test to add a pid
> column to the locks table and to insert insert pg_backend_pid() into
> it, and got:
>
> postgres=# select xmin, * from locks;
>
> ┌───────┬──────┬───────┐
> │ xmin │ path │ pid │
> ├───────┼──────┼───────┤
> │ 17634 │ xyz │ 32932 │
> │ 17639 │ xyz │ 32957 │
> └───────┴──────┴───────┘
>
> Then I filtered the logs (having turned the logging up to capture all
> queries) so I could see just those PIDs and saw this sequence:
>
> 2023-05-29 00:15:43.933 EDT [32932] LOG: duration: 0.182 ms
> statement: BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE
> 2023-05-29 00:15:43.934 EDT [32957] LOG: duration: 0.276 ms
> statement: BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE
> 2023-05-29 00:15:43.935 EDT [32932] LOG: duration: 1.563 ms
> statement: SELECT * FROM locks WHERE path = 'xyz'
> 2023-05-29 00:15:43.936 EDT [32932] LOG: duration: 0.126 ms
> statement: INSERT INTO locks(path, pid) VALUES('xyz',
> pg_backend_pid())
> 2023-05-29 00:15:43.937 EDT [32957] LOG: duration: 2.191 ms
> statement: SELECT * FROM locks WHERE path = 'xyz'
> 2023-05-29 00:15:43.937 EDT [32957] LOG: duration: 0.261 ms
> statement: INSERT INTO locks(path, pid) VALUES('xyz',
> pg_backend_pid())
> 2023-05-29 00:15:43.937 EDT [32932] LOG: duration: 0.222 ms statement: COMMIT
> 2023-05-29 00:15:43.939 EDT [32957] LOG: duration: 1.775 ms statement: COMMIT
I've tried to reproduce it as well, adding more logging around the
serialization code. If it helps, what I observe is the second
overlapping transaction, that has started a bit later, do not error out
because in OnConflict_CheckForSerializationFailure (when checking for
"writer has become a pivot") there are no more conflicts received from
SHMQueueNext. All the rest of the reported serialization conflicts are
coming from this check, so I assume the incorrect transaction should
fail there too. Not sure yet why is that so.
^ permalink raw reply [nested|flat] 28+ messages in thread
* Re: BUG #17949: Adding an index introduces serialisation anomalies.
@ 2023-06-16 23:22 Thomas Munro <thomas.munro@gmail.com>
parent: Dmitry Dolgov <9erthalion6@gmail.com>
0 siblings, 1 reply; 28+ messages in thread
From: Thomas Munro @ 2023-06-16 23:22 UTC (permalink / raw)
To: Dmitry Dolgov <9erthalion6@gmail.com>; +Cc: artem.anisimov.255@gmail.com; pgsql-bugs@lists.postgresql.org
On Thu, Jun 15, 2023 at 7:29 PM Dmitry Dolgov <9erthalion6@gmail.com> wrote:
> I've tried to reproduce it as well, adding more logging around the
> serialization code. If it helps, what I observe is the second
> overlapping transaction, that has started a bit later, do not error out
> because in OnConflict_CheckForSerializationFailure (when checking for
> "writer has become a pivot") there are no more conflicts received from
> SHMQueueNext. All the rest of the reported serialization conflicts are
> coming from this check, so I assume the incorrect transaction should
> fail there too. Not sure yet why is that so.
Some more observations: happens on 11 and master, happens with btrees,
happens with bitmapscan disabled (eg with plain index scan), but so
far in my testing it doesn't happen if the table already contains one
other tuple (ie if you change the reproducer to insert another row
('foo') after the TRUNCATE). There is a special case for predicate
locking empty indexes, which uses a relation-level (since there are no
pages to lock yet), but that doesn't seem to be wrong and if you hack
it to lock pages 1 and 2 instead, it still reproduces. Pondering the
empty index case made me wonder if the case "If we found one of our
own SIREAD locks to remove, remove it now" was implicated (that's
something that would not happen for a relation-level lock), but it
still reproduces if you comment out that optimisation. So far I have
not been able to reproduce it below 8 threads. Hmm, I wonder if there
might be a missing check/lock in some racy code path around the
initial creation of the root page...
^ permalink raw reply [nested|flat] 28+ messages in thread
* Re: BUG #17949: Adding an index introduces serialisation anomalies.
@ 2023-06-19 02:29 Thomas Munro <thomas.munro@gmail.com>
parent: Thomas Munro <thomas.munro@gmail.com>
0 siblings, 1 reply; 28+ messages in thread
From: Thomas Munro @ 2023-06-19 02:29 UTC (permalink / raw)
To: Dmitry Dolgov <9erthalion6@gmail.com>; +Cc: artem.anisimov.255@gmail.com; pgsql-bugs@lists.postgresql.org
How is this schedule supposed to work?
S1: _bt_search(&buf)
S1: if (!BufferIsValid(buf)) // because index is empty
S1: {
S1: PredicateLockRelation(...);
S1: ...
S1: return false; // no tuples for you
S2: _bt_search(&buf)
S1: INSERT ...
S2: if (!BufferIsValid(buf)) // because index *was* empty
S2: {
S2: PredicateLockRelation(...);
S2: ...
S2: return false; // no tuples for you
S2: ...
My point is that S2 won't ever scan S1's tuples, so it won't pass S1's
xid to CheckForSerializableConflictOut(). Am I missing something? I
can repro this with NR_THREADS set to only 2, after inserting
pg_usleep(1) after the _bt_search() in _bt_first() (sched_yield()
wasn't quite enough).
^ permalink raw reply [nested|flat] 28+ messages in thread
* Re: BUG #17949: Adding an index introduces serialisation anomalies.
@ 2023-06-19 03:23 Thomas Munro <thomas.munro@gmail.com>
parent: Thomas Munro <thomas.munro@gmail.com>
0 siblings, 1 reply; 28+ messages in thread
From: Thomas Munro @ 2023-06-19 03:23 UTC (permalink / raw)
To: Dmitry Dolgov <9erthalion6@gmail.com>; +Cc: artem.anisimov.255@gmail.com; pgsql-bugs@lists.postgresql.org
On Mon, Jun 19, 2023 at 2:29 PM Thomas Munro <thomas.munro@gmail.com> wrote:
> S2: _bt_search(&buf)
> S1: INSERT ...
> S2: PredicateLockRelation(...);
> My point is that S2 won't ever scan S1's tuples, so it won't pass S1's
> xid to CheckForSerializableConflictOut()
[completing that sentence a little more] ... so this was our only
chance to detect that S2 read an object that S1 wrote. But the
_bt_search() and PredicateLockXXX() calls are not atomic and not
rechecked, so a write between them is invisible to the algorithm. I'm
not sure about this, but it's the idea I'm exploring...
^ permalink raw reply [nested|flat] 28+ messages in thread
* Re: BUG #17949: Adding an index introduces serialisation anomalies.
@ 2023-06-19 06:50 Thomas Munro <thomas.munro@gmail.com>
parent: Thomas Munro <thomas.munro@gmail.com>
0 siblings, 1 reply; 28+ messages in thread
From: Thomas Munro @ 2023-06-19 06:50 UTC (permalink / raw)
To: Dmitry Dolgov <9erthalion6@gmail.com>; +Cc: artem.anisimov.255@gmail.com; pgsql-bugs@lists.postgresql.org
The attached shows one approach to the problem I described already,
namely scans of empty btrees that concurrently gain an initial root
page. This seems to fix the posted repro case if using a btree with
enable_seqscan=off, enable_bitmapscan=off. That's the variant I had
been working with, because it was simpler.
But that turns out to be only one problem hit by the repro.
Apparently there's a second bug, if you let it use bitmap heapscans.
Or perhaps I am misdiagnosing the above. It could be something like:
btgetbitmap not following the predicate lock protocol correctly (but
it looks OK at a glance), or bitmap heapscan not checking for
conflicts out comprehensively (xids on invisible tuples we scan), eg
not fetching heap tuples for some short cut reason somewhere. But
that's all I have time for today.
Attachments:
[application/octet-stream] 0001-Fix-rare-race-in-SSI-interaction-with-empty-btrees.patch (2.5K, ../../CA+hUKG+3B7uBkJd4rr2FXhTc+95F3RvRovbhBM2UDt68aL5a-g@mail.gmail.com/2-0001-Fix-rare-race-in-SSI-interaction-with-empty-btrees.patch)
download | inline diff:
From 69bc0e964cfa0081058305c46f54f11b684919b1 Mon Sep 17 00:00:00 2001
From: Thomas Munro <thomas.munro@gmail.com>
Date: Mon, 19 Jun 2023 16:28:02 +1200
Subject: [PATCH] Fix rare race in SSI interaction with empty btrees.
When locking key-space gaps in btrees with a page-level SIREAD locks, we
have a special case for completely empty btrees, since there is no page
to lock. This was racy, because a matching key could be inserted
between the _bt_search() and the PredicateLockRelation() calls, with
unluckly scheduling.
Fix, by rechecking _bt_search() after taking the relation-level SIREAD
lock, if using SERIALIZABLE isolation.
XXX WIP, not the end of the story
Bug #17949.
Reported-by: Artem Anisimov <artem.anisimov.255@gmail.com>
Discussion: https://postgr.es/m/17949-a0f17035294a55e2%40postgresql.org
diff --git a/src/backend/access/nbtree/nbtsearch.c b/src/backend/access/nbtree/nbtsearch.c
index 7e05e58676..162a06741d 100644
--- a/src/backend/access/nbtree/nbtsearch.c
+++ b/src/backend/access/nbtree/nbtsearch.c
@@ -1381,23 +1381,33 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
if (!BufferIsValid(buf))
{
/*
- * We only get here if the index is completely empty. Lock relation
- * because nothing finer to lock exists.
+ * Since we have no pages locked, it's possible for another transaction
+ * to insert data between _bt_search() and PredicateLockRelation(). We
+ * have to try again after taking a relation-level predicate lock, to
+ * close a narrow window where we wouldn't scan concurrently inserted
+ * tuples, but the writer wouldn't see our predicate lock.
*/
- PredicateLockRelation(rel, scan->xs_snapshot);
-
- /*
- * mark parallel scan as done, so that all the workers can finish
- * their scan
- */
- _bt_parallel_done(scan);
- BTScanPosInvalidate(so->currPos);
+ if (IsolationIsSerializable())
+ {
+ PredicateLockRelation(rel, scan->xs_snapshot);
+ stack = _bt_search(rel, NULL, &inskey, &buf, BT_READ,
+ scan->xs_snapshot);
+ _bt_freestack(stack);
+ }
- return false;
+ if (!BufferIsValid(buf))
+ {
+ /*
+ * Mark parallel scan as done, so that all the workers can finish
+ * their scan.
+ */
+ _bt_parallel_done(scan);
+ BTScanPosInvalidate(so->currPos);
+ return false;
+ }
}
- else
- PredicateLockPage(rel, BufferGetBlockNumber(buf),
- scan->xs_snapshot);
+
+ PredicateLockPage(rel, BufferGetBlockNumber(buf), scan->xs_snapshot);
_bt_initialize_more_data(so, dir);
--
2.39.2 (Apple Git-143)
^ permalink raw reply [nested|flat] 28+ messages in thread
* Re: BUG #17949: Adding an index introduces serialisation anomalies.
@ 2023-06-19 09:30 Thomas Munro <thomas.munro@gmail.com>
parent: Thomas Munro <thomas.munro@gmail.com>
0 siblings, 1 reply; 28+ messages in thread
From: Thomas Munro @ 2023-06-19 09:30 UTC (permalink / raw)
To: Dmitry Dolgov <9erthalion6@gmail.com>; +Cc: artem.anisimov.255@gmail.com; pgsql-bugs@lists.postgresql.org
On Mon, Jun 19, 2023 at 6:50 PM Thomas Munro <thomas.munro@gmail.com> wrote:
> ... or bitmap heapscan not checking for
> conflicts out comprehensively (xids on invisible tuples we scan), eg
> not fetching heap tuples for some short cut reason somewhere. ...
Ahh, here's such a place. I can't reproduce it with the patch already
posted + this check commented out.
--- a/src/backend/access/heap/heapam_handler.c
+++ b/src/backend/access/heap/heapam_handler.c
@@ -2127,16 +2127,18 @@ heapam_scan_bitmap_next_block(TableScanDesc scan,
hscan->rs_cindex = 0;
hscan->rs_ntuples = 0;
+#if 0
/*
* Ignore any claimed entries past what we think is the end of the
* relation. It may have been extended after the start of our scan (we
* only hold an AccessShareLock, and it could be inserts from this
* backend).
*/
if (block >= hscan->rs_nblocks)
return false;
+#endif
^ permalink raw reply [nested|flat] 28+ messages in thread
* Re: BUG #17949: Adding an index introduces serialisation anomalies.
@ 2023-06-19 12:17 Dmitry Dolgov <9erthalion6@gmail.com>
parent: Thomas Munro <thomas.munro@gmail.com>
0 siblings, 1 reply; 28+ messages in thread
From: Dmitry Dolgov @ 2023-06-19 12:17 UTC (permalink / raw)
To: Thomas Munro <thomas.munro@gmail.com>; +Cc: artem.anisimov.255@gmail.com; pgsql-bugs@lists.postgresql.org
> On Mon, Jun 19, 2023 at 09:30:12PM +1200, Thomas Munro wrote:
> On Mon, Jun 19, 2023 at 6:50 PM Thomas Munro <thomas.munro@gmail.com> wrote:
> > ... or bitmap heapscan not checking for
> > conflicts out comprehensively (xids on invisible tuples we scan), eg
> > not fetching heap tuples for some short cut reason somewhere. ...
>
> Ahh, here's such a place. I can't reproduce it with the patch already
> posted + this check commented out.
>
> --- a/src/backend/access/heap/heapam_handler.c
> +++ b/src/backend/access/heap/heapam_handler.c
> @@ -2127,16 +2127,18 @@ heapam_scan_bitmap_next_block(TableScanDesc scan,
>
> hscan->rs_cindex = 0;
> hscan->rs_ntuples = 0;
>
> +#if 0
> /*
> * Ignore any claimed entries past what we think is the end of the
> * relation. It may have been extended after the start of our scan (we
> * only hold an AccessShareLock, and it could be inserts from this
> * backend).
> */
> if (block >= hscan->rs_nblocks)
> return false;
> +#endif
Great, thanks! Can confirm, after applying both the posted patch and the
change above the issue is not reproducible anymore.
One thing I've noticed is that one can observe a similar issue using a
gin index and int[] for the "path" column, even applying changes from
the thread. The gin implementation does something similar to btree in
startScanEntry -- it lands in "No entry found" branch, but instead of
locking the relation it locks "the leaf page, to lock the place where
the entry would've been, had there been one". The similar fix retrying
ginFindLeafPage didn't solve the problem, even if locking the whole
relation instead, but maybe I'm missing something.
^ permalink raw reply [nested|flat] 28+ messages in thread
* Re: BUG #17949: Adding an index introduces serialisation anomalies.
@ 2023-06-20 01:22 Thomas Munro <thomas.munro@gmail.com>
parent: Dmitry Dolgov <9erthalion6@gmail.com>
0 siblings, 2 replies; 28+ messages in thread
From: Thomas Munro @ 2023-06-20 01:22 UTC (permalink / raw)
To: Dmitry Dolgov <9erthalion6@gmail.com>; +Cc: artem.anisimov.255@gmail.com; pgsql-bugs@lists.postgresql.org
On Tue, Jun 20, 2023 at 12:18 AM Dmitry Dolgov <9erthalion6@gmail.com> wrote:
> > On Mon, Jun 19, 2023 at 09:30:12PM +1200, Thomas Munro wrote:
> > +#if 0
> > /*
> > * Ignore any claimed entries past what we think is the end of the
> > * relation. It may have been extended after the start of our scan (we
> > * only hold an AccessShareLock, and it could be inserts from this
> > * backend).
> > */
> > if (block >= hscan->rs_nblocks)
> > return false;
> > +#endif
>
> Great, thanks! Can confirm, after applying both the posted patch and the
> change above the issue is not reproducible anymore.
Here's a cleaned-up version of the first two changes. What do you
think about the assertions I make in the commit message for 0002?
> One thing I've noticed is that one can observe a similar issue using a
> gin index and int[] for the "path" column, even applying changes from
> the thread. The gin implementation does something similar to btree in
> startScanEntry -- it lands in "No entry found" branch, but instead of
> locking the relation it locks "the leaf page, to lock the place where
> the entry would've been, had there been one". The similar fix retrying
> ginFindLeafPage didn't solve the problem, even if locking the whole
> relation instead, but maybe I'm missing something.
Ouch. I would have to go and study gin's interlocking model, but one
superficial bug I spotted is that ginget.c's collectMatchBitmap()
calls PredicateLockPage(stack->buffer), where a block number is
expected. I wish we had strong typedefs, to reject stuff like that at
compile time. But fixing that alone isn't enough.
In case someone who knows more about gin is interested in helping, I
attach Artem's repro, modified to use gin.
Attachments:
[text/x-patch] v2-0001-Fix-race-in-SSI-interaction-with-empty-btrees.patch (2.6K, ../../CA+hUKGJP3g6PF4vES0X0zy34uuSvHxHUhoq65A_WtzqxPpJ_6g@mail.gmail.com/2-v2-0001-Fix-race-in-SSI-interaction-with-empty-btrees.patch)
download | inline diff:
From 3b833e4e560bba3308ed40e4c8cd8b9c625dac04 Mon Sep 17 00:00:00 2001
From: Thomas Munro <thomas.munro@gmail.com>
Date: Mon, 19 Jun 2023 16:28:02 +1200
Subject: [PATCH v2 1/2] Fix race in SSI interaction with empty btrees.
When predicate-locking btrees, we have a special case for completely
empty btrees, since there is no page to lock. This was racy, because,
without a buffer lock held, a matching key could be inserted between the
_bt_search() and the PredicateLockRelation() calls.
Fix, by rechecking _bt_search() after taking the relation-level SIREAD
lock, if using SERIALIZABLE isolation and an empty btree is discovered.
Back-patch to all supported releases.
Reported-by: Artem Anisimov <artem.anisimov.255@gmail.com>
Tested-by: Dmitry Dolgov <9erthalion6@gmail.com>
Discussion: https://postgr.es/m/17949-a0f17035294a55e2%40postgresql.org
---
src/backend/access/nbtree/nbtsearch.c | 39 +++++++++++++++++----------
1 file changed, 25 insertions(+), 14 deletions(-)
diff --git a/src/backend/access/nbtree/nbtsearch.c b/src/backend/access/nbtree/nbtsearch.c
index 7e05e58676..2477b7aefb 100644
--- a/src/backend/access/nbtree/nbtsearch.c
+++ b/src/backend/access/nbtree/nbtsearch.c
@@ -1381,23 +1381,34 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
if (!BufferIsValid(buf))
{
/*
- * We only get here if the index is completely empty. Lock relation
- * because nothing finer to lock exists.
+ * Since we have no pages locked, it's possible for another
+ * transaction to insert data between _bt_search() and
+ * PredicateLockRelation(). We have to try again after taking a
+ * relation-level predicate lock, to close a narrow window where we
+ * wouldn't scan concurrently inserted tuples, but the writer wouldn't
+ * see our predicate lock.
*/
- PredicateLockRelation(rel, scan->xs_snapshot);
-
- /*
- * mark parallel scan as done, so that all the workers can finish
- * their scan
- */
- _bt_parallel_done(scan);
- BTScanPosInvalidate(so->currPos);
+ if (IsolationIsSerializable())
+ {
+ PredicateLockRelation(rel, scan->xs_snapshot);
+ stack = _bt_search(rel, NULL, &inskey, &buf, BT_READ,
+ scan->xs_snapshot);
+ _bt_freestack(stack);
+ }
- return false;
+ if (!BufferIsValid(buf))
+ {
+ /*
+ * Mark parallel scan as done, so that all the workers can finish
+ * their scan.
+ */
+ _bt_parallel_done(scan);
+ BTScanPosInvalidate(so->currPos);
+ return false;
+ }
}
- else
- PredicateLockPage(rel, BufferGetBlockNumber(buf),
- scan->xs_snapshot);
+
+ PredicateLockPage(rel, BufferGetBlockNumber(buf), scan->xs_snapshot);
_bt_initialize_more_data(so, dir);
--
2.40.1
[text/x-patch] v2-0002-Fix-race-in-SSI-interaction-with-bitmap-heap-scan.patch (2.3K, ../../CA+hUKGJP3g6PF4vES0X0zy34uuSvHxHUhoq65A_WtzqxPpJ_6g@mail.gmail.com/3-v2-0002-Fix-race-in-SSI-interaction-with-bitmap-heap-scan.patch)
download | inline diff:
From de11e590c0a5656e13e66281cd9d5a99c62ed658 Mon Sep 17 00:00:00 2001
From: Thomas Munro <thomas.munro@gmail.com>
Date: Tue, 20 Jun 2023 11:08:54 +1200
Subject: [PATCH v2 2/2] Fix race in SSI interaction with bitmap heap scan.
When performing a bitmap heap scan, we don't want to miss concurrent
writes that occurred after we observed the heap's rs_nblocks, but before
we took predicate locks on index pages. Therefore, we can't skip
fetching any heap tuples that are referenced by the index, because we
need to test them all with CheckForSerializableConflictOut(). The
old optimization that would ignore any references to blocks >=
rs_nblocks gets in the way of that requirement, because it means that
concurrent writes in that window are ignored.
Removing that optimization shouldn't affect correctness at any isolation
level, because any new tuples shouldn't be visible to an MVCC snapshot.
There also shouldn't be any error-causing references to heap blocks past
the end, because we should have held at least an AccessShareLock on the
table before the index scan. It can't get smaller while our transaction
is running.
Back-patch to all supported releases. In release 11, the removed code
is in a different location due to the table AM refactoring in commit
bfbcad47, but not fundamentally different.
Reported-by: Artem Anisimov <artem.anisimov.255@gmail.com>
Tested-by: Dmitry Dolgov <9erthalion6@gmail.com>
Discussion: https://postgr.es/m/17949-a0f17035294a55e2%40postgresql.org
---
src/backend/access/heap/heapam_handler.c | 9 ---------
1 file changed, 9 deletions(-)
diff --git a/src/backend/access/heap/heapam_handler.c b/src/backend/access/heap/heapam_handler.c
index 0755be8390..b41de7e3e1 100644
--- a/src/backend/access/heap/heapam_handler.c
+++ b/src/backend/access/heap/heapam_handler.c
@@ -2128,15 +2128,6 @@ heapam_scan_bitmap_next_block(TableScanDesc scan,
hscan->rs_cindex = 0;
hscan->rs_ntuples = 0;
- /*
- * Ignore any claimed entries past what we think is the end of the
- * relation. It may have been extended after the start of our scan (we
- * only hold an AccessShareLock, and it could be inserts from this
- * backend).
- */
- if (block >= hscan->rs_nblocks)
- return false;
-
/*
* Acquire pin on the target heap page, trading in any pin we held before.
*/
--
2.40.1
[text/x-csrc] test-ssi-gin-repro.c (3.1K, ../../CA+hUKGJP3g6PF4vES0X0zy34uuSvHxHUhoq65A_WtzqxPpJ_6g@mail.gmail.com/4-test-ssi-gin-repro.c)
download | inline:
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <assert.h>
#include <libpq-fe.h>
// Comment this to make serialisation anomalies go away.
#define WITH_INDEX
// I have seen the problem with as few as 3 threads. 32 threads make
// the issue appear much sooner.
#define NR_THREADS (32)
#define NR_RUNS (1024 * 1024)
static PGconn *conns[NR_THREADS];
static void* try_acquire_lock(void *arg)
{
PGconn *c = arg;
PGresult *res;
int ntuples;
res = PQexec(c, "BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE");
assert(PQresultStatus(res) == PGRES_COMMAND_OK);
PQclear(res);
res = PQexec(c, "SELECT * FROM locks WHERE path = '{42}'");
assert(PQresultStatus(res) == PGRES_TUPLES_OK);
ntuples = PQntuples(res);
PQclear(res);
if (ntuples > 0) {
// someone else already has a lock
res = PQexec(c, "COMMIT");
assert(PQresultStatus(res) == PGRES_COMMAND_OK);
PQclear(res);
return NULL;
}
res = PQexec(c, "INSERT INTO locks(path) VALUES('{42}')");
PQclear(res);
res = PQexec(c, "COMMIT");
PQclear(res);
return NULL;
}
static void test_once(void)
{
PGconn *c = conns[0];
PGresult *res;
int ntuples;
pthread_t thrs[NR_THREADS];
for (int i = 0; i < NR_THREADS; ++i)
pthread_create(&thrs[i], NULL, &try_acquire_lock,
conns[i]);
for (int i = 0; i < NR_THREADS; ++i)
pthread_join(thrs[i], NULL);
res = PQexec(c, "SELECT * FROM locks WHERE path = '{42}'");
assert(PQresultStatus(res) == PGRES_TUPLES_OK);
ntuples = PQntuples(res);
PQclear(res);
if (ntuples != 1)
printf("ntuples = %d\n", ntuples);
assert(ntuples == 1);
res = PQexec(c, "TRUNCATE TABLE locks");
assert(PQresultStatus(res) == PGRES_COMMAND_OK);
PQclear(res);
res = PQexec(c, "INSERT INTO locks VALUES ('{666}')");
assert(PQresultStatus(res) == PGRES_COMMAND_OK);
PQclear(res);
}
static void prepare_db(void)
{
PGconn *c = conns[0];
PGresult *res;
res = PQexec(c, "DROP TABLE locks");
PQclear(res);
res = PQexec(c, "CREATE TABLE locks (path int[] NOT NULL)");
assert(PQresultStatus(res) == PGRES_COMMAND_OK);
PQclear(res);
#ifdef WITH_INDEX
res = PQexec(c, "CREATE INDEX ON locks USING gin(path)");
assert(PQresultStatus(res) == PGRES_COMMAND_OK);
PQclear(res);
#endif
}
int main(void)
{
const char *connstr = getenv("DB_CONNSTR");
if (connstr == NULL)
connstr = "dbname=postgres";
for (int i = 0; i < NR_THREADS; ++i) {
conns[i] = PQconnectdb(connstr);
assert(PQstatus(conns[i]) == CONNECTION_OK);
}
prepare_db();
for (int i = 0; i < NR_RUNS; ++i)
test_once();
for (int i = 0; i < NR_THREADS; ++i)
PQfinish(conns[i]);
return 0;
}
^ permalink raw reply [nested|flat] 28+ messages in thread
* Re: BUG #17949: Adding an index introduces serialisation anomalies.
@ 2023-06-20 22:54 Thomas Munro <thomas.munro@gmail.com>
parent: Thomas Munro <thomas.munro@gmail.com>
1 sibling, 1 reply; 28+ messages in thread
From: Thomas Munro @ 2023-06-20 22:54 UTC (permalink / raw)
To: Dmitry Dolgov <9erthalion6@gmail.com>; +Cc: artem.anisimov.255@gmail.com, pgsql-bugs@lists.postgresql.org, Teodor Sigaev <teodor@sigaev.ru>; Heikki Linnakangas <hlinnaka@iki.fi>
On Tue, Jun 20, 2023 at 1:22 PM Thomas Munro <thomas.munro@gmail.com> wrote:
> On Tue, Jun 20, 2023 at 12:18 AM Dmitry Dolgov <9erthalion6@gmail.com> wrote:
> > One thing I've noticed is that one can observe a similar issue using a
> > gin index and int[] for the "path" column, even applying changes from
> > the thread. The gin implementation does something similar to btree in
> > startScanEntry -- it lands in "No entry found" branch, but instead of
> > locking the relation it locks "the leaf page, to lock the place where
> > the entry would've been, had there been one". The similar fix retrying
> > ginFindLeafPage didn't solve the problem, even if locking the whole
> > relation instead, but maybe I'm missing something.
>
> Ouch. I would have to go and study gin's interlocking model, but one
> superficial bug I spotted is that ginget.c's collectMatchBitmap()
> calls PredicateLockPage(stack->buffer), where a block number is
> expected. I wish we had strong typedefs, to reject stuff like that at
> compile time. But fixing that alone isn't enough.
>
> In case someone who knows more about gin is interested in helping, I
> attach Artem's repro, modified to use gin.
This is probably going to go faster if I CC the authors of commit
0bef1c06. Any ideas about how we're missing rw-conflicts under high
concurrency?
^ permalink raw reply [nested|flat] 28+ messages in thread
* Re: BUG #17949: Adding an index introduces serialisation anomalies.
@ 2023-06-20 23:20 Thomas Munro <thomas.munro@gmail.com>
parent: Thomas Munro <thomas.munro@gmail.com>
0 siblings, 1 reply; 28+ messages in thread
From: Thomas Munro @ 2023-06-20 23:20 UTC (permalink / raw)
To: Dmitry Dolgov <9erthalion6@gmail.com>; +Cc: artem.anisimov.255@gmail.com, pgsql-bugs@lists.postgresql.org, Teodor Sigaev <teodor@sigaev.ru>; Heikki Linnakangas <hlinnaka@iki.fi>
On Wed, Jun 21, 2023 at 10:54 AM Thomas Munro <thomas.munro@gmail.com> wrote:
> This is probably going to go faster if I CC the authors of commit
> 0bef1c06. Any ideas about how we're missing rw-conflicts under high
> concurrency?
I guess one (probably stupid) question I have: where is the
CheckForSerializableConflictIn(rootPostingTree) that I was expecting
to see when writing to an existing posting tree? IIUC that should
pair with PredicateLockPage(btree->index, rootPostingTree, snapshot)
when reading.
^ permalink raw reply [nested|flat] 28+ messages in thread
* Re: BUG #17949: Adding an index introduces serialisation anomalies.
@ 2023-06-21 08:58 Dmitry Dolgov <9erthalion6@gmail.com>
parent: Thomas Munro <thomas.munro@gmail.com>
1 sibling, 0 replies; 28+ messages in thread
From: Dmitry Dolgov @ 2023-06-21 08:58 UTC (permalink / raw)
To: Thomas Munro <thomas.munro@gmail.com>; +Cc: artem.anisimov.255@gmail.com; pgsql-bugs@lists.postgresql.org
> On Tue, Jun 20, 2023 at 01:22:19PM +1200, Thomas Munro wrote:
> On Tue, Jun 20, 2023 at 12:18 AM Dmitry Dolgov <9erthalion6@gmail.com> wrote:
> > > On Mon, Jun 19, 2023 at 09:30:12PM +1200, Thomas Munro wrote:
> > > +#if 0
> > > /*
> > > * Ignore any claimed entries past what we think is the end of the
> > > * relation. It may have been extended after the start of our scan (we
> > > * only hold an AccessShareLock, and it could be inserts from this
> > > * backend).
> > > */
> > > if (block >= hscan->rs_nblocks)
> > > return false;
> > > +#endif
> >
> > Great, thanks! Can confirm, after applying both the posted patch and the
> > change above the issue is not reproducible anymore.
>
> Here's a cleaned-up version of the first two changes. What do you
> think about the assertions I make in the commit message for 0002?
Yep, it sounds correct to me. After a quick look I couldn't find where
exactly the similar code lives in the pre-tableam version, so can't say
anything about back-patching there.
^ permalink raw reply [nested|flat] 28+ messages in thread
* Re: BUG #17949: Adding an index introduces serialisation anomalies.
@ 2023-06-21 09:04 Dmitry Dolgov <9erthalion6@gmail.com>
parent: Thomas Munro <thomas.munro@gmail.com>
0 siblings, 1 reply; 28+ messages in thread
From: Dmitry Dolgov @ 2023-06-21 09:04 UTC (permalink / raw)
To: Thomas Munro <thomas.munro@gmail.com>; +Cc: artem.anisimov.255@gmail.com, pgsql-bugs@lists.postgresql.org, Teodor Sigaev <teodor@sigaev.ru>; Heikki Linnakangas <hlinnaka@iki.fi>
> On Wed, Jun 21, 2023 at 11:20:28AM +1200, Thomas Munro wrote:
> On Wed, Jun 21, 2023 at 10:54 AM Thomas Munro <thomas.munro@gmail.com> wrote:
> > This is probably going to go faster if I CC the authors of commit
> > 0bef1c06. Any ideas about how we're missing rw-conflicts under high
> > concurrency?
>
> I guess one (probably stupid) question I have: where is the
> CheckForSerializableConflictIn(rootPostingTree) that I was expecting
> to see when writing to an existing posting tree? IIUC that should
> pair with PredicateLockPage(btree->index, rootPostingTree, snapshot)
> when reading.
I can't find it either, but based on my superficial investigation this
particular reproducer doesn't seem to hit posting trees functionality at
all. What I observe is the inserting transaction uses
ginHeapTupleFastCollect + ginHeapTupleFastInsert, and the corresponding
commentary says that serialization in this case depends on the
metabuffer:
/*
* An insertion to the pending list could logically belong anywhere in the
* tree, so it conflicts with all serializable scans. All scans acquire a
* predicate lock on the metabuffer to represent that.
*/
Now the reading transaction actually does PredicateLockPage on the
metabuffer inside scanPendingInsert, but strangely enough it doesn't
lock anything because the SerializationNeededForRead condition is false.
I'm trying to verify if it's somehow a part of the issue, or something
is broken on my side.
^ permalink raw reply [nested|flat] 28+ messages in thread
* Re: BUG #17949: Adding an index introduces serialisation anomalies.
@ 2023-06-22 10:02 Thomas Munro <thomas.munro@gmail.com>
parent: Dmitry Dolgov <9erthalion6@gmail.com>
0 siblings, 1 reply; 28+ messages in thread
From: Thomas Munro @ 2023-06-22 10:02 UTC (permalink / raw)
To: Dmitry Dolgov <9erthalion6@gmail.com>; +Cc: artem.anisimov.255@gmail.com, pgsql-bugs@lists.postgresql.org, Teodor Sigaev <teodor@sigaev.ru>; Heikki Linnakangas <hlinnaka@iki.fi>
On Wed, Jun 21, 2023 at 9:04 PM Dmitry Dolgov <9erthalion6@gmail.com> wrote:
> Now the reading transaction actually does PredicateLockPage on the
> metabuffer inside scanPendingInsert, but strangely enough it doesn't
> lock anything because the SerializationNeededForRead condition is false.
> I'm trying to verify if it's somehow a part of the issue, or something
> is broken on my side.
Maybe you were confused by the presence of non-SSI transactions in the
repro (eg the transaction that sets up the index)?
To answer my own earlier question, the conflict-in check for posting
trees is hidden in getFindLeafPage(..., true, ...).
I spent some more time trying to grok this today. FTR it reproduces
faster without the extra tuple that repro I posted inserts after
TRUNCATE (the point of that was to find out whether it was an
empty-to-non-empty transition). I still don't know what's wrong but I
am beginning to suspect the "fast" code. It seems as though, under
high concurrency, we sometimes don't scan a recently inserted
(invisible to our snapshot, but needed for SSI checks) tuple, but I
don't yet know why.
^ permalink raw reply [nested|flat] 28+ messages in thread
* Re: BUG #17949: Adding an index introduces serialisation anomalies.
@ 2023-06-23 14:05 Dmitry Dolgov <9erthalion6@gmail.com>
parent: Thomas Munro <thomas.munro@gmail.com>
0 siblings, 1 reply; 28+ messages in thread
From: Dmitry Dolgov @ 2023-06-23 14:05 UTC (permalink / raw)
To: Thomas Munro <thomas.munro@gmail.com>; +Cc: artem.anisimov.255@gmail.com, pgsql-bugs@lists.postgresql.org, Teodor Sigaev <teodor@sigaev.ru>; Heikki Linnakangas <hlinnaka@iki.fi>
> On Thu, Jun 22, 2023 at 10:02:19PM +1200, Thomas Munro wrote:
> On Wed, Jun 21, 2023 at 9:04 PM Dmitry Dolgov <9erthalion6@gmail.com> wrote:
> > Now the reading transaction actually does PredicateLockPage on the
> > metabuffer inside scanPendingInsert, but strangely enough it doesn't
> > lock anything because the SerializationNeededForRead condition is false.
> > I'm trying to verify if it's somehow a part of the issue, or something
> > is broken on my side.
>
> Maybe you were confused by the presence of non-SSI transactions in the
> repro (eg the transaction that sets up the index)?
Yeah, sort of. Need to optimize the way how I consume the logs.
> To answer my own earlier question, the conflict-in check for posting
> trees is hidden in getFindLeafPage(..., true, ...).
>
> I spent some more time trying to grok this today. FTR it reproduces
> faster without the extra tuple that repro I posted inserts after
> TRUNCATE (the point of that was to find out whether it was an
> empty-to-non-empty transition). I still don't know what's wrong but I
> am beginning to suspect the "fast" code. It seems as though, under
> high concurrency, we sometimes don't scan a recently inserted
> (invisible to our snapshot, but needed for SSI checks) tuple, but I
> don't yet know why.
Yep, it's definitely something in the "fast" path. Testing the same, but
with an index having (fastupdate=off) works just fine for me.
^ permalink raw reply [nested|flat] 28+ messages in thread
* Re: BUG #17949: Adding an index introduces serialisation anomalies.
@ 2023-06-24 13:59 Dmitry Dolgov <9erthalion6@gmail.com>
parent: Dmitry Dolgov <9erthalion6@gmail.com>
0 siblings, 1 reply; 28+ messages in thread
From: Dmitry Dolgov @ 2023-06-24 13:59 UTC (permalink / raw)
To: Thomas Munro <thomas.munro@gmail.com>; +Cc: artem.anisimov.255@gmail.com, pgsql-bugs@lists.postgresql.org, Teodor Sigaev <teodor@sigaev.ru>; Heikki Linnakangas <hlinnaka@iki.fi>
> On Fri, Jun 23, 2023 at 04:05:42PM +0200, Dmitry Dolgov wrote:
> > I spent some more time trying to grok this today. FTR it reproduces
> > faster without the extra tuple that repro I posted inserts after
> > TRUNCATE (the point of that was to find out whether it was an
> > empty-to-non-empty transition). I still don't know what's wrong but I
> > am beginning to suspect the "fast" code. It seems as though, under
> > high concurrency, we sometimes don't scan a recently inserted
> > (invisible to our snapshot, but needed for SSI checks) tuple, but I
> > don't yet know why.
>
> Yep, it's definitely something in the "fast" path. Testing the same, but
> with an index having (fastupdate=off) works just fine for me.
I've managed to resolve it, or at least reduce the chances for the issue to
appear, via semi-randomly adding more CheckForSerializableConflictIn /
PredicateLock around the new sublist that has to be created in
ginHeapTupleFastInsert. I haven't seen the reproducer failing with this
changeset after running it multiple times for a couple of minutes, where on the
main branch, with the two fixes from Thomas included, it was failing within a
couple of seconds.
diff --git a/src/backend/access/gin/ginfast.c b/src/backend/access/gin/ginfast.c
@@ -198,6 +199,7 @@ makeSublist(Relation index, IndexTuple *tuples, int32 ntuples,
/*
* Write last page
*/
+ CheckForSerializableConflictIn(index, NULL, BufferGetBlockNumber(curBuffer));
res->tail = BufferGetBlockNumber(curBuffer);
res->tailFreeSize = writeListPage(index, curBuffer,
@@ -273,6 +275,11 @@ ginHeapTupleFastInsert(GinState *ginstate, GinTupleCollector *collector)
separateList = true;
LockBuffer(metabuffer, GIN_UNLOCK);
}
+ else
+ {
+ CheckForSerializableConflictIn(index, NULL, metadata->head);
+ }
}
diff --git a/src/backend/access/gin/ginget.c b/src/backend/access/gin/ginget.c
@@ -140,7 +140,7 @@ collectMatchBitmap(GinBtreeData *btree, GinBtreeStack *stack,
* Predicate lock entry leaf page, following pages will be locked by
* moveRightIfItNeeded()
*/
- PredicateLockPage(btree->index, stack->buffer, snapshot);
+ PredicateLockPage(btree->index, BufferGetBlockNumber(stack->buffer), snapshot);
for (;;)
{
@@ -1925,6 +1926,8 @@ gingetbitmap(IndexScanDesc scan, TIDBitmap *tbm)
/*
* Set up the scan keys, and check for unsatisfiable query.
*/
+ PredicateLockRelation(scan->indexRelation, scan->xs_snapshot);
ginFreeScanKeys(so); /* there should be no keys yet, but just to be
Now the last PredicateLockRelation does look rather weird. But without it, or
with this locking happening in scanPendingInsert (instead of locking the meta
page), or without other changes in ginfast.c, the reproducer is still failing.
This of course makes it not a proper solution by any mean, but hopefully it
will help to understand the problem a bit better.
^ permalink raw reply [nested|flat] 28+ messages in thread
* Re: BUG #17949: Adding an index introduces serialisation anomalies.
@ 2023-06-26 00:25 Thomas Munro <thomas.munro@gmail.com>
parent: Dmitry Dolgov <9erthalion6@gmail.com>
0 siblings, 2 replies; 28+ messages in thread
From: Thomas Munro @ 2023-06-26 00:25 UTC (permalink / raw)
To: Dmitry Dolgov <9erthalion6@gmail.com>; +Cc: artem.anisimov.255@gmail.com, pgsql-bugs@lists.postgresql.org, Teodor Sigaev <teodor@sigaev.ru>; Heikki Linnakangas <hlinnaka@iki.fi>
On Sun, Jun 25, 2023 at 1:59 AM Dmitry Dolgov <9erthalion6@gmail.com> wrote:
> I've managed to resolve it, or at least reduce the chances for the issue to
> appear, via semi-randomly adding more CheckForSerializableConflictIn /
> PredicateLock around the new sublist that has to be created in
> ginHeapTupleFastInsert. I haven't seen the reproducer failing with this
> changeset after running it multiple times for a couple of minutes, where on the
> main branch, with the two fixes from Thomas included, it was failing within a
> couple of seconds.
Ahh, right, thanks. I don't think we need to lock all those pages as
you showed, as this whole "fast" path is supposed to be covered by the
meta page (in other words, GIN is expected to have the highest
possible serialisation failure rate under SSI unless you turn fast
updates off). But there is an ordering bug with the existing
predicate lock in that code, which allows this to happen:
S1: CheckForSerializableConflictIn(meta)
S2: PredicateLockPage(meta)
S2: scan, find no tuples
S1: BufferLock(EXCLUSIVE
S1: modify stuff...
CheckForSerializableConflictIn() was written with the assumption that
you're inserting a tuple (ie you have the page containing the tuple
locked), so you'll either conflict with a reader who already has a
predicate lock at that point OR you'll insert first and then the
reader will see your (invisible-to-snapshot) tuples, but here we're
doing some fancy footwork with a meta page, and we screwed up the
ordering and left a window where neither of those things happens.
Perhaps it was coded that way because there is drop-then-reacquire
dance, but it's easy enough to move the check in both branches. Does
that make sense?
Attachments:
[text/x-patch] v3-0001-Fix-race-in-SSI-interaction-with-empty-btrees.patch (2.6K, ../../CA+hUKGKmR57CgZAPRjeSQfXb_oxjSUx7673SqDRw9RF2FfCw=A@mail.gmail.com/2-v3-0001-Fix-race-in-SSI-interaction-with-empty-btrees.patch)
download | inline diff:
From 564b3472099ab9e61d8c108d5c8d1b3d6f5de423 Mon Sep 17 00:00:00 2001
From: Thomas Munro <thomas.munro@gmail.com>
Date: Mon, 19 Jun 2023 16:28:02 +1200
Subject: [PATCH v3 1/3] Fix race in SSI interaction with empty btrees.
When predicate-locking btrees, we have a special case for completely
empty btrees, since there is no page to lock. This was racy, because,
without buffer lock held, a matching key could be inserted between the
_bt_search() and the PredicateLockRelation() calls.
Fix, by rechecking _bt_search() after taking the relation-level SIREAD
lock, if using SERIALIZABLE isolation and an empty btree is discovered.
Back-patch to all supported releases.
Reported-by: Artem Anisimov <artem.anisimov.255@gmail.com>
Reviewed-by: Dmitry Dolgov <9erthalion6@gmail.com>
Discussion: https://postgr.es/m/17949-a0f17035294a55e2%40postgresql.org
---
src/backend/access/nbtree/nbtsearch.c | 39 +++++++++++++++++----------
1 file changed, 25 insertions(+), 14 deletions(-)
diff --git a/src/backend/access/nbtree/nbtsearch.c b/src/backend/access/nbtree/nbtsearch.c
index 7e05e58676..2477b7aefb 100644
--- a/src/backend/access/nbtree/nbtsearch.c
+++ b/src/backend/access/nbtree/nbtsearch.c
@@ -1381,23 +1381,34 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
if (!BufferIsValid(buf))
{
/*
- * We only get here if the index is completely empty. Lock relation
- * because nothing finer to lock exists.
+ * Since we have no pages locked, it's possible for another
+ * transaction to insert data between _bt_search() and
+ * PredicateLockRelation(). We have to try again after taking a
+ * relation-level predicate lock, to close a narrow window where we
+ * wouldn't scan concurrently inserted tuples, but the writer wouldn't
+ * see our predicate lock.
*/
- PredicateLockRelation(rel, scan->xs_snapshot);
-
- /*
- * mark parallel scan as done, so that all the workers can finish
- * their scan
- */
- _bt_parallel_done(scan);
- BTScanPosInvalidate(so->currPos);
+ if (IsolationIsSerializable())
+ {
+ PredicateLockRelation(rel, scan->xs_snapshot);
+ stack = _bt_search(rel, NULL, &inskey, &buf, BT_READ,
+ scan->xs_snapshot);
+ _bt_freestack(stack);
+ }
- return false;
+ if (!BufferIsValid(buf))
+ {
+ /*
+ * Mark parallel scan as done, so that all the workers can finish
+ * their scan.
+ */
+ _bt_parallel_done(scan);
+ BTScanPosInvalidate(so->currPos);
+ return false;
+ }
}
- else
- PredicateLockPage(rel, BufferGetBlockNumber(buf),
- scan->xs_snapshot);
+
+ PredicateLockPage(rel, BufferGetBlockNumber(buf), scan->xs_snapshot);
_bt_initialize_more_data(so, dir);
--
2.40.1
[text/x-patch] v3-0002-Fix-race-in-SSI-interaction-with-bitmap-heap-scan.patch (2.3K, ../../CA+hUKGKmR57CgZAPRjeSQfXb_oxjSUx7673SqDRw9RF2FfCw=A@mail.gmail.com/3-v3-0002-Fix-race-in-SSI-interaction-with-bitmap-heap-scan.patch)
download | inline diff:
From 8b93cbf472c2d4e3182a41e362b242d0b4d1b57d Mon Sep 17 00:00:00 2001
From: Thomas Munro <thomas.munro@gmail.com>
Date: Tue, 20 Jun 2023 11:08:54 +1200
Subject: [PATCH v3 2/3] Fix race in SSI interaction with bitmap heap scan.
When performing a bitmap heap scan, we don't want to miss concurrent
writes that occurred after we observed the heap's rs_nblocks, but before
we took predicate locks on index pages. Therefore, we can't skip
fetching any heap tuples that are referenced by the index, because we
need to test them all with CheckForSerializableConflictOut(). The
old optimization that would ignore any references to blocks >=
rs_nblocks gets in the way of that requirement, because it means that
concurrent writes in that window are ignored.
Removing that optimization shouldn't affect correctness at any isolation
level, because any new tuples shouldn't be visible to an MVCC snapshot.
There also shouldn't be any error-causing references to heap blocks past
the end, because we should have held at least an AccessShareLock on the
table before the index scan. It can't get smaller while our transaction
is running.
Back-patch to all supported releases. In release 11, the removed code
is in a different location due to the table AM refactoring in commit
bfbcad47, but not fundamentally different.
Reported-by: Artem Anisimov <artem.anisimov.255@gmail.com>
Reviewed-by: Dmitry Dolgov <9erthalion6@gmail.com>
Discussion: https://postgr.es/m/17949-a0f17035294a55e2%40postgresql.org
---
src/backend/access/heap/heapam_handler.c | 9 ---------
1 file changed, 9 deletions(-)
diff --git a/src/backend/access/heap/heapam_handler.c b/src/backend/access/heap/heapam_handler.c
index 0755be8390..b41de7e3e1 100644
--- a/src/backend/access/heap/heapam_handler.c
+++ b/src/backend/access/heap/heapam_handler.c
@@ -2128,15 +2128,6 @@ heapam_scan_bitmap_next_block(TableScanDesc scan,
hscan->rs_cindex = 0;
hscan->rs_ntuples = 0;
- /*
- * Ignore any claimed entries past what we think is the end of the
- * relation. It may have been extended after the start of our scan (we
- * only hold an AccessShareLock, and it could be inserts from this
- * backend).
- */
- if (block >= hscan->rs_nblocks)
- return false;
-
/*
* Acquire pin on the target heap page, trading in any pin we held before.
*/
--
2.40.1
[text/x-patch] v3-0003-Fix-race-in-SSI-interaction-with-gin-fast-path.patch (2.9K, ../../CA+hUKGKmR57CgZAPRjeSQfXb_oxjSUx7673SqDRw9RF2FfCw=A@mail.gmail.com/4-v3-0003-Fix-race-in-SSI-interaction-with-gin-fast-path.patch)
download | inline diff:
From 4b8632a93e3f38e606963e892e76bd268c1b5e21 Mon Sep 17 00:00:00 2001
From: Thomas Munro <thomas.munro@gmail.com>
Date: Mon, 26 Jun 2023 11:43:37 +1200
Subject: [PATCH v3 3/3] Fix race in SSI interaction with gin fast path.
The ginfast.c code previously checked for conflicts in before locking
the relevant buffer, leaving a window where a RW conflict could be
missed.
There was also a place where buffer ID and block number were confused
while trying to predicate-lock a page, noted by visual inspection.
Back-patch to all supported releases.
Reported-by: Dmitry Dolgov <9erthalion6@gmail.com>
Discussion: https://postgr.es/m/17949-a0f17035294a55e2%40postgresql.org
---
src/backend/access/gin/ginfast.c | 10 ++++++++--
src/backend/access/gin/ginget.c | 4 +++-
2 files changed, 11 insertions(+), 3 deletions(-)
diff --git a/src/backend/access/gin/ginfast.c b/src/backend/access/gin/ginfast.c
index ca7d770d86..c6524f759c 100644
--- a/src/backend/access/gin/ginfast.c
+++ b/src/backend/access/gin/ginfast.c
@@ -245,9 +245,10 @@ ginHeapTupleFastInsert(GinState *ginstate, GinTupleCollector *collector)
/*
* An insertion to the pending list could logically belong anywhere in the
* tree, so it conflicts with all serializable scans. All scans acquire a
- * predicate lock on the metabuffer to represent that.
+ * predicate lock on the metabuffer to represent that. Therefore we'll
+ * check for conflicts in, but not until we have the page locked and are
+ * ready to modify the page.
*/
- CheckForSerializableConflictIn(index, NULL, GIN_METAPAGE_BLKNO);
if (collector->sumsize + collector->ntuples * sizeof(ItemIdData) > GinListPageSize)
{
@@ -291,6 +292,8 @@ ginHeapTupleFastInsert(GinState *ginstate, GinTupleCollector *collector)
LockBuffer(metabuffer, GIN_EXCLUSIVE);
metadata = GinPageGetMeta(metapage);
+ CheckForSerializableConflictIn(index, NULL, GIN_METAPAGE_BLKNO);
+
if (metadata->head == InvalidBlockNumber)
{
/*
@@ -310,6 +313,7 @@ ginHeapTupleFastInsert(GinState *ginstate, GinTupleCollector *collector)
}
else
{
+
/*
* Merge lists
*/
@@ -353,6 +357,8 @@ ginHeapTupleFastInsert(GinState *ginstate, GinTupleCollector *collector)
char *ptr;
char *collectordata;
+ CheckForSerializableConflictIn(index, NULL, GIN_METAPAGE_BLKNO);
+
buffer = ReadBuffer(index, metadata->tail);
LockBuffer(buffer, GIN_EXCLUSIVE);
page = BufferGetPage(buffer);
diff --git a/src/backend/access/gin/ginget.c b/src/backend/access/gin/ginget.c
index cb676a710f..1f0214498c 100644
--- a/src/backend/access/gin/ginget.c
+++ b/src/backend/access/gin/ginget.c
@@ -140,7 +140,9 @@ collectMatchBitmap(GinBtreeData *btree, GinBtreeStack *stack,
* Predicate lock entry leaf page, following pages will be locked by
* moveRightIfItNeeded()
*/
- PredicateLockPage(btree->index, stack->buffer, snapshot);
+ PredicateLockPage(btree->index,
+ BufferGetBlockNumber(stack->buffer),
+ snapshot);
for (;;)
{
--
2.40.1
^ permalink raw reply [nested|flat] 28+ messages in thread
* Re: BUG #17949: Adding an index introduces serialisation anomalies.
@ 2023-06-26 02:52 Peter Geoghegan <pg@bowt.ie>
parent: Thomas Munro <thomas.munro@gmail.com>
1 sibling, 1 reply; 28+ messages in thread
From: Peter Geoghegan @ 2023-06-26 02:52 UTC (permalink / raw)
To: Thomas Munro <thomas.munro@gmail.com>; +Cc: Dmitry Dolgov <9erthalion6@gmail.com>; artem.anisimov.255@gmail.com, pgsql-bugs@lists.postgresql.org, Teodor Sigaev <teodor@sigaev.ru>; Heikki Linnakangas <hlinnaka@iki.fi>
On Sun, Jun 25, 2023 at 5:26 PM Thomas Munro <thomas.munro@gmail.com> wrote:
> CheckForSerializableConflictIn() was written with the assumption that
> you're inserting a tuple (ie you have the page containing the tuple
> locked), so you'll either conflict with a reader who already has a
> predicate lock at that point OR you'll insert first and then the
> reader will see your (invisible-to-snapshot) tuples, but here we're
> doing some fancy footwork with a meta page, and we screwed up the
> ordering and left a window where neither of those things happens.
FWIW, there is no fundamental reason why nbtree couldn't always
preallocate a single empty leaf page during CREATE INDEX -- this leaf
page is where values whose keyspace is between negative and positive
infinity (i.e. all items) are located. That would fix this bug. Since,
of course, it would make the theory of operation that you describe
work reliably, even with an empty index. This isn't a serious
proposal, of course -- lazily allocating the first real page has
value, and we're hardly going to throw that away just to fix this bug.
My point is that not allocating a leaf page in CREATE INDEX is the
special case here, if anything.
I'm not surprised that GIN has deeper problems than nbtree due to
things like posting trees. Many GIN features rely on the fact that GIN
only supports lossy index scans. For example, it doesn't matter if the
pending list has TIDs that appear elsewhere within the same index for
a while. It doesn't matter if you have a hard crash when merging the
pending list -- VACUUM will eventually clean everything up. Having the
same TID in two different places at the same time is tolerable. I
imagine that that kind of foundation is harder to build SSI predicate
locks on top of.
--
Peter Geoghegan
^ permalink raw reply [nested|flat] 28+ messages in thread
* Re: BUG #17949: Adding an index introduces serialisation anomalies.
@ 2023-06-26 08:04 Heikki Linnakangas <hlinnaka@iki.fi>
parent: Thomas Munro <thomas.munro@gmail.com>
1 sibling, 1 reply; 28+ messages in thread
From: Heikki Linnakangas @ 2023-06-26 08:04 UTC (permalink / raw)
To: Thomas Munro <thomas.munro@gmail.com>; Dmitry Dolgov <9erthalion6@gmail.com>; +Cc: artem.anisimov.255@gmail.com, pgsql-bugs@lists.postgresql.org, Teodor Sigaev <teodor@sigaev.ru>
On 26/06/2023 03:25, Thomas Munro wrote:
> On Sun, Jun 25, 2023 at 1:59 AM Dmitry Dolgov <9erthalion6@gmail.com> wrote:
>> I've managed to resolve it, or at least reduce the chances for the issue to
>> appear, via semi-randomly adding more CheckForSerializableConflictIn /
>> PredicateLock around the new sublist that has to be created in
>> ginHeapTupleFastInsert. I haven't seen the reproducer failing with this
>> changeset after running it multiple times for a couple of minutes, where on the
>> main branch, with the two fixes from Thomas included, it was failing within a
>> couple of seconds.
>
> Ahh, right, thanks. I don't think we need to lock all those pages as
> you showed, as this whole "fast" path is supposed to be covered by the
> meta page (in other words, GIN is expected to have the highest
> possible serialisation failure rate under SSI unless you turn fast
> updates off). But there is an ordering bug with the existing
> predicate lock in that code, which allows this to happen:
>
> S1: CheckForSerializableConflictIn(meta)
>
> S2: PredicateLockPage(meta)
> S2: scan, find no tuples
>
> S1: BufferLock(EXCLUSIVE
> S1: modify stuff...
>
> CheckForSerializableConflictIn() was written with the assumption that
> you're inserting a tuple (ie you have the page containing the tuple
> locked), so you'll either conflict with a reader who already has a
> predicate lock at that point OR you'll insert first and then the
> reader will see your (invisible-to-snapshot) tuples, but here we're
> doing some fancy footwork with a meta page, and we screwed up the
> ordering and left a window where neither of those things happens.
> Perhaps it was coded that way because there is drop-then-reacquire
> dance, but it's easy enough to move the check in both branches. Does
> that make sense?
Yes, +1 on the patches. Any chance of constructing test cases for these?
The above race condition is hard to reach, but some of these other bugs
seem more testable.
Some minor nits: In
v3-0001-Fix-race-in-SSI-interaction-with-empty-btrees.patch:
> /*
> - * We only get here if the index is completely empty. Lock relation
> - * because nothing finer to lock exists.
> + * Since we have no pages locked, it's possible for another
> + * transaction to insert data between _bt_search() and
> + * PredicateLockRelation(). We have to try again after taking a
> + * relation-level predicate lock, to close a narrow window where we
> + * wouldn't scan concurrently inserted tuples, but the writer wouldn't
> + * see our predicate lock.
> */
I'd like to keep the old comment here, it's good context, and add the
new text in addition to the old.
v3-0002-Fix-race-in-SSI-interaction-with-bitmap-heap-scan.patch: Can we
keep the optimization when not using SSI?
--
Heikki Linnakangas
Neon (https://neon.tech)
^ permalink raw reply [nested|flat] 28+ messages in thread
* Re: BUG #17949: Adding an index introduces serialisation anomalies.
@ 2023-06-26 23:48 Thomas Munro <thomas.munro@gmail.com>
parent: Peter Geoghegan <pg@bowt.ie>
0 siblings, 0 replies; 28+ messages in thread
From: Thomas Munro @ 2023-06-26 23:48 UTC (permalink / raw)
To: Peter Geoghegan <pg@bowt.ie>; +Cc: Dmitry Dolgov <9erthalion6@gmail.com>; artem.anisimov.255@gmail.com, pgsql-bugs@lists.postgresql.org, Teodor Sigaev <teodor@sigaev.ru>; Heikki Linnakangas <hlinnaka@iki.fi>
On Mon, Jun 26, 2023 at 2:53 PM Peter Geoghegan <pg@bowt.ie> wrote:
> FWIW, there is no fundamental reason why nbtree couldn't always
> preallocate a single empty leaf page during CREATE INDEX -- this leaf
> page is where values whose keyspace is between negative and positive
> infinity (i.e. all items) are located. That would fix this bug. Since,
> of course, it would make the theory of operation that you describe
> work reliably, even with an empty index. This isn't a serious
> proposal, of course -- lazily allocating the first real page has
> value, and we're hardly going to throw that away just to fix this bug.
> My point is that not allocating a leaf page in CREATE INDEX is the
> special case here, if anything.
I did briefly wonder about creating the root page on demand here
(probably with a bogus use of BT_WRITE or something like that),
which'd be pretty much equivalent to what you're suggesting there
except it'd work for existing empty indexes in the wild, but I wasn't
sure what complications that might have and didn't look further once I
thought of the 0001 patch's approach.
^ permalink raw reply [nested|flat] 28+ messages in thread
* Re: BUG #17949: Adding an index introduces serialisation anomalies.
@ 2023-06-28 03:18 Thomas Munro <thomas.munro@gmail.com>
parent: Heikki Linnakangas <hlinnaka@iki.fi>
0 siblings, 2 replies; 28+ messages in thread
From: Thomas Munro @ 2023-06-28 03:18 UTC (permalink / raw)
To: Heikki Linnakangas <hlinnaka@iki.fi>; +Cc: Dmitry Dolgov <9erthalion6@gmail.com>; artem.anisimov.255@gmail.com, pgsql-bugs@lists.postgresql.org, Teodor Sigaev <teodor@sigaev.ru>
On Mon, Jun 26, 2023 at 8:04 PM Heikki Linnakangas <hlinnaka@iki.fi> wrote:
> Yes, +1 on the patches. Any chance of constructing test cases for these?
Thanks for looking. I can't think of any good way to test
deterministically. All three depend on unlucky scheduling. Perhaps
if we had one of those 'pause insertion' systems that I have heard
talk of.
> > /*
> > - * We only get here if the index is completely empty. Lock relation
> > - * because nothing finer to lock exists.
> > + * Since we have no pages locked, it's possible for another
> > + * transaction to insert data between _bt_search() and
> > + * PredicateLockRelation(). We have to try again after taking a
> > + * relation-level predicate lock, to close a narrow window where we
> > + * wouldn't scan concurrently inserted tuples, but the writer wouldn't
> > + * see our predicate lock.
> > */
>
> I'd like to keep the old comment here, it's good context, and add the
> new text in addition to the old.
Done.
> v3-0002-Fix-race-in-SSI-interaction-with-bitmap-heap-scan.patch: Can we
> keep the optimization when not using SSI?
Done.
I'll push these in a couple of days if there are no further comments.
Attachments:
[text/x-patch] v4-0001-Fix-race-in-SSI-interaction-with-empty-btrees.patch (2.7K, ../../CA+hUKGKmrBFy-Z7XTHv6o5EV7WEhoscyTqyf=LTBeGjNoYnOkA@mail.gmail.com/2-v4-0001-Fix-race-in-SSI-interaction-with-empty-btrees.patch)
download | inline diff:
From a324fcd59ec61975e3635b2a50a2b8efb3dbeb8e Mon Sep 17 00:00:00 2001
From: Thomas Munro <thomas.munro@gmail.com>
Date: Mon, 19 Jun 2023 16:28:02 +1200
Subject: [PATCH v4 1/3] Fix race in SSI interaction with empty btrees.
When predicate-locking btrees, we have a special case for completely
empty btrees, since there is no page to lock. This was racy, because,
without buffer lock held, a matching key could be inserted between the
_bt_search() and the PredicateLockRelation() calls.
Fix, by rechecking _bt_search() after taking the relation-level SIREAD
lock, if using SERIALIZABLE isolation and an empty btree is discovered.
Back-patch to all supported releases. Fixes one aspect of bug #17949.
Reported-by: Artem Anisimov <artem.anisimov.255@gmail.com>
Reviewed-by: Dmitry Dolgov <9erthalion6@gmail.com>
Reviewed-by: Heikki Linnakangas <hlinnaka@iki.fi>
Discussion: https://postgr.es/m/17949-a0f17035294a55e2%40postgresql.org
---
src/backend/access/nbtree/nbtsearch.c | 38 ++++++++++++++++++---------
1 file changed, 25 insertions(+), 13 deletions(-)
diff --git a/src/backend/access/nbtree/nbtsearch.c b/src/backend/access/nbtree/nbtsearch.c
index 7e05e58676..0879b6730f 100644
--- a/src/backend/access/nbtree/nbtsearch.c
+++ b/src/backend/access/nbtree/nbtsearch.c
@@ -1382,22 +1382,34 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
{
/*
* We only get here if the index is completely empty. Lock relation
- * because nothing finer to lock exists.
+ * because nothing finer to lock exists. Without a buffer lock, it's
+ * possible for another transaction to insert data between
+ * _bt_search() and PredicateLockRelation(). We have to try again
+ * after taking the relation-level predicate lock, to close a narrow
+ * window where we wouldn't scan concurrently inserted tuples, but the
+ * writer wouldn't see our predicate lock.
*/
- PredicateLockRelation(rel, scan->xs_snapshot);
-
- /*
- * mark parallel scan as done, so that all the workers can finish
- * their scan
- */
- _bt_parallel_done(scan);
- BTScanPosInvalidate(so->currPos);
+ if (IsolationIsSerializable())
+ {
+ PredicateLockRelation(rel, scan->xs_snapshot);
+ stack = _bt_search(rel, NULL, &inskey, &buf, BT_READ,
+ scan->xs_snapshot);
+ _bt_freestack(stack);
+ }
- return false;
+ if (!BufferIsValid(buf))
+ {
+ /*
+ * Mark parallel scan as done, so that all the workers can finish
+ * their scan.
+ */
+ _bt_parallel_done(scan);
+ BTScanPosInvalidate(so->currPos);
+ return false;
+ }
}
- else
- PredicateLockPage(rel, BufferGetBlockNumber(buf),
- scan->xs_snapshot);
+
+ PredicateLockPage(rel, BufferGetBlockNumber(buf), scan->xs_snapshot);
_bt_initialize_more_data(so, dir);
--
2.39.2
[text/x-patch] v4-0002-Fix-race-in-SSI-interaction-with-bitmap-heap-scan.patch (2.5K, ../../CA+hUKGKmrBFy-Z7XTHv6o5EV7WEhoscyTqyf=LTBeGjNoYnOkA@mail.gmail.com/3-v4-0002-Fix-race-in-SSI-interaction-with-bitmap-heap-scan.patch)
download | inline diff:
From 910e7df5274906c84baf012f4f99c04233ac660c Mon Sep 17 00:00:00 2001
From: Thomas Munro <thomas.munro@gmail.com>
Date: Tue, 20 Jun 2023 11:08:54 +1200
Subject: [PATCH v4 2/3] Fix race in SSI interaction with bitmap heap scan.
When performing a bitmap heap scan, we don't want to miss concurrent
writes that occurred after we observed the heap's rs_nblocks, but before
we took predicate locks on index pages. Therefore, we can't skip
fetching any heap tuples that are referenced by the index, because we
need to test them all with CheckForSerializableConflictOut(). The
old optimization that would ignore any references to blocks >=
rs_nblocks gets in the way of that requirement, because it means that
concurrent writes in that window are ignored.
Removing that optimization shouldn't affect correctness at any isolation
level, because any new tuples shouldn't be visible to an MVCC snapshot.
There also shouldn't be any error-causing references to heap blocks past
the end, because we should have held at least an AccessShareLock on the
table before the index scan. It can't get smaller while our transaction
is running. For now, though, we'll keep the optimization at lower
levels.
Back-patch to all supported releases. In release 11, the code is in a
different place but not fundamentally different. Fixes one aspect of
bug #17949.
Reported-by: Artem Anisimov <artem.anisimov.255@gmail.com>
Reviewed-by: Dmitry Dolgov <9erthalion6@gmail.com>
Reviewed-by: Heikki Linnakangas <hlinnaka@iki.fi>
Discussion: https://postgr.es/m/17949-a0f17035294a55e2%40postgresql.org
---
src/backend/access/heap/heapam_handler.c | 6 ++++--
1 file changed, 4 insertions(+), 2 deletions(-)
diff --git a/src/backend/access/heap/heapam_handler.c b/src/backend/access/heap/heapam_handler.c
index 0755be8390..5a17112c91 100644
--- a/src/backend/access/heap/heapam_handler.c
+++ b/src/backend/access/heap/heapam_handler.c
@@ -2132,9 +2132,11 @@ heapam_scan_bitmap_next_block(TableScanDesc scan,
* Ignore any claimed entries past what we think is the end of the
* relation. It may have been extended after the start of our scan (we
* only hold an AccessShareLock, and it could be inserts from this
- * backend).
+ * backend). We don't take this optimization in SERIALIZABLE isolation
+ * though, as we need to examine all invisible tuples reachable by the
+ * index.
*/
- if (block >= hscan->rs_nblocks)
+ if (!IsolationIsSerializable() && block >= hscan->rs_nblocks)
return false;
/*
--
2.39.2
[text/x-patch] v4-0003-Fix-race-in-SSI-interaction-with-gin-fast-path.patch (3.2K, ../../CA+hUKGKmrBFy-Z7XTHv6o5EV7WEhoscyTqyf=LTBeGjNoYnOkA@mail.gmail.com/4-v4-0003-Fix-race-in-SSI-interaction-with-gin-fast-path.patch)
download | inline diff:
From 8614733376bc9f3786218006a23716fe64f917ef Mon Sep 17 00:00:00 2001
From: Thomas Munro <thomas.munro@gmail.com>
Date: Mon, 26 Jun 2023 11:43:37 +1200
Subject: [PATCH v4 3/3] Fix race in SSI interaction with gin fast path.
The ginfast.c code previously checked for conflicts in before locking
the relevant buffer, leaving a window where a RW conflict could be
missed.
There was also a place where buffer ID and block number were confused
while trying to predicate-lock a page, noted by visual inspection.
Back-patch to all supported releases. Fixes one more problem discovered
by Dmitry with the reproducer from bug #17949 against other index types.
Reported-by: Artem Anisimov <artem.anisimov.255@gmail.com>
Reported-by: Dmitry Dolgov <9erthalion6@gmail.com>
Reviewed-by: Heikki Linnakangas <hlinnaka@iki.fi>
Discussion: https://postgr.es/m/17949-a0f17035294a55e2%40postgresql.org
---
src/backend/access/gin/ginfast.c | 10 ++++++++--
src/backend/access/gin/ginget.c | 4 +++-
2 files changed, 11 insertions(+), 3 deletions(-)
diff --git a/src/backend/access/gin/ginfast.c b/src/backend/access/gin/ginfast.c
index ca7d770d86..c6524f759c 100644
--- a/src/backend/access/gin/ginfast.c
+++ b/src/backend/access/gin/ginfast.c
@@ -245,9 +245,10 @@ ginHeapTupleFastInsert(GinState *ginstate, GinTupleCollector *collector)
/*
* An insertion to the pending list could logically belong anywhere in the
* tree, so it conflicts with all serializable scans. All scans acquire a
- * predicate lock on the metabuffer to represent that.
+ * predicate lock on the metabuffer to represent that. Therefore we'll
+ * check for conflicts in, but not until we have the page locked and are
+ * ready to modify the page.
*/
- CheckForSerializableConflictIn(index, NULL, GIN_METAPAGE_BLKNO);
if (collector->sumsize + collector->ntuples * sizeof(ItemIdData) > GinListPageSize)
{
@@ -291,6 +292,8 @@ ginHeapTupleFastInsert(GinState *ginstate, GinTupleCollector *collector)
LockBuffer(metabuffer, GIN_EXCLUSIVE);
metadata = GinPageGetMeta(metapage);
+ CheckForSerializableConflictIn(index, NULL, GIN_METAPAGE_BLKNO);
+
if (metadata->head == InvalidBlockNumber)
{
/*
@@ -310,6 +313,7 @@ ginHeapTupleFastInsert(GinState *ginstate, GinTupleCollector *collector)
}
else
{
+
/*
* Merge lists
*/
@@ -353,6 +357,8 @@ ginHeapTupleFastInsert(GinState *ginstate, GinTupleCollector *collector)
char *ptr;
char *collectordata;
+ CheckForSerializableConflictIn(index, NULL, GIN_METAPAGE_BLKNO);
+
buffer = ReadBuffer(index, metadata->tail);
LockBuffer(buffer, GIN_EXCLUSIVE);
page = BufferGetPage(buffer);
diff --git a/src/backend/access/gin/ginget.c b/src/backend/access/gin/ginget.c
index cb676a710f..1f0214498c 100644
--- a/src/backend/access/gin/ginget.c
+++ b/src/backend/access/gin/ginget.c
@@ -140,7 +140,9 @@ collectMatchBitmap(GinBtreeData *btree, GinBtreeStack *stack,
* Predicate lock entry leaf page, following pages will be locked by
* moveRightIfItNeeded()
*/
- PredicateLockPage(btree->index, stack->buffer, snapshot);
+ PredicateLockPage(btree->index,
+ BufferGetBlockNumber(stack->buffer),
+ snapshot);
for (;;)
{
--
2.39.2
^ permalink raw reply [nested|flat] 28+ messages in thread
* Re: BUG #17949: Adding an index introduces serialisation anomalies.
@ 2023-07-03 22:02 Thomas Munro <thomas.munro@gmail.com>
parent: Thomas Munro <thomas.munro@gmail.com>
1 sibling, 1 reply; 28+ messages in thread
From: Thomas Munro @ 2023-07-03 22:02 UTC (permalink / raw)
To: Heikki Linnakangas <hlinnaka@iki.fi>; +Cc: Dmitry Dolgov <9erthalion6@gmail.com>; artem.anisimov.255@gmail.com, pgsql-bugs@lists.postgresql.org, Teodor Sigaev <teodor@sigaev.ru>
On Wed, Jun 28, 2023 at 3:18 PM Thomas Munro <thomas.munro@gmail.com> wrote:
> I'll push these in a couple of days if there are no further comments.
Done.
Thanks Artem, Dmitry and Heikki.
I wonder how we might be more systematic about this. There are some
general principles that were not respected here, but I'm not sure if
they're even written down let alone defended with code. Something to
think about.
It's not great to add a new use of BufferGetBlockNumber() (in terms of
false sharing just to get a value that we must have had moment earlier
in order to pin the buffer), but we do that all the time. That seems
like a micro-optimisation worth looking into in some systematic way
across all AMs.
^ permalink raw reply [nested|flat] 28+ messages in thread
* Re: BUG #17949: Adding an index introduces serialisation anomalies.
@ 2023-07-14 13:05 Artem Anisimov <artem.anisimov.255@gmail.com>
parent: Thomas Munro <thomas.munro@gmail.com>
0 siblings, 1 reply; 28+ messages in thread
From: Artem Anisimov @ 2023-07-14 13:05 UTC (permalink / raw)
To: Thomas Munro <thomas.munro@gmail.com>; Heikki Linnakangas <hlinnaka@iki.fi>; +Cc: Dmitry Dolgov <9erthalion6@gmail.com>; pgsql-bugs@lists.postgresql.org, Teodor Sigaev <teodor@sigaev.ru>
Hi Thomas,
thank you for the fixes. I've looked up the patches in pg's git repo,
and they got me wondering: where is the repo with pg tests? I'd be
really uneasy to make changes to concurrency-related code without a
decent testsuite to verify them.
Best regards,
Artem.
On 04/07/2023 01:02, Thomas Munro wrote:
> On Wed, Jun 28, 2023 at 3:18 PM Thomas Munro <thomas.munro@gmail.com> wrote:
>> I'll push these in a couple of days if there are no further comments.
> Done.
>
> Thanks Artem, Dmitry and Heikki.
>
> I wonder how we might be more systematic about this. There are some
> general principles that were not respected here, but I'm not sure if
> they're even written down let alone defended with code. Something to
> think about.
>
> It's not great to add a new use of BufferGetBlockNumber() (in terms of
> false sharing just to get a value that we must have had moment earlier
> in order to pin the buffer), but we do that all the time. That seems
> like a micro-optimisation worth looking into in some systematic way
> across all AMs.
^ permalink raw reply [nested|flat] 28+ messages in thread
* Re: BUG #17949: Adding an index introduces serialisation anomalies.
@ 2023-07-16 22:04 Thomas Munro <thomas.munro@gmail.com>
parent: Artem Anisimov <artem.anisimov.255@gmail.com>
0 siblings, 0 replies; 28+ messages in thread
From: Thomas Munro @ 2023-07-16 22:04 UTC (permalink / raw)
To: Artem Anisimov <artem.anisimov.255@gmail.com>; +Cc: Heikki Linnakangas <hlinnaka@iki.fi>; Dmitry Dolgov <9erthalion6@gmail.com>; pgsql-bugs@lists.postgresql.org, Teodor Sigaev <teodor@sigaev.ru>
On Sat, Jul 15, 2023 at 1:05 AM Artem Anisimov
<artem.anisimov.255@gmail.com> wrote:
> thank you for the fixes. I've looked up the patches in pg's git repo,
> and they got me wondering: where is the repo with pg tests? I'd be
> really uneasy to make changes to concurrency-related code without a
> decent testsuite to verify them.
Generally, the tests for SSI are in:
https://git.postgresql.org/gitweb/?p=postgresql.git;a=tree;f=src/test/isolation/specs
... and see also ../expected. Typically they are created as features
are developed, but we'll add new tests to cover complicated bugfixes
if we can see how to do it. There are also non-SSI related tests in
there because the "isolation" infrastructure turned out to be so
useful.
For the problems discovered in this thread, I couldn't see how to do
it. These required unlucky scheduling to go wrong -- whereas the
existing test infrastructure is based on deterministic behaviour with
wait points at the statement level. It has been suggested before that
we could perhaps have a way to insert test-harness-controlled
waitpoints. But even if we had such infrastructure, the relevant wait
points are actually gone after the fixes (ie the window where you have
to do something in another thread to cause problems has been closed so
there is no candidate wait point left). Such infrastructure might
have been useful for demonstrating the bugs deterministically while
the windows existed. One of the basic techniques we often use when
trying to understand what is going on in such cases is to insert
sleeps into interesting places to widen windows and make failures
"almost" deterministic, as I did for one of the cases here.
I suppose we could in theory have a suite of 'high load' tests of a
more statistical nature that could include things like the repro you
sent in. It would burn a whole bunch of CPU trying to break
complicated concurrency stuff in ways that have been known to be
broken in the past. I'm not sure it's worth it though. Sometimes
it's OK for tests to be temporarily useful, too...
^ permalink raw reply [nested|flat] 28+ messages in thread
* Re: BUG #17949: Adding an index introduces serialisation anomalies.
@ 2026-07-19 19:53 Peter Geoghegan <pg@bowt.ie>
parent: Thomas Munro <thomas.munro@gmail.com>
1 sibling, 0 replies; 28+ messages in thread
From: Peter Geoghegan @ 2026-07-19 19:53 UTC (permalink / raw)
To: Thomas Munro <thomas.munro@gmail.com>; +Cc: Heikki Linnakangas <hlinnaka@iki.fi>; Dmitry Dolgov <9erthalion6@gmail.com>; artem.anisimov.255@gmail.com, pgsql-bugs@lists.postgresql.org, Teodor Sigaev <teodor@sigaev.ru>
On Tue, Jun 27, 2023 at 11:18 PM Thomas Munro <thomas.munro@gmail.com> wrote:
> I'll push these in a couple of days if there are no further comments.
I spotted an oversight in this fix: scans that use no scan keys (i.e.,
full index scans, or the first primscan used during a skip scan) will
go through _bt_endpoint, which lacks the _bt_first handling that you
added to the end of _bt_first (which will never be reached). You need
a second copy of the empty tree handling in _bt_endpoint.
Attached bug fix shows what I mean.
There's a second patch that adds an isolation test that would have
caught the original problem, as well as this still-overlooked
_bt_endpoint variant. When this fix went in we didn't have injection
points. Now we do, which makes testing these kinds of scenarios
straightforward.
--
Peter Geoghegan
Attachments:
[application/octet-stream] v1-0001-Fix-race-in-SSI-interaction-with-empty-btrees.patch (1.9K, ../../CAH2-WzkNoTn3yXY0iGkSuavJ+sL8EROf+kitW+_2v2tJVWuKmA@mail.gmail.com/2-v1-0001-Fix-race-in-SSI-interaction-with-empty-btrees.patch)
download | inline diff:
From 6d351fff68a3ed0bf80df917b57c52f9e8a1cee3 Mon Sep 17 00:00:00 2001
From: Peter Geoghegan <pg@bowt.ie>
Date: Sun, 19 Jul 2026 14:37:30 -0400
Subject: [PATCH v1 1/2] Fix race in SSI interaction with empty btrees.
Commit f9b7fc65 fixed a race when predicate-locking completely empty
btrees: without a buffer lock held, a matching key could be inserted
between _bt_search() and the PredicateLockRelation() call, so the scan
would miss concurrently inserted tuples while the writer wouldn't see
the reader's predicate lock.
That commit only fixed _bt_first's _bt_search path, though. Scans
without useful insertion scan keys return early from _bt_first via
_bt_endpoint, which still didn't recheck if the relation was empty.
To fix, add handling to _bt_endpoint that is analogous to the handling
added to _bt_search by commit f9b7fc65.
---
src/backend/access/nbtree/nbtsearch.c | 19 ++++++++++++++-----
1 file changed, 14 insertions(+), 5 deletions(-)
diff --git a/src/backend/access/nbtree/nbtsearch.c b/src/backend/access/nbtree/nbtsearch.c
index aae6acb7f..dfcdd2d4c 100644
--- a/src/backend/access/nbtree/nbtsearch.c
+++ b/src/backend/access/nbtree/nbtsearch.c
@@ -2195,12 +2195,21 @@ _bt_endpoint(IndexScanDesc scan, ScanDirection dir)
if (!BufferIsValid(so->currPos.buf))
{
/*
- * Empty index. Lock the whole relation, as nothing finer to lock
- * exists.
+ * Empty index. Lock the whole relation using the approach explained
+ * at the same point in the _bt_first path.
*/
- PredicateLockRelation(rel, scan->xs_snapshot);
- _bt_parallel_done(scan);
- return false;
+ if (IsolationIsSerializable())
+ {
+ PredicateLockRelation(rel, scan->xs_snapshot);
+ so->currPos.buf = _bt_get_endpoint(rel, 0,
+ ScanDirectionIsBackward(dir));
+ }
+
+ if (!BufferIsValid(so->currPos.buf))
+ {
+ _bt_parallel_done(scan);
+ return false;
+ }
}
page = BufferGetPage(so->currPos.buf);
--
2.53.0
[application/octet-stream] v1-0002-Add-empty-nbtree-index-SSI-tests.patch (8.2K, ../../CAH2-WzkNoTn3yXY0iGkSuavJ+sL8EROf+kitW+_2v2tJVWuKmA@mail.gmail.com/3-v1-0002-Add-empty-nbtree-index-SSI-tests.patch)
download | inline diff:
From 4eef7b6380af90616031637feb0321616abb4fb1 Mon Sep 17 00:00:00 2001
From: Peter Geoghegan <pg@bowt.ie>
Date: Sun, 19 Jul 2026 15:43:12 -0400
Subject: [PATCH v1 2/2] Add empty nbtree index SSI tests.
---
src/backend/access/nbtree/nbtsearch.c | 12 +++
src/test/modules/injection_points/Makefile | 1 +
.../expected/btree-empty-ssi.out | 99 +++++++++++++++++++
src/test/modules/injection_points/meson.build | 1 +
.../specs/btree-empty-ssi.spec | 76 ++++++++++++++
5 files changed, 189 insertions(+)
create mode 100644 src/test/modules/injection_points/expected/btree-empty-ssi.out
create mode 100644 src/test/modules/injection_points/specs/btree-empty-ssi.spec
diff --git a/src/backend/access/nbtree/nbtsearch.c b/src/backend/access/nbtree/nbtsearch.c
index dfcdd2d4c..cab370eab 100644
--- a/src/backend/access/nbtree/nbtsearch.c
+++ b/src/backend/access/nbtree/nbtsearch.c
@@ -18,10 +18,12 @@
#include "access/nbtree.h"
#include "access/relscan.h"
#include "access/xact.h"
+#include "catalog/catalog.h"
#include "executor/instrument_node.h"
#include "miscadmin.h"
#include "pgstat.h"
#include "storage/predicate.h"
+#include "utils/injection_point.h"
#include "utils/lsyscache.h"
#include "utils/rel.h"
@@ -1516,6 +1518,11 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
{
Assert(!so->needPrimScan);
+#ifdef USE_INJECTION_POINTS
+ if (!IsCatalogRelation(rel))
+ INJECTION_POINT("btree-first-empty", NULL);
+#endif
+
/*
* We only get here if the index is completely empty. Lock relation
* because nothing finer to lock exists. Without a buffer lock, it's
@@ -2194,6 +2201,11 @@ _bt_endpoint(IndexScanDesc scan, ScanDirection dir)
if (!BufferIsValid(so->currPos.buf))
{
+#ifdef USE_INJECTION_POINTS
+ if (!IsCatalogRelation(rel))
+ INJECTION_POINT("btree-endpoint-empty", NULL);
+#endif
+
/*
* Empty index. Lock the whole relation using the approach explained
* at the same point in the _bt_first path.
diff --git a/src/test/modules/injection_points/Makefile b/src/test/modules/injection_points/Makefile
index c01d2fb09..1782d20dc 100644
--- a/src/test/modules/injection_points/Makefile
+++ b/src/test/modules/injection_points/Makefile
@@ -13,6 +13,7 @@ REGRESS = injection_points hashagg reindex_conc vacuum
REGRESS_OPTS = --dlpath=$(top_builddir)/src/test/regress
ISOLATION = basic \
+ btree-empty-ssi \
inplace \
repack \
repack_temporal \
diff --git a/src/test/modules/injection_points/expected/btree-empty-ssi.out b/src/test/modules/injection_points/expected/btree-empty-ssi.out
new file mode 100644
index 000000000..309458ffb
--- /dev/null
+++ b/src/test/modules/injection_points/expected/btree-empty-ssi.out
@@ -0,0 +1,99 @@
+Parsed test spec with 2 sessions
+
+starting permutation: s1_begin s2_begin s1_scan_first s2_scan s2_insert s2_commit s2_wakeup_first s1_insert s1_commit s2_detach
+injection_points_attach
+-----------------------
+
+(1 row)
+
+step s1_begin:
+ BEGIN ISOLATION LEVEL SERIALIZABLE;
+ SET LOCAL enable_seqscan = off;
+ SET LOCAL enable_bitmapscan = off;
+
+step s2_begin: BEGIN ISOLATION LEVEL SERIALIZABLE;
+step s1_scan_first: SELECT id FROM ssi_btree WHERE id = 2; <waiting ...>
+step s2_scan: SELECT id FROM ssi_btree;
+id
+--
+(0 rows)
+
+step s2_insert: INSERT INTO ssi_btree VALUES (2);
+step s2_commit: COMMIT;
+step s2_wakeup_first: SELECT injection_points_wakeup('btree-first-empty');
+injection_points_wakeup
+-----------------------
+
+(1 row)
+
+step s1_scan_first: <... completed>
+id
+--
+(0 rows)
+
+step s1_insert: INSERT INTO ssi_btree VALUES (1);
+ERROR: could not serialize access due to read/write dependencies among transactions
+step s1_commit: COMMIT;
+step s2_detach:
+ SELECT injection_points_detach('btree-first-empty');
+ SELECT injection_points_detach('btree-endpoint-empty');
+
+injection_points_detach
+-----------------------
+
+(1 row)
+
+injection_points_detach
+-----------------------
+
+(1 row)
+
+
+starting permutation: s1_begin s2_begin s1_scan_endpoint s2_scan s2_insert s2_commit s2_wakeup_endpoint s1_insert s1_commit s2_detach
+injection_points_attach
+-----------------------
+
+(1 row)
+
+step s1_begin:
+ BEGIN ISOLATION LEVEL SERIALIZABLE;
+ SET LOCAL enable_seqscan = off;
+ SET LOCAL enable_bitmapscan = off;
+
+step s2_begin: BEGIN ISOLATION LEVEL SERIALIZABLE;
+step s1_scan_endpoint: SELECT id FROM ssi_btree ORDER BY id; <waiting ...>
+step s2_scan: SELECT id FROM ssi_btree;
+id
+--
+(0 rows)
+
+step s2_insert: INSERT INTO ssi_btree VALUES (2);
+step s2_commit: COMMIT;
+step s2_wakeup_endpoint: SELECT injection_points_wakeup('btree-endpoint-empty');
+injection_points_wakeup
+-----------------------
+
+(1 row)
+
+step s1_scan_endpoint: <... completed>
+id
+--
+(0 rows)
+
+step s1_insert: INSERT INTO ssi_btree VALUES (1);
+ERROR: could not serialize access due to read/write dependencies among transactions
+step s1_commit: COMMIT;
+step s2_detach:
+ SELECT injection_points_detach('btree-first-empty');
+ SELECT injection_points_detach('btree-endpoint-empty');
+
+injection_points_detach
+-----------------------
+
+(1 row)
+
+injection_points_detach
+-----------------------
+
+(1 row)
+
diff --git a/src/test/modules/injection_points/meson.build b/src/test/modules/injection_points/meson.build
index 59dba1cb0..a466ce110 100644
--- a/src/test/modules/injection_points/meson.build
+++ b/src/test/modules/injection_points/meson.build
@@ -44,6 +44,7 @@ tests += {
'isolation': {
'specs': [
'basic',
+ 'btree-empty-ssi',
'inplace',
'repack',
'repack_temporal',
diff --git a/src/test/modules/injection_points/specs/btree-empty-ssi.spec b/src/test/modules/injection_points/specs/btree-empty-ssi.spec
new file mode 100644
index 000000000..91b115f49
--- /dev/null
+++ b/src/test/modules/injection_points/specs/btree-empty-ssi.spec
@@ -0,0 +1,76 @@
+# Test SSI's handling of concurrent insertions into an initially empty
+# btree index.
+#
+# When predicate-locking a completely empty btree there is no page to
+# lock, so we lock the whole relation instead. This was racy: without a
+# buffer lock held, a concurrent transaction can insert a matching key
+# between the descent that found the index empty and the
+# PredicateLockRelation() call. The scan then misses the inserted tuple,
+# but the writer doesn't see the reader's predicate lock either, allowing
+# a write skew anomaly to go undetected.
+
+setup
+{
+ CREATE EXTENSION injection_points;
+ CREATE TABLE ssi_btree (id int PRIMARY KEY);
+}
+
+teardown
+{
+ DROP TABLE ssi_btree;
+ DROP EXTENSION injection_points;
+}
+
+session s1
+setup {
+ SELECT injection_points_set_local();
+ SELECT injection_points_attach('btree-first-empty', 'wait');
+ SELECT injection_points_attach('btree-endpoint-empty', 'wait');
+}
+step s1_begin {
+ BEGIN ISOLATION LEVEL SERIALIZABLE;
+ SET LOCAL enable_seqscan = off;
+ SET LOCAL enable_bitmapscan = off;
+}
+# Scan with a useful insertion scan key: descends via _bt_first/_bt_search.
+step s1_scan_first { SELECT id FROM ssi_btree WHERE id = 2; }
+# Scan without useful insertion scan keys: starts at _bt_endpoint().
+step s1_scan_endpoint { SELECT id FROM ssi_btree ORDER BY id; }
+step s1_insert { INSERT INTO ssi_btree VALUES (1); }
+step s1_commit { COMMIT; }
+
+session s2
+step s2_begin { BEGIN ISOLATION LEVEL SERIALIZABLE; }
+step s2_scan { SELECT id FROM ssi_btree; }
+step s2_insert { INSERT INTO ssi_btree VALUES (2); }
+step s2_commit { COMMIT; }
+step s2_wakeup_first { SELECT injection_points_wakeup('btree-first-empty'); }
+step s2_wakeup_endpoint { SELECT injection_points_wakeup('btree-endpoint-empty'); }
+step s2_detach {
+ SELECT injection_points_detach('btree-first-empty');
+ SELECT injection_points_detach('btree-endpoint-empty');
+}
+
+# _bt_first()/_bt_search() path
+permutation s1_begin
+ s2_begin
+ s1_scan_first
+ s2_scan
+ s2_insert
+ s2_commit
+ s2_wakeup_first
+ s1_insert
+ s1_commit
+ s2_detach
+
+# _bt_endpoint() path
+permutation s1_begin
+ s2_begin
+ s1_scan_endpoint
+ s2_scan
+ s2_insert
+ s2_commit
+ s2_wakeup_endpoint
+ s1_insert
+ s1_commit
+ s2_detach
--
2.53.0
^ permalink raw reply [nested|flat] 28+ messages in thread
end of thread, other threads:[~2026-07-19 19:53 UTC | newest]
Thread overview: 28+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2023-05-28 12:26 BUG #17949: Adding an index introduces serialisation anomalies. PG Bug reporting form <noreply@postgresql.org>
2023-05-30 01:29 ` Thomas Munro <thomas.munro@gmail.com>
2023-06-13 08:00 ` Artem Anisimov <artem.anisimov.255@gmail.com>
2023-06-15 00:12 ` Thomas Munro <thomas.munro@gmail.com>
2023-06-15 07:29 ` Dmitry Dolgov <9erthalion6@gmail.com>
2023-06-16 23:22 ` Thomas Munro <thomas.munro@gmail.com>
2023-06-19 02:29 ` Thomas Munro <thomas.munro@gmail.com>
2023-06-19 03:23 ` Thomas Munro <thomas.munro@gmail.com>
2023-06-19 06:50 ` Thomas Munro <thomas.munro@gmail.com>
2023-06-19 09:30 ` Thomas Munro <thomas.munro@gmail.com>
2023-06-19 12:17 ` Dmitry Dolgov <9erthalion6@gmail.com>
2023-06-20 01:22 ` Thomas Munro <thomas.munro@gmail.com>
2023-06-20 22:54 ` Thomas Munro <thomas.munro@gmail.com>
2023-06-20 23:20 ` Thomas Munro <thomas.munro@gmail.com>
2023-06-21 09:04 ` Dmitry Dolgov <9erthalion6@gmail.com>
2023-06-22 10:02 ` Thomas Munro <thomas.munro@gmail.com>
2023-06-23 14:05 ` Dmitry Dolgov <9erthalion6@gmail.com>
2023-06-24 13:59 ` Dmitry Dolgov <9erthalion6@gmail.com>
2023-06-26 00:25 ` Thomas Munro <thomas.munro@gmail.com>
2023-06-26 02:52 ` Peter Geoghegan <pg@bowt.ie>
2023-06-26 23:48 ` Thomas Munro <thomas.munro@gmail.com>
2023-06-26 08:04 ` Heikki Linnakangas <hlinnaka@iki.fi>
2023-06-28 03:18 ` Thomas Munro <thomas.munro@gmail.com>
2023-07-03 22:02 ` Thomas Munro <thomas.munro@gmail.com>
2023-07-14 13:05 ` Artem Anisimov <artem.anisimov.255@gmail.com>
2023-07-16 22:04 ` Thomas Munro <thomas.munro@gmail.com>
2026-07-19 19:53 ` Peter Geoghegan <pg@bowt.ie>
2023-06-21 08:58 ` Dmitry Dolgov <9erthalion6@gmail.com>
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox