GaussDB(DWS)的执行引擎继承自PG，对于优化器生成的执行计划树，总体采取执行算子+流水线的处理方式。对于NestLoop 算子节点，需要首先从左树的IndexScan算子节点获取元组，然后到右子树的IndexScan算子节点进行连接，匹配元组后进行输出。流水线的执行方式使得对于NestLoop, IndexScan类的一般算子，同时只有一定数量的元组处于内存中，对于行引擎每个算子仅占用一条元组的空间，对于列引擎占用一个batch（最多1000条元组）的空间，占用的空间较小，基本可以忽略不计。但是，GaussDB(DWS)中也有一些需要将所有数据收集后进行处理的算子，在执行时需要使用较多的内存，通常我们称这类算子为物化算子。GaussDB(DWS)中主要存在如下不同种类的物化算子： 1) HashJoin：Hash连接操作符，主要思想是计算左右两表连接列的hash值，通过hash值比较减少元组比较的次数，需要将一个表建立hash表，另一个表进行hash值比较操作，建立hash表需要在内存中进行； 2) HashAgg：Hash聚集操作符，主要思想同HashJoin类似，通过hash值比较减少元组去重比较的次数，需要将不同值的元组保存的内存中； 3) Sort：排序操作符，需要获取所有元组后进行排序操作，待排序元组均存在于内存中； 4) Materialize：物化操作符，通常在需要重复扫描时使用，通过将结果存储在内存中，保证重复扫描时的效率。 

一般而言，Aggregate Path 生成是在表关联的 Path 生成之后，且有三个主要步骤（Unique Path的Aggregate在Join Path生成的时候就已经完成了，但也会有这三个步骤）：先估算出聚集结果的行数，然后选择Path的方式，最后创建出最优Aggregate Path。前者依赖于统计信息和 Cost 估算模型，后者取决于前者的估算结果、集群规模和系统资源。Aggregate 行数估算主要根据聚集列的 distinct 值来组合，我们重点关注Aggregate 行数估算和最优Aggregate Path选择。统计信息显示t1.c2和t2.c2的原始distinct值分别是-0.25和100，-0.25转换为绝对值就是0.25 * 2000 = 500，那它们的组合distinct是不是至少应该是500呢？答案不是。因为Aggregate对JoinRel(t1, t2)的结果进行聚集，而系统表中统计信息是原始信息（没有任何过滤）。这时需要把Join条件和过滤条件都考虑进去，如何考虑呢？首先看过滤条件 “t1.c1<500“可能会过滤掉一部分t1.c2，那么就会有个选择率（此时我们称之为 FilterRatio），然后 Join 条件"t1.c2 = t2.c2"也会有一个选择率（此时我们称之为JoinRatio），这两个 Ratio 都是介于[0, 1]之间的一个数，于是估算t1.c2的distinct时这两个Ratio影响都要考虑。如果不同列之间选择Poisson模型，相同列之间用完全相关模型。

1) Join 路径的选择时，会分两个阶段计算代价，initial和final 代价，initial 代价快速估算了建hash表 、计 算 hash值以及下盘的代价，当initial代价已经比path_list中某个path大时，就提前剪枝掉该路径； 2) cheapest_total_path 有多个原因：主要是考虑到多个维度下，代价很相近的路径都有可能是下一层动态规划的最佳选择，只留一个可能得不到整体最优计划； 3) cheapest_startup_path 记录了启动代价最小的一个，这也是预留了另一个维度，当查询语句需要的结果很少时，有一个启动代价很小的 Path，但总代价可能比较大，这个Path有可能会成为首选； 4) 由于剪枝的原因，有些情况下，可能会提前剪枝掉某个Path，或者这个Path没有被选为cheapest_total_path或cheapest_startup_path，而这个 Path是理论上最优计划的一部分，这样会导致最终的计划不是最优的，这种场景一般概率不大，如果遇到这种情况，可尝试使用Plan Hint进行调优； 5) 路径生成与集群规模大小、系统资源、统计信息、Cost 估算都有紧密关系，如集群DN数影响着重分布的倾斜性和单DN的数据量，系统内存影响下盘代价，统计信息是行数和distinct值估算的第一手数据，而Cost估算模型在整个计划生成中，是选择和淘汰的关键因素，每个JoinRel的行数估算不准，都有可能影响着最终计划。因此，相同的SQL语句，在不同集群或者同样的集群不同统计信息，计划都有可能不一样，如果路径发生一些变化可通过分析Performance信息和日志来定位问题，Performance 详解可以参考博文：GaussDB(DWS)的 explain performance 详解； 6) 如果设置了Random Plan模式，则动态规划的每一层cheapest_startup_path和cheapest_total_path 都是从 path_list 中随机选取的，这样保证随机性。

每一种路径又可以搭配不同的Join方 法（ NestLoop、HashJoin、MergeJoin），总计18种关联路径，优化器需要在这些路径中选择最优路径，筛选的依据就是路径的代价（Cost）。优化器会给每个算子赋予代价，比如 Seq Scan，Redistribute，HashJoin都有代价，代价与数据规模、数据特征、系统资源等等都有关系，关于代价如何估算，由于代价与执行时间成正比，优化器的目标是选择代价最小的计划，因此路径选择也是一样。路径代价的比较思路大致是这样，对于产生的一个新Path，逐个比较该新Path与path_list中的path，若 total_cost很相近，则比较startup cost，如果也差不多，则保留该 Path 到 path_list 中去；如果新路径的total_cost 比较大，但是startup_cost小很多，则保留该Path，此处略去具体的比较过程，直接给出Path的比较结果。t1 和t3表的关联条件是：t1.c1 = t3.c2，因为t1的Join列是分布键c1列，于是t1表上不需要加Redistribute；由 于 t1和t3的Join方式是Semi Join，外表不能Broadcast，否者可能会产生重复结果；另外还有一类Unique Path选择（即t3表去重）。由于只有一边需要重分布且可以进行重分布，则不选Broadcast，因为相同数据量时Broadcast 的代价一般要高于重分布，提前剪枝掉。再把Join方法考虑进去，于是优化器给出了最终选择。此时的最优计划是选择了内表Unique Path的路径，即t3表先去重，然后在走Inner Join 过程。 

已知表关联的方式有多种（比如 NestLoop、HashJoin）、且GaussDB（DWS）的表是分布式的存储在集群中，那么两个表的关联方式可能就有多种了，而我们的目标就是，从这些给定的基表出发，按要求经过一些操作（过滤条件、关联方式和条件、聚集等等），相互组合，层层递进，最后得到我们想要的结果。这就好比从基表出发，寻求一条最佳路径，使得我们能最快得到结果，这就是我们的目的。GaussDB(DWS)优化器选择的基本思路是动态规划，顾名思义，从某个开始状态，通过求解中间状态最优解，逐步往前演进，最后得到全局的最优计划。那么在动态规划中，总有一个变量，驱动着过程演进。在这里，这个变量就是表的个数。我们先记住这三组Path 名称：path_list，cheapest_startup_path ，cheapest_total_path，后面两个就对应了动态规划的局部最优解，在这里是一组集合，统称为最优路径，也是下一步的搜索空间。path_list里面存放了当前Rel集合上的有价值的一组候选 Path（被剪枝调的 Path 不会放在这里），cheapest_startup_path 代表path_list 中启动代价最小的那个Path，cheapest_total_path代表path_list里一组总代价最小的Path（这里用一组主要是可能存在多个维度分别对应的最优Path）。t2表和t3 表类似，最优路径都是一条Seq Scan。有了所有基表的Scan最优路径，下面就可以选择关联路径了。

表关联含有多个Join条件时，与基表过滤条件估算类似，也有两种思路，优先尝试多列统计信息进行选择率估算。当无法使用多列统计信息时，则使用单列统计信息按照上述方法分别计算出每个Join条件的选择率。那么组合选择率的方式也由参数cost_param控制。以下是特殊情况的选择率估算方式： 如果Join列是表达式，没有统计信息的话，则优化器会尝试估算出distinct值，然后按没有MCV的方式来进行估算； Left Join/Right Join 需特殊考虑以下一边补空另一边全输出的特点，以上模型进行适当的修改即可； 如果关联条件是范围类的比较，比如"t1.c2 < t2.c2"，则目前给默认选择率：1 / 3。两表关联时，如果基表上有一些无法下推的过滤条件，则一般会变成JoinFilter，即这些条件是在Join过程中进行过滤的，因此JoinFilter会影响到JoinRel的行数，但不会影响基表扫描上来的行数。严格来说，如果把 JoinRel 看成一个中间表的话，那么这些JoinFilter 是这个中间表的过滤条件，但JoinRel还没有产生，也没有行数和统计信息，因此无法准确估算。然而一种简单近似的方法是，仍然利用基表，粗略估算出这个JoinFilter的选择率，然后放到JoinRel最终行数估算中去。

基表行数估算完，就可以进入表关联阶段的处理了。那么要关联两个表，就需要一些信息，如基表行数、关联之后的行数、关联的方式选择（也叫Path的选择，请看下一节），然后在这些方式中选择代价最小的，也称之为最佳路径。对于关联条件的估算，也有单个条件和多个条件之分，优化器需要算出所有Join条件和JoinFilter的综合选择率，然后给出估算行数，先看单个关联条件的选择率如何估算。t1.c2 列没有 MCV 值，平均每个 distinct 值大约重复 4 次且是均匀分布，由于Histogram 中保留的数据只是桶的边界，并不是实际有哪些数据（重复收集统计信息，这些边界可能会有变化），那么实际拿边界值来与t2.c2进行比较不太实际，可能会产生比较大的误差。此时我们坚信一点：“能关联的列与列是有相同含义的，且数据是尽可能有重叠的”，也就是说，如果t1.c2列有500个distinct值，t2.c2列有100个distinct值，那么这100个与500个会重叠100个，即distinct值小的会全部在distinct值大的那个表中出现。虽然这样的假设有些苛刻，但很多时候与实际情况是较吻合的。回到本例，根据统计信息，n_distinct 显示负值代表占比，而t1表的估算行数是2000因为基表t1上还有个过滤条件"t1.c1 > 100"，当前关联是发生在基表过滤条件之后的，估算的distinct 应该是过滤条件之后的 distinct 有多少，不应是原始表上有多少。那么此时可以采用各种假设模型来进行估算，比如几个简单模型：Poisson 模型（假设 t1.c1 与t1.c2 相关性很弱）或完全相关模型（假设t1.c1与t1.c2 完全相关），不同模型得到的值会有差异。

仅有单列统计信息 该情况下，首先按单列统计信息计算每个过滤条件的选择率，然后选择一种方式来组合这些选择率，选择的方式可通过设置cost_param来指定。为何需要选择组合方式呢？因为实际模型中，列与列之间是有一定相关性的，有的场景中相关性比较强，有的场景则比较弱，相关性的强弱决定了最后的行数。 有多列组合统计信息 如果过滤的组合列的组合统计信息已经收集，则优化器会优先使用组合统计信息来估算行数，估算的基本思想与单列一致，即将多列组合形式上看成“单列”，然后再拿多列的统计信息来估算。 比如，多列统计信息有：((c1, c2, c4))，((c1, c2))，双括号表示一组多列统计信息：若条件是：c1 = 7 and c2 = 3 and c4 = 5，则使用((c1, c2, c4))； 若条件是：c1 = 7 and c2 = 3，则使用((c1, c2))； 若条件是：c1 = 7 and c2 = 3 and c5 = 6，则使用((c1, c2))； 多列条件匹配多列统计信息的总体原则是：多列统计信息的列组合需要被过滤条件的列组合包含； 所有满足“条件1”的多列统计信息中，选取“与过滤条件的列组合的交集最大“的那个多列统计信息。 对于无法匹配多列统计信息列的过滤条件，则使用单列统计信息进行估算。目前使用多列统计信息时，不支持范围类条件；如果有多组多列条件，则每组多列条件的选择率相乘作为整体的选择率； 上面说的单列条件估算和多列条件估算，适用范围是每个过滤条件中仅有表的一列，如果一个过滤条件是多列的组合，比如 “t1.c1 < t1.c2”，那么一般而言单列统计信息是无法估算的，因为单列统计信息是相互独立的，无法确定两个独立的统计数据是否来自一行。目前多列统计信息机制也不支持基表上的过滤条件涉及多列的场景； 无法下推到基表的过滤条件，则不纳入基表行数估算的考虑范畴，如上述：t1.c3 is not null or t2.c3 is not null，该条件一般称为JoinFilter，会在创建JoinRel时进行估算； 如果没有统计信息可用，那就给默认选择率了。 

GaussDB(DWS)优化器的计划生成方法有两种，一是动态规划，二是遗传算法，前者是使用最多的方法，也是本系列文章重点介绍对象。一般来说，一条 SQL 语句经语法树（ParseTree）生成特定结构的查询树（QueryTree）后，从QueryTree开始，才进入计划生成的核心部分，其中有一些关键步骤： 1) 设置初始并行度（Dop）； 2) 查询重写； 3) 估算基表行数； 4) 估算关联表（JoinRel）； 5) 路径生成，生成最优Path； 6) 由最优Path创建用于执行的Plan节点； 7) 调整最优并行度。基表行数估算目前主要依赖于统计信息，统计信息是先于计划生成由Analyze触发收集的关于表的样本数据的一些统计平均信息，如t1表的部分统计信息如下： null_frac：空值比例 n_distinct：全局 distinct 值，取值规则：正数时代表distinct值，负数时其绝对值代表distinct 值与行数的比 n_dndistinct：DN1上的distinct值，取值规则与n_distinct类似 avg_width：该字段的平均宽度 GaussDB(DWS)技术原理-优化器 most_common_vals：高频值列表 most_common_freqs：高频值的占比列表，与most_common_vals对应 从上面的统计信息可大致判断出具体的数据分布，如t1.c1列，平均宽度是4，每个数据的平均重复度是 2，且没有空值，也没有哪个值占比明显高于其他值，即most_common_vals（简称MCV）为空，这个也可以理解为数据基本分布均匀，对于这些分布均匀的数据，则分配一定量的桶，按等高方式划分了这些数据，并记录了每个桶的边界，俗称直方图（Histogram），即每个桶中有等量的数据。 

HDC大会即将举办，大家对大会有哪些期待？

Dify开源平台介绍cid:link_2AI应用开发解决方案cid:link_0云原生时代成本治理cid:link_3云原生时代的应用挑战和趋势cid:link_4数据建模介绍cid:link_5数据模型三要素cid:link_6层次模型介绍cid:link_7层次模型的优缺点cid:link_8网状模型介绍cid:link_9关系模型的数据操纵与完整性约束cid:link_10数据库系统的三级模式结构cid:link_11数据库两级映像cid:link_12数据库系统的三级模式结构小结cid:link_13数据库体系结构cid:link_1关系操作https://bbs.huaweicloud.com/forum/thread-0275181210563924023-1-1.html

关系模型中常用的关系操作包括查询(query)操作和更新操作两大部分，而更新操作又可分为插入(insert)、删除(delete)、修改(update)等操作。关系的查询表达能力很强，因此查询操作是关系操作中最主要的部分。查询操作又可进一步分为选择(select)、投影(project)、连接(join)、除(divide)、并(union)、差(difference)、交(intersection)、笛卡儿积等操作。其中选择、投影、并、差、笛卡儿积是5种基本操作，其他操作可以用基本操作来定义和导出，就像乘法可以用加法来定义和导出一样。关系操作的特点是集合操作方式，即操作的对象和结果都是集合。这种操作方式也称为成组数据处理(set-at-a-time processing)，即一次一个集合的操作方式。相应地，层次模型和网状模型的数据操作方式则为一次一个记录(record-at-a-time)的方式。这里强调一下，关系操作的所有输入和输出均是关系，包括关系操作的中间结果也是关系。关系数据语言的分类早期的关系操作能力通常用代数方式或逻辑方式来表示，分别称为关系代数(relationalalgebra)和关系演算(relational calculus)。关系代数用对关系的运算来表达査询要求，关系演算则用谓词来表达查询要求。关系演算又可按谓词变元的基本对象是元组变量还是域变量分为元组关系演算和域关系演算。一个关系数据语言能够表示关系代数可以表示的查询，称为具有完备的表达能力，简称关系完备性。已经证明关系代数、元组关系演算和域关系演算三种关系数据语言在表达能力上是等价的，都具有完备的表达能力。

根据计算机的系统结构，从数据库最终用户角度来看，数据库系统可分为集中式数据库系统、客户-服务器(浏览器/应用服务器/数据库服务器)数据库系统、并行数据库系统、分布式数据库系统和云计算环境下的数据库系统(云数据库系统)等。这是数据库系统外部的体系结构。1.集中式数据库系统集中式数据库系统的数据库管理系统、数据库和应用程序都在一台计算机上。在小型机和大型机上的集中式数据库系统一般是多用户系统，即多个用户通过各自的终端运行不同的应用系统，共享数据库。微型计算机上的数据库系统一般是单用户的。2.客户-服务器数据库系统在客户-服务器数据库系统中，数据库管理系统、数据库驻留在服务器上，而应用程序放置在客户机上(微型计算机或工作站)，客户机和服务器通过网络进行通信。在这种结构中客户机负责提供业务数据处理流程和应用程序界面，当要存取数据库中的数据时就向服务器发出请求，服务器接收客户机的请求后进行处理，并将客户要求的数据返回给客户机。随着互联网技术的应用，客户-服务器两层结构已经发展为三层或多层结构。三层结构一般是指浏览器/应用服务器/数据库服务器结构。用户界面采用统一的浏览器方式，应用服务器上安装应用系统或应用模块，数据库服务器上安装数据库管理系统和数据库。两层或三层结构对数据库管理系统的功能进行了合理的分配，减轻了数据库服务器的负担，从而使服务器有更多的能力完成事务处理和数据访问控制，支持更多的用户，提高系统的性能。3.并行数据库系统并行数据库系统是在并行计算机上运行的具有并行处理能力的数据库系统，是数据库技术与并行计算技术相结合的产物。并行计算机系统有共享内存型、共享磁盘型、非共享型以及混合型等。并行计算技术利用多处理机并行处理产生的规模效益来提高系统的整体性能。并行数据库系统发挥了多处理机的优势，采用并行查询处理技术和并行数据分布与管理技术，具有高性能、高可用性、高扩展性等优点。

数据库系统的三级模式结构小结在数据库的三级模式结构，其中，模式(即全局逻辑结构)是数据库的核心与关键，它独立于数据库的其他层次。因此设计数据库模式结构时应首先确定数据库的逻辑模式。内模式依赖于数据库的全局逻辑结构，但独立于数据库的用户视图(即外模式)，也独立于具体的存储设备。它将全局逻辑结构中所定义的数据结构及其联系按照一定的物理存储策略进行组织，以达到较好的时间与空间效率。外模式面向具体的应用程序，它定义在逻辑模式之上，但独立于存储模式和存储设备。当应用需求发生较大变化，相应的外模式不能满足其视图要求时，该外模式就得做相应改动。所以设计外模式时应充分考虑到应用的扩充性。特定的应用程序是在外模式描述的数据结构上编制的，它依赖于特定的外模式，与数据库的模式和存储结构独立。不同的应用程序有时可以共用同一个外模式。数据库的两级映像保证了数据库外模式的稳定性，从而从底层保证了应用程序的稳定性，除非应用需求本身发生变化，否则应用程序一般不需修改。数据与程序之间的独立性，使得数据的定义和描述可以从应用程序中分离出去。另外，数据的组织和存取交由数据库管理系统负责，简化了应用程序的编制，大大减少了应用程序的开发和维护成本。

外模式/模式映像前已提及，模式描述的是数据的全局逻辑结构，外模式描述的是数据的局部逻辑结构。对于同一个模式，可以有任意多个外模式。对于每一个外模式，数据库系统都有一个外模式/模式映像来定义该外模式与模式之间的对应关系。这些映像定义通常包含在各自外模式的描述中。当模式改变时(如增加新的关系、新的属性，改变属性的数据类型等)，由数据库管理员对各个外模式/模式的映像做相应改变，可以使外模式保持不变。应用程序是依据数据的外模式编写的，因而应用程序不必修改，保证了数据与程序的逻辑独立性，简称数据的逻辑独立性。模式/内模式映像数据库只有一个模式，也只有一个内模式，所以模式/内模式映像是唯一的，它定义了数据全局逻辑结构与存储结构之间的对应关系。例如，说明逻辑记录和字段在内部是如何表示的。该映像定义通常包含在模式描述中。当数据库的存储结构改变时(如选用了另一种存储结构)，由数据库管理员对模式/内模式映像做相应改变，可以使模式保持不变，因而应用程序也不必改变，保证了数据与程序的物理独立性，简称数据的物理独立性。数据库系统的三级模式结构小结在数据库的三级模式结构，其中，模式(即全局逻辑结构)是数据库的核心与关键，它独立于数据库的其他层次。因此设计数据库模式结构时应首先确定数据库的逻辑模式。内模式依赖于数据库的全局逻辑结构，但独立于数据库的用户视图(即外模式)，也独立于具体的存储设备。它将全局逻辑结构中所定义的数据结构及其联系按照一定的物理存储策略进行组织，以达到较好的时间与空间效率。