大家好，欢迎来到IT知识分享网。

• 逻辑分解和物理优化产紧密
• 重写中,Query->Jointree通过Rangetblentry组织
  • 逻分中,Rangetblentry将建立对应Reloptlnfo
• Rangetblentry对应范围表
  • 对表描述,属逻辑层面
    • 内部没提供和物理代价及物理路径相关的成员变量
  • Reloptlnfo: 生成物理连接路径及计算路径代价,属物理层面

• 査询树中约東条件是表达式,只保存表达式本身内容

• 逻辑分解将这些裸用Restrictlnfo封装

  • 这样就可扩展表达式内容
  • Restrictlnfo中记录约束条件在物理优化中需要的变量

• Query中,约束条件存放位置就是它原始语法位置

  • 逻辑分解对它尝试下推
  • Restrictlnfo是为在下推时能更好和Reloptlnfo结合

• 逻辑分解阶段基于等价类推理,生成隐含约束
• A=B和B=C能推出新约束A=C
• 基于这种推理在物理优化时能生成更丰富连接路径

• 关系数据库引外和半连接,很多关系代数中的经典理论不适用
• 约束条件下推过程中
  • 由于外连接引入导致一些连接条件被延迟下推(delay)
• 谓词下推、连接顺序交换、基于等价类的推理是査询优化难点
  • 没透彻理解逻辑分解优化,物理优化理解就更难

4.1 创建RelOptInfo

• 查询树,基表信息以Rangetblentry放在Query->rtable中
• 查询优化后期,尤其物理优化, Rangetblentry保存的信息无法满足代价计算
  • 因为每个基表都生成扫描路径
  • 多基表间还产连接路径,且要计算这些路径代价
• 因此要新的RelOptInfo

4.1.1 RelOptInfo结构体

• 查询优化中,先面对FROM中表,称范围表
  • 常規意义表
  • 子查询
  • 查询结果的组织为表状的函数(如Tablefunction)
  • 处执行计划树的叶节点
    • 是查询结果的基础,称基表
• 基用Reloptlnfo表示
  • reloptkind是RELOPT_BASEREL
  • 基表间可连接,连接产生的“中间”结果也可用Reloptlnfo表示
    • reloptkind是RELOPT_JOINREL
• RELOPT_OTHER_MEMBER_REL类型的Reloptlnfo来表示
  • 继承表的子表或UNION操作的子查询
• Reloptlnfo多功能,庞大,分多部分介绍

typedef enum RelOptKind
{ 
   
	RELOPT_BASEREL,
	RELOPT_JOINREL,
	RELOPT_OTHER_MEMBER_REL,
	RELOPT_OTHER_JOINREL,
	RELOPT_UPPER_REL,
	RELOPT_OTHER_UPPER_REL,
	RELOPT_DEADREL
} RelOptKind;

/* * Is the given relation a simple relation i.e a base or "other" member * relation? */
#define IS_SIMPLE_REL(rel) \ ((rel)->reloptkind == RELOPT_BASEREL || \ (rel)->reloptkind == RELOPT_OTHER_MEMBER_REL)

/* Is the given relation a join relation? */
#define IS_JOIN_REL(rel) \ ((rel)->reloptkind == RELOPT_JOINREL || \ (rel)->reloptkind == RELOPT_OTHER_JOINREL)

typedef struct RelOptInfo
{ 
   
	NodeTag		type;

	RelOptKind	reloptkind;

	/* all relations included in this RelOptInfo */
	Relids		relids;			/* set of base relids (rangetable indexes) */

	/* size estimates generated by planner */
	double		rows;			/* estimated number of result tuples */

	/* per-relation planner control flags */
	bool		consider_startup;	/* keep cheap-startup-cost paths? */
	bool		consider_param_startup; /* ditto, for parameterized paths? */
	bool		consider_parallel;	/* consider parallel paths? */

	/* default result targetlist for Paths scanning this relation */
	struct PathTarget *reltarget;	/* list of Vars/Exprs, cost, width */

	/* materialization information */
	List	   *pathlist;		/* Path structures */
	List	   *ppilist;		/* ParamPathInfos used in pathlist */
	List	   *partial_pathlist;	/* partial Paths */
	struct Path *cheapest_startup_path;
	struct Path *cheapest_total_path;
	struct Path *cheapest_unique_path;
	List	   *cheapest_parameterized_paths;

	/* parameterization information needed for both base rels and join rels */
	/* (see also lateral_vars and lateral_referencers) */
	Relids		direct_lateral_relids;	/* rels directly laterally referenced */
	Relids		lateral_relids; /* minimum parameterization of rel */

	/* information about a base rel (not set for join rels!) */
	Index		relid;
	Oid			reltablespace;	/* containing tablespace */
	RTEKind		rtekind;		/* RELATION, SUBQUERY, FUNCTION, etc */
	AttrNumber	min_attr;		/* smallest attrno of rel (often <0) */
	AttrNumber	max_attr;		/* largest attrno of rel */
	Relids	   *attr_needed;	/* array indexed [min_attr .. max_attr] */
	int32	   *attr_widths;	/* array indexed [min_attr .. max_attr] */
	List	   *lateral_vars;	/* LATERAL Vars and PHVs referenced by rel */
	Relids		lateral_referencers;	/* rels that reference me laterally */
	List	   *indexlist;		/* list of IndexOptInfo */
	List	   *statlist;		/* list of StatisticExtInfo */
	BlockNumber pages;			/* size estimates derived from pg_class */
	double		tuples;
	double		allvisfrac;
	PlannerInfo *subroot;		/* if subquery */
	List	   *subplan_params; /* if subquery */
	int			rel_parallel_workers;	/* wanted number of parallel workers */

	/* Information about foreign tables and foreign joins */
	Oid			serverid;		/* identifies server for the table or join */
	Oid			userid;			/* identifies user to check access as */
	bool		useridiscurrent;	/* join is only valid for current user */
	/* use "struct FdwRoutine" to avoid including fdwapi.h here */
	struct FdwRoutine *fdwroutine;
	void	   *fdw_private;

	/* cache space for remembering if we have proven this relation unique */
	List	   *unique_for_rels;	/* known unique for these other relid * set(s) */
	List	   *non_unique_for_rels;	/* known not unique for these set(s) */

	/* used by various scans and joins: */
	List	   *baserestrictinfo;	/* RestrictInfo structures (if base rel) */
	QualCost	baserestrictcost;	/* cost of evaluating the above */
	Index		baserestrict_min_security;	/* min security_level found in * baserestrictinfo */
	List	   *joininfo;		/* RestrictInfo structures for join clauses * involving this rel */
	bool		has_eclass_joins;	/* T means joininfo is incomplete */

	/* used by partitionwise joins: */
	bool		consider_partitionwise_join;	/* consider partitionwise * join paths? (if * partitioned rel) */
	Relids		top_parent_relids;	/* Relids of topmost parents (if "other" * rel) */

	/* used for partitioned relations */
	PartitionScheme part_scheme;	/* Partitioning scheme. */
	int			nparts;			/* number of partitions */
	struct PartitionBoundInfoData *boundinfo;	/* Partition bounds */
	List	   *partition_qual; /* partition constraint */
	struct RelOptInfo **part_rels;	/* Array of RelOptInfos of partitions, * stored in the same order of bounds */
	List	  **partexprs;		/* Non-nullable partition key expressions. */
	List	  **nullable_partexprs; /* Nullable partition key expressions. */
	List	   *partitioned_child_rels; /* List of RT indexes. */
} RelOptInfo;

• 第一部分
  • Reloptlnfo公共变量
• RELOPT_BASEREL还JOINREL或其他类型
• 都用到

• Pg
  • 每条物理路径都会记录启动和整体
  • 代价计算是在路径创建后进行
  • 但Pg为提性,在连接路径创建前,会算一个初级的代价对连接路径“预检”,如果这条物理路径没优势,就不建
  • 这样能节省创建路径的消耗
• consider_startup和consider_param_startup
  • 在“预检”时是否比较启动代价
• 启动代价在有LIMIT时才重要(6章中关于代价介绍)
• tuple_fraction>0时consider_startup才有用

也就是tuple_fraction>0时，咱们才考虑那俩个变量哈哈哈！！！他妈的，俩布尔变量而已，也就是这个>0，才看那两个布尔变量！！哈哈哈

• param和startup类似
• 但针对参数化路径“预检”,且在Semi和Antijoin中才起作用(参照set_base_rel_consider_startup)
• 参数化路径目前只能是Nestloopjoin内表路径
  • 它的启动代价的意义不大
• 但Semijoin和 Enjoin
  • 每次对内表只要匹到一条记录就可,这时启动代价就有意义

consider_param_startup考虑参数化路径的启动代价，现在参数化路径目前只能是Nestloopjoin的内表路径，如果恰巧这个JOIn又是Semijoin或Antijoin，那这个consider_param_startup就起到大作用了

• 第二部分是基表(BASEREL)必用的

• Reloptlnfo还记录它自己
  • 如果作为内表时,是否UNIQUE

• 还记录一些扫描路径和连接路径有用的信息。

4.1.2 Indexoptlnfo结构体

• 如果一表有多，就有多个存在Reloptlnf-indexlist
  • 用于生成索引扫描、计算索引扫描代价、索引扫描结果是否有序
• B-tree索引扫描
  • B-tree索引有序,推出索引扫描结果也有序
    • 就给查询优化提供优化空间
  • 假如索引扫描的上层是Mergejoin
  • Mergejoin发现索引扫描结果本身就有序,就可省掉排序

• 唯一索引、主键、局部和表达式
• 唯一和主键在Pg中本质上都是唯一
  • Indexoptlnfo->unique表示唯一性
  • 对于可延退的唯一性约束需通过Indexoptlnfo->immediate表示
  • = false,就代表这个唯一性约束是可延退的,
  • 也就是说唯一性的检査延退到事务结束时,而不是在写入数据(如 INSERT)时检查

• 局部素引指带有约束条件的索引,
  • 约束条件存在Indexoptlnfo->indexpred
• 一个查询中的约束条件包含于局部索引的约束条件,
  • 那predOK可设为tue
  • 这样优化器就可决定是否可用局部索引来生成扫描路径

• 表达式索引指在索引的键值上存在表达式,
  • 它可是针对一个投影列进行表达式求值
  • 也可针对几个投影列的统一的投影列求值,
  • 表达式被统一存储在IndexOptinfo-> indexprs
• 只有查询中出现相同表达式时,
  • 表达式索引才会被采用

• 素引形式上分, 分
  • Btree素引、Hash素引
• 不同的索引, Pg提供不同(AccessMethod),保存在PG_AM
  • amhandler是访问方法的初始化方法,
  • Bree索引的访问方法在bthandler函数
  • Hash索引:hashhandler
• 这些 Xxxhandler
  • 初始化Indexamroutine结构体,
  • IndexAmroutine中的内容
    • 包括针对索引的操作方法(20个函数)和
    • 该类型的素引所有的一些属性。
• 初始化Indexoptlnfo时
  • Indexamroutine中的一个方法(代价估算方法)和
  • 一些属性也会被复制进来,方便给优化器参考

4.1.3 创建 Reloptlnfo

• Plannerlnfo(root)两数组
  • simple_rte_array和simple_rel_array
  • 记录Rangetblentry和Reloptlnfo,一一对应

但要记得，simple_rel_array记录的都是基表的指针，而simple_rte_array记录的是范围表的指针！

• setup_simple_rel_arrays
• 将Query->rtable中的Rangetblentry按顺序提取出
• 记录到 simple_rte_array

• add_base_rels_to_query中
• Query->jointree中的Rangetblref提取出,
• 且按simple_rte_aray中记录的顺序,
• 为每个Rangetbiref创建 Reloptlnfo,
• 也就是为每个Rangetblentry创建对应Reloptlnfo

最后一句话说的非也非也！

• Query->Jointree有三类
• Fromexpr、 Joinexpr和RangeTblref
• Fromexpr和JoinExpr的叶节点也一定是Rangetbiref
• 对Query->jointree深度遍历
  • 直到发现Rangetblref节点
  • 就创建对应的Reloptlnfo
• 且将Reloptlnfo的指针放到对应的Query->simple rel array

• 创建Reloptlnfo在build simple rel 中实现
• 这里创的是基表(含继承表的子表)对应的Reloptlnfo
• 如图4-2
  • 基表主要类型是RELOPT_ BASEREL和 RELOPT OTHER MEMBER REL
  • 基表又根据Rangetblentry>rtekind引申出来
  • 普通表、子查询、 VALUES子查询、函数型基表
  • 图4-2

• Reloptlnfo中大部分变量在创建时不能填
• 物理路径这阶段还没生成
  • 先设物理路径相关的成员变量NULL

• 普通表是最常用表
  • 可通过统计信息、索引信息来丰富Reloptlnfo
• 但子查询、 VALUES类型子查询等不存在统计信息
  • 在创建对应的Reloptlnfo时和普通表不同,
  • 普通表通过get_relation_info填充Reloptlnfo
• 其他类型基表只填min arrt、 max atr、 attr needed和 attr widths

• 普通表的信息获取函数get_relation_info
• 要关注两
  • 估计普通表规模( pages、 tuples)
  • 针对普通表的索引创建 IndexOptinfo来标示素引

• 普通表的规模估计estimate_rel_size中进行
• 对普通表的pages(块数)数量,可直接通过who获得
  • 方式(底层文件大小/块大小,Filesize/ Blocksize)

我记得文件块大小是8KB吧！

#define RelationGetNumberOfBlocks(reln) \ RelationGetNumberOfBlocksInFork(reln, MAIN_FORKNUM)


BlockNumber
RelationGetNumberOfBlocksInFork(Relation relation, ForkNumber forkNum)
{ 
   
	/* Open it at the smgr level if not already done */
	RelationOpenSmgr(relation);

	return smgrnblocks(relation->rd_smgr, forkNum);
}

• 要获得精确元组数就要高代价
  • 因此元组数量采用估计法
• 在统计信息模块,对每个普通表统计后,
  • 都在SYS_CLASS记录这个表当前的页面数和元组数估计值

按老陈觉得是pg_class这个表吧！！

• 设表上元组数和页面数线性增长
  • 那么单页面上元组的数量(元组密度)就不变
• 可通过SYS_CLASS里记录的元组数和页面数来获得元组密度
  • 然后调Relationgetnumberofblocks获得当前页面数
  • 页面密度$\times$当前页面数就可估计出当前元组数

pg_class这个表的数据不是实时的，我就先用那个时候的数据来算一下当时的密度，假设现在的密度和当时的一样，而且我还可以很机灵的获得当前的页面数，所以啊哈哈哈哈！！！

• 对做过TRUNCATE的表
  • 它在SYS_CLASS中记录的页面数是0

分母为零，咋算密度啊！那我就假设每个页面上的元组是满的吧，也就是密度=(8KB)/(元组长度)

• 这时设元组在页面内是“满”的
  • 即页面上所有的空间都用于存放元组,
  • 只要知道页面大小(BLOCKSZ),元组的长度(tuple_with)
  • 就可获得单页面存放的最大元组数量,即页面元组密度。

按老刘发出怒吼：这个tuple_width怎么算啊，你只需要注意到 int32 *attr_widths; /* array indexed [min_attr … max_attr] */

• 对带有索引的普通表,要为每个索引生成一个indexOptlnfo
• 索引大部分信息从索引的元信息中获得的
  • 键值信息、索引类型等
• 对非局部索引,它的元组数=普通表的元组数
  • 无须再次估计
• 对局部索引,estimate_rel_size估计它的元组数量

4.2 初识等价类

• 等价类的处理在约束条件下推后期引入
• 介绍约束下推前,先对等价类做一介绍
• 有A=B约東,
  • 操作符是等值操作符,
• 这种等值约束条件称“等价条件”
• 基于多个等价条件推理
  • 而获得的等价属性集合就是“等价类”

• 发现一个约束A=B
  • 通过这个约束而产生连接结果A和B一定=
  • 如果结果按A排序,那查询结果也一定按B排
• STUDENT.no= SCORE. Sno ORDER BY SCORE.sno,
  • 查询结果中的每一元组都符合STUDENT.sno= SCORE.sno,
  • 因此 STUDENT.sno和 SCORE.sno就构成一等价类
  • Order by中显式指定按 SCORE. sno
  • 但对等价类中的成员而言,只要其中的一个有序
  • 那结果中它们就全都有序

• 查询依照等价类推理产生新排序条件
  • 不是参照显式指定的SCORE.sno
  • 而参照STUDENT.sno

• 两约束A=B和B=C,易推出A=C,
  • 这时就可说{A,B,C}构成一个等价类
  • 可隐式构建出A=C的约束
• 生成物理路径的过程中
  • 由于隐式的约束条件A=C的存在,
  • 就可能“多”一条连接路径
  • 或许就多一更好选择

• COURSE和SCORE间没约東
• 生成物理路径阶段,如果对这两个表(参考第7章)连接,
  • 它们之间没有约束只能产生卡氏积连接路径
  • 基于等价类推理发现
    • COURSE.cno= SCORE.sno
  • 将COURSE和 SCORE间的连接结果“缩小”,也就降低路径代
    价

• 两约束A=B和B=5,
  • 能隐式构出A=5
  • 对于A=5这样的单属性(只涉及一个表)约束条件,
  • 或许能下推到基表上
  • 就可在对表扫描时把没用元组过滤掉

• 基于等价类的推理帮助査询优化器产生更多的物理路径,
• 但注意,在引入外连接(或半连接、反连接)后情况就会复杂
• 外连接中的A=B虽是等值连接条件
  • 但这时不能认为A=B
  • 外连接的查询结果对连接操作的Nullable-side可能会补NULL
  • 这时A和B就不相等
• 对大多数外连接
  • 无法生成等价类
  • 但其中会有一些特例
  • 我们可以在上面做文章

• 对SCORE扫描时增加SCORE.sno=1作过滤
  • SCORE.sno=1并不改变语句结果
• 原因:
  • STUDENT.sno=1作为过滤(STUDENT.Sno=1能谓词下推,下推到STUDENT)
  • 能在表扫描的过程中把STUDENT中所有 STUDENT.sno!=1的元组过滤掉
  • 因此扫描结果中的元组一定符合STUDENT.sno=1,那么用这个扫描结果和SCORE表做约東条件为STUDENT.sno= SCORE.sno的左连接,
  • SCORE.sno!=1的元组就不可能连接上
  • 因此SCORE.Sno=1不对连接结果有影响

上面的成功之处就在于利用了一个等价类，虽然这个是left join，但是增加了一个过滤条件并不影响结果！这个地方牛逼啊！

• 介绍等价类的数据结构
• EquivalenceClass结构体

• 等价类由等价类成员构成

• SELECT* FROM
  • STUDENT
    • LEFT JOIN
  • (SCORE INNER JOIN COURSE ON
    • SCORE.cno =COURSE.cno AND COURSE.cno =5)
  • ON STUDENT.sno =SCORE.sno
  • WHERE STUDENT.sno=1
  • 最终产生3个等价类
  • 这3个等价类会保存在 Plannerinfo->eq_classes

4.3谓词下推

• Reloptlnfo生成后保存在数组中
  • 基表已从树(Query->jointree)
  • 拉成线性(Plannerlnfo->simple_rel_array)
  • 査询树记录有哪些基表做了什么类型的连接(在Fromexpr、 Joinexpr中)
  • 各基表之间有哪些约束(连接条件和过滤条件)
  • 这种“扁平化”不易表现
• 因此,逻辑分解优化要
  • 将约束下推到Reloptlnfo
  • 将基表间的连接类型记录起来

4.3.1连接条件的下推

• 约東条件分连接和过滤
  • 作用略不同
  • 连接强调连接操作的计算过程
    • 外连接对没有连接上的元组补NULL
    • 所以对A=B连接条件产生的结果
      • 不一定满足A=B,有可能A和NULL
  • 过滤: 査询结果的过滤,信息筛选

• 如果只有内连接,就简单
  • 连接条件可直接下推到自己所涉及的表
• 约束student.sno==1,细分它是个连接条件,
  • 但它在执行计划中又被下推到STUDENT的扫描路径上,
  • 变成一个过滤条件
  • 这就减少了STUDENT扫描的结果数量,降低代价

• 结论1
  • 连接下推变成过滤
  • 过滤下推仍是过滤

• 引入外连接和(反)半连接后,变复杂
• 外连接中Nonnullable-side表没匹配上连接条件的元组也显示出来,且在表Nullable-side补NUL

• 连接条件引用Nullable-side的表
  • 连接可下推变成过滤
• 引用Nonnullable-side
  • 无法下推,仍是连接条件

• “强制”下推引用Nonnullable-side的连接条件会咋样?
  • 导致外连接的语义改变
  • 产生“非等价变换”

• 按左连接
• Nonnullable-side中的所有元组都应被投影
  • 而“强制”下推后,
  • 对 Nonnullable-side中的元组过滤
  • 导致部分元组无法显示
  • 因此“强制”下推错误

• 结论2:
• 如果连接条件引用Nonnullable-side
  • 那么连接条件不能下推
• 如果只引用Nullable-side的表
  • 那可下推

记住啊！是连接条件只引用Nullable-side，才可下推

• 目前连接条件只考虑Var= Const
• 对于Var=Var
• Var Op Var=var
• Func((Var)=Var都没验证
• 只需一个原则
  • 连接条件中引用Nonnullable-side的表,
  • 那这个连接条件就不能下推

连接条件只要碰到Nonnullable-side，就死掉了，没法下推喽！可怜死你了!

• 用3个表来代表普

• 顶层左连接Nullable-side是
  • (SCORE LEFT JOIN COURSE ON TRUE),
• 顶层左连接的Nonnullable-side是STUDENT
• STUDENT.sno=1引用STUDENT表中的列
• 不能被下推

• 连接条件引用的表都在( SCORE LEFT JOIN COURSE ON TRUE)中,
• 把(SCORE LEFT JOIN COURSE ON TRUE)看成整体
• 它就处于顶层左连接的Nullable-side
• 也就是说连接条件是能下降的,结合结论1和结论2

4.3.2过滤条件的下推

• 连接已变成过滤
• 那这个子查询中的过滤条件能继续下推吗

• 连接条件下推到子査询中之后变成过滤
• 例1和例2中“下推后”语句的子査询提取出
• 单看这两个子查询的执行计划
• 过滤条件SCORE.cno=1被下推到SCORE上
  • 执行计划里仍然是左连接

• 如果过滤只引用Nonnullable-side,那过滤能下推到 Nonnullable-side
• 如果过滤引用Nullable-side且过滤条件是严格,那导致外连接变成内连接
• 内连接情况下,过滤条件显然也能下推到对应表上
• 如果过滤条件引用Nullable-side的表且过滤条件不严格,
  • 如下所示,过滤条件不能下推

• 结论3:
• 如果过滤只引用Nonnullable-side,那能下推
• 如果引用Nullable-side且过滤条件是严格的
  • 那会导致外连接消除
  • 外连接消除之后变成内连接
  • 过滤条件也能下推

4.3.3连接顺序

• 构建约束条件下推示例时

• 有意避开:

• (A leftioin B) leftioin C

here

4.3.4 deconstruct recurse

• 子查询提升阶段还是预处理表达式阶段都对Query->jointrees递归处理
• 逻辑分解优化过程中,仍需对Jointree递归处理,
  • 这次之后Jointree就正式“退休”了,
• 后续的主要工作就由Query->simple_rel array接手了。
• simple rel array中的 Reloptlnfo已创建好了,
  • 但它信息还没有填充完,
  • 这次递归遍历目的是给这些 Reloptlnfo分发约束条件,
  • 且要把它们的逻辑连接关系建立好

• deconstruct recurse对 Query–jointree的递归遍历仍然分成3部分,分别处理RangeTbIRef、 FromExpr和 JoinExpr,
• 且对FromExpr和 JoinExpr做深度遍历,直到发现RangeTbIRef叶节点
• deconstruct_recurse函数有一些重要变量
• qualscope
  • 在当前连接层次之下出现的所有表的reindex集合
• inner join rels记录在当前连接层次之下所有的内连接涉及的表的 reindex集合
• nul able_rels/ nonnullable_rels两个变量出现在对 Joinexpr进行处理的时候,它们分别记录连接中的 Nullable-side/ Nonnullable-side表的 reindex集合
• below outer_ join变量默认false,递归遍历过程中,
  • 如果遇到了外连接和(反)半连接,这个值就调整。
  • 在对外连接的 Nullable-side遍历时,需递归调用deconstruct recurse函数, below outer join变量在这时设置为true;在对反半连接的RHS端遍历时,同样需递归调用 deconstruct recurse函数, below outer join变量这时也被设置为true。

/* * deconstruct_jointree * Recursively scan the query's join tree for WHERE and JOIN/ON qual * clauses, and add these to the appropriate restrictinfo and joininfo * lists belonging to base RelOptInfos. Also, add SpecialJoinInfo nodes * to root->join_info_list for any outer joins appearing in the query tree. * Return a "joinlist" data structure showing the join order decisions * that need to be made by make_one_rel(). * * The "joinlist" result is a list of items that are either RangeTblRef * jointree nodes or sub-joinlists. All the items at the same level of * joinlist must be joined in an order to be determined by make_one_rel() * (note that legal orders may be constrained by SpecialJoinInfo nodes). * A sub-joinlist represents a subproblem to be planned separately. Currently * sub-joinlists arise only from FULL OUTER JOIN or when collapsing of * subproblems is stopped by join_collapse_limit or from_collapse_limit. * * NOTE: when dealing with inner joins, it is appropriate to let a qual clause * be evaluated at the lowest level where all the variables it mentions are * available. However, we cannot push a qual down into the nullable side(s) * of an outer join since the qual might eliminate matching rows and cause a * NULL row to be incorrectly emitted by the join. Therefore, we artificially * OR the minimum-relids of such an outer join into the required_relids of * clauses appearing above it. This forces those clauses to be delayed until * application of the outer join (or maybe even higher in the join tree). */
List *
deconstruct_jointree(PlannerInfo *root)
{ 
   
	List	   *result;
	Relids		qualscope;
	Relids		inner_join_rels;
	List	   *postponed_qual_list = NIL;

	/* Start recursion at top of jointree */
	Assert(root->parse->jointree != NULL &&
		   IsA(root->parse->jointree, FromExpr));

	/* this is filled as we scan the jointree */
	root->nullable_baserels = NULL;

	result = deconstruct_recurse(root, (Node *) root->parse->jointree, false,
								 &qualscope, &inner_join_rels,
								 &postponed_qual_list);

	/* Shouldn't be any leftover quals */
	Assert(postponed_qual_list == NIL);

	return result;
}

/* * deconstruct_recurse * One recursion level of deconstruct_jointree processing. * * Inputs: * jtnode is the jointree node to examine * below_outer_join is true if this node is within the nullable side of a * higher-level outer join * Outputs: * *qualscope gets the set of base Relids syntactically included in this * jointree node (do not modify or free this, as it may also be pointed * to by RestrictInfo and SpecialJoinInfo nodes) * *inner_join_rels gets the set of base Relids syntactically included in * inner joins appearing at or below this jointree node (do not modify * or free this, either) * *postponed_qual_list is a list of PostponedQual structs, which we can * add quals to if they turn out to belong to a higher join level * Return value is the appropriate joinlist for this jointree node * * In addition, entries will be added to root->join_info_list for outer joins. */
static List *
deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
					Relids *qualscope, Relids *inner_join_rels,
					List **postponed_qual_list)