3.2 单表查询的代价估计
PostgreSQL的查询优化是基于代价的。代价是一个无量纲的值，它不是一种绝对的性能指标，但可以作为比较各种操作代价时的相对性能指标。
costsize.c 中的函数用于估算各种操作的代价。所有被执行器执行的操作都有着相应的代价函数。例如，函数cost_seqscan() 和 cost_index()分别用于估算顺序扫描和索引扫描的代价。
在PostgreSQL中有三种代价，分别是启动代价、运行代价和总代价。总代价是启动代价和运行代价的和，因此只有启动代价和运行代价是单独估计的。
1.启动代价：在读取到第一条元组前花费的代价，比如索引扫描节点的启动代价就是读取目标表的索引页，获取到第一个元组的代价。
2.运行代价：获取全部元组的代价。
3.总代价：前两者之和。
EXPLAIN命令显示了每个操作的启动代价和总代价，下面是一个简单的例子：
1.testdb=# EXPLAIN SELECT ＊ FROM tbl;
2. QUERY PLAN
3.---------------------------------------------------------
4. Seq Scan on tbl (cost=0.00..145.00 rows=10000 width=8)
5.(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，而运行代价由以下公式定义：
run_cost=cpu_run_cost+disk_run_cost
=(cpu_tuple_cost+cpu_operator_cost)×Ntuple+ seq_page_cost × Npage，
其中seq_page_cost、cpu_tuple_cost和cpu_operator_cost是在postgresql.conf中配置的参数，默认值分别为1.0、0.01和0.0025。Ntuple和Npage分别是表中的元组总数与页面总数，这两个值可以使用以下查询获取。
testdb=# SELECT relpages, reltuples FROM pg_class WHERE relname = 'tbl';
relpages | reltuples
----------+-----------
45 | 10000
(1 row)
因此：
run_cost=(0.01+0.0025)×10000+1.0 × 45=170.0
最终：
total_cost=0.0+170.0=170.0
作为验证，下面是该查询的EXPLAIN结果：
1.testdb=# EXPLAIN SELECT ＊ FROM tbl WHERE id < 8000;
2. QUERY PLAN
3.--------------------------------------------------------
4.Seq Scan on tbl (cost=0.00..170.00 rows=8000 width=8)
5. Filter: (id < 8000)
6.(2 rows)
在第 4行中可以看到，启动代价和总代价分别是 0.00和 170.0，且预计全表扫描返回行数为8000条（元组）。
第5行显示了一个顺序扫描的过滤器Filter:(id < 8000)。更精确地说，它是一个表级过滤谓词。注意，这种类型的过滤器只会在读取所有元组的时候使用，它并不会减少需要扫描的表页面数量。
从优化运行代价的角度来看，PostgreSQL假设所有的物理页都是从存储介质中获取的，即PostgreSQL不会考虑扫描的页面是否来自共享缓冲区。
3.2.2 索引扫描
尽管PostgreSQL支持很多索引方法，比如B树、GiST、GIN和BRIN，但是索引扫描的代价估计是使用一个共用的代价函数：cost_index()。
本节将研究索引扫描的代价是如何估计的，以下列查询为例。
testdb=# SELECT id, data FROM tbl WHERE data < 240;
在估计该查询的代价之前，下面的查询能获取Nindex,page和Nindex, tuple的值：
testdb=# SELECT relpages, reltuples FROM pg_class WHERE relname = 'tbl_data_idx';
relpages | reltuples
----------+-----------
30 | 10000
(1 row)
3.2.2.1 启动代价
索引扫描的启动代价就是读取索引页以访问目标表的第一条元组的代价，由下面的公式定义：
start-up_cost={ceil(log2(Nindex, tuple))+(Hindex+1)×50}×cpu_operator_cost
其中Hindex是索引树的高度。
在本例中，套用公式（3），Nindex, tuple是10000；Hindex是1；cpu_operator_cost是0.0025 （默认值）。因此：
3.2.2.2 运行代价
索引扫描的运行代价是表和索引的CPU代价与I/O代价之和。
run_cost=(index_cpu_cost+table_cpu_cost)+(index_io_cost+table_io_cost)
如果使用仅索引扫描，则不会估计table_cpu_cost与table_io_cost，仅索引扫描将在第7章中介绍。
前三个代价（即index_cpu_cost、table_cpu_cost和index_io_cost）如下所示：
index_cpu_cost=Selectivity×Nindex, tuple×(cpu_index_tuple_cost+qual_op_cost)
table_cpu_cost=Selectivity×Ntuple×cpu_tuple_cost
index_io_cost=ceil(Selectivity×Nindex,page)×random_page_cost
以上公式中的cpu_index_tuple_cost和random_page_cost在postgresql.conf中配置（默认值分别为0.005和4.0）。qual_op_cost粗略来说就是索引求值的代价，默认值是0.0025，这里不再展开。选择率是一个0到1之间的浮点数，代表查询指定的WHERE子句在索引中搜索范围的比例。举个例子，（Selectivity×Ntuple）就需要读取表元组数量，（Selectivity×Nindex,page）就需要读取索引元组数量，诸如此类。
选择率
查询谓词的选择率是通过直方图界值与高频值估计的，这些信息都存储在系统目录pg_statistics中，并可通过pg_stats视图查询。这里通过一个具体的例子来简要介绍选择率的计算方法，具体细节可以参考官方文档。
表中每一列的高频值都在pg_stats视图的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会在估算中被用作选择率。
如果高频值不可用，就会使用目标列上的直方图界值来估计代价。
直方图值是一系列值，这些值将列上的取值划分为数量大致相同的若干个组。
下面是一个具体的例子。这是表tbl中data列上的直方图界值。
testdb=# SELECT histogram_bounds FROM pg_stats WHERE tablename = 'tbl' AND attname = 'd
ata';
histogram_bounds
------------------------------------------------------------------------------
{1,100,200,300,400,500,600,700,800,900,1000,1100,1200,1300,1400,1500,1600,1700,1800,19
00,2000,2100,
2200,2300,2400,2500,2600,2700,2800,2900,3000,3100,3200,3300,3400,3500,3600,3700,3800,39
00,4000,4100,
4200,4300,4400,4500,4600,4700,4800,4900,5000,5100,5200,5300,5400,5500,5600,5700,5800,59
00,6000,6100,
6200,6300,6400,6500,6600,6700,6800,6900,7000,7100,7200,7300,7400,7500,7600,7700,7800,79
00,8000,8100,
8200,8300,8400,8500,8600,8700,8800,8900,9000,9100,9200,9300,9400,9500,9600,9700,9800,99
00,10000}
(1 row)
默认情况下，直方图界值会将列上的取值划分入100个桶。图3.7展示了这些桶及其对应的直方图界值。桶从0开始编号，每个桶保存了（大致）相同数量的元组。直方图界值就是相应桶的边界。比如，直方图界值的第0个值是1，意即这是bucket_0中的最小值；第1个值是100，意即bucket_1中的最小值是100；等等。
图3.7 桶和直方图界值
本节例子中选择率计算如下所示。假设查询带有WHERE子句data < 240，而值240落在第二个桶中。在本例中可以通过线性插值推算出相应的选择率。因此查询中data列的选择率可以套用下面的公式计算：
因此，根据公式（1）、（2）、（4）和（6），有
table_io_cost由下面的公式定义：
table_io_cost = max_io_cost+indexCorerelation2×（min_io_cost-max_io_cost）
max_io_cost_io_cost 是最差情况下的 I/O代价，即随机扫描所有数据页的代价。这个代价由以下公式定义：
max_io_cost = Npage×random_page_cost
在本例中，由（2），Npage=45，得
min_io_cost是最优情况下的I/O代价，即顺序扫描选定的数据页。这个代价由以下公式定义：
min_io_cost=1×random_page_cost +(ceil(Selectivity× Npage)-1)×seq_page_cost
在本例中，
下文将详细介绍indexCorrelation，在本例中，
由（10）、（11）和（12），得
综上，由（7）、（8）、（9）和（13）得
索引相关性
索引相关性是列值在物理上的顺序和逻辑上的顺序的统计相关性（引自官方文档）。索引相关性的取值范围从-1到+1。下面的例子有助于理解索引扫描和索引相关性的关系。
表 tbl_corr有 5列，其中 2列为文本类型，3列为整数类型。这 3个整数列保存着从 1到12的数字。在物理上，表tbl_corr包含3个页，每页有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_cor r'; tablename | attname | correlation -----------+----------+------------- tbl_corr | col_asc | 1 tbl_corr | col_desc | -1 tbl_corr | col_rand | 0.125874 (3 rows)
当执行下列查询时，由于所有的目标元组都在第一页中，PostgreSQL只会读取第一页，如图3.8（1）所示。
testdb=# SELECT ＊ FROM tbl_corr WHERE col_asc BETWEEN 2 AND 4;
执行下列查询时则不然，PostgreSQL需要读取所有的页，如图3.8（2）所示。
图3.8 索引相关性
testdb=# SELECT ＊ FROM tbl_corr WHERE col_rand BETWEEN 2 AND 4;
由此可知，索引相关性是一种统计上的相关性。在索引扫描代价估计中，索引相关性体现了索引顺序和物理元组顺序扭曲程度给随机访问性能造成的影响大小。
3.2.2.3 整体代价
由（3）和（14）可得
作为确认，上述SELECT查询的EXPLAIN结果如下所示：
1.testdb=# EXPLAIN SELECT id, data FROM tbl WHERE data < 240;
2. QUERY PLAN
3.---------------------------------------------------------------------------
4. Index Scan using tbl_data_idx on tbl (cost=0.29..13.49 rows=240 width=8)
5. Index Cond: (data < 240)
6.(2 rows)
在第4行可以看到启动代价和总代价分别是0.29和13.49，预估有240条元组被扫描。
在第5行显示了一个索引条件Index Cond:(data < 240)。更准确地说，这个条件叫作访问谓词，它表达了索引扫描的开始条件与结束条件。
seq_page_cost和random_page_cost
seq_page_cost和random_page_cost的默认值分别为1.0和4.0。这意味着PostgreSQL假设随机扫描的进度是顺序扫描的1/4；显然，PostgreSQL的默认值是基于HDD（普通硬盘）设置的。
另一方面，近年来SSD得到了广泛的应用，random_page_cost的默认值就显得太大了。使用SSD时如果仍然采用random_page_cost的默认值，则计划器有可能会选择低效的计划。因此当使用SSD时最好将random_page_cost的值设为1.0。
https://amplitude.engineering/how-a-single-postgresql-config-change-improved-slow-query-p erformance-by-50x-85593b8991b0这篇文章报告了使用random_page_cost默认值导致的问题。
3.2.3 排序
排序路径会在排序操作中被使用。排序操作包括 ORDER BY、归并连接的预处理操作，以及其他函数。函数cost_sort()用于估计排序操作的代价。
如果能在工作内存中放下所有元组，那么排序操作会选用快速排序算法。否则就会创建临时文件，使用文件归并排序算法。
排序路径的启动代价就是对目标表的排序代价，因此代价就是O(Nsort)×log2(Nsort)，这里Nsort就是待排序的元组数。排序路径的运行代价就是读取已经排好序的元组的代价，因而代价就是O(Nsort)。
本节将研究以下查询排序代价的估计过程。假设该查询只使用工作内存，不使用临时文件。
testdb=# SELECT id, data FROM tbl WHERE data < 240 ORDER BY id;
在本例中，启动代价由以下公式定义：
start-up_cost=C+comparison_cost× Nsort×log2(Nsort)
这里的C就是上一次扫描的总代价，即上次索引扫描的总代价。由（15）可得C等于13.485， Nsort=240，comparison_cost定义为2× cpu_operator_cost。因此：
start-up_cost=13.485+(2×0.0025)×240.0×log2(240.0)=22.973
运行代价是在内存中读取排好序的元组的代价，即：
run_cost=cpu_operator_cost×Nsort= 0.0025 × 240 = 0.6
综上：
total_cost=22.973+0.6=23.573
作为确认，以上SELECT查询的EXPLAIN命令结果如下：
1.testdb=# EXPLAIN SELECT id, data FROM tbl WHERE data < 240 ORDER BY id;
2. QUERY PLAN
3.---------------------------------------------------------------------------------
4. Sort (cost=22.97..23.57 rows=240 width=8)
5. Sort Key: id
6. -> Index Scan using tbl_data_idx on tbl (cost=0.29..13.49 rows=240 width=8)
7. Index Cond: (data < 240)
8.(4 rows)
在第4行可以看到启动代价和运行代价分别为22.97和23.57。