Gauss松鼠会
学习 探索 分享数据库知识 共建数据库技术交流圈
关注上篇图文openGauss数据库源码解析系列文章——SQL引擎源码解析（一），从SQL引擎概述和SQL解析两方面进行了详细论述，本篇将接着从SQL引擎的查询优化展开介绍，完整版内容请查看CSDN·Gauss松鼠会专栏博客，以下内容为章节试读：
三、查询优化
openGauss数据库的查询优化过程功能比较明晰，从源代码组织的角度来看，相关代码分布在不同的目录下，如表1所示。表1 查询优化模块说明
| 模块 | 目录 | 说明 |
| 查询重写 | src/gausskernel/optimizer/prep | 主要包括子查询优化、谓词化简及正则化、谓词传递闭包等查询重写优化技术 |
| 统计信息 | src/gausskernel/optimizer/commands/analyze.cpp | 生成各种类型的统计信息，供选择率估算、行数估算、代价估算使用 |
| 代价估算 | src/common/backend/utils/adt/selfuncs.cppsrc/gausskernel/optimizer/path/costsize.cpp | 进行选择率估算、行数估算、代价估算 |
| 物理路径 | src/gausskernel/optimizer/path | 生成物理路径 |
| 动态规划 | src/gausskernel/optimizer/plan | 通过动态规划方法对物理路径进行搜索 |
| 遗传算法 | src/gausskernel/optimizer/geqo | 通过遗传算法对物理路径进行搜索 |
（一）查询重写
SQL语言是丰富多样的，非常的灵活，不同的开发人员依据经验的不同，手写的SQL语句也是各式各样，另外还可以通过工具自动生成。SQL语言是一种描述性语言，数据库的使用者只是描述了想要的结果，而不关心数据的具体获取方式，输入数据库的SQL语言很难做到是以最优形式表示的，往往隐含了一些冗余信息，这些信息可以被挖掘用来生成更加高效的SQL语句。查询重写就是把用户输入的SQL语句转换为更高效的等价SQL，查询重写遵循两个基本原则。
（1） 等价性：原语句和重写后的语句，输出结果相同。
（2） 高效性：重写后的语句，比原语句在执行时间和资源使用上更高效。
查询重写主要是基于关系代数式的等价变换，关系代数的变换通常满足交换律、结合律、分配率、串接率等，如表2所示。表2 关系代数等价变换
| 等价变换 | 内容 |
| 交换律 | A × B == B × AA ⨝B == B ⨝ AA ⨝F B == B ⨝F A ……其中F是连接条件Π p(σF (B)) == σF (Π p(B)) ……其中F∈p |
| 结合律 | (A × B) × C==A × (B × C)(A ⨝ B) ⨝ C==A ⨝ (B ⨝ C)(A ⨝F1 B) ⨝F2 C==A ⨝F1 (B ⨝F2 C) …… F1和F2是连接条件 |
| 分配律 | σF(A × B) == σF(A) × B …… 其中F ∈ AσF(A × B) == σF1(A) × σF2(B)…… 其中F = F1 ∪ F2，F1∈A, F2 ∈B σF(A × B) == σFX (σF1(A) × σF2(B))…… 其中F = F1∪F2∪FX，F1∈A, F2 ∈BΠ p,q(A × B) == Π p(A) × Π q(B) …… 其中p∈A，q∈BσF(A × B) == σF1(A) × σF2(B)…… 其中F = F1 ∪ F2，F1∈A, F2 ∈B σF(A × B) == σFx (σF1(A) × σF2(B))…… 其中F = F1∪F2∪Fx，F1∈A, F2 ∈B |
| 串接律 | Π P=p1,p2,…pn(Π Q=q1,q2,…qn(A)) == Π P=p1,p2,…pn(A)……其中P ⊆ QσF1(σF2(A)) == σF1∧F2(A) |
查询重写优化既可以基于关系代数的理论进行优化，例如谓词下推、子查询优化等，也可以基于启发式规则进行优化，例如Outer Join消除、表连接消除等。另外还有一些基于特定的优化规则和实际执行过程相关的优化，例如在并行扫描的基础上，可以考虑对Aggregation算子分阶段进行，通过将Aggregation划分成不同的阶段，可以提升执行的效率。
从另一个角度来看，查询重写是基于优化规则的等价变换，属于逻辑优化，也可以称为基于规则的优化，那么怎么衡量对一个SQL语句进行查询重写之后，它的性能一定是提升的呢？这时基于代价对查询重写进行评估就非常重要了，因此查询重写不只是基于经验的查询重写，还可以是基于代价的查询重写。
以谓词传递闭包和谓词下推为例，谓词的下推能够极大的降低上层算子的计算量，从而达到优化的效果，如果谓词条件有存在等值操作，那么还可以借助等值操作的特性来实现等价推理，从而获得新的选择条件。
例如，假设有两个表t1、t2分别包含[1,2,3,..100]共100行数据，那么查询语句SELECT t1.c1, t2.c1 FROM t1 JOIN t2 ON t1.c1=t2.c1 WHERE t1.c1=1则可以通过选择下推和等价推理进行优化，如图1所示。
图1 查询重写前后对比图
如图1（1）所示，t1、t2表都需要全表扫描100行数据，然后再做join，生成100行数据的中间结果，最后再做选择操作，最终结果只有1行数据。如果利用等价推理，可以得到{t1.c1, t2.c1, 1}的是互相等价的，从而推导出新的t2.c1=1的选择条件，并把这个条件下推到t2上，从而得到图1（4）重写之后的逻辑计划。可以看到，重写之后的逻辑计划，只需要从基表上面获取1条数据即可，join时内、外表的数据也只有1条，同时省去了在最终结果上的过滤条件，性能大幅提升。
在代码层面，查询重写的架构大致如图2所示。
图2 查询重写的架构
（1） 提升子查询：子查询出现在RangeTableEntry中，它存储的是一个子查询树，若子查询不被提升，则经过查询优化之后形成一个子执行计划，上层执行计划和子查询计划做嵌套循环得到最终结果。在该过程中，查询优化模块对这个子查询所能做的优化选择较少。若该子查询被提升，转换成与上层的join，由查询优化模块常数替换等式：由于常数引用速度更快，故将可以求值的变量求出来，并用求得的常数替换它，实现函数为preprocess_const_params。
（2） 子查询替换CTE：理论上CTE（common table expression，通用表达式）与子查询性能相同，但对子查询可以进行进一步的提升重写优化，故尝试用子查询替换CTE，实现函数为substitute_ctes_with_subqueries。
（3） multi count(distinct)替换为多条子查询：如果出现该类查询，则将多个count(distinct)查询分别替换为多条子查询，其中每条子查询中包含一个count(distinct)表达式，实现函数为convert_multi_count_distinct。
……（本节内容未完）
为提升您的阅读体验，完整版内容已运用专业格式发布到CSDN·Gauss松鼠会专栏，请扫码下方二维码，“关注”后进行内容阅读或点击文末“阅读原文”进入博客进行学习~
Gauss松鼠会
汇集数据库从业人员及爱好者互助解决问题 共建数据库技术交流圈
完整版内容，请点击“阅读原文”
