3.2 单表查询的代价估计_PostgreSQL技术内幕

PostgreSQL的查询优化是基于代价（Cost）的。代价是一个无量纲的值，它并不是一种绝对的性能指标，但可以作为比较各种操作代价时的相对性能指标。

costsize.c中的函数用于估算各种操作的代价。所有被执行器执行的操作都有着相应的代价函数。例如，函数cost_seqscan() 和 cost_index()分别用于估算顺序扫描和索引扫描的代价。

在PostgreSQL中有三种代价：启动（start-up） ， 运行（run） 和总和（total） 。总代价 是启动代价 和运行代价 的和；因此只有启动代价和运行代价是单独估计的。

启动代价（start-up） ：在读取到第一条元组前花费的代价，比如索引扫描节点的启动代价 就是读取目标表的索引页，取到第一个元组的代价
运行代价（run） ：获取全部元组的代价
总代价（total） ：前两者之和

EXPLAIN命令显示了每个操作的启动代价和总代价，下面是一个简单的例子：

testdb=# EXPLAIN SELECT * FROM tbl;
                       QUERY PLAN            
---------------------------------------------------------
 Seq Scan on tbl  (cost=0.00..145.00 rows=10000 width=8)
(1 row)

在第4行显示了顺序扫描的相关信息。代价部分包含了两个值：0.00和145.00。在本例中，启动代价和总代价分别为0.00和145.00。

在本节中，我们将详细介绍顺序扫描，索引扫描和排序操作的代价是如何估算的。在接下来的内容中，我们使用下面这个表及其索引作为例子。

testdb=# CREATE TABLE tbl (id int PRIMARY KEY, data int);
testdb=# CREATE INDEX tbl_data_idx ON tbl (data);
testdb=# INSERT INTO tbl SELECT generate_series(1,10000),generate_series(1,10000);
testdb=# ANALYZE;
testdb=# \d tbl
      Table "public.tbl"
 Column |  Type   | Modifiers 
--------+---------+-----------
 id     | integer | not null
 data   | integer | 
Indexes:
    "tbl_pkey" PRIMARY KEY, btree (id)
    "tbl_data_idx" btree (data)

3.2.1 顺序扫描

顺序扫描的代价是通过函数cost_seqscan()估计的。本节将研究顺序扫描代价是如何估计的，以下面的查询为例：

testdb=# SELECT * FROM tbl WHERE id < 8000;

在顺序扫描中，启动代价等于0，其中seq_page_cost，cpu_tuple_cost和cpu_operator_cost是在postgresql.conf 中配置的参数，默认值分别为1.0，0.01和0.0025。$ N_{\verb|tuple|}$

$N_{\verb|tuple|}$ 和$N_{\verb|page|}$ 分别是表中的元组总数与页面总数，这两个值可以使用以下查询获取。

testdb=# SELECT relpages, reltuples FROM pg_class WHERE relname = 'tbl';
 relpages | reltuples 
----------+-----------
       45 |     10000
(1 row)

$ \verb|total_cost| = 0.0 + 170.0 = 170.0$

作为验证，下面是该查询的EXPLAIN结果：

testdb=# EXPLAIN SELECT * FROM tbl WHERE id < 8000;
                       QUERY PLAN           
--------------------------------------------------------
 Seq Scan on tbl  (cost=0.00..170.00 rows=8000 width=8)
   Filter: (id < 8000)
(2 rows)

在第4行中可以看到，启动代价和总代价分别是0.00和170.0，且预计全表扫描返回行数为8000条（元组）。

在第5行显示了一个顺序扫描的过滤器Filter:(id < 8000)。更精确地说，它是一个表级过滤谓词（table level filter predicate） 。注意这种类型的过滤器只会在读取所有元组的时候使用，它并不会减少需要扫描的表页面数量。

从优化运行代价的角度来看，PostgreSQL假设所有的物理页都是从存储介质中获取的；即，PostgreSQL不会考虑扫描的页面是否来自共享缓冲区。

3.2.2 索引扫描

尽管PostgreSQL支持很多索引方法，比如B树，GiST，GIN和BRIN，不过索引扫描的代价估计都使用一个共用的代价函数：cost_index()。

本节将研究索引扫描的代价是如何估计的，以下列查询为例。

testdb=# SELECT id, data FROM tbl WHERE data < 240;

在估计该查询的代价之前，下面的查询能获取$N_{\verb|index|,\verb|page|}$和$N_{\verb|index|,\verb|tuple|}$的值：

testdb=# SELECT relpages, reltuples FROM pg_class WHERE relname = 'tbl_data_idx';
 relpages | reltuples 
----------+-----------
       30 |     10000
(1 row)

3.2.2.1 启动代价

索引扫描的启动代价就是读取索引页以访问目标表的第一条元组的代价，由下面的公式定义：其中$ H_{\verb|index|}$

$是索引树的高度。

在本例中，套用公式(3)，$N_{\verb|index,tuple|}$是10000；$H_{\verb|index|}$是1；$\verb|cpu_operator_cost|$是0.0025（默认值）。

3.2.2.2 运行代价

索引扫描的运行代价是表和索引的CPU代价与IO代价之和。

如果使用仅索引扫描，则不会估计table_cpu_cost与table_io_cost，仅索引扫描将在第七章堆内元组与仅索引扫描中介绍。

前三个代价（即index_cpu_cost，table_cpu_cost和index_io_cost）

以上公式中的cpu_index_tuple_cost和random_page_cost在postgresql.conf 中配置（默认值分别为0.005和4.0）。$\verb|qual_op_cost|$粗略来说就是索引求值的代价，默认值是0.0025，这里不再展开。选择率（Selectivity） 是一个0到1之间的浮点数，代表查询指定的WHERE子句在索引中搜索范围的比例。举个例子，$(\verb|Selectivity| × N_{\verb|tuple|})$就是需要读取的表元组数量，$(\verb|Selectivity| × N_{\verb|index|,\verb|tuple|})$就是需要读取的索引元组数量，诸如此类。

选择率（Selectivity）

查询谓词的选择率是通过直方图界值（histogram_bounds） 与高频值（Most Common Value, MCV） 估计的，这些信息都存储在系统目录pg_statistics中，并可通过pg_stats视图查询。这里通过一个具体的例子来简要介绍选择率的计算方法，细节可以参考官方文档。

表中每一列的高频值都在pg_stats视图的most_common_vals和most_common_freqs中成对存储。

高频值（most_common_vals） ：该列上最常出现的取值列表

高频值频率（most_common_freqs） ：高频值相应出现频率的列表

下面是一个简单的例子。表countries有两列：一列country存储国家名，一列continent存储该国所属大洲。
testdb=# \d countries
   Table "public.countries"
  Column   | Type | Modifiers 
-----------+------+-----------
 country   | text | 
 continent | text | 
Indexes:
    "continent_idx" btree (continent)

testdb=# SELECT continent, count(*) AS "number of countries", 
testdb-#     (count(*)/(SELECT count(*) FROM countries)::real) AS "number of countries / all countries"
testdb-#       FROM countries GROUP BY continent ORDER BY "number of countries" DESC;
   continent   | number of countries | number of countries / all countries 
---------------+---------------------+-------------------------------------
 Africa        |                  53 |                   0.274611398963731
 Europe        |                  47 |                   0.243523316062176
 Asia          |                  44 |                   0.227979274611399
 North America |                  23 |                   0.119170984455959
 Oceania       |                  14 |                  0.0725388601036269
 South America |                  12 |                  0.0621761658031088
(6 rows)
考虑下面的查询，该查询带有WHERE条件continent = 'Asia'。
testdb=# SELECT * FROM countries WHERE continent = 'Asia';
这时候，计划器使用continent列上的高频值来估计索引扫描的代价，列上的most_common_vals与 most_common_freqs如下所示：
testdb=# \x
Expanded display is on.
testdb=# SELECT most_common_vals, most_common_freqs FROM pg_stats 
testdb-#                  WHERE tablename = 'countries' AND attname='continent';
-[ RECORD 1 ]-----+-----------------------------------------------------------
most_common_vals  | {Africa,Europe,Asia,"North America",Oceania,"South America"}
most_common_freqs | {0.274611,0.243523,0.227979,0.119171,0.0725389,0.0621762}
与most_common_vals中Asia值对应的most_common_freqs为0.227979。因此0.227979会在估算中被用作选择率。

如果高频值不可用，就会使用目标列上的直方图界值来估计代价。

直方图值（histogram_bounds） 是一系列值，这些值将列上的取值划分为数量大致相同的若干个组。

下面是一个具体的例子。这是表tbl中data列上的直方图界值；
testdb=# SELECT histogram_bounds FROM pg_stats WHERE tablename = 'tbl' AND attname = 'data';
                                   histogram_bounds
------------------------------------------------------------------------------
 {1,100,200,300,400,500,600,700,800,900,1000,1100,1200,1300,1400,1500,1600,1700,1800,1900,2000,2100,
2200,2300,2400,2500,2600,2700,2800,2900,3000,3100,3200,3300,3400,3500,3600,3700,3800,3900,4000,4100,
4200,4300,4400,4500,4600,4700,4800,4900,5000,5100,5200,5300,5400,5500,5600,5700,5800,5900,6000,6100,
6200,6300,6400,6500,6600,6700,6800,6900,7000,7100,7200,7300,7400,7500,7600,7700,7800,7900,8000,8100,
8200,8300,8400,8500,8600,8700,8800,8900,9000,9100,9200,9300,9400,9500,9600,9700,9800,9900,10000}
(1 row)
默认情况下，直方图界值会将列上的取值划分入100个桶。图3.7展示了这些桶及其对应的直方图界值。桶从0开始编号，每个桶保存了（大致）相同数量的元组。直方图界值就是相应桶的边界。比如，直方图界值的第0个值是1，意即这是bucket_0中的最小值。第1个值是100，意即bucket_1中的最小值是100，等等。

图3.7 桶和直方图界值

然后本节例子中选择率计算如下所示。假设查询带有WHERE子句data < 240，而值240落在第二个桶中。在本例中可以通过线性插值推算出相应的选择率。因此查询中data列的选择率可以套用下面的公式计算：

$$ \verb|Selectivity| = \frac{2+(240-hb[2])/(hb[3]-hb[2])}{100}=\frac{2+(240-200)/(300-200)}{100}=\frac{2+40/100}{100}=0.024 \ (6)

$$

索引相关性（index correlation）

索引相关性是列值在物理上的顺序和逻辑上的顺序的统计相关性（引自官方文档）。索引相关性的取值范围从$-1$到$+1$。下面的例子有助于理解索引扫描和索引相关性的关系。

表tbl_corr有5个列：两个列为文本类型，三个列为整数类型。这三个整数列保存着从1到12的数字。在物理上表tbl_corr包含三个页，每页有4条元组。每个数字列有一个名如index_col_asc的索引。
testdb=# \d tbl_corr
    Table "public.tbl_corr"
  Column  |  Type   | Modifiers 
----------+---------+-----------
 col      | text    | 
 col_asc  | integer | 
 col_desc | integer | 
 col_rand | integer | 
 data     | text    |
Indexes:
    "tbl_corr_asc_idx" btree (col_asc)
    "tbl_corr_desc_idx" btree (col_desc)
    "tbl_corr_rand_idx" btree (col_rand)
testdb=# SELECT col,col_asc,col_desc,col_rand 
testdb-#                         FROM tbl_corr;
   col    | col_asc | col_desc | col_rand 
----------+---------+----------+----------
 Tuple_1  |       1 |       12 |        3
 Tuple_2  |       2 |       11 |        8
 Tuple_3  |       3 |       10 |        5
 Tuple_4  |       4 |        9 |        9
 Tuple_5  |       5 |        8 |        7
 Tuple_6  |       6 |        7 |        2
 Tuple_7  |       7 |        6 |       10
 Tuple_8  |       8 |        5 |       11
 Tuple_9  |       9 |        4 |        4
 Tuple_10 |      10 |        3 |        1
 Tuple_11 |      11 |        2 |       12
 Tuple_12 |      12 |        1 |        6
(12 rows)
这些列的索引相关性如下：
testdb=# SELECT tablename,attname, correlation FROM pg_stats WHERE tablename = 'tbl_corr';
 tablename | attname  | correlation 
-----------+----------+-------------
 tbl_corr  | col_asc  |           1
 tbl_corr  | col_desc |          -1
 tbl_corr  | col_rand |    0.125874
(3 rows)
当执行下列查询时，由于所有的目标元组都在第一页中，PostgreSQL只会读取第一页，如图3.8(a)所示。
testdb=# SELECT * FROM tbl_corr WHERE col_asc BETWEEN 2 AND 4;
而执行下列查询时则不然，PostgreSQL需要读所有的页，如图3.8(b)所示。
testdb=# SELECT * FROM tbl_corr WHERE col_rand BETWEEN 2 AND 4;
如此可知，索引相关性是一种统计上的相关性。在索引扫描代价估计中，索引相关性体现了索引顺序和物理元组顺序扭曲程度给随机访问性能造成的影响大小。

图3.8 索引相关性

3.2.2.3 整体代价

作为确认，上述SELECT查询的EXPLAIN结果如下所示：

testdb=# EXPLAIN SELECT id, data FROM tbl WHERE data < 240;
                                QUERY PLAN                     
---------------------------------------------------------------------------
 Index Scan using tbl_data_idx on tbl  (cost=0.29..13.49 rows=240 width=8)
   Index Cond: (data < 240)
(2 rows)

在第4行可以看到启动代价和总代价分别是0.29和13.49，预估有240条元组被扫描。

在第5行显示了一个索引条件Index Cond:(data < 240)。更准确地说，这个条件叫做访问谓词（access predicate） ，它表达了索引扫描的开始条件与结束条件。

根据这篇文章，PostgreSQL中的EXPLAIN命令不会区分访问谓词（access predicate） 和索引过滤谓词（index filter predicate） 。因此当分析EXPLAIN的输出时，即使看到了“IndexCond”，也应当注意一下预估返回行数。

seq_page_cost和random_page_cost

seq_page_cost和random_page_cost的默认值分别为1.0和4.0。这意味着PostgreSQL假设随机扫描比顺序扫描慢4倍；显然，PostgreSQL的默认值是基于HDD（普通硬盘）设置的。

另一方面，近年来SSD得到了广泛的应用，random_page_cost的默认值就显得太大了。使用SSD时如果仍然采用random_page_cost的默认值，则计划器有可能会选择低效的计划。因此当使用SSD时最好将random_page_cost的值设为1.0。

这篇文章报告了使用random_page_cost默认值导致的问题。

3.2.3 排序

排序路径（sort path） 会在排序操作中被使用。排序操作包括ORDER BY，归并连接的预处理操作，以及其他函数。函数cost_sort()用于估计排序操作的代价。

如果能在工作内存中放下所有元组，那么排序操作会选用快速排序算法。否则的话则会创建临时文件，使用文件归并排序算法。

排序路径的启动代价就是对目标表的排序代价，因此代价就是$O(N_{\verb|sort|}× \log_2(N_{\verb|sort|})$，这里$N_{\verb|sort|}$就是待排序的元组数。排序路径的运行代价就是读取已经排好序的元组的代价，因而代价就是$O(N_{sort})$。

本节将研究以下查询排序代价的估计过程。假设该查询只使用工作内存，不使用临时文件。

testdb=# SELECT id, data FROM tbl WHERE data < 240 ORDER BY id;

这里$C$就是上一次扫描的总代价，即上次索引扫描的总代价；由(15)可得C等于13.485；$N_{\verb|sort|}=240$；$\verb|comparison_cost|$ 定义为$ 2 × \verb|cpu_operator_cost|$。

作为确认，以上SELECT查询的EXPLAIN命令结果如下：

testdb=# EXPLAIN SELECT id, data FROM tbl WHERE data < 240 ORDER BY id;
                                   QUERY PLAN                        
---------------------------------------------------------------------------------
 Sort  (cost=22.97..23.57 rows=240 width=8)
   Sort Key: id
   ->  Index Scan using tbl_data_idx on tbl  (cost=0.29..13.49 rows=240 width=8)
         Index Cond: (data < 240)
(4 rows)

在第4行可以看到启动代价和运行代价分别为22.97和23.57。

3.2 单表查询的代价估计

3.2.1 顺序扫描

3.2.2 索引扫描

3.2.2.1 启动代价

3.2.2.2 运行代价

选择率（Selectivity）

索引相关性（index correlation）

3.2.2.3 整体代价

seq_page_cost和random_page_cost

3.2.3 排序

`seq_page_cost`和`random_page_cost`