当前位置 博文首页 > 华为云开发者社区:谋而后动:解读数仓计划生成中行数估算和路径
摘要: 孙子兵法云:“谋定而后动,知止而有得”,做任何事一定要进行谋划部署,做好准备,这样才能利于这件事的成功,切不可莽撞而行。同样,GaussDB(DWS)执行查询语句也会按照预定的计划来执行,给定硬件环境的情况下,执行的快慢全凭计划的好坏,那么一条查询语句的计划是如何制定的呢,本文将为大家解读计划生成中行数估算和路径生成的奥秘。
本文分享自华为云社区《GaussDB(DWS)计划生成原理揭秘(一)》,原文作者:Jugg 。
GaussDB(DWS)优化器的计划生成方法有两种,一是动态规划,二是遗传算法,前者是使用最多的方法,也是本系列文章重点介绍对象。一般来说,一条SQL语句经语法树(ParseTree)生成特定结构的查询树(QueryTree)后,从QueryTree开始,才进入计划生成的核心部分,其中有一些关键步骤:
本文主要关注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有多个过滤条件,从计划上看,部分条件下推到基表上了,部分条件没有下推,那么它的行数如何估出来的呢?我们首先从基表的行数估算开始。
如果基表上没有过滤条件或者过滤条件无法下推到基表上,那么基表的行数估算就是统计信息中显示的行数,不需要特殊处理。本节考虑下推到基表上的过滤条件,分单列和多列两种情况。
基表行数估算目前主要依赖于统计信息,统计信息是先于计划生成由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)
各字段含义如下:
从上面的统计信息可大致判断出具体的数据分布,如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,62 0,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“过滤之后的行数就可以估算出来了。
以上就是估算基表行数的基本思想。一般地,
比如t1表有两个过滤条件:t1.c1 = 100 and t1.c3 = 'gauss',那么如何估算该两列的综合选择率?在GaussDB(DWS)中,一般性方法有两个:
该情况下,首先按单列统计信息计算每个过滤条件的选择率,然后选择一种方式来组合这些选择率,选择的方式可通过设置cost_param来指定。为何需要选择组合方式呢?因为实际模型中,列与列之间是有一定相关性的,有的场景中相关性比较强,有的场景则比较弱,相关性的强弱决定了最后的行数。
该参数的意义和使用介绍可参考:GaussDB(DWS)性能调优系列实战篇五:十八般武艺之路径干预。
如果过滤的组合列的组合统计信息已经收集,则优化器会优先使用组合统计信息来估算行数,估算的基本思想与单列一致,即将多列组合形式上看成“单列”,然后再拿多列的统计信息来估算。
比如,多列统计信息有:((c1, c2, c4)),((c1, c2)),双括号表示一组多列统计信息:
多列条件匹配多列统计信息的总体原则是:
对于无法匹配多列统计信息列的过滤条件,则使用单列统计信息进行估算。
基表行数估算完,就可以进入表关联阶段的处理了。那么要关联两个表,就需要一些信息,如基表行数、关联之后的行数、关联的方式选择(也叫Path的选择,请看下一节),然后在这些方式中选择代价最小的,也称之为最佳路径。对于关联条件的估算,也有单个条件和多个条件之分,优化器需要算出所有Join条件和JoinFilter的综合选择率,然后给出估算行数,先看单个关联条件的选择率如何估算。
与基表过滤条件估算行数类似,也是利用统计信息来估算。比如上述SQL示例中的关联条件:t1.c2 = t2.c2,先看t1.c2的统计信息:
postgres=# select tablename, attname, null_frac, n_distinct, n_dndistinct, avg_width, most_common_vals, most_common_freqs from 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值会有差异,如下:
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中的值进行匹配。
表关联含有多个Join条件时,与基表过滤条件估算类似,也有两种思路,优先尝试多列统计信息进行选择率估算。当无法使用多列统计信息时,则使用单列统计信息按照上述方法分别计算出每个Join条件的选择率。那么组合选择率的方式也由参数cost_param控制,详细参考GaussDB(DWS)性能调优系列实战篇五:十八般武艺之路径干预。
另外,以下是特殊情况的选择率估算方式:
两表关联时,如果基表上有一些无法下推的过滤条件,则一般会变成JoinFilter,即这些条件是在Join过程中进行过滤的,因此JoinFilter会影响到JoinRel的行数,但不会影响基表扫描上来的行数。严格来说,如果把JoinRel看成一个中间表的话,那么这些JoinFilter是这个中间表的过滤条件,但JoinRel还没有产生,也没有行数和统计信息,因此无法准确估算。然而一种简单近似的方法是,仍然利用基表,粗略估算出这个JoinFilter的选择率,然后放到JoinRel最终行数估算中去。
有了前面两节的行数估算的铺垫,就可以进入路径生成的流程了。何为路径生成?已知表关联的方式有多种(比如 NestLoop、HashJoin)、且GaussDB(DWS)的表是分布式的存储在集群中,那么两个表的关联方式可能就有多种了,而我们的目标就是,从这些给定的基表出发,按要求经过一些操作(过滤条件、关联方式和条件、聚集等等),相互组合,层层递进,最后得到我们想要的结果。这就好比从基表出发,寻求一条最佳路径,使得我们能最快得到结果,这就是我们的目的。本节我们介绍Join Path和Aggregate 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列,共有两个关联条件:
为了配合分析,我们结合日志来帮助大家理解,设置如下参数,然后在执行语句:
set logging_module='on(opt_join)'; set log_min_messages=debug2;
首先,如何获取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最优路径,下面就可以选择关联路径了。