目录

openGauss数据库SQL引擎
一.SQL引擎概览
二.SQL解析
三.查问优化

Ⅰ.查问重写Ⅱ.门路搜寻

openGauss数据库执行器技术
openGauss存储技术
openGauss事务机制
openGauss数据库安全

openGauss数据库SQL引擎

三、查问优化

Ⅱ、门路搜寻

优化器最外围的问题是针对某个SQL语句取得其最优解的问题，这个过程通常须要枚举SQL语句对应的解空间，也就是枚举不同的候选的执行门路，这些执行门路相互等价，然而执行效率不同，这对解空间中的这些执行门路计算它们的执行代价，最终能够取得一个最优的执行门路。根据候选执行门路的搜寻办法的不同，将优化器的构造划分为如下几种模式：

§ 自底向上模式：如图5所示，自底向上的模式会对逻辑执行打算进行拆解，先建设对表的扫描算子，而后由扫描算子形成连贯算子，最终堆成一个物理执行打算，在这个过程中，因为物理扫描算子和物理连贯算子有多种可能，因而会生成多个物理执行门路，优化器会依据各个执行门路的估算代价抉择出代价最低的执行打算，而后转交由执行器负责执行。

图5 自底向上模式
§ 自顶向下模式：该模式总体是使用面向对象思路，将优化器外围性能对象化，在词法剖析、语法分析、语义剖析后生成逻辑打算。基于此逻辑打算，利用对象化的优化规定，产生多个待选的逻辑打算，通过采纳自顶向下的办法遍历逻辑打算，联合动静布局、代价估算和分支限界技术，取得最优的执行门路，如图6所示。

图6 自顶向下模式

§ 随机搜寻模式：无论是自底向上模式还是自顶下模式，在参加连贯的表的数量比拟多的状况下，都会呈现枚举工夫过长的问题，一些优化器在表比拟多的状况下通过一些随机枚举的办法对门路进行搜寻，尝试在随机的解空间中取得次优的执行打算。

目前Oracle、MySQL、PostgreSQL等数据库的优化器采纳的是自底向上模式，SQL Server以及开源的Calcite、ORCA则采纳了自顶向下的模式，其中Calcite以良好的扩展性被广泛应用到其余开源我的项目里包含Apache Storm、Apache Flink、Apache Kylin、Apache Drill、SQL- Gremlin等我的项目。openGauss采纳的是自底向上模式和随机搜寻模式相结合的形式。

无论是自顶向下的搜寻模式还是自底向上的搜寻模式，搜寻的过程也都是一个从逻辑执行打算想物理执行打算转变的过程，例如针对每个表能够有不同的扫描算子，而逻辑连贯算子也能够转换为多种不同的物理连贯算子，上面介绍一下具体的物理算子。

  1. 单表扫描门路搜寻
    GausssDB采纳的是自底向上的门路搜寻办法，因而门路生成总是从单表拜访门路开始，对于单表拜访门路，个别有两种：

§ 全表扫描：对表中的数据一一拜访。

§ 索引扫描：借助索引来拜访表中的数据，通常须要联合谓词一起应用。

优化器首先依据表的数据量、过滤条件、可用的索引联合代价模型来估算各种不同扫描门路的代价。

例如：给定表定义CREATE TABLE t1(c1 int)；如果表中数据为1,2,3…100000000间断的整型值并且在c1列上有B+树索引，那么对于SELECT * FROM t1 WHERE 从c1=1来说，只有读取1个索引页面和1个表页面就能够获取到数据。然而对于全表扫描，须要读取1亿条数据能力获取同样的后果。在这种状况下索引扫描的门路胜出。

索引扫描并不是在所有状况下都优于全表扫描，它们的优劣取决于过滤条件可能多滤掉多少数据，通常数据库管理系统会采纳B+树来建设索引，如果在选择率比拟高的状况下，B+树索引会带来大量的随机IO，这会升高索引扫描算子的拜访效率。比方SELECT * FROM t1 WHERE c1>0；这条语句，索引扫描须要拜访索引中的全副数据和表中的全副数据，并且带来巨量的随机IO，而全表扫描只须要程序的拜访表中的全副数据，因而在这种状况下，全表扫描的代价更低。

  1. 多表连贯门路搜寻
    多表门路生成的难点次要在于如何枚举所有的表连贯程序（Join Reorder）和连贯算法（Join Algorithm）。

假如有两个表t1和t2做JOIN操作，依据关系代数中的交换律准则，能够枚举的连贯程序有t1 × t2和t2 × t1两种，JOIN的物理连贯算子有Hash Join、Nested Loop Join、Merge Join三种类型。这样一来，可供选择的门路有6种之多。这个数量随着表的增多会呈指数级增长，因而高效的搜索算法显得至关重要。

openGauss通常采纳自底向上的门路搜寻办法，首先生成了每个表的扫描门路，这些扫描门路在执行打算的最底层（第一层），在第二层开始思考两表连贯的最优门路，即枚举计算出每两表连贯的可能性，在第三层思考三表连贯的最优门路，即枚举计算出三表连贯的可能性，直到最顶层为止生成全局最优的执行打算。

假如有4个表做JOIN操作，它们的的连贯门路生成过程如下：

§ 单表最优门路：顺次生成{1}，{2}，{3}，{4}单表的最优门路。

§ 二表最优门路：顺次生成{1 2}，{1 3}，{1 4}，{2 3}，{2 4}，{3 4}的最优门路。

§ 三表最优门路：顺次生成{1 2 3}，{1 2 4}，{2 3 4}，{1 3 4}的最优门路。

§ 四表最优门路：生成{1 2 3 4}的最优门路即为最终门路。

多表门路问题外围为Join Order，这是NP（Nondeterministic Polynomially，非确定性多项式）类问题，在多个关系连贯中找出最优门路，比拟罕用的算法是基于代价的动静布局算法，随着关联表个数的增多，会产生表搜寻空间收缩的问题，进而影响优化器门路抉择的效率，能够采纳基于代价的遗传算法等随机搜索算法来解决。

另外为了避免搜寻空间过大，openGauss采纳了三种剪枝策略：

§ 尽可能先思考有连贯条件的门路，尽量推延笛卡尔积。

§ 在搜寻的过程中基于代价估算对执行门路采纳LowBound剪枝，放弃一些代价较高的执行门路。

§ 保留具备非凡物理属性的执行门路，例如有些执行门路的后果具备有序性的特点，这些执行门路可能在后序的优化过程中防止再次排序。

  1. 分布式门路搜寻
    openGauss优化引擎能够生成高效的分布式门路。在分布式架构下，同一个表的数据会散布到不同的DN上，创立表的时候能够抉择将数据在每个表上做Hash散布或者Random散布，为了正确执行两表连贯操作，可能须要将两个表的数据做从新散布能力失去正确的连贯后果，因而openGauss的分布式执行打算中减少了对数据进行重散布的两个算子：

§ Redistribute：将一个表的数据依照执行的Hash值在所有的DN上做重散布。

§ Broadcast：通过播送的形式从新散布一个表的数据，保障播送之后每个DN上都有这个表的数据的一份正本。

分布式门路生成时，会思考两表以及连贯条件上的数据是否处于同一个数据节点，如果不是，那么会增加相应的数据散发算子。例如：

CREATE TABLE t1(c1 int, c2 int) DISTRIBUTE BY hash(c1);
CREATE TABLE t2(c1 int, c2 int) DISTRIBUTE BY hash(c2);
SELECT * FROM t1 JOIN t2 ON t1.c1=t2.c1;
其中表t1采纳的是Hash散布办法，其散布键为c1列，表t2采纳的也是Hash散布办法，其散布键为c2列，因为SELECT查问中抉择条件是在t1.c1和t2.c2上做连贯操作，这两个列的散布不同，因而做连贯之前须要增加数据重散布来确保连贯的数据在同一数据节点上。那么有如下几种可供选择的门路如图7所示。

图7 分布式打算示例

依据散发算子所须要解决的数据量以及网络通信所带来的耗费，能够计算这些门路的代价，openGauss优化引擎会依据代价从中选出最优的门路。

  1. 利用物理属性优化
    关系的自身能够视为一个汇合或者包，这种数据结构对数据的散布没有设定，为了晋升计算的性能，咱们须要借助一些数据结构或算法来对数据的散布做一些预处理，这些预处理办法或者利用了物理执行门路的物理属性（例如有序性），或者为物理执行门路创立物理属性，总之这些属性常常会在查问优化中施展微小的作用。

1） B+树
如果要查问一个表中的数据，最简略的方法天然是将表中的数据全副遍历一遍，然而随着以后数据量的越来越大，遍历表中数据的代价也越来越高，而B+树就成了咱们高效的查问数据的无力武器。

1970年，R.Bayer和E.mccreight提出了一种实用于外查找的树，它是一种均衡的多叉树，称为B树，B树就是在表的数据上建设一个“目录”，相似于书籍中的目录，这样就能疾速的定位到要查问的数据。

B+树作为一种数据结构和查问优化器自身没有间接的关系，然而数据库管理系统通常会建设基于B+树的索引，而在查问优化的过程中，能够通过索引扫描、位图扫描的办法进步查问效率，这都会波及到这种B+树类型的索引的应用。

2） Hash表
Hash表也是一种对数据进行预处理的办法，openGauss数据库在多个中央应用了Hash表或借用了Hash表的思维来晋升查问效率：

§ 借用Hash能够实现分组操作，因为Hash表人造就有对数据分类的性能。

§ 借用Hash能够建设Hash索引，这种索引实用于等值的约束条件。

§ 物理连贯门路中Hash Join是十分重要的一条门路。

3） 排序
排序也是一种对数据进行预处理的办法，它次要用在以下几个方面：

§ 借用排序能够实现分组操作，因为通过排序之后，雷同的数据都汇集在一起，因而它能够用来实现分组。

§ B树索引的建设须要借助排序来实现。

§ 物理连贯门路Merge Join门路须要借助排序实现。

§ SQL语言中的Order By操作须要借助排序实现。

在数据量比拟小时，数据能够全副加载到内存，这时候应用内排序就能实现排序的工作，而当数据量比拟大时，则须要应用外排序能力实现排序的工作，因而在计算排序的代价时须要依据数据量的大小以及可应用的内存的大小来决定排序的代价。

4） 物化
物化就是将扫描操作或者连贯操作的后果保存起来，如果在两头后果比拟大的状况下可能须要将后果写入外存，这会产生IO代价，因而这种保留是有代价的。

物化的长处是如果内表能够一次读取屡次应用，那么就能够将这个两头后果保留下来屡次利用，例如有t1表和t2表做连贯，如果t2表作为内表通过扫描之后，只有5%的数据作为两头后果，其余95%的数据都被过滤掉了，那么就能够思考将这5%的数据物化起来，这样t1表的每条元组就只和这5%的数据进行连贯就能够了。

两头后果是否物化次要取决于代价计算的模型，通常物理优化生成物理门路时对物化和不物化两条门路都会计算代价，最终抉择代价较低的一个。

未完待续......