Why is performance non-linear if I do many UPDATEs in a single transaction
(Note: I point out that this question is unpractical. So, it is completely inappropriate in order to evaluate the performance of PostgreSQL.)

I guess it is caused by the MVCC mechanism of PostgreSQL.

As well known, PostgreSQL's MVCC is implemented in over-writing mechanism. I'll show a concrete example using the pageinspector extention bundled in contrib subdirectory.

First, I start a transaction and do the first UPDATE statement:


BEGIN;

SELECT lp as tuple, t_xmin, t_xmax, t_field3 as t_cid, t_ctid FROM heap_page_items(get_raw_page('foo', 0));
 tuple | t_xmin | t_xmax | t_cid | t_ctid 
-------+--------+--------+-------+--------
     1 |   2755 |      0 |     0 | (0,1)
(1 row)

UPDATE foo SET count=count+1 WHERE id=1;

SELECT lp as tuple, t_xmin, t_xmax, t_field3 as t_cid, t_ctid FROM heap_page_items(get_raw_page('foo', 0));
 tuple | t_xmin | t_xmax | t_cid | t_ctid 
-------+--------+--------+-------+--------
     1 |   2755 |   2756 |     0 | (0,2)
     2 |   2756 |      0 |     0 | (0,2)
(2 rows)


When updating the data,  PostgreSQL reads and updates the fields of the first tuple header (t_xmax and t_ctid),  and then inserts the new (second) tuple. 

Next, I do the second UPDATE statement:


UPDATE foo SET count=count+1 WHERE id=1;

SELECT lp as tuple, t_xmin, t_xmax, t_field3 as t_cid, t_ctid FROM heap_page_items(get_raw_page('foo', 0));
 tuple | t_xmin | t_xmax | t_cid | t_ctid 
-------+--------+--------+-------+--------
     1 |   2755 |   2756 |     0 | (0,2)
     2 |   2756 |   2756 |     0 | (0,3)
     3 |   2756 |      0 |     1 | (0,3)
(3 rows)


After reading the first tuple, PostgreSQL reads the second tuple since the t_ctid field of the first tuple points to the second tuple (0,2). And then, PostgreSQL updates the fields of the second one and inserts the third one.

In this way, when many UPDATE statements are issued in a single transaction,  PostgreSQL must read and update the header fields of old tuples whenever inserting a new tuple.

This is my hypothesis. An weakness of this hypothesis is that the processing time order is O(n^2), so this may be wrong (it seem that the result of that benchmark doesn't fit with O(n^2)).

In any case, doing many UPDATE statements in single transaction is not a good way because it makes many dead pages that contain only  dead tuples, so you have to do VACUUM FULL (not VACUUM).