一、章节概览本章是逻辑优化的核心章节承接逻辑重写优化开启物理优化的准备工作。主要内容是将查询树中的逻辑结构转换为适合物理优化的数据结构并进行谓词下推、等价类推理、连接顺序优化等关键操作。核心主题从逻辑层RangeTblEntry到物理层RelOptInfo的转换以及约束条件的智能下推与推理。二、核心概念详解2.1 RelOptInfo 结构体作用替代 RangeTblEntry用于物理优化阶段的代价计算和路径生成。三种主要类型类型说明RELOPT_BASEREL基表普通表、子查询、函数等RELOPT_JOINREL连接操作产生的中间结果RELOPT_OTHER_MEMBER_REL继承表子表、UNION子查询等关键成员变量Relids relids;// 基表的rtindex或连接表的rtindex集合doublerows;// 估计的结果集行数bool consider_startup;// 是否考虑启动代价用于LIMIT子句bool consider_param_startup;// 参数化路径是否考虑启动代价bool consider_parallel;// 是否考虑并行查询// 路径相关List*pathlist;// 所有记录的路径List*ppilist;// 参数化路径的参数List*partial_pathlist;// 并行路径链表structPath*cheapest_startup_path;// 启动代价最低的路径structPath*cheapest_total_path;// 整体代价最低的路径// 基表特有变量Index relid;// 基表的rtindexOid reltablespace;// 表空间RTEKind rtekind;// 表类型RTE_RELATION/RTE_SUBQUERY/RTE_FUNCTIONAttrNumber min_attr,max_attr;// 首列和末列编号Relids*attr_needed;// 每列被哪些表引用int32*attr_widths;// 每列的宽度List*indexlist;// 索引列表IndexOptInfoBlockNumber pages;// 页面数doubletuples;// 元组数List*baserestrictinfo;// 基表过滤条件List*joininfo;// 连接条件2.2 IndexOptInfo 结构体作用描述索引信息用于生成索引扫描路径和计算代价。关键成员Oid indexoid;// 索引OIDRelOptInfo*rel;// 所属基表BlockNumber pages;// 索引页面数doubletuples;// 索引元组数intncolumns;// 索引键值数int*indexkeys;// 具体的键值Oid*opfamily;// 操作符族Oid*opcintype;// 操作符类bool*reverse_sort;// 升序/降序bool*nulls_first;// NULL位置bool*canreturn;// 索引能否直接返回索引项Oid relam;// 访问方法B-tree/Hash等List*indexprs;// 表达式索引中的表达式List*indpred;// 局部索引的谓词bool predOK;// 谓词是否满足查询需要bool unique;// 唯一索引索引类型分类唯一索引/主键索引通过unique标识immediate控制是否延迟检查局部索引带WHERE条件的索引存储在indpredpredOK标识是否可用表达式索引索引键值包含表达式存储在indexprs2.3 RestrictInfo 结构体作用封装约束条件记录下推过程中的各种状态信息。关键成员Expr*clause;// 约束条件表达式bool is_pushed_down;// true过滤条件false不能下推的连接条件bool outerjoin_delayed;// 下推过程中是否被外连接阻碍bool can_join;// 是否可用于Merge Join/Hash JoinVarVar形式bool pseudoconstant;// 常量表达式Relids clause_relids;// 约束条件引用的表Relids required_relids;// 约束条件被应用的最小集合Relids outer_relids;// Nonnullable-side表的集合Relids nullable_relids;// 下层外连接的Nullable-side表集合Relids left_relids;// 左操作数对应的表Relids right_relids;// 右操作数对应的表EquivalenceClass*left_ec;// 左操作数对应的等价类EquivalenceClass*right_ec;// 右操作数对应的等价类三、核心算法流程3.1 创建 RelOptInfo流程setup_simple_rel_arrays()将 Query-rtable 中的 RangeTblEntry 提取到simple_rte_arrayadd_base_rels_to_query()遍历 Query-jointree为每个 RangeTblRef 创建 RelOptInfobuild_simple_rel()实际创建 RelOptInfo根据 rtekind 确定具体类型基表类型层次RELOPT_BASEREL ├── RTE_RELATION普通表→ get_relation_info() 填充统计信息 ├── RTE_SUBQUERY子查询→ 递归遍历子查询 ├── RTE_VALUESVALUES子查询 └── RTE_FUNCTION函数型基表普通表信息获取页面数RelationGetNumberOfBlocks()文件大小/块大小元组数通过SYS_CLASS统计信息估算元组密度 × 当前页面数TRUNCATE后的表假设页面满用BLCKSZ / tuple_width计算3.2 等价类EquivalenceClass定义基于多个等值约束条件AB推理出的等价属性集合。示例-- AB AND BC → {A,B,C}构成等价类-- 推理出 AC可生成更多连接路径-- AB AND B5 → {A,B,5}构成等价类-- 推理出 A5可下推到基表过滤数据结构typedefstructEquivalenceClass{List*ec_opfamilies;// 操作符族List*ec_members;// 等价类成员链表EquivalenceMemberList*ec_sources;// 产生等价类的约束条件List*ec_derives;// 推理产生的约束条件Relids ec_relids;// 涉及的所有表bool ec_has_const;// 是否含常量bool ec_has_volatile;// 是否含易失性函数bool ec_below_outer_join;// 是否在外连接之下bool ec_broken;// 推理失败标记structEquivalenceClass*ec_merged;// 已合并到另一个等价类}EquivalenceClass;等价类的价值扩充连接路径AB, BC → 推理出 AC下推过滤条件AB, B5 → 推理出 A5 下推到A表优化排序AB, ORDER BY B → 可按A排序四、谓词下推Predicate Pushdown4.1 连接条件下推规则结论1连接条件下推后变成过滤条件过滤条件下推后仍然是过滤条件。结论2外连接限制连接条件引用了Nonnullable-side的表 →不能下推连接条件只引用了Nullable-side的表 →可以下推各连接类型的 Nullable-side/Nonnullable-side连接类型Nonnullable-sideNullable-sideA Left Join BABA Right Join BBAA Full Join BA、BA、BA Semi Join BA、B无A Anti Join BAB示例-- 左外连接连接条件引用Nonnullable-side不能下推SELECT*FROMSTUDENTLEFTJOINSCOREONSTUDENT.sno1;-- 执行计划Join Filter: (student.sno 1) -- 保持为连接条件-- 右外连接连接条件引用Nullable-side可以下推SELECT*FROMSTUDENTRIGHTJOINSCOREONSTUDENT.sno1;-- 执行计划Filter: (sno 1) -- 变成过滤条件4.2 过滤条件下推规则结论3过滤条件只引用 Nonnullable-side 的表 → 可以下推过滤条件引用 Nullable-side 的表且是严格的 → 导致外连接消除变内连接后可下推过滤条件引用 Nullable-side 的表且是不严格的 →不能下推严格的定义输入NULL输出NULL精确的严格示例-- 严格过滤条件导致外连接消除SELECT*FROMSCORELEFTJOINCOURSEONTRUEWHERECOURSE.cno1;-- 执行计划Hash Join -- 变成内连接-- 不严格过滤条件不能下推SELECT*FROMSCORELEFTJOINCOURSEONTRUEWHERECOURSE.cnoISNULL;-- 执行计划Filter: (course.cno IS NULL) -- 保持为过滤条件4.3 连接顺序交换等式1.1(A leftjoin B on Pab) innerjoin C on Pac (A innerjoin C on Pac) leftjoin B on Pab等式1.2(A leftjoin B on Pab) leftjoin C on Pac (A leftjoin C on Pac) leftjoin B on Pab等式1.3(A leftjoin B on Pab) leftjoin C on Pbc A leftjoin (B leftjoin C on Pbc) on Pab条件Pbc must be strict半连接等式2(A semijoin B ON Pab) join C ON Pac (A join C ON Pac) semijoin B ON Pab反半连接等式3(A antijoin B ON Pab) join C ON Pac (A join C ON Pac) antijoin B ON Pab大原则SemiJoin ≈ InnerJoin 内表唯一化AntiJoin ≈ LeftJoin都含有补NULL逻辑五、关键函数分析5.1 deconstruct_recurse 函数作用递归遍历 Query-jointree为 RelOptInfo 分发约束条件建立逻辑连接关系。关键变量qualscope当前连接层次下所有表的rtindex集合inner_join_rels内连接涉及的表的rtindex集合nullable_rels/nonnullable_relsNullable-side / Nonnullable-side 表的集合below_outer_join是否在外连接的Nullable-side之下postponed_qual_list需要推迟分发的约束条件Lateral相关处理三种节点RangeTblRef设置 qualscopeinner_join_relsNULLFromExpr遍历 fromlist合并 sub_qualscope处理 child_postponed_qualsJoinExpr递归处理 larg/rarg根据连接类型设置各变量5.2 make_outerjoininfo 函数作用生成 SpecialJoinInfo 结构体记录外连接/半连接/反半连接的连接关系和顺序限制。SpecialJoinInfo 结构体typedefstructSpecialJoinInfo{Relids min_lefthand;// LHS出现的最小集Relids min_righthand;// RHS出现的最小集Relids syn_lefthand;// 语法中LHS的表集合Relids syn_righthand;// 语法中RHS的表集合JoinType jointype;// 连接类型bool lhs_strict;// 约束条件是否严格bool delay_upper_joins;// 阻止与上层交换顺序bool semi_can_btree;// 半连接是否可用B-treebool semi_can_hash;// 半连接是否可用HashList*semi_operators;// 半连接操作符List*semi_rhs_exprs;// 半连接右操作数}SpecialJoinInfo;最小集生成流程赋予初值min_lefthand clause_relids ∩ left_rels遍历下层 SpecialJoinInfo 限制连接顺序查看全局 PlaceHolderVar 链表加入涉及 Nullable-side 的表5.3 distribute_qual_to_rels 函数作用参照谓词下推规则对约束条件进行下推。三部分检查推理产生的约束条件is_deducedtrue一定是过滤条件或能下推的连接条件连接条件引用 Nonnullable-side不能下推is_pushed_downfalse过滤条件或能下推的连接条件is_pushed_downtrue检查外连接阻碍关键局部变量is_pushed_downtrue过滤条件false不能下推的连接条件outerjoin_delayed下推是否被外连接阻碍maybe_equivalence是否可用于生成等价类maybe_outer_join外连接情况下的等价类处理5.4 check_outerjoin_delay 函数作用检查约束条件下推是否被外连接阻碍设置delay_upper_joins标记处理特殊左连接情况阻碍条件约束条件引用了 Nullable-side 的表但未包含整个外连接的表集合5.5 生成等价类流程MergeJoinable 条件非常量表达式操作符表达式OpExpr两个参数操作符 MergeJoinableoprcanmerge true不含易失性函数process_equivalence 四种情况两端表达式在同一等价类 → 补充 RestrictInfo 信息两端表达式在不同等价类 → 合并等价类一端找到另一端未找到 → 加入找到的等价类两端都未找到 → 创建新的等价类六、优化技术6.1 PlaceHolderVar作用在子查询提升时对不严格的表达式进行封装保证逻辑等价。使用场景外连接 Nullable-side 的不严格表达式AppendRel 中的表达式Lateral 子查询引用上层表的属性结构体typedefstructPlaceHolderVar{Expr*phexpr;// 被封装的Var或表达式Relids phrels;// 子查询的表Index phid;// 唯一IDIndex phlevelsup;// 层次关系}PlaceHolderVar;6.2 消除无用连接项条件必须是左连接且内表是基表其他位置不出现内表的任何列连接条件中内表的列具有唯一性唯一性判断rel_is_distinct_for主键索引或UNIQUE索引DISTINCT子句GROUP BY子句空GROUP BY返回一行聚集函数无GROUP BYUNION/EXCEPT/INTERSECT无ALL6.3 Semi Join 消除条件内表保证唯一性时Semi Join可转换为Inner Join判断流程reduce_unique_semijoins → is_innerrel_unique_for → rel_is_distinct_for6.4 提取新的约束条件场景(sno1 AND cnamemath) OR (sno2 AND cnamephysics)提取结果sno 1 OR sno 2→ 下推到STUDENT表cname math OR cname physics→ 下推到COURSE表提取条件每个子句引用同一基表符合谓词下推规则不含易失性函数非常量约束条件选择率修正修正后选择率 原选择率 / 新提取条件选择率七、Lateral 语法支持7.1 语义分析在gram.y中添加LATERAL语法支持设置ParseState-p_lateral_active标记允许子查询引用上层表的属性7.2 收集 Lateral 变量find_lateral_references 函数遍历 RelOptInfo 数组查找 Lateral 列属性保存到RelOptInfo-lateral_vars7.3 收集 Lateral 信息create_lateral_join_info 函数direct_lateral_relids直接观察到的依赖关系lateral_relids传递闭包推理出的依赖关系lateral_varsLateral 变量列表lateral_referencers被依赖关系反向八、执行计划示例解析示例1等价类推理SELECT*FROMSTUDENT,SCORE,COURSEWHERECOURSE.cnoSTUDENT.snoANDSTUDENT.snoSCORE.sno;推理COURSE.cnoSTUDENT.sno AND STUDENT.snoSCORE.sno → COURSE.cnoSCORE.sno执行计划Hash Join (cost30.35..68.53 rows71 width69) Hash Cond: (score.sno course.cno) -- 推理出的新条件示例2连接条件下推SELECT*FROMSTUDENTLEFTJOINSCOREONSTUDENT.sno1;分析STUDENT.sno1 引用 Nonnullable-side不能下推执行计划Nested Loop Left Join Join Filter: (student.sno 1) -- 保持为连接条件示例3无用连接消除SELECTSCORE.snoFROMSCORELEFTJOINSTUDENTONSCORE.snoSTUDENT.sno;分析STUDENT表无其他引用且STUDENT.sno有主键唯一性执行计划Seq Scan on score -- STUDENT被消除九、本章小结核心转换RangeTblEntry → RelOptInfo从逻辑层到物理层等价类推理基于等值条件生成隐含约束条件扩充连接路径谓词下推根据连接类型Left/Semi/Anti决定约束条件是否可下推连接顺序交换遵循等价公式受外连接/半连接限制优化技术PlaceHolderVar、无用连接消除、Semi Join消除、OR条件提取难点外连接/半连接/反半连接引入后经典关系代数理论不再完全适用需要深入理解连接语义才能掌握谓词下推和顺序交换的规则。