《PostgreSQL数据库内核分析》之查询编译（五）
【摘要】 查询处理器是将用户的各种命令转化成数据库上的操作序列并执行。分为查询编译和查询优化两个阶段。根据用户的查询语句生成数据库中最优执行计划。再次过程中要考虑视图、规则以及表的连续路径等问题。5.1概述查询优化的核心是生成路径和生成计划两个模块。查询优化要处理的问题聚焦在于如何计算最优的表连接路径。5.2查询分析查询分析是查询编译的第一个模块，包括词法分析、语法分析和语义分析，将用户输入的SQL命...
查询处理器是将用户的各种命令转化成数据库上的操作序列并执行。分为查询编译和查询优化两个阶段。根据用户的查询语句生成数据库中最优执行计划。再次过程中要考虑视图、规则以及表的连续路径等问题。
5.1概述
查询优化的核心是生成路径和生成计划两个模块。查询优化要处理的问题聚焦在于如何计算最优的表连接路径。
5.2查询分析
查询分析是查询编译的第一个模块，包括词法分析、语法分析和语义分析，将用户输入的SQL命令转换为查询树（Query结构）。词法分析和语法分析分别借助词法分析工具Lex和语法分析工具Yacc来完成各自的工作。
用户输入的SQL命令作为字符串传递给查询分析器，对其进行词法和语法分析生成分析树，然后进行语义分析得到查询树。
对于用户的SQL命令，统一由exec_simple_query函数处理，该函数调用pg_parse_query完成词法和语法分析并产生分析树，接下来调用pg_analyze_and_rewrite函数逐个对分析树语义分析和重写：再该函数中又会调用parse_analyze进行语义分析并创建查询树（Query结构），函数pg_rewrite_query则负责查询树进行重写。
查询分析的处理过程如下：
1）example_simple_query 调用函数pg_parse_query进入词法和语法分析的主体处理过程，然后函数pg_parse_query调用词法和语法分析的入口函数raw_parser生成分析树（原始分析树链表raw_parse-tree_list）
2）函数pg_parse_query返回分析树给外部函数
3）exec_simple_query接着调用函数pg_analyze_and_rewrite进行语义分析和查询重写。首先调用函数parse_analyze进行语义分析并生成查询树（用Query结构体表示），之后会将查询传递给函数pg_rewrite_query进行重写。
5.2.1Lex和Yacc简介
1.词法分析Lex
2.语法分析 Yacc
5.2.2词法和语法分析
也是由Lex和Yacc完成
|
源文件
|
说明 |
| parse.c | 词法、语法分析的主入口文件，入口函数是raw_parse;对查询语句进行词法和语法分析后，返回分析树 |
| kwlookup.c | 函数ScanKeywordLookup,查找单词表，返回当前标识符指向单词表中对应单词的指针 |
| scansup.c | 提供词法分析时的常用函数 |
| scanstr 处理转义字符 | |
| downcase_truncate_identifier 将大写英文符转换为小写 | |
| truncate_identifier 如果标识符长度超过规定的最大标识符长度（64），则将其截断 | |
| scanner_isspace 判断是否为空白符（空格，\t \n \r \f） | |
| scan.l | 定义词法结构，用Lex语言书写，用Lex编译后生成scan.c文件 |
| gram.h | 定义关键字的数值编号 |
| gram.y | 定义语法结构，用Yacc语言书写，用Yacc编译后生成gram.c文件 |
词法和语法分析的入口函数是raw_parse，该函数返回的List结构用于存储生成的分析树。
1.distinct子句 对应语法定义中的opt_distinct
2.目标属性 target_list
3.FROM子句 from_clause表示SELECT语句中的FROM子句，from_clause由FROM关键字和from_list组成
4.WHERE子句 where_clause
5.GROUP BY 根据指定的属性进行分组，对应语法定义中的标识符group_clause
6.HAVING和ORDER BY子句 having_clause sort_clause
5.2.3语义分析
检查命令中是否有不符合语义规定的成分
如使用的表、属性、过程函数等是否存在，聚集函数是否合法使用等
语义分析器会根据分析树中的内容得到更有利于执行的数据。
exec_simple_query中词法和语法分析模块获取了parsetree_list之后，会对其中一颗分析树调用pg_analyze_and_rewrite进行语义分析和查询重写，而在其中负责语义分析的则是analyze.c文件中的parse_analyze函数，parse_analyze会根据分析树生成一个对应的查询树，而查询重写模块则继续对这一查询继续修改，并且有可能会将这个查询树改写成一个包含多颗查询树的链表。pg_analyze_and_rewrite最终返回给exec_simple_query的将是一个查询链表。
在parse_analyze函数中，将根据命令类型分七种情况处理，经过语义分析之后，会生成查询数（Query结构）。其中SELECT/INSERT/DELETE/UPDATE这四种情况所生成的查询重写和查询优化作进一步处理。
该过程涉及两个重要的结构体：Query和ParseState
5.3重写
重写的入口函数pg_rewrite_query,在pg_analyze之后被pg_analyze_and_rewrite调用，且pg_rewrite_query的参数就是pg_analyze返回值----查询树
查询重写的源代码在src\Backend\rewrite文件中
5.3.1规则系统
系统表pg_rewrite存储重写规则
|
名字
|
类型 | 引用 | 描述 |
| relname | name | 规则名称 | |
| ev_class | oid | pg_class.oid | 使用该规则的表名称 |
| ev_attr | int2 | 规则适合的属性 | |
| ev_type | char | 规则适用的命令类型，1=SELECT，2=UPDATE，3=INSERT，4=DELETE | |
| is_instread | bool | 如果是INSTEAD类型，则为真 | |
| ev_qual | text | 规则的条件表达式（WHERE子句） | |
| ev_action | text | 规则动作的查询树（DO子句） |
规则分类
1.按照规则适用的命令类型分类：可分成SELECT、UPDATE、INSERT和DELETE四种
2.按照规则执行动作的方式分类：可分成INSTEAD(替代)规则和ALSO规则
5.3.2查询重写的处理操作
查询重写部分的处理操作主要包括定义规则、删除规则以及利用规则进行查询重写。
1.定义重写规则
CREATE RULE命令来完成
重写规则的操作主要由函数DefineRule实现
2.删除重写规则
第一种是根据规则名删除规则，由函数RemoveRewriteRule实现
第二种根据规则的OID删除规则，由函数RemoveRewriteRuleById实现
3.对查询树进行重写
pg_rewrite_query中会调用函数QueryRewrite来完成查询树的重写
5.4查询规则
查询规则即选择一种代价最小的执行方案。
查询优化的核心思想“尽量先作选择操作，后做连接操作”
5.4.1总体处理流程
查询规划最终目的是得到可被执行的最优计划，整个过程可分为预处理、生成路径和生成计划三个阶段。
预处理--对查询树的进一步改造，通过SQL语句体现
生成路劲--接收到改造后的查询树，采用动态规则算法或遗传算法，生成最优连接路径和候选的路径链表。
生成计划--得到最优路径，首先生成基本计划数，然后添加GROUP BY、HAVING和ORDER BY等子句所对应的计划节点形成完整的计划树
|
主要函数
|
说明 |
| planner | 优化器的入口函数，输入经过重写器处理的查询树，输出最优的执行计划（如果连接表比较多，为近似最优） |
| standard_planner | 标准的规则处理，PostgreSQL中提供了扩展接口，开发人员可自行设计规则其并在PostgreSQL中使用 |
| subquery_planner | 优化处理的主体函数，可以递归处理子查询 |
| inheritance_planner | 存在继承表的规则处理 |
| grouping_planner | 不存在继承表的规则处理 |
| set_plan_reference | 完成生成执行计划后的清理工作 |
5.4.2预处理
提升子链接和子查询以及预处理表达式和HAVING子句等。主要是对查询树Query中的范围表rtable和连接树jointree等进行处理。
1.提升子链接/子查询
pg中子链接用来表示出现在表达式中的子查询与普通子查询的联系和区别：子查询是一条完整的查询语句，而子链接时一条表达式，但该表达式内部可以包含查询语句。子查询出现在FROM子句中的，而子链接则出现在WHERE子句或HAVING子句中。
嵌套查询分为相关子查询和非相关子查询。
按关键字，嵌套查询可以分为以下几类：
1.EXISTS: 声明了EXISTS的子查询
2.ALL: 声明了ALL或NOT IN的子查询
3.ANY: 声明ALL或IN的子查询
4.EXPR: 子查询返回一个参数给外层父查询
5.MULTIEXPR: 子查询返回多个参数给外层父查询
6.ARRAY: 子查询时某些值构成数组的表达式
2.预处理表达式 preprocess_expression
处理的对象：目标属性、HAVING子句、OFFSET和LIMIT子句、连接树
5.4.3生成路径
基本表连接成连接表的关系可以从逻辑上表示成一个二叉树结构（连接数），由于表之间不同的连接方式和顺序，同一组基本表形成连接表的连接树会有多个，每一颗连接树在PG中都被称为一条路径。
路径在查询的规划和执行过程中表示了从一组基本表生成最终连接表的方式。而查询规划的工作就是从一系列等效的路径中选取效率最高的路径，并形成执行计划。
生成路径的工作是由query_planner来完成
1.路径生成算法
路径代表了对一个表或多个表中数据的访问方式
单个表--顺序访问、索引访问、TID访问
多个表--嵌套循环连接、归并连接、Hash连接
多个表--左连接、右连接和哈希连接
PostgreSQL中有两种路径生成算法：动态规划算法和遗传算法
5.4.4生成可视化的MIN/MAX聚集计划
主函数是optimize_minmax_aggregates，该函数从一个选定的路径生成一个计划，如果该路径对应的查询可满足可优化的MIN/MAX聚集计划的条件，该函数会返回一个计划；否则该函数返回空值。如果该函数能生成一个非空的计划，则后续生成普通计划的步骤就不再进行，将这个计划进行完善后作为最终的计划。
5.4.5生成普通计划
当optimize_minmax_aggrtegates返回的是空值，则需要继续生成普通计划。生成普通计划的入口函数是create_plan，该函数为最优路径创建计划，依据其路径节点类型的不同，分别调用不同的函数生成相应的计划。
普通计划分为以下几类：
1.扫描计划：主要有顺序扫描、索引扫描等计划类型
2.连接计划：主要有嵌套循环连接、Hash连接、归并连接等计划类型
3.其他计划：Append计划、Result计划、物化计划
5.4.6生成完整计划
依据最优路径base_path生成计划树的过程
groupoing_planner函数调用create_plan生成基本计划树后，则会依据查询树相关约束信息在前面生成的普通计划之上添加相应的计划节点生成完整计划。
5.4.7整理计划树
生成的完整计划经过计划树整理之后就可以交给查询执行器去执行了，负责整理工作的主函数set_plan_references。
整理计划树为了方便执行器的执行，对计划树一些表达式上的细节做最后的调整。
5.5代价估计
代价最小的路径
规划器的核心是建立多条路径，然后从中找出最优的那一条。
评价路径优劣的依据是用系统表pg_statistic中的系统统计信息估计出的不同路径的代价（Cost），用于估算代价的参数有：
1.seq_page_cost: 顺序存取页的代价，值为1.0
2.random_page_cost: 非顺序存取页的代价，值为4.0
3.cpu_tuple_cost: 典型CPU处理一个元组的代价，值为0.01
4.cpu_index_tuple_cost: 典型CPU处理一个索引元组的代价，值为0.005
5.cpu_operator_cost: CPU处理一个典型的WHERE操作的代价，值为0.0025
6.effective_cache_size: 用来量度PostgreSQL和OS缓存的磁盘的数量，值为16384
某个路径的代价要考虑CPU代价和磁盘存取代价两方面。磁盘代价以从磁盘顺序存取一个页面的代价为单位，所有其他形式的代价计算都是相对磁盘存取代价来计算的。
一个路径的代价由三部分组成：启动代价（Startup Cost）、总代价（Total Cost）、执行结果的排序方式（PathKeys）
计算启动和总代价所用的参数：
1.基本参数： 元组数ntuples、磁盘块数nblocks、符合选择条件的元组数nrows
2.统计信息：每个表和索引中的元组总数
3.直方图：各个属性值出现次数的统计信息
5.5.1代价估算方式
代价估算从I/O次数和CPU开销两个方面考虑，估算公式为P+W+T
P： 执行时所要访问的页面数，反映了磁盘I/O次数
T：在执行时所要访问的元组数，反映了CPU开销 W：磁盘I/O代价和CPU开销间的权重因子
计算代价时只考虑访问的页面数和元组数
5.5.2选择度
约束条件中的操作符、约束常量、索引中的元组数、某字段的最大值和最小值
5.5.3单个表的扫描代价
NumPages 表的页面数
NumTuples 表的元组数
ITuples 索引表的元组数
F 多个约束条件组合后的选择度
5.5.4两个表的连接代价
5.6PostgreSQL中的遗传算法
启发式的优化法，通过既定的随机搜索进行操作，在PostgreSQl中，遗传算法主要用在连接路径的生成操作中
遗传算法让PostgreSQL查询规划器可通过非穷举搜索有效地支持很多表的连接路径的生成。
5.6.1个体编码方式及种群初始化
5.6.2适应值
个体的适应值等于该个体中N个表的连接代价,适应值计算由函数geqo_eval实现
5.6.3父体选择策略
基于排名的连接策略
5.6.4杂交算子
边重组杂交、循环杂交、基于位置的杂交何顺序杂交等多种杂交算子，用于从父辈种群中产生新的后代个体，默认使用的时边重组杂交算法。
5.6.5变异算子
由grqo_mutation实现，该函数随机地从父体中产生两个变异位，交换这两个变异位的值，执行num_gene(基因数目)次这样的交换操作。
5.6.6终止条件
遗传算法采用设定演化代数的方法，但演化到一定数量的代数时，就停止演化。默认的演化代数时种群的大小（pool_size，缓冲池的大小）
5.6.7基于排列生成路径
在遗传算法中由排列生成连接路径
5.6.8实例分析
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）