如果我在单个事务中执行多次更新，为什么性能是非线性的

Question

一个较旧的问题涵盖了为什么单个事务中多个 INSERTS 的性能随着 INSERT 计数的增长而非线性的一些原因。

按照那里的一些建议，我一直在尝试优化在单个事务中运行多个更新。在实际场景中，我们正在批处理来自另一个系统的数据，但我有一个较小的场景进行测试。

鉴于 postgresql 9.5.1 上的这个表：

\d+ foo
                                         Table "public.foo"
 Column |  Type   |                    Modifiers                     | Storage | Stats target | Description 
--------+---------+--------------------------------------------------+---------+--------------+-------------
 id     | bigint  | not null default nextval('foo_id_seq'::regclass) | plain   |              | 
 count  | integer | not null                                         | plain   |              | 

我有以下的测试文件：100.sql，1000.sql，10000.sql，50000.sql和100000.sql。每个包含以下行，UPDATE根据文件名重复：

BEGIN;
UPDATE foo SET count=count+1 WHERE id=1;
...
UPDATE foo SET count=count+1 WHERE id=1;
COMMIT;  

当我对加载每个文件进行基准测试时，结果如下所示：

              user     system      total        real   ms/update
100       0.000000   0.010000   0.040000 (  0.044277)  0.44277
1000      0.000000   0.000000   0.040000 (  0.097175)  0.09717
10000     0.020000   0.020000   0.230000 (  1.717170)  0.17171
50000     0.160000   0.130000   1.840000 ( 30.991350)  0.61982
100000    0.440000   0.380000   5.320000 (149.199524)  1.49199

每个 UPDATE 的平均时间随着事务包含更多行而增加，这表明性能是非线性的。

我链接到的较早的问题表明索引可能是一个问题，但是该表没有索引并且只有一行。

这只是“这就是它的工作方式”的一种情况，还是我可以调整一些设置来改善这种情况？

更新

根据当前答案中的理论，我进行了额外的测试。表结构是相同的，但 UPDATE 都更改了不同的行。输入文件现在看起来像这样：

BEGIN;
UPDATE foo SET count=count+1 WHERE id=1;
UPDATE foo SET count=count+1 WHERE id=2;
...
UPDATE foo SET count=count+1 WHERE id=n;
COMMIT; 

当我对加载这些文件进行基准测试时，结果如下所示：

              user     system      total        real   ms/update
100       0.000000   0.000000   0.030000 (  0.044876)  0.44876
1000      0.010000   0.000000   0.050000 (  0.102998)  0.10299
10000     0.000000   0.040000   0.140000 (  0.666050)  0.06660
50000     0.070000   0.140000   0.550000 (  3.150734)  0.06301
100000    0.130000   0.280000   1.110000 (  6.458655)  0.06458

从 10,000 次更新开始（一旦设置成本被摊销），性能是线性的。

Answer 1

（注：我指出这个问题是不切实际的。所以，用它来评估PostgreSQL的性能是完全不合适的。）

我猜测是PostgreSQL的MVCC机制造成的。

众所周知，PostgreSQL的MVCC是通过覆盖机制实现的。我将展示一个使用pageinspectorcontrib 子目录中捆绑的扩展的具体示例。

首先，我启动一个事务并执行第一条UPDATE语句：

开始;

选择 lp 作为元组，t_xmin，t_xmax，t_field3 作为 t_cid，t_ctid FROM heap_page_items(get_raw_page('foo', 0));
 元组| t_xmin | t_xmax | t_cid | t_cid | t_ctid
-------+--------+--------+--------+--------
     1 | 2755 | 2755 0 | 0 | (0,1)
（1 行）

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

选择 lp 作为元组，t_xmin，t_xmax，t_field3 作为 t_cid，t_ctid FROM heap_page_items(get_raw_page('foo', 0));
 元组| t_xmin | t_xmax | t_cid | t_cid | t_ctid
-------+--------+--------+--------+--------
     1 | 2755 | 2755 2756 | 2756 0 | (0,2)
     2 | 2756 | 2756 0 | 0 | (0,2)
（2 行）

更新数据时，PostgreSQL 读取并更新第一个元组头的字段（t_xmax 和 t_ctid），然后插入新的（第二个）元组。

接下来我做第二个UPDATE声明：

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

选择 lp 作为元组，t_xmin，t_xmax，t_field3 作为 t_cid，t_ctid FROM heap_page_items(get_raw_page('foo', 0));
 元组| t_xmin | t_xmax | t_cid | t_cid | t_ctid
-------+--------+--------+--------+--------
     1 | 2755 | 2755 2756 | 2756 0 | (0,2)
     2 | 2756 | 2756 2756 | 2756 0 | (0,3)
     3 | 2756 | 2756 0 | 1 | (0,3)
（3行）

读取第一个元组后，PostgreSQL 会读取第二个元组，因为第一个元组的 t_ctid 字段指向第二个元组(0,2)。然后，PostgreSQL 更新第二个字段并插入第三个字段。

这样，当UPDATE在单个事务中发出许多语句时，PostgreSQL 每当插入新元组时都必须读取并更新旧元组的头字段。

这是我的假设。这个假设的一个弱点是处理时间顺序是 O(n^2)，所以这可能是错误的（看起来该基准测试的结果与 O(n^2) 不符）。

无论如何，UPDATE在单个事务中执行许多语句都不是一个好方法，因为它会产生许多仅包含死元组的死页，因此您必须这样做VACUUM FULL（而不是VACUUM）。