5.1 统计信息5.1.1 PG_STATISTIC系统表统计信息的作用物理优化需要计算各种物理路径的代价代价估算严重依赖于统计信息统计信息是否能准确描述表中的数据分布是决定代价准确性的重要条件单列统计信息类型7种类型说明STATISTIC_KIND_MCV高频值常见值在一个列里出现最频繁的值按频率排序生成一一对应的频率数组STATISTIC_KIND_HISTOGRAM直方图使用等频直方图描述数据分布高频值不出现保证数据分布相对平坦STATISTIC_KIND_CORRELATION相关系数记录未排序数据分布和排序后数据分布的相关性用于索引扫描代价估计STATISTIC_KIND_MCELEM类型高频值用于数组类型或特殊类型由ts_typanalyze函数生成STATISTIC_KIND_DECHIST数组类型直方图由array_typanalyze函数生成STATISTIC_KIND_RANGE_LENGTH_HISTOGRAMRange类型基于长度的直方图由range_typanalyze函数生成STATISTIC_KIND_BOUNDS_HISTOGRAMRange类型基于边界的直方图由range_typanalyze函数生成多列统计信息类型2种类型说明STATS_EXT_NDISTINCT记录基于多列的消重之后的数据量类似单列的stadistinctSTATS_EXT_DEPENDENCIES计算各个列之间的函数依赖度得到准确的统计信息选择率示例-- 高选择率采用顺序扫描EXPLAINSELECT*FROMSTUDENTWHEREsno2;-- 结果Seq Scan on student (cost0.00..224.00 rows9999 width10)-- 低选择率采用索引扫描EXPLAINSELECT*FROMSTUDENTWHEREsno2;-- 结果Index Scan using student_pkey on student (cost0.29..8.30 rows1 width10)顺序读vs随机读#defineDEFAULT_SEQ_PAGE_COST1.0// 顺序读的单页代价#defineDEFAULT_RANDOM_PAGE_COST4.0// 随机读的单页代价PG_STATISTIC系统表结构-- 基本字段starelid-- 对应表的OID来自PG_CLASSstaattnum-- 列的编号来自PG_ATTRIBUTESstanullfrac-- NULL值率NULL值所占比例stawidth-- 列的平均宽度stadistinct-- 消重之后的数据个数或比例stadistinct取值 0代表未知或者未计算的情况0代表消除重复值之后的个数 0绝对值是去重之后的个数占总个数的比例通常使用示例分析-- STUDENT表统计信息starelid|staattnum|stanullfrac|stawidth|stadistinct--------------------------------------------------------24582|1|0|4|-1-- sno列24582|2|0.142857|3|-0.571429-- sname列24582|3|0.142857|4|-0.285714-- ssex列槽位系统每个属性最多支持5种统计方法STATISTIC_NUM_SLOTS 5每个槽位包含stakind、staop、stanumbers、stavalues不同列使用不同数量的槽位槽位示例-- 第一个槽位starelid|staattnum|stakind1|staop1|stanumbers1|stavalues1------------------------------------------------------------------------------24582|1|2|97||{1,2,3,4,5,6,7}-- sno直方图24582|2|1|98|{0.285714,0.285714}|{ls,zs}-- sname MCV24582|3|1|96|{0.571429,0.285714}|{1,2}-- ssex MCV5.1.2 PG_STATISTIC_EXT系统表创建多列统计信息CREATESTATISTICSSTATEXT_STUDENTONsno,sname,ssexFROMSTUDENT;系统表结构属性类型说明stxrelidOid统计信息属于哪个表stxnameNameData统计信息的名字stxnamespaceOid统计信息的namespacestxownerOid统计信息的创建者stxkeysint2vector统计哪些列stxkindchar统计信息类型dNDISTINCT, fDEPENDENCIESstxndistinctpg_ndistinctNDISTINCT类型的统计信息stxdependenciespg_dependenciesDEPENDENCIES类型的统计信息示例CREATESTATISTICSSTATEXT_STUDENTONsno,sname,ssexFROMSTUDENT;ANALYZESTUDENT(sno,sname,ssex);-- 查看统计信息SELECT*FROMpg_statistic_extWHEREstxnamestatext_student;-- 结果包含NDISTINCT和DEPENDENCIES信息5.1.3 单列统计信息生成生成步骤数据采样acquire_sample_rows函数数据统计compute_scalar_stats函数等采样算法第一阶段S算法选择抽样技术对页面进行随机采样第二阶段Z(Vitter)算法蓄水池抽样对元组进行采样S算法简化版从N个记录中随机选取n个记录0 n N S1. [初始化] K N - t, k n - m S2. [生成随机数] 0 V 1 S3. [生成跳过条件] p 1 - k/K S4. [检测] 如果 V p跳转至S6 S5. [纳入样本] m, t, 如果 m n 跳转至S2 S6. [跳过] t, K--, p * 1 - k/K, 跳转至S4Vitter算法改进随机数生成算法改进通过随机变量跳过记录避免O(N)复杂度使用临界点22.0 × n在X算法和Z算法之间切换采样框架acquire_sample_rows{BlockSampler_Init;// S算法赋初值reservoir_init_selection_state;// Z算法赋初值while(BlockSampler_HasMore){blockBlockSampler_Next;// S算法核心foreach(tuple in block){if(蓄水池未满){记录TUPLE到蓄水池;}if(rowstoskip0){// Z算法中的随机变量Trowstoskipreservoir_get_next_S;if(rowstoskip0){随机替换蓄水池中的元组;}}}}}元组密度估算EMA方法old_densityold_rel_tuples/old_rel_pages;new_densityscanned_tuples/scanned_pages;multiplier(double)scanned_pages/(double)total_pages;updated_densityold_density(new_density-old_density)*multiplier;reltuplesfloor(updated_density*total_pages0.5);采样相关变量变量说明old_rel_pages目前采样的表中的总页面数old_rel_tuples目前采样的表中的总元组数scanned_pages第一阶段采样获得的页面数scanned_tuples第二阶段采样获得的有效元组数total_pages第一阶段采样时获得的实际总页面数统计方法选择if(OidIsValid(eqopr)OidIsValid(ltopr)){stats-compute_statscompute_scalar_stats;// 有等值和不等值操作符}elseif(OidIsValid(eqopr)){stats-compute_statscompute_distinct_stats;// 只有等值操作符}else{stats-compute_statscompute_trivial_stats;// 其他情况}compute_scalar_stats函数处理流程以sname列为例初始状态 samplerows 7 -- 样本容量 null_cnt 1 -- NULL值个数 nonnull_cnt 6 -- 非NULL值个数 toowide_cnt 0 -- 超长值的个数 total_width 18 -- 非NULL值的长度总和 排序后 ndistinct 4 -- 去掉重复值和NULL值之后的个数 stanullfrac 1/7 -- NULL值比例 stdwidth 3 -- 平均宽度 stadistinct 4/7 -- 去重比例MCV高频值确定情况1所有值都可以做MCV值满足条件时情况2部分值做MCV值不满足条件时直方图生成使用等频直方图桶数计算num_hist ndistinct - num_mcv边界值确定通过排序后的值均匀分布相关系数计算// 排序前编号0, 1, 2, 3, 4, 5// 排序后编号1, 5, 2, 3, 0, 4// 相关系数公式ρ (n * ∑xd - ∑x * ∑d) / (√(n * ∑x² - (∑x)²) * √(n * ∑d² - (∑d)²))5.1.4 多列统计信息生成STATS_EXT_NDISTINCT类型记录多列组合的去重数据量例如{sno, sname}、{sno, ssex}、{sname, ssex}、{sno, sname, ssex}的去重数据量生成流程for(k2;knumattrs;k){generatorgenerator_init(numattrs,k);while((combinationgenerator_next(generator))){item-ndistinctndistinct_for_combination(...);}}STATS_EXT_DEPENDENCIES类型计算列之间的函数依赖度函数依赖度定义两个属性之间满足函数依赖的值占总体数量的比例函数依赖度计算for(i1;inumrows;i){if(当前值和上一个值不同){if(n_violations0){n_supporting_rowsgroup_size;}n_violations0;group_size1;}else{if(第k个值相同){group_size;}else{n_violations;}}}// 函数依赖度 n_supporting_rows / numrows数据结构// MVDependencies记录整个多列统计信息的函数依赖关系typedefstructMVDependencies{uint32 magic;uint32 type;uint32 ndeps;MVDependency*deps[FLEXIBLE_ARRAY_MEMBER];}MVDependencies;// MVDependency记录每个单独的函数依赖关系typedefstructMVDependency{doubledegree;// 函数依赖度AttrNumber nattributes;// 涉及的属性数量AttrNumber attributes[FLEXIBLE_ARRAY_MEMBER];}MVDependency;5.2 选择率5.2.1 使用函数依赖计算选择率使用条件约束条件中只涉及一个表该表上有基于函数依赖的统计信息约束条件形式Var Const或RelabelType Const统计信息选择原则约束条件的属性和函数依赖关系统计信息中的键值取交集交集中的键值多的最适用如果交集中键值数相同则键值数少的获胜示例-- 约束条件A 1 AND B 1-- 统计信息键值{A, B}, {A, B, C}, {B, C, D}-- 最适合使用{A, B}交集2键值数2选择率计算公式P(A Const, B Const) P(A Const) * (d (1-d) * P(B Const)) 其中d是{A - B}的函数依赖度递归计算while(true){dependencyfind_strongest_dependency(stat,dependencies,clauses_attnums);s2clause_selectivity(root,clause,...);s1*(dependency-degree(1-dependency-degree)*s2);}5.2.2 子约束条件的选择率默认选择率clause_selectivity函数默认选择率0.5缓存机制RestrictInfo-norm_selec和outer_selec选择率计算函数表子约束条件类型计算方法Var使用boolvarsel函数或默认0.5ConstNULL或0→选择率0其他→选择率1Param先常量替换否则默认0.5NOTP(B) 1 – P(A)ANDP(AB) P(A) × P(B)ORP(AB) P(A) P(B) – P(AB)NullTest有统计信息IS NULLstanullfracIS NOT NULL1-stanullfracBooleanTest根据统计信息中的高频值数组计算CurrentOfExpr选择率 1/表的元组数量RelabelType递归调用clause_selectivityCoerceToDomain递归调用clause_selectivity5.2.3 基于范围的约束条件的选择率修正问题约束条件A 5 AND A 7 AND A 9 AND A 8中的子条件不独立解决方法使用RangeQueryClause链表数据结构typedefstructRangeQueryClause{structRangeQueryClause*next;Node*var;// 属性列bool have_lobound;// 是否有下界bool have_hibound;// 是否有上界Selectivity lobound;// 下界选择率Selectivity hibound;// 上界选择率}RangeQueryClause;修正逻辑if(上界和下界同时存在){s2hiboundlobound-1.0;// P(A x) P(A y) 1 - P(A x AND A y)s2nulltestsel(IS_NULL);// 考虑NULL值s1*s2;}else{if(只有下界)s1*lobound;if(只有上界)s1*hibound;}5.3 OpExpr的选择率连接条件vs过滤条件varRelid有值过滤条件sjinfo NULL过滤条件其他根据引用表数量判断操作符选择率函数对照表操作符oprrest函数oprjoin函数eqseleqjoinselneqselneqjoinsel, scalarltselScalarltjoinsel, scalargtselscalargtjoinsel~regexeqselregexeqjoinsel~~likesellikejoinsel5.3.1 eqsel函数处理流程eqsel/neqsel ↓ eqsel_internal(negate) ↓ const? → var_eq_const nonconst? → var_eq_non_constvar_eq_const函数逻辑如果列有唯一性选择率 1/元组数量如果常量在高频值数组中直接使用高频值频率否则计算剩余值的平均选择率选择率计算// 从高频值数组获取for(i0;isslot.nvalues;i){if(匹配成功){selecsslot.numbers[i];break;}}// 未匹配时sumcommonsum(所有高频值比例);selec1.0-sumcommon-nullfrac;// 去除NULL和高频值otherdistinctget_variable_numdistinct()-sslot.nnumbers;selec/otherdistinct;// 平均分配// 限制不能比高频值中最低的比例高if(selecsslot.numbers[sslot.nnumbers-1])selecsslot.numbers[sslot.nnumbers-1];5.3.2 scalargtsel函数处理流程保证Var在操作符左侧调用scalarineqsel函数结合MCV和直方图计算直方图计算// 二分法找Const所在的桶while(loboundhibound){intprobe(loboundhibound)/2;// get_actual_variable_range修正边界值}// 计算桶内比例if(桶边界相等)binfrac0.5;elseif(vallow)binfrac0.0;elseif(valhigh)binfrac1.0;elsebinfrac(val-low)/(high-low);// 总选择率histfrac(满足条件的桶数binfrac)/总桶数;selec(1.0-NULL比例-高频值比例)× histfracmcv_selec;5.3.3 eqjoinsel函数连接选择率计算的4个部分NULL值率部分一个表的某列NULL值比例高频值数组中互相匹配部分两个表的高频值数组取交集高频值数组中未匹配部分去掉互相匹配的值其他值部分去掉NULL值和高频值后的值选择率公式selec S(x2)×S(y2) S(x3)×S(y4) S(x4)×S(y3) S(x4)×S(y4) ───────────────────────────────────────────────────────── N × N其中S(x2), S(y2)高频值数组中互相匹配的部分S(x3), S(y3)高频值数组中未匹配的部分S(x4), S(y4)其他值的部分匹配算法for(i0;isslot1.nvalues;i){for(j0;jsslot2.nvalues;j){if(值相等){matchprodfreqsslot1.numbers[i]*sslot2.numbers[j];hasmatch1[i]hasmatch2[j]true;nmatches;break;}}}5.4 小结核心要点统计信息是选择率计算的基础PostgreSQL 10.0之前只有单列统计信息10.0增加了多列统计信息选择率估算依赖统计信息的准确性假设数据分布平坦可能导致估算偏差无法使用统计信息时采用默认值局限性统计信息基于样本样本显著性影响结果数据更新后不会立即更新统计信息基于概率的方法不适用于所有情况默认值可能导致代价估算偏差关键概念速查概念定义用途选择率约束条件过滤后的元组数占总元组数的比例查询代价估算MCV高频值数组记录最频繁出现的值及其频率等值条件选择率计算直方图等频直方图描述数据分布范围条件选择率计算相关系数未排序和排序后数据分布的相关性索引扫描代价估计函数依赖列之间的依赖关系多列约束条件选择率计算EMA指数平均数指标元组密度估算S算法页面采样算法统计信息生成第一阶段Z算法蓄水池采样算法统计信息生成第二阶段常用SQL查询-- 查看表的统计信息SELECT*FROMpg_statisticWHEREstarelid表名::regclass;-- 查看表的基本信息SELECTrelname,relpages,reltuplesFROMpg_classWHERErelname表名;-- 创建多列统计信息CREATESTATISTICSstats_nameONcol1,col2,col3FROMtable_name;-- 更新统计信息ANALYZEtable_name;-- 查看多列统计信息SELECT*FROMpg_statistic_extWHEREstxnamestats_name;-- 查看查询计划EXPLAINANALYZESELECT*FROMtable_nameWHERE条件;