提升 PostgreSQL 中 Count 的速度-Linuxeden开源社区

分析 PostgreSQL 中可用于不同情况的优化技术，并了解如何在分布式数据库中的进行并行计数。人人都进行优化计数 – 但并不总是很快。本文将仔细研究 PostgreSQL 如何优化计数。如果你知道这些技巧，那么有一些方法进行计数可以比你更快速。问题实际上还没被识别 – 这有几种计数方式，每种都有自己的方法。首先，你要考虑是否需要确切的计数，或者估算计数。然后，检查是计数重复数据或仅计数不同的值？最后，你想要整个表的一个块数，还是想只计算符合额外条件的那些行？我们将分析每种情况的可用技术，并比较其速度和资源消耗。在学习单个数据库的技术后，我们将使用 Citus 来演示如何在分布式数据库中的并行计数。

准备用于测试的数据库

下面的部分会使用这个表作为测试基准。

-- create a million random numbers and strings
CREATE TABLE items AS
  SELECT
    (random()*1000000)::integer AS n,
    md5(random()::text) AS s
  FROM
    generate_series(1,1000000);
-- inform planner of big table size change
VACUUM ANALYZE;

包含重复数据的计数

我们来看看精确计数和估计计数。

精确计数

我们从头开始。精确计算允许表中有部分重复甚至全都重复 —— 是好的老办法 count(*)。测量运行此命令的时间，用作其它类型的计数速度的参照。 pgbench 提供了一个便捷的方法来重复执行一个查询并统计性能。

# Tests in this article were run against PostgreSQL 9.5.4
echo "SELECT count(*) FROM items;" | pgbench -d count -t 50 -P 1 -f -
# average  84.915 ms
# stddev    5.251 ms

关于 count(1) 和 count(*) 比较的说明：有人会认为 count(1) 会更快，因为 count(*) 看起来遍历了整行。然而实事却并非如此。星号在这里没有意义，这与 SELECT * 中的星号不同。PostgreSQL 将 count(*) 表达式解析为特殊情况，表示没有参数。(历史上这个表达式应该被定义为 count())。另一方面，count(1) 有一个参数，PostgreSQL 不会用这个参数去检查每一行，1，实际表示非空(NULL)。

用 count(1) 运行上面的测试基准，结果是：

# average  98.896 ms
# stddev    7.280 ms

不过，count(1) 和 count(*) 这两个形式从根本上来说都很慢。PostgreSQL 使用多版本并发控制 (MVCC) 来保证并发事务之间的一致性。这就是说，每个事务可以看到表中 —— 不同的行 —— 以及不同的行数。数据库不能缓存单一的普通行计数，所以它必须遍历检查所有行来统计有多少行可见。精确统计性能[译者注：这里指耗时]与表尺寸增长成线性关系。

EXPLAIN SELECT count(*) FROM items;
Aggregate  (cost=20834.00..20834.01 rows=1 width=0)
  ->  Seq Scan on items  (cost=0.00..18334.00 rows=1000000 width=0)

扫描消耗占总消耗的 88%。如果我们的表尺寸翻倍，查询时间大约增加一倍，扫描和聚合消耗都根据对方按比例增长。

行数	平均时间
1M	85ms
2M	161ms
4M	343ms

我们要怎么才能提高速度呢？这必须要有所付出。我们可以采用估算计数而不是精确计数，或者通过手工递增/递减计数并缓存起来。然而，对于第二种情况，我们必须为每个表和每个 where 子句保存计数器，以便后面进行快速计数。

这里有一个关于计数器方法的示例，它应用于整个 items 表。下面基于触发器的解决方案改编自 A. Elein Mustain。PostgreSQL 的 MVCC 会维护 items 表和保存行数的表之间的一致性。

BEGIN;
CREATE TABLE row_counts (
  relname   text PRIMARY KEY,
  reltuples bigint
);
-- establish initial count
INSERT INTO row_counts (relname, reltuples)
  VALUES ('items', (SELECT count(*) from items));
CREATE OR REPLACE FUNCTION adjust_count()
RETURNS TRIGGER AS
$
   DECLARE
   BEGIN
   IF TG_OP = 'INSERT' THEN
      EXECUTE 'UPDATE row_counts set reltuples=reltuples +1 where relname = ''' || TG_RELNAME || '''';
      RETURN NEW;
   ELSIF TG_OP = 'DELETE' THEN
      EXECUTE 'UPDATE row_counts set reltuples=reltuples -1 where relname = ''' || TG_RELNAME || '''';
      RETURN OLD;
   END IF;
   END;
$
LANGUAGE 'plpgsql';
CREATE TRIGGER items_count BEFORE INSERT OR DELETE ON items
  FOR EACH ROW EXECUTE PROCEDURE adjust_count();
COMMIT;

读取和更新缓存值的速度不受表尺寸影响，而且读取会非常快。不过，这个技术会把开销转嫁到插入 (insert) 和删除 (delete) 操作。没有触发器的情况下，下面的语句大约需要 4.7 秒，而使用了触发器的插入操作会慢50倍：

INSERT INTO items (n, s)
  SELECT
    (random()*1000000)::integer AS n,
    md5(random()::text) AS s
  FROM generate_series(1,1000000);

估算计数

我们来看看完整的表估算和筛选过的表估算。

完整表估算

前面缓存“计数器”的方法会让插入变慢。如果我们可以接受估算计数而不是精确计数，我们就可以在不减弱插入的情况下像计数器一样迅速获取计数值。我们可以依靠来自 PostgreSQL 子系统的估算聚集。两个来源分别是统计采集器和自动清理守护。这里是获取估算的两种选择：

-- Asking the stats collector
SELECT n_live_tup
  FROM pg_stat_all_tables
 WHERE relname = 'items';
-- Updated by VACUUM and ANALYZE
SELECT reltuples
  FROM pg_class
 WHERE relname = 'items';

然而，越准确的来源越不可能是陈旧的。Andrew Gierth (RhodiumToad) 建议：

记住 reltuples 并不是估计实际使用的计划器；计划器使用 reltuples/relpages 乘以当前页数。

这是直觉。随着表中数据样本的增加，物理页面中拟合的平均行数可能比总行数的变化更为彻底。我们可以通过用每页的平均行数乘以当前页数的最新信息，以获得更精确的估算当前行数。

-- pg_relation_size and block size have fresh info so combine them with
-- the estimation of tuples per page
SELECT
  (reltuples/relpages) * (
    pg_relation_size('items') /
    (current_setting('block_size')::integer)
  )
  FROM pg_class where relname = 'items';

过滤表评估

上一节讲了整表行数评估，但是有没有一种方法来获得带条件的行数? Michael Fuhr 想出了一个聪明的技巧来运行 EXPLAIN 进行查询并解析其输出行数。

CREATE FUNCTION count_estimate(query text) RETURNS integer AS $
DECLARE
  rec   record;
  rows  integer;
BEGIN
  FOR rec IN EXECUTE 'EXPLAIN ' || query LOOP
    rows := substring(rec."QUERY PLAN" FROM ' rows=([[:digit:]]+)');
    EXIT WHEN rows IS NOT NULL;
  END LOOP;
  RETURN rows;
END;
$ LANGUAGE plpgsql VOLATILE STRICT;

我们可以使用这样的函数：

SELECT count_estimate('SELECT 1 FROM items WHERE n < 1000');

该方法的准确性依赖于使用几种技术来估计 where 子句的选择性，并从中返回行数。

去重计数（无重复）

我们来看看准确的计数和预估的计数。

精确计数

我们来看看低内存，自定义聚合，HashAggregate 和仅索引扫描下的默认行为。

低内存下的默认行为

重复计数可能很慢，但去重计数明显更糟。由于工作内存有限，没有索引，PostgreSQL 无法优化。在其库存配置中，PostgreSQL 为每个并发查询（work_mem）指定了一个低内存限制。在我的开发机器上，默认是四兆字节。使用默认设置，这里是处理一百万行的性能情况。

echo "SELECT count(DISTINCT n) FROM items;" | pgbench -d count -t 50 -P 1 -f -
# average  742.855 ms
# stddev    21.907 ms
echo "SELECT count(DISTINCT s) FROM items;" | pgbench -d count -t 5 -P 1 -f -
# average  31747.337 ms
# stddev     267.183 ms

运行 EXPLAIN 显示大量查询发生在聚合中，并且在字符串列上运行计数的时间长于整数列：

-- plan for the integer column, n
Aggregate  (cost=20834.00..20834.01 rows=1 width=4) (actual time=860.620..860.620 rows=1 loops=1)
  Output: count(DISTINCT n)
  Buffers: shared hit=3904 read=4430, temp read=1467 written=1467
  ->  Seq Scan on public.items  (cost=0.00..18334.00 rows=1000000 width=4) (actual time=0.005..107.702 rows=1000000 loops=1)
        Output: n, s
        Buffers: shared hit=3904 read=4430
-- plan for the text column, s
Aggregate  (cost=20834.00..20834.01 rows=1 width=33) (actual time=31172.340..31172.340 rows=1 loops=1)
  Output: count(DISTINCT s)
  Buffers: shared hit=3936 read=4398, temp read=5111 written=5111
  ->  Seq Scan on public.items  (cost=0.00..18334.00 rows=1000000 width=33) (actual time=0.005..142.276 rows=1000000 loops=1)
        Output: n, s
        Buffers: shared hit=3936 read=4398

在聚集内部发生了什么？在输出中的描述信息是含糊的。我们可以通过分析相关查询来获得更多细节，选择使用 distinct 而不是 count distinct。

EXPLAIN (ANALYZE, VERBOSE) SELECT DISTINCT n FROM items;
Unique  (cost=131666.34..136666.34 rows=498824 width=4) (actual time=766.775..1229.040 rows=631846 loops=1)
  Output: n
  ->  Sort  (cost=131666.34..134166.34 rows=1000000 width=4) (actual time=766.774..1075.712 rows=1000000 loops=1)
        Output: n
        Sort Key: items.n
        Sort Method: external merge  Disk: 13632kB
        ->  Seq Scan on public.items  (cost=0.00..18334.00 rows=1000000 width=4) (actual time=0.006..178.153 rows=1000000 loops=1)
              Output: n

无需更多的 work_mem 或像索引这样的外部数据结构，PostgreSQL 合并-排序保存在内存和磁盘中的表，然后迭代结果并删除重复的内容，这很像经典的 Unix 命令组合 sort | uniq。排序会占用大部分查询时间，特别是如果我们选择字符串列 s 而不是整数列 n的情况下。在这两种情况下，唯一的过滤器会以相同的速度执行。

自定义聚合（Custom Aggregate）

Thomas Vondra 创建了一个自定义聚合，用于计数在固定长度类型的列中的不同值（另外，类型必须最多有 64 位）。无需任何额外的工作内存或索引，它会使用默认的基于排序的计数。安装步骤：

克隆该项目，tvondra/count_distinct
运行 make install
在你的数据库中执行：CREATE EXTENSION count_distinct;

Thomas 在此博客中解释了该聚合是如何工作的，但其简短的描述就是它在内存中构建了一个唯一元素的排序数组，并在运行时将其压缩。

echo "SELECT COUNT_DISTINCT(n) FROM items;" | pgbench -d count -t 50 -P 1 -f -
# average  434.726 ms
# stddev    19.955 ms

这击败了对唯一聚聚合的标准计数方法，其在我们的数据集上平均运行时间为 742 ms。请注意，用 C 编写的自定义扩展（如 count_distinct）不受 work_mem 的值约束。在这个扩展中构造的数组可能会超过你对内存使用的预期。

Hash 聚合（HashAggregate）

当要计数的所有行可以放到 work_mem 中时，PostgreSQL 使用一个哈希表来获取唯一值：提升 PostgreSQL 中 Count 的速度

SET work_mem='1GB';
EXPLAIN SELECT DISTINCT n FROM items;
HashAggregate  (cost=20834.00..25822.24 rows=498824 width=4)
  Group Key: n
  ->  Seq Scan on items  (cost=0.00..18334.00 rows=1000000 width=4)

到目前为止，这是最快的方式来获得唯一值的。对于 n，平均需要 372 ms，s 为 23 ms。查询选择唯一的 n 并且 select count（distinct n）大致使用相同的时间量运行，这表明计数唯一值的聚合在内部也使用了一个 HashAggregate。注意 – 设置足够高的内存容量来激活此方法可能是不可取的。请记住，work_mem 单独应用于所有并发查询，因此它可以累加。相信我们可以做得更好。

仅索引扫描

PostgreSQL 9.2 引入了这个性能特性。当索引包含查询所需的所有信息时，数据库就可以单独遍历索引，而不用访问任何常规表存储空间（“堆”）。索引类型必须支持仅索引扫描。Btree 索引总是满足该条件。GiST 和 SP-GiST 索引支持一些操作符类的仅索引扫描，而不支持其他类型。我们将使用 btree 索引，并为 n 和 s 列创建一个：

CREATE INDEX items_n_idx ON items USING btree (n);
CREATE INDEX items_s_idx ON items USING btree (s);

从这些列中筛选唯一值现在会使用新的策略：提升 PostgreSQL 中 Count 的速度

EXPLAIN SELECT DISTINCT n FROM items;
Unique  (cost=0.42..28480.42 rows=491891 width=4)
  ->  Index Only Scan using items_n_idx on items  (cost=0.42..25980.42 rows=1000000 width=4)

但现在我们遇到一个怪事。SELECT COUNT（DISTINCT n）FROM items 不会使用索引，然而 SELECT DISTINCT n 却会使用。许多博客文章提到（“一个奇葩技巧，让 postgres 快 50 倍！”），你可以通过以 count 子查询的形式重写 count 来辅助 planner 执行：

-- SELECT COUNT(DISTINCT n) FROM items;
-- must be rewritten as
EXPLAIN SELECT COUNT(*)
  FROM (SELECT DISTINCT n FROM items) t;
Aggregate  (cost=34629.06..34629.07 rows=1 width=0)
  ->  Unique  (cost=0.42..28480.42 rows=491891 width=4)
        ->  Index Only Scan using items_n_idx on items  (cost=0.42..25980.42 rows=1000000 width=4)

有序二叉树遍历速度很快。这个查询平均需要 177 ms（或者 s 列为 270 ms）。 警告: 当 work_mem 大到足够保存整个关系时，即使索引存在，PostgreSQL 也会选择 HashAggregate。矛盾的是，给数据库更多的内存资源可能导致更糟糕规划方案。你可以通过设置 SET enable_hashagg = false 来强制进行索引扫描；但记住要随后将其设置为 true，否则其他查询计划会被失败。

估计数量

我们只需要查看 HyperLogLog.

HyperLogLog

以前的技术依赖内存中的拟合索引，散列表或排序数组，或者从单个数据库实例查询的统计表。当数据在多个数据库实例之间变得非常大并且/或者在扩展时，这些技术就不奏效了。概率数据结构在这里就有帮助了 – 它提供了快速的近似解答，并且易于并行化。我们使用一个被称为 HyperLogLog（HLL）的基数估计器来查询唯一（distinct）记录的数量。它使用了少量内存来表示一组项目。对我们来说重要的是，它的联合操作是无损的，这意味着取任意 HLL 值的联合并不会降低估计精度。

HLL 背后的思想植根于一个好的散列函数的行为，特别是散列值之间的距离。一个函数分布均匀的值往往使他们最大程度的分开。随着更多的值被散列散开，越来越多的空间被占据，值更靠近在一起。通过跟踪散列值之间的一些最小距离，算法可以估计导致拥挤的哈希输入的可能数量。我们来测量速度。首先，安装 PostgreSQL 扩展。

克隆 postgresql-hll 项目
运行 make install
在您的数据库中输入：CREATE EXTENSION hll;

它表现出来的方式是提供一个快速聚合，作用于顺序扫描：

EXPLAIN SELECT #hll_add_agg(hll_hash_integer(n)) FROM items;
Aggregate  (cost=23334.00..23334.01 rows=1 width=4)
  ->  Seq Scan on items  (cost=0.00..18334.00 rows=1000000 width=4)

在 n 上不同的 HLL 计数的平均速度为 239 ms，s 为 284 ms。因此，对于该大小的数据，它比仅针对索引的扫描稍慢。它的真正厉害之处在于，HLL 联合是无损的，关联的和交换的。这意味着它们可以并行化服务器并合并出最终的结果。

并行

像进行实时分析的应用程序，例如：谷歌分析，使用了 count 的扩展——这是一种可以并行的 count 操作。这一节将会度量一些技术的性能，这些测试会被放在 Citus 云的一组小 Citus 集群上运行。一般的想法是通过多台机器来运行分立的数据库实例（worker）。这个实例共享一个 schema，而每个实例只承担整个数据集的一部分（分片）。所有的 worker 们会并行统计行数。

设置集群

在示例中，我们将创建小型集群，因为我们的目的是比较几种技术的性能改进，而不是谋求最终的基准化速度。对于这个例子，我在 Citus Cloud 上创建了一个八机集群，并为每个工作者选择了最低允许的硬件配置。如果你想自己尝试此示例，你可以注册一个帐户。创建集群后，我连接到协调器节点来运行 SQL。首先，像以前一样创建一个表。

CREATE TABLE items (
  n integer,
  s text
);

此时，表仅存在于协调器数据库中。我们需要在工作台上划分表，然后用行填充分片。 Citus 通过查看我们选择的“分配列”中的值，将每一行分配给一个唯一的分片。下面我们通过将它们的 n 列散列分配到分片中，将它们分散在 items 表中的未来行。

SELECT master_create_distributed_table('items', 'n', 'hash');
SELECT master_create_worker_shards('items', 32, 1);

我们将通过协调器节点将数据随机加载到分片中。（Citus 还支持 MX，一种“无主”模式，可以更快的加载数据，但这个示例不会用到这个模式）获取集群协调器数据库 URL 后，请在具有快速网络访问权限的计算机上运行以下操作。（所有生成的数据都将通过这台计算机，因此需要良好的网络速度。）

cat << EOF > randgen.sql
COPY (
    SELECT
      (random()*100000000)::integer AS n,
      md5(random()::text) AS s
    FROM
      generate_series(1,100000000)
  ) TO STDOUT;
EOF
psql $CITUS_URL -q -f randgen.sql | \
  psql $CITUS_URL -c "COPY items (n, s) FROM STDIN"

而在单数据库测试中我们使用了一百万行，这次我们把它改为了一亿。

精确计数（count）

让我们来看一下非唯一（non-distinct），去重（distinct）和预估唯一计数（estimated count distinct）。

非唯一（Non-Distinct）

简单非唯一计数 (non-distinct) 已经没有问题。协调者（coordinator）让所有工作者（worker）运行查询，然后将结果相加。输出的 EXPLAIN 显示计划关闭在一个典型的工作者（worker）(“Distributed Query”) 之后，并且计划被协调者（coordinator）使用到了。

EXPLAIN VERBOSE SELECT count(*) FROM items;
Distributed Query into pg_merge_job_0003
  Executor: Real-Time
  Task Count: 32
  Tasks Shown: One of 32
  ->  Task
        Node: host=*** port=5432 dbname=citus
        ->  Aggregate  (cost=65159.34..65159.35 rows=1 width=0)
              Output: count(*)
              ->  Seq Scan on public.items_102009 items  (cost=0.00..57340.27 rows=3127627 width=0)
                    Output: n, s
Master Query
  ->  Aggregate  (cost=0.00..0.02 rows=1 width=0)
        Output: (sum(intermediate_column_3_0))::bigint
        ->  Seq Scan on pg_temp_2.pg_merge_job_0003  (cost=0.00..0.00 rows=0 width=0)
              Output: intermediate_column_3_0

作为参考，计数（count）查询在此集群中平均执行时间是 1.2 秒。在分片上，进行唯去重计数（distinct count）会造成更为困难的问题。

Distinct

计算分片上列的不同值的困难在于碎片之间的复制，从而导致双重计数。但是，在计算分布列中的值时，这不是问题。此列中具有相同值的任何两行将被散列到相同的分片位置，并避免交叉分页重复。对于在分布列上计算非重复结果，Citus 知道将查询推送给每个工作者（worker），然后对结果进行求和。在我们的示例集群中，它的平均时间为 3.4 秒。更难的情况是对非分布列执行非唯一计算。逻辑上有两种可能性：

将所有行拉到协调器（coordinator）并在那里计数
在工作者（worker）之间重新排列，以避免工作者（worker）之间的列值重复，然后对每个工作者（worker）进行不同的计数，并在协调器（coordinator）上求和

第一个选项是真的不会对单个数据库实例的 count （计数）操作有更好的表现的——实际上，确实如此，因为增加了在网络上的消耗。第二个选项才是可行的方式。第二个选项被叫做“重新分配”。其想法是在工作者（worker）上使用一个新的分布式列来制作一张临时表。工作者（worker）彼此之间发送行以填充临时表，执行查询，并移除临时表。不同的分布式数据库在不同查询条件下执行重新分区。在 Citus 中的重新分类查询的具体细节超出了本文讨论的范围。

预测非重复结果的数目

像 HLL 这样的基数估计是分布式数据库中的“救世主”。它们允许系统对甚至没有网络开销的非分布列进行不同的计数。HLL 数据类型具有小字节大小，可以从工作者快速发送到协调器。因为合并操作是无损的，所以我们不用担心影响其精度的工作者数量。在 Citus 上，特别是你不需要显式调用 postgresql-hll。简单来说，citus.count_distinct_error_rate 为非零，Citus 将重写计算非重的查询计划来使用 HLL。例如：

SET citus.count_distinct_error_rate = 0.005;
EXPLAIN VERBOSE SELECT count(DISTINCT n) FROM items;
Distributed Query into pg_merge_job_0090
  Executor: Real-Time
  Task Count: 32
  Tasks Shown: One of 32
  ->  Task
        Node: host=*** port=5432 dbname=citus
        ->  Aggregate  (cost=72978.41..72978.42 rows=1 width=4)
              Output: hll_add_agg(hll_hash_integer(n, 0), 15)
              ->  Seq Scan on public.items_102009 items  (cost=0.00..57340.27 rows=3127627 width=4)
                    Output: n, s
Master Query
  ->  Aggregate  (cost=0.00..0.02 rows=1 width=0)
        Output: (hll_cardinality(hll_union_agg(intermediate_column_90_0)))::bigint
        ->  Seq Scan on pg_temp_2.pg_merge_job_0090  (cost=0.00..0.00 rows=0 width=0)
              Output: intermediate_column_90_0

这也很快：统计 n 个非重列的时间为 3.2 秒，在非分布列和字符串列中，统计 1 亿条记录为 3.8 秒。HLL 是在分布式数据库中横向扩展统计非重列的好方法。

英文原文：Faster PostgreSQL Counting

参与翻译 (5人) : Tocy, 无若, 亚林瓜子, 边城, 总长

转自 https://www.oschina.net/translate/faster-postgresql-counting

准备用于测试的数据库

包含重复数据的计数

精确计数

估算计数

完整表估算

过滤表评估

去重计数（无重复）

精确计数

低内存下的默认行为

自定义聚合（Custom Aggregate）

Hash 聚合（HashAggregate）

仅索引扫描

估计数量

HyperLogLog

并行

设置集群

精确计数（count）

非唯一（Non-Distinct）

Distinct

预测非重复结果的数目

相关推荐