PostgreSQL——查询优化——生成路径1

2021SC@SDUSC

概述

我负责的PostgreSQL代码部分：查询的编译与执行
此篇博客的分析内容：查询优化——生成路径
查询优化的整个过程可以分为预处理，生成路径和生成计划三个阶段。在上一篇博客中，我分析了查询优化的第一个阶段——预处理。这篇博客分析查询优化的第二个阶段——生成路径。在关系数据库中和非关系数据库对比，最大的特色是支持表的连接。但是表的连接结果会因连接顺序的不同而不同，所以同一组表的连接结果可能有多个。表的连接在逻辑上，我们可以看做是一棵连接树，每一棵连接树在PostgreSQL中都被称作是一条路径。因为同一组表的连接结果会有多条路径，所以查询优化的工作是：从一系列等效路径中选取效率最高的路径并形成执行计划

query_planner函数

生成路径的工作是由query_planner函数来完成的。为一个基本的查询(可能涉及连接)生成访问路径
query_planner函数执行流程

query_planner(PlannerInfo *root,
			  query_pathkeys_callback qp_callback, void *qp_extra)
{
    
	Query	   *parse = root->parse;//查询树
	List	   *joinlist;//连接表
	RelOptInfo *final_rel;//最后生成的路径结果存放在RelOptInfo结构体中返回

	//初始化planner中的相关变量
	root->join_rel_list = NIL;
	root->join_rel_hash = NULL;
	root->join_rel_level = NULL;
	root->join_cur_level = 0;
	root->canon_pathkeys = NIL;
	root->left_join_clauses = NIL;
	root->right_join_clauses = NIL;
	root->full_join_clauses = NIL;
	root->join_info_list = NIL;
	root->placeholder_list = NIL;
	root->fkey_list = NIL;
	root->initial_rels = NIL;

	//调用setup_simple_rel_arrays函数将范围表扁平化，以便更快地访问，并为索引基本关系设置一个空数组。
	setup_simple_rel_arrays(root);

	//判断jointree->fromlist是否为空，即该表是否为简单表而不是连接表
	Assert(parse->jointree->fromlist != NIL);
	//处理fromlist字段只有一个表的情况即无表连接
	if (list_length(parse->jointree->fromlist) == 1)
	{
              //取出连接表的fromlist字段，并将其转化为node节点形式
		Node	   *jtnode = (Node *) linitial(parse->jointree->fromlist);

		if (IsA(jtnode, RangeTblRef))//取出连接表的fromlist字段是否为范围表即from子句
		{
    
			int			varno = ((RangeTblRef *) jtnode)->rtindex;//获取该节点在r_table即范围表中的位置
			RangeTblEntry *rte = root->simple_rte_array[varno];//根据上一步获得的r_table的位置，取出该表的RTE

			Assert(rte != NULL);//判断RTE是否为空
			if (rte->rtekind == RTE_RESULT)//判断RTE的种类是否为空的from子句
			{
    
				//为查询中的基本表关系构建RelOptInfo节点
				final_rel = build_simple_rel(root, varno, NULL);

基本表就是 FROM 后指定的一个普通的表，而不是由连接等操作生成的表。

			//如果查询在一般情况下允许并行性，检查是否有并行限制。
				if (root->glob->parallelModeOK &&
					force_parallel_mode != FORCE_PARALLEL_OFF)
					final_rel->consider_parallel =
						is_parallel_safe(root, parse->jointree->quals);//判断是否是安全的并行

				//添加访问路径
				add_path(final_rel, (Path *)
						 create_group_result_path(root, final_rel,
												  final_rel->reltarget,
												  (List *) parse->jointree->quals));

				//选择最优的访问路径，并将最优路径放在最后返回的PlannerInfo结构体中
				set_cheapest(final_rel);
				//回调函数
				(*qp_callback) (root, qp_extra);
				//返回的PlannerInfo结构体中存放的最优路径
				return final_rel;
			}
		}
	}
	//处理fromlist字段>1的情况即有多个表的连接的情况
	
	setup_append_rel_array(root);//用每个AppendRelInfo填充append rel数组，允许通过子relid直接查找

	//在 add_base_rels_to_query() 中初始化每个 RelOptInfo
	add_base_rels_to_query(root, (Node *) parse->jointree);

	
	 //检查targetlist和join树，为所有引用的占位符添加条目到baserel targetlists，并为所有引用的占位符生成占位信息条目。
	build_base_rel_tlists(root, root->processed_tlist);

    //查找级联引用
	find_lateral_references(root);
  //deconstruct_jointree() 调用完成后，会返回一个上述的连接链表，同时针对每个基本表的扫描或连接限制条件，都存入了各自的 RelOptInfo 的 baserestrictinfo/joininfo 中
	joinlist = deconstruct_jointree(root);

	 //处理隐含的等式条件
	generate_base_implied_equalities(root);

	 //规范化pathkeys
	(*qp_callback) (root, qp_extra);

	//移除没有用上的外部连接
	joinlist = remove_useless_joins(root, joinlist);
	//将任何具有唯一内部关系的半连接减少为普通的内部连接
	reduce_unique_semijoins(root);
	//构建级联参考
	create_lateral_join_info(root);

	// 将外键与等价类相匹配并添加配额。这一步必须在最终确定等价类后进行，这样就可以跳过处理参与删除关系的外键。
	match_foreign_keys_to_quals(root);
	//提取or子句的限制条件
	extract_restriction_or_clauses(root);

	//现在通过添加其他表来扩展
	add_other_rels_to_query(root);

	 //调用make_one_rel函数返回查询路径
	final_rel = make_one_rel(root, joinlist);
    //检查是否得到可用的路径
	if (!final_rel || !final_rel->cheapest_total_path ||
		final_rel->cheapest_total_path->param_info != NULL)
		//没有可用路径则报错
		elog(ERROR, "failed to construct the join relation");
	//返回的PlannerInfo结构体中存放的最优路径
	return final_rel;
}

RelOptInfo结构体

RelOptInfo结构体是贯穿整个路径生成过程的一个数据结构，生成路径的最终结果始终存放其中，生成和选择路径所需的许多数据也存放在其中。路径生成和选择涉及的所有操作，几乎都是针对RelOptInfo结构体操作。

RelOptInfo结构体涉及baserel(基本关系)和joinrel(连接关系)。baserel(基本关系)是一个普通表，子查询或者范围表中出现的函数。joinrel(连接关系)是两个或者两个以上的baserel(基本关系)在一定约束条件下的简单合并。对任何一组baserel仅有一个joinrel，即对于任何给定的baserel集合，只有一个RelOptInfo结构体。例如：连接{a,b,c}是用同一个RelOptInfo结构体表示，无论a,b,c这三个baserel连接的顺序是什么样的。因为对于joinrel(连接关系)来说，baserel之间是没有顺序的。至于这三个baserel之间是以什么样的路径（连接顺序，方式）连接成{a,b,c}形式的连接，则记录在RelOptInfo结构体中的pathlist字段中。

typedef struct RelOptInfo
{
    
	NodeTag		type;//节点类型

	RelOptKind	reloptkind;//关系的类型（基本关系类型，连接关系类型，其他成员关系类型）

	Relids		relids;		//关系所涉及的基本表（在范围表中的编号）

	double		rows;		//估计的元组数量
	bool		consider_startup;	//是否考虑启动成本?是,需要保留启动成本低的路径
	bool		consider_param_startup; //是否考虑参数化?的路径
	bool		consider_parallel;	//是否考虑并行处理路径

	List	   *pathlist;	//多个基本关系生成该关系的路径
	List	   *ppilist;	  //路径链表中的ParamPathInfos链表
	List	   *partial_pathlist;	  //并行部分路径
	struct Path *cheapest_startup_path;//最小的启动代价的路径
	struct Path *cheapest_total_path;//最小的总代价的路径
	struct Path *cheapest_unique_path;//最小的唯一代价的路径
	List	   *cheapest_parameterized_paths; //参数化代价最低的路径

	Relids		direct_lateral_relids;	//使用lateral语法,需依赖的Relids
	Relids		lateral_relids;  //rel的最小化参数信息
	
	Index		relid;//当前关系在范围表中的编号
	Oid			reltablespace;	/* containing tablespace */
	RTEKind		rtekind;		//基本关系的类型（普通关系，子查询，函数等）
	AttrNumber	min_attr;		//关系中最小的字段编号
	AttrNumber	max_attr;		//关系中最大的字段编号
	Relids	   *attr_needed;	//连接关系中哪些字段是需要的
	int32	   *attr_widths;	//每个字段的宽度的估计
	List	   *lateral_vars;	  //关系依赖的LATERAL Vars/PHVs
	Relids		lateral_referencers;	  //依赖该关系的Relids
	List	   *indexlist;		//索引关系的信息
	List	   *statlist;		 //统计信息链表
	BlockNumber pages;		//关系占用的页面数
	double		tuples;     //关系的元组数
	PlannerInfo *subroot;		//如为子查询,存储子查询的root
	List	   *subplan_params;  //如为子查询,存储子查询的参数
	int			rel_parallel_workers;	 //并行执行,需要多少个workers，记录workers数量
	Oid			serverid;		 //表或连接的服务器标识符
	Oid			userid;			  //用户id标识
	bool		useridiscurrent;	  //标识当前用户，对于当前用户来说,连接才是有效的
	struct FdwRoutine *fdwroutine;    //使用结构体FdwRoutine,避免包含头文件fdwapi.h

	List	   *unique_for_rels;	 //已知的,可保证唯一的Relids链表
	List	   *non_unique_for_rels;	//已知的,不唯一的Relids链表
	
	List	   *baserestrictinfo;	//如为基本关系,存储约束条件链表
	QualCost	baserestrictcost;	 //解析约束表达式的成本
	Index		baserestrict_min_security;	 //在baserestrictinfo中最低安全等级
	List	   *joininfo;	//连接子句中调用该关系时的约束信息
	bool		has_eclass_joins;	//是否存在等值连接

	bool		consider_partitionwise_join;	  //是否考虑使用partitionwise join
	Relids		top_parent_relids;	  //最高层的父关系Relids

	PartitionScheme part_scheme; //分区的schema 
	int			nparts;			//分区数 
	struct PartitionBoundInfoData *boundinfo;	 //分区边界信息 
	List	   *partition_qual;  //分区约束
	struct RelOptInfo **part_rels;	  //分区的RelOptInfo数组
	List	  **partexprs;		   //非空分区键表达式链表
	List	  **nullable_partexprs;  //可为空的分区键表达式 
	List	   *partitioned_child_rels; // 分区子表RT Indexes链表 
} RelOptInfo;

Path结构体

在上面介绍的RelOptInfo中，变量pathlist记录的是生成该RelOptInfo在某方面较优的路径，其中路径中每一个节点都是一个path结构，path结构也成为路径。在pathlist中，每一个path节点对应的具体路径节点则存放的是构成该路径的具体信息，包括表连接的方式，顺序，以及参加连接的baserel的访问方式。

typedef struct Path
{
    
	NodeTag		type;    //节点类型

	NodeTag		pathtype;		//标记扫描/连接方法

	RelOptInfo *parent;			//此路径所构建的关系
	double		rows;			//估计的结果元组的数量
	Cost		startup_cost;	//执行此路径的启动代价估计
	Cost		total_cost;		//执行此路径的总代价估计
	List	   *pathkeys;		//此路径的输出的排序信息
} Path;

query_planner函数调用的——make_one_rel函数

make_one_rel函数找出执行查询的所有可能访问路径。make_one_rel函数分为两个阶段:生成扫描路径(set_base_rel_pathlists)和生成连接路径(make_rel_from_joinlist).

make_one_rel(PlannerInfo *root, List *joinlist)
{
    	
//传入参数List *joinlist：这个链表中每一个节点都代表一个基本关系，该基本关系可能表示一个范围表或者是一个子查询

	RelOptInfo *rel;//RelOptInfo结构体，存储最终路径以及路径查找的相关信息
	Index		rti;//记录当前关系在范围表中的编号
	double		total_pages; //关系占用的页面数

	//构建All_baserels Relids集合
	root->all_baserels = NULL;//初始将它置空
	for (rti = 1; rti < root->simple_rel_array_size; rti++)//遍历RelOptInfo
	{
    
		RelOptInfo *brel = root->simple_rel_array[rti];//取得关系

		//检查上一步获得的brel即获取的关系是否为空
		if (brel == NULL)
			continue;
      //检查该关系是否在范围表中
		Assert(brel->relid == rti);

		//如果不是brel的reloptkind字段的类型不是基本表则忽略（说明该关系是连接关系而不是基本关系）
		if (brel->reloptkind != RELOPT_BASEREL)
			continue;
       //如果是基本表的话，则将它加入基本表链表中
		root->all_baserels = bms_add_member(root->all_baserels, brel->relid);
	}

	//设置RelOptInfo的consider_param_startup变量,是否考量fast-start plans
	set_base_rel_consider_startup(root);
   //估算Relation的Size并且设置consider_parallel标记
	set_base_rel_sizes(root);

	 //计算总表页数
	total_pages = 0;//总表页数初始化为0
	for (rti = 1; rti < root->simple_rel_array_size; rti++)//遍历每一个RelOptInfo结构体
	{
    		//取得关系
		RelOptInfo *brel = root->simple_rel_array[rti];
		//如果关系为空则忽略
		if (brel == NULL)
			continue;
		//检查该关系是否在范围表中
		Assert(brel->relid == rti);
		
		//上面取得的brel类型是否为简单表
		if (IS_SIMPLE_REL(brel))
			total_pages += (double) brel->pages;//如果是简单表则将该表的页数累加到总页数上
	}
	root->total_table_pages = total_pages;//返回计算好的总页数即关系占用的页面数

	//调用set_base_rel_pathlists函数，生成基本关系的访问路径（即为每个基本关系生成一个RelOptInfo结构并生成路径）放在其
	//RelOptInfo的pathlist字段中，对应动态规划算法中的第一层（动态规划算法讲解见下面）
	set_base_rel_pathlists(root);

	//调用make_rel_from_joinlist函数生成最终路径返回一个代表连接所有基本关系的RelOptInfo结构，它的pathlist字段就是所有的最终路径组成的链表，对应动态规划算法的第2层到第n层。（动态规划算法讲解见下面）
	rel = make_rel_from_joinlist(root, joinlist);

	//返回最上层的RelOptInfo结构体
	return rel;
}

make_one_rel函数调用的—— set_base_rel_pathlists函数

函数set_base_rel_pathlists负责为基本关系生成访问路径，它扫描范围表中的所有的基本关系并考虑顺序扫描和所有可用的索引扫描最后把每个值得保留的路径加入到基本关系的RelOptInfo结构的pathlist字段中。（所谓值得保留的路径即：1总代价最优；2启动代价最优；3有最好的排序结果）

set_base_rel_pathlists(PlannerInfo *root)
{
    
	Index		rti;//记录当前关系在范围表中的编号

	for (rti = 1; rti < root->simple_rel_array_size; rti++)//遍历每一个RelOptInfo结构体
	{
    		//取得关系
		RelOptInfo *rel = root->simple_rel_array[rti];

		//如果关系为空则忽略
		if (rel == NULL)
			continue;
		//检查该关系是否在范围表中
		Assert(rel->relid == rti);	
       //调用set_rel_pathlist函数，为基本表添加访问路径
		set_rel_pathlist(root, rel, rti, root->simple_rte_array[rti]);
	}
}

make_one_rel函数调用的—— make_rel_from_joinlist函数

make_rel_from_joinlist函数会将传入参数joinlist中的基本关系连接起来生成最终的连接关系并且为最终的连接关系建立RelOptInfo结构，其pathlist字段就是最终路径组成的链表。该函数的实质就是选择不同的连接方式作为中间节点，选择不同的连接顺序将代表基本关系的叶子结点连接成一棵树，使其代价最小。

make_rel_from_joinlist(PlannerInfo *root, List *joinlist)
{
    	//传入参数List *joinlist：这个链表中每一个节点都代表一个基本关系，该基本关系可能表示一个范围表或者是一个子查询
	int			levels_needed;//动态规划算法所需的层数，和joinlist链表的长度相同
	List	   *initial_rels;//存储所有第一层关系的RelOptInfo结构
	ListCell   *jl;//临时变量 节点

	levels_needed = list_length(joinlist);//动态规划算法所需的层数，和joinlist链表的长度相同
//判断动态规划算法的层数
	if (levels_needed <= 0)//如果动态规划算法的层数为0则直接返回null
		return NULL;		

	initial_rels = NIL;//将initial_rels初始化为空即没有存储第一层关系的RelOptInfo结构
	foreach(jl, joinlist)//遍历joinlist链表
	{
    
		Node	   *jlnode = (Node *) lfirst(jl);
		RelOptInfo *thisrel;

		if (IsA(jlnode, RangeTblRef))//如果是一个基本关系
		{
    
			int			varno = ((RangeTblRef *) jlnode)->rtindex;

			thisrel = find_base_rel(root, varno);//将基本关系的RelOptInfo结构装入动态规划算法的第一层关系
		}
		else if (IsA(jlnode, List))//判断joinlist中的基本关系是否为一个子查询
		{
    
			//如果joinlist中的基本关系为一个子查询递归调用make_rel_from_joinlist函数为子查询生成路径
			thisrel = make_rel_from_joinlist(root, (List *) jlnode);
		}
		else
		{
    
			elog(ERROR, "unrecognized joinlist node type: %d",
				 (int) nodeTag(jlnode));
			thisrel = NULL;		
		}
//将所有第一层关系的RelOptInfo结构放入initial_rels链表中
		initial_rels = lappend(initial_rels, thisrel);
	}
//如果动态规划算法所需层数为1则表示from子句中只有一项那么可以将initial_rels中第一个节点对应的RelOptInfo作为最终的连接关系路径返回
	if (levels_needed == 1)
	{
    
		//将initial_rels中第一个节点对应的RelOptInfo作为最终的连接关系路径返回
		return (RelOptInfo *) linitial(initial_rels);
	}
	//如果动态规划算法所需层数>1
	else
	{
    
		//将initial_rels中存储的第一个节点对应的RelOptInfo记录到root中，方便后续的其他函数可以调用它
		root->initial_rels = initial_rels;

		if (join_search_hook)//使用全局变量join_search_hook调用的第三方函数来进行路径生成
			return (*join_search_hook) (root, levels_needed, initial_rels);
		else if (enable_geqo && levels_needed >= geqo_threshold)//启用了遗传算法并且动态规划算法所需层数超过了遗传算法的触发值，将利用遗传算法完成路径生成
			return geqo(root, levels_needed, initial_rels);
		else //使用standard_join_search函数实现动态规划算法
			return standard_join_search(root, levels_needed, initial_rels);
	}
}

路径生成算法

动态规划算法

在 PostgreSQL 中，通常情况下是使用动态规划来获得最优的路径的

动态规划算法
（1）初始
初始状态下，为每一个待连接的 baserel生成基本关系访问路径，选出最优路径。这些关系称为第1层中间关系。把所有的由n个关系连接生成的中间关系称为第n 层关系。
（2）归纳
已知第1 ~n- 1层的路径，用下列方法生成第n层的关系(n >1):将第n-1层的关系分别与每个第1层的关系连接，并在各自最优路径的基础上，生成使用不同连接方法的路径。若n>3，将第n -2层的关系分别与每个第2层的关系连接，n-3层的关系分别与每个第3层的关系连接，并在各自最优路径的基础上，生成使用不同连接方法的路径，并依此类推。3）生成第n层关系后，选出每个第n层关系的最优路径作为结果。
（3）生成第n层关系后选出每个第n层关系的最优路径作为结果

遗传算法

动态规划算法是生成路径的默认算法，但在有些情况下，检查一个查询所有可能的路径会花去很多的时间和内存空间，特别是所要执行的查询涉及大量的关系的时候。在这种情况下，为了在合理的时间里判断一个合理的执行计划，PostgreSQL将使用遗传算法生成路径。是否启用遗传算法由两个因素决定:在系统配置中是否允许使用遗传算法以及需要连接的基本关系是否超过使用遗传算法的阙值。

在PostgreSQL中，遗传算法将路径作为个体，将个体以某种方式编码（个体体现了连接顺序)，然后通过重组得到后代，考虑连接代价来计算后代的适应值，再选择合适的后代进行下一次迭代。当到达一定的迭代次数之后，遗传算法终止。选择遗传算法可以减少生成路径的时间，但是遗传算法并不一定能找到“最好”的规划，它只能找到相对较优的路径。

总结

通过此篇源码分析，了解到了PostgreSQL查询优化的生成路径阶段的主要函数。

感谢批评指正