复用关系子集，搜索多表连接计划
PostgreSQL 按参与连接的关系数量逐层生成候选，把同一关系集合的路径归入同一 RelOptInfo，复用已经分析的子问题。
工程问题#
多表查询存在许多连接顺序与执行方式。若从头枚举每一棵连接树，同一组表的中间连接会被反复分析；但只贪心选择当前估计最便宜的一次连接，又可能错失后续可用的顺序或路径。
实际实现#
standard_join_search 将初始关系放入 join_rel_level[1]，逐层调用 join_search_one_level。后者把较小且不重叠的关系集合组合起来，既考虑与单个关系连接，也考虑满足连接条件或顺序限制的 bushy 计划。build_join_rel 按关系集合复用 RelOptInfo；每层生成相关路径后再调用 set_cheapest 保存成本最低的候选。
处理流程#
- 把初始 jointree 项作为第一层状态，每个状态表示一个关系集合及其可用路径
- 从第 2 层开始，组合已经生成且关系集合不重叠的较小状态
- 检查连接条件、外连接等顺序限制，生成合法连接路径；必要时才考虑笛卡尔积
- 把同一关系集合的路径放到同一 RelOptInfo，完成当前层后确定其最便宜路径
- 继续扩展到覆盖全部初始关系的状态，交给后续规划阶段处理
源码片段#
固定版本 · 原文摘录3433 root->join_rel_level = (List **) palloc0((levels_needed + 1) * sizeof(List *));34343435 root->join_rel_level[1] = initial_rels;34363437 for (lev = 2; lev <= levels_needed; lev++)3438 {3439 ListCell *lc;34403441 /*3442 * Determine all possible pairs of relations to be joined at this3443 * level, and build paths for making each one from every available3444 * pair of lower-level relations.3445 */3446 join_search_one_level(root, lev);第一层保存初始关系；每一层只依赖已经生成的较小关系集合，构成自底向上的动态规划顺序。
178 for_each_from(r2, joinrels[other_level], first_rel)179 {180 RelOptInfo *new_rel = (RelOptInfo *) lfirst(r2);181182 if (!bms_overlap(old_rel->relids, new_rel->relids))183 {184 /*185 * OK, we can build a rel of the right level from this186 * pair of rels. Do so if there is at least one relevant187 * join clause or join order restriction.188 */189 if (have_relevant_joinclause(root, old_rel, new_rel) ||190 have_join_order_restriction(root, old_rel, new_rel))191 {192 (void) make_join_rel(root, old_rel, new_rel);193 }194 }195 }bms_overlap 排除重复包含的关系。bushy 连接只在存在相关连接条件或顺序限制时生成，以控制规划规模；其他分支会在必要时处理笛卡尔积。
679 /*680 * See if we already have a joinrel for this set of base rels.681 */682 joinrel = find_join_rel(root, joinrelids);683684 if (joinrel)685 {686 /*687 * Yes, so we only need to figure the restrictlist for this particular688 * pair of component relations.689 */690 if (restrictlist_ptr)691 *restrictlist_ptr = build_joinrel_restrictlist(root,692 joinrel,693 outer_rel,694 inner_rel,695 sjinfo);696 return joinrel;697 }相同 joinrelids 对应同一个 RelOptInfo，即便它由不同的左右关系组合得到。这个分支仍重新生成该组合的限制条件，不能直接复用任意旧 restrictlist。
3458 foreach(lc, root->join_rel_level[lev])3459 {3460 rel = (RelOptInfo *) lfirst(lc);34613462 /* Create paths for partitionwise joins. */3463 generate_partitionwise_join_paths(root, rel);34643465 /*3466 * Except for the topmost scan/join rel, consider gathering3467 * partial paths. We'll do the same for the topmost scan/join rel3468 * once we know the final targetlist (see grouping_planner's and3469 * its call to apply_scanjoin_target_to_paths).3470 */3471 if (!bms_equal(rel->relids, root->all_query_rels))3472 generate_useful_gather_paths(root, rel, false);34733474 /* Find and save the cheapest paths for this rel */3475 set_cheapest(rel);当前层所有组合生成完毕后，补分区连接和可用 Gather 路径，再保存这个关系集合最便宜的路径；这里比较的是估计成本。
依次展示逐层调度、子集组合、同一集合复用与成本归纳。RelOptInfo 保存路径列表和多个 cheapest 字段；set_cheapest 并不是丢弃所有其他路径，仅靠此摘录不能推导一个精确、统一的规划复杂度。
收益与取舍#
工程分析带来的收益
- 按关系集合复用子问题，避免每种连接树都重新建立同一集合的规划对象
- 保留不同路径属性，再由成本比较裁剪；不把一个集合简单压成单个标量
- 连接条件和顺序约束可减少无意义组合
付出的代价
- 子集及其分割数量仍可能指数增长；动态规划不等于多表连接规划具有多项式复杂度
- 成本依据统计和估计，估计最便宜不保证实际运行最快；路径裁剪也受到排序、参数化等属性约束
- 不能任意交换外连接、LATERAL 等受约束连接；大查询可能走 GEQO 或插件钩子，而不进入本文路径
可比较的选择
GEQO 遗传搜索达到配置阈值且启用 GEQO 时，PostgreSQL 用启发式搜索控制规划开销；避免穷举大量组合，但不保证找到同一搜索空间的最优解。
贪心连接顺序逐步选择当前看起来代价最小的连接，规划工作更少；没有同等的候选保留能力，早期决定可能限制后续更好的组合。
版本与适用范围#
固定 PostgreSQL REL_17_0，针对 standard_join_search 的传统连接搜索。初始项可以是已经规划的子连接，不应一概叫作单张物理表。join_search_hook 和启用后的 GEQO 可替代此路径；这不是 SQL 执行阶段的连接算法，也不代表所有合法 SQL 计划均被穷举。
参考来源#
源码、官方文档与原始论文src/backend/optimizer/path/allpaths.c · make_rel_from_joinlist / standard_join_search
src/backend/optimizer/path/joinrels.c · join_search_one_level