PostgreSQL数据库之查询优化基础

      在数据库管理系统中，用户的查询请求可以采用不同的方案来执行。尽管不同方案返回给用户的结果相同，但执行效率却存在差异，查询优化就是根据系统收集的统计信息，进行代价模型估算，选择一种代价最小的执行方案。因此，查询优化在数据库的查询性能方面起着举足轻重的作用，称为数据库的大脑。本文从三个方面介绍PostgreSQL的查询优化，首先从优化器的产物查询计划进行介绍数据库中有哪些计划节点，什么样的SQL会生成什么计划节点，然后再介绍统计信息有哪些以及统计信息的作用，最后介绍优化器的整体处理流程以及如何使用统计信息估算代价，选择最小代价的查询计划。

计划

     计划是优化器的产物，是查询优化的结果，是SQL调优的最基本方法，普通的一条SQL就对应一个查询计划，查看计划命令：EXPLAIN (ANALYZE VERBOSE COSTS) sql stmt;其中sql_stmt指SQL语句，只能是DML语句，ANALYZE指定此关键字时，表示在解释SQL语句计划的同时，还会统计其执行时间（单位：ms），否则，只解释SQL语句的计划。VERBOSE指定此关键字，打印更详细的信息，包括每个计划节点的元组描述，COSTS指定此关键字，打印每个计划节点的代价。计划是一棵（非满）二叉树，其树形结构如下：

    计划树是由需要计划节点组成，节点称为执行元操作或算子，每个算子后面的第一部分表示估算代价包括启动代价和总代价，启动代价指算子输出第一行元组所花费的时间，总代价指算子输出最后一行所花费的时间、估算行数、估算宽度，第二部分表示实际执行时间（算子输出第一个元组的时间和最后一个元组的时间，单位:ms），实际行数以及循环次数。Planning time代表生成计划的所使用的时间（单位ms），Execution time代表执行该计划所使用的时间（单位:ms）。计划树中一般包含哪些计划节点呢？在PostgreSQL数据库中，计划节点分为四类，分别是控制节点（Control Node）、扫描节点(Scan Node)、物化节点（Material Node）、连接节点（Join Node）。

控制节点

    控制节点用于完成一些特殊的流程执行方式。由于PostgreSQL为查询语句生成二叉树状的查询计划，其中大部分节点的执行过程需要两个以内的输入和一个输出。但有一些特殊的功能为了优化的需要，会含有特殊的执行方式和输入需求（例如需要两个以上的输入），这一类的节点被称为控制节点。例如，为了能让union操作执行多个表（大于2）的合并，Append算子并未把union涉及的多个表放在孩子节点中，而是将这些表组成一个链表放在Append节点的appendplans字段中，一次处理该链表中的节点获取输入。 PostgreSQL中一般包括如下的控制节点：

节点类型	描述	对应SQL
Result	处理含有仅需一次计算的条件表达式或INSERT中仅有一个VALUES子句	select 1,2; insert into ... values (1,2);
Append	用于表示和组织需要包含多个（大于等于2）子查询执行流程	SQL中含有union all,union,except all, except, intersect, intersect all集合等操作
BitmapAnd	用于需要对两个或多个位图进行并操作的流程	SQL中对表进行扫描，并在表上建有索引，假设表有属性attrA和attrB,且分别建立了索引。如果需要进行的查询条件中（attrA的条件 AND 涉及attrB的条件），则可以首先利用第一个条件扫描属性attrA上的索引并构建位图Bitmap A,其中每一位对应表中的一个元组，用同样的方法利用attrB的索引构建位图Bitmap B.因此可以对两个位图进行AND操作，从而得到Bitmap AB，其中值1的位表示对应元组同事满足A、B两属性上约束。
BitmapOr	用于需要对两个或多个位图进行或操作的流程	同上，只不过由AND操作变成了OR操作
RecursiveUnion	用于处理WITH子句中递归定义的UNION子查询	SQL语句定义从1到100求和： with recursive t(n) as( values(1)union all select n+1 from t where n<100 ) select sum(n) from t;

 

扫描节点

     扫描节点的作用是扫描表，每次获取一条元组作为上层节点的输入。扫描节点普遍存在于查询计划树的叶子节点，它不仅可以扫描表，还可以扫描函数的结果集、链表结构、子查询结果集等，由于优化的需要，扫描节点中有一类使用索引进行扫描的节点，前面介绍的BitmapAnd和BitmapOr节点所需要的位图也是通过索引扫描节点得到。PostgreSQL数据库中一般包含如下的扫描节点。

节点类型	描述	对应SQL
SeqScan	顺序扫描表	select * from t1;
IndexScan	利用索引进行表扫描	create index t1_ix on t1(tc1); select * from t1 where tc1=1
BitmapHeapScan	利用Bitmap结构获取元组	create index t1_ix on t1(tc1); select * from t1 where tc1=1
BitmapIndexScan	利用索引结构获取满足选择条件的Bitmap	create index t1_ix on t1(tc1); select * from t1 where tc1=1
TidScan	用于扫描一个元组TID数组	select * from t1 where rowid= 24545344;
SubqueryScan	出现在from子句中，形式为范围表，扫描一个子查询	select * from (select * from XXX join XXX)
FunctionScan	处理范围表中含有函数的扫描	select * from func;
ValuesScan	用于扫描Values链表	insert into XXX values(),(),();
CteScan	用于扫描withas 定义的公公表达式	with t_1 as(select * from t1)select * from t1_1;
WorkTableScan	扫描RecursiveUnion迭代的中间数据	SQL语句定义从1到100求和： with recursive t(n) as( values(1)union all select n+1 from t where n<100 ) select sum(n) from t;

 

物化节点

      物化节点是一类可缓存元组的节点。在执行过程中，很多扩展的物理操作符需要首先获取所有的元组后才能进行操作，比如聚集函数操作，排序等，这时要用物化节点将元组缓存起来，PostgreSQL数据中一般提供如下的物化节点。

节点类型	描述	对应SQL
Material	对子查询结果进行缓存	SQL语句中含有join,配合nestloop一起使用
Sort	对底层节点返回的元组进行排序	order by子句
Group	对下层排序元组进行分组操作	group by 子句
Agg	执行聚集函数	子句的目标列中含有sum、count、avg、max、min函数，而不含有group by子句
HashAgg	对下层元组分组后执行聚集函数	子句的目标列中含有sum、count、avg、max、min函数，并且含有group by子句
GroupAgg	对下层排序元组分组后执行聚集函数	子句的目标列中含有sum、count、avg、max、min函数，并且含有group by子句
Unique	执行去重操作	子句中的目标列中含有消除重复distinct关键字
Hash	HashJoin算子辅助节点	子句中含有join配合Hashjoin算子使用
SetOp	处理集合操作except,intersect查询	子句中含有集合操作except、except all、intersect、intersect all
Limit	限定返回结果的操作	子句中含有limit、offset、top[percent]
Windowagg	处理窗口函数（新的聚集方式下的聚集函数）	子句中含有窗口函数，比如select rank() over (order by tc1 partition by tc1) from t1
subplan	出现在on、where、投影目标列中，形式为表达式，如果是非相关子查询，并且只计算一次，并且结果为一样，则优化initplan	子句中含有where In/Not In/Exists/Not Exists/Any/All/Some

 

连接节点

     连接类型节点对应于关系代数中的连接操作，连接类型一般包括CROSS JOIN、INNER JOIN、LEFT JOIN、RIGHT JOIN、FULL JOIN。PostgreSQL数据库中使用三种连接算子实现，嵌套循环连接NestLoop、归并连接MergeJoin和Hash连接（HashJoin）。

（1）NestLoop嵌套循环连接，依次从外表取元组匹配内表元组，支持所有的连接类型，包含非条件下降的NestLoop和条件下降NestLoop，当内表在连接条件列建索引，并且外表较小，内表较大且连接条件的选择率极低，一般会生成条件下降的NestLoop，扫描内表时，执行器将外表的一行作为过滤条件，传递给内表，提前过滤内表数据，减少Join时的元组数，提高NestLoop的执行效率。

（2）MergeJoin归并连接，左右子树一定按连接键有序，支持所有连接类型。MergeJoin在左右子树已经有序，或者所需要的结果有序的情况下，性能会比较好。

（3）HashJoin哈希连接，内表建好hash表，外表元组映射到hash桶，与桶中元组进行连接比较，右子树一定是Hash算子，只支持等值连接，一般内表数据区别率教高，内表教小的情况，性能会比较好。

当子查询子句（in、not in、exists、not exists、any、all、some）经过子查询提升后会生成8种半连接算子：

节点类型	描述	对应SQL
left semi join	扫描外表的每一行，扫描内表，如果遇见有满足条件的，就返回外表元组	子句含有exists、in、any等关键字
right semi join	扫描内表的每一行，扫描外表，如果遇见有满足条件的，就返回内表元组	子句含有exists、in、any等关键字
left anti semi join	扫描外表的每一行，扫描内表，如果都不满足条件，返回外表元组	子句含有not exists、 not in、all关键字
right anti semi join	扫描内表的每一行，扫描外表，如果都不满足条件，返回内表元组	子句含有not exists、 not in、all关键字
left semi residual join	扫描外表的每一行，先与第一个内表进行联接条件的判断，符合条件的返回外表元组，不符合条件的外表元组再去下一个内表进行条件判定，返回剩下的符合条件的外表元组。	子句中含有in (XXX) or in (XXX)
right semi residual join	扫描内表的每一行，先与第一个外表进行联接条件的判断，符合条件的返回内表元组，不符合条件的内表元组再去下一个外表进行条件判定，返回剩下的符合条件的内表元组。	子句中含有in (XXX) or in (XXX)
left anti semi residual join	扫描外表的每一行，先与第一个内表进行联接条件的判断，如果都不满足条件，返回外表元组，满足条件的元组再去下一个内表进行条件判定，返回剩下的不符合条件的外表元组。	子句中含有not in (XXX) or not in (XXX)
right anti semi residual join	扫描内表的每一行，先与第一个外表进行联接条件的判断，如果都不满足条件，返回内表元组，满足条件的元组再去下一个外表进行条件判定，返回剩下的不符合条件的内表元组。	子句中含有not in (XXX) or not in (XXX)

统计信息

     PostgreSQL数据库中，ANALYZE命令用于收集表内容的统计信息，并将这些信息存储在系统表pg_statistic中，这些统计信息会被查询优化器使用确定最有效的查询计划。在默认的PostgreSQL配置中，autovacuum守护进程负责在表首次加载数据时以及在整个常规操作过程更改时自动分析表。如果禁用了autovacuum,则最好定期运行ANALYZE，或者再对表内容进行重大更改之后立即运行ANALYZE。因此统计信息收集有自动和手动两种方式, 手动收集统计信息的语法如下：ANALYZE [VERBOSE] [table_name [(column_name [, ...])]]; VERBOSE:如果指定，ANALYZE会显示处理进度的消息。table_name:要分析的特定表的名称，可以是模式限定的。如果省略，则分析当前用户有权分析的所有表。column_name:要分析的特定列的名称。如果省略，则分析所有列。

产物

     PostgreSQL数据库中，统计信息的产物主要是存储在系统表pg_statistic，具体来说，统计信息的产物包括以下几种：

    (1) 表和列的统计信息

     tuples：表中行的数量，主要用来估算cpu运算量

     pages：页面数，主要用来估算IO量

     最小值和最大值：列中值的最小值和最大值（如果适用）。

     平均值：数值列的平均值。

     标准差：数值列的标准差。

     distinct：不重复的元素数，主要用来计算选择率、聚集率。

     mcv：最常用的值和它们的出现频率，主要用来计算选择率。

     NULL 值的数量：列中 NULL 值的数量，这对某些查询优化也很重要。

     分布直方图：列值的分布情况，通常用于离散值的列，帮助优化器了解数据的分布特征，主要用来计算选择率。

 （2）索引的统计信息

   索引的使用情况：有关索引的使用频率和效率的信息。

   索引的基数（distinct values）：索引中不同值的数量，这有助于优化器评估使用该索引的有效性。

作用

     每个算子都有自己的代价模型，优化器计算代价的依据就是统计信息，代价一般包括IO代价，CPU代价，网络代价。代价分为启动代价、执行代价和总代价，总代价等于启动代价与执行代价之和，启动代价代表算子获取第一行元组所花费的代价，运行代价代表算子从获取第一行到最后一行所花费的代价，优化器计算每个算子的代价都是基于相对值，并没有具体的单位，比如规定cpu处理一行元组代价为1，顺序扫描一个页面的代价为1，而随机扫描一个页面的代价为2等，基于以上规定一个顺序扫描的代价计算公式如下：

cost_seqscan
        {
            startup_cost = 0;
	        //！ 顺序扫描页面IO代价
              run_cost += baserel->pages;
              //！处理一行元组的CPU代价
              cpu_per_tuple = cpu_tuple_cost + baserel->baserestrictcost;
           //！运行代价 = 处理一行元组的CPU代价 * 元组数 + 顺序扫描页面代价
              run_cost += cpu_per_tuple * baserel->tuples;
              path->startup_cost = startup_cost;
              //！ 总代价 = 启动代价 + 运行代价
              path->total_cost = startup_cost + run_cost;
         }

      在统计信息中，比较重要的统计数据，一个是Distinct值，一个是直方图。Distinct值代表不重复的属性个数，描述了数据集合的密度，主要作用是估算等值条件的选择率和聚集率，比如在Hashagg和Groupagg的选择中，用来估算Hashagg需要用到的桶数，当该列distinct比较小，就说明该列的聚集率高，那么Hashagg的代价就会小，就会选择Hashagg。PostgrsSQL数据库中采用的是等高直方图，基于一个数据均匀分布的独立性假设，剔除奇异值MCV之后，将数据散列到每个桶中，默认桶数100，主要作用是描述数据分布状态，每个桶内数据均匀分布，计算范围条件和连接条件的选择率。那么一个扫描条件a <(<=、>、>=)const是如何计算选择率的呢？选择率代表满足条件的元组数除以总元组数，得到的比率。

（1）扫描MCV，计算来自MCV的选择率；

（2）扫描直方图，定位const到其中一个桶里；

（3）选择条件所占的直方图桶数计算来自直方图的选择率；

（4）两个选择率相加

优化器

      PostgreSQL数据库主要包括语法解析，语义分析，查询优化，查询执行几个部分，查询优化俗称数据库的大脑，在数据库的查询性能方面起着举足轻重的作用。优化器的最终目的是得到可被执行器执行的最优计划，整个过程分为规则优化、代价优化和生成计划三个阶段，规则优化实际上是对查询树Query结构体进一步改造，最重要的是提升子链接和提升子查询。在代价优化阶段，接收到改造后的查询树后，采用动态规划算法或遗传算法，生成最优连接路径和候选的路径链表。在生成计划阶段，用得到的最优路径，首先生成基本计划树，然后再添加GROUP BY、HAVING和ORDER BY等子句所对应的计划节点形成完整计划树。因此优化器的主要工作是通过规则改写查询树，生成各种查询计划，准确衡量计划代价、高效搜索候选计划空间、选择估算代价最小计划提供给执行器。优化器的整体处理流程如下：

规则优化

      优化器的输入是Query查询树，规则优化就是利用一些规则对查询树Query进行改造，主要包括逻辑重写优化和逻辑分解优化。而逻辑重写优化包括列级语义规则、子链接提升、子查询提升、表达式预处理、外连接消除等。逻辑分解优化主要包括谓词下推、连接顺序交换、等价类推理等。

列级语义规则

● group by的聚集函数唯一性改写规则

描述：考虑一查询，其含有group by子句，并且select 子句中含有聚集函数，如果group by子句中的列集（一列或多列）满足列集唯一性，from涉及的表只有一个，则select子句中出现的聚集函数可以做如下变换：Max(c1)变换为c1，Min(c1)变换为c2，count变换为1，Sum(c1)变换为c1，Average(c1)变换为c1。

示例：

定义视图v1：

create view v1 as

select tc1 from t1

where vc1 > 10 group by vc1;

则，查询：

select count(*), Max(vc1), Sum(vc1) from v1

group by vc1;

可根据上述规则被转换为：

select 1, vc1, vc1 from v1

group by vc1;

● group by常量性改写规则

描述：考虑一查询，其含有group by子句，并且select 子句中含有聚集函数，如果group by子句中的列集（一列或多列）满足列集常量性，则group by子句可以去除。

示例：考虑查询：

select count(*), max(tc1), sum(tc1) from t1

where tc1 in (select tc1 from t2 where tc1 = 10)

group by tc1;

可转换为

select count(*), max(tc1), sum(tc1) from t1

where tc1 in (select tc1 from t2 where tc1 = 10);

● 聚集函数空值性改写规则

描述：考虑一含聚集函数查询，若作为聚集函数参数的列集满足空值性，则该查询中count可被替换为0，其余聚集函数可用NULL替换。

示例：考虑查询：

select count(tc1), Max(tc1) from t1

where tc1 is null;

可被改写为:

select 0, NULL;

● 聚集函数常量性改写规则

描述：考虑一含聚集函数查询，若作为聚集函数参数的列集满足常量性，则该查询中各聚集函数可做如下转换：Max(c)、Min(c)可被替换为c，Sum(c)可被替换为c*count(c)，Average(c) 可被替换为c。

示例：考虑查询：

select count(tc1), Max(tc1) from t1

where tc1 =10

group by tc1;

可被改写为:

select 1, 10 from t1

where tc1 = 10

group by tc1;

● 消除排序规则

描述：Order by后面的列集满足有序性，并且排序符合升序和降序要求，则order by子句可以消去。

● Distinct消除规则

描述：考虑一个查询，若from只涉及一个表，并且select distinct后的列集满足唯一性，则distinct可以消去。

● 恒真恒假条件消去规则

描述：考虑一查询，WHERE条件含有恒真或恒假条件，则这个条件可以消去

子链接子查询提升

子链接出现在ON/WHERE/投影中的子句，形式是表达式，而子查询出现在FROM后面的子句，形式是范围表。

● 子链接提升

子链接按照关键字的不同，可以分为以下几类：

1）EXISTS: 声明了EXISTS的子查询

2）ALL：生成了ALL或NOT IN的子查询

3）ANY：声明ANY或IN的子查询

4）EXPR: 子查询返回一个参数给外层父查询

5)  MULTIEXPR: 子查询返回多个参数给外层父查询。

6)  ARRAY: 子查询将某些值构成数组的表达式，例如："select array[1,2,3+4];".

以ANY类型为例，它的提升规则如下：

1）不相关的子链接，都可以提升, 简单查询(不含group by/agg/having

/sort/distinct/limit/top等)提升为left semi join/inner join，复杂查询提升到子查询层。

示例：

select distinct a

from A

where a in (select b from B where b > 1) and a > 2;

优化为

select distinct A.a

from A, B

where A.a = B.b and A.a > 2 and B.b > 1;

2）相关度=1并且满足一定条件提升为left semi join/inner join，否则不提升。

示例：

select * from t1 where c1 in (select c1 from t2 where t2.c2=t1.c2)；

优化为

select * from t1,t2 where c1 = t2.c1 and t2.c2=t1.c2;

 

3）相关度>1的不提升，否则结果错误。

● 子查询提升

简单查询才能提升（不含group by/agg/having/sort/distinct/limit/top等）

示例：

select a

from A,(select b from B where b > 1 )

where a > 2;

优化为

select A.a

from A,B

where A.a > 2 and B.b > 1;

表达式预处理

● 常量化简

示例：select max(d + (1+2)) from score 化简为select max(d+3) from score;

● 谓词规范

示例：null or false or a = 1 化简为a = 1

● 谓词拉平

示例：a = 1 or (a = 2 or (a = 3 or a = 4)) 拉平为a = 1 or a = 2 or a = 3 or a = 4.

● 子链接处理

分为相关子链接和非相关子链接，相关子链接通过Param进行父子执行计划的通信，非相关子连接可以优化为Onetime filter,生成initplan.

外连接消除

示例：外连接转化为内连接：select from t1 left join t2 on t1.tc1 = t2.tc1 where t1.tc1 is not null 优化为select from t1 inner join t2 on t1.tc1 = t2.tc1.

谓词下推

根据连接类型，可分为非空边Nonnullable-side和空边Nullable-side.

连接类型	Nonnullable-side	Nullable-side
A Left Join B	A	B
A Right Join B	B	A
A Full Join B	A、B	A、B
A Semi Join B	A、B	无
A Anti Join B	A	B

1）连接条件下推之后会变成过滤条件，过滤条件下推之后仍然是过滤条件。

示例：select * from t1 inner join t2 on t1.a = 1; 转化为select * from (select from t1 where a = 1)t inner join t2 on true;

2) 如果连接条件引用了非NULL边的表，那么连接条件不能下推，如果连接条件只引用了NULL边的表，那么连接条件可以下推。

示例：select * from t1 left join t2 on t1.a = 1;--不可下推

select * from t1 left join t2 on t2.a = 1;--可下推

3) 如果过滤条件只引用了Nonnullable-side的表，那么这个过滤条件能够下推到表上，如果过滤条件引用了Nullable-side的表且过滤条件是严格的，那么会导致外连接消除，外连接消除之后变成内连接，过滤条件也是能下推的。

示例：select * from t1 left join t2 on true where t1.a = 1;--可下推

select * from t1 left join t2 on true where t2.a = 1;--不可下推

代价优化

优化器根据统计信息，每个算子的代价模型，估算出每个路径的代价，选择代价最小的路径，生成查询计划传递给执行器，因此在代价优化阶段，首先需要确定每张表的扫描方法，是顺序扫描还是索引扫描，然后再根据动态编程算法或者遗传算法确定表的连接顺序以及连接方法，是选择NestLoop、HashJoin、还是MergeJoin。因此代价优化包括生成路径、生成普通计划、生成完整计划、整理计划树四个部分。

生成路径

生成路径的处理流程如下：

其中，set_base_rel_pathlists:生成访问简单基表的所有路径。make_fromexpr_rel：生成最终路径，返回一个代表所有基本关系的RelOptInfo结构，它的pathlist字段代表所有的路径组合，路径会通过代价竞争，最终找出最优连接路径，包括连接顺序和方式。该过程是用经典的优化算法—动态编程实现。函数make_join_rel的主要功能是生成连接路径，主体调用函数add_paths_to_joinrel实现，为了处理三种不同的连接方式， 调用create_nestloop_path, create_hashjoin_path, create_mergejoin_path生成NestPath，HashPath，MergePath）。同时，make_join_rel也会考虑使用每个rel作为外部和内部关系的情况(如，A join B <=> (A做外表，B做内表)或（A做内表，B做外表))。

生成路径最重要的就是确定表的连接顺序，默认配置中小于11张表使用动态编程算法，大于11张表使用遗传算法，下面以动态编程算法为例，说明是如何求解n个关系的最佳连接顺序：

1）–填写涉及1个关系和2个关系的子集表

2）–填写3个关系的子集表，此时可以参考2个关系的子集表

3）–继续填写4个关系的子集表，此时可以参考2个关系和3个关系的子集表

4）–直到填充完n个关系的子集表为止

示例：explain select * from t1,t2,t3,t4 where t1.tc1=t2.tc1;

1）先确定基表的访问方式

2）确定两个表的连接顺序和连接方式，由于t1,t2有链接条件，所以选择t1,t2结合在一起，t3,t4结合在一起。

 

3）确定三张表的连接顺序和连接方法

4）得到四张表的连接顺序和连接方法

 

生成计划

优化器经过代价优化之后，就会生成一个最优路径，生成计划阶段就调用create_plan接口，为最优路径创建计划，依据其路径节点类型的不同，分别调用不同的函数生成对应的计划，包括生成普通计划、生成完整计划、调整计划树三部分。

生成普通计划

普通计划分为以下几类：

● 扫描计划：主要有顺序扫描、索引扫描等计划类型。

● 连接计划：主要有嵌套循环连接、hash连接、归并连接等计划类型。

● 其他计划：如Append计划、Result计划、物化计划等。

生成完整计划

生成路径阶段仅仅考虑基本查询语句信息，并没有保留如GROUP BY、ORDER BY等信息。grouping_planner函数调用create_plan生成基本计划树后，则会依据查询树相关约束信息在前面生成的普通计划之上添加相应的计划节点生成完整计划。整体处理流程如下：

整理计划树

 生成的完整计划经过计划树整理之后就可以交给查询执行器去执行了，负责整理工作的主函数是set_plan_references。整理计划树是优化器处理工作的最后一步，主要是为了方便执行器的执行，对计划树一些表达上的细节做最后的调整。例如，将上层的Var结构变为对子计划的输出结果的引用、获取操作符的OID等。同时，这一步也会删除那些没有任何用处的子查询扫描计划节点。