一文读懂简单查询代价估算

　　摘要：查询引擎会在所有可行的查询访问路径中选择执行代价最低的一条。
　　本文分享自华为云社区《一文读懂简单查询代价估算【这次高斯不是数学家】云社区华为云》，作者：leapdb。查询代价估算如何选择一条最优的执行路径
　　SQL生命周期：词法分析（Lex）语法分析（YACC）分析重写查询优化（逻辑优化和物理优化）查询计划生成查询执行。词法分析：描述词法分析器的。l文件经Lex工具编译生成lex。yy。c，再由C编译器生成可执行的词法分析器。基本功能就是将一堆字符串根据设定的保留关键字和非保留关键字，转化成相应的标识符（Tokens）。语法分析：语法规则描述文件。y经YACC工具编译生成gram。c，再由C编译器生成可执行的语法分析器。基本功能就是将一堆标识符（Tokens）根据设定的语法规则，转化成原始语法树。分析重写：查询分析将原始语法树转换为查询语法树（各种transform）；查询重写根据pgrewrite中的规则改写表和视图，最终得到查询语法树。查询优化：经过逻辑优化和物理优化（生成最优路径）。查询计划生成：将最优的查询路径转化为查询计划。查询执行：通过执行器去执行查询计划生成查询的结果集。
　　在物理优化阶段，同样的一条SQL语句可以产生很多种查询路径，例如：多表JOIN操作，不同的JOIN顺序产生不同的执行路径，也导致中间结果元组规模的不同。查询引擎会在所有可行的查询访问路径中选择执行代价最低的一条。
　　通常我们依据COSTCOST（CPU）COST（IO）这一公式来选择最优执行计划。这里最主要的问题是如何确定满足某个条件的元组数量，基本方法就是依据统计信息和一定的统计模型。某条件的查询代价tuplenumpertuplecost。
　　统计信息主要是pgclass中的relpages和reltuples，以及pgstatistics中的distinct，nullfrac，mcv，histgram等。为何需要这些统计信息，有了这些够不够？
　　统计信息的收集来自analyze命令通过random方式随机采集的部分样本数据。我们将其转化为一个数学问题就是：给定一个常量数组可以分析出来哪些数据特征？找规律哈。
　　用最朴素的数学知识能想到的是：是不是空数组是不是常量数组是不是unique无重复是不是有序是不是单调的，等差，等比出现次数最多的数字有哪些数据的分布规律（打点方式描绘数据增长趋势）
　　还有吗？这是一个值得不断思考的问题。如何依据统计信息估算查询代价
　　统计信息是不准确的，不可靠的，两个原因：统计信息只来自部分采样数据，不能精准描述全局特征。统计信息是历史数据，实际数据随时可能在变化。
　　如何设计一个数学模型，利用不可靠的统计信息，尽可能准确的估算查询代价，是一个很有意思的事情。接下来我们通过一个个的具体例子来介绍。
　　主要内容来自以下链接，我们主要对其进行详细的解读。
　　https：www。postgresql。orgdocs14plannerstatsdetails。html
　　https：www。postgresql。orgdocs14usingexplain。html最简单的表的行数估算（使用relpages和reltuples）SELECTrelpages，reltuplesFROMpgclassWHERErelnametenk1；采样估算有358个页面，10000条元组relpagesreltuples35810000EXPLAINSELECTFROMtenk1；查询估算该表有10000条元组QUERYPLANSeqScanontenk1（cost0。00。。458。00rows10000width244）
　　【思考】查询计划中估算的rows10000就直接是pgclassreltuples吗？
　　统计信息是历史数据，表的元组数在随时变化。例如：analyze数据采样时有10个页面，存在50条元组；实际执行时有20个页面，可能存在多少条元组？用你最朴素的情感想一想是不是，很可能是100条元组对不对？
　　表大小的估算方法在函数estimaterelsizetablerelationestimatesizeheapamestimaterelsize中。先通过表物理文件的大小计算实际页面数actualpagesfilesizeBLOCKSIZE计算页面的元组密度a。如果相关页大于0，密度reltuples（双）重页b。如果relpages为空，density（BLCKSZSizeOfPageHeaderData）tuplewidth，页面大小元组宽度。估算表元组个数页面元组密度实际页面数actualpages
　　所以，估算rows的10000（10000358）358，历史页面密度新的页面数，以推算当前元组数。最简单的范围比较（使用直方图）SELECThistogramboundsFROMpgstatsWHEREtablenametenk1ANDattnameunique1；histogrambounds｛0，993，1997，3050，4040，5036，5957，7057，8029，9016，9995｝EXPLAINSELECTFROMtenk1WHEREunique11000；估算小于1000的有1007条QUERYPLANBitmapHeapScanontenk1（cost24。06。。394。64rows1007width244）RecheckCond：（unique11000）BitmapIndexScanontenk1unique1（cost0。00。。23。80rows1007width0）IndexCond：（unique11000）
　　查询引擎在查询语法树的WHERE子句中识别出比较条件，再到pgoperator中根据操作符和数据类型找到oprrest为scalarltsel，这是通用的标量数据类型的小于操作符的代价估算函数。最终是在scalarineqselineqhistogramselectivity中进行直方图代价估算。
　　在PG中采用的是等高直方图，也叫等频直方图。将样本范围划分成N等份的若干个子区间，取所有子区间的边界值，构成直方图。
　　使用：使用时认为子区间（也叫桶）内的值是线性单调分布的，也认为直方图的覆盖范围就是整个数据列的范围。因此，只需计算出在直方图中的占比，既是总体中的占比。
　　【思考】以上的两点假设靠谱吗？有没有更合理的办法？选择率（前面桶的总数目标值在当前桶中的范围当前桶的区间范围）桶的总数selectivity（1（1000bucket〔2〕。min）（bucket〔2〕。maxbucket〔2〕。min））numbuckets（1（1000993）（1997993））100。100697估算元组数基表元组数条件选择率rowsrelcardinalityselectivity100000。1006971007（roundingoff）最简单的等值比较（使用MCV）SELECTnullfrac，ndistinct，mostcommonvals，mostcommonfreqsFROMpgstatsWHEREtablenametenk1ANDattnamestringu1；nullfrac0ndistinct676mostcommonvals｛EJAAAA，BBAAAA，CRAAAA，FCAAAA，FEAAAA，GSAAAA，JOAAAA，MCAAAA，NAAAAA，WGAAAA｝mostcommonfreqs｛0。00333333，0。003，0。003，0。003，0。003，0。003，0。003，0。003，0。003，0。003｝EXPLAINSELECTFROMtenk1WHEREstringu1CRAAAA；QUERYPLANSeqScanontenk1（cost0。00。。483。00rows30width244）Filter：（stringu1CRAAAA：：name）
　　查询引擎在查询语法树的WHERE子句中识别出比较条件，再到pgoperator中根据操作符和数据类型找到oprrest为eqsel，这是通用的等值比较操作符的代价估算函数。最终是在eqselinternalvareqconst中进行MCV代价估算。
　　MCV是在样本中选取重复次数最多的前100个组成，并计算每个值在样本中的占比。使用时，就简单的认为这个占比就是在全局中的占比。
　　【思考】将样本中占比就这样简单的认为是在全局中的占比，这样合理吗？有没有更好的办法？CRAAAA位于MCV中的第3项，占比是0。003selectivitymcf〔3〕0。003rows100000。00330
　　接下来，我们在看一个不在MCV中的等值比较。EXPLAINSELECTFROMtenk1WHEREstringu1xxx；查找不存在于MCV中的值QUERYPLANSeqScanontenk1（cost0。00。。483。00rows15width244）Filter：（stringu1xxx：：name）
　　通常MCV用于等值比较，直方图用于范围比较。不存在于MCV中的值，认为它们共享不存在于MCV中的概率，即：选择率（1MCV概率总和）（不在MCV中的值的distinct个数）。
　　【思考】这样判断不在MCV中的方法合理吗？有没有更好的方法？selectivity（1sum（mvf））（numdistinctnummcv）（1（0。003333330。0030。0030。0030。0030。0030。0030。0030。0030。003））（67610）0。0014559rows100000。001455915（roundingoff）复杂一点的范围比较（同时使用MCV和直方图）
　　前面unique1000的例子，在scalarineqsel函数中只利用到了直方图，是因为unique列没有重复值，也就不存在MCV。下面我们用一个不是unique的普通列再看一下范围比较。
　　这个范围包括两部分，重复次数比较多的值（在MCV中）和重复次数比较少的值（覆盖在直方图里），又由于计算直方图时去掉了MCV的值，因此MCV和直方图互相独立可以联合使用。SELECTnullfrac，ndistinct，mostcommonvals，mostcommonfreqsFROMpgstatsWHEREtablenametenk1ANDattnamestringu1；nullfrac0ndistinct676mostcommonvals｛EJAAAA，BBAAAA，CRAAAA，FCAAAA，FEAAAA，GSAAAA，JOAAAA，MCAAAA，NAAAAA，WGAAAA｝mostcommonfreqs｛0。00333333，0。003，0。003，0。003，0。003，0。003，0。003，0。003，0。003，0。003｝SELECThistogramboundsFROMpgstatsWHEREtablenametenk1ANDattnamestringu1；histogrambounds｛AAAAAA，CQAAAA，FRAAAA，IBAAAA，KRAAAA，NFAAAA，PSAAAA，SGAAAA，VAAAAA，XLAAAA，ZZAAAA｝EXPLAINSELECTFROMtenk1WHEREstringu1IAAAAA；查找一个不存在于MCV中的值QUERYPLANSeqScanontenk1（cost0。00。。483。00rows3077width244）Filter：（stringu1IAAAAA：：name）
　　小于IAAAAA的值在MCV中有前6个，因此把它们的frac累加起来，就是小于IAAAAA且重复次数较多的人的概率selectivitysum（relevantmvfs）0。003333330。0030。0030。0030。0030。0030。01833333
　　还有一部分小于IAAAAA但重复次数较少的人的概率可以通过直方图进行范围计算。前面使用unique1列进行等值比较时，因为unique约束列不存在MCV，只有直方图。因此，只计算在直方图中桶的覆盖占比就是选择率了。这里还要考虑落在直方图中值的整体占比histogramfraction1sum（mcvfrac），直方图桶的覆盖占比整个直方图整体占比就是在直方图中的选择率了。selectivitymcvselectivityhistogramselectivityhistogramfraction0。01833333（（2（IAAAAAFRAAAA）（IBAAAAFRAAAA））10）（1sum（mvfs））0。018333330。2983870。969666670。307669rows100000。3076693077（roundingoff）
　　【思考】在这个特殊的例子中，从MCV中计算出来的选择率为0。01833333，远小于从直方图中计算出来的选择率0。28933593，是因为该列中数值分布的太平缓了（统计信息显示MCV中的这些值出现的频率比其他值要高，这可能是因为采样导致的错误）。在大多数存在明显重复值多的场景下，从MCV中计算出的选择率会比较明显，因为重复值的出现概率是比较准确的。多条件联合查询的例子EXPLAINSELECTFROMtenk1WHEREunique11000ANDstringu1xxx；QUERYPLANBitmapHeapScanontenk1（cost23。80。。396。91rows1width244）RecheckCond：（unique11000）Filter：（stringu1xxx：：name）BitmapIndexScanontenk1unique1（cost0。00。。23。80rows1007width0）IndexCond：（unique11000）
　　多条件的选择率计算其实也很简单，就按条件本身的逻辑运算来。
　　两个条件是与的关系，属于互相独立事件，就相乘就可以了。selectivityselectivity（unique11000）selectivity（stringu1xxx）0。1006970。00145590。0001466rows100000。00014661（roundingoff）一个使用JOIN的例子EXPLAINSELECTFROMtenk1t1，tenk2t2WHEREt1。unique150ANDt1。unique2t2。unique2；QUERYPLANNestedLoop（cost4。64。。456。23rows50width488）BitmapHeapScanontenk1t1（cost4。64。。142。17rows50width244）RecheckCond：（unique150）BitmapIndexScanontenk1unique1（cost0。00。。4。63rows50width0）IndexCond：（unique150）IndexScanusingtenk2unique2ontenk2t2（cost0。00。。6。27rows1width244）IndexCond：（unique2t1。unique2）
　　unique150这个约束在nestedloopjoin之前被执行，还是使用直方图计算，类似前面的简单范围查找的例子，只不过这次50落在第一个桶中。selectivity（0（50bucket〔1〕。min）（bucket〔1〕。maxbucket〔1〕。min））numbuckets（0（500）（9930））100。005035rows100000。00503550（roundingoff）
　　JOIN约束t1。unique2t2。unique2的选择率估算，还是先到pgoperator中查找等于操作符的oprjoin，是eqjoinsel。JOIN的话，两边的统计信息都要参考。SELECTtablename，nullfrac，ndistinct，mostcommonvalsFROMpgstatsWHEREtablenameIN（tenk1，tenk2）ANDattnameunique2；tablenamenullfracndistinctmostcommonvalstenk101tenk201
　　对于unique列没有MCV，所以这里我们只能依赖distinct和nullfrac来计算选择率。【】选择率两边的非空概率相乘，再除以最大JOIN条数。selectivity（1nullfrac1）（1nullfrac2）min（1numdistinct1，1numdistinct2）（10）（10）max（10000，10000）0。0001【】JOIN的函数估算就是两边输入数量的笛卡尔积，再乘以选择率rows（outercardinalityinnercardinality）selectivity（5010000）0。000150
　　如果存在MCV，则分成两部分计算选择率：在MCV中的部分和不在MCV中的部分。更详细的信息
　　表大小的估算：src后端optimizerutilplancat。c
　　一般逻辑子句的选择率估算：srcbackendoptimizerpathclausesel。c
　　操作符函数的选择率估算：srcbackendutilsadtselfuncs。c。
　　点击下方，第一时间了解华为云新鲜技术
　　华为云博客大数据博客AI博客云计算博客开发者中心华为云