写点什么

谋而后动:解读数仓计划生成中行数估算和路径生成的奥秘

发布于: 2021 年 05 月 27 日

​​​​​​​​​​​​​​​​摘要:孙子兵法云:“谋定而后动,知止而有得”,做任何事一定要进行谋划部署,做好准备,这样才能利于这件事的成功,切不可莽撞而行。同样,GaussDB(DWS)执行查询语句也会按照预定的计划来执行,给定硬件环境的情况下,执行的快慢全凭计划的好坏,那么一条查询语句的计划是如何制定的呢,本文将为大家解读计划生成中行数估算和路径生成的奥秘。


本文分享自华为云社区《GaussDB(DWS)计划生成原理揭秘(一)》,原文作者:Jugg 。

 

GaussDB(DWS)优化器的计划生成方法有两种,一是动态规划,二是遗传算法,前者是使用最多的方法,也是本系列文章重点介绍对象。一般来说,一条 SQL 语句经语法树(ParseTree)生成特定结构的查询树(QueryTree)后,从 QueryTree 开始,才进入计划生成的核心部分,其中有一些关键步骤:


1.   设置初始并行度(Dop)

2.   查询重写

3.   估算基表行数

4.   估算关联表(JoinRel)

5.   路径生成,生成最优 Path

6.   由最优 Path 创建用于执行的 Plan 节点

7.   调整最优并行度


本文主要关注 3、4、5,这些步骤对一个计划生成影响比较大,其中主要涉及行数估算、路径选择方法和代价估算(或称 Cost 估算),Cost 估算是路径选择的依据,每个算子对应一套模型,属于较为独立的部分,后续文章再讲解。Plan Hint 会在 3、4、5 等诸多步骤中穿插干扰计划生成,其详细的介绍读者可参阅博文:GaussDB(DWS)性能调优系列实现篇六:十八般武艺Plan hint运用


先看一个简单的查询语句:


select count(*) from t1 join t2 on t1.c2 = t2.c2 and t1.c1 > 100 and (t1.c3 is not null or t2.c3 is not null);
复制代码


​GaussDB(DWS)优化器给出的执行计划如下:


postgres=# explain verbose select count(*) from t1 join t2 on t1.c2 = t2.c2 and t1.c1 > 100 and (t1.c3 is not null or t2.c3 is not null);                                                  QUERY PLAN                                                  --------------------------------------------------------------------------------------------------------------  id |                    operation                     | E-rows | E-distinct | E-memory | E-width | E-costs  ----+--------------------------------------------------+--------+------------+----------+---------+---------   1 | ->  Aggregate                                    |      1 |            |          |       8 | 111.23     2 |    ->  Streaming (type: GATHER)                  |      4 |            |          |       8 | 111.23     3 |       ->  Aggregate                              |      4 |            | 1MB      |       8 | 101.23     4 |          ->  Hash Join (5,7)                     |   3838 |            | 1MB      |       0 | 98.82      5 |             ->  Streaming(type: REDISTRIBUTE)    |   1799 | 112        | 2MB      |      10 | 46.38      6 |                ->  Seq Scan on test.t1           |   1799 |            | 1MB      |      10 | 9.25       7 |             ->  Hash                             |   1001 | 25         | 16MB     |       8 | 32.95      8 |                ->  Streaming(type: REDISTRIBUTE) |   1001 |            | 2MB      |       8 | 32.95      9 |                   ->  Seq Scan on test.t2        |   1001 |            | 1MB      |       8 | 4.50                Predicate Information (identified by plan id)           -----------------------------------------------------------------   4 --Hash Join (5,7)         Hash Cond: (t1.c2 = t2.c2)         Join Filter: ((t1.c3 IS NOT NULL) OR (t2.c3 IS NOT NULL))   6 --Seq Scan on test.t1         Filter: (t1.c1 > 100)
复制代码


​通常一条查询语句的 Plan 都是从基表开始,本例中基表 t1 有多个过滤条件,从计划上看,部分条件下推到基表上了,部分条件没有下推,那么它的行数如何估出来的呢?我们首先从基表的行数估算开始。

一、基表行数估算

       

如果基表上没有过滤条件或者过滤条件无法下推到基表上,那么基表的行数估算就是统计信息中显示的行数,不需要特殊处理。本节考虑下推到基表上的过滤条件,分单列和多列两种情况。


1、单列过滤条件估算思想


基表行数估算目前主要依赖于统计信息,统计信息是先于计划生成由 Analyze 触发收集的关于表的样本数据的一些统计平均信息,如 t1 表的部分统计信息如下:


postgres=# select tablename, attname, null_frac, n_distinct, n_dndistinct, avg_width, most_common_vals, most_common_freqs from pg_stats where tablename = 't1'; tablename | attname | null_frac | n_distinct | n_dndistinct | avg_width | most_common_vals | most_common_freqs -----------+---------+-----------+------------+--------------+-----------+------------------+------------------- t1        | c1      |         0 |        -.5 |          -.5 |         4 |                  |  t1        | c2      |         0 |       -.25 |     -.431535 |         4 |                  |  t1        | c3      |        .5 |          1 |            1 |         6 | {gauss}          | {.5} t1        | c4      |        .5 |          1 |            1 |         8 | {gaussdb}        | {.5}(4 rows)
复制代码


​各字段含义如下:


  • null_frac:空值比例

  • n_distinct:全局 distinct 值,取值规则:正数时代表 distinct 值,负数时其绝对值代表 distinct 值与行数的比

  • n_dndistinct:DN1 上的 distinct 值,取值规则与 n_distinct 类似

  • avg_width:该字段的平均宽度

  • most_common_vals:高频值列表

  • most_common_freqs:高频值的占比列表,与 most_common_vals 对应


从上面的统计信息可大致判断出具体的数据分布,如 t1.c1 列,平均宽度是 4,每个数据的平均重复度是 2,且没有空值,也没有哪个值占比明显高于其他值,即 most_common_vals(简称 MCV)为空,这个也可以理解为数据基本分布均匀,对于这些分布均匀的数据,则分配一定量的桶,按等高方式划分了这些数据,并记录了每个桶的边界,俗称直方图(Histogram),即每个桶中有等量的数据。

有了这些基本信息后,基表的行数大致就可以估算了。如 t1 表上的过滤条件"t1.c1>100",结合 t1.c1 列的均匀分布特性和数据分布的具体情况:


postgres=# select histogram_bounds from pg_stats where tablename = 't1' and attname = 'c1';                                                                                                                                                                                              histogram_bounds                                                                                                                                                                                               ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- {1,10,20,30,40,50,60,70,80,90,100,110,120,130,140,150,160,170,180,190,200,210,220,230,240,250,260,270,280,290,300,310,320,330,340,350,360,370,380,390,400,410,420,430,440,450,460,470,480,490,500,510,520,530,540,550,560,570,580,590,600,610,620,630,640,650,660,670,680,690,700,710,720,730,740,750,760,770,780,790,800,810,820,830,840,850,860,870,880,890,900,910,920,930,940,950,960,970,980,990,1000}(1 row)
复制代码


​可知,t1.c1 列的数据分布在 1~1000 之间,而每两个边界中含有的数据量是大致相同的(这里是根据样本统计的统计边界),先找到 100 在这个直方图中的大概位置,在这里它是某个桶的边界(有时在桶的内部),那么 t1.c1>100 的数据占比大约就是边界 100 之后的那些桶的数量的占比,这里的占比也称为选择率,即经过这个条件后,被选中的数据占比多少,因此由“t1.c >100“过滤之后的行数就可以估算出来了。


以上就是估算基表行数的基本思想。一般地


有统计信息:


1.   等值条件 1)对比 MCV,如果满足过滤条件,则选择率(即 most_common_freqs)累加;2)对 Histogram 数据,按 distinct 值个数粗略估算选择率;


2.   范围条件 1)对比 MCV 数据,如果满足过滤条件,则选择率累加;2)对 Histogram 数据,按边界位置估算选择率;


3.   不等值条件:可转化为等值条件估算


无统计信息:


1.   等值条件:比如过滤条件是:“substr(c3, 1, 5) = 'gauss'”,c3 列有统计信息,但 substr(c3, 1, 5)没有统计信息。那如何估算这个条件选择率呢?一个简单的思路是,如果 substr(c3, 1, 5) 的 distinct 值已知的话,则可粗略假设每个 distinct 值的重复度一致,于是选择率也可以估算出来;在 GaussDB(DWS)中,可通过设置 cost_model_version=1 开启表达式 distinct 值估算功能;


2.   范围条件:此时仅仅知道 substr(c3, 1, 5)的 distinct 值是无法预估选择率的,对于无法估算的表达式,可通过 qual_num_distinct 进行设置指定相应 distinct 值;


3.   不等值条件:可转化为等值条件估算


2. 多列过滤条件估算思想


比如 t1 表有两个过滤条件:t1.c1 = 100 andt1.c3 = 'gauss',那么如何估算该两列的综合选择率?在 GaussDB(DWS)中,一般性方法有两个:


仅有单列统计信息


该情况下,首先按单列统计信息计算每个过滤条件的选择率,然后选择一种方式来组合这些选择率,选择的方式可通过设置 cost_param 来指定。为何需要选择组合方式呢?因为实际模型中,列与列之间是有一定相关性的,有的场景中相关性比较强,有的场景则比较弱,相关性的强弱决定了最后的行数。

该参数的意义和使用介绍可参考:GaussDB(DWS)性能调优系列实战篇五:十八般武艺之路径干预。


有多列组合统计信息


如果过滤的组合列的组合统计信息已经收集,则优化器会优先使用组合统计信息来估算行数,估算的基本思想与单列一致,即将多列组合形式上看成“单列”,然后再拿多列的统计信息来估算。


比如,多列统计信息有:((c1, c2, c4)),((c1, c2)),双括号表示一组多列统计信息:


1.   若条件是:c1 = 7 and c2 = 3 and c4 = 5,则使用((c1, c2, c4))

2.   若条件是:c1 = 7 and c2 = 3,则使用((c1, c2))

3.   若条件是:c1 = 7 and c2 = 3 and c5 = 6,则使用((c1, c2))


多列条件匹配多列统计信息的总体原则是:


1.   多列统计信息的列组合需要被过滤条件的列组合包含;

2.   所有满足“条件 1”的多列统计信息中,选取“与过滤条件的列组合的交集最大“的那个多列统计信息。


对于无法匹配多列统计信息列的过滤条件,则使用单列统计信息进行估算。


3. 值得注意的地方


  • 目前使用多列统计信息时,不支持范围类条件;如果有多组多列条件,则每组多列条件的选择率相乘作为整体的选择率。


  • 上面说的单列条件估算和多列条件估算,适用范围是每个过滤条件中仅有表的一列,如果一个过滤条件是多列的组合,比如 “t1.c1 < t1.c2”,那么一般而言单列统计信息是无法估算的,因为单列统计信息是相互独立的,无法确定两个独立的统计数据是否来自一行。目前多列统计信息机制也不支持基表上的过滤条件涉及多列的场景。


  • 无法下推到基表的过滤条件,则不纳入基表行数估算的考虑范畴,如上述:t1.c3 is not null or t2.c3 is not null,该条件一般称为 JoinFilter,会在创建 JoinRel 时进行估算。


  • 如果没有统计信息可用,那就给默认选择率了。

二、JoinRel 行数估算

        

基表行数估算完,就可以进入表关联阶段的处理了。那么要关联两个表,就需要一些信息,如基表行数、关联之后的行数、关联的方式选择(也叫 Path 的选择,请看下一节),然后在这些方式中选择代价最小的,也称之为最佳路径。对于关联条件的估算,也有单个条件和多个条件之分,优化器需要算出所有 Join 条件和 JoinFilter 的综合选择率,然后给出估算行数,先看单个关联条件的选择率如何估算。


1. 一组 Join 条件估算思想

       

与基表过滤条件估算行数类似,也是利用统计信息来估算。比如上述 SQL 示例中的关联条件:t1.c2 = t2.c2,先看 t1.c2 的统计信息:


postgres=# select tablename, attname, null_frac, n_distinct, n_dndistinct, avg_width, most_common_vals, most_common_freqsfrom pg_stats where tablename = 't1' and attname = 'c2'; tablename | attname | null_frac | n_distinct | n_dndistinct | avg_width | most_common_vals | most_common_freqs -----------+---------+-----------+------------+--------------+-----------+------------------+------------------- t1        | c2      |         0 |       -.25 |     -.431535 |         4 |                  | (1 row)
复制代码


​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:


postgres=# select reltuples from pg_class where relname = 't1'; reltuples -----------      2000(1 row)
复制代码


​于是,t1.c2 的 distinct 是 0.25 * 2000 =500,类似地,根据统计信息,t2.c2 的 distinct 是 100:


postgres=# select tablename, attname, null_frac, n_distinct, n_dndistinct from pg_stats where tablename = 't2' and attname = 'c2'; tablename | attname | null_frac | n_distinct | n_dndistinct -----------+---------+-----------+------------+-------------- t2        | c2      |         0 |        100 |      -.39834(1 row)
复制代码


那么,t1.c2 的 distinct 值是否可以直接用 500 呢?答案是不能。因为基表 t1 上还有个过滤条件"t1.c1 >100",当前关联是发生在基表过滤条件之后的,估算的 distinct 应该是过滤条件之后的 distinct 有多少,不应是原始表上有多少。那么此时可以采用各种假设模型来进行估算,比如几个简单模型:Poisson 模型(假设 t1.c1 与 t1.c2 相关性很弱)或完全相关模型(假设 t1.c1 与 t1.c2 完全相关),不同模型得到的值会有差异,在本例中,"t1.c1 > 100"的选择率是 8.995000e-01,则用不同模型得到的 distinct 值会有差异,如下:


a.   Poisson 模型(相关性弱模型):500 * (1.0 -exp(-2000 * 8.995000e-01 / 500)) = 486

b.   完全相关模型:500 * 8.995000e-01 = 450

c.   完全不相关模型:500 * (1.0 - pow(1.0 - 8.995000e-01, 2000 / 500)) = 499.9,该模型可由概率方法得到,感兴趣读者可自行尝试推导

d.   实际过滤后的 distinct:500,即 c2 与 c1 列是不相关的


postgres=# select count(distinct c2) from t1 where c1 > 100; count -------   500(1 row)
复制代码


​估算过滤后 t1.c2 的 distinct 值,那么"t1.c2 =t2.c2"的选择率就可以估算出来了: 1 / distinct。

以上是任一表没有 MCV 的情况,如果 t1.c2 和 t2.c2 都有 MCV,那么就先比较它们的 MCV,因为 MCV 中的值都是有明确占比的,直接累计匹配结果即可,然后再对 Histogram 中的值进行匹配。


2. 多组 Join 条件估算思想

        

表关联含有多个 Join 条件时,与基表过滤条件估算类似,也有两种思路,优先尝试多列统计信息进行选择率估算。当无法使用多列统计信息时,则使用单列统计信息按照上述方法分别计算出每个 Join 条件的选择率。那么组合选择率的方式也由参数 cost_param 控制,详细参考GaussDB(DWS)性能调优系列实战篇五:十八般武艺之路径干预。


另外,以下是特殊情况的选择率估算方式:


  • 如果 Join 列是表达式,没有统计信息的话,则优化器会尝试估算出 distinct 值,然后按没有 MCV 的方式来进行估算;


  • Left Join/RightJoin 需特殊考虑以下一边补空另一边全输出的特点,以上模型进行适当的修改即可;


  • 如果关联条件是范围类的比较,比如"t1.c2 < t2.c2",则目前给默认选择率:1 / 3;


3. JoinFilter 的估算思想

       

两表关联时,如果基表上有一些无法下推的过滤条件,则一般会变成 JoinFilter,即这些条件是在 Join 过程中进行过滤的,因此 JoinFilter 会影响到 JoinRel 的行数,但不会影响基表扫描上来的行数。严格来说,如果把 JoinRel 看成一个中间表的话,那么这些 JoinFilter 是这个中间表的过滤条件,但 JoinRel 还没有产生,也没有行数和统计信息,因此无法准确估算。然而一种简单近似的方法是,仍然利用基表,粗略估算出这个 JoinFilter 的选择率,然后放到 JoinRel 最终行数估算中去。

三、路径生成

       

有了前面两节的行数估算的铺垫,就可以进入路径生成的流程了。何为路径生成?已知表关联的方式有多种(比如 NestLoop、HashJoin)、且 GaussDB(DWS)的表是分布式的存储在集群中,那么两个表的关联方式可能就有多种了,而我们的目标就是,从这些给定的基表出发,按要求经过一些操作(过滤条件、关联方式和条件、聚集等等),相互组合,层层递进,最后得到我们想要的结果。这就好比从基表出发,寻求一条最佳路径,使得我们能最快得到结果,这就是我们的目的。本节我们介绍 Join Path 和 Aggregate Path 的生成。


1. Join Path 的生成

       

GaussDB(DWS)优化器选择的基本思路是动态规划,顾名思义,从某个开始状态,通过求解中间状态最优解,逐步往前演进,最后得到全局的最优计划。那么在动态规划中,总有一个变量,驱动着过程演进。在这里,这个变量就是表的个数。本节,我们以如下 SQL 为例进行讲解:


select count(*) from t1, t2 where t1.c2 = t2.c2 and t1.c1 < 800 and exists (select c1 from t3 where t1.c1 = t3.c2 and t3.c1 > 100);
复制代码


​该 SQL 语句中,有三个基表 t1, t2, t3,三个表的分布键都是 c1 列,共有两个关联条件:


1.   t1.c2 = t2.c2, t1 与 t2 关联

2.   t1.c1 = t3.c2, t1 与 t3 关联


为了配合分析,我们结合日志来帮助大家理解,设置如下参数,然后在执行语句:


set logging_module='on(opt_join)';set log_min_messages=debug2;
复制代码


第一步,如何获取 t1 和 t2 的数据


首先,如何获取 t1 和 t2 的数据,比如 Seq Scan、Index Scan 等,由于本例中,我们没有创建 Index,那选择只有 Seq Scan 了。日志片段显示:



​​我们先记住这三组 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 最优路径,下面就可以选择关联路径了。


第二步,求解(t1, t2)关联的最优路径


t1 和 t2 两个表的分布键都是 c1 列,但 Join 列都是 c2 列,那么理论上的路径就有:(放在右边表示作为内表)


1.   Broadcast(t1)join t2

2.   t1 joinBroadcast(t2)

3.   Broadcast(t2)join t1

4.   t2 joinBroadcast(t1)

5.   Redistribute(t1)join Redistribute(t2)

6.   Redistribute(t2)join Redistribute(t1)


然后每一种路径又可以搭配不同的 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 作为内表的路径。


第三步,求解(t1, t3)关联的最优路径


t1 和 t3 表的关联条件是:t1.c1 = t3.c2,因为 t1 的 Join 列是分布键 c1 列,于是 t1 表上不需要加 Redistribute;由于 t1 和 t3 的 Join 方式是 Semi Join,外表不能 Broadcast,否者可能会产生重复结果;另外还有一类 Unique Path 选择(即 t3 表去重),那么可用的候选路径大致如下:


1.    t1 semijoin Redistribute(t3)

2.   Redistribute(t3)right semi join t1

3.   t1 joinUnique(Redistribute(t3))

4.   Unique(Redistribute(t3))join t1


由于只有一边需要重分布且可以进行重分布,则不选 Broadcast,因为相同数据量时 Broadcast 的代价一般要高于重分布,提前剪枝掉。再把 Join 方法考虑进去,于是优化器给出了最终选择:



​此时的最优计划是选择了内表 Unique Path 的路径,即 t3 表先去重,然后在走 Inner Join 过程。


第四步,求解(t1,t2,t3)关联的最优路径


有了前面两步的铺垫,三个表关联的思路是类似的,形式上是分解成两个表先关联,然候在与第三个表关联,实际操作上是直接取出所有两表关联的 JoinRel,然后逐个增加另一个表,尝试关联,选择的方式如下:


  • JoinRel(t1,t2)  join t3:


  • (t1, t2)->(cheapest_startup_path + cheapest_total_path) joint3->(cheapest_startup_path + cheapest_total_path)


  • JoinRel(t1,t3)  join t2:


  • (t1, t3)->(cheapest_startup_path + cheapest_total_path) joint2->(cheapest_startup_path + cheapest_total_path)


  • JoinRel(t2, t3)join t1:由于没有(t2, t3)关联,所以此种情况不存在


每取一对内外表的 Path 进行 Join 时,也会判断是否需要重分布、是否可以去重,选择关联方式,比如 JoinRel(t1, t2)  join t3 时,也会尝试对 t3 表进行去重的 Path,因为这个 Join 本质仍然是 Semi Join。下图是选择过程中产生的部分有价值的候选路径(篇幅所限,只截取了一部分):



​优化器在这些路径中,选出了如下的最优路径:



对比实际的执行计划,二者是一样的(对比第 4 层 HashJoin 的“E-costs“是一样的):



​从这个过程可以大致感受到 path_list 有可能会发生一些膨胀,如果 path_list 中路径太多了,则可能会导致 cheapest_total_path 有多个,那么下一级的搜索空间也就会变的很大,最终会导致计划生成的耗时增加。关于 Join Path 的生成,作以下几点说明:


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 中随机选取的,这样保证随机性。


2. Aggregate Path 的生成

       

一般而言,Aggregate Path 生成是在表关联的 Path 生成之后,且有三个主要步骤(Unique Path 的 Aggregate 在 Join Path 生成的时候就已经完成了,但也会有这三个步骤):先估算出聚集结果的行数,然后选择 Path 的方式,最后创建出最优 Aggregate Path。前者依赖于统计信息和 Cost 估算模型,后者取决于前者的估算结果、集群规模和系统资源。Aggregate 行数估算主要根据聚集列的 distinct 值来组合,我们重点关注 Aggregate 行数估算和最优 Aggregate Path 选择。


2.1 Aggregate 行数估算


以如下 SQL 为例进行说明:


select t1.c2, t2.c2, count(*) cnt from t1, t2 where t1.c2 = t2.c2 and t1.c1 < 500 group by t1.c2, t2.c2;
复制代码


​该语句先是两表关联,基表上有过滤条件,然后求取两列的 GROUP BY 结果。这里的聚集列有两个,t1.c2 和 t2.c2,在看一下系统表中给出的原始信息:


postgres=# select tablename, attname, null_frac, n_distinct, n_dndistinct from pg_stats where (tablename = 't1' or tablename = 't2') and attname = 'c2'; tablename | attname | null_frac | n_distinct | n_dndistinct -----------+---------+-----------+------------+-------------- t1        | c2      |         0 |       -.25 |     -.431535 t2        | c2      |         0 |        100 |      -.39834(2 rows)
复制代码


统计信息显示 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 模型,相同列之间用完全相关模型,则 t1.c2 的 distinct 大约是这样:

distinct(t1.c2) = Poisson(d0, ratio1, nRows) * ratio2


其中 d0 表示基表中原始 distinct,ratio1 代表使用 Poisson 模型的 Ratio,ratio2 代表使用完全相关模型的 Ratio,nRows 是基表行数。如果需要定位分析问题,这些 Ratio 可以从日志中查阅,如下设置后在运行 SQL 语句:


set logging_module='on(opt_card)';set log_min_messages=debug3;
复制代码


​本例中,我们从日志中可以看到 t1 表上的两个 Ratio:



在看 t2.c2,这一列原始 distinct 是 100,而从上面日志中可以看出 t2 表的数据全匹配上了(没有 Ratio),那么 Join 完 t2.c2 的 distinct 也是 100。此时不能直接组合 t1.c2 和 t2.c2,因为"t1.c2 =t2.c2“暗含了这两个列的值是一样的,那就是说它们等价,于是只需考虑 Min(distinct(t1.c2), distinct(t2.c2))即可,下图是 Performance 给出的实际和估算行数:


postgres=# explain performance select t1.c2, t2.c2, count(*) cnt from t1, t2 where t1.c2 = t2.c2 and t1.c1 < 500 group by t1.c2, t2.c2;                                                                            QUERY PLAN                                                                            ------------------------------------------------------------------------------------------------------------------------------------------------------------------  id |                   operation                   |      A-time      | A-rows | E-rows | E-distinct |  Peak Memory   | E-memory | A-width | E-width | E-costs  ----+-----------------------------------------------+------------------+--------+--------+------------+----------------+----------+---------+---------+---------   1 | ->  Streaming (type: GATHER)                  | 48.500           |     99 |    100 |            | 80KB           |          |         |      16 | 89.29      2 |    ->  HashAggregate                          | [38.286, 40.353] |     99 |    100 |            | [28KB, 31KB]   | 16MB     | [24,24] |      16 | 79.29      3 |       ->  Hash Join (4,6)                     | [37.793, 39.920] |   1980 |   2132 |            | [6KB, 6KB]     | 1MB      |         |       8 | 75.04      4 |          ->  Streaming(type: REDISTRIBUTE)    | [0.247, 0.549]   |   1001 |   1001 | 25         | [53KB, 53KB]   | 2MB      |         |       4 | 32.95      5 |             ->  Seq Scan on test.t2           | [0.157, 0.293]   |   1001 |   1001 |            | [12KB, 12KB]   | 1MB      |         |       4 | 4.50       6 |          ->  Hash                             | [36.764, 38.997] |    998 |   1000 | 62         | [291KB, 291KB] | 16MB     | [20,20] |       4 | 29.88      7 |             ->  Streaming(type: REDISTRIBUTE) | [36.220, 38.431] |    998 |    999 |            | [53KB, 61KB]   | 2MB      |         |       4 | 29.88      8 |                ->  Seq Scan on test.t1        | [0.413, 0.433]   |    998 |    999 |            | [14KB, 14KB]   | 1MB      |         |       4 | 9.25    
复制代码


2.2 Aggregrate Path 生成


有了聚集行数,则可以根据资源情况,灵活选择聚集方式。Aggregate 方式主要有以下三种:


1.   Aggregate +Gather (+ Aggregate)

2.   Redistribute +Aggregate (+Gather)

3.   Aggregate +Redistribute + Aggregate (+Gather)


括号中的表示可能没有这一步,视具体情况而定。这些聚集方式可以理解成,两表关联时选两边 Redistribute 还是选一边 Broadcast。优化器拿到聚集的最终行数后,会尝试每种聚集方式,并计算相应的代价,选择最优的方式,最终生成路径。这里有两层 Aggregate 时,最后一层就是最终聚集行数,而第一层聚集行数是根据 Poisson 模型推算的。Aggregate 方式选择默认由优化器根据代价选择,用户也可以通过参数 best_agg_plan 指定。三类聚集方式大致适用范围如下:


  • 第一种,直接聚集后行数不太大,一般是 DN 聚集,CN 收集,有时 CN 需进行二次聚集

  • 第二种,需要重分布且直接聚集后行数未明显减少

  • 第三种,需要重分布且直接聚集后行数减少明显,重分布之后,行数又可以减少,一般是 DN 聚集、重分布、再聚集,俗称双层 Aggregate

四、结束语

       

本文着眼于计划生成的核心步骤,从行数估算、到 Join Path 的生成、再到 Aggregate Path 的生成,介绍了其中最简单过程的基本原理。而实际的处理方法远远比描述的要复杂,需要考虑的情况很多,比如多组选择率如何组合最优、分布键怎么选、出现倾斜如何处理、内存用多少等等。权衡整个计划生成过程,有时也不得不有所舍,这样才能有所得,而有时计划的一点劣势也可以忽略或者通过其他能力弥补上来,比如 SMP 开启后,并行的效果会淡化一些计划上的缺陷。总而言之,计划生成是一项复杂而细致的工作,生成全局最优计划需要持续的发现问题和优化,后续博文我们将继续探讨计划生成的秘密。


想了解 GuassDB(DWS)更多信息,欢迎微信搜索“GaussDB DWS”关注微信公众号,和您分享最新最全的 PB 级数仓黑科技,后台还可获取众多学习资料哦~


点击关注,第一时间了解华为云新鲜技术~

发布于: 2021 年 05 月 27 日阅读数: 199
用户头像

提供全面深入的云计算技术干货 2020.07.14 加入

华为云开发者社区,提供全面深入的云计算前景分析、丰富的技术干货、程序样例,分享华为云前沿资讯动态,方便开发者快速成长与发展,欢迎提问、互动,多方位了解云计算! 传送门:https://bbs.huaweicloud.com/

评论

发布
暂无评论
谋而后动:解读数仓计划生成中行数估算和路径生成的奥秘