统计信息是历史数据，表的元组数在随时变化。例如：Analyze数据采样时有10个页面，存在50条元组；实际执行时有20个页面，可能存在多少条元组？用你最朴素的情感想一想是不是，很可能是100条元组对不对？ 表大小的估算方法在函数estimate_rel_size -> table_relation_estimate_size -> heapam_estimate_rel_size 中。 1) 先通过表物理文件的大小计算实际页面数 actual_pages = file_size / BLOCKSIZE； 2) 计算页面的元组密度 a) 如果relpages大于0，density = reltuples / (double) relpages； b) 如果relpages为空，density = (BLCKSZ - SizeOfPageHeaderData) / tuple_width, 页面大小 / 元组宽度。 3) 估算表元组个数 = 页面元组密度 * 实际页面数 = density * actual_pages 所以，估算rows的10000 = (10000 / 358) * 358，历史页面密度 * 新的页面数，以推算当前元组数。查询引擎在查询语法树的WHERE子句中识别出比较条件，再到pg_operator中根据操作符和数据类型找到oprrest为scalarltsel，这是通用的标量数据类型的小于操作符的代价估算函数。最终是在 scalarineqsel -> ineq_histogram_selectivity 中进行直方图代价估算。 在PG中采用的是等高直方图，也叫等频直方图。将样本范围划分成N等份的若干个子区间，取所有子区间的边界值，构成直方图。 使用：使用时认为子区间（也叫桶）内的值是线性单调分布的，也认为直方图的覆盖范围就是整个数据列的范围。因此，只需计算出在直方图中的占比，既是总体中的占比。

生命周期：词法分析(Lex) -> 语法分析(YACC) -> 分析重写 -> 查询优化（逻辑优化和物理优化） -> 查询计划生成 -> 查询执行。词法分析：描述词法分析器的*.l文件经Lex 工具编译生成lex.yy.c, 再由 C编译器生成可执行的词法分析器。基本功能就是将一堆字符串根据设定的保留关键字和非保留关键字，转化成相应的标识符。SQL生命周期：词法分析(Lex) -> 语法分析(YACC) -> 分析重写 -> 查询优化（逻辑优化和物理优化） -> 查询计划生成 -> 查询执行。 词法分析：描述词法分析器的*.l文件经Lex工具编译生成lex.yy.c, 再由C编译器生成可执行的词法分析器。基本功能就是将一堆字符串根据设定的保留关键字和非保留关键字，转化成相应的标识符(Tokens)； 语法分析：语法规则描述文件*.y经YACC工具编译生成gram.c，再由C编译器生成可执行的语法分析器。基本功能就是将一堆标识符(Tokens)根据设定的语法规则，转化成原始语法树； 分析重写：查询分析将原始语法树转换为查询语法树（各种transform）； 查 询 重写根据pg_rewrite中的规则改写表和视图，最终得到查询语法树； 查询优化：经过逻辑优化和物理优化（生成最优路径）； 查询计划生成：将最优的查询路径转化为查询计划； 查询执行：通过执行器去执行查询计划生成查询的结果集。 在物理优化阶段，同样的一条SQL语句可以产生很多种查询路径，例如：多表JOIN操作，不同的JOIN顺序产生不同的执行路径，也导致中间结果元组规模的不同。查询引擎会在所有可行的查询访问路径中选择执行代价最低的一条。 通常我们依据 COST = COST(CPU) + COST(IO) 这一公式来选择最优执行计划。这里最主要的问题是如何确定满足某个条件的元组数量，基本方法就是依据统计信息和一定的统计模型。某条件的查询代价 = tuple_num * per_tuple_cost。

通过开启use_workload_manager 和 enable_dynamic_workload 两个参数开启GaussDB(DWS)的内存自适应控制机制。 使用内存自适应机制时，打印SQL语句的explain performance执行计划运行信息时，会包含以下额外的信息辅助定位问题： 1) 在最下方的 Query Summary 一栏中，会显示出 System available mem、Query max mem和Query estimated mem，分别表示：系统当前可用内存、语句可用最大内存（系统可用最大内存），语句估算内存使用量，均为单DN的衡量值。表示当前语句的语句最大可用内存和系统当前可用内存均为 22G，语句估算内存使用为1.6G；2) 在Memory Information一栏，会显示CN和每个DN的内存使用峰值，语句实际内存使用，单DN使用16GB，CN使用76MB；3) 在Memory Information一栏下方每个算子对应的位置，会显示每个算子单DN的内存峰值，同时会显示每个DN上内存使用的自动扩展和提前下盘情况，可以看出第15号HashJoin算子，每个SMP线程的内存使用均为3.8GB，估算内存是860MB，经历了五次内存自动扩展，在第五次扩展后，系统内存告急，算子未用到第五次扩展后的峰值即提前下盘；4) 在explain performance最顶层的表格中，汇总了每个算子的估算内存和实际使用内存的情况，见下图的E-memory和Peak Memory两列所示。与上面信息对应，第15号算子单SMP线程的peak memory，最大值为3766MB，最小值为3753MB，估算内存值（单DN4个SMP线程）为860MB。

1) 对于每个 SQL，生成计划前首先从资源管理模块获取系统当前的最大可用内存（Query Max Mem）和当前可用内存（System Available Mem）。最大可用内存通常为每个DN的最大可用内存去除系统预分配内存，例如：数据缓存等，表示语句可用的最大内存，如果语句使用内存超过该值，必须下盘。当前可用内存用于表示当前系统的繁忙程度，如果当前可用内存比较小，倾向于选择耗费内存少的计划； 2) 依据当前可用内存生成计划，同时根据SQL引擎优化器计划生成过程中的cost估算值估算每个物化算子的内存使用量，以及流水线场景下整个查询使用的内存总量估算值。如果该值大于当前可用内存，则尝试将整个查询的内存使用量调到当前可用内存以下，此时会造成部分算子下盘； 3) 将语句及估算的语句内存发送到CCN，如果当前可用内存小于语句估算内存，则估算语句的内存进一步减少是否对查询性能造成较大的影响，如果根据cost评估影响不大，则进一步减少算子的内存使用，使语句内存使用满足当前可用内存，将语句下发执行，否则则进入排队状态； 4) 由于每个算子的内存使用量是基于 cost 评估获得，可能存在一定的误差。因此，在SQL语句执行时，支持内存的动态调整，包括：执行算子内存的自动扩展和提前下盘。当算子达到估算的内存值上限，但系统还有宽裕的内存时，会进行算子内存的扩展，继续保持不下盘的状态。当系统已用内存达到80%或更高时，如果算子已有最小内存保证，则会触发提前下盘逻辑，保证不会由于内存不足而报错。 

针对静态内存管理机制的弊端，GaussDB(DWS)设计实现了内存自适应控制技术，主要目的如下： GaussDB(DWS)技术原理-优化器 1) 去除静态内存管理对work_mem的依赖。可以由SQL引擎优化器模块自动估算每个算子所需的内存； 2) 避免大并发场景下内存不足现象的发生。资源管理模块根据SQL引擎优化器对于每个查询内存的估算值，对每个查询进行调度，如果超过系统可用内存，则进行排队。 动态资源管理与内存自适应技术的组件图如上图所示。我们从多个CN中选择一个CN，命名为 CCN（Central CN），进行语句队列的管理。对于每个查询SQL，CN在生成完执行计划后，为每个物化算子分配合适的内存，同时计算整个语句内存使用量，并将语句及对应的内存使用量发给CCN。CCN维护系统可用的内存值，对于新来的语句，如果语句内存使用量小于可用内存值，则允许其下发到DN执行，否则挂起，等到有语句结束释放内存后再次将其唤醒，是否可以下发。

GaussDB(DWS)也提供下盘的机制，当上述操作符需要使用的内存太大时，可以将部分或全部的数据下盘处理，提高内存的使用效率，但相应的查询性能也会受到影响。PG 使用 work_mem 参数来控制算子可使用内存的阈值，当使用内存超过阈值时，就需要做下盘处理。GaussDB(DWS)的静态内存管理机制也延续了 PG 的处理机制，使用work_mem来控制单算子的内存使用上限。 静态内存管理存在较大弊端，需要调优人员能够根据数据量、语句复杂程度和系统的内存大小设置合理的work_mem，既避免 work_mem设置太大导致系统资源不够用，还要考虑到数据规模，保证大部分算子不下盘。通常情况下，这个是很难做到的，有以下几点原因： 1) 通常情况下，复杂语句的执行计划中包含多个复杂算子，每个算子的内存使用上限是work_mem，我们没有办法计算一个语句要使用多少内存，因此也就不容易设置一个最优的work_mem参数，保证尽可能不下盘，同时内存又够用。并发场景更无法设置了； 2) work_mem只是每个算子内存使用的上限，并不是预分配；如果数据量没有那么大的话，实际内存使用是达不到work_mem的。因此也会影响work_mem的设置； 3) 每个语句的场景不一样，有的语句包含多个物化算子，而另外的语句只有一个物化算子，而这个算子对内存的需求会比较大，因此无法全局统一地进行设置。 

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），即每个桶中有等量的数据。