BUG #13723: "duplicate key" error occurs when update delete and insert the same row concurrently

The following bug has been logged on the website:

Bug reference: 13723
Logged by: ChenHuajun
Email address: chjischj(at)163(dot)com
PostgreSQL version: 9.4.5
Operating system: CentOS 6
Description:

When i run sysbench's complex test with PostgreSQL, the following error
always occured.
duplicate key value violates unique constraint "%s"

It seems to be a bug which occurs when executing update,delete and
insert(within one transaction) the same row concurrently.

And i reproduced this issue via pgbench. Just as the following

1. prepare table & data
create table tb1(id int primary key,c int);
insert into tb1 values(1,1);

2. prepare test sql script
[postgres(at)localhost ~]$ cat test.sql
begin;
update tb1 set c=2 where id=1
delete from tb1 where id=1;
insert into tb1 values(1,2);
commit;

3. run test
[postgres(at)localhost ~]$ pgbench -n -f test.sql -c 2 -j 2 -t 2
client 1 aborted in state 3: ERROR: duplicate key value violates unique
constraint "tb1_pkey"
DETAIL: Key (id)=(1) already exists.
transaction type: Custom query
scaling factor: 1
query mode: simple
number of clients: 2
number of threads: 2
number of transactions per client: 2
number of transactions actually processed: 2/4
latency average: 0.000 ms
tps = 130.047467 (including connections establishing)
tps = 225.060485 (excluding connections establishing)

4. show log
[postgres(at)localhost ~]$ cat
pg95data/pg_log/postgresql-2015-10-25_141648.log
2015-10-25 14:16:48.144 EDT 57177 0 LOG: database system was shut down at
2015-10-25 14:16:47 EDT
2015-10-25 14:16:48.146 EDT 57177 0 LOG: MultiXact member wraparound
protections are now enabled
2015-10-25 14:16:48.149 EDT 57175 0 LOG: database system is ready to accept
connections
2015-10-25 14:16:48.150 EDT 57181 0 LOG: autovacuum launcher started
2015-10-25 14:16:57.960 EDT 57184 0 LOG: connection received: host=[local]
2015-10-25 14:16:57.961 EDT 57184 0 LOG: connection authorized:
user=postgres database=postgres
2015-10-25 14:16:57.971 EDT 57186 0 LOG: connection received: host=[local]
2015-10-25 14:16:57.971 EDT 57187 0 LOG: connection received: host=[local]
2015-10-25 14:16:57.972 EDT 57186 0 LOG: connection authorized:
user=postgres database=postgres
2015-10-25 14:16:57.972 EDT 57187 0 LOG: connection authorized:
user=postgres database=postgres
2015-10-25 14:16:57.975 EDT 57186 0 LOG: statement: begin;
2015-10-25 14:16:57.975 EDT 57186 0 LOG: statement: update tb1 set c=2
where id=1
2015-10-25 14:16:57.975 EDT 57187 0 LOG: statement: begin;
2015-10-25 14:16:57.976 EDT 57187 0 LOG: statement: update tb1 set c=2
where id=1
2015-10-25 14:16:57.978 EDT 57186 39682 LOG: statement: delete from tb1
where id=1;
2015-10-25 14:16:57.979 EDT 57186 39682 LOG: statement: insert into tb1
values(1,2);
2015-10-25 14:16:57.979 EDT 57186 39682 LOG: statement: commit;
2015-10-25 14:16:57.980 EDT 57186 0 LOG: statement: begin;
2015-10-25 14:16:57.981 EDT 57186 0 LOG: statement: update tb1 set c=2
where id=1
2015-10-25 14:16:57.981 EDT 57187 39683 LOG: statement: delete from tb1
where id=1;
2015-10-25 14:16:57.981 EDT 57186 39684 LOG: statement: delete from tb1
where id=1;//*ERROR!*, Both process 57186 and 57187 had excuted "update tb1
set c=2 where id=1" successfully at the same time.
2015-10-25 14:16:57.981 EDT 57186 39684 LOG: statement: insert into tb1
values(1,2);
2015-10-25 14:16:57.981 EDT 57186 39684 LOG: statement: commit;
2015-10-25 14:16:57.983 EDT 57187 39683 LOG: statement: insert into tb1
values(1,2);
2015-10-25 14:16:57.983 EDT 57187 39683 ERROR: duplicate key value violates
unique constraint "tb1_pkey"
2015-10-25 14:16:57.983 EDT 57187 39683 DETAIL: Key (id)=(1) already
exists.
2015-10-25 14:16:57.983 EDT 57187 39683 STATEMENT: insert into tb1
values(1,2);

I have tested PostgreSQL 9.3.1,9.4.5 and 9.5beta1,all of them has this
issue.