Ubuntu – Serialization failure on very simple insert scenario in Postgres

When trying to use SERIALIZABLE transactions in PostgreSQL, I’m hitting very unexpected serialization failures on the simplest possible access patterns: SELECT row to see if it exists, and then INSERT when it doesn’t.

To set the background:

--psql (14.10 (Ubuntu 14.10-0ubuntu0.22.04.1), server 16.1 (Debian 16.1-1.pgdg120+1))
create table kv(
  key TEXT NOT NULL PRIMARY KEY, 
  value TEXT);

Now, we run the following transactions in two terminals:

Terminal 1:

begin isolation level serializable read write;
SET enable_seqscan=off;

select value from kv where key = 'a';--(0 rows)
insert into kv(key, value) values ('a', 'vala');--INSERT 0 1
commit;--COMMIT

Terminal 2:

begin isolation level serializable read write;
SET enable_seqscan=off;

select value from kv where key = 'b';--(0 rows)
insert into kv(key, value) values ('b', 'valb');--INSERT 0 1
commit;

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

The above reproduces for me 100% consistently, as long as the order of operations is:

1. begin transaction in 1st term
2. begin transaction in 2nd term
3. select in 1st
4. select in 2nd
5. insert in 1st
6. insert in 2nd
7. commit in 1st
8. commit in 2nd

After step 6), before commits, the pg_locks looks like this

select nspname, relname, l.* 
from pg_locks l 
    join pg_class c on (relation = c.oid) 
    join pg_namespace nsp on (c.relnamespace = nsp.oid)
where pid in (select pid 
              from pg_stat_activity
              where datname = current_database() 
                and query != current_query());

Interestingly, if instead of interleaving selects and inserts in different transactions, I do select and insert in first transaction, and then select and insert in the other, both of them successfully commit. The pre-commit locks then look as follows:

Note how instead of two relation SIReadLocks, we have one relation and one page lock.

I already bumped the max_pred_locks_per_*:

show all;

Questions:

1. Just as a sanity check: logically speaking, these two transactions are obviously serializable, and this is just Postgres being unable to prove it to itself, right?
2. Why is Postgres failing to see it? Why does it take two relation locks on the private key index?
3. Why does select-select-insert-insert order fail, but select-insert-select-insert order work?
4. What can I do to make such an obvious and simple access pattern work? I’m clearly touching non-overlapping sets of keys in both transaction, so there should be a practical way to make it work, I hope.