openGauss SQL引擎专题

2025-03-28  本文已影响0人  这货不是王马勺

数据库的SQL引擎是数据库重要的子系统之一，它对上负责承接应用程序发送的SQL语句，对下负责指挥执行器运行执行计划。
其中优化器作为SQL引擎中最重要、最复杂的模块，被称为数据库的“大脑”，优化器产生的执行计划的优劣直接决定数据库的性能。

1. SQL引擎概览

SQL引擎是数据库系统的重要组成部分，主要职责是将应用程序输入的SQL语句在当前负载场景下生成高效的执行计划，在SQL语句的高效执行上扮演重要角色。

SQL语句在SQL引擎中的执行过程如图：

可以看出，应用程序的SQL语句需要经过SQL解析生成逻辑执行计划、经过查询优化生成物理执行计划，然后将物理执行
计划转交给查询执行引擎做物理算子的执行操作。

SQL解析通常包含词法分析、语法分析、语义分析几个子模块。
SQL是介于关系演算和关系代数之间的一种描述性语言，它吸取了关系代数中一部分逻辑算子的描述，而放弃了关系代数中“过程化”的部分，SQL解析主要的作用就是将一个SQL语句编译成为一个由关系算子组成的逻辑执行计划。

描述语言的特点是规定了需要获取的WHAT，而不关心HOW，也就是只关注结果而不关注过程，因此SQL描述性的特点导致查询优化在数据库管理系统中具有非常重要的作用。

查询重写则是在逻辑执行计划的基础上进行等价的关系代数变换，这种优化也可以称为代数优化，虽然两个关系代数式获得的结果完全相同，但是它们的执行代价却可能有很大的差异，这就构成了查询重写优化的基础。

在早期的数据库管理系统中，通常采用基于启发式规则的方法来生成最优的物理执行计划，但是这种基于规则的优化的灵活度不够，常常产生一些次优的执行计划，而代价估算的引入，则从根本上解决了基于规则优化的不足。

基于代价的优化器一方面生成“候选”的物理执行路径，另一方面计算这些执行路径执行代价，这样就建立了执行路径的筛选标准，从而能够通过比较代价而获得最优的物理执行计划。

2. SQL解析

SQL语句在数据库管理系统中的编译过程符合编译器实现的常规过程，需要进行词法分析、语法分析和语义分析。

在SQL标准中，确定了SQL的关键字以及语法规则信息，SQL解析器在做词法分析的过程中会将一个SQL语句根据关键字信息以及间隔信息划分为独立的原子单位，每个单位以一个词的方式展现，例如有SQL语句：

select w_name from warehouse where w_no = 1;

该SQL语句可以划分的关键字、标识符、运算符、常量等原子单位如表所示：

词性 内容
关键字 select , from , where
标识符 w_name, warehouse , w_no
运算符 =
常量 1

语法分析会根据词法分析获得的词来匹配语法规则，最终生成一个抽象语法树，每个词作为语法树的叶子节点出现，如图:

抽象语法树表达的语义还仅仅限制在能够保证应用的SQL语句符合SQL标准的规范，但是对于SQL语句的内在含义还需要做有效性检查。

在有效性检查的同时，语义分析的过程还是有效性语义绑定（Bind）的过程，通过语义分析的检查，抽象语法树就转换成一个逻辑执行计划。

逻辑执行计划可以通过关系代数表达式的形式来表现，如图:


3. 查询优化

SQL语句在编写的过程中，数据库应用开发人员通常会考虑以不同的形式编写SQL语句达到提升执行性能的目的。
那么，为什么还需要查询优化器来对SQL进行优化呢？
这是因为一个应用程序可能会涉及大量的SQL语句，而且有些SQL语句的逻辑极为复杂，数据库开发人员很难面面俱到地写出高性能语句，而查询优化器则具有一些独特的优势：

因此，查询优化器是提升查询效率的非常重要的一个手段，虽然一些数据库也提供了人工干预执行计划生成的方法，但是通常而言，查询优化器的优化过程对数据库开发人员是透明的，它自动进行逻辑上的等价变换、自动进行物理执行计划的筛选，极大地提高了数据库应用程序开发人员的“生产力”。

依据优化方法的不同，优化器的优化技术可以分为：

在早期的数据库中，查询优化器通常采用启发式规则进行优化，这种优化方式不够灵活，往往难以获得最优的执行代价，而基于代价的优化则能够针对大多数场景高效筛选出性能较好的执行计划，但面对千人千面的用户和日趋复杂的实际查询场景，普适性的查询优化难以捕捉到用户特定的查询需求、数据分布、硬件性能等特征，难以全方位满足实际的优化需求。

近年来AI技术发展迅速，特别是在深度学习领域。
ABO在建模效率、估算准确率和自适应性等方面都有很大优势，有望打破RBO和CBO基于静态模型的限制。
通过对历史经验的不断学习，ABO将目标场景的模式进行抽象化，形成动态的模型，自适应地针对用户的实际场景进行优化。当前很多数据库产品采用基于CBO的优化技术，另外在ABO方面也在进行积极探索。

3.1 查询重写

查询重写利用已有语句特征和关系代数运算来生成更高效的等价语句，在数据库优化器中扮演关键角色，尤其在复杂查询中，能够在性能上带来数量级的提升，可谓是“立竿见影”的“黑科技”。
下面介绍查询重写的基本概念、常见的查询重写技术、查询重写面临的挑战等内容。

3.1.1 查询重写的概念

SQL是丰富多样的，应用非常灵活，不同的开发人员依据不同的经验，编写的SQL语句也是各式各样，SQL语句还可以通过工具自动生成。
SQL是一种描述性语言，数据库的使用者只是描述了想要的结果，而不关心数据的具体获取方式。
输入数据库的SQL语句很难做到以最优形式表示，往往隐含了冗余信息，这些信息可以被挖掘以生成更加高效的SQL语句。
查询重写就是把用户输入的SQL语句转换为更高效的等价SQL。
查询重写遵循两个基本原则：

3.1.2 关系代数式等价变换

查询重写主要是基于关系代数式的等价变换，关系代数式变换通常满足交换律、结合律、分配率、串接率等：

等价变换规则并不能把所有的情况都列举出来，例如，如果对

继续推导，那么就可以得到：

因此，在熟悉了关系代数的操作之后，就可以灵活地利用关系代数的等价关系进行推导，获得更多的等价式。
这些等价的变换一方面可以用来根据启发式的规则做优化，保证等价转换之后的关系代数表达式的执行效率提高而非降低，例如借助分配率可以将一个选择操作下推，降低上层节点的计算量，另一方面还可以用来生成候选的执行计划，再由优化器根据估算的代价进行筛选。

3.1.3 常见的查询重写技术

下面介绍几个关键的查询重写技术：常量表达式化简、子查询优化、选择下推和等价推理、外连接消除、DISTINCT消除、IN谓词展开、视图展开等。

常量表达式即用户输入的SQL语句中包含运算结果为常量的表达式，如算数表达式、逻辑运算表达式、函数表达式，查询重写可以对常量表达式预先计算以提升效率。
例如下面语句为典型的算数表达式查询重写，经过重写之后，避免了在执行时每条数据都需要进行1+1运算。

select * from t1 where c1 = 1 + 1;
# 常量表达式化简后
select * from t1 where c1 = 2;

下面语句为典型的逻辑运算表达式查询重写，经过重写之后，条件永远为false，可以直接返回0行结果，避免了整个语句的实际执行。

select * from t1 where 1 = 0 and a = 1;
# 常量表达式化简后
select * from t1 where false;

下面语句包含函数表达式，由于函数的输入参数为常量，经过重写之后，直接把函数运算结果在优化阶段计算出来，避免了在执行过程中逐条数据的函数调用开销。

select * from t1 where c1 = ADD(1,1);
# 常量表达式化简后
select * from t1 where c1 = 2;

由于子查询表示的结构更清晰，符合人们的阅读理解习惯，用户输入的SQL语句往往包含了大量的子查询。
子查询有几种分类方法，根据子查询是否可以独立求解，分为相关子查询和非相关子查询。

①相关子查询：相关子查询是指子查询中有依赖父查询的条件，例如：

select * from t1 where exists(select t2.c1 from t2 where t1.c1 = t2.c1);

语句中子查询依赖父查询传入t1.c1的值。

②非相关子查询：非相关子查询是指子查询不依赖父查询，可以独立求解，例如：

select * from t1 where exists(select t2.c1 from t2);

语句中子查询没有依赖父查询的条件。

其中，相关子查询需要父查询执行出一条结果，然后驱动子查询运算，这种嵌套循环的方式执行效率较低。
如果能把子查询提升为与父查询同级别，那么子查询中的表就能和父查询中的表直接做Join（连接）操作，由于Join操作可以有多种实现方法，优化器就可以从多种实现方法中选择最优的一种，就有可能提高查询的执行效率，另外优化器还能够应用Join Reorder优化规则对不同表的连接顺序进行交换，进而有可能产生更好的执行计划。

下面语句为典型的子查询提升重写，重写之后利用Semi Join可以提升查询性能。

select * from t1 where t1.c1 in (select t2.c1 from t2);
# 子查询优化后
select * from t1 semi join t2 on t1.ci = t2.c1;

Semi-Join即半连接，当外表在内表中找到匹配的记录之后，Semi-Join会返回外表中的记录。
但即使在内表中找到多条匹配的记录，外表也只会返回已经存在于外表中的记录。
而对于子查询，外表的每个符合条件的元组都要执行一轮子查询，效率比较低下。
此时使用半连接操作优化子查询，会减少查询次数，提高查询性能。
其主要思路是将子查询上拉到父查询中，这样内表和外表是并列关系，外表的每个符合条件的元组，只需要在内表中找符合条件的元组即可，所以效率会大大提高。

选择下推能够极大降低上层算子的计算量，从而达到优化的效果，如果选择条件存在等值操作，那么还可以借助等值操作的特性来实现等价推理，从而获得新的选择条件。

例如，假设有两个表t1、t2，它们分别包含1，2，…，100共100行数据，那么查询语句则可以通过选择下推和等价推理进行优化：

select t1.c1, t2.c1 from t1 join t2 on t1.ci = t2.c1 where t1.c1 = 1;

如图，t1、t2表都需要全表扫描100行数据，然后再做Join操作，生成100行数据的中间结果，最后再做选择操作，最终结果只有1行数据。
如果利用等价推理，可以得到{t1.c1，t2.c1，1}是互相等价的，从而推导出新的t2.c1=1的选择条件，并把这个条件下推到t2表上，从而得到图中重写之后的逻辑计划。
可以看到，重写之后的逻辑计划，只需要从基表上获取1条数据即可，连接时内、外表的数据也只有1条，同时省去了在最终结果上的过滤条件，使性能大幅提升。

外连接和内连接的主要区别是对于不能产生连接结果的元组需要补充NULL值，如果SQL语句中有过滤条件符合空值拒绝的条件（即会将补充的NULL值再过滤掉），则可以直接消除外连接。

外连接转成内连接之后，便于优化器应用更多的优化规则，提高执行效率。
SQL语句如下：

select * from t1 full join t2 
on t1.c1 = t2.c1 
where t1.c2 > 5 and t2.c3 < 10;
# 外连接消除后
select * from t1 inner join t2 
on t1.c1 = t2.c1 
where t1.c2 > 5 and t2.c3 < 10;

DISTINCT列上如果有主键约束，则此列不可能为空，且无重复值，因此可以不需要DISTINCT操作，减少计算量。

例：c1列上的主键属性决定了无须做DISTINCT操作。
语句如下：

create table t1(c1 int primary key , c2 int);
select distinct(c1) from t1;
# distinct消除后
select c1 from t1;

将IN运算符改写成等值的过滤条件，便于借助索引减少计算量。
语句如下：

select * from t1 where c1 in (10,20,30);  
# IN谓词展开后
select * from t1 where c1 = 10  or c1 = 20 or c1 = 30;

视图从逻辑上可以简化书写SQL的难度，提高查询的易用性，而视图本身是虚拟的，因此在查询重写的过程中，需要展开视图。

可以将视图查询重写成子查询的形式，然后再对子查询做简化。
语句如下：

create view v1 as (select * from t1,t2 where t1.c1 = t2.c2);
select * from v1;
# 视图展开后重写成子查询的形式
select * from(select * from t1,t2 where t1.c1 = t2.c2) as v1;
# 视图展开后对子查询做简化
select * from t1,t2 where t1.c1 = t2.c2;

3.2 路径搜索

优化器最核心的问题是针对某个SQL语句获得其最优解。
这个过程通常需要枚举SQL语句对应的解空间，也就是枚举不同的候选执行路径。
这些候选执行路径互相等价，但是执行效率不同，需要对它们计算执行代价，最终获得一个最优的执行路径。
依据候选执行路径的搜索方法的不同，将优化器的结构划分为如下几种模式：

openGauss采用的是自底向上模式和随机搜索模式相结合的方式。
无论是自顶向下的搜索模式还是自底向上的搜索模式，搜索的过程也都是一个从逻辑执行计划向物理执行计划转变的过程，例如针对每个表可以有不同的扫描算子，而逻辑连接算子也可以转换为多种不同的物理连接算子。下面介绍具体的物理算子。

3.2.1 单表扫描路径搜索

openGauss采用的是自底向上的路径搜索方法，因此路径生成总是从单表访问路径开始。
对于单表访问路径，一般有两种：

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

例如：给定表定义

CREATE TABLE t1(c1 int);

如果表中数据为1，2，…，100000000的连续整型数并且在c1列上有B+树索引，那么对于语句：

SELECT * FROM t1 WHERE c1=1；

只要读取1个索引页面和1个表页面就可以获取到数据。
然而对于全表扫描，需要读取1亿条数据才能获取同样的结果。
在这种情况下索引扫描的路径胜出。

索引扫描并不是在所有情况下都优于全表扫描，它们的优劣取决于过滤条件能够过滤掉多少数据，通常数据库管理系统会采用B+树来建立索引，如果在选择率比较高的情况下，B+树索引会带来大量的随机IO，这会降低索引扫描算子的访问效率。
比如：

SELECT * FROM t1 WHERE c1>0;

这条语句，索引扫描需要访问索引中的全部数据和表中的全部数据，并且带来巨量的随机IO，而全表扫描只需要顺序地访问表中的全部数据，因此在这种情况下，全表扫描的代价更低。

3.2.2 多表连接路径搜索

多表路径生成的难点主要在于如何枚举所有的表连接顺序（Join Reorder）和连接算法（Join Algorithm）。
假设对t1和t2两个表做Join操作，根据关系代数中的交换律，可以枚举的连接顺序有t1×t2和t2×t1两种，Join的物理连接算子HashJoin、NestLoop、MergeJoin三种类型。
这样一来，可供选择的路径有6种之多。
这个数量随着表的增多呈指数级增长，因此高效的搜索算法显得至关重要。

openGauss通常采用自底向上的路径搜索方法，首先生成每个表的扫描路径，这些扫描路径在执行计划的最底层（第一层），然后在第二层开始考虑两表连接的最优路径，即枚举计算出两表连接的可能性，再在第三层考虑三表连接的最优路径，即枚举计算出三表连接的可能性，直到最顶层为止，生成全局最优的执行计划。

假设有4个表做Join操作，它们的连接路径生成过程如下：

多 表 路 径 问 题 的 核 心 为 Join Order ， 这 是NP（Nondeterministic Polynomially，非确定性多项式）类问题。
在多个关系连接中找出最优路径，比较常用的算法是基于代价的动态规划算法，随着关联表个数的增多，会发生表搜索空间膨胀的问题，影响优化器路径选择的效率，可以采用基于代价的遗传算法等随机搜索算法来解决。

另外为了防止搜索空间过大，openGauss采用了下面三种剪枝策略：

3.2.3 分布式路径搜索

openGauss优化引擎可以生成高效的分布式路径。
在分布式架构下，同一个表的数据会分布到不同的DN（数据节点）上，创建表的时候可以选择将数据在每个表上做哈希（Hash）分布或者随机分布，为了正确执行两表连接操作，可能需要将两个表的数据重新分布才能得到正确的连接结果，因此openGauss的分布式执行计划中增加了对数据进行重分布的两个算子：

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

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.c2;

其中表t1采用的是哈希分布方法，其分布键为c1列，表t2采用的也是哈希分布方法，其分布键为c2列，由于SELECT查询中选择条件是在t1.c1和t2.c2上做连接操作，这两个列的分布不同，因此做连接
操作之前需要添加数据重分布来确保连接的数据在同一数据节点上。
那么有如下几种可供选择的路径，如图:

根据分发算子所需要处理的数据量以及网络通信所带来的消耗，可以计算这些路径的代价，openGauss优化引擎会根据代价从中选出最优的路径。

3.2.4 利用物理属性优化

关系的本身可以视为一个集合或者包，这种数据结构对数据的分布没有设定，为了提升计算的性能，需要借助一些数据结构或算法来对数据的分布做一些预处理，这些预处理方法或者利用了物理执行路径的物理属性（例如有序性），或者为物理执行路径创建物理属性，总之这些属性经常会在查询优化中发挥巨大的作用。

如果要查询一个表中的数据，最简单的办法自然是将表中的数据全部遍历一遍，但是随着当前数据量变得越来越大，遍历表中数据的代价也越来越高，而B+树就成了高效查询数据的有力武器。
1970年，R. Bayer和E. Mccreight提出了一种适用于外查找的树，它是一种平衡的多叉树，称为B树，B树就是在表的数据上建立一个“目录”，类似于书中的目录，这样就能快速地定位到要查询的数据。
B+树作为一种数据结构，和查询优化器本身没有直接的关系，但是数据库管理系统通常会建立基于B+树的索引，而在查询优化的过程中，可以通过索引扫描、位图扫描的方法提高查询效率，这都会涉及这种B+树类型的索引的使用。

哈希表也是一种对数据进行预处理的方法。
openGauss数据库在多个地方使用了哈希表或借用了哈希表的思想来提升数据查询效率：
（1）借用哈希可以实现分组操作，因为哈希表天然就有对数据分类的功能。
（2）借用哈希可以建立哈希索引，这种索引适用于等值的约束条件。
（3）物理连接路径中Hash Join是非常重要的一条路径。

排序也是一种对数据进行预处理的方法。
它主要用在以下几个方面：
（1）借用排序可以实现分组操作，因为经过排序之后，相同的数据都聚集在一起，因此可以用来实现分组。
（2）B树索引的建立需要借助排序来实现。
（3）物理连接路径Merge Join路径需要借助排序实现。
（4）SQL中的Order By操作需要借助排序实现。

在数据量比较小时，数据可以全部加载到内存，这时候使用内排序就能完成排序的工作，而当数据量比较大时，则需要使用外排序才能完成排序的工作，因此在计算排序的代价时需要根据数据量的大小及可使用的内存的大小来决定排序的代价。

物化就是将扫描操作或者连接操作的中间结果保存起来，如果中间结果比较大可能需要将结果写入外存，这会产生IO代价，因此这种保存是有代价的。
物化的优点是如果内表的中间结果可以一次读取并多次使用，那么就可以将这个中间结果保存下来多次利用。
例如有t1表和t2表做连接，如果t2表作为内表经过扫描之后，只有5%的数据作为中间结果，其他95%的数据都被过滤掉了，那么就可以考虑将这5%的数据物化起来，这样t1表的每条元组就只和这5%的数据进行连接就可以了。
中间结果是否物化主要取决于代价计算的模型，通常物理优化生成物理路径时对物化和不物化两条路径都会计算代价，最终选择代价较低的一个。

3.3 代价估算

优化器会根据生成的逻辑执行计划枚举出候选的执行路径，要确保执行的高效，就需要在这些路径中选择开销最小、执行效率最高的路径。
那么如何评估这些计划路径的执行开销就变得非常关键。
代价估算就是来完成这项任务的，基于收集的数据统计信息，对不同的计划路径建立代价估算模型，评估所给出的代价，为路径搜索提供输入。

3.3.1 统计信息

统计信息是计算计划路径代价的基石，统计信息的准确度对代价估算模型中行数估算和代价估算起着至关重要的作用，直接影响查询计划的优劣。
openGauss支持使用Analyze命令完成对全库、单表、列、相关性多列进行统计信息收集。

由于统计信息直接影响代价计算的准确度，所以统计信息收集的频率就是一个非常敏感的参数，如果统计信息收集的频率太低，则会导致统计信息的滞后，相反，如果过于频繁地收集统计信息，则会间接影响查询的性能。

通常数据库管理系统会提供手动的收集统计信息的方法，openGauss支持通过Analyze命令来收集统计信息，同时数据库管理系统也会根据数据变化的情况自动决定是否重新收集统计信息。
例如当一个表中数据的频繁更新程度超过了一个阈值，那么就需要自动更新这个表的统计信息。
在查询优化的过程中，如果优化器发现统计信息的数据已经严重滞后，也可以发起统计信息的收集工作。

表级的统计信息通常包括元组的数量（N）、表占有的页面数（B），而列级的统计信息则主要包括属性的宽度（W）、属性的最大值（Max）、最小值（Min）、高频值（MCV）等，通常针对每个列会建立一个直方图（H），将列中的数据按照范围以直方图的方式展示出来，可以更方便地计算选择率。

直方图通常包括等高直方图、等频直方图和多维直方图等，这些直方图可以从不同的角度来展现数据的分布情况。
openGauss采用的是等高直方图，直方图的每个柱状体都代表了相同的频率。

3.3.2 选择率

通过统计信息，代价估算系统就可以了解一个表有多少行数据，用了多少个数据页面，某个值出现的频率等，然后根据这些信息就能计算出一个约束条件（例如SQL语句中的WHERE条件）能够过滤掉多少数据，这种约束条件过滤出的数据占总数据量的比例称为选择率。

约束条件可以是由独立的表达式构成的，也可以是由多个表达式构成的合取范式或析取范式，其中独立的表达式需要根据统计信息计算选择率，合取范式和析取范式则借助计算概率的方法获得选择率。

假设要对约束条件“A>5 and B<3”计算选择率，那么首先需要对A>5和B<3分别计算选择率，由于已经有了A列和B列的统计信息，因此可以根据统计信息计算出A列中值大于5的数据比例，类似的，还可以计算出B列的选择率。
假设A>5的选择率为0.3，B<3的选择率为0.5，那么“A>5 and B<3”的选择率为：

由于约束条件的多样性，选择率的计算通常会遇到一些困难，例如选择率在计算过程中通常假设多个表达式之间是相互“独立”的，但实际情况中不同的列之间可能存在函数依赖关系，因此这时候就可能导致选择率的计算不准确。

3.3.3 代价估算方法

openGauss的优化器是基于代价的优化器，对每条SQL语句，openGauss都会生成多个候选计划，并且给每个计划计算一个执行代价，然后选择代价最小的计划。

当一个约束条件确定了选择率之后，就可以确定每个计划路径所需要处理的行数，并根据行数可以推算出所需要处理的页面数。
当计划路径处理页面的时候，会产生IO代价，而当计划路径处理元组的时候 （例如针对元组做表达式计算） ， 会产生 CPU 代价 ，由于openGauss是分布式数据库，在CN和DN之间传输数据（元组）会产生通信的代价，因此一个计划的总体代价可以表示为：

总代价=IO代价+CPU代价+通信代价

openGauss把所有顺序扫描一个页面的代价定义为单位1，所有其他算子的代价都归一化到这个单位1上。
比如把随机扫描一个页面的代价定义为4，即认为随机扫描一个页面所需的代价是顺序扫描一个页面所需代价的4倍。
又比如，把CPU处理一条元组的代价定义为0.01，即认为CPU处理一条元组所需代价为顺序扫描一个页面所需代价的百分之一。

从另一个角度来看，openGauss将代价又分成了启动代价和执行代价，其中：

总代价=启动代价+执行代价

代价计算示例：

如图所示，SQL查询中包含两张表，分别为t1、t2，它的某个候选计划的计算过程如下：

注释

参考：

https://bbs.csdn.net/topics/618125897
``
上一篇 下一篇

猜你喜欢

热点阅读