Postgresql源码（133）优化器动态规划生成连接路径的实例分析

mingjie

修改于 2024-10-10 16:38:50

1030

修改于 2024-10-10 16:38:50

文章被收录于专栏：Postgresql源码分析

物理算子的生成分为两步，基表的扫描路径生成set_base_rel_pathlists；连接路径生成（make_rel_from_joinlist动态规划）。本篇简单分析实现。
看过代码会发现，“基表的扫描路径生成”其实就是作为连接路径生成dp计算的第一层数据，然后逐层拼接上新的连接节点，每层选一个局部最优的在留几个有序的，就进入到下一层计算。一般有几张表相连就会有几层计算。
入口函数：make_one_rel

1 物理算子基表扫描路径生成set_base_rel_pathlists

set_base_rel_sizes
- 为查询计划中每个基本关系估计大小；预估的行数、行宽；决定是否并行。
set_base_rel_pathlists
- 为查询计划中每个基本关系找到所有可用的扫描路径。包括顺序扫描、索引扫描。识别出所有扫描路径将它们附加到对应基本关系的 pathlist 字段中。

生成基础关系的path：set_base_rel_pathlists，执行后生成的PATH在RelOptInfo数组中保存：

(gdb) p *root->simple_rel_array[1]->pathlist
$37 = {type = T_List, length = 2, max_length = 5, elements = 0x2a2aa40, initial_elements = 0x2a2aa40}

RelOptInfo数组和RTE数组是对应的：

(gdb) p root->simple_rte_array[1]->relid
$40 = 16471

生成结果实例

2 物理算子连接路径生成make_rel_from_joinlist

经过set_base_rel_pathlists生成扫描路径，每个基表的RelOptInfo都记录了若干条path，这些基表作为扫描的基础节点，再次基础上继续构造连接物理算子。

standard_join_search用动态规划方法来尝试不同的连接顺序和组合：

初始化：从initial_rels提供的初始关系开始，dp的起点。
逐层连接：每一层都会尝试将现有的连接关系与另一个关系结合，形成新的连接关系。
搜索连接顺序：对于每一对可能的连接关系，函数会考虑所有可能的连接方法（如嵌套循环连接、散列连接等），生成一个或多个path。
评估和选择：每个生成的path都会评估成本，优化器会选择成本最低的path作为该连接步骤的最佳路径。
最终结果：返回将所有原始关系连接在一起的结果。

make_rel_from_joinlist

standard_join_search
	...
	// levels_needed = 3 三张表
	root->join_rel_level = (List **) palloc0((levels_needed + 1) * sizeof(List *));

这里是第一层，有三个RelOptInfo（student、course、teacher）

	root->join_rel_level[1] = initial_rels;

从第2层开始处理：

	for (lev = 2; lev <= levels_needed; lev++)
	{
		ListCell   *lc;

搜索一个层级，拿到的所有RelOptInfo可能得组合，把可能的组合放到root->join_rel_levellev中。
join_rel_levellev记录的是RelOptInfo指针，每个RelOptInfo表示一个关系，一个关系可能带多个path。

		join_search_one_level(root, lev);

在连接搜索的一个层级完成后，为每个连接关系生成额外的路径（如分区连接路径和聚合路径），并确定每个连接关系成本最低路径：

		foreach(lc, root->join_rel_level[lev])
		{
			rel = (RelOptInfo *) lfirst(lc);

			generate_partitionwise_join_paths(root, rel);

			if (!bms_equal(rel->relids, root->all_query_rels))
				generate_useful_gather_paths(root, rel, false);

			/* Find and save the cheapest paths for this rel */
			set_cheapest(rel);
		}
	}

三层路径生成实例

第一层有三张基表的RelOptInfo
- RelOptInfo
  - path : student(seq)
  - path : student(idx)
- RelOptInfo
  - path : score(seq)
  - path : score(索引)
  - path : score(覆盖索引)
- RelOptInfo
  - path : course(seq)
  - path : course(索引)
  - path : course(覆盖索引)
- 虽然seq的代价最小，但第一层也保留了索引扫的path，因为本层代价最小的情况不一定是全局代价最小的情况，还需要保留一些有序的path方便后面节点使用。
第二层返回了两个RelOptInfo，里面的路径都是两张表拼接的结果
- RelOptInfo
  - path : Hash(score(seq), student(seq))
- RelOptInfo
  - path : Hash(score(seq), course(seq)) <<<< 第三层选择
  - path : Nestloop(score(索引), Material(course(seq)))
  - path : Nestloop(score(覆盖索引), Material(course(seq)))
第三层返回了一个RelOptInfo，代表最终路径
- RelOptInfo
  - path : Hash(Hash(score(seq), student(seq)),course(seq))

3 实例

drop table student;
create table student(sno int primary key, sname varchar(10), ssex int);
insert into student values(1, 'stu1', 0);
insert into student values(2, 'stu2', 1);
insert into student values(3, 'stu3', 1);
insert into student values(4, 'stu4', 0);

drop table course;
create table course(cno int primary key, cname varchar(10), tno int);
insert into course values(1, 'meth', 10);
insert into course values(2, 'english', 11);

drop table teacher;
create table teacher(tno int primary key, tname varchar(10), tsex int);
insert into teacher values(10, 'te1', 1);
insert into teacher values(11, 'te2', 0);

drop table score;
create table score (sno int, cno int, degree int);
create index idx_score_sno on score(sno);
insert into score values (1, 10, 100);
insert into score values (1, 11, 89);
insert into score values (2, 10, 99);
insert into score values (2, 11, 90);
insert into score values (3, 10, 87);
insert into score values (3, 11, 20);
insert into score values (4, 10, 60);
insert into score values (4, 11, 70);


explain 
SELECT * 
FROM STUDENT 
LEFT JOIN SCORE ON STUDENT.sno = SCORE.sno
LEFT JOIN COURSE ON SCORE.cno = COURSE.cno;

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-05-22，如有侵权请联系 cloudcommunity@tencent.com 删除

腾讯技术创作特训营S9